LR-regular grammars An extension of LR(k) grammars

1 October 1971

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02724847,p. 153-165
https://doi.org/10.1109/swat.1971.17

Abstract

LR-regular grammars are defined similarly to Knuth's LR(k) grammars, with the following exception. Arbitrarily long look-ahead is allowed before making a parsing decision during the bottom-up syntactical analysis; however, this look-ahead is restricted in that the essential "lookahead information" can be represented by a finite number of regular sets, thus can be computed by a finite state machine. LR-regular grammars can be parsed deterministically in linear time by a rather simple two-scan algorithm. Efficient parsers are constructed for given LR-regular grammars. The family of LR-regular languages is studied; it properly includes the family of deterministic CF languages and has similar properties. Necessary and sufficient conditions for a grammar to be LR-regular are derived and then utilized for developing parser generation techniques for arbitrary grammars.

Keywords

This publication has 10 references indexed in Scilit:

Properties of deterministic top-down grammars
Information and Control, 1970
Abstract families of deterministic languages
Published by Association for Computing Machinery (ACM) ,1969
A regularity test for pushdown machines
Information and Control, 1967
A proposal for definitions in ALGOL
Communications of the ACM, 1967
Structural equivalence of context-free grammars
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1967
Deterministic context free languages
Information and Control, 1966
The introduction of definitional facilities into higher level programming languages
Published by Association for Computing Machinery (ACM) ,1966
On the translation of languages from left to right
Information and Control, 1965
Bounded context syntactic analysis
Communications of the ACM, 1964
Syntactic Analysis and Operator Precedence
Journal of the ACM, 1963