How does ANTLR decide which lexer rule to apply? The longest matching lexer rule wins?

user_264052 0
Viewed 936

The input content:

enter image description here

The grammar:

grammar test;

p : EOF;

Char : [a-z];

fragment Tab : '\t';
fragment Space : ' ';
T1 : (Tab|Space)+ ->skip;

T2 : '#' T1+ Char+;

The matching result is this:

[@0,0:6='#   abc',<T2>,1:0]    <<<<<<<< PLACE 1
[@1,7:6='<EOF>',<EOF>,1:7]
line 1:0 extraneous input '#   abc' expecting <EOF>

Please ignore the error in the last line. I am wondering why the token matched at PLACE 1 is T2.

In the grammar file, the T2 lexer rule goes after the T1 lexer rule. So I expect T1 rule should get applied first. So why the spaces in # abc is not skipped?

Does ANTLR uses some greedy strategy to match current character stream with the longest lexer rule?

antlr4 antlr lexer compiler-construction
3 Answers

In response to ...

Does ANTLR uses some greedy strategy to match current character stream with the longest lexer rule?

... I will quote from ANTLR4's Wildcard Operator and Nongreedy Subrules documentation.

Here is how the lexer chooses token rules:

  1. The primary goal is to match the lexer rule that recognizes the most input characters.
INT : [0-9]+ ;
DOT : '.' ; // match period
FLOAT : [0-9]+ '.' ; // match FLOAT upon '34.' not INT then DOT
  1. If more than one lexer rule matches the same input sequence, the priority goes to the rule occurring first in the grammar file.
DOC : '/**' .*? '*/' ; // both rules match /** foo */, resolve to DOC
CMT : '/*' .*? '*/' ;
  1. Nongreedy subrules match the fewest number of characters that still allows the surrounding lexical rule to match.
/** Match anything except \n inside of double angle brackets */
STRING : '<<' ~'\n'*? '>>' ; // Input '<<foo>>>>' matches STRING then END
END    : '>>' ;
  1. After crossing through a nongreedy subrule within a lexical rule, all decision-making from then on is "first match wins."

For example, literal ab in rule right-hand side (grammar fragment) .*? ('a'|'ab') is dead code and can never be matched. If the input is ab, the first alternative, 'a', matches the first character and therefore succeeds. ('a'|'ab') by itself on the right-hand side of a rule properly matches the second alternative for input ab. This quirk arises from a nongreedy design decision that’s too complicated to go into here.

If you understand rules 1, 2, and 3, you will likely be fine. The fourth rule is esoteric.

Based only the information quoted above, I don't see a definitive answer as to where the implicit token rule applies. As I find more information, I will update this answer.

I encourage you to also review TomServo's answer, which talks more about the implicit token rule.

(Aside: in my opinion, the content quoted above probably would be more discoverable and understandable if incorporated into the lexer rules docs.)

user_1096180
Related