Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

antlr match input using multiple alternatives error

Tags:

antlr

antlr3

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

like image 630
probably at the beach Avatar asked Jun 27 '11 21:06

probably at the beach


1 Answers

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:

enter image description here

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.

like image 57
Bart Kiers Avatar answered Oct 23 '22 19:10

Bart Kiers