- LALR parser
In
computer science , a lookahead LR parser or LALR parser is a specialized form ofLR parser that can deal with morecontext-free grammar s than Simple LR (SLR)parser s. 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 theparsing table s it requires. It is these types of parsers that are most often generated bycompiler-compiler s such asyacc andGNU 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.
References
* Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. "" 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 [http://www.cs.mdx.ac.uk/staffpages/r_bornat/#vanitypublishing] .)See also
*
LALR Parser Generator
*Lookahead External links
* [http://jscc.jmksf.com/ JS/CC] Interactive online implementation of a LALR(1) parser generator running in the web-browser.
Wikimedia Foundation. 2010.
