[jira] [Created] (GROOVY-12398) Improve lexer and parser performance

["Daniel Sun (Jira)" <ji...@apache.org>]

Daniel Sun created GROOVY-12398:
-----------------------------------

             Summary: Improve lexer and parser performance
                 Key: GROOVY-12398
                 URL: https://issues.apache.org/jira/browse/GROOVY-12398
             Project: Groovy
          Issue Type: Improvement
            Reporter: Daniel Sun


The Groovy ANTLR4 grammar already uses left-recursive expressions, which is the main idea of the [optimized Java grammar|https://github.com/antlr/grammars-v4/tree/master/java/java]. Several remaining lexer and parser costs still match patterns that grammar was written to avoid.

h3. Problem

* Number literals are assembled from a chain of one-character fragments ({{Digit}}, {{Zero}}, {{NonZeroDigit}}, ...). The invalid-octal alternative also counts digits in a mid-rule action loop, which prevents DFA compilation of {{IntegerLiteral}}.
* Every identifier, including ASCII names such as {{Foo}} and {{foo}}, evaluates {{Character.isUpperCase}} to choose {{CapitalizedIdentifier}} vs {{Identifier}}.
* GString and comment predicates ({{isFollowedByJavaLetterInGString}}, {{isFollowedByWhiteSpaces}}) allocate a one-character {{String}} and run {{Pattern.matcher}} on each lookahead.
* {{elementValues}} is ambiguous with assignment: {{@Foo(a = 1)}} can be named pairs or an assignment expression, so {{AdaptivePredict}} explores both (see [antlr/grammars-v4#215|https://github.com/antlr/grammars-v4/issues/215]).

h3. Approach

Keep token types and language semantics unchanged.

* Flatten number and float fragments to character classes, as in the optimized Java lexer. Validate invalid octal once at the end of the alternative.
* Split ASCII identifiers on a predicate-free DFA path: uppercase {{A-Z}} becomes {{CapitalizedIdentifier}}; {{a-z}}, dollar and underscore become {{Identifier}}. Unicode still uses predicates.
* Replace the regex-based predicates with direct character tests.
* Gate {{elementValue}} with {{!isIdentifierAssign(_input)}}, the same idea as Java's {{IsNotIdentifierAssign}}.

h3. Result

Local parse-only measurement (SLL then LL) of {{src/main/groovy}} + {{src/test-resources/core}} (245 files, approximately 570k characters):

||Run||Best||Mean||
|before|0.231s|0.401s|
|after|0.146s|0.169s|

Best run is about 1.6x faster. Mean improves more because prediction is more stable after DFA warmup.


Related: GROOVY-10454, GROOVY-9588




--
This message was sent by Atlassian Jira
(v8.20.10#820010)