Regression in parsing expressions between ANTLR 4.6 and 4.7.2+

[prbisht]

Description:

We are seeing different parsing behavior between ANTLR 4.6 and 4.7.2 (and later).
Certain expressions that fail in 4.6 fail are parsing successfully in 4.7.2+, even though our grammar files are unchanged.

This makes us suspect a possible regression or behaviour change in the ANTLR runtime.

Details

• Grammar in use: Custom grammar files (Expression.g4, OrderBy.g4)
• Observed differences:

  • STRING rule escape-sequence :

    STRING: '\'' (( ~('\\'|'\'') | ('\\' '\'')))* '\'' |
            '"'  (( ~('\\'|'"') | ('\\' '"')))* '"';
    

    Error:

    error(156): Expression.g4:39:9: invalid escape sequence \"
    error(156): Expression.g4:39:24: invalid escape sequence \"
    error(156): Expression.g4:39:38: invalid escape sequence \"
    error(156): Expression.g4:39:47: invalid escape sequence \"
    error(144): Expression.g4:39:23: multi-character literals are not allowed in lexer sets: '\"'
    

    This error now occurs even in ANTLR 4.6, though previously the same grammar file allowed ANTLR to generate listeners, visitors, and parsers successfully.

  • OrderBy parsing

    Grammar excerpt:

    orderBy: orderByClause | orderByClause (',' orderBy)* ;
    orderByClause: path DIRECTION ;
    direction: DIRECTION ;
    path: expr;
    expr: atom (('+' | '-') atom)*;
    atom: KEY ('.' KEY)* | LPAREN expr RPAREN ;
    DIRECTION: 'ASC' | 'DESC' ;
    

    In ANTLR 4.7.2+, a couple of expressions that were failing in 4.6 are now being accepted, for example:

    • agent.skill ASC, (agent.chat.tasks + agent.email.tasks) ASC - agent.voice.tasks
    • agent.skill ASC DESC

Expected behaviour: Behaviour should be consistent between versions. Both versions should reject the invalid expressions.

Java version: 21

[kaby76]

You're going to have to provide the .g4's and input parse examples. We can't work on snippets.

The message error(156): Expression.g4:39:9: invalid escape sequence \" has nothing to do with the generated parser. It's output by the Antlr Tool indicating that it can't generate a parser because your .g4 is not syntactically correct.

Your snippet works for 4.6 and 4.13.2, and likely everything in between.

09/23-06:23:48 ~/temp/Generated-CSharp
$ cat Exp.g4
grammar Exp;

file : .* EOF;

STRING: '\'' (( ~('\\'|'\'') | ('\\' '\'')))* '\'' |
        '"'  (( ~('\\'|'"') | ('\\' '"')))* '"';

WS     : [ \t\r\n]+ -> skip ;09/23-06:23:52 ~/temp/Generated-CSharp
$ antlr4 -v 4.6 -Dlanguage=CSharp Exp.g4
warning(131): Exp.g4:3:8: greedy block ()* contains wildcard; the non-greedy syntax ()*? may be preferred
09/23-06:24:05 ~/temp/Generated-CSharp
$ antlr4 -v 4.13.2 -Dlanguage=CSharp Exp.g4
warning(131): Exp.g4:3:8: greedy block ()* contains wildcard; the non-greedy syntax ()*? may be preferred
09/23-06:25:38 ~/temp/Generated-CSharp
$

[prbisht]

attaching the grammar files needed to reproduce the parsing differences between ANTLR 4.6 and 4.7.2+. Skipping Expression.g4 for now to keep the reproduction minimal and focused on the OrderBy behaviour:

• OrderBy.g4

  grammar OrderBy; //a grammar for specification of order-by expressions
  import Common;
  
  orderBy: orderByClause | orderByClause (',' orderBy)* ; //multidimensional order_by expression
  
  orderByClause: path direction ; // skill to order by + ordering direction 
  
  direction: DIRECTION ; 
  
  path: expr;
  
  expr: atom (('+' | '-') atom)*; //expression with + and - operators
  
  atom: KEY ('.' KEY)* | LPAREN expr RPAREN ;
  
  DIRECTION: 'ASC' | 'DESC' ;
  
  LPAREN: '(';
  RPAREN: ')';
  

• Common.g4

  grammar Common;
  
  // Lexer rules: break the input into tokens for parsing by the parser rules.
  key: KEY ;
  
  KEY: [\p{L}\p{N}_]+;
  
  WS  :   ( ' '
          | '\t'
          | '\r'
          | '\n'
          ) -> skip;
  
  

Example input that triggers the problem in OrderBy.g4:

• agent.skill ASC, (agent.chat.tasks + agent.email.tasks) ASC - agent.voice.tasks
• agent.skill ASC DESC

[kaby76]

