[tool] Antlr tool enters an epsilon action transition with direct left recursion removal.

[kaby76]

I've been analyzing antlr/grammars-v4#4465. Apparently, the Antlr tool is inserting an epsilon transition with non-existent action arbitrarily for the first alt of a rule that has direct left recursion. This action causes AdaptivePredict() to make an incorrect decision when parsing certain input because of "actions shadowing predicates". The workaround swaps out rules that have derivations containing predicates out of the arbitrary first alt. However, this seems quite wrong. It feels like a bug in the tool.

Here is an example: the classic "expression" grammar.

// Template generated code from trgen 0.23.18

// $antlr-format alignTrailingComments true, columnLimit 150, minEmptyLines 1, maxEmptyLinesToKeep 1, reflowComments false, useTab false
// $antlr-format allowShortRulesOnASingleLine false, allowShortBlocksOnASingleLine true, alignSemicolons hanging, alignColons hanging

grammar Arithmetic;

file_
    : expression (SEMI expression)* EOF
    ;

expression
    : expression POW expression
    | expression (TIMES | DIV) expression
    | expression (PLUS | MINUS) expression
    | LPAREN expression RPAREN
    | (PLUS | MINUS)* atom
    ;

atom
    : scientific
    | variable
    ;

scientific
    : SCIENTIFIC_NUMBER
    ;

variable
    : VARIABLE
    ;

VARIABLE
    : VALID_ID_START VALID_ID_CHAR*
    ;

SCIENTIFIC_NUMBER
    : NUMBER (E SIGN? UNSIGNED_INTEGER)?
    ;

LPAREN
    : '('
    ;

RPAREN
    : ')'
    ;

PLUS
    : '+'
    ;

MINUS
    : '-'
    ;

TIMES
    : '*'
    ;

DIV
    : '/'
    ;

GT
    : '>'
    ;

LT
    : '<'
    ;

EQ
    : '='
    ;

POINT
    : '.'
    ;

POW
    : '^'
    ;

SEMI
    : ';'
    ;

WS
    : [ \r\n\t]+ -> channel(HIDDEN)
    ;

fragment VALID_ID_START
    : ('a' .. 'z')
    | ('A' .. 'Z')
    | '_'
    ;

fragment VALID_ID_CHAR
    : VALID_ID_START
    | ('0' .. '9')
    ;

fragment NUMBER
    : ('0' .. '9')+ ('.' ('0' .. '9')+)?
    ;

fragment UNSIGNED_INTEGER
    : ('0' .. '9')+
    ;

fragment E
    : 'E'
    | 'e'
    ;

fragment SIGN
    : ('+' | '-')
    ;

This is what the tool produces for rule expression:

Note the empty transition s20 -> s21. There are no explicit actions in the grammar, and it always adds the fake action epsilon transition to alt one of a decision.

I think the idea of "actions shadow predicates" is hard to understand. According to the doc: More importantly, the parser can't execute actions until it has decided which alternative to match. That's because actions have side effects and we can't undo things like print statements. For example, in the following rule, the parser can't execute the action in front of the {java5}? predicate before committing to that alternative. I guess the reason for it is because AdaptivePredict() is simultaneously testing out various derivations. One cannot rely on a state variable.

[kaby76]

It's done here:

antlr4/tool/resources/org/antlr/v4/tool/templates/LeftRecursiveRules.stg

Line 42 in cb85012

