antlr match input using multiple alternatives error

Question

I'm receiving a warning when antlr v3.1 compiles on this rule

 sentence
:
(CAPITAL_LETTERS_AND_NUMBERS | INT | ANY_WORD ) 
(
    INT
| CAPITAL_LETTERS_AND_NUMBERS
| ANY_WORD 
)*;

The warning is:

 5:2: Decision can match input such as "CAPITAL_LETTERS_AND_NUMBERS" using multiple alternatives: 1, 2
 As a result, alternative(s) 2 were disabled for that input
 Semantic predicates were present but were hidden by actions.
 Decision can match input such as "INT" using multiple alternatives: 1, 2
 As a result, alternative(s) 2 were disabled for that input
 Semantic predicates were present but were hidden by actions.

The reason I'm confused is the grammar which is quite complex passes until I put another subrule in another place in the file that uses sentence as well. It accepts the above rule until this happens which seems strange. I'm looking for hints as to how best to go about debugging and understanding how this could happen?

Thanks, Richard

Stowaway

Answer 1

That's difficult. Especially with larger grammars, changing (or adding) rules can cause ambiguities which are hard to track down.

ANTLRWorks can assist in finding these ambiguities. Given the following grammar:

grammar T;

parse
  :  other? WORD? EOF
  ;

other
  :  WORD
  ;

WORD
  :  ('a'..'z' | 'A'..'Z')+
  ;

the parser does not know how to handle the parse rule properly. Input such as foo (one WORD token) could be matched by other EOF and by WORD EOF, which is what the warning:

Decision can match input such as "WORD" using multiple alternatives

means.

Generating a parser and lexer using ANTLRWorks results in the following visualization of the problem:

Yes, I realize that this is just a trivial example, and that your problem is quite a bit trickier, but there's AFAIK no holy grail here. If you could post the grammar that generates a parser & lexer without a problem and the edited grammar that produces these warnings, I might have a look at it to see if I can see the problem.

Interracial

great explanation. Adding a syntactic predicate (CAPITAL_LETTERS_AND_NUMBERS) => CAPITAL_LETTERS_AND_NUMBERS fixed the issue though I think I'd have trouble explaining exactly why. – Stowaway

@Richard, by adding a syntactic predicate in front of token X: (X)=> X, you're more or less saying: "if an X can be seen, go ahead and match it, no matter if another sub-rule could possibly also match this X". I hope I didn't confuse you more :). A while ago I wrote a small Q&A about semantic predicates, perhaps I should do one on syntactic predicates in the near future... – Interracial