Re: Where reductions in LALR?

tubylerczyk wrote:
> This way I find lookaaheads for items in state 8,9,10 and 11
> I find all are #, but in table in book reduction in this state are for
> any terminal symbol, not only end of stream
> What is mean? If lookaheads is # I must reduce for ALL symbols when
> state <> 1 ? Or maybe in state 8,9,10,11 lookaheads are set of all
> symbols? How is would created?


If you look at states 8, 9, 10 and 11, you will notice the knowledge of
the lookahead is not necessary in order to make a deterministic
decision: the LR(0) automaton is already powerful enough to decide the
reductions using rules 2, 3, 4 and 5 respectively.


Conversely, in states 5 and 7, the LR(0) automaton is in (shift/reduce)
conflict, and we need the LALR(1) lookaheads in order to choose between
the parsing actions.


The obvious rationale for not using the lookaheads, and basing our
decisions on the LR(0) states only, is that it allows efficient parsing
tables compression: the last four rows of your parsing table can be
represented by a single table with one default reduction for each state:
four memory slots instead of twenty.


> Note that LALR tables (differs to SLR) often have state with the same
> reduction for all terminal symbols.


The same mechanism is also working for SLR parsing: use the LR(0) parser
most of the time, and use the SLR lookaheads when necessary.


--
Hope that helps,


      Sylvain

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