Lune

PLDI2020Top-tier venue

Zippy LL(1) parsing with derivatives

Romain Edelmann, Jad Hamza, Viktor Kuncak

Abstract

In this paper, we present an efficient, functional, and formally verified parsing algorithm for LL(1) context-free expressions based on the concept of derivatives of formal languages. Parsing with derivatives is an elegant parsing technique, which, in the general case, suffers from cubic worst-case time complexity and slow performance in practice. We specialise the parsing with derivatives algorithm to LL(1) context-free expressions, where alternatives can be chosen given a single token of lookahead. We formalise the notion of LL(1) expressions and show how to efficiently check the LL(1) property. Next, we present a novel linear-time parsing with derivatives algorithm for LL(1) expressions operating on a zipperinspired data structure. We prove the algorithm correct in Coq and present an implementation as a part of Scallion, a parser combinators framework in Scala with enumeration and pretty printing capabilities.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Intrinsic Verification of Parsers and Formal Grammar Theory in Dependent Lambek Calculus cites CoStar: a verified ALL() parser
  • A derivative-based parser generator for visibly Pushdown grammars cites CoStar: a verified ALL() parser
  • A derivative-based parser generator for visibly Pushdown grammars cites EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. CoStar: a verified ALL(*) parserSam Lasser, Chris Casinghino, Kathleen Fisher, Cody RouxPLDI 2021 · 10 citations
  2. A derivative-based parser generator for visibly Pushdown grammarsXiaodong Jia, Ashish Kumar, Gang TanOOPSLA 2021 · 7 citations
  3. Linear Layouts: Robust Code Generation of Efficient Tensor Computation Using F_2Keren Zhou, Mario Lezcano Casado, Adam P. Goucher, Akhmed Rakhmati et al.ASPLOS 2026 · 3 citations
  4. ChopChop: A Programmable Framework for Semantically Constraining the Output of Language ModelsShaan Nagy, Timothy Zhou, Nadia Polikarpova, Loris D'AntoniPOPL 2026 · 1 citation
  5. Intrinsic Verification of Parsers and Formal Grammar Theory in Dependent Lambek CalculusSteven Schaefer, Nathan Varner, Pedro Henrique Azevedo de Amorim, Max S. NewPLDI 2025

Builds on1

  1. EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message FormatsTahina Ramananandro, Antoine Delignat-Lavaud, Cédric Fournet, Nikhil Swamy et al.USENIX Security 2019 · 70 citations

Related papers

  1. Faster general parsing through context-free memoizationGrzegorz HermanPLDI 2020 · 4 citations
  2. Formally Verified Linear-Time Invertible LexingSamuel Chassot, Viktor KuncakCAV 2026
  3. flap: A Deterministic Parser with Fused LexingJeremy Yallop, Ningning Xie, Neel KrishnaswamiPLDI 2023 · 10 citations
  4. Parsing randomnessHarrison Goldstein, Benjamin C. PierceOOPSLA 2022 · 11 citations
  5. Scalable Verification of Zero-Knowledge ProtocolsMiguel Isabel, Clara Rodríguez-Núñez, Albert RubioS&P 2024 · 14 citations
Dusk over the sea between two cliffs drawn in fine vertical lines