Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3735

An Empirical Comparison of General Context-Free Parsers

Show all headers | View raw

General parsers aren't much slower than LR(1), so you might as well use
them.  This shouldn't come as a surprise, particularly since parsing is
rarely a significant part of overall compile time, but it's nice to have
numbers.

https://arxiv.org/abs/2606.08465

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 context-free parsers eliminate this
constraint. Yet, 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 3x 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.

Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

Back to comp.compilers | Previous | Next | Find similar | Unroll thread

Thread

An Empirical Comparison of General Context-Free Parsers John R Levine <johnl@taugh.com> - 2026-06-09 10:39 +0200

csiph-web