: ( {} <primaryAlts:{alt | <alt.altText> }; separator="\n | ">

Why is an empty action inserted? 9c1e58d

add {} in primary alt block to prevent ID|INT from becoming SET, which breaks code gen needs.

cc @mike-lischke

[mike-lischke]

Oh yes, I have seen this in the left recursion resolver. The entire approach of generating a new grammar text to refactor left-recursion, and parsing it again looks suspicious to me. But then I don't know all the reasons that lead to this code.

I would have expected that the ATN is modified in place, like set transformations and so on.

@parrt Do you remember what was the reason for adding that empty action there in the first place?

[kaby76]

I removed the {} from the template (antlr-ng), rebuilt the tool, generated the parser for the current, unmodified sql/mysql/Oracle, and the input in antlr/grammars-v4#4465 now parses just fine. The regression test also works. Going to do a full test of grammars-v4.

[mike-lischke]

@Kaby I'm glad that works so far, but please check that set handling still works as before (seeing the comment preventing ID|INT from becoming SET sounds like the change might have an impact on set generation).

[kaby76]

Oh yes, I have seen this in the left recursion resolver. The entire approach of generating a new grammar text to refactor left-recursion, and parsing it again looks suspicious to me. But then I don't know all the reasons that lead to this code.

I would have expected that the ATN is modified in place, like set transformations and so on.

Either way is ok--I implemented it both ways in Trash. But I've settled on tree transformations instead because Trash is a pipelined toolkit on CSTs. I looked at the template, and outside of the addition of {}, it all looks fine, and is what Trash does, too.

So far, the regression tests of grammars-v4 using the swapped tool are working. I'll need to test using an expression grammar with ID | INT, but I'm suggesting that the {} hack may no longer be needed.

[kaby76]

Unfortunately, the hack is currently required. The tool crashes on input awk.g4.

$ make
bash build.sh
Exception in thread "main" java.lang.ClassCastException: class org.antlr.v4.tool.ast.GrammarAST cannot be cast to class org.antlr.v4.tool.ast.BlockAST (org.antlr.v4.tool.ast.GrammarAST and org.antlr.v4.tool.ast.BlockAST are in unnamed module of loader 'app')
        at org.antlr.v4.analysis.LeftRecursiveRuleTransformer.setAltASTPointers(LeftRecursiveRuleTransformer.java:231)
        at org.antlr.v4.analysis.LeftRecursiveRuleTransformer.translateLeftRecursiveRule(LeftRecursiveRuleTransformer.java:159)
        at org.antlr.v4.analysis.LeftRecursiveRuleTransformer.translateLeftRecursiveRules(LeftRecursiveRuleTransformer.java:71)
        at org.antlr.v4.semantics.SemanticPipeline.process(SemanticPipeline.java:71)
        at org.antlr.v4.Tool.processNonCombinedGrammar(Tool.java:374)
        at org.antlr.v4.Tool.process(Tool.java:362)
        at org.antlr.v4.Tool.processGrammarsOnCommandLine(Tool.java:321)
        at org.antlr.v4.Tool.main(Tool.java:165)
mingw32-make: *** [makefile:3: build] Error 1

For antlr-ng, I don't get any output (it should always output a crash), but the traceback is the same.

Exception has occurred: TypeError: Cannot read properties of null (reading 'alts')
  at OutputModelController.buildLeftRecursiveRuleFunction (C:\msys64\home\Kenne\save-antlr-ng\src\codegen\OutputModelController.ts:196:49)
    at OutputModelController.buildRuleFunction (C:\msys64\home\Kenne\save-antlr-ng\src\codegen\OutputModelController.ts:154:18)
    at OutputModelController.buildParserOutputModel (C:\msys64\home\Kenne\save-antlr-ng\src\codegen\OutputModelController.ts:85:18)
    at CodeGenerator.generateParser (C:\msys64\home\Kenne\save-antlr-ng\src\codegen\CodeGenerator.ts:91:50)
    at CodeGenPipeline.process (C:\msys64\home\Kenne\save-antlr-ng\src\codegen\CodeGenPipeline.ts:47:37)
    at Tool.processNonCombinedGrammar (C:\msys64\home\Kenne\save-antlr-ng\src\Tool.ts:253:17)
    at Tool.process (C:\msys64\home\Kenne\save-antlr-ng\src\Tool.ts:197:14)
    at Tool.processGrammarsOnCommandLine (C:\msys64\home\Kenne\save-antlr-ng\src\Tool.ts:158:26)
    at Function.main (C:\msys64\home\Kenne\save-antlr-ng\src\Tool.ts:70:19)
    at <anonymous> (C:\msys64\home\Kenne\save-antlr-ng\cli\runner.ts:10:6)

It's crashing on rule terminator.

https://github.com/antlr/grammars-v4/blob/8198039423517f50fc4800c139c73077315d6598/awk/awk.g4#L68-L72

Will attempt a proper fix with hack removed.

[mike-lischke]

Watch out! It's not the same stack. In Java it's in the left recursive rule transformer, while in antlr-ng it's in the output model.

[parrt]

Oh yes, I have seen this in the left recursion resolver. The entire approach of generating a new grammar text to refactor left-recursion, and parsing it again looks suspicious to me. But then I don't know all the reasons that lead to this code.

I would have expected that the ATN is modified in place, like set transformations and so on.

@parrt Do you remember what was the reason for adding that empty action there in the first place?

I don’t have a strong memory of why that would be but it doesn’t sound unreasonable given the complex nature of the algorithm. It sounds like it’s just trying to prevent semantic predicates from being evaluated. I also don’t remember why we did it at the grammar level rather than the ATN. Maybe @sharwell remembers

[kaby76]

The crash is a similar problem for both generators: the AST is not as expected.

The original rule is:

terminator
    : terminator NEWLINE
    | ';'
    | NEWLINE
    ;

In antlr-ng, this gets turned into:

(RULE
  terminator
  (BLOCK
    (ALT
      (SET
        (';' (ELEMENT_OPTIONS (= tokenIndex 167)))
        (NEWLINE (ELEMENT_OPTIONS (= tokenIndex 171))))
      (*
        (BLOCK
          (ALT
            ({Precpred(Context, 3)}? (ELEMENT_OPTIONS (= p 3)))
            (NEWLINE (ELEMENT_OPTIONS (= tokenIndex 163)))
) ) ) ) ) )

The expected AST is supposed to be:

(RULE
  terminator
  (BLOCK
    (ALT
      (BLOCK
        (ALT {} (';' (ELEMENT_OPTIONS (= tokenIndex 167))))
        (ALT (NEWLINE (ELEMENT_OPTIONS (= tokenIndex 171)))))
      (*
        (BLOCK
          (ALT
            ({Precpred(Context, 3)}? (ELEMENT_OPTIONS (= p 3)))
            (NEWLINE (ELEMENT_OPTIONS (= tokenIndex 163)))
) ) ) ) ) )

It trips up here. Indeed, the BLOCK of ALTs was turned into a SET, as the comment said.

[mike-lischke]

Hmm, but that's just a convention and the following code transformation/generation can adapt to that. Since we know we are in left recursion handling at this point, we can convert the set to ALT nodes for further processing. Another option is to figure out why it becomes a set in the first place, if we don't want that. Maybe we can modify AST creation in a way that gives us what we need.

[kaby76]

I was able to fix the problem by removing the {} from the left-recursion rewrite template, then adding the predicate ({ $bb.getParent() != null && $bb.getParent().getParent() != null && $bb.getParent().getParent().getParent() != null && $bb.getParent().getParent().getParent().getType() != ANTLRParser.RULE }? just after bb=BLOCK) in the second alt of the blockSet transform rule in BlockSetTransformer.g (rewrites /BLOCK/ALT+ to a SET) to prevent the rewrite when we see ../../../RULE. This performs the same function as the empty action in preventing the rewriting of /BLOCK/ALT+ into a SET for left-recursive rules but allows for a more natural predicate evaluation. It might require refinements. Over in antlr-ng, I couldn't figure out how to add a predicate to the equivalent code because the antlr3 dependency was removed, and the generated parser is not easy to understand. The inserted predicate and empty action removal fixes antlr/grammars-v4#4465 (without resorting to alt reordering), and the grammars-v4 tests pass.

[mike-lischke]

The linked code doesn't contain the parent checks. Can you point me to the changed code? Is there are PR? The former antlr3 tree parsers have been converted to tree walkers. They are no longer re-generated. I'm sure the test you found can be added easily to the new code.

[kaby76]

Here are the updated files.

BlockSetTransformer.g.txt

LeftRecursiveRules.stg.txt

diff.txt

Not planning on a PR because I want to work on other grammars-v4 issues: adding a symbol table to the golang grammar to remove ambiguities.