LALR parser generator: Difference between revisions

Revision as of 17:53, 10 July 2012

Revision as of 17:54, 10 July 2012

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 conficts may arise from LR(0) cores sharing the same right hand side and lookahead terminal, conflicts that are not present in LALR. This why SLR has less language recognition power than LALR with Canonical LR being stronger than both since it does not include any simplifications.

==See also==