Theory TIGER_Lexer.TIGER_Codepoints
theory TIGER_Codepoints
imports TIGER_Tables "HOL-Library.Code_Target_Nat"
begin
section ‹The codepoint instance›
text ‹Codepoints are natural numbers, and the range is
‹0 .. 0x10FFFF›. Surrogates are in the range: excluding them is the business of the
decoder. As \<^typ>‹nat› is unbounded, character classes are no Boolean algebra on it
(the negation of a class holds of no number above the range). We read a class at the
number clamped to the range instead, so a number above the range lexes as
‹U+10FFFF›, and prove that on an input in range this reading is the plain one
(\<^const>‹in_cls›).
Generated code represents \<^typ>‹nat› by target integers (‹Code_Target_Nat›):
in the default unary representation ‹0x10FFFF› alone has a million constructors.
The lexer ‹cp_lexer› takes the tables of the modes as one array and a
mode index into it, so modes with the same rules share their tables. Its surface
theorems hold for every index under which each mode finds its tables. A spec on
codepoints is read on bytes by ‹char_spec›, which keeps the part of each
class below ‹0x100›.›
subsection ‹Classes read in the range›
locale range_order = discrete_order bot top succ pred
for bot top :: ‹'ch::linorder› and succ pred
begin
definition clamp :: ‹'ch ⇒ 'ch› where
‹clamp c = (if c < bot then bot else if top < c then top else c)›
definition in_clamped :: ‹'ch cls ⇒ 'ch ⇒ bool› where
‹in_clamped p c ⟷ in_cls p (clamp c)›
definition sat_clamped :: ‹'ch cls ⇒ bool› where
‹sat_clamped p ⟷ sat_cls (clip p)›
lemma clamp_in_range: ‹bot ≤ clamp c ∧ clamp c ≤ top›
using bot_le_top by (auto simp: clamp_def)
lemma clamp_id: ‹⟦ bot ≤ c; c ≤ top ⟧ ⟹ clamp c = c›
by (auto simp: clamp_def)
lemma in_clamped_iff: ‹⟦ bot ≤ c; c ≤ top ⟧ ⟹ in_clamped p c ⟷ in_cls p c›
by (simp add: in_clamped_def clamp_id)
text ‹Read in the range, classes form an effective Boolean algebra:›
sublocale eba in_clamped cls_top cls_bot cls_conj cls_disj cls_neg sat_clamped
proof unfold_locales
fix p
show ‹sat_clamped p ⟷ (∃c. in_clamped p c)›
using clamp_in_range clamp_id
by (auto simp: sat_clamped_def in_clamped_def sat_cls_iff in_cls_clip) metis
qed (simp_all add: in_clamped_def clamp_in_range in_cls_top in_cls_bot in_cls_conj in_cls_disj
in_cls_neg)
end
subsection ‹Semantics that agree on the input›
text ‹The judgments read the denotation only at the characters of the input. Two
denotations that agree there give the same lexing:›
lemma star_cong:
assumes ‹⋀w. set w ⊆ A ⟹ w ∈ L ⟷ w ∈ L'› ‹w ∈ star L› ‹set w ⊆ A›
shows ‹w ∈ star L'›
using assms(2,3) by induct (auto simp: assms(1))
lemma conc_cong:
assumes ‹⋀w. set w ⊆ A ⟹ w ∈ L1 ⟷ w ∈ L1'› ‹⋀w. set w ⊆ A ⟹ w ∈ L2 ⟷ w ∈ L2'›
and ‹set w ⊆ A›
shows ‹w ∈ L1 @@ L2 ⟷ w ∈ L1' @@ L2'›
proof
assume ‹w ∈ L1 @@ L2›
then obtain u v where ‹w = u @ v› ‹u ∈ L1› ‹v ∈ L2›
by blast
with assms show ‹w ∈ L1' @@ L2'›
by auto
next
assume ‹w ∈ L1' @@ L2'›
then obtain u v where ‹w = u @ v› ‹u ∈ L1'› ‹v ∈ L2'›
by blast
with assms show ‹w ∈ L1 @@ L2›
by auto
qed
lemma lang_cong:
assumes ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c› ‹set w ⊆ A›
shows ‹w ∈ symbolic.lang sem r ⟷ w ∈ symbolic.lang sem' r›
using assms(2)
proof (induction r arbitrary: w)
case (Atom p)
then show ?case
by (auto simp: assms(1) symbolic.lang.simps)
next
case (Times r1 r2)
then show ?case
using conc_cong[of A ‹symbolic.lang sem r1› ‹symbolic.lang sem' r1›
‹symbolic.lang sem r2› ‹symbolic.lang sem' r2› w]
by (simp add: symbolic.lang.simps)
next
case (Star r)
then show ?case
using star_cong[of A ‹symbolic.lang sem r› ‹symbolic.lang sem' r› w]
star_cong[of A ‹symbolic.lang sem' r› ‹symbolic.lang sem r› w]
by (auto simp: symbolic.lang.simps)
qed (auto simp: symbolic.lang.simps)
text ‹In the rest of this subsection ‹sem› and ‹sem'› agree on ‹A›:›
context
fixes A and sem sem' :: ‹'p ⇒ 'ch ⇒ bool›
assumes agree: ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c›
begin
lemma match_rule_cong:
‹set w ⊆ A ⟹ symbolic.match_rule sem ρ w ⟷ symbolic.match_rule sem' ρ w›
using lang_cong[where A = A and sem = sem and sem' = sem', OF agree]
by (simp add: symbolic.match_rule.simps)
lemma max_pref_cong:
assumes ‹set s ⊆ A›
shows ‹symbolic.max_pref sem (rs :: ('k, 'p, 'ch, 'm) rule list) p s ⟷
symbolic.max_pref sem' rs p s›
proof -
have mr: ‹symbolic.match_rule sem ρ' p' ⟷ symbolic.match_rule sem' ρ' p'›
if ‹s = p' @ u'› for ρ' :: ‹('k, 'p, 'ch, 'm) rule› and p' u'
using match_rule_cong[of p'] that assms by simp
show ?thesis
unfolding symbolic.max_pref.simps by (metis mr)
qed
lemma first_token_cong:
assumes ‹set s ⊆ A›
shows ‹symbolic.first_token sem (rs :: ('k, 'p, 'ch, 'm) rule list) i p s ⟷
symbolic.first_token sem' rs i p s›
proof -
have ‹set p ⊆ A› if ‹∃u. s = p @ u›
using that assms by auto
then have ‹(∃u. s = p @ u) ⟹
symbolic.match_rule sem ρ p ⟷ symbolic.match_rule sem' ρ p›
for ρ :: ‹('k, 'p, 'ch, 'm) rule›
using match_rule_cong by blast
then show ?thesis
using max_pref_cong[OF assms] symbolic.max_prefD[of sem rs p s]
symbolic.max_prefD[of sem' rs p s]
unfolding symbolic.first_token.simps by metis
qed
lemma step_cong:
assumes ‹set s ⊆ A›
shows ‹symbolic.step sem sp st s x ⟷ symbolic.step sem' sp st s x›
by (simp add: symbolic.step.simps first_token_cong[OF assms])
lemma lexes_cong_imp:
assumes ‹symbolic.lexes sem sp is_newline st q s l r st⇩f› ‹set s ⊆ A›
shows ‹symbolic.lexes sem' sp is_newline st q s l r st⇩f›
using assms
proof (induction rule: symbolic.lexes.induct[of sem, consumes 1, case_names stop token trivia])
case (stop st s q)
then have ‹¬ symbolic.step sem' sp st s x› for x
using step_cong[of s sp st x] by blast
then show ?case
by (rule symbolic.lexes_stop)
next
case (token st s k p st' s' q h ts r st⇩f)
from token.hyps(1) token.prems have ‹set s' ⊆ A›
by (auto simp: symbolic.step.simps)
from token.hyps(1) have ‹symbolic.step sem' sp st s (Some k, p, st', s')›
by (simp add: step_cong[OF token.prems])
from this token.IH[OF ‹set s' ⊆ A›] show ?case
by (rule symbolic.lexes_token)
next
case (trivia st s p st' s' q h ts r st⇩f)
from trivia.hyps(1) trivia.prems have ‹set s' ⊆ A›
by (auto simp: symbolic.step.simps)
from trivia.hyps(1) have ‹symbolic.step sem' sp st s (None, p, st', s')›
by (simp add: step_cong[OF trivia.prems])
from this trivia.IH[OF ‹set s' ⊆ A›] show ?case
by (rule symbolic.lexes_trivia)
qed
end
lemma lexes_cong:
assumes ‹⋀p c. c ∈ A ⟹ sem p c = sem' p c› ‹set s ⊆ A›
shows ‹symbolic.lexes sem sp is_newline st q s l r st⇩f ⟷
symbolic.lexes sem' sp is_newline st q s l r st⇩f›
using lexes_cong_imp[of A sem sem'] lexes_cong_imp[of A sem' sem] assms by (metis (no_types))
context range_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 of the clamped character in the minterm table of a mode is a
classifier into its minterms. Above the range it is the class of ‹top›:›
lemma minterm_classifier_class_of_clamp:
‹minterm_classifier rs (λc. class_of (IArray (class_table (mode_minterms rs))) (clamp c))›
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)
have disj: ‹i = j›
if ‹i < length ?M› ‹j < length ?M› ‹in_cls (snd (?M ! i)) d› ‹in_cls (snd (?M ! j)) d›
for i j d
proof -
from that(1,3) wf[of i] have ‹bot ≤ d› ‹d ≤ top›
by (auto simp: wf_cls_def in_range_iff in_cls_iff)
with that minterms_disjoint show ?thesis
by (metis in_clamped_iff mode_minterms_def)
qed
obtain S μ where ‹(S, μ) ∈ set ?M› ‹in_clamped μ 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)) (clamp c)›
by (metis in_set_conv_nth snd_conv in_clamped_def)
from class_of_partition[OF wf disj this]
show ‹class_of (IArray (class_table ?M)) (clamp c) < length ?M ∧
in_clamped (snd (?M ! class_of (IArray (class_table ?M)) (clamp c))) c›
by (simp add: in_clamped_def)
qed
end
subsection ‹The interpretation›