From: Jasmin Blanchette <jasmin.blanchette@ifi.lmu.de>
Subject: [isabelle] New in the AFP: Tokenization, Indentation-sensitive Grammars & Executable Recognizers
Dear all,
It is my pleasure to announce the following new AFP entry by Basil Fürer and Dmitriy Traytel:
Tokenization, Indentation-sensitive Grammars & Executable Recognizers
https://isa-afp.org/entries/TIGER_Lexer_Parser.html
Two definitional packages for Isabelle/HOL that turn the source text of a language into verified values: The command 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 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 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.
Enjoy!
Jasmin
Last updated: Nov 19 2026 at 01:46 UTC