Why does the order of ANTLR4 tokens matter?

3
votes

I have a simple grammar that will eventually parse YANG source. When I make when seem to be an arbitrary change the location of the MODULE token the IntelliJ ANTLR4 Plugin can/cannot parse my input.

The input string to be parsed:

module x { }

Here is the grammar that works without any error:

grammar Yang ;

yang: module_open module_close;

module_open : MODULE ID BRACKET_OPEN ;

module_close: BRACKET_CLOSE ;

MODULE: 'module' ;

ID: ([A-Za-z][A-Za-z0-9_-]*) ;
BRACKET_OPEN: '{' ;
BRACKET_CLOSE: '}' ;

WS: [ \t\r\n]+ -> skip ;

Here is the grammar that fails:

grammar Yang ;

yang: module_open module_close;

module_open : MODULE ID BRACKET_OPEN ;

module_close: BRACKET_CLOSE ;

ID: ([A-Za-z][A-Za-z0-9_-]*) ;

MODULE: 'module' ;

BRACKET_OPEN: '{' ;
BRACKET_CLOSE: '}' ;

WS: [ \t\r\n]+ -> skip ;

All I'm doing is cutting-pasting the MODULE token definition before/after the ID token, and it always fails if the MODULE definition is after the ID definition.

What am I missing? I see no discussion of order of tokens in the docs!

EDIT: @BartKiers Related Post... ANTLR4 lexer rules don't work as expected

2
parsingintellij-ideatokenantlr4
@BartKiers That answer only acknowledges the problem: What are the specific rules of ordering tokens? I fail to see why what amounts to a simple substitution (.aka. MODULE -> "module") should be subject to the order of declaration. Please cite references in the documentation if possible. - mdeazley
@BartKiers First, thanks for the effort answering newb questions! I get the "The lexer tries to match as much characters as possible" part. But I fail to see why "and when 2 (or more) rules match the same amount of characters, the rule defined first will win." even applies in this situation... I have only one MODULE token definition and only one rule "module_open" that uses that definition." - mdeazley
@BartKiers The closest I can come to answering my own question is "Token definitions must be declared in the order they are used in the parse tree." or something like that... But what if I use them in a different order in the another parse rule? - mdeazley
"First, thanks for the effort answering ...": no problem. "... the order they are used in the parse tree." no, that is not how it works. Since my answer is not clear to you, I'll re-open your question and removed the link. Perhaps someone else is able to explain it. - Bart Kiers

2 Answers

3
votes

It fails if module is after ID because the text 'module' is also a valid 'ID'. If the ID rule appears first, then it has precedence. That's when the order of lexer rules matters, when two or more lexer rules can match the same input. In this case, the one appearing first trumps those that follow; it has precedence.

Your excellent test case here is a perfect and exemplary illustration of this behavior at work.

There used to be in the ANTLR4 documentation here a great article by none other than Sam Harwell that explained this perfectly, but I can no longer find it.

1
votes

From the book of Antlr (section 5.5):

Matching Identifiers

In grammar pseudocode, a basic identifier is a nonempty sequence of upper- case and lowercase letters. Using our newfound skills, we know to express the sequence pattern using notation (...)+. Because the elements of the sequence can be either uppercase or lowercase letters, we also know that we’ll have a choice operator inside the subrule.

ID : ('a'..'z'|'A'..'Z')+ ; // match 1-or-more upper or lowercase letters

The only new ANTLR notation here is the range operator: 'a'..'z' means any character from a to z. That is literally the ASCII code range from 97 to 122. To use Unicode code points, we need to use '\uXXXX' literals where XXXX is the hexadecimal value for the Unicode character code point value.

As a shorthand for character sets, ANTLR supports the more familiar regular expression set notation.

ID : [a-zA-Z]+ ; // match 1-or-more upper or lowercase letters

Rules such as ID sometimes conflict with other lexical rules or literals refer- enced in the grammar such as 'enum'. 

grammar KeywordTest;
enumDef : 'enum' '{' ... '}' ;
...
FOR : 'for' ;
...
ID : [a-zA-Z]+ ; // does NOT match 'enum' or 'for'

Rule ID could also match keywords such as enum and for, which means there’s more than one rule that could match the same string. To make this clearer, consider how ANTLR handles combined lexer/parser grammars such as this. ANTLR collects and separates all of the string literals and lexer rules from the parser rules. Literals such as 'enum' become lexical rules and go immediately after the parser rules but before the explicit lexical rules.

ANTLR lexers resolve ambiguities between lexical rules by favoring the rule specified first. That means your ID rule should be defined after all of your keyword rules, like it is here relative to FOR. ANTLR puts the implicitly gener- ated lexical rules for literals before explicit lexer rules, so those always have priority. In this case, 'enum' is given priority over ID automatically. Because ANTLR reorders the lexical rules to occur after the parser rules, the following variation on KeywordTest results in the same parser and lexer:

grammar KeywordTestReordered;
FOR : 'for' ;
ID : [a-zA-Z]+ ; // does NOT match 'enum' or 'for' ...
enumDef : 'enum' '{' ... '}' ;
...