Tokenization, Indentation-sensitive Grammars & Executable Recognizers

Basil Fürer 📧 and Dmitriy Traytel 📧

November 13, 2026

Abstract

Two definitional packages for Isabelle/HOL that turn the source text of a language into verified values: The command \textbf{lexer} elaborates a flex-style specification, with modes, longest match and rule priority, into an inductive lexing judgment and an executable lexer on precomputed DFA tables. The command \textbf{grammar} elaborates an indentation-sensitive context-free grammar with semantic actions into a grammar specification, decoders from parse trees to the values of the semantic actions and an inductive relation. The related command \textbf{parser} emits an executable LR parser for it. Both executable constants for lexing and parsing are proved sound and complete with respect to their specifications. The parser completeness, and with it the unambiguity of the grammar, follows from an LALR conflict analysis that the command carries out by evaluation.

License

BSD License

Note

Claude was used to write initial theories, refactor proofs/ML code under the authors' direction.

Topics

Related publications

  • Adams, M. D. (2013). Principled parsing for indentation-sensitive languages. Proceedings of the 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 511–522. https://doi.org/10.1145/2429069.2429129
  • Adams, M. D., & Might, M. (2017). Restricting grammars with tree automata. Proceedings of the ACM on Programming Languages, 1(OOPSLA), 1–25. https://doi.org/10.1145/3133906
  • Knuth, D. E. (1965). On the translation of languages from left to right. Information and Control, 8(6), 607–639. https://doi.org/10.1016/s0019-9958(65)90426-2
  • DeRemer, F., & Pennello, T. (1982). Efficient Computation of LALR(1) Look-Ahead Sets. ACM Transactions on Programming Languages and Systems, 4(4), 615–649. https://doi.org/10.1145/69622.357187
  • Brzozowski, J. A. (1964). Derivatives of Regular Expressions. Journal of the ACM, 11(4), 481–494. https://doi.org/10.1145/321239.321249
  • OWENS, S., REPPY, J., & TURON, A. (2009). Regular-expression derivatives re-examined. Journal of Functional Programming, 19(2), 173–190. https://doi.org/10.1017/s0956796808007090

Session TIGER_Token

Session TIGER_Grammar_Model

Session TIGER_Grammar

Session TIGER_Grammar_Tests

Session TIGER_Grammar_Tests_Slow

Session TIGER_Lexer

Session TIGER_Lexer_Tests

Session TIGER_Lexer_Parser