Re: LL(1) BNF validator wanted

: 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)? YACC is a last resort, since I have to do more to the
: BNF grammar than I would like.


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


I don't know of any tool/argorithm that just points out all the
*non*-LL(1) constructs, but I've done quite a lot of rewriting from LALR-
ish to LL(1). It works OK if you're not afraid of pedantic work and the
grammar in question is not too big/complicated. My feeling is that it is
very difficult indeed to device an algorithm that indicates the non-LL
constructs since the degree of ambiguity would be enormous. To be of any
use it must know how humans read a grammar (I'm assuming the LL(1) grammar
you want is intended for human eyes) and hence it must somehow decide
where the "fault" is so you can rewrite in some reasonable way.


There are some programs/algorithms that can try to transform a grammar to
LL(1) and when it fails, you're stuck since it being stuck does not prove
the grammar is not LL(1). The methods do work quite well on a "reasonable"
set of "ad hoc" grammars though.


Send me email if you want more info, I can't post all the material I've
got to comp.compilers.


Regards,
M
--
Michael Bergman Email: euambn@eua.ericsson.se
EUA/XO Phone: +46 8 7275709
Ellemtel Telecom Systems Labs, Armborstv 14, S-125 25 Alvsjo, Sweden
--

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