Re: LL(1) BNF validator wanted

Michael.Bergman@eua.ericsson.se (Michael Bergman) writes:
|> There was a lot of discussions about LL, LALR and language theory in this
|> group about a year ago. I followed everything closely and the conclusion
|> was that it is not possible to *decide* whether an unambiguous CFG is
|> LL(k).


You may be confusing languages and grammars. It is certainly possible to
decide whether a grammar is LL(k), and every decent LL(k) parser generator
will check it and warn the user if the grammar is not LL(k).


As far as I remember, there was a discussion about the problem of
transforming an arbitrary CFG into an LL(k) grammar. For this it would be
necessary to decide whether the *language* described by the CFG was LL(k)
(in other words, whether there was an LL(k)-grammar for the language at
all). This problem may be undecidable, but I don't remember the discussion
that well.


- anton
--
M. Anton Ertl anton@mips.complang.tuwien.ac.at
--

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