Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!olivea!mintaka!spdcc!iecc!compilers-sender From: jml@wally.altair.fr (Jean-Marie [John] Larcheveque) Newsgroups: comp.compilers Subject: Re: Technical question about yacc and LALR parsers Keywords: yacc, parse, errors Message-ID: <2091@seti.inria.fr> Date: 22 Apr 91 13:55:48 GMT References: <9104210204.AA07587@florida.HQ.Ileaf.COM> Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: jml@wally.altair.fr (Jean-Marie [John] Larcheveque) Organization: Gip Altair/INRIA, France Lines: 28 Approved: compilers@iecc.cambridge.ma.us 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 or -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.