In ANTLR, the lexer is isolated from the parser, which means it will split the text into typed tokens according to the lexer grammar rules, and the parser has no influence on this process (it cannot say "give me an INTEGER
now" for instance). It produces a token stream by itself. Furthermore, the parser doesn't care about the token text, it only cares about the token types to match its rules.
This may easily become a problem when several lexer rules can match the same input text. In that case, the token type will be chosen according to these precedence rules:
- First, select the lexer rules which match the longest input substring
- If the longest matched substring is equal to an implicitly defined token (like
'='
), use the implicit rule as the token type
- If several lexer rules match the same input, choose the first one, based on definition order
These rules are very important to keep in mind in order to use ANTLR effectively.
In the example from the question, the parser expects to see the following token stream to match the keyValue
parser rule: IDENTIFIER
'='
INTEGER
';'
where '='
and ';'
are implicit token types.
Since 42
can match both INTEGER
and IDENTIFIER
, and IDENTIFIER
is defined first, the parser will receive the following input: IDENTIFIER
'='
IDENTIFIER
';'
which it won't be able to match to the keyValue
rule. Remember, the parser cannot communicate to the lexer, it can only receive data from it, therefore it cannot say "try to match INTEGER
next".
It's advisable to minimize the lexer rules overlap to limit the impact of this effect. In the above example, we have several options:
- Redefine
IDENTIFIER
as [A-Za-z] [A-Za-z0-9]*
(require it to start with a letter). This avoids the problem entirely but prevents identifier names starting with a number from being defined, so it changes the intent of the grammar.
- Reorder
INTEGER
and IDENTIFIER
. This solves the problem for most cases, but prevents fully numeric identifiers from being defined, therefore it also changes the intent of the grammar in a subtle, not so obvious way.
- Make the parser accept both token types when lexer rules overlap:
First, swap INTEGER
and IDENTIFIER
in order to give priority to INTEGER
. Then, define a parser rule id: IDENTIFIER | INTEGER;
then use that rule instead of IDENTIFIER
in other parser rules, which would change keyValue
to key=id '=' value=INTEGER ';'
.
Here's a second lexer behavior example to sum up:
The following combined grammar:
grammar LexerPriorityRulesExample;
// Parser rules
randomParserRule: 'foo'; // Implicitly declared token type
// Lexer rules
BAR: 'bar';
IDENTIFIER: [A-Za-z]+;
BAZ: 'baz';
WS: [ \t\r\n]+ -> skip;
Given the following input:
aaa foo bar baz barz
Will produce the following token sequence from the lexer:
IDENTIFIER
'foo'
BAR
IDENTIFIER
IDENTIFIER
EOF
aaa
is of type IDENTIFIER
Only the IDENTIFIER
rule can match this token, there is no ambiguity.
foo
is of type 'foo'
The parser rule randomParserRule
introduces the implicit 'foo'
token type, which is prioritary over the IDENTIFIER
rule.
bar
is of type BAR
This text matches the BAR
rule, which is defined before the IDENTIFIER
rule, and therefore has precedence.
baz
is of type IDENTIFIER
This text matches the BAZ
rule, but it also matches the IDENTIFIER
rule. The latter is chosen as it is defined before BAR
.
Given the grammar, BAZ
will never be able to match, as the IDENTIFIER
rule already covers everything BAZ
can match.
barz
is of type IDENTIFIER
The BAR
rule can match the first 3 characters of this string (bar
), but the IDENTIFIER
rule will match 4 characters. As IDENTIFIER
matches a longer substring, it is chosen over BAR
.
EOF
(end of file) is an implicitly defined token type which always occurs at the end of the input.
As a rule of thumb, specific rules should de defined before more generic rules. If a rule can only match an input which is already covered by a previously defined rule, it will never be used.
Implicitly defined rules such as 'foo'
act as if they were defined before all other lexer rules. As they add complexity, it's advisable to avoid them altogether and declare explicit lexer rules instead. Just having a list of tokens in one place instead of having them scattered across the grammar is a compelling advantage of this approach.