Content deleted Content added
move link to Further reading |
m Typo fixing and cleanup, typos fixed: conficts → conflicts using AWB |
||
Line 28:
The LALR parser and its alternatives, the SLR parser and the [[Canonical LR parser]], have similar methods and parsing tables; their main difference is in the mathematical grammar analysis algorithm used by the parser generation tool. LALR generators accept more grammars than do SLR generators, but fewer grammars than full LR(1). Full LR involves much larger parse tables and is avoided unless clearly needed for some particular computer language. Real computer languages can often be expressed as LALR(1) grammars. In cases where they can't, a LALR(2) grammar is usually adequate. If the parser generator allows only LALR(1) grammars, the parser typically calls some hand-written code whenever it encounters constructs needing extended lookahead.
Similar to an [[SLR parser]] and Canonical LR parser generator, an LALR parser generator constructs the LR(0) state machine first and then computes the lookahead sets for all rules in the grammar, checking for ambiguity. The Canonical LR constructs full lookahead sets. LALR uses merge sets, that is it merges lookahead sets where the LR(0) core is the same. The SLR uses [[LR(1)#FIRST and FOLLOW sets|FOLLOW]] sets as lookahead sets which associate the right hand side of a LR(0) core to a lookahead terminal. This is a greater simplification that in the case of LALR because many
==See also==
Line 42:
* [http://www.cs.dartmouth.edu/~mckeeman/cs48/mxcom/doc/knuth65.pdf On the translation of languages from left to right, Knuth, D.E., Information and Control 8, 607-639 (1965)]
* [http://computer-refuge.org/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-065.pdf Practical Translators for LR(k) Languages, DeRemer, F.L., PhD Dissertation, M.I.T. (1969)]
[[Category:Parser generators]]
| |||