Theory TIGER_Lexer.TIGER_Spec

(* Author: Basil Fürer *)

theory TIGER_Spec
  imports TIGER_Regex TIGER_Lexed
begin

section ‹The lexer specification›

text ‹A lexer spec maps each mode to a prioritized list of rules. A rule is a regex over
  syntactic predicates and an action. The action sees the matched text and the mode stack
  (its head is the current mode) and returns the token kind, or const‹None› for
  trivia, and the new stack cite‹‹Sect.~10› in "paxson2026-flex-manual"›. The judgments follow Verbatim
  cite‹‹Figs.~3--4› in "egolf2021-verbatim-verified-lexer"›: the longest prefix, the
  first rule matching it, and the driver, which stops with the unread residue and the
  stack it stops in.

  The judgments live in the context of ‹symbolic› and read a rule's regex through the
  denotation ‹sem› of its predicates (const‹symbolic.lang›).

  An empty match is never a match, and an action returning the empty stack is an error
  (the driver stops before that step). Both make the driver total and deterministic.
  Reps assumes instead that no token regex admits the empty word
  cite‹‹Sect.~1› in "reps1998-maximal-munch-linear"›. Here a rule's regex
  may accept it, and ‹match_rule› drops that match.›

record ('k, 'p, 'ch, 'm) rule =
  match :: ‹'p rexp›
  act :: ‹'ch list ⇒ 'm list ⇒ 'k option × 'm list›

type_synonym ('k, 'p, 'ch, 'm) lexer_spec = ‹'m ⇒ ('k, 'p, 'ch, 'm) rule list›

context symbolic
begin

inductive match_rule :: ‹('k, 'p, 'ch, 'm) rule ⇒ 'ch list ⇒ bool› where
  match_ruleI: ‹⟦ p ∈ lang (match ρ); p ≠ [] ⟧ ⟹ match_rule ρ p›

text ‹A rule matches a nonempty word of its language
  cite‹‹Fig.~4, FirstToken› in "egolf2021-verbatim-verified-lexer"›.›

inductive max_pref where
  max_prefI:
    ‹⟦ s = p @ u; ρ ∈ set rs; match_rule ρ p;
      ⋀p' u' ρ'.
        ⟦ s = p' @ u'; length p < length p'; ρ' ∈ set rs ⟧ ⟹
        ¬ match_rule ρ' p'
     ⟧ ⟹
     max_pref rs p s›

text ‹‹p› is the longest prefix of ‹s› that some rule matches
  cite‹‹Fig.~3, MaxPref› in "egolf2021-verbatim-verified-lexer"›.›

inductive first_token where
  first_tokenI:
    ‹⟦ max_pref rs p s; i < length rs; match_rule (rs ! i) p;
      ⋀j. j < i ⟹ ¬ match_rule (rs ! j) p
     ⟧ ⟹
     first_token rs i p s›

text ‹Rule ‹i› wins on ‹s› with lexeme ‹p›: ‹p› is the longest match and ‹i› the first
  rule matching it cite‹‹Sect.~7› in "paxson2026-flex-manual"›, as in lex
  cite‹‹Sect.~5› in "lesk1975-lex"›.›

