Theory TIGER

(* Author: Basil Fürer *)

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 m1 … mn›} lists modes in which only the rules
  tagged for them are active (flex's ‹%x› cite‹‹Sect.~10› in "paxson2026-flex-manual"›).

  ➧ \descform{⬚‹final m1 … mn›} 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 r1 | … | rn›} 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> (r1 | … | rn)› 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(p1, …, pn)› 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 stf› 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 ‹stf› 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 ‹q0›. 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, stf) ⟷
    symbolic.lexes in_cls L.spec L.is_newline [L.start] q0 w l r stf›}
  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 a1 … an› 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 :: ‹τ› = alt1 | … | altn›} 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{⬚‹X1 … Xk (›\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(X1, …, Xn) :: τ = …›, is a ∗‹template› and
  defines nothing by itself. A use ‹P(a1, …, an)›, with the parenthesis directly
  after the name, is an ∗‹instance›: the production with each ‹Xi› replaced by
  ‹ai›, 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 = X1r1 … Xnrn› chooses for
  each symbol an indentation ‹jk› with ‹irel_sat rk jk 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 sp1 = i›} \\
     \mbox{‹i < s_col sp2›} \\
     \mbox{‹i < s_col sp3›} \\
     \mbox{‹i < j›}}
    {\mbox{‹py_Stmt i (⟨While; sp1⟩ # ⟨Id; sp2⟩ # ⟨Colon; sp3⟩ # 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›.
›

(* Citations in the theories that this document does not make, as cite forms to paste
   into a text block.

  LR construction:
    the state sets cite‹‹Sect.~II, step 3› in "knuth1965-lr-translation"›,
    the LR(k) condition cite‹‹Sect.~I› in "knuth1965-lr-translation"›;
    the LR(0) automaton cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›,
    per-item lookahead cite‹‹Sect.~3› in "deremer1982-lalr-lookahead"›,
    the NQLALR pitfall cite‹‹Sect.~5.1› in "deremer1982-lalr-lookahead"›;
    the worklist ‹visit› cite‹‹Sect.~5.3, Def.~5.5.4› in "barthwal2010-thesis-cfl-hol4"›,
    conflict freedom on reachable states cite‹‹Def.~5.3.7, Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"›;
    the completeness validator cite‹‹Sect.~3.3, Thm.~3› in "jourdan2012-validating-lr1"›,
    unambiguity cite‹‹Thm.~4› in "jourdan2012-validating-lr1"›.

  Regexes and lexer tables:
    partial derivatives cite‹‹Def.~2.8, Prop.~2.10› in "antimirov1996-partial-derivatives"›,
    finitely many cite‹‹Thm.~3.4› in "antimirov1996-partial-derivatives"›;
    effective Boolean algebras cite‹‹Sect.~2› in "dantoni2014-minimization-symbolic-automata"›,
    minterms cite‹‹Sect.~4, Fig.~2› in "dantoni2014-minimization-symbolic-automata"›,
    a transition by a minterm cite‹‹Prop.~1› in "dantoni2014-minimization-symbolic-automata"›;
    character classes of a regex cite‹‹Thm.~4.2› in "owens2009-regex-derivatives-reexamined"›;
    backing up to the last accepting position cite‹‹Sect.~2, Fig.~1(a)› in "reps1998-maximal-munch-linear"›,
    the quadratic example cite‹‹Sect.~1› in "reps1998-maximal-munch-linear"›,
    linear-time tokenization cite‹‹Sect.~3› in "reps1998-maximal-munch-linear"›;
    JFlex's ‹%8bit› cite‹‹``Input Character sets''› in "klein2023-jflex-manual"›;
    Unicode scalar values cite‹‹Sect.~3.9, D76› in "unicode2025-standard"›.
*)

end