Fri, 4 Feb 1994 18:29:52 GMT

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

Newsgroups: | comp.compilers |

From: | "Terence Parr" <parrt@s1.arc.umn.edu> |

Keywords: | LL(1), tools |

Organization: | Compilers Central |

References: | 94-01-135 94-02-008 |

Date: | Fri, 4 Feb 1994 18:29:52 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.