Re: LL(1) BNF validator wanted

dave@cs.arizona.edu (Dave Schaumann)
Wed, 2 Feb 1994 22:31:26 GMT

          From comp.compilers

Related articles
LL(1) BNF validator wanted emp@xgml.com (1994-01-31)
Re: LL(1) BNF validator wanted mw@ipx2.rz.uni-mannheim.de (1994-01-31)
Re: LL(1) BNF validator wanted Michael.Bergman@eua.ericsson.se (1994-02-01)
Re: LL(1) BNF validator wanted parag@netcom.com (1994-02-01)
Re: LL(1) BNF validator wanted anton@mips.complang.tuwien.ac.at (1994-02-02)
Re: LL(1) BNF validator wanted gary@intrepid.com (1994-02-02)
Re: LL(1) BNF validator wanted dave@cs.arizona.edu (1994-02-02)
Re: LL(1) BNF validator wanted parrt@s1.arc.umn.edu (Terence Parr) (1994-02-04)
Re: LL(1) BNF validator wanted adrian@dcs.rhbnc.ac.uk (1994-02-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: dave@cs.arizona.edu (Dave Schaumann)
Keywords: LL(1), tools
Organization: University of Arizona CS Department, Tucson AZ
References: 94-01-135 94-02-008
Date: Wed, 2 Feb 1994 22:31:26 GMT

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.
--


Post a followup to this message

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