[antlr-interest] Understanding a really simple nondeterminism :p

[John B. Brodie]

on Sun, 30 Jul 2006 23:57:29 +0200, kototama kototama asked:
>Hello,

Hi!

>Sorry for this question but I don't understand the nondeterminism of the
>following grammar :
>
>a: b (MUL b)*
>;
>
>b: DEGREE a
> | ID
>;
>
>Thanks in advance for your help!

Consider an input consisting of this sequence of 4 tokens:

                           DEGREE ID MUL ID

we have two ways to parse them:

     a              or                 a
      \                               /|\
       b                             / | \
      / \                           b MUL ID
DEGREE   a                         / \
        /|\                  DEGREE   a
       / | \                           \
     ID MUL ID                          b
                                         \
                                          ID

e.g we could have either DEGREE (ID MUL ID) or (DEGREE ID) MUL ID

thus the nondeterminism.

Hope this helps...
   -jbb