LALR parser

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help improve the introduction to meet Wikipedia's layout standards. You can discuss the issue on the talk page.

In computer science, Look-Ahead LR parsers or LALR parsers are a specialized form of LR parsers that can deal with more context-free grammars than Simple LR parsers but fewer than LR(1) parsers 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.

[edit] References

Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison--Wesley, 1986. (Describes the traditional techniques for building LALR(1) parsers.)
Frank DeRemer and Thomas Pennello. Efficient Computation of LALR(1) Look-Ahead Sets. ACM Transactions on Programming Languages and Systems (TOPLAS) 4:4, pp. 615–649. 1982. (Describes a more efficient technique for building LALR(1) parsers.)
Richard Bornat Understanding and Writing Compilers, Macmillan, 1979. (Describes the principles of automated left-to-right parsing and how to construct the parser tables, what a follow set is, etc., in English, not mathematics.)