Abstract

A grammar is LR{1} if it can be parsed deterministically from left to right while looking ahead no more than one symbol. Because of the difficulty in generating full LR{l) parsers, many parser generators such as YACC limit themselves to LALR(1} grammars which are a subset of the LR{l) grammars.

Unlike other algorithms in the literature for testing whether a grammar is LR{l), the algorithm presented here uses only the characteristic finite state machine and other structures necessary for creating an LALR{l) parser. Thus, if a parser generator finds that a grammar is not LALR{l), with little additional work the parser generator can test whether the grammar is LR{l). The methodology used for testing can also be employed to generate a full LR{l) parser.

Department(s)

Computer Science

Comments

This paper has been submitted for publication to Information Processing Letters.

Keywords and Phrases

Compilers, Formal Languages, Language Processors, LR(l) Grammars, LR(l) Parsing

Report Number

Csc-91-18

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