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
Note
Claude was used to write initial theories, refactor proofs/ML code under the authors' direction.
Topics
- Computer science/Automata and formal languages
- Computer science/Programming languages/Compiling
- Tools
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
- LR
- LR_Driver
- LR_Fast
- LR_Sparse
- LR_Vec
- LR_Det
- LR_Simple
- LR_Int
- LR_Trie
- LR_Tok
- LR_Prod
- LR_Loop
- LR_Plain
- LR_Diag
- LR_Recover
- LR_Restrict
- LR_Prec
- Grammar_Command
- LR_Parser
- LR_Prec_Parse
Session TIGER_Grammar_Tests
- Parser_Check
- Regression_Tests
- Diag_Tests
- Reach_Tests
- Prec_Tests
- Prec_Surface_Tests
- Compose_Tests
- Param_Tests
- Span_Tests
- Ast_Tests
- Same_Terms
Session TIGER_Grammar_Tests_Slow
Session TIGER_Lexer
- TIGER_Lexed
- TIGER_Regex
- TIGER_Pred_Algebra
- TIGER_Intervals
- TIGER_Spec
- TIGER_Gen
- TIGER_Lexer
- TIGER_Driver
- TIGER_Tables
- TIGER_Codepoints
- TIGER_Pattern
- TIGER_Rules
- Lexer_Command
- Lexer_Check
Session TIGER_Lexer_Tests
- Intervals_Tests
- Tables_Tests
- Driver_Tests
- Codepoint_Tests
- Pattern_Tests
- Lexer_Command_Tests
- Lexer_Table_Tests