Abstract

The MINLRl algorithm for finding minimal deterministic parsers for LR(1) grammars is presented. MINLRl also detects whether a grammar is LR(l) with little more work than building the grammar's LALR(l) parser. MINLRl starts by building the characteristic finite state machine, CFSM, for the input grammar and then checks for LR(l)ness. If the input grammar is LR(l), MINLRl transforms the CFSM into a minimal LR(l) parser by creating extra copies of certain states of the CFSM as necessary. The complexity of the algorithm is O(n3l2v2) where n is the number of states in the parser, l is the size of the input grammar and v is the number of symbols in the input grammar. Minimal is defined as not being a proper refinement of any deterministic LR-parser.

Department(s)

Computer Science

Comments

This paper has been submitted for publication to the IEEE Computer Society 1992 International Conference on Computer Languages to be held in April 1992.

Keywords and Phrases

LR(l) grammars, LR(l) parsing

Report Number

CSc-91-20

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1991 University of Missouri - Rolla, All rights reserved

Publication Date

10 November 1991

Download

Share

 
COinS