[antlr-interest] Multiple alternatives warning

John B. Brodie jbb at acm.org
Tue Jun 22 08:59:13 PDT 2010


Greetings!

On Tue, 2010-06-22 at 11:08 -0400, Pavel Grinfeld wrote:
> Hi,
> 
> I'm begging to get my bearings on this.... But the following gives two 
> "multiple alternatives" warnings.
> 
> How come?
> 
> Many thanks in advance,
> 
> Pavel
> 
> grammar PGTeX;
> 
> doc
> :     
> (a=text{System.out.print(">"+$a.value+"<");}|b=command{System.out.print($b.value);})+ 
> EOF;
> 
> command returns [ String value ]
> :'\\' a=word '\{' b=word '\}' {$value=$a.value+"+"+$b.value;};
> 
> text    returns[String value]
> :{$value="";}(a=word{$value += $a.value;} | WS{$value += $WS.text;} )+;
> 
> word    returns[String value]
> :WORD  {$value = $WORD.text;}  ;
> 
> WS  :   ( ' '
>          | '\t'
>          | '\r'
>          | '\n'
>          )+;
> 
> 
> WORD:    ('a'..'z')+;

your grammar is ambiguous because there is no way to know how to divide
up multiple text instances and supply them to the loop in the doc rule.

my explanation is probably really confusing but lets look at an example.

consider this input: a b

so the input is just 3 tokens: a WS b

now there are at least 4 derivations (e.g. parse trees) for this input
under your grammar:

doc
   text
      word=='a'
      WS==' '
      word=='b'

or

doc
   text
      word=='a'
   text
      WS==' '
   text
      word=='b'

or

doc
   text
      word=='a'
      WS==' '
   text
      word=='b'

doc
   text
      word=='a'
   text
      WS==' '
      word=='b'

all of these are perfectly valid under your grammar and there is no way
for the Tool to decide which derivation you really want (i'm guessing
you want the first...)

I think if you ignore the warning and try your grammar you will get the
first derivation, not sure.

of course the better solution is to re-work your grammar in order to
remove the ambiguity.

is this Knuth's TeX typesetting language? I have not used TeX directly,
but have used Lamport's LaTeX quite a bit. And in LaTeX commands and
text are interleaved. is that true for TeX also? so maybe:

doc : command+ ( text command+ )+ EOF;

Hope this helps...
   -jbb




More information about the antlr-interest mailing list