Re: LR Grammars not in LALR(1) or LR(1)

"tj bandrowsky" <tbandrow@unitedsoftworks.com> wrote:


>Are there examples of grammars that are GLR but not LR(1) or LALR(1)?


I do not know the definition of GLR, but I have an old book by Robin
Hunter, "Compilers...", which says on page 103 that LR(k) grammars are
LR(1) grammars, and even LR(0) if each sentence is given an
end-marker, citing a paper by Hopcroft and Ullman, "Introduction to
Automata Theory, Languages and Computation" 1979.


It also says, p. 105, that for each fixed k, it is decidable whether a
grammar is LR(k), but undecidable for a given grammar if there is a k such
that it is LR(k).


These grammar rewritings are just syntactic in the sense that if one
attaches semantics to the language, the rewriting may screw that up, at
least from the practical point of view. Therefore these theoretically
possible grammar rewritings have not been of much practical use.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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