[antlr-interest] Antwort: antlr-interest Digest, Vol 21, Issue 56

[Timo Heiber]

Seref,

your last example actually illustrates the ambiguity problem quite nicely:

"D x + D x  (should parse as D (x + D x) )"

D (x + D x) can be obtained by applying the following sequence of parser
rules:

a
-> b
-> c
-> 'D' a
-> 'D' b '+' b
-> 'D' c '+' c
-> 'D' 'x' '+' 'D' a
-> 'D' 'x' '+' 'D' b
-> 'D' 'x' '+' 'D' c
-> 'D' 'x' '+' 'D' x

But you can get the same by applying an alternative sequence of rules:

a
-> b '+' b
-> c '+' c
-> 'D' a '+' 'D' a
-> 'D' b '+' 'D' b
-> 'D' 'x' '+' 'D' 'x'

Hope this helps.

      - Timo


> ------------------------------
>
> Message: 7
> Date: Tue, 29 Aug 2006 19:27:03 +0300
> From: Seref Arikan <serefarikan at kurumsalteknoloji.com>
> Subject: [antlr-interest] An ambiguity question
> To: pradeep kulkarni <pradeep_koolkarni at yahoo.com>
> Cc: antlr-interest at antlr.org
> Message-ID: <44F46AD7.3060309 at kurumsalteknoloji.com>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed
>
> Hi,
> While taking a look at the past messages, I saw an interesting one. This
> is from Martin Traverso:
>
> Howdy,
>
> What is the best way to resolve the ambiguities caused by 'D' a in rule c
in
> the following grammar?
>
> grammar T;
> a: b ('+' b)*;
> b: c ('*' c)*;
> c: 'D' a
>    | 'x';
>
> Essentially, I want it to parse stuff like:
>
> x * x + x * x
> D x * x + x * x    (should parse as D ((x * x) + (x * x)) )
> x + D x * x + x * x  (should parse as x + D ((x * x) + (x * x)) )
> D x + D x  (should parse as D (x + D x) )
> etc.
>
> Now, Terrence has answered this one, but I'd like to ask the following:
> How does the ambiguity occur?  Would someone please provide me an
> example input to the question below that will cause the problem?  A
> little explanation on this one would be great
>
> Best Regards
> Seref Arikan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20060830/91ec0329/attachment.html