Re: Technical question about yacc and LALR parsers

In article <9104210204.AA07587@florida.HQ.Ileaf.COM>
jar@florida.HQ.Ileaf.COM (Jim Roskind x5570) observes that, from the
verbose output of yacc, one can infer that a given parse state is always
reached through the same terminal/nonterminal transition, and asks if this
property is true of all LALR parsers.


The construction algorithm given in the Dragon book for SLR tables will
always yield parsers with this property. Indeed, a new state is
constructed from existing ones by picking a state and a transition symbol
and deriving the kernel items of the new state by moving the dot past this
symbol. So all the kernel items of a given state have the same symbol to
the left of the dot. Now, since LALR construction does not involve
merging states with different cores (i.e. sets of LR(0) items), the same
property holds for LALR. The problem is, however, that some "LALR" parser
generators might carry out further mergers. But I think that, beyond LALR,
you can still merge parts of tables, but not whole states, because no two
states will have exactly the same actions and transitions. You do find
aggressive optimizations after which it is difficult to recognize the
original LALR states, as in the Syntax compiler compiler, described in
Boullier's thesis (Universite d'Orleans, France), but this is hardly
likely to happen in the various implementations of yacc.


--
Jean-Marie (John) Larcheveque
<jml@bdblues.altair.fr> or <jml@nuri.inria.fr>
--

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