[antlr-interest] Long puzzuled problem "nondeterminism upon"

[John B. Brodie]

Greetings!

sunjigang1965 at yahoo.com.cn asked:
>Warning messaged
>
>par.g:92: warning:nondeterminism upon
>par.g:92:     k==1:DERIVES
>par.g:92:     between alt 1 and exit branch of block
>
> generated for grammar:
>
>typeExp
>	:
>	subTypeExp( DERIVES typeExp)* //line 92, DERIVES stands for "->"
>	;
>	
>subTypeExp
>	:
>	(LPAREN typeList)=>LPAREN typeList RPAREN DERIVES typeExp //line 97
>	|LPAREN typeExp RPAREN
                               \___ i assume this is line 98
>	|typeDenotor
>	;
>	
>typeList
>	:
>	(typeExp (COMMA typeExp)* )?
>	;
>
>typeDenotor
>	:
>	 ("int" LSQUARE)=> "int" LSQUARE RSQUARE  //int []
>	| "int"
>	| id:ID {#typeDenotor=#([ID_TYPE,id.getText()], id); typeDenotor_AST.setPos(id_AST.getPos());}
>	| "boolean" 
>	;
>
>There is no left recursive problem with the grammar. I am suspicious
>about line 97, but still have no idea about it.


Consider this sequence of tokens:

                  LPAREN "int" RPAREN DERIVES "int"

which may be semantic nonsense in your language but seems to be
syntactically permissible.

Please observe that we have two possible derivations of this sequence:

typeExp ==>
   subTypeExp <empty> ==>
      LPAREN typeList RPAREN DERIVES typeExp <empty> ==>
         LPAREN typeExp <empty> RPAREN DERIVES typeExp <empty> ==>
            LPAREN "int" <empty> RPAREN DERIVES typeExp <empty> ==>
               LPAREN "int" <empty> RPAREN DERIVES "int" <empty>

or we can derive it as:

typeExp ==>
   subTypeExp DERIVES typeExp ==>
      LPAREN typeExp RPAREN DERIVES typeExp ==>
         LPAREN "int" RPAREN DERIVES typeExp ==>
            LPAREN "int" RPAREN DERIVES "int"

thus you have a non-determinism. if we parse the initial subTypeExp using
line 97 then there is no "DERIVES" phrase in the typeExp (the exit branch
should be taken). or if we parse the initial subTypeExp using line 98 then
there is one "DERIVES" phrase in the typeExp (alt 1 should be taken).

Antlr can not determine which one is intended.

Hope this helps
   -jbb