Re: Where reductions in LALR?

Sylvain Schmitz <schmitz@i3s.unice.fr>
4 Sep 2005 10:32:16 -0400

          From comp.compilers

Related articles
Where reductions in LALR? tubylerczyk@wp.pl (tubylerczyk) (2005-09-03)
Re: Where reductions in LALR? schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-09-04)
Re: Where reductions in LALR? 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-09-04)
Re: Where reductions in LALR? cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-09-07)
| List of all articles for this month |

From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 4 Sep 2005 10:32:16 -0400
Organization: Compilers Central
References: 05-09-016
Keywords: LALR, parse
Posted-Date: 04 Sep 2005 10:32:16 EDT

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



Post a followup to this message

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