Theory TIGER_Lexer
theory TIGER_Lexer
imports TIGER_Gen
begin
section ‹The runner›
text ‹The runner steps the DFA of a mode over the input, remembers the last accepting
position and its rule, stops at the dead state or at the end of input, and backs up to
that position \<^cite>‹‹Sect.~17› in "paxson2026-flex-manual"›
\<^cite>‹‹Sect.~2, Fig.~1(a)› in "reps1998-maximal-munch-linear"›. Its surface theorem is
equality with \<^const>‹symbolic.first_token›, the step of the specification. The proof
follows the shape of ‹auto_split_lemma› in \<^session>‹Functional-Automata›
(‹AutoMaxChop›), Nipkow's scanner ‹auto_split›
\<^cite>‹‹Sect.~5.2› in "nipkow1998-verified-lexical-analysis"›: an invariant on the
part already read, carried along the scan. Nipkow's scanner has one automaton and no rule
priorities; here the last accept also records the winning rule.
The driver over \<^const>‹symbolic.lexes› is in theory ‹TIGER_Driver›. Reps'
bounded-lookahead linearity \<^cite>‹‹Sect.~3› in "reps1998-maximal-munch-linear"›
comes later, and Reps' memoization of failed state-position pairs is deferred.
Verbatim++ verifies a Reps-style memo of maximal-prefix results across tokens, keyed by
the length of the suffix, and analyses the result as ‹O(n log n)›
\<^cite>‹‹Sects.~4--5› in "egolf2022-verbatim-plus-plus"›.›
subsection ‹The scan on tables›
text ‹The scan reads tables only: the transition table ‹T›, indexed by state and
minterm number, the acceptance table ‹A›, the classifier ‹cls› from characters to
minterm numbers (a table lookup at run time) and the index ‹d› of the dead state. It
keeps the current state ‹q›, the number ‹n› of characters read and the last accept
as a rule and a length. The initial state is ‹0› and the empty prefix never counts as
an accept:›
fun scan ::
‹nat list list ⇒ nat option list ⇒ ('ch ⇒ nat) ⇒ nat ⇒ nat ⇒ nat ⇒ 'ch list ⇒
(nat × nat) option ⇒ (nat × nat) option›
where
‹scan T A cls d q n [] b = b›
| ‹scan T A cls d q n (c # v) b =
(let q' = T ! q ! cls c in
if q' = d then b
else scan T A cls d q' (Suc n) v (case A ! q' of None ⇒ b | Some i ⇒ Some (i, Suc n)))›
text ‹The runner backs up to the last accept and splits the input there:›
definition run_tables ::
‹nat list list ⇒ nat option list ⇒ ('ch ⇒ nat) ⇒ nat ⇒ 'ch list ⇒
(nat × 'ch list × 'ch list) option›
where
‹run_tables T A cls d s =
map_option (λ(i, n). (i, take n s, drop n s)) (scan T A cls d 0 0 s None)›
text ‹An index below the length of the list finds its element:›
lemma nth_index_of_if_less: ‹index_of Q y < length Q ⟹ Q ! index_of Q y = y›
by (induct Q) auto
subsection ‹The invariant›
context symbolic
begin
text ‹After reading ‹u›, the remembered accept ‹b› is the longest nonempty prefix of ‹u›
that some rule matches, with the least rule matching it. This is \<^const>‹first_token›
on ‹u›. With no accept, no rule matches a prefix of ‹u›:›
definition last_accept :: ‹('k, 'p, 'ch, 'm) rule list ⇒ 'ch list ⇒ (nat × nat) option ⇒ bool›
where
‹last_accept rs u b = (case b of
None ⇒ ∀p t ρ. u = p @ t ⟶ ρ ∈ set rs ⟶ ¬ match_rule ρ p
| Some (i, n) ⇒ n ≤ length u ∧ first_token rs i (take n u) u)›
lemma last_accept_Nil: ‹last_accept rs [] None›
by (simp add: last_accept_def match_rule.simps)
text ‹A longest match stays longest when the input grows by words that no rule matches:›
lemma max_pref_append:
assumes ‹max_pref rs p u›
and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
shows ‹max_pref rs p (u @ v)›
proof -
from assms(1) obtain r ρ where ‹u = p @ r› ‹ρ ∈ set rs› ‹match_rule ρ p›
by (blast dest: max_prefD)
show ?thesis
proof (rule max_prefI[of ‹u @ v› p ‹r @ v› ρ rs])
show ‹u @ v = p @ r @ v›
using ‹u = p @ r› by simp
next
fix p' u' ρ'
assume ‹u @ v = p' @ u'› ‹length p < length p'› ‹ρ' ∈ set rs›
from ‹u @ v = p' @ u'› obtain us where ‹u = p' @ us ∧ us @ v = u' ∨ u @ us = p' ∧ v = us @ u'›
unfolding append_eq_append_conv2 by blast
then show ‹¬ match_rule ρ' p'›
proof
assume ‹u = p' @ us ∧ us @ v = u'›
then show ?thesis
using max_pref_longest[OF assms(1), of p' us ρ'] ‹length p < length p'› ‹ρ' ∈ set rs›
by blast
next
assume ‹u @ us = p' ∧ v = us @ u'›
then show ?thesis
using max_pref_longest[OF assms(1), of p' ‹[]› ρ'] ‹length p < length p'›
‹ρ' ∈ set rs› assms(2)[of us u' ρ']
by (cases ‹us = []›) auto
qed
qed fact+
qed
lemma first_token_append:
assumes ‹first_token rs i p u›
and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
shows ‹first_token rs i p (u @ v)›
proof -
from assms(1) have ‹max_pref rs p u› ‹i < length rs› ‹match_rule (rs ! i) p›
‹∀j < i. ¬ match_rule (rs ! j) p›
by (auto elim: first_token.cases)
moreover from ‹max_pref rs p u› assms(2) have ‹max_pref rs p (u @ v)›
by (rule max_pref_append)
ultimately show ?thesis
by (blast intro: first_tokenI)
qed
lemma last_accept_append:
assumes ‹last_accept rs u b›
and ‹⋀w t ρ. v = w @ t ⟹ w ≠ [] ⟹ ρ ∈ set rs ⟹ ¬ match_rule ρ (u @ w)›
shows ‹last_accept rs (u @ v) b›
proof (cases b)
case None
moreover have ‹¬ match_rule ρ p› if ‹u @ v = p @ t› ‹ρ ∈ set rs› for p t ρ
proof -
from ‹u @ v = p @ t› obtain us where ‹u = p @ us ∧ us @ v = t ∨ u @ us = p ∧ v = us @ t›
unfolding append_eq_append_conv2 by blast
then show ?thesis
proof
assume ‹u = p @ us ∧ us @ v = t›
with assms(1) None ‹ρ ∈ set rs› show ?thesis
by (auto simp: last_accept_def)
next
assume ‹u @ us = p ∧ v = us @ t›
with assms None ‹ρ ∈ set rs› show ?thesis
by (cases ‹us = []›) (auto simp: last_accept_def)
qed
qed
ultimately show ?thesis by (simp add: last_accept_def)
next
case (Some a)
then obtain i n where ‹b = Some (i, n)›
by (cases a) auto
with assms(1) have ‹n ≤ length u› ‹first_token rs i (take n u) u›
by (simp_all add: last_accept_def)
with ‹b = Some (i, n)› show ?thesis
using first_token_append[OF ‹first_token rs i (take n u) u› assms(2)]
by (simp add: last_accept_def)
qed
text ‹On a nonempty word, the acceptance of the state reached says which rules match it:›
lemma no_match_iff_acc_None:
‹w ≠ [] ⟹
(∀ρ ∈ set rs. ¬ match_rule ρ w) ⟷ acc (foldl delta_char (init_state rs) w) = None›
by (auto simp: acc_foldl_delta_char_None_iff match_rule.simps in_set_conv_nth) (metis nth_mem)
lemma first_token_self_if_acc:
assumes ‹w ≠ []› ‹acc (foldl delta_char (init_state rs) w) = Some i›
shows ‹first_token rs i w w›
proof -
from assms have ‹i < length rs› ‹match_rule (rs ! i) w› ‹∀j < i. ¬ match_rule (rs ! j) w›
using acc_foldl_delta_char_match_rule[OF assms(1), of rs i] by blast+
moreover have ‹max_pref rs w w›
by (rule max_prefI[of w w ‹[]› ‹rs ! i› rs]) (use calculation in auto)
ultimately show ?thesis
by (blast intro: first_tokenI)
qed
end
subsection ‹The scan keeps the invariant›
context eba
begin
text ‹A classifier sends every character to a minterm of the mode that holds for it.
\<^const>‹minterm_index› is one. The run-time lexer uses a table:›
definition minterm_classifier :: ‹('k, 'p, 'ch, 'm) rule list ⇒ ('ch ⇒ nat) ⇒ bool› where
‹minterm_classifier rs cls ⟷
(∀c. cls c < length (mode_minterms rs) ∧ sem (snd (mode_minterms rs ! cls c)) c)›
lemma minterm_classifier_minterm_index: ‹minterm_classifier rs (minterm_index rs)›
by (simp add: minterm_classifier_def minterm_index)
text ‹The dead state is the index of the empty state. If the empty state is not
explored, the index is out of range and never reached:›
definition dead_state :: ‹('k, 'p, 'ch, 'm) rule list ⇒ nat› where
‹dead_state rs = index_of (dfa_states (mode_dfa rs)) {}›
definition run_dfa ::
‹('k, 'p, 'ch, 'm) rule list ⇒ ('ch ⇒ nat) ⇒ 'ch list ⇒
(nat × 'ch list × 'ch list) option›
where
‹run_dfa rs cls =
run_tables (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs)›
text ‹A transition through the classifier is the step by the character
(@{thm [source] delta_eq_delta_char}):›
lemma trans_step:
assumes ‹minterm_classifier rs cls› ‹q < length (dfa_states (mode_dfa rs))›
shows ‹dfa_trans (mode_dfa rs) ! q ! cls c < length (dfa_states (mode_dfa rs)) ∧
dfa_states (mode_dfa rs) ! (dfa_trans (mode_dfa rs) ! q ! cls c) =
delta_char (dfa_states (mode_dfa rs) ! q) c›
proof -
let ?M = ‹mode_minterms rs›
let ?Q = ‹dfa_states (mode_dfa rs)›
let ?k = ‹cls c›
let ?q' = ‹dfa_trans (mode_dfa rs) ! q ! ?k›
from assms(1) have k: ‹?k < length ?M› ‹sem (snd (?M ! ?k)) c›
unfolding minterm_classifier_def by blast+
have q': ‹?q' < length ?Q ∧ ?Q ! ?q' = delta (?Q ! q) (fst (?M ! ?k))›
using dfa_trans_correct[of q ‹map fst ?M› rs ?k] assms(2) k(1)
by (simp add: mode_dfa_def)
have ‹?Q ! q ⊆ tagged_closure rs›
using dfa_states_subset[OF nth_mem[OF assms(2)[unfolded mode_dfa_def]]]
by (simp add: mode_dfa_def)
moreover have ‹(fst (?M ! ?k), snd (?M ! ?k)) ∈ set ?M›
using k(1) by simp
ultimately have ‹delta (?Q ! q) (fst (?M ! ?k)) = delta_char (?Q ! q) c›
using k(2) by (rule delta_eq_delta_char)
with q' show ?thesis
by simp
qed
text ‹The invariant holds after every character the scan reads. At the dead state no
extension of the input read so far is matched, so stopping there keeps it too:›
lemma scan_last_accept:
assumes ‹minterm_classifier rs cls›
and ‹q < length (dfa_states (mode_dfa rs))›
and ‹dfa_states (mode_dfa rs) ! q = foldl delta_char (init_state rs) u›
and ‹last_accept rs u b›
shows ‹last_accept rs (u @ v)
(scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs)
q (length u) v b)›
using assms(2-)
proof (induct v arbitrary: q u b)
case (Cons c v)
let ?Q = ‹dfa_states (mode_dfa rs)›
let ?q' = ‹dfa_trans (mode_dfa rs) ! q ! cls c›
let ?X = ‹foldl delta_char (init_state rs) (u @ [c])›
from trans_step[OF assms(1) Cons.prems(1), of c] Cons.prems(2)
have q': ‹?q' < length ?Q› ‹?Q ! ?q' = ?X›
by simp_all
show ?case
proof (cases ‹?q' = dead_state rs›)
case True
with q' have ‹?X = {}›
by (metis dead_state_def nth_index_of_if_less)
have ‹¬ match_rule ρ (u @ w)› if ‹c # v = w @ t› ‹w ≠ []› ‹ρ ∈ set rs› for w t ρ
proof -
from that(1,2) obtain w' where ‹w = c # w'›
by (cases w) auto
with ‹?X = {}› have ‹acc (foldl delta_char (init_state rs) (u @ w)) = None›
by (simp add: acc_def)
with ‹w ≠ []› ‹ρ ∈ set rs› show ?thesis
using no_match_iff_acc_None[of ‹u @ w› rs] by simp
qed
then have ‹last_accept rs (u @ c # v) b›
by (rule last_accept_append[OF Cons.prems(3)])
with True show ?thesis
by simp
next
case False
let ?b' = ‹case dfa_accept (mode_dfa rs) ! ?q' of None ⇒ b | Some i ⇒ Some (i, Suc (length u))›
have ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X›
using q' by (simp add: dfa_accept_eq mode_dfa_def)
have ‹last_accept rs (u @ [c]) ?b'›
proof (cases ‹acc ?X›)
case None
then have ‹¬ match_rule ρ (u @ [c])› if ‹ρ ∈ set rs› for ρ
using no_match_iff_acc_None[of ‹u @ [c]› rs] that by simp
then have ‹last_accept rs (u @ [c]) b›
by (intro last_accept_append[OF Cons.prems(3)]) (auto simp: Cons_eq_append_conv)
with None ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X› show ?thesis
by simp
next
case (Some i)
then have ‹first_token rs i (u @ [c]) (u @ [c])›
by (intro first_token_self_if_acc) simp_all
with Some ‹dfa_accept (mode_dfa rs) ! ?q' = acc ?X› show ?thesis
by (simp add: last_accept_def)
qed
from Cons.hyps[OF q'(1) q'(2) this] False show ?thesis
by (simp add: Let_def)
qed
qed simp
lemma last_accept_scan:
assumes ‹minterm_classifier rs cls›
shows ‹last_accept rs s
(scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs) 0 0 s None)›
proof -
have ‹0 < length (dfa_states (mode_dfa rs))›
‹dfa_states (mode_dfa rs) ! 0 = foldl delta_char (init_state rs) []›
using dfa_run_correct[of rs ‹[]›] by (simp_all add: dfa_run_def)
from scan_last_accept[OF assms this last_accept_Nil, of s] show ?thesis
by simp
qed
lemma run_dfa_sound:
assumes ‹minterm_classifier rs cls› ‹run_dfa rs cls s = Some (i, p, rest)›
shows ‹first_token rs i p s ∧ s = p @ rest›
proof -
from assms(2) obtain n where
‹scan (dfa_trans (mode_dfa rs)) (dfa_accept (mode_dfa rs)) cls (dead_state rs) 0 0 s None =
Some (i, n)› ‹p = take n s› ‹rest = drop n s›
by (auto simp: run_dfa_def run_tables_def)
with last_accept_scan[OF assms(1), of s] show ?thesis
by (simp add: last_accept_def)
qed
lemma run_dfa_None_no_first_token:
assumes ‹minterm_classifier rs cls› ‹run_dfa rs cls s = None›
shows ‹¬ first_token rs i p s›
proof
assume ‹first_token rs i p s›
then obtain u ρ where ‹s = p @ u› ‹ρ ∈ set rs› ‹match_rule ρ p›
by (blast dest: first_token_max_pref max_prefD)
moreover from assms have
‹last_accept rs s None›
using last_accept_scan[OF assms(1), of s] by (simp add: run_dfa_def run_tables_def)
ultimately show False
by (auto simp: last_accept_def)
qed
section ‹Surface theorems›
text ‹With any classifier into the minterms of the mode, the runner returns exactly the
winning rule and lexeme of \<^const>‹first_token›, and fails exactly when no rule
matches a nonempty prefix. For one step, this is Verbatim's soundness and completeness
\<^cite>‹‹Sects.~V-A, V-C› in "egolf2021-verbatim-verified-lexer"›, which Verbatim
proves for derivatives, not for a DFA:›
theorem run_dfa_Some_iff:
assumes ‹minterm_classifier rs cls›
shows ‹run_dfa rs cls s = Some (i, p, rest) ⟷ first_token rs i p s ∧ s = p @ rest›
proof
assume ‹run_dfa rs cls s = Some (i, p, rest)›
with assms show ‹first_token rs i p s ∧ s = p @ rest›
by (rule run_dfa_sound)
next
assume ‹first_token rs i p s ∧ s = p @ rest›
then have ‹first_token rs i p s› ‹s = p @ rest›
by blast+
show ‹run_dfa rs cls s = Some (i, p, rest)›
proof (cases ‹run_dfa rs cls s›)
case None
with assms ‹first_token rs i p s› show ?thesis
by (blast dest: run_dfa_None_no_first_token)
next
case (Some x)
then obtain i' p' rest' where ‹run_dfa rs cls s = Some (i', p', rest')›
by (cases x) auto
moreover from run_dfa_sound[OF assms this] have ‹first_token rs i' p' s› ‹s = p' @ rest'›
by blast+
moreover from first_token_deterministic[OF ‹first_token rs i' p' s› ‹first_token rs i p s›]
have ‹i' = i› ‹p' = p›
by simp_all
ultimately show ?thesis
using ‹s = p @ rest› by simp
qed
qed
theorem run_dfa_None_iff:
assumes ‹minterm_classifier rs cls›
shows ‹run_dfa rs cls s = None ⟷ (∄i p. first_token rs i p s)›
proof
assume ‹run_dfa rs cls s = None›
with assms show ‹∄i p. first_token rs i p s›
by (blast dest: run_dfa_None_no_first_token)
next
assume ‹∄i p. first_token rs i p s›
then show ‹run_dfa rs cls s = None›
using run_dfa_Some_iff[OF assms] by (cases ‹run_dfa rs cls s›) auto
qed
end
end