[antlr-interest] Fwd: Simple question, Hard answer?

[Thomas Brandon]

On Wed, Sep 3, 2008 at 10:28 PM, Bill Mayfield <antlrinterest at gmail.com> wrote:
>
> Thomas: This one doesn't work however
>
>
> grammar test;
>
> start   :       chaos* pattern* chaos*;
>
> pattern :       T1 T2 T2 T1;
>
> chaos   :       T1 | T2;
>
> T1      :       'o';
> T2      :       'k';
>
> It seems to be recognizing only "chaos*" and ignores the "pattern*
> chaos*" part. I guess it is logical to keep matching the first loop as
> long as possible.
If you check the output of ANTLR you will see:
warning(200): test.g:4:5: Decision can match input such as "T1" using
multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): test.g:4:5: Decision can match input such as "T2" using
multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
warning(200): test.g:4:12: Decision can match input such as "T1 T2 T2
T1" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

The first 2 indicate that given the chaos* decision, either continuing
the chaos* loop (alternative 1) or exiting the loop (alternative 2)
will allow either T1 or T2 to match (T2 matches by skipping the
optional pattern). So ANTLR will disable alternative 2 (exiting the
loop) and will thus keep going until it gets something other than T1
or T2.
The 3rd message is saying that in the pattern loop the sequence T1 T2
T2 T1 can be matched either by continuing the pattern* loop or by
skipping that and going to the chaos*. Here, ANTLR disables the exit
loop alternative and will match a pattern if it can.

> But if I change that start rule to:
>
> start   :       chaos+ pattern+ chaos+;
>
> Which states that there should be some chaos, some patterns and again
> some chaos, I get an error stating that "The following alternatives
> could never be matched: 2" which I don't understand. Or would it stay
> in the first chaos+ because the parser keeps believing it sees chaos..
>
Here ANTLR is talking about the first chaos+ loop and saying that
nothing will let it exit the loop (alternative 2) as the only things
that can legally follow the loop (the T1 to start the required
pattern) is also matched in the loop.

Check out the Syntax Diagram in ANTLRWorks to see what ANTLR is
talking about in ambiguities like these.

You could use predicates to resolve the problem. e.g.
start:	 chaos ((pattern chaos)=>pattern|chaos)* chaos;
will ensure there is a chaos at the start an end, so
"okkooookkoooookkoookko" will match only 2 patterns, the one's at the
start and end not being valid due to no chaos before\after.
Though as I said filtering lexers may be a more appropriate solution
for your real problem.

Tom.
>
> Damn.. it's hard to communicate this by email.
>
>
> Thanks so far for your input Thomas, Matt, Robert & Liehann! I've
> learned something out of this...
>
> Kind regards,
> Bill
>
>
>
>