ANTLR Grammar Optimisation

About

The aim of this project is to optimise the performance of an existing ANTLR 4 grammar from a start-up. The grammar transforms a domain-specific language (DSL) into an internal intermediate language (IR). The ANTLR grammar, the generated parser source code, and the implemented visitors and listeners are analysed in detail.

The methodology comprises several steps. First, a benchmarking framework is developed in Python to make the effects of optimisations measurable. The parsing process is then analysed using profiling to identify areas with potential for improvement (context-sensitivity spots for 2-stage parsing, expression bottlenecks, LL(1) productions, and so on). Based on these findings and on ideas from the literature, targeted optimisations are iteratively implemented and evaluated.

The results show a performance optimisation of 85.6% for unit tests with the generated ANTLR Python parser. Key approaches include reducing the number of rules through generalisation, rule inlining, and left factorisation in order to minimise lookahead effort and decision branches. In addition, 2-stage parsing was implemented for the ANTLR extension Speedy ANTLR (see own fork).

Interestingly, eliminating ambiguity does not increase performance. This is explained by the deterministic behaviour of ANTLR 4 in conflict situations. Replacing left-recursive productions with non-left-recursive variants did not bring significant improvements either.

A key finding is that the visitor components of the generated parser have a significant impact on overall runtime. While the unit tests exclusively measure the transformation time from DSL to IR, practical tests with customer data showed a lower influence of the grammar optimisations — from 23% to 61%, depending on the customer. Missing visitor caching was identified: parse trees were cached, visitors were not. Through targeted adjustments, the lowest optimisation effect was increased from 23% to 81%.

Future improvements should focus primarily on the visitor components. Overall performance remains heavily dependent on the runtime environment and the programming language (Python), which further relativises the influence of grammar optimisations.

Optimisation types

The following were implemented in different parts of the grammar. Not all of them achieved an improvement.

Parser generation

Set available storage space
2-stage parsing
Same parser instance across multiple parses (persisting the DFA cache)

Lexer

Explicit definition of lexer rules
Lexer rule pattern: comment
Lexer rule pattern: whitespace and newline

Parser

Sequence of sub-rules
(Left-)factorisation
Rule resolution through generalisation
Concrete ANTLR operators (optional, semantic predicates, …)
Remove rules completely covered by others
Manual elimination of left-recursion
Rule inlining

Rule inlining contributed a lot. In the grammar, over 80 parser rules each defined individual lexemes. As soon as ANTLR reached this decision point, it unnecessarily created over 80 subparsers. Flattening these branches into a single non-terminal with implicit lexer rules reduced that cost sharply.

For more detailed information, including how much each optimisation actually achieved, further strategies, theoretical background, or the full paper, contact hi@valenzelektron.com.