1. You don't specify the start rule. An ANTLR grammar MUST have an EOF-terminated start rule!!! Otherwise, the parse stops at the point of failure, backs up to the previous valid parse state, and outputs "everything is just fine!". The latest example of that is [clickhouse] Improper start rule causes bad input to parse as success. grammars-v4#4619.
2. orderBy: orderByClause | orderByClause (',' orderBy)* ; You have two alternatives for orderBy that can match the exact same input because the *-operator in (',' orderBy)* means "zero or more of". So, it's as though you wrote orderBy: orderByClause | orderByClause, which is nonsense. Get rid of the first alternative.
3. I took the OrderBy.g4, added a proper EOF-terminated start rule file: orderBy EOF;, then generated a driver app using trgen against Antlr 4.13.2. I then ran the app on the input string agent.skill ASC DESC. It does not parse because you specified DIRECTION twice: first "ASC", then "DESC". The grammar says: orderByClause: path direction ; direction: DIRECTION ;. That's for one direction only.
4. Antlr 4.6 doesn't accept this grammar, outputting error(156): OrderBy.g4:6:5: invalid escape sequence, which is complete nonsense because there's no escape sequence in file OrderBy.g4. However, it is in Common.g4, line 6, column 5, which you can see by typing antlr4 -v 4.6 Common.g4--which you should never do anyway, because Common.g4 is not a "top-level" grammar. There is a bug in the Antlr Tool because it reports the error in the wrong file. It still exists in 4.13.2 and is likely because import statements in Antlr copy the rules from one file into a global list of rules, losing the location of the source of the rule. In any case, I can't see how you can say this worked for 4.6 unmodified when Unicode support really didn't happen until 4.7.
5. I don't understand why you want to use 4.7 versus 4.13.2. There are many bugs fixed since 4.7.

[prbisht]

Yeah, my bad. The KEY rule in Common.g4 should be:

KEY: [a-zA-Z_0-9]+;

I accidentally shared the Unicode version (KEY: [\p{L}\p{N}_]+;) which ANTLR 4.6 doesn’t support (you get the invalid-escape / property-escape errors).

For context: we’re working to upgrade the grammar to support Unicode identifiers long-term, but when we tested earlier (in 4.13.2) some expressions that should fail were being accepted, so we temporarily were testing it out on 4.7.2 but plan going forward is to develop against the latest runtime (4.13.2) only.

Attaching the correct Common.g4 -

grammar Common;

// Lexer rules: break the input into tokens for parsing by the parser rules.
key: KEY ;

KEY: [a-zA-Z_0-9]+;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) -> skip;

I’m a bit unclear: even though we did not have an EOF-terminated start rule (previously with 4.6), why did some expressions fail under ANTLR 4.6 but now parse under 4.13.2 with the same grammar (without EOF)? The specific examples where we saw differing behaviour are:

• agent.skill ASC, (agent.chat.tasks + agent.email.tasks) ASC - agent.voice.tasks
• agent.skill ASC DESC

[ericvergnaud]

I believe Unicode is now supported, see working example here: https://github.com/antlr/antlr4/blob/dev/tool-testsuite/test/org/antlr/v4/test/tool/TestUnicodeGrammar.java.
So this may be a good opportunity to unify your grammars ?

[prbisht]

I’m still a bit unclear on one point: even without an EOF-terminated start rule, why did some expressions fail under ANTLR 4.6 but now parse successfully under 4.13.2 with the same grammar? For reference, the expressions we observed differing behaviour on are:

1. agent.skill ASC, (agent.chat.tasks + agent.email.tasks) ASC - agent.voice.tasks
2. agent.skill ASC DESC

[kaby76]

I’m still a bit unclear on one point: even without an EOF-terminated start rule, why did some expressions fail under ANTLR 4.6 but now parse successfully under 4.13.2 with the same grammar? For reference, the expressions we observed differing behaviour on are:

1. agent.skill ASC, (agent.chat.tasks + agent.email.tasks) ASC - agent.voice.tasks
2. agent.skill ASC DESC

An EOF-terminated start rule could very well explain why in 4.13.2 a parse succeeds when it should fail. I haven't checked whether the parser engine has changed since 4.6, but I would expect it to have fixed some incorrect behavior in the parser, and it may have affected this.

If it can, the parser engine "backs up" the point of the input pointer and returns a valid parse and parse tree for the partial input. You can verify this in your code with 4.13.2 by printing out the parse tree and examining where it left off during the parse. Or, by adding an EOF-terminated start rule.

Why would someone implement the code this way? There are a number of reasons. I use this feature for parsing .g4 grammar action code that is in Java, e.g., whatever: { this.Foobar() }? a | b; The valid Java code is delimited by open curly and closing curly braces. I don't want to scan ahead and start counting opening and closing curly braces to extract out the Java code, then parse the Java code on this substring. That's ridiculous. Instead, Antlr can do this, by calling the Java parser in the lexer when it starts seeing an action. The parser stops at the point of invalid input, which is the closing curly, then outputs a parse tree for this.Foobar(), not an invalid parse for this.Foobar() }.

[kaby76]

Indeed, I've verified this behavior for 4.6 and 4.13.2. Input: aaaba. Grammar as follows.

grammar x;
s: a* ;
a: 'a';
A: 'a';
B: 'b';

For version 4.6, the parser outputs an error. For 4.13.2, the parser succeeds, with the input being the string aaa and not including b.

You'll need to augment your grammar with an EOF-terminated start rule. And, I recommend that you update to 4.13.2.