Theory TIGER
theory TIGER
imports TIGER_Grammar.LR_Prec_Parse TIGER_Lexer.Lexer_Check
begin
section ‹Overview›
text ‹
TIGER (Tokenization, Indentation-sensitive Grammars and Executable Recognizers)
provides Isabelle/HOL commands that turn a specification of syntax into
executable recognizers. They work like the lexer and parser generators
▩‹flex› \<^cite>‹"paxson2026-flex-manual"›, ocamlyacc
\<^cite>‹"leroy2026-ocaml-manual"› and Menhir \<^cite>‹"pottier2026-menhir-manual"›.
Unlike Isabelle's mixfix annotations
\<^cite>‹‹Sect.~9.2› in "wenzel2026-isabelle-isar-reference"›
or ▩‹Isabelle_Lex-Yacc› \<^cite>‹"brucker2026-isabelle-lex-yacc"› they also prove that what they generate meets the
specification: a lexing judgment after Verbatim
\<^cite>‹"egolf2021-verbatim-verified-lexer"›, and a grammar with layout constraints
after Adams \<^cite>‹"adams2013"›.
The TIGER entry provides three main commands:
▪ @{command lexer} (Section~\ref{sec:lexer}) defines a lexer specification with
modes and rules, its lexing judgment, and an executable lexer on DFA tables that
computes the judgment.
▪ @{command grammar} (Section~\ref{sec:grammar}) defines a grammar with semantic
actions, decoders from parse trees to values and, on request, an inductive relation
between words and values.
▪ @{command parser} (Section~\ref{sec:parser}) emits an executable LR parser for grammars, proven sound for
the particular grammar. Completeness is proven by evaluation when it has no LALR conflicts.
›
section ‹Lexers\label{sec:lexer}›
text ‹
A lexer specification gives each ∗‹mode› a list of ∗‹rules›, each a regular
expression with an action. Lexing follows flex \<^cite>‹"paxson2026-flex-manual"›: in
the mode on top of a stack of modes, the longest prefix of the input that a rule
matches is the next lexeme, and of the rules that match it the first one wins. Its
action gives the token class of the lexeme (or \<^term>‹None› for trivia such as blanks and
comments), and the new stack. Trivia go with the token before them, so the source is
the concatenation of its tokens and trivia, and each token carries its span: line,
column, offset, length and text.
This meaning is an inductive judgment over the specification, not a program
(Section~\ref{sec:lexer-defined}), and the command proves that the lexer it generates
computes it. The lexer runs on DFA tables, one per mode. Their states are sets of
partial derivatives of the rules' regular expressions, each tagged with its rule: the
subset construction over partial derivatives
\<^cite>‹‹Prop.~4.3› in "antimirov1996-partial-derivatives"› rather than the
derivative automata of \<^cite>‹"brzozowski1964-derivatives-regular-expressions" and
"owens2009-regex-derivatives-reexamined"›. The expressions are kept
symbolic \<^cite>‹"keil2014-symbolic-regex-inequalities"›: their atoms are classes of
characters, intervals of codepoints, not single characters, and a transition goes by a
minterm of the atoms \<^cite>‹‹Sect.~4, Fig.~2› in "dantoni2014-minimization-symbolic-automata"›.
›
subsection ‹Specifications›
text ‹
The categories ‹name›, ‹string›, ‹type›, ‹term› and ‹cartouche› in the
syntax diagrams are those of the Isar reference manual
\<^cite>‹‹Sects.~4.2--4.3› in "wenzel2026-isabelle-isar-reference"›.
\<^rail>‹
@@{command lexer} ('(' (option + ',') ')')? name '::' type ⏎
(clause *) definitions? rules
›
➧ \descform{⬚‹lexer L :: ‹τ› …›} defines the lexer ‹L› with token
classes of type ‹τ›. Each clause is given at most once.
›
text ‹
\<^rail>‹
option: 'sketch' | 'codepoints' | 'char' | 'no_check'
›
➧ \descform{▩‹sketch›} stops after the specification: generates no tables
and no lexer. The other options are ignored.
➧ \descform{▩‹codepoints›} (default) builds a lexer on codepoints,
natural numbers: \<^const>‹cp_lexer› on the tables of ‹L.spec›.
➧ \descform{▩‹char›} builds a lexer on bytes, of type \<^typ>‹char›:
\<^const>‹char_lexer› on the tables of \<^const>‹char_spec› ‹L.spec›, where a class
means its part below ‹0x100›. A class that reaches above ‹0xFF› is then an error,
unless it reaches the last codepoint: ▩‹_› and ‹[^…]› mean the remaining
bytes.
➧ \descform{▩‹no_check›} drops the warning at rules that can never match
(Section~\ref{sec:lexer-defined}).
›
text ‹
\<^rail>‹
clause: @'modes' (cartouche | (name +)) | (@'start' | @'after') term |
(@'exclusive' | @'final') (term +) | @'newline' name
›
➧ \descform{⬚‹modes A B …›} names the modes, which become a datatype
‹L_mode›; ⬚‹modes ‹μ›› takes an existing datatype ‹μ›, whose values the
command enumerates. Without the clause there is one mode, of type \<^typ>‹unit›.
➧ \descform{⬚‹start m›} is the start mode, by default the first.
➧ \descform{⬚‹exclusive m⇩1 … m⇩n›} lists modes in which only the rules
tagged for them are active (flex's ‹%x› \<^cite>‹‹Sect.~10› in "paxson2026-flex-manual"›).
➧ \descform{⬚‹final m⇩1 … m⇩n›} lists the modes in which the input may end,
by default those that are not exclusive: an input that ends in a comment mode is an
unterminated comment.
➧ \descform{⬚‹after h›} is a hook ‹h :: τ option ⇒ μ ⇒ μ› that computes
the new top of the stack from the token class of a lexeme, when its rule names no
mode (by default the identity). It is lex's user flag
\<^cite>‹‹Sect.~10› in "lesk1975-lex"› made pure: a flag set in every action is a
function of the token.
➧ \descform{⬚‹newline c›} names the class of characters that end a line,
by default ‹[\n]›.
›
text ‹
\<^rail>‹
definitions: @'where' (definition + '|')
;
definition: name ('(' (name + ',') ')')? '=' cartouche
›
➧ \descform{⬚‹where c = ‹p› | …›} names patterns (lex's definitions
\<^cite>‹‹Sect.~6› in "lesk1975-lex"›); each becomes a constant ‹L.c›. A
definition with parameters is a template, for example ‹p+› may be redefined
as ‹many(p) = ‹p p*››. Templates are substituted where they are used.
›
text ‹
\<^rail>‹
rules: @'rules' (item + '|')
;
item: tag? (rule | '(' (item + '|') ')')
;
tag: '<' (term + ',') '>'
›
➧ \descform{⬚‹rules r⇩1 | … | r⇩n›} lists the rules. Each mode has its
active rules in the order of the source, so priority is the order of the file.
A rule is active in the modes its tag matches, or, without a tag, in every mode
that is not exclusive. The terms of a tag are HOL patterns over the mode type,
with ▩‹_› for any part. A scope ‹<p> (r⇩1 | … | r⇩n)› tags each rule in it; it is
written with parentheses where flex has braces, as ‹{› opens a proof block in Isar.
›
text ‹
\<^rail>‹
rule: pattern '⇒' action (@'when' term)? (',' mode_op)?
;
pattern: cartouche | string
›
➧ \descform{⬚‹p ⇒ a when P, m›} lexes a match of the pattern ‹p›
with the action ‹a› and then applies the mode operation ‹m›. The pattern is a
cartouche in the syntax of Section~\ref{sec:patterns}, or a string for the literal
text. The guard ⬚‹when P› makes a lexeme ‹u› with ‹¬ P u› an error.
‹⇒› may be written ▩‹=>›.
›
text ‹
\<^rail>‹
action: @'skip' | @'error' | term
›
➧ \descform{⬚‹skip› | ⬚‹error› | ‹t›} is
⬚‹skip› for trivia, ⬚‹error› to stop, or a term: a token class, a
function from the lexeme to a token class, or a complete action of type
\<^typ>‹'ch list ⇒ 'm list ⇒ 'k option × 'm list›.
›
text ‹
\<^rail>‹
mode_op: @'begin' term | @'push' term | @'pop' | cartouche
›
➧ \descform{⬚‹begin m› | ⬚‹push m› | ⬚‹pop› | ‹‹f››} change
the stack as flex does \<^cite>‹‹Sect.~10› in "paxson2026-flex-manual"›:
⬚‹begin m› replaces the top, ⬚‹push m› pushes ‹m›,
⬚‹pop› pops, and a cartouche is a function on the stack. Without a mode
operation the stack stays as it is, up to the hook. A pop of the last mode is the
empty stack, where lexing stops (flex aborts there).
›
subsection ‹Patterns\label{sec:patterns}›
text ‹
A pattern elaborates to a class of codepoints, of type \<^typ>‹nat cls›, or a regular
expression over classes, of type \<^typ>‹nat cls rexp›. Its syntax follows flex \<^cite>‹‹Sect.~6› in "paxson2026-flex-manual"› and
ocamllex \<^cite>‹‹Sect.~17.2.4› in "leroy2026-ocaml-manual"›, with the usual precedence: postfix operators bind tightest, then
concatenation, then the difference ‹#›, then the union ‹|›.
➧ ‹"text"› is the literal text, with the escapes ‹\n›, ‹\t›, ‹\r›, ‹\\›,
‹\"› and ‹\u{h}› for the codepoint with hexadecimal number ‹h›.
➧ ‹[a-zα-ω0-9]› is a class of characters and ranges, a dash at
either end for itself, and a backslash before any character for that character. As
in flex, a blank in a class is a member: ‹[a-z A-Z]› holds the space, an escaped
blank is an error, and a newline is written ‹\n›.
‹[^…]› is its complement, and ▩‹_› is any codepoint.
➧ A character is a codepoint: an ASCII or UTF-8 character, or a named symbol such
as ‹α›, read through the ‹code› column of Isabelle's symbol table.
➧ ‹p*›, ‹p+› and ‹p?› repeat, ‹p q› concatenates, ‹p | q› is the union, ‹p # q›
the difference of two classes, and ‹(p)› groups.
➧ A name refers to a definition of the specification, ‹name(p⇩1, …, p⇩n)› instantiates a
template, and any other name is a HOL constant of one of the two types.
›
text ‹
Classes and regular expressions share one namespace, and the elaborator infers the
kind of each pattern: a union, difference or complement of classes is a class,
everything else a regular expression.
⬚‹pattern ‹p› where …› prints the elaboration of a pattern and its kind,
in an optional environment of definitions. In a term, ‹PAT‹p›› is the elaboration
of the pattern ‹p›, whose names are HOL constants: \<^term>‹PAT‹[a-z]+ | "_"››.
›
subsection ‹What is defined\label{sec:lexer-defined}›
text ‹
Lexing is defined once, for every alphabet, in the locale \<^locale>‹symbolic›. It
fixes nothing but the reading ‹sem :: 'p ⇒ 'ch ⇒ bool› of the atoms: \<^term>‹Pred p›
matches the characters ‹c› with ‹sem p c›, and \<^const>‹symbolic.lang› is the
language of a regular expression over atoms. There is no type class on ‹'ch› and no
finite alphabet, so codepoints and bytes are instances, not assumptions.
A specification ‹sp› gives each mode its list of rules. One step of lexing follows
the judgments ‹MaxPref› and ‹FirstToken› of Verbatim
\<^cite>‹‹Figs.~3--4› in "egolf2021-verbatim-verified-lexer"›: the lexeme is the
longest nonempty prefix of the input that a rule of the mode on top of the stack
matches, and the winning rule is the first that matches it. Its action, which Verbatim
does not have, gives the token class and the new stack.
The judgment ‹lexes sp is_newline st q s l r st⇩f› chains steps from the stack ‹st› and
the position ‹q›, and relates the input ‹s› to its tokens with their spans and trivia
‹l›, the residue ‹r› where no step applies, and the stack ‹st⇩f› it stops in. A lexical
error is not a failure but a nonempty residue, and an unterminated comment is an empty
residue in a mode that is not final. Each step consumes a nonempty lexeme, so whatever
the actions do to the stack, lexing ends:
@{thm [display, margin = 80] symbolic.lexes_total [no_vars]}
and with @{thm [source] symbolic.lexes_deterministic} the judgment is a function.
Totality is the argument Verbatim gives for the termination of its lexer, whose
recursive calls are on proper suffixes of the input
\<^cite>‹‹Sect.~IV› in "egolf2021-verbatim-verified-lexer"›. Determinism is its
Uniqueness lemma \<^cite>‹‹Sect.~V-B› in "egolf2021-verbatim-verified-lexer"›, here
for a judgment that also carries the stack.
The command takes the codepoints, natural numbers, as the alphabet, and classes of
type \<^typ>‹nat cls›, read by \<^const>‹in_cls›, as the atoms. For a lexer ‹L› it
defines:
➧ The specification ‹L.spec :: μ ⇒ … rule list›, by cases on the mode ‹μ›, with
the equations ‹L.spec.simps›. A rule pairs a regular expression \<^const>‹match›
with an action \<^const>‹act›, built by \<^const>‹mk_act› from the token class, the
guard, the effect on the stack and the hook. The constants ‹L.c› of the definitions,
the start mode ‹L.start›, the final modes ‹L.final› and the line ends
‹L.is_newline› come with it.
➧ The lexer ‹L_lex›, which runs \<^const>‹cp_lexer› on the DFA tables of
‹L.spec› from the stack ‹[L.start]› and the first position ‹q⇩0›. The command
evaluates the tables once for each distinct list of active rules, as constants
‹L_lex.tables_k› whose code equations are the evaluated tables, so modes with the
same rules share them; ‹L_lex.index› maps each mode to its tables. The code
equations are proved by evaluation, and only the generated code depends on them. ‹L_lex.ok w›
holds if ‹L_lex› consumes all of ‹w› and stops in a final mode.
➧ ‹L_lex.correct›: on an input of codepoints, ‹L_lex› computes the judgment,
@{text [display] ‹(∀c ∈ set w. c ≤ 0x10FFFF) ⟹
L_lex w = (l, r, st⇩f) ⟷
symbolic.lexes in_cls L.spec L.is_newline [L.start] q⇩0 w l r st⇩f›}
the instance of @{thm [source] cp_lexer_iff_lexes_in_range} for ‹L.spec›. With the
option ‹(▩‹char›)› it is @{thm [source] char_lexer_iff_lexes}, the judgment of
\<^const>‹char_spec› ‹L.spec› on bytes, with no condition on the input.
›
text ‹
The command reports each table with its modes, its size and the time of its
evaluation. It warns at a rule that wins in no state of a mode's tables, as
rules of higher priority match all its lexemes; ‹(▩‹no_check›)› drops the warning.
›
subsection ‹Example›
text ‹
Words and numbers, with nested comments in an exclusive mode:
@{theory_text [display, indent = 2]
‹datatype ctok = Word | Num
lexer cmt :: ‹ctok›
modes Code Comment
exclusive Comment
where letter = ‹[a-z]›
rules
‹letter+› ⇒ Word
| ‹[0-9]+› ⇒ Num
| ‹[ \n]+› ⇒ skip
| "(*" ⇒ skip, push Comment
| <Comment> (
"(*" ⇒ skip, push Comment
| "*)" ⇒ skip, pop
| ‹[^*(]+ | [*(]› ⇒ skip
)›}
The comment rules are active only in ‹Comment›, and the stack counts the depth of
nesting. ‹cmt.final› holds of ‹Code› only, so a text that ends inside a comment is
not ‹cmt_lex.ok›.
A hook tells a negation from a subtraction by the token before it:
@{theory_text [display, indent = 2]
‹datatype otok = Id | Minus | Neg | LParen | RParen
datatype omode = Start | AfterOperand
fun after_tok :: ‹otok option ⇒ omode ⇒ omode› where
‹after_tok (Some Id) _ = AfterOperand›
| ‹after_tok (Some RParen) _ = AfterOperand›
| ‹after_tok _ _ = Start›
lexer ops :: ‹otok›
modes ‹omode›
after after_tok
rules
‹[a-z]+› ⇒ Id | "(" ⇒ LParen | ")" ⇒ RParen | ‹[ ]+› ⇒ skip
| <Start> "-" ⇒ Neg
| <AfterOperand> "-" ⇒ Minus›}
Both examples can be found in 🗏‹lexer/tests/Lexer_Command_Tests.thy›.
›
section ‹Grammars and parsers\label{sec:grammar}›
text ‹
A grammar is a value of type \<^typ>‹('n, 'tok) is_cfg›: a list of productions over
nonterminals ‹'n› and token classes ‹'tok› with a start symbol, in which every
symbol on a right-hand side carries an indentation relation \<^typ>‹irel›
(🗏‹grammar/model/Indentation_Sensitive.thy›, after Adams
\<^cite>‹"adams2013"›). Its language \<^term>‹ilang G› is a set of token words, lists of
records \<^typ>‹('tok, 'ch, 'm) token_scheme›, of which a parser reads the class
\<^const>‹tok› and the column \<^const>‹s_col› of the \<^const>‹span›; the other fields
and any extension ‹'m› of the record pass through to the semantic actions. A
grammar may use the nonterminals of an earlier one and parametric nonterminals such as
‹Sep1(X, S)›, with the postfix operators ‹* + ?› for lists and options; both are
expanded before anything is defined, so the result is an ordinary closed grammar.
This meaning is a set of derivations, not a program
(Section~\ref{sec:grammar-defined}), and the command proves the parser it generates
sound for it. The parser runs the LR automaton of the grammar under one token of
lookahead with layout constraints in its lookahead. This static check of the tables
is evaluated when the parser is defined and its result is used to discharge the
determinism premise for completeness. Thus parsers for LALR(1) grammars are
automatically proven correct.
›
subsection ‹Specifications›
text ‹
\<^rail>‹
@@{command grammar} ('(' 'relation' ')')? name '=' ⏎
(@'open' (name +))? (@'tokens' type)? ⏎
terminals? (prec_decl *) ⏎
productions
›
➧ \descform{⬚‹grammar G = …›} checks the specification and defines the
grammar constant ‹G›; ⬚‹grammar (relation) G = …› also defines the
relation. The first nonterminal is the start symbol. ⬚‹open a⇩1 … a⇩n› lets
the productions refer to the nonterminals of earlier grammars without qualifier
(Section~\ref{sec:composition}), and the declarations ‹prec_decl› restrict the
trees of an ambiguous grammar (Section~\ref{sec:precedence}).
➧ \descform{⬚‹tokens T›} fixes the token type. ‹T› is a ground instance
of \<^typ>‹('tok, 'ch, 'm) token_scheme›: the plain record \<^typ>‹('tok, 'ch) token›,
or an extension ⬚‹record my_token = ‹(my_tok, char) token› + …›. Another
type ‹T› abbreviates ‹(T, unit) token›, and without the clause the token classes
are strings.
›
text ‹
\<^rail>‹
terminals: @'terminals' ((string '=' term | name) + @'and')
›
➧ \descform{⬚‹terminals "s" = t and c …›} declares the terminals. A
∗‹fixed spelling› ‹"s" = t› lets ‹"s"› stand for the token class ‹t› in the
productions, and binds no value. A bare name ‹c› declares a ∗‹token class›,
written by its name in the productions, whose value is the whole token record. A name
used in a production that is neither a nonterminal nor declared is read as a term of
the token class type.
›
text ‹
\<^rail>‹
productions: @'productions' (production + @'and')
;
production: name ('(' (name + ',') ')')? ('::' type)? '=' ⏎
(alternative + '|')
›
➧ \descform{⬚‹A :: ‹τ› = alt⇩1 | … | alt⇩n›} declares the nonterminal
‹A› with ∗‹carrier› ‹τ›, the type of its values. The ascription can be omitted
when the actions determine it. A production with parameters is a template
(Section~\ref{sec:templates}).
›
text ‹
\<^rail>‹
alternative: (symbol *) mark? ('⇒' term)?
;
mark: '(' @'prec' (string | name) ')'
›
➧ \descform{⬚‹X⇩1 … X⇩k (›\isakeyword{prec}~⬚‹q) ⇒ f›} is an alternative: a sequence of
symbols, an optional mark and an optional action. The action ‹f› computes the value
of the alternative from the values of its symbols, in order:
‹f :: τ⇩1 ⇒ … ⇒ τ⇩k ⇒ τ⇩A›. An alternative without action has exactly one
symbol with a value, which it passes on; one without symbols needs an action. The
mark gives the alternative a precedence level (Section~\ref{sec:precedence}).
‹⇒› may be written ▩‹=>›.
›
text ‹
\<^rail>‹
symbol: item ('⇧=' | '⇧≥' | '⇧>')? | @'@span'
;
item: (atom | '(' (symbol +) ')') (('*' | '+' | '?') *)
;
atom: string | cartouche | name ('.' name | '(' (item + ',') ')')?
›
➧ \descform{‹X›, ‹X⇧=›, ‹X⇧≥›, ‹X⇧>›} is a symbol ‹X› with its
annotation. ‹X› is a nonterminal, a
fixed spelling, a token class, an inline token class ‹‹t››, a nonterminal ‹a.X›
of an earlier grammar ‹a› (Section~\ref{sec:composition}), an instance of a template,
or a group with an operator. A nonterminal contributes its value, a token class the
token record. The annotation of a symbol is its indentation relation: ‹⇧=› for
\<^const>‹Eq›, ‹⇧≥› for \<^const>‹Ge› and ‹⇧>› for \<^const>‹Gt›, written
▩‹^=›, ▩‹^>=› and ▩‹^>› in ASCII; without annotation it is
\<^const>‹Any›. This departs from the convention of
\<^cite>‹‹Sect.~3.4› in "adams2013"›, where an unannotated nonterminal defaults to ‹=›
and an unannotated terminal to ‹>›.
➧ \descform{⬚‹@span›} is not a grammar symbol but a value of type
\<^typ>‹'ch span› among those of the symbols, where it is written: the span of the
alternative's yield, from the line, column and offset of its first token to the end
of its last, with their concatenated texts (\<^const>‹word_span›). It needs a symbol
that derives no empty word, is written once per alternative, takes no annotation and
stands at the top level of the alternative.
›
subsection ‹Precedence\label{sec:precedence}›
text ‹
\<^rail>‹
prec_decl: @'precedence' levels | @'forbid' forbid
;
levels: (level + '>')
;
level: (@'left' | @'right' | @'nonassoc' | @'open' | @'list') ((prec '!'?) +)
;
forbid: prec '@' nat (@'direct' | @'left' | @'right') (prec +)
;
prec: string | name
›
\isakeyword{precedence}~\isakeyword{right}~⬚‹"^" >›~\isakeyword{left}~⬚‹"*" "/" >›~\isakeyword{left}~⬚‹"+" "-" >›~\isakeyword{nonassoc}~⬚‹"=="›
declares levels, ‹>› binding tighter. A production has the level of its mark
(\isakeyword{prec}~‹NAME›), else that of its last terminal, written as its spelling or
its name; the name of a level need not be a terminal, as in
⬚‹"-" E (›\isakeyword{prec}~‹UMINUS›). This is the convention of yacc's ‹%left› and
‹%prec› in ocamlyacc \<^cite>‹"leroy2026-ocaml-manual"› and Menhir
\<^cite>‹"pottier2026-menhir-manual"›. Several declarations merge: a name in two of them is
one level, the order is their transitive closure, and a cycle is an error, as for the
priority chains of \<^cite>‹‹Sect.~3.3, Def.~2› in "afroozeh2013-operator-precedence"›. Two
levels that no declaration orders stay ambiguous, and the parser reports the conflict.
\isakeyword{left}, \isakeyword{right} and \isakeyword{nonassoc} have the usual readings. \isakeyword{open} leaves the left
operand of its productions unconstrained, for forms that end in an open construct,
and \isakeyword{list} does not order the productions of the level against each other, for
flat chains. A prefix form is allowed on the right of a tighter operator, as in
‹a * - b›; ‹!› on a name forbids that. \isakeyword{left} and \isakeyword{right} are the
associativity relations of \<^cite>‹‹Def.~4› in "afroozeh2013-operator-precedence"›, and the
levels become patterns after \<^cite>‹‹Tables~1--2› in "afroozeh2013-operator-precedence"›;
\isakeyword{open}, \isakeyword{list} and ‹!› are not in the paper. \isakeyword{forbid}~⬚‹p @ k›~\isakeyword{right}~‹c› says what no
level says: ‹c› is not on the right spine of child ‹k› of ‹p› (\isakeyword{left}: the left
spine, \isakeyword{direct}: the child itself). \isakeyword{direct} is a pattern
\<^cite>‹‹Def.~5› in "afroozeh2013-operator-precedence"›; the spine forms exclude
operators at any depth, which one-level patterns cannot
\<^cite>‹‹Sect.~2.2, Fig.~2› in "afroozeh2013-operator-precedence"›.
These declarations restrict the trees, not the grammar: they are a filter on the parse
trees of ‹G› \<^cite>‹‹Defs.~4.1, 4.8› in "klint1994-disambiguation-filters"›, given
as a tree automaton \<^cite>‹‹Sects.~1, 3.1› in "adams2017-tree-automata"›. A parser of ‹G› is built from
‹p_gram = restricted G p_prec›, and its theorems are stated against ‹G› and the
trees that satisfy ‹prec_ok›, or against the language ‹prec_lang›. Such a theory
imports ▩‹TIGER_Grammar.LR_Prec_Parse›. The relation of
⬚‹grammar (relation)› does not read the declarations, so no theorem is
stated against it.
›
subsection ‹Composition\label{sec:composition}›
text ‹
A symbol ‹a.X›, with ‹a› an earlier grammar and ‹X› one of its nonterminals, uses
‹X› in another grammar ‹b›. The productions of ‹a› reachable from ‹X› are copied
into ‹b›, renaming each nonterminal ‹Y› of ‹a› to ‹a.Y›; a copy ‹c.Z› that ‹a›
made itself keeps its name, so it is copied once however it is reached.
‹b› is then a closed grammar, and ‹a.X› one of its nonterminals. In the names of
constants and facts the dot is replaced with an underscore, for example
‹b__dec_a_X›, or ‹b_a_X›.
If ‹a› and ‹b› both have a relation, ‹b.a_X_iff: b_a_X i w x ⟷ a_X i w x› links them,
so what a parser of ‹b› proves about ‹a.X› is a fact about ‹a›.
⬚‹grammar b = open a› lets ‹b› write ‹X› for ‹a.X›: a bare name that is not a
nonterminal, terminal or template parameter of ‹b› itself is ‹a.X› if ‹a› defines ‹X›.
›
subsection ‹Templates and operators\label{sec:templates}›
text ‹
A production with parameters, ‹P(X⇩1, …, X⇩n) :: τ = …›, is a ∗‹template› and
defines nothing by itself. A use ‹P(a⇩1, …, a⇩n)›, with the parenthesis directly
after the name, is an ∗‹instance›: the production with each ‹X⇩i› replaced by
‹a⇩i›, an ordinary nonterminal made once for each distinct list of arguments. An
argument is a symbol, a symbol with an operator or a group of symbols. The actions of
the template see the right-hand side after the replacement, so a parameter bound to
a fixed spelling binds no value, and the type variables of the carrier are inferred
per instance. A template of an earlier grammar ‹g› is used as ‹g.P(…)›, or as
‹P(…)› if no other template has that name.
›
subsection ‹Parsers\label{sec:parser}›
text ‹
\<^rail>‹
@@{command parser} ('(' (option + ',') ')')? (entry + @'and')
;
entry: name @'for' name ('(' name ')')? error_clauses
›
➧ \descform{⬚‹parser p for G›} defines ‹p :: word ⇒ τ⇩S option› for the start
symbol ‹S› of ‹G›, with soundness and completeness theorems
(Section~\ref{sec:grammar-defined}).
➧ \descform{⬚‹parser p for G (A)›} parses from the nonterminal ‹A› instead:
‹p :: word ⇒ τ⇩A option›, for the grammar ‹G⦇istart := ''A''⦈› with the same
productions and the start ‹A›. Its theorems are those of the start symbol with
‹A› for ‹S›.
➧ \descform{⬚‹parser p for G and q for G (A)›} defines several parsers for one
grammar. They share its decoders, its relation and the lemmas their theorems are
proved with; each has its own tables. The clauses ‹error_clauses› are about
rejected words (Section~\ref{sec:diagnostics}).
›
text ‹
\<^rail>‹
option: 'ast' | 'diagnostics' | 'no_diagnostics' | name
›
➧ \descform{▩‹ast›} defines ‹p :: word ⇒ (…) ast option›, which
returns the raw parse tree and evaluates no semantic action.
➧ \descform{▩‹diagnostics› | ▩‹no_diagnostics›} turns the
report of a rejected word, ‹p_diag›, on (default) or off
(Section~\ref{sec:diagnostics}).
➧ \descform{‹name›} selects the parser generator, by default the
most recently declared one (i.e. ‹LR›).
›
subsection ‹What is defined\label{sec:grammar-defined}›
text ‹
The language of a grammar is defined by derivations in which every symbol has an
indentation. The indentation of a terminal is the column of its token. A nonterminal
has no token of its own; its indentation is free up to the annotations. Expanding a
nonterminal at indentation ‹i› by a production ‹A = X⇩1⇧r⇧1 … X⇩n⇧r⇧n› chooses for
each symbol an indentation ‹j⇩k› with ‹irel_sat r⇩k j⇩k i›:
\begin{center}
@{thm [mode = iff] irel_sat.simps(1) [no_vars]} \qquad
@{thm [mode = iff] irel_sat.simps(2) [no_vars]} \\
@{thm [mode = iff] irel_sat.simps(3) [no_vars]} \qquad
@{thm [mode = iff] irel_sat.simps(4) [no_vars]}
\end{center}
So ‹⇧=› aligns a symbol with the nonterminal being expanded, ‹⇧>› indents it
further, ‹⇧≥› allows both, and no annotation places no constraint. A block of aligned
statements is ‹Block = Stmt⇧= | Block⇧= Stmt⇧=›. A grammar without annotations is an
ordinary context-free grammar, and \<^term>‹ilang G› is the set of words derived in this
way from the start symbol at indentation ‹0›. This is the rewrite relation of
Adams \<^cite>‹‹Sect.~4› in "adams2013"›, with his four relations
‹=›, ‹>›, ‹≥› and ‹⋆›, the last written as no annotation.
›
text ‹
For ⬚‹grammar G› with nonterminals ‹A› of carrier ‹τ⇩A› and start
symbol ‹S› the command defines:
➧ The grammar ‹G :: (string, 'tok) is_cfg› with its definition ‹G_def›. The
nonterminals are represented by their names.
➧ A decoder ‹G__dec_A :: (…) ast ⇒ τ⇩A option› for each nonterminal, with the
equations ‹G__dec_A.simps›, which evaluates the actions over a parse tree.
➧ With ‹(relation)›, an inductive predicate ‹G_A :: nat ⇒ word ⇒ τ⇩A ⇒ bool›
for each nonterminal, with one introduction rule per alternative: ‹G_A i w x› holds
if ‹w› derives from ‹A› at indentation ‹i› with the value ‹x›. The facts are
‹G.intros›, ‹G.inducts› and ‹G.lang: (∃x. G_S 0 w x) ⟷ w ∈ ilang G›. For a
grammar without annotations the indentation argument is dropped.
›
text ‹
For ⬚‹parser p for G› it defines:
➧ The parser ‹p w = Option.bind (dparse G Shn w) G__dec_S›, where ‹dparse› is
the verified driver of 🗏‹grammar/lr/LR_Driver.thy› and ‹Shn› a fresh start symbol.
The code equation of ‹p› runs on tables that are computed once, when the code is
loaded, by a faster driver proved equal to ‹dparse›; for a grammar without
annotations this is a table-driven LR driver on a stack of state numbers. With
⬚‹declare [[parser_literal_tables]]› the tables are evaluated when the
parser is defined instead.
➧ ‹p.sound› and ‹p.complete› relate the parser to the language:
\begin{center}
‹p.sound: p w = Some x ⟹ w ∈ ilang G› \\
‹p.complete: w ∈ ilang G ⟹ ∃x. p w = Some x›
\end{center}
For a grammar with a relation, to the relation of the start symbol:
\begin{center}
‹p.sound: p w = Some x ⟹ G_S 0 w x› \\
‹p.complete: G_S 0 w x ⟹ p w = Some x›
\end{center}
and the language forms are ‹p.sound_lang› and ‹p.complete_lang›. With ‹(ast)›
they are about the parse trees of ‹G›:
\begin{center}
‹p.sound: p w = Some t ⟹ ast_of G (Nt (istart G)) (istart_ind G) t w› \\
‹p.complete: wf_ptree G pt ⟹ proot pt = (Nt (istart G), istart_ind G) ⟹
p (pyield pt) = Some (erase pt)›
\end{center}
that is, ‹t› is (the erasure of) a parse tree of ‹w›, and every parse tree of a
word is the one ‹p› returns, which is therefore unique.
›
text ‹
Soundness holds outright. Completeness needs the determinism of the driver on the
grammar, ‹mdet G Shn›, and the totality of the decoders. For determinism the
command evaluates ‹rlalr_conflicts G Shn›, the LALR(1) conflict analysis extended with
the layout constraints. If there are no conflicts, ‹mdet› follows; otherwise the
command lists the conflicting states and keeps ‹mdet› as a premise of
‹p.complete›. The check is sufficient but not necessary: an ambiguous grammar
always fails it, a deterministic one may fail it too. The parser is defined either
way, and ⬚‹thm p.complete› shows what has been established.
The checks are proved by evaluation (‹Code_Runtime.dynamic_holds_conv›), so an
unconditional ‹p.complete› trusts the code generator; ‹p.sound› does not
depend on evaluation. The code equation of ‹p› does: the checks that let the
faster driver stand for ‹dparse› are evaluated too. Jourdan, Pottier and Leroy
also check their automaton by computation, running their validator with Coq's
virtual machine \<^cite>‹‹Sect.~5› in "jourdan2012-validating-lr1"›.
›
subsection ‹Diagnostics and recovery\label{sec:diagnostics}›
text ‹
‹p› says only ‹None› on a rejected word. Unless ⬚‹parser (no_diagnostics)›
turns it off, each parser also defines ‹p_diag›, with ‹p_diag w = Inr x› exactly
when ‹p w = Some x› (‹p_diag.Inr_iff›) and otherwise ‹Inl e›, a report: the token
where the word failed, the expected terminals with their columns, the stack with its
spans and any repair. ‹perr_message› renders it. A bracket that is not closed is
named as such, and a long list of expected terminals is shortened to the
nonterminals that may start there.
No theorem is about the ‹Inl› side, by design: a report can be wrong, but no word
changes its status. Recovery is built the same way. It rewrites the word, unverified,
and the verified ‹p› parses the result, so all its theorems apply to the tree. None
of this changes ‹p› or its tables, and all of it runs only after a failure.
›
text ‹
\<^rail>‹
error_clauses: (@'recover' name)? repair? ⏎
(@'on_error_reduce' (name +))? ⏎
(@'token_info' term)? ⏎
(@'errors' (message + '|'))?
›
➧ \descform{\isakeyword{recover}~‹e›} adds ‹p_recover› for a grammar in which the terminal ‹e›
stands for broken input, with ordinary productions such as ‹Expr = … | ERR ⇒ EErr›.
‹p_recover w = (errs, p w')›: where ‹w› fails, the stack is popped to a state that
can shift ‹e›, tokens are skipped up to one that continues, and the stretch becomes
one ‹e›, as with the ‹error› token of ocamlyacc
\<^cite>‹‹Sect.~17.4.4› in "leroy2026-ocaml-manual"›, which skips to three tokens
that continue.
➧ \descform{\isakeyword{on\_error\_reduce}~‹A B›} lets the report of a rejected word come after
reducing productions of ‹A› or ‹B› \<^cite>‹‹Sect.~4› in "pottier2016-lr1-reachability"›, so it names the
construct that was complete.
➧ \descform{\isakeyword{token\_info}~‹f›} gives the record extension for a token
class, for the sentences of \isakeyword{errors} with extended token records.
›
text ‹
\<^rail>‹
repair: @'repair' (@'token' term)? (@'avoid' (name +))?
›
➧ \descform{\isakeyword{repair}} adds ‹p_recover› for any grammar: at an error it searches for
a least-cost sequence of inserted and deleted tokens, ranked by how far parsing goes
on, as in CPCT+ \<^cite>‹"diekmann2020-dont-panic"›. A budget of search nodes bounds it.
\isakeyword{repair}~\isakeyword{token}~‹f› supplies inserted tokens whose text an action reads, and
\isakeyword{repair}~\isakeyword{avoid}~‹A B› ranks repairs that insert ‹A› or ‹B› lower.
›
text ‹
\<^rail>‹
message: (sentence | cartouche) ('(' (@'token' | @'shift') ')')? '⇒' text
;
sentence: ((name ('@' nat)?) +)
›
➧ \descform{\isakeyword{errors}~⬚‹s ⇒ ‹m› | …›} attaches messages to error states by example
\<^cite>‹"jeffery2003-lr-error-messages" and "pottier2016-lr1-reachability"›. The sentence ‹s› is written with the spellings or
names of terminals, each with an optional column after ‹@›, or as a cartouche with a
term of the word type. It fails at its last token, or at its end. The message
replaces the first line of the report of every word that fails in the same state, or
with ‹(token)› in the same state at the same terminal; ‹$0› to ‹$9› stand for the
text of the stack entries from the top. The keys are computed from the sentences,
so an edit of the grammar that renumbers the states needs no change of the block.
›
subsection ‹Example›
text ‹
A statement is an identifier or a ‹while› header followed by a block indented
further than the header, the statements of a block aligned. The value is the number
of statements:
@{theory_text [display, indent = 2]
‹datatype tok = While | Colon | Id
grammar (relation) py =
tokens ‹tok›
terminals "while" = ‹While› and ":" = ‹Colon›
productions
Prog :: ‹nat› = Block
and
Block :: ‹nat›
= Stmt⇧=
| Block⇧= Stmt⇧= ⇒ ‹(+)›
and
Stmt :: ‹nat›
= Id⇧= ⇒ ‹λ_. 1›
| "while"⇧= Id⇧> ":"⇧> Block⇧> ⇒ ‹λ_ n. n + 1›
parser py_parse for py›}
‹Id› is a token class, so the first action of ‹Stmt› takes its token record and
ignores it. ‹Block› without annotation leaves the column of the outermost block free,
‹Block⇧>› after a header demands a deeper one, and ‹Block⇧= Stmt⇧=› aligns the
members. The introduction rules of ‹py_Stmt›, writing ‹⟨t; sp⟩› for the token
‹⦇tok = t, span = sp⦈›, are
\begin{mathpar}
\inferrule
{\mbox{‹s_col sp = i›}}
{\mbox{‹py_Stmt i [⟨Id; sp⟩] 1›}}
\and
\inferrule
{\mbox{‹py_Block j w v›} \\
\mbox{‹s_col sp⇩1 = i›} \\
\mbox{‹i < s_col sp⇩2›} \\
\mbox{‹i < s_col sp⇩3›} \\
\mbox{‹i < j›}}
{\mbox{‹py_Stmt i (⟨While; sp⇩1⟩ # ⟨Id; sp⇩2⟩ # ⟨Colon; sp⇩3⟩ # w) (v + 1)›}}
\end{mathpar}
The grammar has no conflicts, so completeness is unconditional:
\begin{center}
‹py_parse.complete: py_Prog 0 w x ⟹ py_parse w = Some x›
\end{center}
With ‹tu c t› a token of class ‹t› at column ‹c›:
@{theory_text [display, indent = 2]
‹lemma ‹py_parse [tu 1 While, tu 7 Id, tu 8 Colon, tu 3 Id, tu 3 Id, tu 1 Id] = Some 4›
by eval
lemma ‹py_parse [tu 1 While, tu 7 Id, tu 8 Colon, tu 3 Id, tu 4 Id] = None›
by eval›}
More examples are in 🗏‹grammar/tests/Regression_Tests.thy›.
›
end