Verified invertible lexer using regular expressions and DFAs

Samuel Chassot, Viktor KuncakarXiv 2024 · DOI · arXiv

TL;DR

This paper presents a formally verified framework for building invertible lexers in Scala, ensuring that tokenizing code and then reconstructing it from tokens yields the original input. They introduce novel conditions for invertibility and provide implementations using both regular expressions and Deterministic Finite Automata (DFAs), verified with the Stainless framework.

What Problem Does This Paper Address?

Lexing, the process of breaking down a stream of characters into meaningful tokens, is a fundamental step in many software systems, like compilers. Ideally, if you tokenize some input and then reconstruct the original character stream from those tokens, you should get back exactly what you started with – this is the property of invertibility. However, achieving this invertibility, especially with formal guarantees, is challenging. Existing lexer generators often lack formal verification, and the conditions under which a lexer's output is truly invertible are not well-understood or easily guaranteed. This paper tackles the problem of building lexers that are not only correct according to established principles like maximal munch but also provably invertible.

Methods

The authors developed a verified lexer framework in Scala, leveraging the Stainless formal verification tool. Their approach involves:

  • Verified Regex and DFA Matchers: They implemented and formally verified matchers for regular expressions and DFAs. The regex matcher uses Brzozowski derivatives, with optimizations like memoization and zippers explored for performance. The DFA matcher takes DFAs directly as input.
  • Maximal Munch Principle: The lexer implementation adheres to the maximal munch principle, ensuring that the longest possible prefix of the input is matched by a rule, and in case of ties, the rule with higher priority is chosen. This guarantees a unique tokenization.
  • Invertibility Conditions: The core contribution lies in defining and proving conditions for lexer invertibility. They explore two main scenarios:
  • Characters to Tokens to Characters: This is the simpler case, where print(lex(s)) = s.
  • Tokens to Characters to Tokens: This is more complex, requiring specific conditions on the token sequence to ensure lex(print(ts)) = ts. They propose conditions based on token separability and disjoint character sets for separator and non-separator tokens.
  • Formal Verification: All implementations and specifications are verified using Stainless, providing strong guarantees about correctness and invertibility.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Invertibility is Not Trivial: The paper highlights that lexer invertibility is not a given and requires specific conditions to hold, especially when reconstructing tokens back into characters.
  • Separability is Key: For the token-to-character-to-token invertibility, the concept of "separability" between tokens is crucial. This ensures that a prefix of a second token's characters, when appended to a first token's characters, doesn't accidentally form a valid token for the first token's rule.
  • Disjoint Character Sets for Separators: A practical and sufficient condition for invertibility involves ensuring that separator tokens and non-separator tokens use disjoint sets of characters. This simplifies the proof and makes the condition more manageable.
  • Regex vs. DFA Trade-offs: The paper offers two lexer implementations (regex and DFA based), allowing users to choose based on performance needs and ease of use, while maintaining the same formal guarantees.

Key Results

  • A Scala implementation of a verified lexer framework.
  • Formally verified regex and DFA matchers.
  • Formal proofs for the maximal munch principle in the lexer.
  • Two novel, formally verified conditions for lexer invertibility, with proofs demonstrating their sufficiency.
  • The framework allows for the addition of new matchers (e.g., NFA-based) by proving their equivalence to existing ones.

Limitations and Future Work

  • Token Augmentation: The current lexer only outputs simple tokens with characters and a tag. Future work could involve augmenting tokens with more complex data types for practical use in applications like compilers.
  • POSIX Disambiguation: Exploring the POSIX disambiguation method for lexing could lead to performance improvements and is suggested as an area for future research and formal verification.
  • Performance Optimizations: Further performance enhancements for the regex matcher, such as dynamic programming or more advanced caching, are suggested.
  • New Matcher Integration: The framework is designed to easily incorporate new matchers by proving their equivalence to existing ones, which could be a future direction.

Summary updated

BibTeX
@misc{chassot2024verified,
  author = {Samuel Chassot and Viktor Kuncak},
  title = {{Verified invertible lexer using regular expressions and DFAs}},
  year = {2024},
  eprint = {2412.13581},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.13581},
}

Loading related content...

Figure