arXiv:2606.08465v1 [cs.FL] 7 Jun 2026
An Empirical Comparison of General Context-Free Parsers Huan Vo
Danushka Liyanage
Hong Jin Kang
University of Sydney Australia [email protected]
University of Sydney Australia [email protected]
University of Sydney Australia [email protected]
Sasha Rubin
Rahul Gopinath
University of Sydney Australia [email protected]
University of Sydney Australia [email protected]
Abstract Parsing underpins a vast range of software engineering tasks— from compilers and static analyzers to language servers and fuzz testing tools. Yet most parsers deployed in practice are deterministic (LL or LR), forcing developers not only to contort their grammars to fit the parser, but to simplify the very languages they design— sacrificing expressiveness for the sake of parseability. General contextfree parsers eliminate this constraint, but despite decades of algorithmic development, no rigorous head-to-head comparison exists across the major families of parsing algorithms. We present the first unified, controlled benchmark of six generalized parsing algorithms—CYK, Valiant, Earley, GLL, RNGLR, and BRNGLR—plus deterministic LL(1) and LR(1) baselines, all implemented in Rust with shared data structures and parse-tree extraction, and evaluated across 22 grammars ranging from simple expressions to full C++ and Java. Our results show that the cost of generality is lower than widely assumed. On deterministic grammars, the GLR family incurs only a 3× median slowdown over LR(1), with a narrow and predictable variance. GLR is the clear performance winner among generalized parsers and a practical default choice for software engineering tools.
CCS Concepts • Software and its engineering → Parsers.
Keywords Parsing, Generalized Parsing, GLL, GLR, Performance Evaluation
1
Introduction
Parsing is a cornerstone of software engineering. Every tool that reads, analyzes, or transforms source code such as compilers, static analyzers, language servers, IDEs, fuzzers, and program transformation frameworks depends on a parser as its front end. The choice of parsing algorithm, and hence the expressivity of the supported language, has far-reaching consequences for the flexibility, robustness, and maintainability of software engineering tooling. Despite this centrality, most deployed parsers are limited to the deterministic subset of context-free languages: either top-down LL or bottom-up LR. These algorithms are fast—𝑂 (𝑛) in input length— but accept only a restricted subclass of context-free grammars. In practice, this forces developers to engage in grammar hacking [19,
21]: manually rewriting grammars to eliminate left recursion, resolve shift-reduce conflicts, or otherwise contort the structure of the language to satisfy parser constraints. The practical consequence is striking. Despite parsing theory being well-established since the early decades of computer science [17], it has made limited inroads into software engineering practice. Faced with the arcana of LL and LR grammar restrictions, developers routinely abandon formal parsing altogether and write parsers by hand [8, 9, 18]. GitHub alone hosts over 29,800 repositories containing JSON parsers [13]—a format with a simple grammar. This proliferation of ad hoc parsers carries real costs: hand-written parsers are harder to maintain, more prone to subtle bugs and vulnerabilities. The Language-theoretic Security community [22] has long argued that formal, declarative parsers are a prerequisite for robust and secure input handling, yet adoption remains low. The root cause, we argue, is not that formal grammar-based parsing is difficult to apply in practice. Instead, the issue is that the perceived complexity of grammar engineering for satisfying deterministic parsers has obscured simpler, more general alternatives [21, 34]. During grammar engineering, it is common to add one more rule, and find oneself with several shift-reduce conflicts [36], effectively stopping further progress. While general context-free parsers1 such as CYK [40], Earley [7], GLR [33], and GLL [28] accept any context-free grammar without modification, they were historically dismissed as impractical due to their 𝑂 (𝑛 3 ) worst-case complexity [14]. However, they have seen renewed interest in tools like Tree-sitter [5], which uses incremental GLR for syntax highlighting, Parglare [6], a complete GLR parser, and GNU Bison, which now offers a GLR mode. Other approaches, such as Parsing Expression Grammars [12], sidestep the problem by using ordered choice—but at the cost of redefining language semantics and complicating grammar composition. Yet, despite decades of development across these algorithm families [17], no rigorous head-to-head comparison exists. As later discussed, existing evaluations are narrow: they typically cover a single algorithm family, use different implementation languages, different data structures, or different output representations, making direct comparison impossible. It remains unclear, in practice, how much performance is sacrificed by choosing a generalized parser, or which generalized algorithm is best suited for software engineering tasks. These open questions leave the misconception of
1 These are also called generalized parsers, which we will use interchangeably.
Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, and Rahul Gopinath
prohibitive cost unchallenged, and the status quo of proliferating hand-written parsers intact. We close this gap by implementing six generalized algorithms across all four major parsing families: Earley and GLL (online, topdown), RNGLR and BRNGLR (online, bottom-up GLR variants), and matrix multiplication based parsers such as CYK and Valiant (offline, bottom-up)—alongside deterministic LL(1) and LR(1) baselines. All implementations are written in Rust, a compiled systems language without garbage collection, using shared grammar representations and shared data structures. This controlled environment allows fair, direct comparison across 22 grammars ranging in complexity from simple expressions to full C++ and Java. We address the following research questions:
⟨expr⟩ → ⟨expr⟩ ‘+’ ⟨expr⟩ | ⟨expr⟩ ‘-’ ⟨expr⟩ | ‘(’ ⟨expr⟩ ‘)’ | ⟨number⟩ ⟨number⟩ → ⟨digit⟩ ⟨number⟩ | ⟨digit⟩ ⟨digit⟩ → ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’ Figure 1: An arithmetic expression grammar
assigns to (1+2)+3: the parentheses force the left 〈expr〉 to span (1+2), and the outer 〈expr〉 combines it with 3 via addition. 〈expr〉
RQ1. How do various families of general-context-free parsing algorithms such as matrix-based, top-down, and bottom-up compare in terms of parsing efficiency? RQ2. How do deterministic parsing algorithms such as LL(1) and LR(1) compare against practical general context-free parsing algorithms such as BRNGLR, RNGLR, GLL, and Earley? RQ3. How effective is grammar-hacking where a general-contextfree grammar is refactored to conform to LR(1) or LL(1) constraints? Our results show that the GLR family of parsers is the fastest among the generalized parsers in our study. On deterministic grammars, the GLR family incurs only a 3× median slowdown compared to the LR(1) parser. GLL is slower, with a ∼6× median overhead over LR(1), while Earley is the slowest, at ∼10× median overhead. We make the following contributions: • The first unified, controlled benchmark of six generalized parsing algorithms across four algorithm families on realworld software engineering grammars. • A detailed comparison of the parser performance on refactored grammars recognizing the same language. • Practical guidance for SE tool builders on when to use generalized parsing as a default, and when grammar hacking can be counterproductive.
2 Background 2.1 Context-Free Grammars and Parsing Consider the arithmetic expression (1+2)+3. The parentheses make the grouping explicit: add 2 to 1 first, then add 3 to the result. Without parentheses, as in 1+2-3, the situation is less clear: grouping the addition first gives (1+2)-3, while grouping the subtraction first gives 1+(2-3), and these produce different values since subtraction is not associative. A parser’s job is to recover this structural information from a flat string of characters. The primary output of a parser is a parse tree (or derivation tree): a rooted tree whose root represents the whole input, whose internal nodes represent syntactic categories such as 〈expr〉 or 〈number〉, and whose leaves are the individual input tokens. Figure 1 shows a grammar for arithmetic expressions, which we use as our running example throughout this section. The grammar consists of production rules, each of which says that a syntactic category may be formed in a particular way. Together the rules define every valid string and every valid parse tree in the language. Figure 2 shows the parse tree that the grammar
〈expr〉
+
〈expr〉
(
)
〈expr〉 〈number〉
〈number〉
〈digit〉
〈digit〉
〈digit〉
3
1
2
〈number〉
+
Figure 2: Expression grammar parse tree for (1+2)+3 For a string such as 1+2-3, the grammar permits two trees— one for each grouping—making it ambiguous. This property has consequences for parser design, examined in the next subsection. Parsing encompasses two related tasks. Recognition determines whether 𝑤 ∈ 𝐿(𝐺): does the input conform to the grammar? Parsetree construction goes further and recovers one or more derivation trees for 𝑤. For an unambiguous grammar every string has at most one tree; for an ambiguous grammar like Figure 1, multiple trees may exist and must all be accounted for. Recognition is the primary benchmark criterion; tree extraction is a separate pass that does not affect the asymptotic cost (Section 3). We now make these notions precise. A Context-Free Grammar (CFG) is a 4-tuple 𝐺 = (𝑁 , Σ, 𝑃, 𝑆), where 𝑁 is a finite set of nonterminals (syntactic categories), Σ is a finite set of terminals (the alphabet of the input), 𝑃 is a finite set of production rules of the form 𝐴 → 𝛼 where 𝐴 ∈ 𝑁 and 𝛼 ∈ (𝑁 ∪ Σ) ∗ , and 𝑆 ∈ 𝑁 is the start symbol. A grammar generates strings by derivation: starting from 𝑆 (here 〈expr〉), non-terminals are repeatedly replaced by production-rule right-hand sides until only terminals remain, simultaneously constructing the parse tree. Expanding the leftmost non-terminal yields a leftmost derivation; expanding the rightmost gives a rightmost derivation. The set of all strings derivable from 𝑆 is the language 𝐿(𝐺). It is a classic result that for every CFG, the recognition problem can be solved in cubic time [7, 40]. For most practical purposes this is too slow, motivating the development of restricted grammar classes that admit linear-time algorithms.
2.2
Ambiguity and Determinism
A grammar 𝐺 is ambiguous if some string 𝑤 ∈ 𝐿(𝐺) has two or more distinct parse trees. The grammar in Figure 1 is itself ambiguous: 1+2-3 admits the two derivations, visualized as proof-tree
An Empirical Comparison of General Context-Free Parsers
Table 1: Parsing algorithm families
derivations with only 〈expr〉 shown for clarity: 1 + 2 <expr> <expr>
3
1 and
2 - 3 + <expr> <expr>
These correspond to (1+2)-3 and 1+(2-3), which yield different semantic values since subtraction is not associative. The classic dangling else illustrates a deeper difficulty: even a natural, unambiguous-seeming language construct can resist a clean deterministic grammar. The rule ⟨stmt⟩ → ‘if’ ⟨E⟩ ‘then’ ⟨stmt⟩ | ‘if’ ⟨E⟩ ‘then’ ⟨stmt⟩ ‘else’ ⟨stmt⟩ is ambiguous: in if 𝑎 then if 𝑏 then 𝑠 1 else 𝑠 2 , the else can attach to either if. Most languages resolve this informally— associate else with the nearest unmatched if, but the intuitive representation of the grammar does not encode this rule, and no clean unambiguous rewrite exists without introducing auxiliary non-terminals that obscure the grammar’s intent. C and Java sidestep the problem in the parser rather than the grammar, quietly resolving the shift-reduce conflict in favor of shifting. Similarly, for the expression grammar, an addition rule is intuitively represented as: 〈E〉 → 〈E〉 ‘+’ 〈E〉, and not as 〈E〉 → 〈T 〉 ‘+’ 〈F〉
2.3
Deterministic Parsers
Deterministic parsers exploit the LL or LR structure of a grammar to parse in 𝑂 (𝑛) time. LL parsers. LL parsers work top-down, building the parse tree from the root. At each step, they predict which production rule to expand based on the current non-terminal and the next token. LR parsers. LR parsers work bottom-up, assembling the parse tree from the leaves upward. First introduced by Knuth [20], they maintain an explicit state stack and make decisions—shift the next token onto the stack, or reduce the top of the stack to a non-terminal—by consulting a precomputed parse table. Because decisions are made after seeing the full right-hand side of a rule, LR parsers handle left recursion naturally and are strictly more powerful than LL parsers. However, the parse tables can contain shift-reduce or reduce-reduce conflicts when the grammar requires more than 𝑘 tokens of lookahead, signalling that the grammar lies outside LR(𝑘).
2.4
Generalized Parsers
Generalized parsers accept any CFG, handling both ambiguity and constructs that fall outside the deterministic grammar classes. Their worst-case runtime is 𝑂 (𝑛𝜔 ), where 𝜔 = 3 for most parsers. Our work studies algorithms in three families along two axes: build direction (top-down vs. bottom-up) and scan discipline (online left-to-right vs. offline). Online algorithms process the input one token at a time, left to right, and can in principle begin producing output before the input is fully consumed. Offline algorithms require the complete input string before any work begins, filling a table over all substrings simultaneously. Table 1 summarizes these algorithms alongside deterministic baselines from Section 2.3. We describe each family in turn.
Algorithm
Build
Scan
Deterministic LL(1) Top-down Online LR(1) Bottom-up Online Generalized — online, top-down Earley Top-down Online GLL Top-down Online Generalized — online, bottom-up RNGLR Bottom-up Online BRNGLR Bottom-up Online Generalized — offline, bottom-up CYK Bottom-up Offline Valiant† Bottom-up Offline
Accepts
𝑂 (𝜔 )
LoC
LL(1) only LR(1) only
𝑂 (𝑛) 𝑂 (𝑛)
254 923
All CFG All CFG
𝑂 (𝑛 3 ) 𝑂 (𝑛 3 )
708 912
All CFG All CFG
𝑂 (𝑛 3 ) 𝑂 (𝑛 3 )
1,699 2,015
All CFGCNF All CFGCNF
𝑂 (𝑛 3 ) 𝑛3 𝑂 ( log 𝑛)
143 312
† Using the method of Four Russians.
3
Methodology
CYK CYK (Cocke–Younger [40]–Kasami) uses dynamic programming in a bottom-up fashion. It fills an 𝑛×𝑛 triangular table. It runs in consistent 𝑂 (𝑛 3 ) and requires the grammar to be in Chomsky Normal Form (CNF). Valiant [35] showed that parsing can be reduced to boolean matrix multiplication, achieving sub-cubic time using fast multiplication algorithms such as Strassen’s [32]. In our implementation, we use the Method of Four Russians [3], 𝑛3 which is a subcubic (𝑂 ( log 𝑛 )) practical matrix multiplication algorithm implemented in the Rust library m4ri2 . Earley The Earley parser [7] handles any CFG without grammar conversion. It operates top-down, maintaining at each input position a set of Earley items—-dotted rules 𝐴 → 𝛼 • 𝛽 that record how far a rule has been matched and where the match began. Its worst-case complexity is 𝑂 (𝑛 3 ), but it degrades gracefully: 𝑂 (𝑛 2 ) on unambiguous grammars and 𝑂 (𝑛) on a broad class of deterministic grammars. Aycock et al. [4] resolved a long-standing issue with epsilon rules, and Leo [23] introduced a right-recursion optimization that restores linear time on LR(𝑘) grammars without requiring lookahead or the LR table. Generalized LL GLL, introduced by Scott and Johnstone in 2010 [28], generalizes LL parsing using a Graph Structured Stack to explore multiple derivations without redundant recomputation. It handles left-recursive grammars—-LL’s central limitation—-and can be implemented in a recursive-descent style without large precomputed parse tables. Generalized LR GLR [33] extends LR by forking the parse stack at every conflict and pursuing all alternatives in parallel. A Graph-Structured Stack (GSS) shares stack prefixes across branches, preventing exponential blow-up in most cases. Issues with hidden left recursion and epsilon rules were solved by Scott and Johnstone through Right-Nulled GLR (RNGLR) [27], and its binary variant BRNGLR [31], which achieves a strict 𝑂 (𝑛 3 ) worst-case bound for all grammars. 2 From here on, we use Valiant to describe the Valiant algorithm with the Method of
Four Russians.
Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, and Rahul Gopinath
General context-free
LR(1), not LL(1)
LL(1)
Table 2: Benchmark grammars and their structural properties. Prod. = productions; NT = non-terminals; Term. = terminals; Null. = nullable non-terminals; Left Rec. = left recursion present; Ambiguous = grammar is known to be ambiguous. Grammar
Category
Prod.
NT
Term.
Null.
Left Rec.
Ambiguous
LL(1)
LR(1)
S-Expr LL-1 Expr LL-1 JSON LL-1 TinyPascal Expr (lr) Expr (rr) JSON (rr) JSON (lr) TinyC LR-1 S-Expression Bool Expr (ambig) JSON (ambig) TinyC ANSI C Pascal Java C++ CSS HTML Shell SQL
Simple Simple Moderate Moderate Simple Simple Moderate Moderate Moderate Simple Simple Simple Moderate Moderate Complex Complex Complex Complex Complex Complex Complex Complex
49 24 135 68 21 21 140 140 66 165 6 18 140 63 405 501 1835 762 582 686 393 623
10 9 15 17 6 6 20 20 16 20 1 3 20 15 85 215 532 161 127 172 32 87
39 16 94 63 16 16 94 94 54 94 10 16 94 45 94 95 99 94 94 94 94 85
2 3 7 9 0 0 5 5 2 5 0 0 7 1 5 66 222 10 56 67 5 4
— — — — ✓ — — ✓ ✓ — ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
— — — — — — — — — ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
✓ ✓ ✓ ✓ — — — — — — — — — — — — — — — — — —
✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ — — — — — — — — — — — — —
Empirical evaluation [16] suggests RNGLR and BRNGLR are the best-performing GLR variants in practice. Benchmark. A central challenge in comparing parsers is isolating algorithmic differences from implementation artifacts: a parser written in Python will behave very differently from one written in C, even if both implement the same algorithm. We therefore implement all parsers in a single unified Rust framework. Every implementation shares the same grammar representation [41], tokenstream format, AST structures, and memory management strategy, and all are compiled with identical optimization settings (–release). Each parser was implemented directly from its best-known published algorithm or optimizations without tuning beyond what the publication describes, so that observed differences reflect the algorithms rather than engineering choices. To validate correctness, each implementation was independently reviewed by a second researcher. For each grammar, we generated test inputs with a grammar-based fuzzer [41] and verified that the original string can be reconstructed from the parse tree. We also evaluated diverse input mutations to verify that every parser correctly rejects strings outside the grammar. Parser Implementations. We implement the six parsing algorithms mentioned in Table 1. CYK A standard dynamic programming parser. Valiant Matrix-multiplication variant of CYK, using the Method of Four Russians [3]. Earley With Aycock–Horspool [4] and Leo’s optimization [23]. GLL Johnstone’s Generalized LL parser [15]. RNGLR Right-Nulled GLR parser from Economopoulos [11]. BRNGLR Binary RNGLR variant from Economopoulos [11].
We also implement LL(1) and LR(1) parsers for baselines. LR and GLR parsers use precomputed parse tables. All parsers operate in scannerless mode. For Valiant and CYK, the grammars are transformed to CNF prior to parsing. Valiant uses the Method of Four Russians [3] for boolean matrix multiplication, via m4ri-rust [39]. Grammar Selection. We evaluate our parsers against 22 grammars. The dataset ranges from simple structures (S-Expressions) to full-scale programming languages (C++, Java). Table 2 details the size and classification of each grammar. While generalized parsers consume these grammars directly, deterministic baselines require refactored versions. Refactoring includes left-recursion elimination, left-factoring, and rule inlining to remove indirect recursion. For TinyC and TinyPascal, keywords were capitalized (if→IF) to simulate a lexer, and dangling-else ambiguity was resolved by rule splitting. Consequently, the refactored grammar may accept a slightly different language; this is unavoidable in our scannerless setting. Inputs. Inputs were generated by bounded-depth grammar-based fuzzing: Only inputs within a defined size is retained; the upper bound is set so that the fastest parser completes within one second. Measurement. For each (parser, grammar, input) triple, an iteration is a complete parse timed from the first token to the final parse-forest node. Each triple runs for at least 10 iterations; if the total time is under 500 ms, iterations are increased up to 20. Short inputs thus run 20 iterations, longer ones 10. We report the median iteration time to mitigate transient system noise. Triples with a median parse time exceeding 1 second are excluded from larger input analyses, though individual runs over 1 second are retained. Memory is measured by polling RSS every 1 ms. Experiments are conducted on an Apple M1 with 16 GB RAM, with parsers compiled via rustc –release.
An Empirical Comparison of General Context-Free Parsers
Table 3: Median runtime (ms) of CYK and Valiant. Grammar
Tokens
CYK (ms)
Valiant (ms)
Earley (ms)
0–10 0.077 ± 0.023 — 0.044 ± 0.022 S-Expression 10–20 0.233 ± 0.067 — 0.095 ± 0.013 20–100 3.53 ± 4.12 — 0.243 ± 0.080 0–10 0.018 ± 0.006 8.78 ± 6.06 0.021 ± 0.004 Expr (lr) 10–20 0.083 ± 0.030 150 ± 72 0.050 ± 0.008 20–100 2.41 ± 2.24 796 ± 380 0.190 ± 0.067 0–10 0.006 ± 0.002 2.16 ± 5.82 0.004 ± 0.002 Bool 10–20 0.025 ± 0.011 80.0 ± 60.8 0.015 ± 0.006 20–100 0.530 ± 1.141 248 ± 376 0.140 ± 0.451 0–10 0.008 ± 0.003 1.53 ± 4.16 0.013 ± 0.006 Expr (ambig) 10–20 0.026 26.5 0.032 20–100 2.26 ± 1.31 3306 ± 3414 1.17 ± 3.18 0–10 0.014 ± 0.007 2.14 ± 6.07 0.015 ± 0.006 Expr (rr) 10–20 0.045 39.2 0.033 20–100 4.24 ± 2.34 1330 0.235 ± 0.068 Blue indicates best values, and orange worst values.
4
Results
Table 4 summarizes absolute median runtimes across all 22 grammars, broken down by input-size bucket, the classification of the grammar, and the grammar itself. Similarly Table 5 summarizes the peak memory usage while processing these inputs.
4.1
RQ1. Comparison of Parser Families
Offline generalized parsers. Table 3 shows our experimental results for offline generalized parsers. Despite Valiant’s superior as𝑛3 3 ymptotic complexity of 𝑂 ( log 𝑛 ) versus CYK’s 𝑂 (𝑛 ), in practice, Valiant is dramatically slower than CYK across every tested grammar. On Expr (lr) at 20–100 tokens, CYK takes 2.41 ms while Valiant takes 796 ms—a 330× difference. The gap widens further on ambiguous grammars: Valiant reaches 3,306 ms on Expr (ambig) at 20– 100 tokens, versus 2.26 ms for CYK. Our results show that these algorithms are inefficient. Earley is faster than both CYK and Valiant on every grammar: on Expr (lr) at 20–100 tokens Earley completes in 0.19 ms, a 13× speedup over CYK and a 4,000× speedup over Valiant. As these algorithms are impractical even at token counts below 100, we do not evaluate them further. Both CYK and Valiant are impractical at realistic input sizes. Earley outperforms both even on inputs of fewer than 100 tokens.
Runtime of online generalized parsers. Table 4 reports median runtime across input-size buckets for Earley, GLL, RNGLR, and BRNGLR. RNGLR and BRNGLR are the fastest generalized parsers by a consistent margin. At 15k–30k tokens on TinyPascal, RNGLR takes 21 ms versus 40 ms for GLL and 157 ms for Earley; on S-Expr LL-1 the same ordering holds at 26.4 ms, 45.6 ms, and 213 ms. Across all grammars and buckets where all four algorithms are applicable, RNGLR and BRNGLR are typically two to three times faster than GLL and four to ten times faster than Earley. RNGLR and BRNGLR themselves are essentially indistinguishable, typically within 15% of each other in every case.
GLL’s performance is sensitive to grammar structure. On LLfriendly inputs it is competitive with RNGLR, but it degrades severely on left-recursive grammars: on JSON (lr) at 15k–30k tokens, GLL takes 346 ms while RNGLR takes 17 ms—a 20× gap. On SQL, GLL reaches 0.08 ms at 0-5k tokens versus 0.03–0.04 ms for RNGLR and BRNGLR. Earley is generally the slowest generalized parser. RNGLR and BRNGLR are consistently the fastest generalized parsers, and are effectively equivalent to each other. GLL is competitive on LL-friendly grammars but degrades sharply on left-recursive inputs. Earley is consistently the slowest generalized parser.
Memory consumption. Table 5 reveals a different ordering than runtime. LL(1) and LR(1) parsers maintain negligible memory usage— at or below the 0.016 MB measurement floor—across all grammars and input sizes. RNGLR and BRNGLR are similarly memory-efficient, remaining at 0.016 MB for the vast majority of grammars even at 15k–30k tokens, comparable in practice to the deterministic parsers. Earley uses slightly more memory on a few grammars (Pascal at 15k–30k: 0.141 MB; C++ at 5k–15k: 1.58 MB, S-Expr LL-1: 4.16 MB) but remains modest in most cases. GLL stands out as the only generalized parser with substantial memory growth for numerous grammars. Its consumption rises steeply on larger and more complex grammars: 2.30–2.41 MB on S-Expression, TinyC, and TinyPascal at 15k–30k tokens; 3.84 MB on Pascal at 5k–15k tokens, growing to 12.5 MB at 15k–30k tokens; 7.10 MB on ANSI C and 11.6 MB on C++ at 5k–15k tokens. RNGLR on the same grammars stays at 0.016 MB throughout. RNGLR and BRNGLR are the most memory-efficient generalized parsers, matching deterministic parsers on most grammars.
4.2
RQ2. Deterministic vs. Generalized Parsers
Runtime. Table 4 and Figure 3 compare deterministic and generalized parsers across all input-size buckets. LL(1) and LR(1) are the fastest parsers in every row where they are applicable, typically running at 5–8 ms at 15k–30k tokens regardless of grammar, while even the fastest generalized parser (RNGLR) runs at 15–26 ms on most grammars (up to 63–115 ms on JSON variants) at the same input size. LL(1) is consistently 10–20% faster on LL(1) grammars. Comparing on five LR(1) baseline grammars, the median runtime overhead relative to LR(1) is: RNGLR ×3.0 (IQR: ×2.9–×3.1, max ×4.6); BRNGLR ×3.0 (IQR: ×2.7–×3.2, max ×5.7); GLL ×6.0 (IQR: ×4.5–×8.4, max ×139); Earley ×10.0 (IQR: ×7.9–×11.4, max ×15.3). GLR’s overhead is narrow and predictable: the IQR spans only 0.2× around the median, and no grammar class causes it to exceed ×5.7. GLL’s overhead is considerably more variable: its IQR is nearly twenty times wider than GLR’s. Deterministic parsers are 3× faster than the best generalized alternative at large input sizes. Among generalized parsers, GLR’s overhead over LR(1) is narrow and predictable (×3, IQR ±0.2), while GLL’s varies widely and can reach ×139 on left-recursive grammars.
Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, and Rahul Gopinath
Table 4: Median runtime (ms) by grammar and input-size bucket. Blue is best, orange worst. Grammar TinyPascal
LL(1)
S-Expr LL-1
Expr LL-1
JSON LL-1
LR(1), not LL(1)
JSON (rr)
JSON (lr)
Expr (lr) Expr (rr) TinyC LR-1
S-Expression
TinyC
General context-free
Bool Expr (ambig) JSON (ambig) ANSI C Pascal Java C++ CSS HTML Shell SQL
Tokens 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 0–5k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 0–5k 5k–15k 0–5k 0–5k 0–5k 0–5k
Deterministic (ms) LL(1) LR(1) 0.059 ± 0.379 2.16 ± 0.68 5.33 ± 1.01 0.780 ± 0.392 2.98 ± 0.62 7.17 0.028 ± 0.415 2.78 ± 0.96 6.03 ± 1.29 0.212 ± 0.591 2.84 ± 1.12 7.79 ± 2.50 — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
0.083 ± 0.477 2.75 ± 0.86 6.68 ± 1.25 0.907 ± 0.462 3.53 ± 0.72 8.19 0.037 ± 0.524 3.53 ± 1.23 7.65 ± 1.59 0.234 ± 0.656 3.17 ± 1.14 7.67 ± 1.72 0.170 ± 0.463 2.24 ± 0.78 5.39 ± 1.19 0.172 ± 0.469 2.27 ± 0.80 5.49 ± 1.22 0.030 ± 0.424 2.91 ± 0.98 6.14 ± 1.28 0.089 ± 0.050 0.409 ± 0.341 2.19 ± 0.65 4.84 ± 1.29 — — — — — — — — — — — — — — — — — — — — — — — —
Memory. LL(1) and LR(1) stay at the 0.016 MB measurement floor across every grammar and every input-size bucket in Table 5. Among generalized parsers, RNGLR and BRNGLR also remain at 0.016 MB on most grammars, matching the deterministic parsers in practice.
Earley 1.09 ± 8.50 57.8 ± 21.1 157 ± 31 15.5 ± 9.5 85.2 ± 21.0 213 0.353 ± 5.480 40.9 ± 17.3 100 ± 24 5.07 ± 25.78 132 ± 53 384 ± 105 4.56 ± 23.75 125 ± 48 342 ± 98 4.13 ± 23.12 131 ± 57 393 ± 145 0.266 ± 4.088 30.9 ± 12.7 77.3 ± 17.8 0.810 ± 0.488 5.10 ± 4.96 35.7 ± 14.3 95.6 ± 29.2 5.13 ± 7.59 61.0 ± 26.1 170 ± 43 0.257 ± 4.439 50.5 ± 18.0 125 ± 28 0.016 ± 0.874 15.3 ± 247.5 4.80 ± 23.89 122 ± 46 356 ± 100 15.5 ± 63.0 276 ± 70 11.2 ± 32.3 160 ± 62 460 ± 64 7.75 ± 52.69 299 ± 73 91.4 ± 148.5 1151 4.30 ± 45.95 2.57 ± 15.62 3.99 ± 8.75 0.068 ± 1.694
Generalised (ms) GLL RNGLR 0.311 ± 2.042 13.6 ± 5.1 39.7 ± 8.3 3.62 ± 1.91 16.6 ± 3.8 45.6 0.150 ± 2.181 17.1 ± 7.4 43.1 ± 11.2 0.991 ± 2.979 15.4 ± 7.2 46.9 ± 11.7 0.803 ± 2.163 11.3 ± 4.8 32.8 ± 8.6 1.22 ± 13.87 86.2 ± 65.0 346 ± 204 0.197 ± 3.041 24.1 ± 10.6 60.0 ± 14.2 0.603 ± 0.345 2.85 ± 2.56 18.4 ± 6.6 47.3 ± 14.2 1.62 ± 1.97 14.6 ± 6.4 43.6 ± 10.8 0.149 ± 2.330 23.7 ± 8.9 61.2 ± 13.1 0.021 ± 0.269 16.6 ± 49.6 0.829 ± 2.192 11.3 ± 4.9 34.4 ± 9.0 8.19 ± 32.99 151 ± 42 4.64 ± 14.24 74.1 ± 30.4 214 ± 26 3.62 ± 30.84 198 ± 46 58.6 ± 85.4 365 ± 96 1.15 ± 6.43 1.08 ± 10.29 8.27 ± 47.32 0.078 ± 49.789
0.227 ± 1.386 8.13 ± 2.73 21.1 ± 4.6 2.63 ± 1.31 10.2 ± 2.2 26.4 0.104 ± 1.426 9.55 ± 3.35 22.2 ± 5.2 0.695 ± 3.356 25.6 ± 20.0 115 ± 77 0.517 ± 2.090 15.1 ± 10.4 63.6 ± 39.0 0.505 ± 1.337 6.49 ± 2.52 17.4 ± 4.8 0.085 ± 1.218 8.08 ± 2.94 18.6 ± 4.6 0.246 ± 0.140 1.22 ± 1.02 6.49 ± 2.01 14.8 ± 5.0 0.917 ± 1.109 7.20 ± 2.77 19.6 ± 5.5 0.065 ± 0.941 8.22 ± 2.62 19.7 ± 4.8 0.009 ± 0.261 7.86 ± 25.74 0.524 ± 2.087 14.9 ± 10.5 64.0 ± 39.4 5.33 ± 14.02 60.3 ± 14.1 3.33 ± 7.90 38.4 ± 14.6 105 ± 12 1.29 ± 4.93 29.4 ± 6.7 15.0 ± 24.3 128 ± 57 1.22 ± 10.36 0.903 ± 34.885 2.66 ± 16.58 0.028 ± 0.459
BRNGLR 0.237 ± 1.398 8.73 ± 2.84 23.8 ± 5.0 2.37 ± 1.18 9.18 ± 1.99 24.0 0.110 ± 1.448 9.81 ± 3.43 22.9 ± 5.2 0.641 ± 3.182 24.5 ± 19.6 112 ± 76 0.466 ± 1.931 14.2 ± 10.2 61.1 ± 38.7 0.454 ± 1.181 5.71 ± 2.25 15.5 ± 4.4 0.090 ± 1.309 8.77 ± 3.13 21.8 ± 4.8 0.259 ± 0.146 1.29 ± 1.07 6.90 ± 2.15 16.1 ± 5.5 0.992 ± 1.199 7.69 ± 3.01 22.2 ± 5.7 0.072 ± 0.990 8.94 ± 2.77 22.8 ± 5.1 0.011 ± 0.230 6.61 ± 19.52 0.472 ± 1.937 14.2 ± 10.2 61.3 ± 39.0 4.43 ± 12.66 54.9 ± 12.8 3.25 ± 7.76 38.8 ± 14.4 103 ± 13 1.25 ± 4.78 28.0 ± 6.4 13.9 ± 21.7 112 ± 46 0.993 ± 8.003 0.732 ± 25.722 2.23 ± 14.08 0.036 ± 0.571
GLL diverges at larger inputs, reaching 2–4 MB on simpler grammars and 12.5 MB on Pascal at 15k–30k tokens. Earley is more modest, staying below 0.2 MB on most grammars with the exception of C++ (1.58 MB at 5k–15k tokens).
An Empirical Comparison of General Context-Free Parsers
Table 5: Median peak memory (MB) by grammar and input-size bucket. Blue is best, orange worst. Grammar TinyPascal
LL(1)
S-Expr LL-1
Expr LL-1
JSON LL-1
LR(1), not LL(1)
JSON (rr)
JSON (lr)
Expr (lr) Expr (rr) TinyC LR-1
S-Expression
TinyC
General context-free
Bool Expr (ambig) JSON (ambig) ANSI C Pascal Java C++ CSS HTML Shell SQL
Tokens 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 15k–30k 0–5k 0–5k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 0–5k 5k–15k 15k–30k 0–5k 5k–15k 0–5k 5k–15k 0–5k 0–5k 0–5k 0–5k
Deterministic (MB) LL(1) LR(1) 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 0.016 ± 0.013 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.003 0.016 ± 0.003 — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 0.016 ± 0.000 0.016 ± 0.002 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.002 0.016 ± 0.010 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.012 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 — — — — — — — — — — — — — — — — — — — — — — — —
Deterministic parsers consume negligible memory regardless of input size. RNGLR and BRNGLR match this behavior on most grammars. GLL is the only parser whose memory grows substantially with input size and grammar complexity.
Earley 0.016 ± 0.008 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 4.16 0.016 ± 0.006 0.016 ± 0.004 0.016 ± 0.004 0.016 ± 0.003 0.016 ± 0.000 0.016 ± 0.024 0.016 ± 0.031 0.062 ± 0.038 0.062 ± 0.035 0.016 ± 0.000 0.016 ± 0.002 0.016 ± 0.198 0.016 ± 0.036 0.016 ± 0.003 0.016 ± 0.005 0.016 ± 0.006 0.016 ± 0.008 0.016 ± 0.015 0.016 ± 0.041 0.016 ± 0.002 0.016 ± 0.007 0.047 ± 0.021 0.016 ± 0.006 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.004 0.016 ± 0.531 0.016 ± 0.036 0.062 ± 0.041 0.062 ± 0.333 0.031 ± 0.072 0.094 ± 0.083 0.016 ± 0.024 0.016 ± 0.037 0.141 ± 0.064 0.016 ± 0.061 0.062 ± 0.135 0.047 ± 0.239 1.58 0.016 ± 0.224 0.016 ± 0.010 0.016 ± 0.016 0.016 ± 0.005
4.3
Generalised (MB) GLL RNGLR 0.016 ± 0.000 0.016 ± 0.089 2.38 ± 1.07 0.016 ± 0.002 0.531 ± 0.088 4.41 0.016 ± 0.003 0.062 ± 1.018 2.42 ± 1.24 0.016 ± 0.023 0.016 ± 0.653 0.297 ± 1.383 0.016 ± 0.134 0.016 ± 0.054 0.828 ± 1.359 0.016 ± 0.007 0.016 ± 0.087 0.016 ± 0.000 0.016 ± 0.005 0.016 ± 1.225 2.44 ± 1.69 0.016 ± 0.009 0.016 ± 0.002 0.016 ± 0.824 2.34 ± 1.26 0.016 ± 0.002 0.016 ± 0.920 2.30 ± 1.33 0.016 ± 0.000 0.016 ± 0.994 2.41 ± 1.20 0.016 ± 0.000 0.016 ± 1.374 0.016 ± 0.101 0.016 ± 0.055 0.719 ± 1.448 0.016 ± 1.488 7.10 ± 4.56 0.016 ± 0.893 3.84 ± 1.96 12.5 ± 1.7 0.016 ± 1.385 4.95 ± 2.54 0.078 ± 5.131 11.6 ± 15.2 0.016 ± 0.046 0.016 ± 1.191 0.016 ± 0.295 0.016 ± 0.000
0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.807 0.016 ± 0.000 0.109 ± 0.133 0.344 0.016 ± 0.002 0.016 ± 0.000 0.016 ± 0.553 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.448 0.016 ± 0.004 0.016 ± 0.005 0.016 ± 0.487 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.560 0.016 ± 0.002 0.016 ± 0.005 0.016 ± 0.769 0.016 ± 0.002 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 1.195 0.016 ± 0.005 0.016 ± 0.096 0.016 ± 0.462 0.016 ± 0.163 0.016 ± 1.734 0.016 ± 0.002 0.016 ± 0.003 0.094 ± 0.035 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.561 0.016 ± 1.078 0.016 ± 0.005 0.016 ± 0.037 0.016 ± 0.022 0.016 ± 0.000
BRNGLR 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.928 0.016 ± 0.000 0.016 ± 0.000 0.016 0.016 ± 0.002 0.016 ± 0.033 0.016 ± 0.829 0.016 ± 0.035 0.016 ± 0.000 0.016 ± 0.304 0.016 ± 0.002 0.016 ± 0.003 0.016 ± 0.703 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.396 0.016 ± 0.000 0.016 ± 0.005 0.031 ± 1.018 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.007 0.016 ± 0.040 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.015 0.016 ± 0.017 0.016 ± 0.000 0.016 ± 0.993 0.016 ± 0.002 0.016 ± 0.002 0.016 ± 0.487 0.016 ± 0.274 0.016 ± 1.659 0.016 ± 0.000 0.016 ± 0.020 0.062 ± 0.049 0.016 ± 0.000 0.016 ± 0.000 0.016 ± 0.580 0.016 ± 0.356 0.016 ± 0.002 0.016 ± 0.000 0.016 ± 0.020 0.016 ± 0.000
RQ3. Effectiveness of Grammar Refactoring
We compare four variants of two representative grammars—JSON and Expr—across all parsers to isolate the effect of grammar structure. JSON and Expr are the only grammars in our benchmark for
Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, and Rahul Gopinath
TinyPascal
Time (ms)
102
100
LL(1) LR(1) Earley GLL RNGLR BRNGLR
10 −2 102
103 Expr (lr)
104
Time (ms)
102
100
Grammar-hacking to LL(1)/LR(1) consistently reduces runtime by 4– 7× compared to the fastest generalized parser on the same grammar.
10 −2
Effect of grammar structure on generalized parsers. Grammar structure has a substantial and parser-specific impact even without a switch to deterministic parsing. RNGLR performs best on left-recursive grammars. On JSON (lr) at 15k–30k tokens, RNGLR takes 17.4 ms; on JSON (rr) the same parser takes 63.6 ms (a 3.7× slowdown), and on the LL(1)-refactored JSON (LL-1) it takes 115 ms (a 6.6× slowdown). The LL(1) refactoring— which replaces left-recursion with right-recursion to satisfy LL(1) constraints—actually produces the worst-case grammar for RNGLR. GLL’s performance moves in the opposite direction. It handles right-recursive and LL-refactored grammars well (JSON (rr): 32.8 ms; JSON LL-1: 46.9 ms at 15k–30k tokens), but collapses on left-recursive input: JSON (lr) at 15k–30k tokens takes 346 ms for GLL, a 10.5× regression versus the right-recursive form. Earley is comparatively grammar-structure-insensitive. Across all four JSON variants at 15k–30k tokens, Earley ranges from 342 ms (rr) to 393 ms (lr)— a variation of only 15%— while GLL varies by a factor of 10 and RNGLR by a factor of seven over the same grammar family. Adding ambiguity to the recursive rules (ambig) has negligible runtime impact when the underlying recursion structure is already fixed. JSON (ambig) differs from JSON (rr) by less than 1% for all four generalized parsers.
101
102
103
104
103 TinyC LR-1
104
JSON (lr) 104
Time (ms)
102
100
10−2 101
102
103 102 Time (ms)
which all four structural variants (left-recursive, right-recursive, LL(1)-refactored, and ambiguous) have been prepared; the remaining grammars exist only in their natural form, so a comparable cross-variant analysis is not possible for them. The variants are: a right-recursive form (rr), a left-recursive form (lr), an LL(1)-refactored form (LL-1) that eliminates both recursion styles in favor of iteration, and an ambiguous form (ambig) that retains the recursive structure with underspecified associativity. Unlocking the deterministic tier. The primary payoff of grammarhacking is that it enables LL(1) or LR(1) parsing. As shown in Table 4 and Figure 4, the LL(1)-refactored JSON grammar runs at 7.79 ms (LL(1)) and 7.67 ms (LR(1)) at 15k–30k tokens. The original right-recursive JSON grammar cannot be parsed by LL(1) at all, and yields 342 ms for Earley and 32.8 ms for GLL—the best available generalized parser for that variant. Grammar-hacking to LL(1) thus represents a 4× speedup over the fastest generalized option for that grammar form. The same pattern holds for Expr: LL(1)-refactored Expr runs at 6.03 ms with LL(1), versus 43.1 ms for GLL on the same grammar—a 7× gap.
101
Grammar structure has a large, parser-specific effect on generalized parsers. RNGLR benefits from left-recursion and degrades on rightrecursion; GLL benefits from right and collapses on left-recursion. Earley is largely insensitive to recursion style. Refactoring a grammar to LL(1) to help GLL penalizes RNGLR.
100 10−1 10−2
103
104 Tokens
Figure 3: Runtime (ms) versus token count for grammars with a known LR(1) baseline.
Memory across grammar variants. Memory consumption is also affected by grammar structure, most visibly for GLL. On JSON (lr) at 15k–30k tokens, GLL stays at the 0.016 MB floor despite taking 346 ms to parse. On JSON (rr) at the same size, GLL grows to 0.828 MB; on Expr (LL-1) it reaches 2.42 MB. RNGLR and BRNGLR
An Empirical Comparison of General Context-Free Parsers
Expr
JSON LL(1) + LL(1) LR(1) + LR(1) Ambi + BRNGLR
102 Time (ms)
Time (ms)
102
100
10−2
100
10 −2 101
102 103 Input size (tokens)
104
101
102 103 Input size (tokens)
104
Figure 4: Runtime (ms) versus input size (tokens) for three grammar/parser pairings on JSON (left) and Expr (right). Expr
JSON LL(1) LR(1) BRNGLR
102 Time (ms)
Time (ms)
102
100
LL(1) LR(1) BRNGLR
100
10 −2
10−2 101
102
103 Input size (tokens)
104
101
102 103 Input size (tokens)
104
Figure 5: Runtime (ms) versus input size (tokens) for three parsers—LL(1), LR(1), and BRNGLR, same grammar. remain at 0.016 MB across all JSON and Expr variants at every input-size bucket. GLL’s memory and runtime costs are inversely coupled across grammar variants: the grammar forms where it runs fastest are those where it consumes the most memory.
5
Discussion
GLR is the practical default for generalized parsing. Across every grammar and input size tested, RNGLR and BRNGLR are the fastest generalized parsers by a consistent margin, and simultaneously the most memory-efficient, matching deterministic parsers at the measurement floor on most grammars. The BRNGLR variant was motivated by a theoretical concern: the standard RNGLR SPPF can grow to 𝑂 (𝑛 3 ) nodes in the worst case, whereas BRNGLR bounds this to 𝑂 (𝑛 2 ) via binarization. In our results, RNGLR and BRNGLR typically differ by less than 15% in runtime and are indistinguishable in memory, suggesting that the pathological 𝑂 (𝑛 3 )node SPPF is rare in typical software engineering grammars. For practitioners, the two algorithms are interchangeable; RNGLR is simpler to implement and should be preferred. GLL’s memory and runtime costs are inversely coupled across grammar variants. GLL’s performance profile is unstable across grammars. On right-recursive and LL(1)-refactored grammars, GLL is fast— JSON (rr) at 15k–30k tokens takes 32.8 ms—but it consumes significant memory, reaching 0.828 MB on JSON (rr) and 2.42 MB
on Expr (LL-1). On JSON (lr), the pattern reverses: JSON (lr) at 15k– 30k tokens takes 346 ms, yet GLL remains at the 0.016 MB floor. A deployment that selects GLL must carefully verify that GLL is indeed the fastest algorithm on such grammars. The cost of generality is modest for GLR. A 3× median runtime overhead relative to LR(1), with an IQR of only 0.2×, means GLR’s cost is both low and predictable: for GLR, that cost is bounded and narrow across diverse real-world grammars. GLL’s overhead is less favorable—a median of 6× with an IQR nearly twenty times wider than GLR’s, and a worst-case of 139× on left-recursive JSON— and Earley’s median of 10× makes it the most expensive online option. However, even for these parsers, the overhead is a constant factor on any given grammar; the behavior is not inherently unbounded. The practical implication is that GLR closes the performance gap with deterministic parsers to a level that is acceptable for a wide range of software engineering applications. Grammar structure and parser choice interact. No single grammar form is universally optimal once the algorithm family is fixed. RNGLR is fastest on left-recursive grammars and degrades on rightrecursive ones; GLL is faster than RNGLR on the JSON LL(1)-refactored grammar, but collapses on left-recursive ones. This interaction has a concrete consequence: grammar-hacking a grammar to LL(1)— the refactoring that introduces right-recursion and iteration to satisfy LL(1) constraints—improves GLL by enabling faster parsing
Huan Vo, Danushka Liyanage, Hong Jin Kang, Sasha Rubin, and Rahul Gopinath
but simultaneously produces the worst-case grammar for RNGLR. A practitioner who refactors a grammar expecting to improve performance across the board may inadvertently degrade the parser they are actually using. The recommendation is to choose a grammar refactoring in light of the target algorithm: LR(1)-style refactoring (preserving or introducing left-recursion) suits the GLR family, while LL(1)-style refactoring suits GLL. Grammar hacking is most valuable as a gateway to the deterministic tier. The primary benefit of grammar hacking is not marginal improvement within the generalized tier but the ability to unlock LL(1) or LR(1) parsing entirely. This 4–7× speedup is consistent, but comes with maintenance costs: refactored grammars are harder to read, and can be brittle under language evolution. Grammar hacking should therefore be undertaken deliberately, only when parsing is a demonstrated bottleneck. For most software engineering tools, the 3× GLR overhead is acceptable. Practical guidance for SE tool builders. Our recommendation: For tools that require the maximum parsing throughput and whose grammar can be kept strictly deterministic, LL(1) or LR(1) remain the best choices. For tools that prioritize grammar flexibility—accepting arbitrary context-free grammars without modification—RNGLR is the recommended default: it offers the best combination of runtime and memory efficiency, and its overhead relative to LR(1) is small and predictable. GLL is a reasonable alternative when a topdown parsing style is architecturally desirable, but practitioners must choose grammar forms carefully and be aware of memory growth. Earley is the most conservative choice for correctness on exotic or highly ambiguous grammars, but it is consistently the slowest online generalized parser and its use should be justified. CYK and Valiant are not competitive for any practical input size in our benchmark and should not be considered for production use.
6
Threats to Validity
Internal Validity. All parsers are implemented in Rust from scratch; implementation bugs may exist. Shared data structures and grammar representations reduce the surface area for implementationspecific bias. Memory measurements rely on polling at 1 ms intervals, which may miss short-lived peak allocations. Timing is reported as the median over multiple iterations to reduce the impact of transient system noise, but background load on the experimental machine (Apple M1) cannot be fully eliminated. External Validity. All benchmark inputs are generated by a grammarbased fuzzer. Synthetic inputs produced by bounded-depth derivation may not reflect the patterns that appear in developer-written code. Our experiments ran exclusively on an Apple M1; processors differ in branch predictor, cache hierarchy, and instruction throughput in ways that may affect relative rankings. Our grammar corpus does not include real developer-written source files or intentionally ambiguous grammars, which are precisely the setting where generalized parsers have the most to offer. Construct Validity. Structural metrics (LL(1)/LR(1) class, production count, nonterminal count) are used as proxies for grammar complexity, but may not capture all aspects of runtime difficulty.
7
Related Work
General parsing as a strategy. Van den Brand et al. [38] identified friction in software renovation caused by deterministic grammar constraints, arguing that resolving LR conflicts manually imposes significant engineering cost. They proposed GLR as a practical alternative. Klint et al. [19] formalised this concern in the notion of grammarware engineering, observing that grammar transformations required for deterministic parsing obscure the intended language structure and increase long-term maintenance burden. A practical benefit of generalized parsers is scannerless parsing [26], treating each character as a token without a separate lexer phase. Van den Brand et al. [37] demonstrated that Scannerless GLR (SGLR) is viable in industrial language processing tools, and Economopoulos et al. [10] showed that RNGLR can improve scannerless performance. Our benchmark also operates in a scannerless mode, allowing direct comparison without a lexer. Existing empirical comparisons. The earliest cross-family comparison appears in Tomita’s original GLR work [33], which argued that GLR substantially outperforms Earley on natural-language grammars. The original GLL paper [28] noted that GLL parsers perform well relative to RNGLR and BRNGLR, but provides no systematic evaluation. Johnstone et al. [16] provided the most detailed pre-GLL empirical study of general parsers, comparing three GLR variants (Farshi, RNGLR, BRNGLR) across ANSI C, Pascal, and COBOL grammars. However, it predates GLL, omits Earley, and evaluates each algorithm on a single input per grammar rather than a distribution of sizes. Economopoulos’s dissertation [11] provides a thorough theoretical treatment of RNGLR and BRNGLR, with implementation details our work draws on, but its empirical evaluation is similarly limited in grammar and input coverage. McPeak and Necula’s Elkhound [24] is a hybrid GLR parser evaluated on construction speed rather than algorithmic throughput. Afroozeh and Izmaylova [1] benchmarked an optimized GLL against the original GLL implementation on Java, C#, and OCaml grammars. However, these results characterize within-family improvement only. None of the above studies compares algorithms from all three major families—matrix-based, top-down online (Earley, GLL), and bottom-up online (GLR)—in a unified implementation across a grammar corpus of comparable breadth and with statistical evaluation over inputs of varying length. Parsing algorithm improvements. Scott and Johnstone [29] introduced FGLL and RGLL, structural refinements to GLL that reduce descriptor overhead. Afroozeh and Izmaylova also proposed Iguana [2], a GLL-focused framework for practical scannerless parsing. More recently, Scott and Johnstone [30] adapted the Earley algorithm to use a precomputed parse table in the style of GLR, reporting performance approaching BRNGLR on their test grammars. Our framework does not yet include this table-driven Earley variant; it is a natural direction for future work. Other parsing approaches. Parr et al. [25] introduced ALL(*), which handles a broad class of grammars using adaptive lookahead. ALL(*) does not handle indirect left recursion and cannot enumerate all parse trees for ambiguous inputs, placing it outside the general CFG class studied here. Parsing Expression Grammars [12] use ordered choice to enforce deterministic parsing by construction, at the cost of potentially rejecting strings that belong to the intended
An Empirical Comparison of General Context-Free Parsers
language. Parglare [6] is a practical LR/GLR library for Python that includes informal runtime comparisons between its LR and GLR modes, though not as a controlled cross-algorithm benchmark.
8
Data Availability
Available at: https://doi.org/10.5281/zenodo.19231343
9
Conclusion
We presented the first unified, controlled benchmark of six generalized parsing algorithms—CYK, Valiant, Earley, GLL, RNGLR, and BRNGLR—alongside LL(1) and LR(1) baselines, implemented in a single Rust framework with shared data structures. Through an evaluation of 22 grammars, from simple expressions to complex languages such as C++ and Java, we provide actionable guidance for software practitioners. Our results show that the performance penalty for choosing GLR is modest: a median 3× overhead over LR(1). This is an acceptable margin for the broad class of tools— compilers, static analyzers, and language servers—that currently rely on hand-written or grammar-hacked deterministic parsers. Our work provides the empirical foundation for principled adoption of generalized parsing as a safe and efficient default.
References [1] Ali Afroozeh and Anastasia Izmaylova. 2015. Faster, Practical GLL Parsing. In Proc. Int. Conf. Compiler Construction (CC). Springer, 89–108. https://doi.org/10. 1007/978-3-662-46663-6_5 [2] Ali Afroozeh and Anastasia Izmaylova. 2015. One Parser to Rule Them All. In Proc. ACM Symp. New Ideas, New Paradigms, Refl. Program. Softw. (Onward!). 151–170. https://doi.org/10.1145/2814228.2814242 [3] V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradjev. 1970. On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady 11, 5 (1970), 1209–1210. [4] J. Aycock. 2002. Practical Earley Parsing. Comput. J. 45, 6 (June 2002), 620–630. https://doi.org/10.1093/comjnl/45.6.620 [5] Max Brunsfeld et al. 2024. Tree-sitter. Zenodo. https://doi.org/10.5281/zenodo. 4619183 Version 0.25.3. [6] Igor Dejanović. 2022. Parglare: A LR/GLR parser for Python. Science of Computer Programming 214 (2022), 102734. https://doi.org/10.1016/j.scico.2021.102734 [7] Jay Earley. 1970. An Efficient Context-Free Parsing Algorithm. Commun. ACM 13, 2 (Feb. 1970), 94–102. https://doi.org/10.1145/362007.362035 [8] Phil Eaton. 2021. Enumerating and analyzing 40+ non-V8 JavaScript implementations. https://notes.eatonphil.com/javascript-implementations.html [9] Phil Eaton. 2021. Parser generators vs. handwritten parsers: surveying major language implementations in 2021. https://notes.eatonphil.com/parser-generatorsvs-handwritten-parsers-survey-2021.html [10] Giorgios Economopoulos, Paul Klint, and Jurgen Vinju. 2009. Faster Scannerless GLR Parsing. In Compiler Construction, Oege de Moor and Michael I. Schwartzbach (Eds.). Springer, Berlin, Heidelberg, 126–141. https://doi.org/10. 1007/978-3-642-00722-4_10 [11] Giorgios Robert Economopoulos. 2006. Generalised LR Parsing Algorithms. Ph. D. Dissertation. Royal Holloway, University of London. [12] Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-based Syntactic Foundation. SIGPLAN Not. 39, 1 (Jan. 2004), 111–122. https://doi.org/10.1145/ 982962.964011 [13] GitHub. 2026. Search Results for “json parser” Repositories. https://github. com/search?q=json+parser&type=repositories. Accessed: March 2026. Returns 29,800+ repositories. [14] Dick Grune and Ceriel J. H. Jacobs. 2008. Introduction to Parsing. In Parsing Techniques: A Practical Guide. Springer New York, New York, NY, 61–102. https: //doi.org/10.1007/978-0-387-68954-8_3 [15] Adrian Johnstone. 2023. A Reference GLL Implementation. In Proc. ACM SIGPLAN Int. Conf. Softw. Lang. Eng. (SLE). 43–55. https://doi.org/10.1145/3623476. 3623521 [16] Adrian Johnstone, Elizabeth Scott, and Giorgios Economopoulos. 2006. Evaluating GLR Parsing Algorithms. Sci. Comput. Program. 61, 3 (Aug. 2006), 228–244. https://doi.org/10.1016/j.scico.2006.04.004 [17] Jeffrey Kegler. 2023. Parsing: a Timeline. https://jeffreykegler.github.io/ personal/timeline_v3 Revision 9, 6 July 2023. Accessed: 2026-03-27.
[18] Lukas Kirschner, Ezekiel Soremekun, Rahul Gopinath, and Andreas Zeller. 2022. Input repair via synthesis and lightweight error feedback. arXiv preprint arXiv:2208.08235 (2022). [19] Paul Klint, Ralf Lämmel, and Chris Verhoef. 2005. Toward an engineering discipline for grammarware. ACM Transactions on Software Engineering and Methodology (TOSEM) 14, 3 (2005), 331–380. [20] Donald E. Knuth. 1965. On the Translation of Languages from Left to Right. Inform. Control 8, 6 (Dec. 1965), 607–639. https://doi.org/10.1016/S0019-9958(65) 90426-2 [21] Ralf Lämmel. 2001. Grammar testing. In International Conference on Fundamental Approaches to Software Engineering. Springer, 201–216. [22] LangSec Workshop. 2026. Language-theoretic Security (LangSec). https:// langsec.org/. Accessed: March 2026. [23] Joop M. I. M. Leo. 1991. A General Context-Free Parsing Algorithm Running in Linear Time on Every LR(𝑘 ) Grammar without Using Lookahead. Theoret. Comput. Sci. 82, 1 (May 1991), 165–176. https://doi.org/10.1016/0304-3975(91) 90180-A [24] Scott McPeak and George C. Necula. 2004. Elkhound: A Fast, Practical GLR Parser Generator. In Proc. Int. Conf. Compiler Construction (CC). Springer, 73–88. https://doi.org/10.1007/978-3-540-24723-4_6 [25] Terence Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) Parsing: The Power of Dynamic Analysis. SIGPLAN Not. 49, 10 (Oct. 2014), 579–598. https://doi.org/10.1145/2714064.2660202 [26] D. J. Salomon and G. V. Cormack. 1989. Scannerless NSLR(1) parsing of programming languages. SIGPLAN Not. 24, 7 (June 1989), 170–178. https://doi.org/ 10.1145/74818.74833 [27] Elizabeth Scott and Adrian Johnstone. 2006. Right Nulled GLR Parsers. ACM Trans. Program. Lang. Syst. 28, 4 (July 2006), 577–618. https://doi.org/10.1145/ 1146809.1146810 [28] Elizabeth Scott and Adrian Johnstone. 2010. GLL Parsing. Electron. Notes Theor. Comput. Sci. 253, 7 (Sept. 2010), 177–189. https://doi.org/10.1016/j.entcs.2010. 08.041 [29] Elizabeth Scott and Adrian Johnstone. 2016. Structuring the GLL parsing algorithm for performance. Science of Computer Programming 125 (Sept. 2016), 1–22. https://doi.org/10.1016/j.scico.2016.04.003 [30] Elizabeth Scott and Adrian Johnstone. 2026. Earley Table Traversing Parsers. Sci. Comput. Program. 247 (Jan. 2026), 103335. https://doi.org/10.1016/j.scico. 2025.103335 [31] Elizabeth Scott, Adrian Johnstone, and Rob Economopoulos. 2007. BRNGLR: A Cubic Tomita-style GLR Parsing Algorithm. Acta Inform. 44, 6 (Oct. 2007), 427–461. https://doi.org/10.1007/s00236-007-0054-z [32] Volker Strassen. 1969. Gaussian Elimination is not Optimal. Numer. Math. 13, 4 (Aug. 1969), 354–356. https://doi.org/10.1007/BF02165411 [33] Masaru Tomita. 1986. Efficient Parsing for Natural Language. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-1885-0 [34] Laurence Tratt. 2011. Parsing: The Solved Problem That Isn’t. https://tratt.net/ laurie/blog/2011/parsing_the_solved_problem_that_isnt.html [35] Leslie G. Valiant. 1975. General Context-Free Recognition in Less than Cubic Time. J. Comput. System Sci. 10, 2 (April 1975), 308–315. https://doi.org/10.1016/ S0022-0000(75)80046-8 [36] Mark van den Brand. [n. d.]. Current Parsing Techniques in Software Renovation Considered Harmful. https://www.cs.vu.nl/~x/ref/ref.html. Accessed: 2026-03-18. [37] Mark G. J. Van Den Brand, Jeroen Scheerder, Jurgen J. Vinju, and Eelco Visser. 2002. Disambiguation Filters for Scannerless Generalized LR Parsers. Lecture Notes in Computer Science, Vol. 2304. Springer Berlin Heidelberg, Berlin, Heidelberg, 143–158. https://doi.org/10.1007/3-540-45937-5_12 [38] Mark G. J. van den Brand, A. Sellink, and C. Verhoef. 1998. Current Parsing Techniques in Software Renovation Considered Harmful. In Proc. Int. Workshop Program Comprehension (IWPC). 108. [39] Thom Wiggers and Renovate Bot. 2019. thomwiggers/m4ri-rust v0.3.2. https: //doi.org/10.5281/zenodo.3377514 [40] Daniel H. Younger. 1967. Recognition and Parsing of Context-Free Languages in Time 𝑛 3 . Inform. Control 10, 2 (Feb. 1967), 189–208. https://doi.org/10.1016/ S0019-9958(67)80007-X [41] Andreas Zeller, Rahul Gopinath, Marcel Böhme, Gordon Fraser, and Christian Holler. 2024. Fuzzing with Grammars. In The Fuzzing Book. CISPA Helmholtz Center for Information Security. https://www.fuzzingbook.org/ html/Grammars.html Retrieved 2024-06-30 18:31:28+02:00.