Re: LL(1) BNF validator wanted

Michael Bergman <Michael.Bergman@eua.ericsson.se> wrote:
>: Is there a tool out there that can take a BNF (or BNF-like)
>: description of a language and indicate all parts of the grammar that
>: are not LL(1)?
>
>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).


This might be just nit-picking, but surely it is always possible to decide
if a particular *grammar* is LL(k)? The Dragon book gives an easily-
computable algorithm for deciding if a grammar is LL(1) (p. 192 in my
edition) based on FIRST and FOLLOW sets, which could be extended to LL(k)
grammars in an obvious way.


Note that the question "is G an LL(k) grammar?" is different than
    - can G be transformed to an LL(k) grammar?
    - is there an LL(k) grammar for the language G describes?


Which are certainly undecidable for arbitrary CFGs, and probably
undecidable for unambiguous CFGs too (though I don't see how you would
prove that off the top of my head).


Since one is easy, and the others are (probably) undecidable, it's worth
while to be clear which one is meant...


>I don't know of any tool/argorithm that just points out all the
>*non*-LL(1) constructs,


I would think that any of the LL(1)-based parser constructors out there
would have to include that as a subset of its functionality, similar to
the way yacc & related tools report shift/shift and shift/reduce errors.
--

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