Re: detecting ambiguous grammars

Thant Tessman <thant@acm.org>
12 Mar 2001 02:36:42 -0500

          From comp.compilers

Related articles
[2 earlier articles]
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)
Re: detecting ambiguous grammars genew@shuswap.net (2001-03-27)
[7 later articles]
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 12 Mar 2001 02:36:42 -0500
Organization: XMission http://www.xmission.com/
References: 01-02-080 01-03-020 01-03-032 01-03-078
Keywords: parse
Posted-Date: 12 Mar 2001 02:36:42 EST

David Lester wrote:


[...]


> The language is: "x(xx)* | x^(2^(n+1))". The grammar is not ambiguous
> (but not LR(1), or anything else useful either).


Yes, I now understand the problem is a little more pathological than I
first suspected.


For what it's worth, I did manage to implement the ambiguity detector
I described earlier, and here are the results on the ambiguous version
of the grammar David Lester offered. The 'd' is the recursion depth at
which the ambiguity was detected.


n d
0 3
1 4
2 6
3 10
4 18
5 34
6 (got bored waiting for an answer)


It seems


d(n) = d(n-1) + 2^(n-1) where d(0) = 3


Note that for 'fatter' grammars, the ambiguity detector ran out of
memory for recursion depths of as little as 4.


I'm questioning whether the advantage of being able to use a grammar
that isn't necessarily LR(1) outweighs the disadvantage of knowing
unambiguously whether a grammar is unambiguous.


-thant


Post a followup to this message

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