LALR parser
From Wikipedia, the free encyclopedia
In computer science, a lookahead LR parser or LALR parser is a specialized form of LR parser that can deal with more context-free grammars than Simple LR (SLR) parsers. 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 most often 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 item I in state S 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.
Properties of LALR:
- Cost is Manageable
- Efficiency is very high.
- It is the intermediate between SLR and canonical LR.
[edit] References
- Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools Addison--Wesley, 1986. (AKA The Dragon Book, 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 – available freely from the author's page at [1].)
[edit] See also
[edit] External links
- JS/CC Interactive online implementation of a LALR(1) parser generator running in the web-browser.
