Re: detecting ambiguous grammars

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

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