Wed, 2 Feb 1994 22:31:26 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: | 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.