ZipLex: Verified Invertible Lexing with Memoized Derivatives and Zippers

Samuel Chassot, Viktor KuncakarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces ZipLex, a formally verified framework for linear-time lexical analysis that guarantees invertibility – meaning lexing and printing tokens are mutual inverses. This is crucial for applications like IDE refactoring and program synthesis where information must be preserved when transforming code. ZipLex achieves this through a novel combination of verified data structures, memoized derivatives, and zipper-based regular expression matching.

What Problem Does This Paper Address?

Lexical analysis (lexing) is the first step in many programming language tools, converting raw text into a sequence of tokens. While correctness is paramount, existing verified lexers often focus on just the "longest match" rule, which can lead to information loss when tokens are printed back to text. This "invertibility" is essential for tools that manipulate code, like refactoring engines or program synthesizers. Previous work has not adequately addressed verified, efficient, and invertible lexing, especially when dealing with the complexities of maximal munch semantics and the need for practical performance.

Methods

ZipLex tackles this challenge with several key innovations:

  • Verified Invertible Lexing: The core contribution is a framework that guarantees lex(print(tokens)) == tokens and print(lex(string)) == string. This is achieved by defining a "separability" condition for token sequences and ensuring it's maintained.
  • Memoized Brzozowski Derivatives: ZipLex uses Brzozowski's derivatives for regular expression matching, but crucially, it employs memoization to ensure linear-time performance. This avoids the quadratic complexity that naive approaches can suffer from.
  • Zipper-Based Regular Expression Matching: To optimize derivative computations and enable efficient memoization, ZipLex represents regular expressions using Huet's zippers. This provides a more manageable structure for derivative computation and significantly reduces cache misses.
  • Verified Data Structures: The framework relies on a suite of verified data structures, including a mutable hash table for memoization and a balanced tree structure for efficient sequence manipulation.
  • R-Path Predicates: To formally reason about token sequence separability and invertibility, the paper introduces "R-Path predicates," which are conditions on consecutive elements in a sequence.

Datasets

Not discussed in the paper. The paper focuses on a formal framework and its evaluation on synthetic grammars and a JSON example.

Key Insights and Ideas

  • Invertibility is Key: The paper strongly emphasizes that for many practical applications, invertibility (lexing and printing being inverses) is as important as correctness of the lexing process itself.
  • Memoization is Crucial for Performance: Without memoization, even optimized derivative-based lexers can struggle with adversarial grammars. ZipLex's verified memoization is a significant factor in achieving linear time complexity.
  • Zippers for Efficient Derivatives: Representing regular expressions with zippers provides a more structured and memoization-friendly way to compute derivatives compared to traditional tree-based approaches.
  • Separability as a Formal Tool: The concept of "separability" (captured by R-Path predicates) is a novel and effective way to formally reason about and enforce invertibility in lexing.
  • Verified Mutable Data Structures Pay Off: The use of a verified mutable hash table for memoization, while requiring careful verification, significantly boosts performance and simplifies the implementation of memoization caches.

Key Results

  • Linear-Time Lexing: ZipLex achieves linear-time complexity for lexical analysis, even on grammars that cause quadratic behavior in tools like flex and ocamllex.
  • Verified Invertibility: The framework provides formal guarantees that lexing and printing are mutual inverses.
  • Performance: ZipLex is competitive with other verified lexers, being up to two orders of magnitude faster than Verbatim++ and comparable to Coqlex on JSON parsing, while offering linear time complexity.
  • Practical Applications: The framework has been demonstrated to support realistic applications like JSON processing and lexers for programming languages.

Limitations and Future Work

  • Performance Gap with Coqlex: While ZipLex is linear-time, it is still about 3.5x slower than Coqlex on JSON inputs. The authors suspect this is due to Coqlex's specialization for ASCII characters and character intervals, whereas ZipLex uses generic characters.
  • Memoization Overhead: For certain grammars like JSON, memoization can introduce a slight overhead, though it's crucial for adversarial cases.
  • Future Work: The authors suggest exploring more expressive regular expression features and further optimizing the data structures and memoization strategies. They also highlight the potential for applying this framework to other areas of language processing.

Summary updated

BibTeX
@misc{chassot2025ziplex,
  author = {Samuel Chassot and Viktor Kuncak},
  title = {{ZipLex: Verified Invertible Lexing with Memoized Derivatives and Zippers}},
  year = {2025},
  eprint = {2510.18479},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.18479},
}

Loading related content...

Figure