An Empirical Comparison of General Context-Free Parsers

• URL: http://arxiv.org/abs/2606.08465v1
• Date: Sun, 07 Jun 2026 05:58:58 GMT
• Title: An Empirical Comparison of General Context-Free Parsers
• Abstract summary: Parsing underpins a vast range of software engineering tasks, from compilers and static analyzers to language servers and fuzz testing tools.<n>Most algorithms deployed in practice are deterministic (LL or LR), forcing developers to contort their grammars to fit the languages they design sacrificing for the sake of parseability.<n>We present the first unified, controlled benchmark of six generalized parsing algorithms implemented in Rust with shared data structures and parse-tree extraction.<n>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 with a narrow and predictable
• Score: 9.393047946491487
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• NL2Scratch: An Executable Benchmark and Evaluation for Block-Based Programming [62.89531126732269]
  We introduce NL2Scratch, an executable benchmark for natural-language-to-Scratch generation.<n>We construct a semantically validated pool of 23,594 examples, and a slot-balanced 800 diagnostic benchmark.<n>Experiments across instruction-tuned and fine-tuned LLMs reveal a notable gap between lexical similarity and semantic alignment.
  arXiv  Detail & Related papers  (2026-06-20T14:22:59Z)
• Prefix Parsing is Just Parsing [53.010152712125766]
  Prefix parsing asks whether an input prefix can be extended to a complete string generated by a given grammar.<n>We introduce the prefix grammar transformation, an efficient reduction of prefix parsing to ordinary parsing.<n>We also present a strategy-based on algorithmic differentiation-for computing the next-token weight vector.
  arXiv  Detail & Related papers  (2026-04-23T01:20:40Z)
• Superset Decompilation [7.989066784325648]
  decompilation is the reverse of compilation and can be structured as a sequence of modular passes.<n>We formalize this as provenance-guided superset decompilation (PGSD), a framework that monotonically derives facts about the binary into a relation store.<n>Mandel implements PGSD as a declarative reverse engineering framework that lifts Linux ELF binaries to C99 through a granular intermediate representation in 35K lines of Rust and Datalog.
  arXiv  Detail & Related papers  (2026-03-30T03:47:19Z)
• Towards the Systematic Testing of Regular Expression Engines [8.561133495117675]
  ReTest is a framework that systematically tests regular expression engines.<n>It combines grammar-aware fuzzing for high code coverage with metamorphic testing to generate dialect-independent test oracles.<n>Our preliminary evaluation on PCRE shows that ReTest achieves 3x higher edge coverage than existing fuzzing approaches.
  arXiv  Detail & Related papers  (2026-02-27T21:00:31Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  We introduce EquiBench, a new benchmark for evaluating large language models (LLMs)<n>This task directly tests a model's ability to reason about program semantics.<n>We evaluate 19 state-of-the-art LLMs and find that in the most challenging categories, the best accuracies are 63.8% and 76.2%, only modestly above the 50% random baseline.
  arXiv  Detail & Related papers  (2025-02-18T02:54:25Z)
• Leveraging Code to Improve In-context Learning for Semantic Parsing [48.66031267718704]
  In-context learning (ICL) is an appealing approach for semantic parsing due to its few-shot nature and improved generalization. We improve the effectiveness of ICL for semantic parsing by (1) using general-purpose programming languages such as Python instead of DSLs, and (2) augmenting prompts with a structured domain description.
  arXiv  Detail & Related papers  (2023-11-16T02:50:06Z)
• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  This study on a neuro-symbolic architecture called the Compositional Program Generator (CPG) CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules. It perfect achieves generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS.
  arXiv  Detail & Related papers  (2023-09-28T14:33:20Z)
• Happy-GLL: modular, reusable and complete top-down parsers for parameterized nonterminals [0.0]
  This paper presents a strategy for generating modular reusable and complete top-down grammars. The strategy is discussed and demonstrated as a novel back-end for the Happy generator.
  arXiv  Detail & Related papers  (2023-03-14T16:23:23Z)
• Zero-Shot Cross-lingual Semantic Parsing [56.95036511882921]
  We study cross-lingual semantic parsing as a zero-shot problem without parallel data for 7 test languages. We propose a multi-task encoder-decoder model to transfer parsing knowledge to additional languages using only English-Logical form paired data. Our system frames zero-shot parsing as a latent-space alignment problem and finds that pre-trained models can be improved to generate logical forms with minimal cross-lingual transfer penalty.
  arXiv  Detail & Related papers  (2021-04-15T16:08:43Z)
• The LL(finite) strategy for optimal LL(k) parsing [0.0]
  The LL(finite) parsing strategy for parsing of LL(k) grammars where k needs not to be known is presented. The strategy parses input in linear time, uses arbitrary but always minimal lookahead necessary to disambiguate between alternatives of nonterminals.
  arXiv  Detail & Related papers  (2020-10-15T16:52:29Z)
• A Simple Global Neural Discourse Parser [61.728994693410954]
  We propose a simple chart-based neural discourse that does not require any manually-crafted features and is based on learned span representations only. We empirically demonstrate that our model achieves the best performance among globals, and comparable performance to state-of-art greedys.
  arXiv  Detail & Related papers  (2020-09-02T19:28:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.