Theory LR_Simple
theory LR_Simple
imports LR_Det "HOL-Library.IArray"
begin
section ‹A table-driven driver for grammars without layout annotations›
text ‹
For a grammar whose relations are all \<^const>‹Any› (\<^const>‹ii›), the
indentation sets of the set-anchored driver carry no information beyond
whether they are empty: every set is empty or contains the start
indentation. Such a grammar is an ordinary context-free grammar: Adams
encodes one by giving every symbol the unconstrained relation (\<^const>‹Any›)
\<^cite>‹‹Sect.~4› in "adams2013"›. The live items of a frame are then exactly those of the state of
the precise automaton \<^const>‹pr0_states› the driver tracks, and the
driver's choices are read off its index. This theory defines a driver over
the index stack alone and proves that it computes the same result as
\<^const>‹dparse›. It is the LR parser of DeRemer and Pennello
\<^cite>‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›: a stack of automaton states and
tables for the transition and reduce functions.
›
subsection ‹Anchor sets are empty or contain the start indentation›
definition anch_set :: ‹nat ⇒ indrep ⇒ bool› where
‹anch_set i0 R ⟷ irep_set R = {} ∨ i0 ∈ irep_set R›
definition anch_items :: ‹nat ⇒ ('n, 't) xitem list ⇒ bool› where
‹anch_items i0 xs ⟷ (∀(pr, m, R) ∈ set xs. anch_set i0 R)›
text ‹The relations in the productions of the items: \<^const>‹Any›, or
\<^const>‹Eq› on a nonterminal (the start production).›
definition rel_ok :: ‹irel ⇒ ('n, 't) sym ⇒ bool› where
‹rel_ok r X ⟷ r = Any ∨ (r = Eq ∧ (∃B. X = Nt B))›
definition anns_ok :: ‹('n, 't) xitem list ⇒ bool› where
‹anns_ok xs ⟷ (∀(pr, m, R) ∈ set xs. ∀k < length (snd pr).
rel_ok (snd (snd pr ! k)) (fst (snd pr ! k)))›
lemma rel_okD: ‹rel_ok r X ⟹ r = Any ∨ r = Eq›
unfolding rel_ok_def by blast
lemma ii_rels:
assumes ‹ii G› and ‹pr ∈ set (iprods G)› and ‹k < length (snd pr)›
shows ‹snd (snd pr ! k) = Any›
using assms unfolding ii_def by (cases pr) (auto simp: list_all_iff)
lemma anch_set_union:
‹anch_set i0 R⇩1 ⟹ anch_set i0 R⇩2 ⟹ anch_set i0 (irep_union R⇩1 R⇩2)›
unfolding anch_set_def by auto
lemma anch_set_img:
‹anch_set i0 R ⟹ r = Any ∨ r = Eq ⟹ anch_set i0 (irep_img r R)›
unfolding anch_set_def by auto
lemma anch_set_fold_xcontrib:
assumes ‹anch_set i0 acc›
and ‹⋀A rhs m R. ((A, rhs), m, R) ∈ set items ⟹
anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
shows ‹anch_set i0 (fold (xcontrib pr) items acc)›
using assms
proof (induction items arbitrary: acc)
case (Cons it items)
obtain A rhs m R where it: ‹it = ((A, rhs), m, R)› by (cases it) auto
have ok: ‹anch_set i0 R› ‹∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq›
using Cons.prems(2)[of A rhs m R] it by auto
have c: ‹anch_set i0 (xcontrib pr it acc)›
using ok Cons.prems(1) unfolding it
by (auto intro!: anch_set_union anch_set_img)
have h: ‹anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
if ‹((A, rhs), m, R) ∈ set items› for A rhs m R
using Cons.prems(2)[of A rhs m R] that by simp
show ?case using Cons.IH[OF c h] by simp
qed simp
lemma xiter_anch:
assumes ii: ‹ii G› and kern: ‹anch_items i0 xs› and anns: ‹anns_ok xs›
shows ‹p < length (iprods G) ⟹ anch_set i0 (xiter G xs t ! p)›
proof (induction t arbitrary: p)
case 0
then show ?case by (simp add: anch_set_def)
next
case (Suc t)
have len: ‹length (xiter G xs t) = length (iprods G)› by simp
show ?case
unfolding xiter.simps xround_nth[OF len Suc.prems]
proof (rule anch_set_fold_xcontrib)
show ‹anch_set i0 (xiter G xs t ! p)› by (rule Suc.IH[OF Suc.prems])
next
fix A rhs m R assume mem: ‹((A, rhs), m, R) ∈ set (xslots G xs (xiter G xs t))›
show ‹anch_set i0 R ∧ (∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq)›
using mem
proof (rule xslots_memE)
assume mem: ‹((A, rhs), m, R) ∈ set xs›
have ‹anch_set i0 R› using kern mem unfolding anch_items_def by fastforce
moreover have ‹∀k < length rhs. snd (rhs ! k) = Any ∨ snd (rhs ! k) = Eq›
using anns mem rel_okD unfolding anns_ok_def by fastforce
ultimately show ?thesis by blast
next
fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs t)›
and eq: ‹((A, rhs), m, R) = (iprods G ! q, 0, xiter G xs t ! q)›
have pr: ‹(A, rhs) ∈ set (iprods G)› using q eq by (metis nth_mem prod.inject)
have ‹R = xiter G xs t ! q› using eq by simp
then have ‹anch_set i0 R› using Suc.IH[OF q] by simp
moreover have ‹∀k < length rhs. snd (rhs ! k) = Any›
using ii_rels[OF ii pr] by simp
ultimately show ?thesis by simp
qed
qed
qed
lemma xclosure_auto_anch:
assumes ii: ‹ii G› and kern: ‹anch_items i0 xs› and anns: ‹anns_ok xs›
shows ‹anch_items i0 (xclosure_auto G xs)›
unfolding anch_items_def
proof (intro ballI, clarify)
fix pr m R assume mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)›
then have ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
unfolding xclosure_auto_def xclosure_def .
then show ‹anch_set i0 R›
proof (rule xslots_memE)
assume ‹(pr, m, R) ∈ set xs›
then show ?thesis using kern unfolding anch_items_def by fastforce
next
fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs (xfuel G xs))›
and ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs (xfuel G xs) ! q)›
then show ?thesis using xiter_anch[OF ii kern anns q] by simp
qed
qed
lemma xclosure_auto_anns_mem:
assumes ii: ‹ii G› and anns: ‹anns_ok xs›
and mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)› and k: ‹k < length (snd pr)›
shows ‹rel_ok (snd (snd pr ! k)) (fst (snd pr ! k))›
proof -
have mem': ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
using mem unfolding xclosure_auto_def xclosure_def .
show ?thesis
using mem'
proof (rule xslots_memE)
assume ‹(pr, m, R) ∈ set xs›
then show ?thesis using anns k unfolding anns_ok_def by fastforce
next
fix q assume q: ‹q < length (iprods G)› and ‹q < length (xiter G xs (xfuel G xs))›
and eq: ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs (xfuel G xs) ! q)›
have ‹pr ∈ set (iprods G)› using q eq by simp
then show ?thesis using ii_rels[OF ii _ k] by (simp add: rel_ok_def)
qed
qed
lemma xclosure_auto_anns:
assumes ii: ‹ii G› and anns: ‹anns_ok xs›
shows ‹anns_ok (xclosure_auto G xs)›
unfolding anns_ok_def using xclosure_auto_anns_mem[OF ii anns] by fast
subsection ‹The live part of a closure is the reachable closure›
lemma irep_img_nonempty: ‹irep_set R ≠ {} ⟹ irep_set (irep_img r R) ≠ {}›
proof -
assume ‹irep_set R ≠ {}›
then obtain i where i: ‹i ∈ irep_set R› by blast
have ‹∃j. irel_sat r j i› by (cases r) (auto intro: exI[of _ ‹Suc i›] exI[of _ i])
then show ?thesis using i by auto
qed
lemma creach_funpow_live:
assumes stable: ‹xstable G xs cls› and len: ‹length cls = length (iprods G)›
and kern: ‹set s ⊆ lcore xs›
shows ‹set ((creach_step G ^^ k) s) ⊆ lcore (xslots G xs cls)›
proof (induction k)
case 0
have ‹lcore xs ⊆ lcore (xslots G xs cls)›
unfolding lcore_def using xslots_kernel by fast
then show ?case using kern by simp
next
case (Suc k)
let ?cs = ‹(creach_step G ^^ k) s›
show ?case
proof
fix c assume ‹c ∈ set ((creach_step G ^^ Suc k) s)›
then have ‹c ∈ set (creach_step G ?cs)› by simp
then consider ‹c ∈ set ?cs›
| pr pr' m' where ‹c = (pr, 0)› ‹pr ∈ set (iprods G)› ‹(pr', m') ∈ set ?cs›
‹m' < length (snd pr')› ‹fst (snd pr' ! m') = Nt (fst pr)›
unfolding creach_step_set by blast
then show ‹c ∈ lcore (xslots G xs cls)›
proof cases
case 1 then show ?thesis using Suc.IH by blast
next
case (2 pr pr' m')
from 2(3) Suc.IH have ‹(pr', m') ∈ lcore (xslots G xs cls)› by blast
then obtain R' where mem': ‹(pr', m', R') ∈ set (xslots G xs cls)›
and ne: ‹irep_nonempty R'› unfolding lcore_def by blast
from 2(2) obtain q where q: ‹q < length (iprods G)› and pq: ‹iprods G ! q = pr›
by (metis in_set_conv_nth)
obtain A rhs where pr': ‹pr' = (A, rhs)› by (cases pr')
have img: ‹ximg pr (pr', m', R') ≠ {}›
using 2(4,5) ne irep_img_nonempty[of R' ‹snd (rhs ! m')›]
unfolding pr' by auto
have ‹ximg (iprods G ! q) (pr', m', R') ⊆ irep_set (xround G xs cls ! q)›
unfolding xround_nth[OF len q] fold_xcontrib_set using mem' by blast
also have ‹… ⊆ irep_set (cls ! q)› by (rule xstableD[OF stable len q])
finally have ‹irep_nonempty (cls ! q)› using img pq by auto
moreover have ‹(iprods G ! q, 0, cls ! q) ∈ set (xslots G xs cls)›
using xslots_slot[OF q] len q by simp
ultimately show ?thesis unfolding 2(1) lcore_def pq[symmetric] by blast
qed
qed
qed
theorem lcore_xclosure_auto:
assumes kern: ‹lcore xs = set s›
shows ‹lcore (xclosure_auto G xs) = set (creach G s)›
proof
show ‹lcore (xclosure_auto G xs) ⊆ set (creach G s)›
proof
fix c assume ‹c ∈ lcore (xclosure_auto G xs)›
then obtain pr m R where c: ‹c = (pr, m)› and mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)›
and ne: ‹irep_nonempty R› unfolding lcore_def by blast
from ne obtain j where ‹j ∈ irep_set R› by auto
have k: ‹⋀pr m R. (pr, m, R) ∈ set xs ⟹ irep_nonempty R ⟹ (pr, m) ∈ set s›
using kern unfolding lcore_def by blast
from xclosure_auto_live_creach[OF k mem ‹j ∈ _›] show ‹c ∈ set (creach G s)› using c by simp
qed
next
show ‹set (creach G s) ⊆ lcore (xclosure_auto G xs)›
unfolding creach_def xclosure_auto_def xclosure_def
by (rule creach_funpow_live[OF xfuel_stable]) (use kern in simp_all)
qed
subsection ‹The set-valued goto on live cores›
text ‹Through a position with relation \<^const>‹Any› an item keeps its set; through
\<^const>‹Eq› (only the start production has it) it is intersected with the
goto's set, which contains the start indentation.›
definition goto_ok :: ‹nat ⇒ ('n, 't) xitem list ⇒ ('n, 't) sym ⇒ indrep ⇒ bool› where
‹goto_ok i0 CL X RA ⟷ irep_nonempty RA ∧
(∀(pr, m, R) ∈ set CL. m < length (snd pr) ⟶ fst (snd pr ! m) = X ⟶
snd (snd pr ! m) = Any ∨ (snd (snd pr ! m) = Eq ∧ i0 ∈ irep_set RA))›
lemma goto_set:
assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_set i0 R›
and mem: ‹(pr, m, R) ∈ set CL› and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
shows ‹irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}›
and ‹anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
proof -
have ne: ‹irep_set RA ≠ {}› using ok unfolding goto_ok_def by simp
have r: ‹snd (snd pr ! m) = Any ∨ (snd (snd pr ! m) = Eq ∧ i0 ∈ irep_set RA)›
using ok mem m X unfolding goto_ok_def by fastforce
have pa: ‹irep_set (irep_pre Any RA) = UNIV› using ne by auto
have pe: ‹irep_set (irep_pre Eq RA) = irep_set RA› by simp
from r consider ‹snd (snd pr ! m) = Any› | ‹snd (snd pr ! m) = Eq› ‹i0 ∈ irep_set RA› by blast
then have ‹(irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}) ∧
anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
proof cases
case 1 then show ?thesis using pa anch by (simp add: anch_set_def)
next
case 2 then show ?thesis using pe anch unfolding anch_set_def by auto
qed
then show ‹irep_set (irep_inter R (irep_pre (snd (snd pr ! m)) RA)) = {} ⟷ irep_set R = {}›
and ‹anch_set i0 (irep_inter R (irep_pre (snd (snd pr ! m)) RA))› by blast+
qed
lemma set_cgoto:
‹set (cgoto cs X) = {(pr, Suc m) | pr m. (pr, m) ∈ set cs ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
unfolding cgoto_def by force
theorem lcore_lgoto:
assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_items i0 CL› and cs: ‹lcore CL = set cs›
shows ‹lcore (lgoto CL X RA) = set (cgoto cs X)›
proof -
have a: ‹anch_set i0 R› if ‹(pr, m, R) ∈ set CL› for pr m R
using anch that unfolding anch_items_def by fastforce
have ‹lcore (lgoto CL X RA) =
{(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
proof (intro equalityI subsetI)
fix c assume ‹c ∈ lcore (lgoto CL X RA)›
then obtain pr m' R' where c: ‹c = (pr, m')› and mem: ‹(pr, m', R') ∈ set (lgoto CL X RA)›
and ne: ‹irep_nonempty R'› unfolding lcore_def by blast
from mem obtain m R where m': ‹m' = Suc m› and memCL: ‹(pr, m, R) ∈ set CL›
and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
unfolding lgoto_def by auto
have ‹irep_nonempty R› using goto_set(1)[OF ok a[OF memCL] memCL m X] ne R' by auto
then have ‹(pr, m) ∈ lcore CL› using memCL unfolding lcore_def by blast
then show ‹c ∈ {(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
using c m' m X by blast
next
fix c assume ‹c ∈ {(pr, Suc m) | pr m. (pr, m) ∈ lcore CL ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X}›
then obtain pr m where c: ‹c = (pr, Suc m)› and l: ‹(pr, m) ∈ lcore CL›
and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X› by blast
from l obtain R where memCL: ‹(pr, m, R) ∈ set CL› and ne: ‹irep_nonempty R›
unfolding lcore_def by blast
have mem: ‹(pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA)) ∈ set (lgoto CL X RA)›
by (rule lgoto_memI[OF memCL m X])
have ‹irep_nonempty (irep_inter R (irep_pre (snd (snd pr ! m)) RA))›
using goto_set(1)[OF ok a[OF memCL] memCL m X] ne by auto
then show ‹c ∈ lcore (lgoto CL X RA)› using mem c unfolding lcore_def by blast
qed
also have ‹… = set (cgoto cs X)› unfolding set_cgoto cs by blast
finally show ?thesis .
qed
lemma lgoto_anch:
assumes ok: ‹goto_ok i0 CL X RA› and anch: ‹anch_items i0 CL›
shows ‹anch_items i0 (lgoto CL X RA)›
unfolding anch_items_def
proof (intro ballI, clarify)
fix pr m' R' assume mem: ‹(pr, m', R') ∈ set (lgoto CL X RA)›
from mem obtain m R where memCL: ‹(pr, m, R) ∈ set CL›
and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X›
and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
unfolding lgoto_def by auto
have ‹anch_set i0 R› using anch memCL unfolding anch_items_def by fastforce
from goto_set(2)[OF ok this memCL m X] show ‹anch_set i0 R'› using R' by simp
qed
lemma lgoto_anns: ‹anns_ok CL ⟹ anns_ok (lgoto CL X RA)›
unfolding anns_ok_def lgoto_def by fastforce
text ‹The two gotos of the driver meet \<^const>‹goto_ok›: a terminal has
relation \<^const>‹Any› everywhere, and the set of a reduce contains the start
indentation when it is not empty.›
lemma goto_ok_Tm:
‹anns_ok CL ⟹ irep_nonempty RA ⟹ goto_ok i0 CL (Tm a) RA›
unfolding goto_ok_def anns_ok_def rel_ok_def by fastforce
lemma goto_ok_Nt:
‹anns_ok CL ⟹ irep_nonempty RA ⟹ i0 ∈ irep_set RA ⟹ goto_ok i0 CL (Nt A) RA›
unfolding goto_ok_def anns_ok_def rel_ok_def by fastforce
lemma red_set_anch:
assumes ‹anch_items i0 CL› and ‹irep_nonempty (red_set CL pr)›
shows ‹i0 ∈ irep_set (red_set CL pr)›
proof -
from assms(2) obtain R where mem: ‹(pr, length (snd pr), R) ∈ set CL› and ne: ‹irep_nonempty R›
unfolding red_set_nonempty_iff by blast
have ‹anch_set i0 R› using assms(1) mem unfolding anch_items_def by fastforce
then have ‹i0 ∈ irep_set R› using ne unfolding anch_set_def by auto
then show ?thesis unfolding red_set_correct using mem by blast
qed
text ‹The successor in the precise automaton, with the sentinel
\<^term>‹length psts› for a dead successor.›
theorem pnext_resolve:
assumes psts: ‹psts = pr0_states G Shn› and p: ‹p < length psts›
shows ‹dnext (pgtab G psts) psts p X < length psts ⟷ cgoto (creach G (psts ! p)) X ≠ []›
and ‹dnext (pgtab G psts) psts p X < length psts ⟹
set (psts ! dnext (pgtab G psts) psts p X) = set (cgoto (creach G (psts ! p)) X)›
proof -
let ?s = ‹psts ! p› and ?pgt = ‹pgtab G psts›
have len: ‹length ?pgt = length psts› unfolding pgtab_def by simp
have dn: ‹dnext ?pgt psts p X = la_next ?pgt psts p X› unfolding dnext_def using p len by simp
have s_in: ‹?s ∈ set psts› using p by simp
have univ: ‹set ?s ⊆ cuniv G Shn›
by (rule pr0_states_univ) (use s_in psts in simp)
have ‹(dnext ?pgt psts p X < length psts ⟷ cgoto (creach G ?s) X ≠ []) ∧
(dnext ?pgt psts p X < length psts ⟶
set (psts ! dnext ?pgt psts p X) = set (cgoto (creach G ?s) X))›
proof (cases ‹∃pr m. (pr, m) ∈ set (creach G ?s) ∧ m < length (snd pr) ∧ fst (snd pr ! m) = X›)
case True
then obtain pr m where mem: ‹(pr, m) ∈ set (creach G ?s)› and m: ‹m < length (snd pr)›
and X: ‹fst (snd pr ! m) = X› by blast
have ‹(pr, m) ∈ cuniv G Shn› using creach_univ[OF univ] mem by blast
from cuniv_next_gram_syms[OF this m] have X_sym: ‹X ∈ set (gram_syms G)› using X by simp
obtain t where t: ‹t ∈ set psts› and te: ‹set t = set (cgoto (creach G ?s) X)›
using pr0_states_closed[OF s_in[unfolded psts] X_sym] unfolding psts by blast
from st_find_found[OF t te] have
sf_lt: ‹st_find psts (cgoto (creach G ?s) X) < length psts›
and sf_set: ‹set (psts ! st_find psts (cgoto (creach G ?s) X)) = set (cgoto (creach G ?s) X)›
by auto
have look: ‹map_of (?pgt ! p) X = Some (st_find psts (cgoto (creach G ?s) X))›
using pgtab_lookup[OF p mem m] X by simp
have eq: ‹dnext ?pgt psts p X = st_find psts (cgoto (creach G ?s) X)›
unfolding dn la_next_def look using sf_lt by simp
have ‹cgoto (creach G ?s) X ≠ []›
using cgoto_memI[OF mem m X] by auto
then show ?thesis using eq sf_lt sf_set by simp
next
case False
have none: ‹map_of (?pgt ! p) X = None›
by (rule pgtab_none[OF p]) (use False in blast)
have eq: ‹dnext ?pgt psts p X = length psts› unfolding dn la_next_def none by simp
have f: ‹filter (λ(pr, m). m < length (snd pr) ∧ fst (snd pr ! m) = X) (creach G ?s) = []›
unfolding filter_empty_conv using False by fast
have ‹cgoto (creach G ?s) X = []› unfolding cgoto_def f by simp
then show ?thesis using eq by simp
qed
then show ‹dnext ?pgt psts p X < length psts ⟷ cgoto (creach G ?s) X ≠ []›
and ‹dnext ?pgt psts p X < length psts ⟹
set (psts ! dnext ?pgt psts p X) = set (cgoto (creach G ?s) X)› by blast+
qed
subsection ‹The simple driver›
text ‹Per state: the productions it completes, and whether it completes the
start production.›
definition pcomps :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ ('n × ('n, 't) rhs) list list› where
‹pcomps G sts =
map (λs. remdups (map fst (filter (λ(pr, m). m = length (snd pr)) (creach G s)))) sts›
definition pfins :: ‹'n ⇒ ('n, 't) citem list list ⇒ bool list› where
‹pfins Shn sts = map (λs. list_ex (λ(pr, m). fst pr = Shn ∧ m = Suc 0) s) sts›
text ‹A reduce cell licenses the reduce by naming the next token (or the end of
the input); the width relation is not consulted.›
definition slic :: ‹nat ⇒ ('n, 't) lacell list ⇒ ('m, 'ch, 't) tword ⇒ 'n × ('n, 't) rhs ⇒ bool› where
‹slic i cells v pr ⟷ list_ex (λ(i', itm, t, τ).
i' = i ∧ itm = (pr, length (snd pr)) ∧
(case v of [] ⇒ t = None | x # _ ⇒ t = Some (tok x))) cells›
definition scands :: ‹('n × ('n, 't) rhs) list ⇒ nat ⇒ ('n, 't) lacell list ⇒
('m, 'ch, 't) tword ⇒ ('n, 't) dact list› where
‹scands comps i cells v = (let reds = map DReduce (filter (slic i cells v) comps)
in (case v of [] ⇒ reds | _ ⇒ DShift # reds))›
text ‹The successor of an action, if it is live.›
definition starget :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
nat list ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't) dact ⇒ nat option› where
‹starget gt sts stk v act = (case act of
DShift ⇒ (case v of [] ⇒ None | x # _ ⇒
let q = dnext gt sts (hd stk) (Tm (tok x)) in
if q < length sts then Some q else None)
| DReduce pr ⇒ (if length (snd pr) < length stk then
let q = dnext gt sts (stk ! length (snd pr)) (Nt (fst pr)) in
if q < length sts then Some q else None
else None))›
fun spick :: ‹('a ⇒ 'b option) ⇒ 'a list ⇒ ('a × 'b) option› where
‹spick f [] = None›
| ‹spick f (a # as) = (case f a of Some b ⇒ Some (a, b) | None ⇒ spick f as)›
type_synonym ('m, 'ch, 't) sctl_t = ‹nat list × ('m, 'ch, 't) tword›
type_synonym ('m, 'ch, 'n, 't) sst = ‹nat list × ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list›
text ‹The step on the control part (the index stack and the input).›
definition sctl :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ ('m, 'ch, 't) sctl_t ⇒
(('n, 't) dact × ('m, 'ch, 't) sctl_t) option› where
‹sctl gt sts redtab pc c = (case c of (stk, v) ⇒
(case stk of [] ⇒ None | i # _ ⇒
let cells = (if i < length redtab then redtab ! i else []);
comps = (if i < length pc then pc ! i else [])
in (case spick (starget gt sts stk v) (scands comps i cells v) of
None ⇒ None
| Some (act, q) ⇒ Some (act, case act of
DShift ⇒ (q # stk, tl v)
| DReduce pr ⇒ (q # drop (length (snd pr)) stk, v)))))›
definition stree :: ‹('n, 't) dact ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) ast list ⇒
('m, 'ch, 'n, 't) ast list› where
‹stree act v tstk = (case act of
DShift ⇒ Leaf (hd v) # tstk
| DReduce pr ⇒ Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)›
definition sstep :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ ('m, 'ch, 'n, 't) sst ⇒
('m, 'ch, 'n, 't) sst option› where
‹sstep gt sts redtab pc st = (case st of (stk, v, tstk) ⇒
map_option (λ(act, stk', v'). (stk', v', stree act v tstk)) (sctl gt sts redtab pc (stk, v)))›
definition sfinal :: ‹bool list ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
‹sfinal pf c ⟷ (case c of (stk, v) ⇒ v = [] ∧ stk ≠ [] ∧ hd stk < length pf ∧ pf ! hd stk)›
definition sresult :: ‹('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast option› where
‹sresult tstk = (case tstk of t # _ ⇒ Some t | [] ⇒ None)›
fun srun :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒ nat ⇒
('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option› where
‹srun gt sts redtab pc pf 0 st = (case st of (stk, v, tstk) ⇒
if sfinal pf (stk, v) then sresult tstk else None)›
| ‹srun gt sts redtab pc pf (Suc n) st = (case st of (stk, v, tstk) ⇒
if sfinal pf (stk, v) then sresult tstk
else (case sstep gt sts redtab pc st of
None ⇒ None
| Some st' ⇒ srun gt sts redtab pc pf n st'))›
partial_function (option) srun⇩w⇩f ::
‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒
('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹srun⇩w⇩f gt sts redtab pc pf st = (case st of (stk, v, tstk) ⇒
if sfinal pf (stk, v) then sresult tstk
else Option.bind (sstep gt sts redtab pc st) (srun⇩w⇩f gt sts redtab pc pf))›
text ‹The run with a history of the stacks since the last shift, over any
step on the control part (\<^const>‹sctl›, or the indexed step below) and
final test.›
partial_function (option) srun_hist ::
‹(('m, 'ch, 't) sctl_t ⇒ (('n, 't) dact × ('m, 'ch, 't) sctl_t) option) ⇒
(('m, 'ch, 't) sctl_t ⇒ bool) ⇒ nat list list ⇒
('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 'n, 't) ast option›
where
‹srun_hist ctl fin seen st = (case st of (stk, v, tstk) ⇒
if fin (stk, v) then sresult tstk
else if stk ∈ set seen then None
else Option.bind (ctl (stk, v)) (λ(act, stk', v').
srun_hist ctl fin (if act = DShift then [] else stk # seen)
(stk', v', stree act v tstk)))›
lemmas srun_hist_simps [code] = srun_hist.simps
definition sinit :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒ ('m, 'ch, 't) tword ⇒
('m, 'ch, 'n, 't) sst› where
‹sinit G Shn sts w = ([st_find sts (lr0_start G Shn)], w, [])›
definition sparse :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) ast option› where
‹sparse G Shn w = (let sts = pr0_states G Shn; gt = pgtab G sts;
redtab = red_buckets G Shn (length sts)
in srun⇩w⇩f gt sts redtab (pcomps G sts) (pfins Shn sts) (sinit G Shn sts w))›
subsection ‹The simulation relation›
text ‹The static conditions: no layout annotations, operational determinism,
and reduce cells naming a token carry no width constraint.›
definition wany_ok :: ‹('n, 't) lacell list list ⇒ bool› where
‹wany_ok redtab ⟷ list_all (list_all (λ(i, itm, t, τ). t = None ∨ τ = WAny)) redtab›
definition sstatic :: ‹('n, 't) is_cfg ⇒ 'n ⇒ bool› where
‹sstatic G Shn ⟷ ii G ∧ mdet G Shn ∧
wany_ok (red_buckets G Shn (length (pr0_states G Shn)))›
lemma sstaticI:
‹ii G ⟹ rlalr_conflicts G Shn = [] ⟹ fresh_name G Shn ⟹
wany_ok (red_buckets G Shn (length (pr0_states G Shn))) ⟹ sstatic G Shn›
unfolding sstatic_def using rlalr_sufficient[of G Shn] by (intro conjI) simp_all
lemma wany_okD:
‹wany_ok redtab ⟹ i < length redtab ⟹ (i', itm, t, τ) ∈ set (redtab ! i) ⟹
t ≠ None ⟹ τ = WAny›
unfolding wany_ok_def list_all_iff by (fastforce dest: nth_mem)
definition sctrl :: ‹('m, 'ch, 'n, 't) sst ⇒ ('m, 'ch, 't) sctl_t› where
‹sctrl ss = (case ss of (stk, v, tstk) ⇒ (stk, v))›
definition ssim :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) sst ⇒ bool› where
‹ssim G Shn sts st ss ⟷ (case st of ((Xs, w), cstk, istk, v, tstk) ⇒
case ss of (stk, v', tstk') ⇒
v' = v ∧ tstk' = tstk ∧ w = tcols v ∧ Xs ≠ [] ∧ stk = istk ∧
cstk_ok G Xs cstk ∧ didx_ok G (pr0_states G Shn) Xs istk ∧
(∀k < length Xs. istk ! k < length sts ∧ set (sts ! (istk ! k)) = lcore (Xs ! k)) ∧
(∀X ∈ set Xs. anch_items (istart_ind G) X ∧ anns_ok X) ∧
imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk))›
lemma ssim_init:
assumes sts: ‹sts = pr0_states G Shn›
shows ‹ssim G Shn sts (dinit G Shn sts w) (sinit G Shn sts w)›
proof -
obtain t where t: ‹t ∈ set sts› and te: ‹set t = set (ccore (xinit G Shn))›
using pr0_states_start[of G Shn] sts by blast
from st_find_found[OF t te[unfolded ccore_xinit]]
have lt: ‹st_find sts (lr0_start G Shn) < length sts›
and eq: ‹set (sts ! st_find sts (lr0_start G Shn)) = set (lr0_start G Shn)› by auto
have anch: ‹anch_items (istart_ind G) (xinit G Shn)›
unfolding anch_items_def anch_set_def xinit_def by simp
have anns: ‹anns_ok (xinit G Shn)›
unfolding anns_ok_def rel_ok_def xinit_def by simp
show ?thesis
unfolding ssim_def dinit_def sinit_def
using lt eq anch anns
by (simp add: cstk_ok_def lcore_xinit didx_ok_init[OF tables_ok_concrete] imreach_init sts)
qed
lemma ssim_len:
‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v', tstk') ⟹ length stk = length Xs›
unfolding ssim_def using didx_ok_len by fastforce
lemma ssim_final:
assumes sim: ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v', tstk')›
shows ‹gfinal G Shn (Xs, w) ⟷ sfinal (pfins Shn sts) (stk, v')›
proof -
from sim have v: ‹v' = v› ‹w = tcols v› and ne: ‹Xs ≠ []› and si: ‹stk = istk›
and p: ‹istk ! 0 < length sts› ‹set (sts ! (istk ! 0)) = lcore (Xs ! 0)›
and anch: ‹anch_items (istart_ind G) (hd Xs)›
unfolding ssim_def by auto
have len: ‹length stk = length Xs› using ssim_len[OF sim] .
then have stk_ne: ‹stk ≠ []› using ne by auto
then have hd: ‹hd stk = stk ! 0› by (simp add: hd_conv_nth)
have hdX: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have i0: ‹⋀pr m R. (pr, m, R) ∈ set (hd Xs) ⟹ irep_mem (istart_ind G) R ⟷ irep_nonempty R›
using anch unfolding anch_items_def anch_set_def by fastforce
have ‹list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧ irep_mem (istart_ind G) R) (hd Xs) ⟷
(∃(pr, m) ∈ lcore (hd Xs). fst pr = Shn ∧ m = Suc 0)›
unfolding list_ex_iff lcore_def using i0 by fastforce
also have ‹… ⟷ pfins Shn sts ! hd stk›
unfolding pfins_def using p hd hdX si by (auto simp: list_ex_iff)
moreover have ‹w = [] ⟷ v' = []› using v by (simp add: tcols_def)
ultimately show ?thesis
unfolding gfinal_def sfinal_def using ne stk_ne p hd si by (auto simp: pfins_def)
qed
lemma pcomps_mem:
‹p < length sts ⟹
pr ∈ set (pcomps G sts ! p) ⟷ (pr, length (snd pr)) ∈ set (creach G (sts ! p))›
unfolding pcomps_def by force
lemma slic_dlic:
assumes c: ‹⋀i' itm t τ. (i', itm, t, τ) ∈ set cells ⟹ t ≠ None ⟹ τ = WAny›
and ne: ‹irep_nonempty RS›
shows ‹dlic i cells (tcols v) pr RS ⟷ slic i cells v pr›
proof -
show ?thesis
proof (cases v)
case Nil
then show ?thesis unfolding dlic_def slic_def by simp
next
case (Cons x v')
have ‹⋀i' itm t τ. (i', itm, t, τ) ∈ set cells ⟹ t = Some (tok x) ⟹
irep_ex_wsat τ (s_col (span x)) RS›
using c ne by fastforce
then show ?thesis unfolding dlic_def slic_def Cons list_ex_iff by fastforce
qed
qed
subsection ‹Candidates and picks›
lemma cstk_ok_map: ‹cstk_ok G Xs cstk ⟷ cstk = map (xclosure_auto G) Xs›
unfolding cstk_ok_def by (induction Xs arbitrary: cstk) (auto simp: list_all2_Cons1)
lemma dpick_NoneD:
‹dpick G cstk gc acts = None ⟹ a ∈ set acts ⟹ mstep_cached G cstk gc a = Some gc' ⟹
¬ dlive gc'›
by (induction acts) (auto split: option.splits if_splits)
lemma spick_SomeD: ‹spick f xs = Some (a, b) ⟹ a ∈ set xs ∧ f a = Some b›
by (induction xs) (auto split: option.splits)
lemma spick_None_iff: ‹spick f xs = None ⟷ (∀a ∈ set xs. f a = None)›
by (induction xs) (auto split: option.splits)
lemma dcands_mem:
assumes ‹Xs ≠ []›
shows ‹act ∈ set (dcands G i cells CL (Xs, w)) ⟷ (case act of
DShift ⇒ w ≠ []
| DReduce pr ⇒ irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))›
proof -
have comp: ‹pr ∈ set (remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL)))›
if ‹irep_nonempty (red_set CL pr)› for pr
proof -
from that obtain R where ‹(pr, length (snd pr), R) ∈ set CL›
unfolding red_set_nonempty_iff by blast
then show ?thesis by force
qed
show ?thesis
using assms comp unfolding dcands_def
by (cases act; cases w) (auto simp: Let_def)
qed
lemma scands_mem:
‹act ∈ set (scands comps i cells v) ⟷ (case act of
DShift ⇒ v ≠ []
| DReduce pr ⇒ pr ∈ set comps ∧ slic i cells v pr)›
unfolding scands_def by (cases act; cases v) auto
subsection ‹One step›
context
fixes G :: ‹('n, 't) is_cfg› and Shn :: 'n
and sts :: ‹('n, 't) citem list list› and gt :: ‹(('n, 't) sym × nat) list list›
and redtab :: ‹('n, 't) lacell list list› and pc :: ‹('n × ('n, 't) rhs) list list›
assumes static: ‹sstatic G Shn›
and sts: ‹sts = pr0_states G Shn› and gt: ‹gt = pgtab G sts›
and redtab: ‹redtab = red_buckets G Shn (length sts)›
and pc: ‹pc = pcomps G sts›
begin
lemma tabs: ‹tables_ok G Shn sts gt (la_fix G Shn)›
using tables_ok_concrete[of G Shn] unfolding sts gt .
lemma ii: ‹ii G› and det: ‹mdet G Shn›
and wany: ‹wany_ok (red_buckets G Shn (length sts))›
using static unfolding sstatic_def sts by blast+
context
fixes Xs :: ‹('n, 't) xitem list list› and w cstk istk
and v :: ‹('m, 'ch, 't) tword› and tstk :: ‹('m, 'ch, 'n, 't) ast list› and stk i
assumes sim: ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v, tstk)›
and hd_stk: ‹hd stk = i›
begin
lemma c_ne: ‹Xs ≠ []› and c_w: ‹w = tcols v› and c_stk: ‹stk = istk›
and c_cstk: ‹cstk = map (xclosure_auto G) Xs›
and c_didx: ‹didx_ok G sts Xs istk›
and c_reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk)›
using sim unfolding ssim_def sts cstk_ok_map by auto
lemma c_prec: ‹k < length Xs ⟹ istk ! k < length sts ∧ set (sts ! (istk ! k)) = lcore (Xs ! k)›
using sim unfolding ssim_def by auto
lemma c_frames: ‹X ∈ set Xs ⟹ anch_items (istart_ind G) X ∧ anns_ok X›
using sim unfolding ssim_def by auto
lemma c_ilen: ‹length istk = length Xs›
using didx_ok_len[OF c_didx] .
lemma c_len: ‹length stk = length Xs›
using c_stk c_ilen by simp
lemma c_hd0: ‹stk ! 0 = i› and c_hdX: ‹hd Xs = Xs ! 0›
using c_len c_ne hd_stk by (cases stk; cases Xs; simp)+
lemma c_istk_case: ‹(case istk of [] ⇒ length sts | j # _ ⇒ j) = i›
using c_stk c_len c_ne hd_stk by (cases stk) auto
lemma c_cstk_case: ‹(case cstk of [] ⇒ [] | c # _ ⇒ c) = xclosure_auto G (hd Xs)›
using c_cstk c_ne by (cases Xs) auto
lemma c_istk0: ‹istk ! 0 = i›
using c_stk c_hd0 by simp
lemma c_i_lt: ‹i < length sts›
using c_prec[of 0] c_ne c_istk0 by simp
lemma c_cells: ‹(if i < length redtab then redtab ! i else []) = red_buckets G Shn (length sts) ! i›
using c_i_lt unfolding redtab by simp
lemma c_comps: ‹(if i < length pc then pc ! i else []) = pcomps G sts ! i›
using c_i_lt unfolding pc pcomps_def by simp
lemma c_frame_cl:
assumes ‹k < length Xs›
shows ‹lcore (xclosure_auto G (Xs ! k)) = set (creach G (sts ! (istk ! k)))›
and ‹anch_items (istart_ind G) (xclosure_auto G (Xs ! k))›
and ‹anns_ok (xclosure_auto G (Xs ! k))›
proof -
have f: ‹anch_items (istart_ind G) (Xs ! k) ∧ anns_ok (Xs ! k)›
using c_frames assms by simp
show ‹lcore (xclosure_auto G (Xs ! k)) = set (creach G (sts ! (istk ! k)))›
by (rule lcore_xclosure_auto) (use c_prec[OF assms] in simp)
show ‹anch_items (istart_ind G) (xclosure_auto G (Xs ! k))›
using xclosure_auto_anch[OF ii] f by blast
show ‹anns_ok (xclosure_auto G (Xs ! k))›
using xclosure_auto_anns[OF ii] f by blast
qed
lemma c_CL:
‹lcore (xclosure_auto G (hd Xs)) = set (creach G (sts ! i))›
‹anch_items (istart_ind G) (xclosure_auto G (hd Xs))›
‹anns_ok (xclosure_auto G (hd Xs))›
using c_frame_cl[of 0] c_ne c_istk0 c_hdX by simp_all
lemma c_red_comps:
‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr) ⟷ pr ∈ set (pcomps G sts ! i)›
unfolding pcomps_mem[OF c_i_lt] c_CL(1)[symmetric] red_set_nonempty_iff lcore_def by blast
lemma c_shift:
assumes v: ‹v = x # v'›
shows ‹mstep G (Xs, w) DShift =
Some (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v')›
and ‹lcore (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) =
set (cgoto (creach G (sts ! i)) (Tm (tok x)))›
proof -
show ‹mstep G (Xs, w) DShift =
Some (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v')›
unfolding mstep_def mstep_cached_def using c_ne by (simp add: c_w v hd_map)
show ‹lcore (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) =
set (cgoto (creach G (sts ! i)) (Tm (tok x)))›
by (rule lcore_lgoto[OF goto_ok_Tm[OF c_CL(3)] c_CL(2) c_CL(1)]) simp
qed
lemma c_reduce:
assumes n: ‹length (snd pr) < length Xs›
and RS: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
shows ‹mstep G (Xs, w) (DReduce pr) =
Some (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w)›
and ‹lcore (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr)) =
set (cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)))›
proof -
show ‹mstep G (Xs, w) (DReduce pr) =
Some (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w)›
unfolding mstep_def mstep_cached_def using c_ne n RS by (simp add: Let_def hd_map)
have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr)›
by (rule goto_ok_Nt[OF c_frame_cl(3)[OF n] RS red_set_anch[OF c_CL(2) RS]])
show ‹lcore (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr)) =
set (cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)))›
by (rule lcore_lgoto[OF ok c_frame_cl(2)[OF n] c_frame_cl(1)[OF n]])
qed
lemma c_act_iff:
‹(act ∈ set (dcands G i (red_buckets G Shn (length sts) ! i) (xclosure_auto G (hd Xs)) (Xs, w)) ∧
(∃gc'. mstep G (Xs, w) act = Some gc' ∧ dlive gc')) ⟷
(act ∈ set (scands (pcomps G sts ! i) i (red_buckets G Shn (length sts) ! i) v) ∧
starget gt sts stk v act ≠ None)›
proof (cases act)
case DShift
show ?thesis
proof (cases v)
case Nil
then show ?thesis unfolding DShift dcands_mem[OF c_ne] scands_mem using c_w by simp
next
case (Cons x v')
have pr: ‹dnext gt sts i (Tm (tok x)) < length sts ⟷
cgoto (creach G (sts ! i)) (Tm (tok x)) ≠ []›
using pnext_resolve(1)[OF sts c_i_lt] unfolding gt .
show ?thesis unfolding DShift dcands_mem[OF c_ne] scands_mem c_shift(1)[OF Cons]
using pr c_shift(2)[OF Cons] c_w Cons hd_stk by (simp add: dlive_lcore starget_def Let_def)
qed
next
case (DReduce pr)
show ?thesis
proof (cases ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›)
case False
then show ?thesis unfolding DReduce dcands_mem[OF c_ne] scands_mem c_red_comps by simp
next
case RS: True
have lic: ‹dlic i (red_buckets G Shn (length sts) ! i) w pr (red_set (xclosure_auto G (hd Xs)) pr)
⟷ slic i (red_buckets G Shn (length sts) ! i) v pr›
unfolding c_w
by (rule slic_dlic[OF wany_okD[OF wany] RS]) (use c_i_lt in simp_all)
show ?thesis
proof (cases ‹length (snd pr) < length Xs›)
case False
then have ‹mstep G (Xs, w) (DReduce pr) = None›
unfolding mstep_def mstep_cached_def by simp
moreover have ‹starget gt sts stk v (DReduce pr) = None›
using False c_len unfolding starget_def by simp
ultimately show ?thesis unfolding DReduce by simp
next
case n: True
have q_lt: ‹istk ! length (snd pr) < length sts› using c_prec[OF n] by simp
have pr': ‹dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) < length sts ⟷
cgoto (creach G (sts ! (istk ! length (snd pr)))) (Nt (fst pr)) ≠ []›
using pnext_resolve(1)[OF sts q_lt] unfolding gt .
show ?thesis unfolding DReduce dcands_mem[OF c_ne] scands_mem c_reduce(1)[OF n RS]
using RS lic pr' c_reduce(2)[OF n RS] n c_len c_stk c_red_comps
by (simp add: dlive_lcore starget_def Let_def)
qed
qed
qed
lemma lcore_Nil_ne: ‹lcore xs ≠ {} ⟹ xs ≠ []›
unfolding lcore_def by auto
lemma c_shift_post:
assumes v: ‹v = x # v'› and q: ‹q = dnext gt sts i (Tm (tok x))› and q_lt: ‹q < length sts›
shows ‹ssim G Shn sts
((lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v'),
xclosure_auto G (lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])) # cstk,
dnext gt sts i (Tm (tok x)) # istk, v', ts)
(q # stk, v', ts)›
proof -
let ?F = ‹lgoto (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])›
let ?q = ‹dnext gt sts i (Tm (tok x))›
have ne: ‹cgoto (creach G (sts ! i)) (Tm (tok x)) ≠ []›
using pnext_resolve(1)[OF sts c_i_lt, of ‹Tm (tok x)›] q q_lt unfolding gt by simp
have Fl: ‹lcore ?F = set (sts ! q)›
using c_shift(2)[OF v] pnext_resolve(2)[OF sts c_i_lt, of ‹Tm (tok x)›] q q_lt
unfolding gt by simp
have Fne: ‹?F ≠ []› using c_shift(2)[OF v] ne by (intro lcore_Nil_ne) simp
have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (hd Xs)) (Tm (tok x)) (FinRep [s_col (span x)])›
by (rule goto_ok_Tm[OF c_CL(3)]) simp
have Fa: ‹anch_items (istart_ind G) ?F› using lgoto_anch[OF ok c_CL(2)] .
have Fn: ‹anns_ok ?F› using lgoto_anns[OF c_CL(3)] .
have didx: ‹didx_ok G sts (?F # Xs) (?q # istk)›
using didx_ok_push[OF tabs c_didx, of 0 ‹Tm (tok x)› ‹FinRep [s_col (span x)]›]
c_ne c_hdX c_istk0 by simp
have hdi: ‹hd istk = i› using c_stk hd_stk by simp
have reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
((?F # Xs, tcols v'), ?q # istk)›
proof (rule imreach_step[OF c_reach, of DShift])
show ‹imstep G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk) DShift =
Some ((?F # Xs, tcols v'), ?q # istk)›
unfolding imstep_def prod.case c_shift(1)[OF v] option.case dact.case hdi gt sts
by (simp add: c_w v tcols_def)
show ‹dlive (fst ((?F # Xs, tcols v'), ?q # istk))›
unfolding fst_conv dlive_lcore c_shift(2)[OF v] using ne by simp
qed
have prec: ‹∀k < length (?F # Xs). (?q # istk) ! k < length sts ∧
set (sts ! ((?q # istk) ! k)) = lcore ((?F # Xs) ! k)›
proof (intro allI impI)
fix k assume k: ‹k < length (?F # Xs)›
show ‹(?q # istk) ! k < length sts ∧ set (sts ! ((?q # istk) ! k)) = lcore ((?F # Xs) ! k)›
proof (cases k)
case 0 then show ?thesis using q_lt Fl q by simp
next
case (Suc k') then show ?thesis using c_prec[of k'] k by simp
qed
qed
have fr: ‹∀X ∈ set (?F # Xs). anch_items (istart_ind G) X ∧ anns_ok X›
unfolding list.set(2) ball_simps(7) using Fa Fn c_frames by blast
have cs: ‹cstk_ok G (?F # Xs) (xclosure_auto G ?F # cstk)›
using c_cstk by (simp add: cstk_ok_map)
have ist: ‹q # stk = ?q # istk›
using c_stk q by simp
have sts': ‹didx_ok G (pr0_states G Shn) (?F # Xs) (?q # istk)›
using didx unfolding sts .
show ?thesis unfolding ssim_def prod.case
by (intro conjI refl list.distinct(2) ist cs sts' prec fr reach)
qed
lemma c_reduce_post:
assumes n: ‹length (snd pr) < length Xs›
and RS: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
and q: ‹q = dnext gt sts (istk ! length (snd pr)) (Nt (fst pr))› and q_lt: ‹q < length sts›
shows ‹ssim G Shn sts
((lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr) # drop (length (snd pr)) Xs, w),
xclosure_auto G (lgoto (xclosure_auto G (Xs ! length (snd pr))) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr)) # drop (length (snd pr)) cstk,
dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) # drop (length (snd pr)) istk, v, ts)
(q # drop (length (snd pr)) stk, v, ts)›
proof -
let ?n = ‹length (snd pr)›
let ?F = ‹lgoto (xclosure_auto G (Xs ! ?n)) (Nt (fst pr)) (red_set (xclosure_auto G (hd Xs)) pr)›
let ?q = ‹dnext gt sts (istk ! ?n) (Nt (fst pr))›
have sn: ‹istk ! ?n < length sts› using c_prec[OF n] by simp
have ne: ‹cgoto (creach G (sts ! (istk ! ?n))) (Nt (fst pr)) ≠ []›
using pnext_resolve(1)[OF sts sn, of ‹Nt (fst pr)›] q q_lt unfolding gt by simp
have Fl: ‹lcore ?F = set (sts ! q)›
using c_reduce(2)[OF n RS] pnext_resolve(2)[OF sts sn, of ‹Nt (fst pr)›] q q_lt
unfolding gt by simp
have Fne: ‹?F ≠ []› using c_reduce(2)[OF n RS] ne by (intro lcore_Nil_ne) simp
have ok: ‹goto_ok (istart_ind G) (xclosure_auto G (Xs ! ?n)) (Nt (fst pr))
(red_set (xclosure_auto G (hd Xs)) pr)›
by (rule goto_ok_Nt[OF c_frame_cl(3)[OF n] RS red_set_anch[OF c_CL(2) RS]])
have Fa: ‹anch_items (istart_ind G) ?F› using lgoto_anch[OF ok c_frame_cl(2)[OF n]] .
have Fn: ‹anns_ok ?F› using lgoto_anns[OF c_frame_cl(3)[OF n]] .
have didx: ‹didx_ok G sts (?F # drop ?n Xs) (?q # drop ?n istk)›
using didx_ok_push[OF tabs c_didx n] .
have reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
((?F # drop ?n Xs, w), ?q # drop ?n istk)›
proof (rule imreach_step[OF c_reach, of ‹DReduce pr›])
show ‹imstep G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk) (DReduce pr) =
Some ((?F # drop ?n Xs, w), ?q # drop ?n istk)›
unfolding imstep_def prod.case c_reduce(1)[OF n RS] option.case dact.case gt sts ..
show ‹dlive (fst ((?F # drop ?n Xs, w), ?q # drop ?n istk))›
unfolding fst_conv dlive_lcore c_reduce(2)[OF n RS] using ne by simp
qed
have prec: ‹∀k < length (?F # drop ?n Xs). (?q # drop ?n istk) ! k < length sts ∧
set (sts ! ((?q # drop ?n istk) ! k)) = lcore ((?F # drop ?n Xs) ! k)›
proof (intro allI impI)
fix k assume k: ‹k < length (?F # drop ?n Xs)›
show ‹(?q # drop ?n istk) ! k < length sts ∧
set (sts ! ((?q # drop ?n istk) ! k)) = lcore ((?F # drop ?n Xs) ! k)›
proof (cases k)
case 0 then show ?thesis using q_lt Fl q by simp
next
case (Suc k')
have kk: ‹?n + k' < length Xs› using k Suc n by simp
have e1: ‹drop ?n istk ! k' = istk ! (?n + k')›
by (rule nth_drop) (use n c_ilen in ‹metis less_imp_le›)
have e2: ‹drop ?n Xs ! k' = Xs ! (?n + k')›
by (rule nth_drop) (rule less_imp_le[OF n])
show ?thesis unfolding Suc nth_Cons_Suc e1 e2 by (rule c_prec[OF kk])
qed
qed
have fr: ‹∀X ∈ set (drop ?n Xs). anch_items (istart_ind G) X ∧ anns_ok X›
proof
fix X assume ‹X ∈ set (drop ?n Xs)›
then have ‹X ∈ set Xs› by (rule in_set_dropD)
then show ‹anch_items (istart_ind G) X ∧ anns_ok X› by (rule c_frames)
qed
have fr': ‹∀X ∈ set (?F # drop ?n Xs). anch_items (istart_ind G) X ∧ anns_ok X›
unfolding list.set(2) ball_simps(7) using Fa Fn fr by blast
have cs: ‹cstk_ok G (?F # drop ?n Xs) (xclosure_auto G ?F # drop ?n cstk)›
using c_cstk by (simp add: cstk_ok_map drop_map)
have ist': ‹q # drop ?n stk = ?q # drop ?n istk›
using c_stk q by simp
have sts': ‹didx_ok G (pr0_states G Shn) (?F # drop ?n Xs) (?q # drop ?n istk)›
using didx unfolding sts .
show ?thesis unfolding ssim_def prod.case
by (intro conjI refl list.distinct(2) ist' cs sts' prec fr' reach c_w)
qed
end
lemma ssim_step:
assumes sim: ‹ssim G Shn sts st ss› and nf: ‹¬ gfinal G Shn (fst st)›
shows ‹rel_option (ssim G Shn sts) (dstep G gt sts redtab st) (sstep gt sts redtab pc ss)›
proof -
obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)›
by (cases st) auto
obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
have v': ‹v' = v› and t': ‹tstk' = tstk› using sim unfolding st ss ssim_def by auto
have sim': ‹ssim G Shn sts ((Xs, w), cstk, istk, v, tstk) (stk, v, tstk)›
using sim unfolding st ss v' t' .
obtain i where hd: ‹hd stk = i› by blast
have ne: ‹Xs ≠ []› using c_ne[OF sim' hd] .
have stk_ne: ‹stk ≠ []› using c_len[OF sim' hd] ne by auto
then obtain rest where stk_eq: ‹stk = i # rest› using hd by (cases stk) auto
let ?cells = ‹red_buckets G Shn (length sts) ! i›
let ?CL = ‹xclosure_auto G (hd Xs)›
let ?D = ‹dcands G i ?cells ?CL (Xs, w)›
let ?S = ‹scands (pcomps G sts ! i) i ?cells v›
let ?f = ‹starget gt sts stk v›
have dstep_eq: ‹dstep G gt sts redtab st = (case dpick G cstk (Xs, w) ?D of
None ⇒ None
| Some (act, gc') ⇒ Some (case act of
DShift ⇒ (gc', xclosure_auto G (hd (fst gc')) # cstk,
dnext gt sts i (Tm (tok (hd v))) # istk, tl v, Leaf (hd v) # tstk)
| DReduce pr ⇒ (gc', xclosure_auto G (hd (fst gc')) # drop (length (snd pr)) cstk,
dnext gt sts (istk ! length (snd pr)) (Nt (fst pr)) # drop (length (snd pr)) istk, v,
Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)))›
unfolding st dstep_def Let_def prod.case c_istk_case[OF sim' hd] c_cstk_case[OF sim' hd]
c_cells[OF sim' hd] ..
have sctl_eq: ‹sctl gt sts redtab pc (stk, v) = (case spick ?f ?S of
None ⇒ None
| Some (act, q) ⇒ Some (act, case act of
DShift ⇒ (q # stk, tl v)
| DReduce pr ⇒ (q # drop (length (snd pr)) stk, v)))›
using c_cells[OF sim' hd] c_comps[OF sim' hd]
by (simp only: sctl_def stk_eq list.case prod.case Let_def)
have iff: ‹⋀a. (a ∈ set ?D ∧ (∃gc'. mstep G (Xs, w) a = Some gc' ∧ dlive gc')) ⟷
(a ∈ set ?S ∧ ?f a ≠ None)›
by (rule c_act_iff[OF sim' hd])
have mc: ‹⋀a. mstep_cached G cstk (Xs, w) a = mstep G (Xs, w) a›
by (simp add: mstep_def c_cstk[OF sim' hd])
have hdi: ‹i = hd istk› using c_stk[OF sim' hd] hd by simp
have didx': ‹didx_ok G (pr0_states G Shn) Xs istk› using c_didx[OF sim' hd] unfolding sts .
have uniq: ‹a⇩1 = a⇩2›
if ‹a⇩1 ∈ set ?D› ‹a⇩2 ∈ set ?D› ‹mstep G (Xs, w) a⇩1 = Some gc⇩1› ‹mstep G (Xs, w) a⇩2 = Some gc⇩2›
‹dlive gc⇩1› ‹dlive gc⇩2› for a⇩1 a⇩2 gc⇩1 gc⇩2
proof (rule ccontr)
assume ‹a⇩1 ≠ a⇩2›
from det[unfolded mdet_def, rule_format, of ‹(Xs, w)› istk i ‹?cells› ?CL a⇩1 a⇩2 gc⇩1 gc⇩2]
show False using c_reach[OF sim' hd] ne didx' hdi that ‹a⇩1 ≠ a⇩2› unfolding sts by simp
qed
show ?thesis
proof (cases ‹dpick G cstk (Xs, w) ?D›)
case None
have ‹∀a ∈ set ?S. ?f a = None›
proof (intro ballI)
fix a assume a: ‹a ∈ set ?S›
show ‹?f a = None›
proof (rule ccontr)
assume ‹?f a ≠ None›
with a iff obtain gc' where ‹a ∈ set ?D› ‹mstep G (Xs, w) a = Some gc'› ‹dlive gc'› by blast
with dpick_NoneD[OF None] mc show False by metis
qed
qed
then have ‹spick ?f ?S = None› by (simp add: spick_None_iff)
then show ?thesis unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq None by simp
next
case (Some r)
obtain a gc' where r: ‹r = (a, gc')› by (cases r)
from dpick_sound[OF Some[unfolded r]] mc have aD: ‹a ∈ set ?D›
and ms: ‹mstep G (Xs, w) a = Some gc'› and lv: ‹dlive gc'› by auto
from iff[of a] aD ms lv obtain q where fq: ‹?f a = Some q› by auto
have aS: ‹a ∈ set ?S› using iff[of a] aD ms lv by blast
obtain a' q' where sp: ‹spick ?f ?S = Some (a', q')›
using spick_None_iff[of ?f ?S] aS fq by (cases ‹spick ?f ?S›) auto
from spick_SomeD[OF sp] have a'S: ‹a' ∈ set ?S› and fq': ‹?f a' = Some q'› by auto
from iff[of a'] a'S fq' obtain gc'' where ‹a' ∈ set ?D› ‹mstep G (Xs, w) a' = Some gc''›
‹dlive gc''› by auto
from uniq[OF aD this(1) ms this(2) lv this(3)] have aa: ‹a' = a› by simp
with fq fq' have qq: ‹q' = q› by simp
have sp': ‹spick ?f ?S = Some (a, q)› using sp aa qq by simp
show ?thesis
proof (cases a)
case DShift
from fq obtain x v'' where v: ‹v = x # v''› by (cases v) (auto simp: DShift starget_def)
have q: ‹q = dnext gt sts i (Tm (tok x))› and q_lt: ‹q < length sts›
using fq unfolding DShift starget_def v hd by (auto simp: Let_def split: if_splits)
have gc': ‹gc' = (lgoto ?CL (Tm (tok x)) (FinRep [s_col (span x)]) # Xs, tcols v'')›
using ms c_shift(1)[OF sim' hd v] unfolding DShift by simp
show ?thesis
unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq sp' Some r DShift
using c_shift_post[OF sim' hd v q q_lt, of ‹Leaf x # tstk›] gc' v
by (simp add: stree_def)
next
case (DReduce pr)
let ?n = ‹length (snd pr)›
have RS: ‹irep_nonempty (red_set ?CL pr)› using aD unfolding DReduce dcands_mem[OF ne] by simp
have n: ‹?n < length Xs› and q: ‹q = dnext gt sts (stk ! ?n) (Nt (fst pr))›
and q_lt: ‹q < length sts›
using fq c_len[OF sim' hd] unfolding DReduce starget_def by (auto simp: Let_def split: if_splits)
have gc': ‹gc' = (lgoto (xclosure_auto G (Xs ! ?n)) (Nt (fst pr)) (red_set ?CL pr)
# drop ?n Xs, w)›
using ms c_reduce(1)[OF sim' hd n RS] unfolding DReduce by simp
show ?thesis
unfolding dstep_eq ss sstep_def v' t' prod.case sctl_eq sp' Some r DReduce
using c_reduce_post[OF sim' hd n RS q[unfolded c_stk[OF sim' hd]] q_lt,
of ‹Node (fst pr) (rev (take ?n tstk)) # drop ?n tstk›] gc'
by (simp add: stree_def)
qed
qed
qed
lemma ssim_final':
assumes ‹ssim G Shn sts st ss›
shows ‹gfinal G Shn (fst st) ⟷ sfinal (pfins Shn sts) (sctrl ss)›
proof -
obtain Xs w cstk istk v tstk where st: ‹st = ((Xs, w), cstk, istk, v, tstk)› by (cases st) auto
obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
show ?thesis using ssim_final[OF assms[unfolded st ss]] unfolding st ss sctrl_def by simp
qed
lemma ssim_tstk:
‹ssim G Shn sts ((gc, cstk, istk, v, tstk)) (stk, v', tstk') ⟹ tstk' = tstk›
unfolding ssim_def by (cases gc) auto
lemma ssim_drun:
‹ssim G Shn sts st ss ⟹
drun G Shn gt sts redtab n st = srun gt sts redtab pc (pfins Shn sts) n ss›
proof (induction n arbitrary: st ss)
case 0
obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st) auto
obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
have f: ‹gfinal G Shn gc ⟷ sfinal (pfins Shn sts) (stk, v')›
using ssim_final'[OF "0"] unfolding st ss sctrl_def by simp
have t: ‹tstk' = tstk› using ssim_tstk "0" unfolding st ss by blast
show ?case using f t unfolding st ss by (auto simp: sresult_def split: list.splits)
next
case (Suc n)
obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st) auto
obtain stk v' tstk' where ss: ‹ss = (stk, v', tstk')› by (cases ss) auto
have f: ‹gfinal G Shn gc ⟷ sfinal (pfins Shn sts) (stk, v')›
using ssim_final'[OF Suc.prems] unfolding st ss sctrl_def by simp
show ?case
proof (cases ‹gfinal G Shn gc›)
case True
have t: ‹tstk' = tstk› using ssim_tstk Suc.prems unfolding st ss by blast
then show ?thesis using f True unfolding st ss by (auto simp: sresult_def split: list.splits)
next
case False
have r: ‹rel_option (ssim G Shn sts) (dstep G gt sts redtab st) (sstep gt sts redtab pc ss)›
by (rule ssim_step[OF Suc.prems]) (use False st in simp)
show ?thesis
proof (cases ‹dstep G gt sts redtab st›)
case None
with r have ‹sstep gt sts redtab pc ss = None› by (cases ‹sstep gt sts redtab pc ss›) auto
then show ?thesis using None False f unfolding st ss by simp
next
case (Some st')
with r obtain ss' where ss': ‹sstep gt sts redtab pc ss = Some ss'›
and sim': ‹ssim G Shn sts st' ss'› by (cases ‹sstep gt sts redtab pc ss›) auto
show ?thesis using Some ss' False f Suc.IH[OF sim'] unfolding st ss
by (simp del: srun.simps) (simp add: ss'[unfolded ss])
qed
qed
qed
end
subsection ‹Runs›
lemma srun_imp_srun⇩w⇩f:
‹srun gt sts redtab pc pf n st = Some t ⟹ srun⇩w⇩f gt sts redtab pc pf st = Some t›
by (induction n arbitrary: st) (auto simp: srun⇩w⇩f.simps split: prod.splits option.splits if_splits)
lemma srun⇩w⇩f_imp_srun_ex:
assumes ‹srun⇩w⇩f gt sts redtab pc pf st = Some t›
shows ‹∃n. srun gt sts redtab pc pf n st = Some t›
proof (rule srun⇩w⇩f.raw_induct[OF _ assms], goal_cases)
case (1 f gt sts redtab pc pf st t)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
show ?case
proof (cases ‹sfinal pf (stk, v)›)
case True
with "1"(2)[unfolded st] have ‹srun gt sts redtab pc pf 0 st = Some t›
unfolding st by simp
then show ?thesis by blast
next
case False
with "1"(2)[unfolded st] obtain st⇩1 where
sp: ‹sstep gt sts redtab pc (stk, v, tstk) = Some st⇩1›
and rec: ‹f gt sts redtab pc pf st⇩1 = Some t›
by (auto simp: bind_eq_Some_conv)
from "1"(1)[OF rec] obtain n where ‹srun gt sts redtab pc pf n st⇩1 = Some t› ..
with False sp have ‹srun gt sts redtab pc pf (Suc n) st = Some t›
unfolding st by simp
then show ?thesis by blast
qed
qed
lemma drun⇩w⇩f_srun⇩w⇩f:
assumes ‹⋀n. drun G Shn gt sts redtab n st = srun gt' sts' redtab' pc pf n ss›
shows ‹drun⇩w⇩f G Shn gt sts redtab st = srun⇩w⇩f gt' sts' redtab' pc pf ss›
proof (cases ‹drun⇩w⇩f G Shn gt sts redtab st›)
case None
show ?thesis
proof (cases ‹srun⇩w⇩f gt' sts' redtab' pc pf ss›)
case (Some t)
from srun⇩w⇩f_imp_srun_ex[OF Some] obtain n where ‹srun gt' sts' redtab' pc pf n ss = Some t› ..
with assms[of n] have ‹drun G Shn gt sts redtab n st = Some t› by simp
from drun_imp_drun⇩w⇩f[OF this] None show ?thesis by (metis option.distinct(1))
qed (simp only: None)
next
case (Some t)
from drun⇩w⇩f_imp_drun_ex[OF Some] obtain n where ‹drun G Shn gt sts redtab n st = Some t› ..
with assms[of n] have ‹srun gt' sts' redtab' pc pf n ss = Some t› by simp
from srun_imp_srun⇩w⇩f[OF this] Some show ?thesis by (simp only:)
qed
theorem dparse_eq_sparse:
assumes ‹sstatic G Shn›
shows ‹dparse G Shn w = sparse G Shn w›
unfolding dparse_def sparse_def Let_def
by (rule drun⇩w⇩f_srun⇩w⇩f, rule ssim_drun[OF assms refl refl refl refl])
(rule ssim_init[OF refl])
subsection ‹Repeated stacks: the code equation of \<^const>‹srun⇩w⇩f››
text ‹As for \<^const>‹drun⇩w⇩f›: a run that revisits a control state never
ends, and \<^const>‹srun_hist› stops it. The control state is the stack and
the input, and reduces keep the input, so the stacks seen since the last
shift are recorded. Reduces of unit and empty productions do not shrink
the stack, so a run can revisit one \<^cite>‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›; Jourdan et al.
bound the run by fuel instead.›
definition snext :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒
('m, 'ch, 't) sctl_t ⇒ ('m, 'ch, 't) sctl_t ⇒ bool› where
‹snext gt sts redtab pc pf c d ⟷
¬ sfinal pf c ∧ (∃a. sctl gt sts redtab pc c = Some (a, d))›
lemma sctl_reduce_v:
‹sctl gt sts redtab pc (stk, v) = Some (DReduce pr, stk', v') ⟹ v' = v›
unfolding sctl_def by (auto simp: Let_def split: list.splits option.splits prod.splits)
lemma srun_on_cycle_None:
assumes ‹(snext gt sts redtab pc pf)⇧+⇧+ c (sctrl st)›
‹(snext gt sts redtab pc pf)⇧+⇧+ (sctrl st) c›
shows ‹srun gt sts redtab pc pf n st = None›
using assms
proof (induction n arbitrary: st)
case (0 st)
from converse_tranclpE[OF "0.prems"(2)] obtain e where ‹snext gt sts redtab pc pf (sctrl st) e›
by blast
then show ?case unfolding snext_def sctrl_def by (cases st) auto
next
case (Suc n st)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
from converse_tranclpE[OF Suc.prems(2)] obtain e where
e: ‹snext gt sts redtab pc pf (sctrl st) e› by blast
then obtain a where nf: ‹¬ sfinal pf (stk, v)›
and sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, e)›
unfolding snext_def st sctrl_def by auto
obtain stk' v' where e': ‹e = (stk', v')› by (cases e)
let ?st' = ‹(stk', v', stree a v tstk)›
have step: ‹sstep gt sts redtab pc st = Some ?st'›
unfolding sstep_def st using sc e' by simp
have ce: ‹(snext gt sts redtab pc pf)⇧+⇧+ c (sctrl ?st')›
using tranclp.trancl_into_trancl[OF Suc.prems(1) e] e' by (simp add: sctrl_def)
have ec: ‹(snext gt sts redtab pc pf)⇧+⇧+ (sctrl ?st') c›
proof (rule converse_tranclpE[OF Suc.prems(2)])
assume ‹snext gt sts redtab pc pf (sctrl st) c›
with e have ‹e = c› unfolding snext_def by auto
then show ?thesis using Suc.prems e' by (auto simp: sctrl_def intro: tranclp_trans)
next
fix e'' assume ‹snext gt sts redtab pc pf (sctrl st) e''›
‹(snext gt sts redtab pc pf)⇧+⇧+ e'' c›
with e have ‹e'' = e› unfolding snext_def by auto
then show ?thesis using ‹(snext gt sts redtab pc pf)⇧+⇧+ e'' c› e'
by (simp add: sctrl_def)
qed
have ‹srun gt sts redtab pc pf (Suc n) st = srun gt sts redtab pc pf n ?st'›
using nf step unfolding st by simp
also have ‹… = None› by (rule Suc.IH[OF ce ec])
finally show ?case .
qed
lemma srun⇩w⇩f_on_cycle_None:
assumes ‹(snext gt sts redtab pc pf)⇧+⇧+ c (sctrl st)›
‹(snext gt sts redtab pc pf)⇧+⇧+ (sctrl st) c›
shows ‹srun⇩w⇩f gt sts redtab pc pf st = None›
using srun⇩w⇩f_imp_srun_ex[of gt sts redtab pc pf st] srun_on_cycle_None[OF assms]
by (cases ‹srun⇩w⇩f gt sts redtab pc pf st›) auto
definition shist_ok :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list list ⇒ ('n × ('n, 't) rhs) list list ⇒ bool list ⇒ nat list list ⇒
('m, 'ch, 'n, 't) sst ⇒ bool› where
‹shist_ok gt sts redtab pc pf seen st ⟷
(∀k ∈ set seen. (snext gt sts redtab pc pf)⇧+⇧+ (k, fst (snd st)) (sctrl st))›
lemma shist_ok_Nil [simp]: ‹shist_ok gt sts redtab pc pf [] st›
unfolding shist_ok_def by simp
lemma srun_hist_imp_srun⇩w⇩f:
assumes h: ‹srun_hist ctl fin seen st = Some t›
and c: ‹ctl = sctl gt sts redtab pc› and f: ‹fin = sfinal pf›
shows ‹srun⇩w⇩f gt sts redtab pc pf st = Some t›
proof -
have ‹ctl = sctl gt sts redtab pc ⟶ fin = sfinal pf ⟶
srun⇩w⇩f gt sts redtab pc pf st = Some t›
proof (rule srun_hist.raw_induct[OF _ h], goal_cases)
case (1 f ctl fin seen st t)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
show ?case
proof (intro impI)
assume c: ‹ctl = sctl gt sts redtab pc› and fi: ‹fin = sfinal pf›
show ‹srun⇩w⇩f gt sts redtab pc pf st = Some t›
proof (cases ‹sfinal pf (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (simp add: srun⇩w⇩f.simps)
next
case False
from False "1"(2) obtain a stk' v' where
sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, stk', v')›
and rec: ‹f ctl fin (if a = DShift then [] else stk # seen)
(stk', v', stree a v tstk) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv split: if_splits)
from "1"(1)[OF rec] c fi
have ‹srun⇩w⇩f gt sts redtab pc pf (stk', v', stree a v tstk) = Some t› by blast
with False sc show ?thesis unfolding st by (subst srun⇩w⇩f.simps) (simp add: sstep_def)
qed
qed
qed
with c f show ?thesis by blast
qed
lemma srun_imp_srun_hist:
assumes ‹srun gt sts redtab pc pf n st = Some t›
and ‹shist_ok gt sts redtab pc pf seen st›
shows ‹srun_hist (sctl gt sts redtab pc) (sfinal pf) seen st = Some t›
using assms
proof (induction n arbitrary: st seen)
case (0 st seen)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
show ?case using "0.prems"(1) unfolding st
by (subst srun_hist.simps) (auto split: if_splits)
next
case (Suc n st seen)
obtain stk v tstk where st: ‹st = (stk, v, tstk)› by (cases st)
show ?case
proof (cases ‹sfinal pf (stk, v)›)
case True
with Suc.prems(1) show ?thesis unfolding st by (subst srun_hist.simps) simp
next
case False
with Suc.prems(1) obtain st⇩1 where sp: ‹sstep gt sts redtab pc st = Some st⇩1›
and rec: ‹srun gt sts redtab pc pf n st⇩1 = Some t›
unfolding st by (auto split: option.splits)
from sp obtain a stk' v' where sc: ‹sctl gt sts redtab pc (stk, v) = Some (a, stk', v')›
and st1: ‹st⇩1 = (stk', v', stree a v tstk)›
unfolding st sstep_def by (auto split: prod.splits)
have r: ‹snext gt sts redtab pc pf (stk, v) (stk', v')›
unfolding snext_def using False sc by blast
have nk: ‹stk ∉ set seen›
proof
assume ‹stk ∈ set seen›
with Suc.prems(2) have c: ‹(snext gt sts redtab pc pf)⇧+⇧+ (stk, v) (sctrl st)›
unfolding shist_ok_def st by simp
then have ‹(snext gt sts redtab pc pf)⇧+⇧+ (sctrl st) (sctrl st)›
unfolding st sctrl_def by simp
from srun⇩w⇩f_on_cycle_None[OF this this] srun_imp_srun⇩w⇩f[OF Suc.prems(1)] show False by simp
qed
have ok: ‹shist_ok gt sts redtab pc pf (if a = DShift then [] else stk # seen) st⇩1›
proof (cases ‹a = DShift›)
case True then show ?thesis by simp
next
case nsh: False
then obtain pr where a: ‹a = DReduce pr› by (cases a) auto
have vv: ‹v' = v› using sctl_reduce_v sc[unfolded a] .
show ?thesis unfolding shist_ok_def st1 sctrl_def
proof (intro ballI)
fix k assume ‹k ∈ set (if a = DShift then [] else stk # seen)›
with nsh have ‹k = stk ∨ k ∈ set seen› by simp
then show ‹(snext gt sts redtab pc pf)⇧+⇧+ (k, fst (snd (stk', v', stree a v tstk)))
(case (stk', v', stree a v tstk) of (stk, v, tstk) ⇒ (stk, v))›
proof
assume ‹k = stk›
then show ?thesis using r vv by simp
next
assume ‹k ∈ set seen›
with Suc.prems(2) have ‹(snext gt sts redtab pc pf)⇧+⇧+ (k, v) (stk, v)›
unfolding shist_ok_def st sctrl_def by simp
then show ?thesis using r vv by (simp add: tranclp.trancl_into_trancl)
qed
qed
qed
from Suc.IH[OF rec ok] have ih: ‹srun_hist (sctl gt sts redtab pc) (sfinal pf)
(if a = DShift then [] else stk # seen) st⇩1 = Some t› .
show ?thesis using False nk sc ih unfolding st st1 by (subst srun_hist.simps) simp
qed
qed
theorem srun⇩w⇩f_code [code]:
‹srun⇩w⇩f gt sts redtab pc pf st =
srun_hist (sctl gt sts redtab pc) (sfinal pf) [] st›
proof (cases ‹srun_hist (sctl gt sts redtab pc) (sfinal pf) [] st›)
case None
show ?thesis
proof (cases ‹srun⇩w⇩f gt sts redtab pc pf st›)
case (Some t)
from srun⇩w⇩f_imp_srun_ex[OF Some] obtain n where ‹srun gt sts redtab pc pf n st = Some t› ..
from srun_imp_srun_hist[OF this shist_ok_Nil] None show ?thesis by simp
qed (simp only: None)
next
case (Some t)
from srun_hist_imp_srun⇩w⇩f[OF Some refl refl] Some show ?thesis by simp
qed
subsection ‹Table inlining›
text ‹The counterpart of \<^text>‹dparse_via_tables›: under the static
conditions the parser runs the simple driver on precomputed tables.›
lemma dparse_via_simple_tables:
assumes static: ‹sstatic G Shn›
and st: ‹pr0_states G Shn = sts› and gt: ‹pgtab G sts = gtab›
and rt: ‹red_buckets G Shn (length sts) = redtab›
and pcs: ‹pcomps G sts = pc› and pfs: ‹pfins Shn sts = pf›
and i0: ‹st_find sts (lr0_start G Shn) = i⇩0›
shows ‹dparse G Shn w = srun⇩w⇩f gtab sts redtab pc pf ([i⇩0], w, [])›
unfolding dparse_eq_sparse[OF static] sparse_def sinit_def Let_def
by (simp add: st gt rt pcs pfs i0)
section ‹Indexed tables›
text ‹The step \<^const>‹sctl› looks up goto rows by symbol, compares productions
in the reduce cells, and indexes lists. The indexed step below does the same
lookups on tables computed from those of \<^const>‹sctl› at definition time:
productions and nonterminals are numbered, goto rows are keyed by the
terminal or by the number of the nonterminal (the usual split into an action
and a goto table \<^cite>‹‹Sect.~2.4› in "jourdan2012-validating-lr1"›), the length of the state list
is stored, and the tables are immutable arrays. It computes the same function
(\<^text>‹isctl_eq›).›
lemma la_tindex_nth: ‹x ∈ set xs ⟹ la_tindex xs x < length xs ∧ xs ! la_tindex xs x = x›
by (induction xs) auto
lemma la_tindex_inj:
‹x ∈ set xs ⟹ y ∈ set xs ⟹ la_tindex xs x = la_tindex xs y ⟷ x = y›
by (metis la_tindex_nth)
definition tm_row :: ‹(('n, 't) sym × nat) list ⇒ ('t × nat) list› where
‹tm_row row = concat (map (λ(X, j). case X of Tm a ⇒ [(a, j)] | Nt _ ⇒ []) row)›
definition nt_row :: ‹'n list ⇒ (('n, 't) sym × nat) list ⇒ (nat × nat) list› where
‹nt_row nms row = concat (map (λ(X, j). case X of
Nt B ⇒ if B ∈ set nms then [(la_tindex nms B, j)] else [] | Tm _ ⇒ []) row)›
lemma map_of_tm_row: ‹map_of (tm_row row) a = map_of row (Tm a)›
unfolding tm_row_def by (induction row) (auto split: sym.splits)
lemma map_of_nt_row:
‹A ∈ set nms ⟹ map_of (nt_row nms row) (la_tindex nms A) = map_of row (Nt A)›
unfolding nt_row_def by (induction row) (auto split: sym.splits simp: la_tindex_inj)
text ‹The reduce cells of a coarse state, by production number.›
definition cell_row :: ‹('n × ('n, 't) rhs) list ⇒ nat ⇒ ('n, 't) lacell list ⇒
(nat × 't option) list› where
‹cell_row prs i cells = concat (map (λ(i', itm, t, τ).
if i' = i ∧ snd itm = length (snd (fst itm)) ∧ fst itm ∈ set prs
then [(la_tindex prs (fst itm), t)] else []) cells)›
text ‹The tables as lists, which evaluation computes, and as arrays.›