inductive step where
  stepI:
    ‹⟦ first_token (sp m) i p s;
       act (sp m ! i) p (m # st) = (k, st');
       st' ≠ [];
       s = p @ s'
     ⟧ ⟹
     step sp (m # st) s (k, p, st', s')›

text ‹One step in the stack ‹m # st› reads the winning lexeme ‹p›, runs the winning action
  and yields the kind ‹k›, the new stack and the rest of the input.›

inductive lexes ::
  ‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒
    'ch list ⇒ ('k, 'ch) lexed ⇒ 'ch list ⇒ 'm list ⇒ bool›
for sp is_newline where
  lexes_stop:
    ‹(⋀x. ¬ step sp st s x) ⟹ lexes sp is_newline st q s (Lexed [] []) s st›
| lexes_token:
    ‹⟦ step sp st s (Some k, p, st', s');
       lexes sp is_newline st' (advance_list is_newline p q) s' (Lexed h ts) r stf
     ⟧ ⟹
     lexes sp is_newline st q s
      (Lexed [] (⦇tok = k, span = span_at q p, trivia = h⦈ # ts)) r stf›
| lexes_trivia:
    ‹⟦ step sp st s (None, p, st', s');
       lexes sp is_newline st' (advance_list is_newline p q) s' (Lexed h ts) r stf
     ⟧ ⟹
     lexes sp is_newline st q s (Lexed (p @ h) ts) r stf›

text ‹The driver lexes ‹s› from stack ‹st› and position ‹q› into a lexed source, the
  residue ‹r› where no step applies and the stack ‹stf› it stops in
  cite‹‹Fig.~4, Tokens› in "egolf2021-verbatim-verified-lexer"›. The leading trivia
  of the rest become the trailing trivia of a token, or the header in front of the
  first token. Spans come from const‹advance_list›.

  The final stack says where the input ended, so the end of the input needs no
  sentinel character (flex's ‹<<EOF>>› cite‹‹Sect.~12› in "paxson2026-flex-manual"›).
  An empty residue in a stack whose top is not a final mode (an unterminated comment)
  is an error of the consumer's, not of the driver.›

subsection ‹Some facts›

lemma max_prefD: ‹max_pref rs p s ⟹ (∃u. s = p @ u) ∧ (∃ρ ∈ set rs. match_rule ρ p)›
  by (blast elim: max_pref.cases)

lemma max_pref_longest:
  assumes ‹max_pref rs p s› ‹s = p' @ u'› ‹length p < length p'› ‹ρ' ∈ set rs›
  shows ‹¬ match_rule ρ' p'›
  using ‹max_pref rs p s›
proof (cases rule: max_pref.cases)
  case max_prefI
  then have ‹⋀p' u' ρ'. ⟦ s = p' @ u'; length p < length p'; ρ' ∈ set rs ⟧ ⟹ ¬ match_rule ρ' p'›
    by blast
  with assms show ?thesis by blast
qed

lemma first_token_max_pref: ‹first_token rs i p s ⟹ max_pref rs p s›
  by (auto elim: first_token.cases)

lemma first_token_match: ‹first_token rs i p s ⟹ match_rule (rs ! i) p›
  by (auto elim: first_token.cases)

lemma first_token_first: ‹first_token rs i p s ⟹ j < i ⟹ ¬ match_rule (rs ! j) p›
  by (auto elim: first_token.cases)

lemma first_token_prefix: ‹first_token rs i p s ⟹ ∃u. s = p @ u›
  by (auto elim!: first_token.cases max_pref.cases)

lemma step_length_less: ‹step sp st s (k, p, st', s') ⟹ length s' < length s›
  by (auto elim!: step.cases first_token.cases match_rule.cases)

text ‹Every step consumes input (no empty matches). This is the progress measure of the
  driver.›

lemma lexes_source: ‹lexes sp is_newline st q s l r stf ⟹ source l @ r = s›
  by (induct rule: lexes.induct) (auto simp: source_def span_at_def elim!: step.cases)

section ‹Surface theorems›

text ‹The spec is unambiguous: the first token is unique, and so are a step and a whole
  run. This is Verbatim's Uniqueness lemma
  cite‹‹Sect.~V-B› in "egolf2021-verbatim-verified-lexer"›, proved the same way: both
  lexemes are maximal prefixes of one string, so they are equal, and of two rules matching
  it the later one cannot win. Verbatim has no modes; here the run also fixes the final
  stack.›

theorem first_token_deterministic:
  assumes ‹first_token rs i p s› ‹first_token rs i' p' s›
  shows ‹i = i' ∧ p = p'›
proof -
  from assms have mp: ‹max_pref rs p s› and mp': ‹max_pref rs p' s›
    by (simp_all add: first_token_max_pref)
  from mp obtain u ρ where ‹s = p @ u› ‹ρ ∈ set rs› ‹match_rule ρ p›
    by (blast dest: max_prefD)
  from mp' obtain u' ρ' where ‹s = p' @ u'› ‹ρ' ∈ set rs› ‹match_rule ρ' p'›
    by (blast dest: max_prefD)
  have ‹¬ length p < length p'›
    using max_pref_longest[OF mp ‹s = p' @ u'› _ ‹ρ' ∈ set rs›] ‹match_rule ρ' p'› by blast
  moreover have ‹¬ length p' < length p›
    using max_pref_longest[OF mp' ‹s = p @ u› _ ‹ρ ∈ set rs›] ‹match_rule ρ p› by blast
  ultimately have ‹p = p'›
    using ‹s = p @ u› ‹s = p' @ u'› by simp
  with assms show ?thesis
    by (metis linorder_neqE_nat first_token_first first_token_match)
qed

theorem step_deterministic: ‹step sp st s x ⟹ step sp st s y ⟹ x = y›
  by (elim step.cases) (auto dest: first_token_deterministic)

theorem lexes_deterministic:
  assumes ‹lexes sp is_newline st q s l r stf› ‹lexes sp is_newline st q s l' r' stf'›
  shows ‹l = l' ∧ r = r' ∧ stf = stf'›
  using assms
proof (induction arbitrary: l' r' stf' rule: lexes.induct)
  case (lexes_stop st s q)
  from lexes_stop.prems show ?case
    by (cases rule: lexes.cases) (use lexes_stop.hyps in blast)+
next
  case (lexes_token st s k p st' s' q h ts r stf)
  from lexes_token.prems ‹step sp st s (Some k, p, st', s')› show ?case
    by (cases rule: lexes.cases)
      (auto dest: step_deterministic[OF ‹step sp st s (Some k, p, st', s')›] lexes_token.IH)
next
  case (lexes_trivia st s p st' s' q h ts r stf)
  from lexes_trivia.prems ‹step sp st s (None, p, st', s')› show ?case
    by (cases rule: lexes.cases)
      (auto dest: step_deterministic[OF ‹step sp st s (None, p, st', s')›] lexes_trivia.IH)
qed

text ‹The driver terminates on every input, whatever the actions do to the stack
  (each step consumes a nonempty lexeme, @{thm [source] step_length_less}). This is the
  termination argument of Verbatim's ‹lex0›, which recurses on proper suffixes of the input
  cite‹‹Sect.~IV› in "egolf2021-verbatim-verified-lexer"›. Verbatim must thread an
  accessibility proof through the function; here the run is an inductive relation and
  totality is a theorem, by induction on the length of the input:›

theorem lexes_total: ‹∃l r stf. lexes sp is_newline st q s l r stf›
proof (induct s arbitrary: st q rule: length_induct[case_names len])
  case (len s) show ?case
  proof (cases ‹∃x. step sp st s x›)
    case True
    then obtain k p st' s' where step: ‹step sp st s (k, p, st', s')›
      by (metis prod_cases4)
    with len obtain l r stf
      where ‹lexes sp is_newline st' (advance_list is_newline p q) s' l r stf›
      by (meson step_length_less)
    with step show ?thesis
      by (cases l; cases k; blast intro: lexes_token lexes_trivia)
  qed (blast intro: lexes_stop)
qed

end

end