[antlr-interest] parser nondeterminism rule

Bans VGLab bans.vglab at gmail.com
Thu Jul 20 03:15:30 PDT 2006


Hello Jigang,

The first rule can be re-written like this:

graphExp
    : brackGraph
        (
            brackGraph
            |
        )+
        (options {greedy=true;}:op graphExp)*
    ;

So, the statement "between alt 1 and exit branch of block" means the first
alternative in the grammar expression " brackGraph |  " and its exit.

This can be easily seen with this example derivation:

Applying different alternatives in the rule 1, we can derive

"brackGraph op graphExp"
          and
"brackGraph brackGraph brackGraph".

But both of them will eventually derive
   "op op op"

So looking at the next terminal LA(1) which could be any of the "UpperCaseId
| LowerCaseId | FunnyId", there is no way to predict which alternative to
pick. This can go to arbitrary depth. So, increasing k to any value will not
solve the problem. You need to re-structure the grammar.

Hope this helps.

-Sujeet Banerjee
SMTS
Persistent Systems Pvt. Ltd.

On 7/19/06, Ëï¼Í¸Õ Jigang (Robert) Sun <sunjigang1965 at yahoo.com.cn> wrote:
>
> I have a parser rule,
>
> graphExp: (brackGraph)+ (options {greedy=true;}:op graphExp)*;  //line 101
>
> brackGraph: op | ("(" graphExp ")")=> "(" graphExp ")"
>
> op: UpperCaseId | LowerCaseId | FunnyId;
>
> I know op (UpperCaseId | LowerCaseId | FunnyId) is either part of
> brackGraph or (op graphExp)*,
> and in (op graphExp)*  op could be a subset of graphExp,
>
> so warning was given:
>
> par.g:101: warning:nondeterminism upon
> par.g:101:     k==1:UpperCaseId,LowerCaseId,FunnyId
> par.g:101:     between alt 1 and exit branch of block
>
> I have not got an idea about it.
>
> Thanks.
>
> Jigang
>
>
>
>
> ___________________________________________________________
> ÑÅ»¢Ãâ·ÑÓÊÏä-3.5GÈÝÁ¿£¬20M¸½¼þ
> http://cn.mail.yahoo.com/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20060720/2367b86d/attachment.html


More information about the antlr-interest mailing list