Lar(m, c, l) grammars

Abstract

We present the class of LAR(M, C, L) context-free grammars: a generalization of several classes of fixed and arbitrary lookahead LR grammars that appear in the literature. The parser construction is based on three parameters M, C and L; M and C determine the type of parser, and L is the amount of lookahead. Specific settings of these parameters yield fixed-lookahead grammar classes such as LALR(k), SLR(k) and NQLALR, along with several arbitrary lookahead classes, all of which are subsets of LR-Regular. Thus both fixed and arbitrary lookahead LR techniques are described (and implemented) by one powerful model.

Keywords:

• LALR(k)
• SLR(k)
• NQLALR(l)
• Lookahead FSA
• LR-Regular
• LAR(M, C, L)

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
• context-free grammar
• LR parsing