Theory TIGER_Lexer.TIGER_Regex
theory TIGER_Regex
imports "Regular-Sets.Derivatives"
begin
section ‹Symbolic regular expressions›
text ‹A symbolic regular expression is a \<^typ>‹'p rexp› of \<^session>‹Regular-Sets› whose
atoms are syntactic predicates. A denotation ‹sem :: 'p ⇒ 'ch ⇒ bool› says which
characters a predicate holds for \<^cite>‹‹Sect.~2› in
"dantoni2014-minimization-symbolic-automata"›. We reuse the datatype rather than copy it
(its \<^const>‹nullable›, \<^const>‹atoms› and partial derivatives then apply unchanged).
Predicates are syntax, not functions (the generator compares regexes and decides
satisfiability of predicates, and functions allow neither). The locale ‹symbolic› fixes
‹sem›, and ‹'ch› carries no type class. Definitions that need no denotation stay
outside it.
The language \<^const>‹lang› reads an atom as the characters its denotation holds for.
This theory defines the derivative \<^cite>‹"brzozowski1964-derivatives-regular-expressions"›,
the partial derivative \<^cite>‹"antimirov1996-partial-derivatives"› by a character and by a
predicate class, proves both language-correct and proves that the partial derivatives
of a regex are finitely many.›
abbreviation Pred :: ‹'p ⇒ 'p rexp› where
‹Pred ≡ Atom›
locale symbolic =
fixes sem :: ‹'p ⇒ 'ch ⇒ bool›
begin
primrec lang :: ‹'p rexp ⇒ 'ch lang› where
‹lang Zero = {}›
| ‹lang One = {[]}›
| ‹lang (Pred p) = {[c] | c. sem p c}›
| ‹lang (Plus r s) = lang r ∪ lang s›
| ‹lang (Times r s) = lang r @@ lang s›
| ‹lang (Star r) = star (lang r)›
text ‹\<^const>‹Regular_Exp.lang› would read \<^term>‹Pred p› as the one-letter word ‹[p]›
over the alphabet of predicates. \<^const>‹lang› is the symbolic reading.›
lemma nullable_iff: ‹nullable r ⟷ [] ∈ lang r›
by (induct r) (auto simp: conc_def)
subsection ‹Derivative›
primrec deriv :: ‹'ch ⇒ 'p rexp ⇒ 'p rexp› where
‹deriv c Zero = Zero›
| ‹deriv c One = Zero›
| ‹deriv c (Pred p) = (if sem p c then One else Zero)›
| ‹deriv c (Plus r s) = Plus (deriv c r) (deriv c s)›
| ‹deriv c (Times r s) =
(if nullable r then Plus (Times (deriv c r) s) (deriv c s)
else Times (deriv c r) s)›
| ‹deriv c (Star r) = Times (deriv c r) (Star r)›
text ‹The derivative of ‹r› by ‹c› denotes the words ‹w› with ‹c # w ∈ lang r›
\<^cite>‹‹Thm.~3.1› in "brzozowski1964-derivatives-regular-expressions"›:›
lemma Deriv_Pred[simp]: ‹Deriv c {[d] | d. P d} = (if P c then {[]} else {})›
by (auto simp: Deriv_def)
lemma lang_deriv: ‹lang (deriv c r) = Deriv c (lang r)›
by (induct r) (simp_all add: nullable_iff)
subsection ‹Partial derivatives›
primrec pderiv :: ‹'ch ⇒ 'p rexp ⇒ 'p rexp set› where
‹pderiv c Zero = {}›
| ‹pderiv c One = {}›
| ‹pderiv c (Pred p) = (if sem p c then {One} else {})›
| ‹pderiv c (Plus r s) = pderiv c r ∪ pderiv c s›
| ‹pderiv c (Times r s) =
(if nullable r then Timess (pderiv c r) s ∪ pderiv c s
else Timess (pderiv c r) s)›
| ‹pderiv c (Star r) = Timess (pderiv c r) (Star r)›
primrec pderivs :: ‹'ch list ⇒ 'p rexp ⇒ 'p rexp set› where
‹pderivs [] r = {r}›
| ‹pderivs (c # w) r = ⋃ (pderivs w ` pderiv c r)›
text ‹The partial derivatives of ‹r› by ‹c› are a set of regexes whose union denotes
the derivative \<^cite>‹‹Def.~2.8, Prop.~2.10› in "antimirov1996-partial-derivatives"›.
The proofs follow \<^session>‹Regular-Sets› (‹Derivatives›, @{thm [source]
Derivatives.Deriv_pderiv} and @{thm [source] Derivatives.Derivs_pderivs}):›
lemma Deriv_pderiv: ‹Deriv c (lang r) = ⋃ (lang ` pderiv c r)›
by (induct r) (auto simp: nullable_iff conc_UNION_distrib)
lemma Derivs_pderivs: ‹Derivs w (lang r) = ⋃ (lang ` pderivs w r)›
proof (induct w arbitrary: r)
case (Cons c w)
have ‹Derivs w (⋃ (lang ` pderiv c r)) =
(⋃r' ∈ pderiv c r. Derivs w (lang r'))›
by (auto simp: Derivs_def)
then show ?case
by (simp add: Deriv_pderiv Cons)
qed simp
end
subsection ‹Partial derivatives by a predicate class›
text ‹A class is a set ‹S› of predicates, read as the characters for which exactly the
predicates in ‹S› hold (so it needs no denotation). The partial derivative by a class
treats every atom in ‹S› as true \<^cite>‹‹Sect.~5.2, Thm.~12› in "keil2014-symbolic-regex-inequalities"›:›
primrec pderiv_cls :: ‹'p set ⇒ 'p rexp ⇒ 'p rexp set› where
‹pderiv_cls S Zero = {}›
| ‹pderiv_cls S One = {}›
| ‹pderiv_cls S (Pred p) = (if p ∈ S then {One} else {})›
| ‹pderiv_cls S (Plus r s) = pderiv_cls S r ∪ pderiv_cls S s›
| ‹pderiv_cls S (Times r s) =
(if nullable r then Timess (pderiv_cls S r) s ∪ pderiv_cls S s
else Timess (pderiv_cls S r) s)›
| ‹pderiv_cls S (Star r) = Timess (pderiv_cls S r) (Star r)›
primrec pderivs_cls :: ‹'p set list ⇒ 'p rexp ⇒ 'p rexp set› where
‹pderivs_cls [] r = {r}›
| ‹pderivs_cls (S # Ss) r = ⋃ (pderivs_cls Ss ` pderiv_cls S r)›
text ‹The partial derivative by a class is a union of \<^session>‹Regular-Sets› partial
derivatives over the alphabet of predicates. This lifting lemma is the bridge to its
finiteness theorem:›
lemma pderiv_cls_eq_UN: ‹pderiv_cls S r = (⋃p ∈ S. Derivatives.pderiv p r)›
by (induct r) auto
lemma pderiv_empty_if_notin_atoms: ‹p ∉ atoms r ⟹ Derivatives.pderiv p r = {}›
by (induct r) simp_all
lemma atoms_if_pderiv: ‹x ∈ Derivatives.pderiv p r ⟹ p ∈ atoms r›
by (metis empty_iff pderiv_empty_if_notin_atoms)
lemma pderiv_cls_Int_atoms: ‹pderiv_cls (S ∩ atoms r) r = pderiv_cls S r›
unfolding pderiv_cls_eq_UN by (auto dest: atoms_if_pderiv)
context symbolic
begin
definition sig :: ‹'p rexp ⇒ 'ch ⇒ 'p set› where
‹sig r c = {p ∈ atoms r. sem p c}›
text ‹The signature of ‹c› in ‹r› is the set of atoms of ‹r› that hold for ‹c›:›
lemma pderiv_eq_pderiv_cls: ‹pderiv c r = pderiv_cls {p. sem p c} r›
by (induct r) simp_all
text ‹Characters with the same signature have the same partial derivatives
\<^cite>‹‹Thm.~4.2› in "owens2009-regex-derivatives-reexamined"›, so the partial
derivative by a class is the partial derivative by any of its characters:›
lemma pderiv_eq_pderiv_cls_sig: ‹pderiv c r = pderiv_cls (sig r c) r›
proof -
have ‹sig r c = {p. sem p c} ∩ atoms r›
by (auto simp: sig_def)
then show ?thesis
by (simp add: pderiv_eq_pderiv_cls pderiv_cls_Int_atoms)
qed
lemma pderiv_eq_if_sig_eq: ‹sig r c = sig r d ⟹ pderiv c r = pderiv d r›
by (simp add: pderiv_eq_pderiv_cls_sig)
lemma Deriv_pderiv_cls:
‹sig r c = S ∩ atoms r ⟹ Deriv c (lang r) = ⋃ (lang ` pderiv_cls S r)›
by (simp add: Deriv_pderiv pderiv_eq_pderiv_cls_sig pderiv_cls_Int_atoms)
lemma pderivs_eq_pderivs_cls: ‹pderivs w r = pderivs_cls (map (λc. {p. sem p c}) w) r›
by (induct w arbitrary: r) (simp_all add: pderiv_eq_pderiv_cls)
end
subsection ‹Finiteness›
definition pderiv_closure :: ‹'p rexp ⇒ 'p rexp set› where
‹pderiv_closure r = (⋃Ss. pderivs_cls Ss r)›
text ‹The closure of ‹r› under partial derivatives by classes contains the partial
derivatives by all words. It is a subset of the \<^session>‹Regular-Sets› partial
derivatives of ‹r› over the alphabet of predicates, so @{thm [source]
finite_pderivs_lang} and @{thm [source] card_pderivs_lang_UNIV_le_awidth} apply
unchanged and no proof is copied \<^cite>‹‹Thm.~3.4› in "antimirov1996-partial-derivatives"›:›
lemma pderivs_cls_subset_pderivs_lang: ‹pderivs_cls Ss r ⊆ pderivs_lang UNIV r›
proof (induct Ss arbitrary: r)
case (Cons S Ss)
show ?case
proof
fix x
assume ‹x ∈ pderivs_cls (S # Ss) r›
then obtain p r' where ‹r' ∈ Derivatives.pderiv p r› ‹x ∈ pderivs_cls Ss r'›
by (auto simp: pderiv_cls_eq_UN)
with Cons obtain u where ‹r' ∈ Derivatives.pderiv p r› ‹x ∈ Derivatives.pderivs u r'›
by (auto simp: pderivs_lang_def)
then have ‹x ∈ Derivatives.pderivs (p # u) r›
by auto
then show ‹x ∈ pderivs_lang UNIV r›
unfolding pderivs_lang_def by blast
qed
qed (simp add: pderivs_lang_UNIV)
lemma pderiv_closure_subset_pderivs_lang: ‹pderiv_closure r ⊆ pderivs_lang UNIV r›
using pderivs_cls_subset_pderivs_lang by (fastforce simp: pderiv_closure_def)
lemma finite_pderiv_closure: ‹finite (pderiv_closure r)›
using pderiv_closure_subset_pderivs_lang finite_pderivs_lang by (rule finite_subset)
lemma card_pderiv_closure_le_awidth: ‹card (pderiv_closure r) ≤ awidth r + 1›
using card_mono[OF finite_pderivs_lang pderiv_closure_subset_pderivs_lang]
card_pderivs_lang_UNIV_le_awidth by (rule le_trans)
context symbolic
begin
lemma pderivs_subset_pderiv_closure: ‹pderivs w r ⊆ pderiv_closure r›
by (auto simp: pderiv_closure_def pderivs_eq_pderivs_cls)
lemma finite_pderivs_UNIV: ‹finite (⋃w. pderivs w r)›
by (rule finite_subset[OF UN_least finite_pderiv_closure]) (rule pderivs_subset_pderiv_closure)
end
end