LALR parser

In computer programming, an LALR parser or Look-ahead LR(left to right) parser is a specific type of LR parser that can deal with more context-free grammars than SLR parsers but less than LR(1) parserss can. It is a very popular type of parser because it gives a good trade-off between the number of grammars it can deal with and the size of the parsing tables it requires. It is these types of parsers that are generated by compiler-compilers such as yacc and GNU bison.

Like SLR, LALR is a refinement to the technique for constructing LR(0) parse tables. While SLR uses FOLLOW sets to construct reduce actions, LALR uses LOOKAHEAD sets, which are more specific because they take more of the parsing context into account. FOLLOW sets are associated with a symbol, while LOOKAHEAD sets are specific to an LR(0) item and a parser state.

Specifically, the FOLLOW set for a given LR(0) item I in a given parser state S contains all symbols that are allowed by the grammar to appear after I's left-hand-side nonterminal. In contrast, the LOOKAHEAD set for I contains only those symbols that are allowed by the grammar to appear after I's right-hand-side has been parsed starting from state S. FOLLOW(I) is effectively the union of the LOOKAHEAD sets for all LR(0) items with the same left-hand-side as I, regardless of parser states or right-hand-sides, therefore losing all context information. Because the LOOKAHEAD set is specific to a particular parsing context, it can be more selective, therefore allowing finer distinctions than the FOLLOW set.

To do: The LALR algorithm for generating a parsing table