Implement redundant epsilon removing optimization

KvanTTT commented 9 months ago

Porting a PR from ANTLR4 repository (https://github.com/antlr/antlr4/pull/3676)

Introduced RedundantEpsilonRemover that performs the following ATN optimizations for BasicState:
- Removing of single incoming epsilon transition
- Removing of single outgoing epsilon transition with several incoming transitions
Removed all optimizations from ParserATNFactory since they are useless, not fully correct and are performed on the separated optimization step
Introduced ATNOptimizerHelper that do the following:
- Calculates incoming transitions that are used in ATN optimizers
- Tracks replacement of state that are being removed during optimization. Old states are being replaced on the new ones in the final step (updateAstNodes)
- Compresses array of ATN states (removes null items after previous optimization steps, compressStates)
Fixed the previous ATNOptimizer and renamed to SetMerger. Now it considers incoming transitions and ATNOptimizerHelper accurately tracks replacements.

Implemented optimizations decreases ATN especially for lexers and should improve performance for generated parsers because of decreased number of method calls. Also they don't affect runtime code except of interpreter part (that is buggy anyway).

Removing of single incoming epsilon transition

Input

single_incoming_output

Output

single_incoming_output

Removing of single outgoing epsilon transition with several incoming transitions

Input

single_outgoing_input

Output

single_outgoing_output

Example

lexer grammar L;
A: 'A' 'B'+ (C | D) 'E';
fragment C: 'C';
fragment D: 'D';

Old ATN

Number of states: 23

old_atn

New ATN

Number of states: 15

new_atn

Plans

It looks like BlockEndState (8, 14), LoopEndState (10) can be also safely removed in the same way since they are not used in decisions. But it might require small changes in runtimes.

ericvergnaud commented 9 months ago

Hey, thanks for this. I have 2 concerns:

these changes apply to the Java runtime, which is going away in favor of the Kotlin runtime
do we have a benchmark demonstrating that this change does improve performance ?

KvanTTT commented 9 months ago

these changes apply to the Java runtime, which is going away in favor of the Kotlin runtime

The changes in runtime are small and not-functional, they can be easily ported to Kotlin later. The PR is mostly about improving the tool (ATN generation). The tool is currently written in Java.

do we have a benchmark demonstrating that this change does improve performance ?

Yes, you can explore the thread in the original PR, specifically this comment and later: https://github.com/antlr/antlr4/pull/3676#issuecomment-1116050463

ericvergnaud commented 9 months ago

Ok then I'd suggest updating Kotlin code accordingly as part of this PR, otherwise it's going to be very messy when I drop the Java runtime ?

KvanTTT commented 9 months ago

Ok then I'd suggest updating Kotli n code accordingly as part of this PR ?

I suggest postponing it since tool currently doesn't rely on Kotlin runtime and it anyway requires a lot of fixes and maybe even modules splitting.

I'm suggesting this PR now because it's already ready and if I decide to suggest it after moving to Kotlin runtime, I'll encountered a lot of conflicts and rewriting code to Kotlin, it's not very productive.

ericvergnaud commented 9 months ago

Need to do Kotlin part rapidly, see issue #39

antlr / antlr5