Re: LALR(1) differences to LR(1)

haberg@math.su.se (Hans Aberg)
1 Nov 2005 21:45:23 -0500

          From comp.compilers
Related articles
LALR(1) differences to LR(1) aegis@scientist.com (aegis) (2005-11-01)
Re: LALR(1) differences to LR(1) haberg@math.su.se (2005-11-01)
Re: LALR(1) differences to LR(1) branco.medeiros@gmail.com (2005-11-08)
Re: LALR(1) differences to LR(1) parsersinc@earthlink.net (SLK Parsers) (2005-11-12)
| List of all articles for this month |
From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 1 Nov 2005 21:45:23 -0500
Organization: Mathematics
References: 05-11-001
Keywords: LALR
Posted-Date: 01 Nov 2005 21:45:23 EST

"aegis" <aegis@scientist.com> wrote:


> In what regard is LALR(1) more strict than LR(1)? From what I have
> read they both perform lookaheads when parsing. What are the other
> additional restrictions associated with LALR(1)? Also, what is
> considered a follow set in contrast with a lookahead set?


LALR(1) is a state compaction of the result of the LR(1)-algorithm, which
does not work with all LR(1) grammars. The LALR(1) machine (formally
"push-down automaton"), when encountering an error token, will (as the
LR(1) machine) not read any further tokens, but may (unlike LR(1)) perform
additional rule reductions (and their actions).


LALR(1) is historically preferred due to lack of and expense of computer
memory, which today perhaps cannot serve as a motivation.


LR(1) seems better in various modern uses, such as more exact error
recovery, tools that predict lookahead, and GLR parsers.


> The book I am reading is lex and yacc and also reading the bison
> manual.


The book by Aho, Ullman & Sethi, "Compilers..." ("Dragon book") has a
description.


--
    Hans Aberg

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.