Theory TIGER_Lexer.TIGER_Tables
theory TIGER_Tables
imports TIGER_Driver TIGER_Intervals "HOL-Library.Char_ord" "HOL-Library.IArray"
begin
section ‹Tables by evaluation›
text ‹The generator runs once, at definition time. Its output becomes nullary constants
whose code equations ‹eval› produces, and the run-time lexer only indexes them
\<^cite>‹‹Sect.~17› in "paxson2026-flex-manual"›. The transition and acceptance
tables are immutable arrays (\<^typ>‹'a iarray›). On the interval instance a character
finds its minterm by binary search in the intervals of all minterms, sorted by their
lower ends.
The correctness of a table is that of its generator, instantiated: the runner on
arrays is \<^const>‹eba.run_dfa› and the classifier is a
\<^const>‹eba.minterm_classifier›, for every spec. No proof looks at a table value.
The byte instance of the interval algebra is interpreted here, after the generator
(an interpretation carries only the locale constants defined before it).›
subsection ‹The runner on arrays›
text ‹The scan of \<^const>‹scan› with array lookups:›
fun scan_ia ::
‹nat iarray iarray ⇒ nat option iarray ⇒ ('ch ⇒ nat) ⇒ nat ⇒ nat ⇒ nat ⇒
'ch list ⇒ (nat × nat) option ⇒ (nat × nat) option›
where
‹scan_ia T A cls d q n [] b = b›
| ‹scan_ia T A cls d q n (c # v) b =
(let q' = T !! q !! cls c in
if q' = d then b
else scan_ia T A cls d q' (Suc n) v (case A !! q' of None ⇒ b | Some i ⇒ Some (i, Suc n)))›
definition run_tables_ia ::
‹nat iarray iarray ⇒ nat option iarray ⇒ ('ch ⇒ nat) ⇒ nat ⇒ 'ch list ⇒
(nat × 'ch list × 'ch list) option›
where
‹run_tables_ia T A cls d s =
map_option (λ(i, n). (i, take n s, drop n s)) (scan_ia T A cls d 0 0 s None)›
text ‹The two scans agree as long as no transition leaves the table:›
lemma scan_ia_eq_scan:
assumes ‹⋀q c. q < length T ⟹ T ! q ! cls c < length T› ‹q < length T›
shows ‹scan_ia (IArray (map IArray T)) (IArray A) cls d q n s b = scan T A cls d q n s b›
using assms(2) by (induct s arbitrary: q n b) (simp_all add: Let_def assms(1))
context eba
begin
lemma run_tables_ia_eq_run_dfa:
assumes ‹minterm_classifier rs cls›
shows ‹run_tables_ia (IArray (map IArray (dfa_trans (mode_dfa rs))))
(IArray (dfa_accept (mode_dfa rs))) cls (dead_state rs) s = run_dfa rs cls s›
proof -
let ?T = ‹dfa_trans (mode_dfa rs)›
let ?A = ‹dfa_accept (mode_dfa rs)›
have len: ‹length ?T = length (dfa_states (mode_dfa rs))›
by (simp add: mode_dfa_def length_dfa_trans)
have ‹0 < length (dfa_states (mode_dfa rs))›
using dfa_run_correct[of rs ‹[]›] by (simp add: dfa_run_def)
then have ‹scan_ia (IArray (map IArray ?T)) (IArray ?A) cls (dead_state rs) 0 0 s None =
scan ?T ?A cls (dead_state rs) 0 0 s None›
by (intro scan_ia_eq_scan) (use trans_step[OF assms] len in auto)
then show ?thesis
by (simp add: run_tables_ia_def run_dfa_def run_tables_def)
qed
end
subsection ‹Binary search›
text ‹In an array sorted by first components, the search finds the last entry between
‹l› and ‹h› whose first component is at most ‹c›:›
function bsearch :: ‹('a::linorder × 'b) iarray ⇒ 'a ⇒ nat ⇒ nat ⇒ nat› where
‹bsearch t c l h =
(if Suc l < h then
if fst (t !! ((l + h) div 2)) ≤ c then bsearch t c ((l + h) div 2) h
else bsearch t c l ((l + h) div 2)
else l)›
by pat_completeness auto
termination
by (relation ‹measure (λ(t, c, l, h). h - l)›) auto
declare bsearch.simps[simp del]
lemma bsearch:
assumes ‹sorted (map fst (IArray.list_of t))› ‹l < h› ‹h ≤ IArray.length t›
and ‹fst (t !! l) ≤ c›
shows ‹l ≤ bsearch t c l h ∧ bsearch t c l h < h ∧ fst (t !! bsearch t c l h) ≤ c ∧
(∀j. bsearch t c l h < j ⟶ j < h ⟶ c < fst (t !! j))›
using assms(2-)
proof (induction ‹h - l› arbitrary: l h rule: less_induct)
case less
let ?m = ‹(l + h) div 2›
show ?case
proof (cases ‹Suc l < h›)
case False
then have ‹bsearch t c l h = l›
by (simp add: bsearch.simps)
with less.prems False show ?thesis
by auto
next
case True
then have m: ‹l < ?m› ‹?m < h›
by presburger+
then have d: ‹h - ?m < h - l› ‹?m - l < h - l›
by linarith+
show ?thesis
proof (cases ‹fst (t !! ?m) ≤ c›)
case True
with less.hyps[of h ?m] less.prems m d have ‹?m ≤ bsearch t c ?m h ∧
bsearch t c ?m h < h ∧ fst (t !! bsearch t c ?m h) ≤ c ∧
(∀j. bsearch t c ?m h < j ⟶ j < h ⟶ c < fst (t !! j))›
by simp
moreover from True ‹Suc l < h› have ‹bsearch t c l h = bsearch t c ?m h›
by (subst bsearch.simps) simp
ultimately show ?thesis
using m by auto
next
case False
have ‹c < fst (t !! j)› if ‹?m ≤ j› ‹j < h› for j
using False sorted_nth_mono[OF assms(1) that(1)] that(2) less.prems by fastforce
moreover from False ‹Suc l < h› have ‹bsearch t c l h = bsearch t c l ?m›
by (subst bsearch.simps) simp
ultimately show ?thesis
using less.hyps[of ?m l] less.prems m d by (simp, meson not_le)
qed
qed
qed
subsection ‹The minterm table of the interval instance›
text ‹The minterm table lists every interval of every minterm with the number of its
minterm, sorted by lower ends. A character looks up the last interval starting at or
below it:›
definition class_table :: ‹('s × 'ch::linorder cls) list ⇒ ('ch × 'ch × nat) list› where
‹class_table M = sort_key fst
(concat (map (λk. map (λ(l, h). (l, h, k)) (snd (M ! k))) [0 ..< length M]))›
definition class_of :: ‹('ch::linorder × 'ch × nat) iarray ⇒ 'ch ⇒ nat› where
‹class_of t c = snd (snd (t !! bsearch t c 0 (IArray.length t)))›
lemma mem_class_table:
‹x ∈ set (class_table M) ⟷
(∃k l h. k < length M ∧ x = (l, h, k) ∧ (l, h) ∈ set (snd (M ! k)))›
by (force simp: class_table_def)
text ‹A list of well-formed, pairwise disjoint classes is a partition of the characters
it covers. The lookup in its table finds the class of each character it covers:›
context discrete_order
begin
text ‹Two different intervals of a separated class share no character:›
lemma separated_disjoint:
assumes ‹separated p› ‹x ∈ set p› ‹y ∈ set p› ‹x ≠ y›
and ‹fst x ≤ c› ‹c ≤ snd x› ‹fst y ≤ c› ‹c ≤ snd y›
shows False
proof -
have sep: ‹snd (p ! i) < top ∧ succ (snd (p ! i)) < fst (p ! j)›
if ‹i < j› ‹j < length p› for i j
using assms(1) that by (simp add: separated_def sorted_wrt_iff_nth_less)
have *: ‹False› if ‹u ∈ set p› ‹w ∈ set p› ‹u ≠ w› ‹c ≤ snd u› ‹fst w ≤ c›
‹index_of p u < index_of p w› for u w
proof -
from that have ‹snd u < top› ‹succ (snd u) < fst w›
using sep[of ‹index_of p u› ‹index_of p w›] index_of_less[of w p] nth_index_of[of u p]
nth_index_of[of w p]
by simp_all
with less_succ[of ‹snd u›] that(4,5) show False
by (meson le_less_trans less_le_not_le order.strict_trans)
qed
have ‹index_of p x ≠ index_of p y›
using assms(2-4) by (metis nth_index_of)
then have ‹index_of p x < index_of p y ∨ index_of p y < index_of p x›
by (rule neq_iff[THEN iffD1])
with *[of x y] *[of y x] assms(2-8) show False
by blast
qed
text ‹The intervals of different entries of the table of a partition share no
character, and each entry is nonempty:›
lemma class_table_disjoint:
assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
and disj: ‹⋀i j c. ⟦ i < length M; j < length M; in_cls (snd (M ! i)) c;
in_cls (snd (M ! j)) c ⟧ ⟹ i = j›
and ‹x ∈ set (class_table M)› ‹y ∈ set (class_table M)›
and ‹fst x ≤ c› ‹c ≤ fst (snd x)› ‹fst y ≤ c› ‹c ≤ fst (snd y)›
shows ‹x = y›
proof -
from assms(3) obtain k l h where x: ‹k < length M› ‹x = (l, h, k)› ‹(l, h) ∈ set (snd (M ! k))›
by (auto simp: mem_class_table)
from assms(4) obtain k' l' h' where
y: ‹k' < length M› ‹y = (l', h', k')› ‹(l', h') ∈ set (snd (M ! k'))›
by (auto simp: mem_class_table)
from x y assms(5-8) have ‹in_cls (snd (M ! k)) c› ‹in_cls (snd (M ! k')) c›
by (auto simp: in_cls_iff intro: bexI[rotated])
with disj x(1) y(1) have ‹k' = k›
by blast
from wf[OF x(1)] have ‹separated (snd (M ! k))›
by (simp add: wf_cls_def)
with separated_disjoint[of ‹snd (M ! k)› ‹(l, h)› ‹(l', h')› c] x y ‹k' = k› assms(5-8)
show ‹x = y›
by fastforce
qed
lemma class_table_nonempty:
assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
and ‹x ∈ set (class_table M)›
shows ‹fst x ≤ fst (snd x)›
proof -
from assms(2) obtain k l h where
‹k < length M› ‹x = (l, h, k)› ‹(l, h) ∈ set (snd (M ! k))›
by (auto simp: mem_class_table)
with wf[of k] show ?thesis
by (auto simp: wf_cls_def in_range_iff)
qed
lemma class_of_partition:
assumes wf: ‹⋀k. k < length M ⟹ wf_cls (snd (M ! k))›
and disj: ‹⋀i j c. ⟦ i < length M; j < length M; in_cls (snd (M ! i)) c;
in_cls (snd (M ! j)) c ⟧ ⟹ i = j›
and k: ‹k < length M› ‹in_cls (snd (M ! k)) c›
shows ‹class_of (IArray (class_table M)) c < length M ∧
in_cls (snd (M ! class_of (IArray (class_table M)) c)) c›
proof -
let ?xs = ‹class_table M›
let ?i = ‹bsearch (IArray ?xs) c 0 (length ?xs)›
have sorted: ‹sorted (map fst ?xs)›
by (simp add: class_table_def)
from k obtain l h where ‹(l, h) ∈ set (snd (M ! k))› ‹l ≤ c› ‹c ≤ h›
by (auto simp: in_cls_iff)
with k(1) obtain j where j: ‹j < length ?xs› ‹?xs ! j = (l, h, k)›
by (metis in_set_conv_nth mem_class_table)
moreover from j(1) have len: ‹0 < length ?xs›
by linarith
moreover have ‹fst (?xs ! 0) ≤ c›
using sorted_nth_mono[OF sorted, of 0 j] j ‹l ≤ c› len by simp
ultimately
have i: ‹?i < length ?xs› ‹fst (?xs ! ?i) ≤ c›
‹∀j'. ?i < j' ⟶ j' < length ?xs ⟶ c < fst (?xs ! j')›
using bsearch[of ‹IArray ?xs› 0 ‹length ?xs› c] sorted by auto
with j ‹l ≤ c› have ‹j ≤ ?i›
by (metis fst_conv not_le)
with sorted_nth_mono[OF sorted this] i(1) j have ‹l ≤ fst (?xs ! ?i)›
by simp
moreover have ‹fst (?xs ! ?i) ≤ fst (snd (?xs ! ?i))›
using class_table_nonempty[OF wf] i(1) by simp
ultimately have ‹?xs ! ?i = ?xs ! j›
using class_table_disjoint[OF wf disj, where x = ‹?xs ! ?i› and y = ‹?xs ! j›
and c = ‹fst (?xs ! ?i)›] i(1,2) j nth_mem[OF j(1)] order.trans[OF i(2) ‹c ≤ h›]
by simp
with j k show ?thesis
by (simp add: class_of_def)
qed
end
context bounded_discrete_order
begin
lemma wf_minterms: ‹(S, μ) ∈ set (minterms P) ⟹ wf_cls μ›
by (induct P arbitrary: S μ) (auto simp: wf_top wf_conj)
text ‹The lookup in the minterm table of a mode is a classifier into its minterms:›
lemma minterm_classifier_class_of:
‹minterm_classifier rs (class_of (IArray (class_table (mode_minterms rs))))›
unfolding minterm_classifier_def
proof
fix c
let ?M = ‹mode_minterms rs›
have wf: ‹wf_cls (snd (?M ! k))› if ‹k < length ?M› for k
using wf_minterms nth_mem[OF that] by (metis mode_minterms_def prod.collapse)
obtain S μ where ‹(S, μ) ∈ set ?M› ‹in_cls μ c›
using minterms_cover[of ‹mode_atoms rs› c] by (auto simp: mode_minterms_def)
then obtain k where ‹k < length ?M› ‹in_cls (snd (?M ! k)) c›
by (metis in_set_conv_nth snd_conv)
from class_of_partition[OF wf _ this] minterms_disjoint
show ‹class_of (IArray (class_table ?M)) c < length ?M ∧
in_cls (snd (?M ! class_of (IArray (class_table ?M)) c)) c›
by (metis mode_minterms_def)
qed
end
subsection ‹The byte instance›
text ‹Bytes are the first instance. The interpretation follows the generator, so it
carries the generator's constants (‹char_mode_dfa›) and theorems.›
lemma of_char_le_255: ‹of_char c ≤ (255::nat)›
using nat_of_char_less_256[of c] by linarith
lemma of_char_minus_mod: ‹(of_char c - Suc 0) mod 256 = (of_char c - Suc 0 :: nat)›
by (simp add: less_imp_diff_less)
definition char_succ :: ‹char ⇒ char› where
‹char_succ c = char_of (Suc (of_char c))›
definition char_pred :: ‹char ⇒ char› where
‹char_pred c = char_of (of_char c - 1 :: nat)›
text ‹Bytes are a bounded discrete order:›