10 Mar 2001 16:00:09 -0500

Related articles |
---|

detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-02-15) |

Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-02-17) |

Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-02-23) |

Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-01) |

Re: detecting ambiguous grammars henry@spsystems.net (2001-03-04) |

Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-04) |

Re: detecting ambiguous grammars davidpereira@home.com (David Pereira) (2001-03-08) |

Re: detecting ambiguous grammars dlester@cs.man.ac.uk (2001-03-10) |

Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-12) |

Re: detecting ambiguous grammars christian.bau@isltd.insignia.com (2001-03-22) |

Re: detecting ambiguous grammars thant@acm.org (Thant Tessman) (2001-03-26) |

Re: detecting ambiguous grammars joachim_d@gmx.de (Joachim Durchholz) (2001-03-26) |

Re: detecting ambiguous grammars cfc@world.std.com (Chris F Clark) (2001-03-27) |

Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27) |

[8 later articles] |

From: | dlester@cs.man.ac.uk (David Lester) |

Newsgroups: | comp.compilers |

Date: | 10 Mar 2001 16:00:09 -0500 |

Organization: | Dept Computer Science, University of Manchester, U.K. |

References: | 01-02-080 01-03-020 01-03-032 |

Keywords: | parse |

Posted-Date: | 10 Mar 2001 16:00:09 EST |

Thant Tessman <thant@acm.org> writes:

*> Thanks to everyone who's responded.*

*>*

*> Joachim Durchholz wrote:*

*>*

*> [...]*

*>*

*> > Note that the Earley algorithm will parse any string against any*

*> > context-free grammar, but it will not tell you whether the grammar*

*> > is ambiguous, it will tell you whether that particular string can be*

*> > parsed in an ambiguous manner (and give you all the relevant parse*

*> > trees as well). [...]*

*>*

*> Ah! This is what motivated my question. A few years ago, without*

*> knowing the "right" way to parse a grammar (other than using lex and*

*> yacc), I implemented exactly this. I was delighted because the*

*> implementation was very concise--about two pages of Scheme code. But*

*> its strength is its weakness. The ability to get all possible parse*

*> trees is pretty cool, but of course there is also an advantage to*

*> knowing absolutely that a given grammar isn't ambiguous.*

*>*

*> The earlier responses I got to my original question convinced me to*

*> revisit the dragon book (this time armed with a pot of coffee), but*

*> the fact that there are production compilers that use an Earley parser*

*> leads me to ask: Does the use of an Earley parser offend people's*

*> sense of programming language design aesthetics if one is able and*

*> required to make it explicit which parse tree is to be preferred?*

If you'd like a context-free grammar against which to try using your

system in deciding ambiguity, how about:

S -> A | B

A -> x A x | x

B -> B_0 B_0

...

B_i -> B_{i+1} B_{i+1}

...

B_n -> x

The language is: "x(xx)* | x^(2^(n+1))". The grammar is not ambiguous

(but not LR(1), or anything else useful either).

Notice that one subtle change, leads to ambiguity after 1+2^(n+1)

terminals have been considered.

S -> A | B

A -> x A x | x

B -> B_0 B_0 x /* change on this line */

...

B_i -> B_{i+1} B_{i+1}

...

B_n -> x

The initial sequence of an string with an ambiguous parse, grows

exponentially with the size of the grammar.

HTH

---

David Lester.

ps You could also have fun with B -> x B x | /* NULL */

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.