Antlr4 unexpectedly stops parsing expression

问题:

I'm developing a simple calculator with the formula grammar:

grammar Formula ;
expr : <assoc=right> expr POW expr             # pow
     | MINUS expr                              # unaryMinus
     | PLUS expr                               # unaryPlus
     | expr PERCENT                            # percent
     | expr op=(MULTIPLICATION|DIVISION) expr  # multiplyDivide
     | expr op=(PLUS|MINUS) expr               # addSubtract
     | ABS '(' expr ')'                        # abs
     | '|' expr '|'                            # absParenthesis
     | MAX '(' expr ( ',' expr )* ')'          # max
     | MIN '(' expr ( ',' expr )* ')'          # min
     | '(' expr  ')'                           # parenthesis
     | NUMBER                                  # number
     | '"' COLUMN '"'                          # column
     ;

MULTIPLICATION: '*' ;
DIVISION: '/' ;
PLUS: '+' ;
MINUS: '-' ;
PERCENT: '%' ;
POW: '^' ;
ABS: [aA][bB][sS] ;
MAX: [mM][aA][xX] ;
MIN: [mM][iI][nN] ;
NUMBER: [0-9]+('.'[0-9]+)? ;
COLUMN: (~[\r\n"])+ ;
WS : [ \t\r\n]+ -> skip ;

"column a"*"column b" input gives me following tree as expected:

But "column a" * "column b" input unexpectedly stops parsing:

What am I missing?

回答1:

Your WS rule is broken by the COLUMN rule, which has a higher precedence. More precisely, the issue is that ~[\r\n"] matches space characters too.

"column a"*"column b" lexes as follows: '"' COLUMN '"' MULTIPLICATION '"' COLUMN '"'

"column a" * "column b" lexes as follows: '"' COLUMN '"' COLUMN '"' COLUMN '"'

Yes, "space star space" got lexed as a COLUMN token because that's how ANTLR lexer rules work: longer token matches get priority.

As you can see, this token stream does not match the expr rule as a whole, so expr matches as much as it could, which is '"' COLUMN '"'.

Declaring a lexer rule with only a negative rule like you did is always a bad idea. And having separate '"' tokens doesn't feel right for me either.

What you should have done is to include the quotes in the COLUMN rule as they're logically part of the token:

COLUMN: '"' (~["\r\n])* '"';

Then remove the standalone quotes from your parser rule. You can either unquote the text later when you'll be processing the parse tree, or change the token emission logic in the lexer to change the underlying value of the token.

And in order to not ignore trailing input, add another rule which will make sure you've consumed the whole input:

formula: expr EOF;

Then use this rule as your entry rule instead of expr when calling your parser.

回答2:

But "column a" * "column b" input unexpectedly stops parsing

If I run your grammar with ANTLR 4.6, it does not stop parsing, it parses the whole file and displays in pink what the parser can't match :

The dots represent spaces.

And there is an important error message :

line 1:10 mismatched input ' * ' expecting {<EOF>, '*', '/', '+', '-', '%', '^'}

As I explain here as soon as you have a "mismatched" error, add -tokens to grun.

With "column a"*"column b" :

$ grun Formula expr -tokens -diagnostics t1.text
[@0,0:0='"',<'"'>,1:0]
[@1,1:8='column a',<COLUMN>,1:1]
[@2,9:9='"',<'"'>,1:9]
[@3,10:10='*',<'*'>,1:10]
[@4,11:11='"',<'"'>,1:11]
[@5,12:19='column b',<COLUMN>,1:12]
[@6,20:20='"',<'"'>,1:20]
[@7,22:21='<EOF>',<EOF>,2:0]

With "column a" * "column b":

$ grun Formula expr -tokens -diagnostics t2.text
[@0,0:0='"',<'"'>,1:0]
[@1,1:8='column a',<COLUMN>,1:1]
[@2,9:9='"',<'"'>,1:9]
[@3,10:12=' * ',<COLUMN>,1:10]
[@4,13:13='"',<'"'>,1:13]
[@5,14:21='column b',<COLUMN>,1:14]
[@6,22:22='"',<'"'>,1:22]
[@7,24:23='<EOF>',<EOF>,2:0]
line 1:10 mismatched input ' * ' expecting {<EOF>, '*', '/', '+', '-', '%', '^'}

you immediately see that " * "is interpreted as COLUMN.

Many questions about matching input with lexer rules have been asked these last days :

extraneous input

ordering

greedy

ambiguity

expression

So many times that Lucas has posted a false question just to make an answer which summarizes all that problematic : disambiguate.