Re: LL(1) BNF validator wanted

Eric Promislow (emp@xgml.com) writes:


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


Our moderator writes:


> [Yacc, being a LALR parser generator, is unlikely to give you much insight
> into LL(1)-ness. -John]


Oddly enough, an LALR(1) tool can give you sufficient conditions for a
grammar to be LL(1) as well. Unfortunately, because there is at least one
(contrived) grammar that is LL(1) that is not LALR(1), therefore, YACC
cannot be used to determine if a grammar is NOT LL(1).


Here's the cool idea (with kudos to a proof by Brosgol in his 74 PhD
thesis at Harvard, I think):


Given a (LALR(1)) grammar, G:


[1] Construct G' by placing a unique action on the extreme left
edge of each production of G.


[2] Run YACC on G'. If G' is still LALR(1), it is also LL(1).


I.e., do this


a : {} A
    | {} B
    ;


and then run YACC on it. The rule "cracking" to force actions to a
"reduce" is the key to the mechanism here.


By placing actions at the left edge of productions, the LALR parser is
forced to know its position in the grammar at the left edge of every rule
rather than at the right edge; which implies that it must be able to
predict which production it will apply; hence, if the augmented grammar is
LALR, the grammar must also be LL.


The explicit corollary I wrote a while back on LALR(1) is thus:


Corollary: G' member LALR(k) is a sufficient, BUT NOT NECESSARY, condition
for the corresponding LALR(k) grammar, G, to be LL(k). For the proof,
send me email.


Regards,
Terence Parr (parrt@acm.org)
"Cool Tools Dept."
AHPCRC, U of MN
--

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