A general model for fixed look-ahead lr parsers

Abstract

A single construction method for SLR, LALR, NQLALR and NQSLR parsers is presented. The latter two are generalizations of NQLALR(l) grammars, defined for the first time here. The construction method is based on two relations that capture the essential structure of the problem of computing fixed look-ahead for LR parsers. These relations capture both the similarities and the differences among the various techniques, which have been misunderstood in the past. Three parameters are used to specify the type of parser to be constructed and the amount of look-ahead to be used.

Keywords:

• Context-free Grammar
• LALR(k)
• SLR(k)
• NQLALR(1)
• look-ahead FSA

Categories and Subject Descriptors:

• D.3.1 [Programming Languages]
• Formal Definitions and Theory—syntax
• D.3.4 [Programming Languages]
• Processors—translator writing systems and compiler generators
• F.4.2 [Mathematical Logic and Formal Languages]:
• Grammars and Other Rewriting Systems—parsing

General Terms:

• Algorithms
• languages
• theory