Theory LR_Vec
theory LR_Vec
imports LR_Sparse
begin
section ‹A state-indexed driver with precomputed closures›
text ‹The set-anchored drivers of \<^text>‹LR_Driver› and \<^text>‹LR_Sparse› compute a
closure after every step as a fixpoint over the kernel's anchor sets. The
closure's ∗‹shape› is a property of the LR(0) state alone: which productions
get a slot, and from which kernel item each slot's anchors descend, through
which chain of right-hand-side relations. This follows Adams
\<^cite>‹‹Sect.~5.8› in "adams2013"›: only the items before the closure keep
indentation sets, and the closure items carry the relation that leads to
them. Only the anchor sets are
input-dependent, and a chain of relations acts on an anchor set as one of three
transfers: the identity (\<^const>‹Eq›), the up-set from the least anchor plus an
offset (\<^const>‹Gt›, \<^const>‹Ge›), or the up-set from a constant
(\<^const>‹Any›). The driver of this theory tabulates, per state, its items,
the transfer from each kernel item to each slot, the predecessor of each
kernel item under each symbol, and its reduce cells, so that a step does no
search: it indexes.
The driver returns what \<^const>‹dparse› returns on every input, for a grammar
whose automaton is deterministic (\<^const>‹mdet›). Without determinism the two
could pick different reduce candidates, since this driver's items are in table
order rather than in the order the kernels happen to arrive in.›
subsection ‹Canonical anchor sets›
text ‹\<^const>‹irep_union› concatenates and \<^const>‹irep_pre› materialises intervals,
so anchor sets of the running drivers carry duplicates. The operations here
keep a set sorted and duplicate-free, with the finite part of an
\<^const>‹UpRep› below its bound; only the set an operation denotes enters the
correctness argument.›
fun merge :: ‹nat list ⇒ nat list ⇒ nat list› where
‹merge [] ys = ys›
| ‹merge xs [] = xs›
| ‹merge (x # xs) (y # ys) =
(if x < y then x # merge xs (y # ys)
else if y < x then y # merge (x # xs) ys else x # merge xs ys)›
lemma set_merge [simp]: ‹set (merge xs ys) = set xs ∪ set ys›
by (induction xs ys rule: merge.induct) auto
fun cunion :: ‹indrep ⇒ indrep ⇒ indrep› where
‹cunion (FinRep xs) (FinRep ys) = FinRep (merge xs ys)›
| ‹cunion (FinRep xs) (UpRep ys n) = UpRep (filter (λi. i < n) (merge xs ys)) n›
| ‹cunion (UpRep xs n) (FinRep ys) = UpRep (filter (λi. i < n) (merge xs ys)) n›
| ‹cunion (UpRep xs n) (UpRep ys m) = UpRep (filter (λi. i < min n m) (merge xs ys)) (min n m)›
lemma cunion_set [simp]: ‹irep_set (cunion R S) = irep_set R ∪ irep_set S›
by (cases R; cases S) auto
text ‹The set with the up-set from ‹t› added.›
fun cup :: ‹nat ⇒ indrep ⇒ indrep› where
‹cup t (FinRep xs) = UpRep (filter (λi. i < t) xs) t›
| ‹cup t (UpRep xs n) = UpRep (filter (λi. i < min t n) xs) (min t n)›
lemma cup_set [simp]: ‹irep_set (cup t R) = irep_set R ∪ {m. t ≤ m}›
by (cases R) auto
fun cinter :: ‹indrep ⇒ indrep ⇒ indrep› where
‹cinter (FinRep xs) S = FinRep (filter (λi. irep_mem i S) xs)›
| ‹cinter (UpRep xs n) (FinRep ys) = FinRep (filter (λi. irep_mem i (UpRep xs n)) ys)›
| ‹cinter (UpRep xs n) (UpRep ys m) =
UpRep (filter (λi. i < max n m)
(merge (filter (λi. irep_mem i (UpRep ys m)) xs) (filter (λi. irep_mem i (UpRep xs n)) ys)))
(max n m)›
lemma cinter_set [simp]: ‹irep_set (cinter R S) = irep_set R ∩ irep_set S›
by (cases R; cases S) auto
text ‹The elements below a bound, as a finite set.›
fun cbelow :: ‹nat ⇒ indrep ⇒ indrep› where
‹cbelow b (FinRep xs) = FinRep (filter (λi. i < b) xs)›
| ‹cbelow b (UpRep xs n) = FinRep (filter (λi. i < b) xs @ [n..<b])›
lemma cbelow_set [simp]: ‹irep_set (cbelow b R) = irep_set R ∩ {i. i < b}›
by (cases R) auto
lemma fold_max_lt_iff: ‹i < fold max ys a ⟷ i < a ∨ (∃y ∈ set ys. i < y)› for ys :: ‹nat list›
using Max.set_eq_fold[of a ys, symmetric] by (simp add: Max_gr_iff)
lemma fold_max_le_iff: ‹i ≤ fold max ys a ⟷ i ≤ a ∨ (∃y ∈ set ys. i ≤ y)› for ys :: ‹nat list›
using Max.set_eq_fold[of a ys, symmetric] by (simp add: Max_ge_iff)
lemma up_unbounded: ‹∃j ∈ A ∪ Collect ((≤) n). x < j› ‹∃j ∈ A ∪ Collect ((≤) n). x ≤ j›
for n x :: nat
by (rule bexI[of _ ‹max (Suc x) n›]; simp)+
text ‹The parent anchors in ‹R› compatible with a child anchor in ‹RA›:
\<^term>‹irep_inter R (irep_pre q RA)› without materialising the preimage.›
definition cpre :: ‹irel ⇒ indrep ⇒ indrep ⇒ indrep› where
‹cpre q RA R = (case q of
Eq ⇒ cinter R RA
| Gt ⇒ (case RA of FinRep ys ⇒ (if ys = [] then FinRep [] else cbelow (fold max ys 0) R)
| UpRep _ _ ⇒ R)
| Ge ⇒ (case RA of FinRep ys ⇒ (if ys = [] then FinRep [] else cbelow (Suc (fold max ys 0)) R)
| UpRep _ _ ⇒ R)
| Any ⇒ (if irep_nonempty RA then R else FinRep []))›
lemma cpre_set [simp]: ‹irep_set (cpre q RA R) = irep_set R ∩ irep_set (irep_pre q RA)›
proof (cases q)
case Gt
then show ?thesis
by (cases RA) (auto simp: cpre_def fold_max_lt_iff up_unbounded simp del: irep_pre.simps)
next
case Ge
then show ?thesis
by (cases RA) (auto simp: cpre_def fold_max_le_iff less_Suc_eq_le up_unbounded ex_in_conv simp del: irep_pre.simps)
qed (auto simp: cpre_def)
subsection ‹Anchor-set transfers›
text ‹A transfer is a join of up to three parts: the identity, the up-set from
the least anchor shifted by ‹d›, and the up-set from a constant ‹d› (present only
when the set is non-empty). The relations of the grammar are transfers, and
transfers are closed under join and composition. They stand in for the
closure of the indentation relations under composition and union
\<^cite>‹‹Lemmas~2 and~3› in "adams2013"›, where a union holds each form at most once.
Unlike the relations there, a transfer acts on anchor sets.›
type_synonym eff = ‹bool × nat option × nat option›
definition sh :: ‹nat ⇒ nat set ⇒ nat set› where ‹sh d S = {m. ∃j ∈ S. j + d ≤ m}›
definition cn :: ‹nat ⇒ nat set ⇒ nat set› where ‹cn d S = {m. S ≠ {} ∧ d ≤ m}›
definition osh :: ‹nat option ⇒ nat set ⇒ nat set› where
‹osh s S = (case s of None ⇒ {} | Some d ⇒ sh d S)›
definition ocn :: ‹nat option ⇒ nat set ⇒ nat set› where
‹ocn c S = (case c of None ⇒ {} | Some d ⇒ cn d S)›
fun eff_set :: ‹eff ⇒ nat set ⇒ nat set› where
‹eff_set (i, s, c) S = (if i then S else {}) ∪ osh s S ∪ ocn c S›
abbreviation ebot :: eff where ‹ebot ≡ (False, None, None)›
abbreviation eid :: eff where ‹eid ≡ (True, None, None)›
fun of_rel :: ‹irel ⇒ eff› where
‹of_rel Eq = (True, None, None)›
| ‹of_rel Gt = (False, Some 1, None)›
| ‹of_rel Ge = (False, Some 0, None)›
| ‹of_rel Any = (False, None, Some 0)›
lemma eff_set_of_rel: ‹eff_set (of_rel q) S = {j. ∃i ∈ S. irel_sat q j i}›
by (cases q) (auto simp: osh_def ocn_def sh_def cn_def Suc_le_eq)
lemma eff_set_img: ‹eff_set (of_rel q) (irep_set R) = irep_set (irep_img q R)›
by (simp add: eff_set_of_rel)
lemma osh_simps [simp]: ‹osh None S = {}› ‹osh (Some d) S = sh d S›
and ocn_simps [simp]: ‹ocn None S = {}› ‹ocn (Some d) S = cn d S›
by (simp_all add: osh_def ocn_def)
lemma sh_empty [simp]: ‹sh d {} = {}› and cn_empty [simp]: ‹cn d {} = {}›
by (simp_all add: sh_def cn_def)
lemma osh_empty [simp]: ‹osh s {} = {}› and ocn_empty [simp]: ‹ocn c {} = {}›
by (simp_all add: osh_def ocn_def split: option.splits)
lemma eff_set_empty [simp]: ‹eff_set e {} = {}›
by (cases e) simp
lemma eff_set_bot [simp]: ‹eff_set ebot S = {}›
by (simp add: osh_def ocn_def)
lemma eff_set_id [simp]: ‹eff_set eid S = S›
by (simp add: osh_def ocn_def)
lemma sh_UN: ‹sh d (⋃ 𝒜) = ⋃ (sh d ` 𝒜)› and cn_UN: ‹cn d (⋃ 𝒜) = ⋃ (cn d ` 𝒜)›
unfolding sh_def cn_def by auto
lemma osh_UN: ‹osh s (⋃ 𝒜) = ⋃ (osh s ` 𝒜)› and ocn_UN: ‹ocn c (⋃ 𝒜) = ⋃ (ocn c ` 𝒜)›
unfolding osh_def ocn_def by (auto simp: sh_UN cn_UN split: option.splits)
lemma eff_set_UN: ‹eff_set e (⋃ 𝒜) = ⋃ (eff_set e ` 𝒜)›
by (cases e) (auto simp: osh_UN ocn_UN)
lemma eff_set_Un: ‹eff_set e (A ∪ B) = eff_set e A ∪ eff_set e B›
using eff_set_UN[of e ‹{A, B}›] by simp
lemma eff_set_mono: ‹A ⊆ B ⟹ eff_set e A ⊆ eff_set e B›
by (metis eff_set_Un subset_Un_eq)
text ‹Join: the parts of both. The joins of the shifts and of the constants are
their minima, since a smaller offset gives a larger up-set.›
definition omin :: ‹nat option ⇒ nat option ⇒ nat option› where
‹omin a b = (case a of None ⇒ b | Some x ⇒ (case b of None ⇒ Some x | Some y ⇒ Some (min x y)))›
lemma sh_min: ‹sh (min x y) S = sh x S ∪ sh y S› and cn_min: ‹cn (min x y) S = cn x S ∪ cn y S›
unfolding sh_def cn_def min_def
by (auto 0 3 intro: le_trans add_left_mono) (meson add_le_cancel_left le_trans nat_le_linear)
lemma omin_simps [simp]:
‹omin None b = b› ‹omin a None = a› ‹omin (Some x) (Some y) = Some (min x y)›
by (simp_all add: omin_def split: option.split)
lemma osh_omin: ‹osh (omin a b) S = osh a S ∪ osh b S›
and ocn_omin: ‹ocn (omin a b) S = ocn a S ∪ ocn b S›
unfolding osh_def ocn_def omin_def by (auto simp: sh_min cn_min split: option.splits)
fun ejoin :: ‹eff ⇒ eff ⇒ eff› where
‹ejoin (i⇩1, s⇩1, c⇩1) (i⇩2, s⇩2, c⇩2) = (i⇩1 ∨ i⇩2, omin s⇩1 s⇩2, omin c⇩1 c⇩2)›
lemma eff_set_join: ‹eff_set (ejoin e f) S = eff_set e S ∪ eff_set f S›
by (cases e; cases f) (auto simp: osh_omin ocn_omin)
lemma eff_set_fold_ejoin: ‹eff_set (fold ejoin xs a) S = eff_set a S ∪ (⋃x ∈ set xs. eff_set x S)›
by (induction xs arbitrary: a) (auto simp: eff_set_join)
text ‹Composition, ‹e⇩2› after ‹e⇩1›: a shift after a shift adds the offsets, a
constant after anything stays, a shift after a constant is a constant.›
lemma sh_sh: ‹sh d⇩2 (sh d⇩1 S) = sh (d⇩1 + d⇩2) S›
unfolding sh_def by (auto 0 3 intro: le_trans[OF add_right_mono] simp: add.assoc[symmetric])
lemma cn_sh: ‹cn d⇩2 (sh d⇩1 S) = cn d⇩2 S›
unfolding sh_def cn_def by auto
lemma sh_cn: ‹sh d⇩2 (cn d⇩1 S) = cn (d⇩1 + d⇩2) S›
unfolding sh_def cn_def by auto
lemma cn_cn: ‹cn d⇩2 (cn d⇩1 S) = cn d⇩2 S›
unfolding cn_def by auto
lemma sh_absorb: ‹d ≤ d' ⟹ sh d' S ⊆ sh d S› and cn_absorb: ‹d ≤ d' ⟹ cn d' S ⊆ cn d S›
unfolding sh_def cn_def by (auto intro: le_trans[OF add_left_mono])
text ‹What a transfer ‹e› does after a shift, and after a constant, by ‹d›.›
fun aft_sh :: ‹nat ⇒ eff ⇒ eff› where
‹aft_sh d (i, s, c) = (False, omin (if i then Some d else None) (map_option ((+) d) s), c)›
fun aft_cn :: ‹nat ⇒ eff ⇒ eff› where
‹aft_cn d (i, s, c) =
(False, None, omin (if i then Some d else None) (omin (map_option ((+) d) s) c))›
lemma eff_set_after_sh: ‹eff_set e (sh d S) = eff_set (aft_sh d e) S›
proof (cases e)
case (fields i s c)
then show ?thesis
using sh_absorb[of d ‹d + _› S]
by (cases i; cases s; cases c) (auto simp: sh_sh cn_sh sh_min)
qed
lemma eff_set_after_cn: ‹eff_set e (cn d S) = eff_set (aft_cn d e) S›
proof (cases e)
case (fields i s c)
then show ?thesis
using cn_absorb[of d ‹d + _› S]
by (cases i; cases s; cases c) (auto simp: sh_cn cn_cn cn_min)
qed
fun ecomp :: ‹eff ⇒ eff ⇒ eff› where
‹ecomp e⇩2 (i⇩1, s⇩1, c⇩1) =
ejoin (if i⇩1 then e⇩2 else ebot)
(ejoin (case s⇩1 of None ⇒ ebot | Some d ⇒ aft_sh d e⇩2)
(case c⇩1 of None ⇒ ebot | Some d ⇒ aft_cn d e⇩2))›
lemma eff_set_comp: ‹eff_set (ecomp e⇩2 e⇩1) S = eff_set e⇩2 (eff_set e⇩1 S)›
proof (cases e⇩1)
case (fields i s c)
have ‹eff_set e⇩2 (osh s S) = eff_set (case s of None ⇒ ebot | Some d ⇒ aft_sh d e⇩2) S›
by (cases s) (simp_all add: eff_set_after_sh)
moreover have ‹eff_set e⇩2 (ocn c S) = eff_set (case c of None ⇒ ebot | Some d ⇒ aft_cn d e⇩2) S›
by (cases c) (simp_all add: eff_set_after_cn)
moreover have ‹eff_set e⇩2 (if i then S else {}) = eff_set (if i then e⇩2 else ebot) S›
by simp
ultimately show ?thesis
by (simp only: fields ecomp.simps eff_set.simps[of i s c] eff_set_Un eff_set_join Un_assoc)
qed
subsection ‹The transfer order and its well-foundedness›
text ‹A transfer below another denotes a subset for every argument. Every
ascending chain is finite: the identity is added at most once, and each offset,
once present, only decreases.›
fun ole :: ‹nat option ⇒ nat option ⇒ bool› where
‹ole None _ = True›
| ‹ole (Some d) None = False›
| ‹ole (Some d) (Some d') = (d' ≤ d)›
fun ele :: ‹eff ⇒ eff ⇒ bool› where
‹ele (i⇩1, s⇩1, c⇩1) (i⇩2, s⇩2, c⇩2) = ((i⇩1 ⟶ i⇩2) ∧ ole s⇩1 s⇩2 ∧ ole c⇩1 c⇩2)›
lemma ole_refl [simp]: ‹ole a a›
by (cases a) simp_all
lemma ole_trans: ‹ole a b ⟹ ole b c ⟹ ole a c›
by (cases a; cases b; cases c) simp_all
lemma ole_omin1: ‹ole a (omin a b)› and ole_omin2: ‹ole b (omin a b)›
by (cases a; cases b; simp add: omin_def)+
lemma ele_refl [simp]: ‹ele e e›
by (cases e) simp
lemma ele_trans: ‹ele e f ⟹ ele f g ⟹ ele e g›
by (cases e; cases f; cases g) (auto intro: ole_trans)
lemma ele_join2: ‹ele f (ejoin e f)›
by (cases e; cases f; simp add: ole_omin2)
lemma ele_fold_ejoin: ‹ele a (fold ejoin xs a)›
proof -
have ‹ele b a ⟹ ele b (fold ejoin xs a)› for b
proof (induction xs arbitrary: a)
case (Cons x xs)
from Cons.prems have ‹ele b (ejoin x a)› by (rule ele_trans) (rule ele_join2)
then have ‹ele b (fold ejoin xs (ejoin x a))› by (rule Cons.IH)
then show ?case by simp
qed simp
then show ?thesis by simp
qed
fun omeas :: ‹nat option ⇒ nat × nat› where
‹omeas None = (1, 0)›
| ‹omeas (Some d) = (0, d)›
lemma ole_omeas:
‹ole a b ⟹ a ≠ b ⟹ (omeas b, omeas a) ∈ less_than <*lex*> less_than›
by (cases a; cases b) auto
text ‹An increase raises the identity flag, or keeps it and decreases the shift,
or keeps both and decreases the constant.›
lemma wf_eff_inc: ‹wf {(f, e). ele e f ∧ e ≠ f}›
proof -
have wo: ‹wf {(b, a). ole a b ∧ a ≠ b}›
by (rule wf_subset[OF wf_inv_image[OF wf_lex_prod[OF wf_less_than wf_less_than]], of _ omeas])
(auto dest: ole_omeas)
have wb: ‹wf {(True, False)}›
by (rule wf_subset[OF wf_inv_image[OF wf_less_than], of _ ‹λb. if b then 0 else 1›]) auto
have ‹{(f, e). ele e f ∧ e ≠ f} ⊆
{(True, False)} <*lex*> ({(b, a). ole a b ∧ a ≠ b} <*lex*> {(b, a). ole a b ∧ a ≠ b})›
by clarsimp (metis (full_types))
then show ?thesis by (rule wf_subset[rotated]) (intro wf_lex_prod wb wo)
qed
lemma list_all2_ne_lex:
assumes ‹list_all2 ele xs ys› and ‹xs ≠ ys›
shows ‹(ys, xs) ∈ lex {(f, e). ele e f ∧ e ≠ f}›
using assms
proof (induction rule: list_all2_induct)
case (Cons x xs y ys)
show ?case
proof (cases ‹x = y›)
case True
with Cons have ‹(ys, xs) ∈ lex {(f, e). ele e f ∧ e ≠ f}› by simp
then show ?thesis unfolding True lex_conv
by clarsimp (metis Cons_eq_appendI)
next
case False
then have ‹ele x y ∧ x ≠ y› using Cons.hyps(1) by blast
moreover have ‹y # ys = [] @ y # ys› ‹x # xs = [] @ x # xs› by simp_all
moreover have ‹length (y # ys) = length (x # xs)›
using list_all2_lengthD[OF Cons.hyps(2)] by simp
ultimately show ?thesis unfolding lex_conv by (simp only: mem_Collect_eq case_prod_conv) blast
qed
qed simp
lemma wf_eff_list_inc: ‹wf {(ys, xs). list_all2 ele xs ys ∧ xs ≠ ys}›
by (rule wf_subset[OF wf_lex[OF wf_eff_inc]]) (auto simp: list_all2_ne_lex)
declare eff_set.simps [simp del]
subsection ‹The closure graph›
text ‹A closure round sends the anchor set of a nonterminal ‹c› through the
first symbol of each production of ‹c›: an edge to ‹a›, labelled with the
relation of that symbol. The table invariant ‹ntl_ok› says that only
nonterminals with a number have productions.›
definition tedge :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ irel ⇒ bool› where
‹tedge T c a q ⟷ c < s_np T ∧ a < s_np T ∧
(∃k ∈ set (ntl T c). ∃rest. rrhs (s_recs T !! k) = (Nt a, q) # rest)›
definition ntl_ok :: ‹('n, 't) stab ⇒ bool› where
‹ntl_ok T ⟷ (∀c. s_np T ≤ c ⟶ ntl T c = [])›
lemma ntl_ok_mk_stab: ‹ntl_ok (mk_stab G Shn gt sts redtab)›
unfolding ntl_ok_def ntl_mk_stab
by (auto intro!: filter_False) (metis le_trans lids_nth_le not_le)
lemma nx_set_slot:
‹nx_set np a (r, 0, R) =
⋃{irep_set (irep_img q R) |q. a < np ∧ (∃rest. rrhs r = (Nt a, q) # rest)}›
by (auto simp: nx_set_def sitem_nx_def neq_Nil_conv split: list.splits sym.splits prod.splits)
lemma sslot_kset_tedge:
assumes ‹ntl_ok T›
shows ‹kset a (sslot_nx T c R) = ⋃{eff_set (of_rel q) (irep_set R) |q. tedge T c a q}›
proof (cases ‹c < s_np T›)
case True
have ‹kset a (sslot_nx T c R) = ⋃ (nx_set (s_np T) a ` (λk. (s_recs T !! k, 0, R)) ` set (ntl T c))›
unfolding sslot_nx_def
using map_filter_nx_set[of a ‹s_np T› ‹map (λk. (s_recs T !! k, 0, R)) (ntl T c)›]
by (simp add: map_filter_map o_def)
also have ‹… = ⋃{eff_set (of_rel q) (irep_set R) |q. tedge T c a q}›
using True by (auto simp: nx_set_slot tedge_def eff_set_img)
finally show ?thesis .
next
case False
with assms show ?thesis by (simp add: ntl_ok_def sslot_nx_def tedge_def List.map_filter_def)
qed
text ‹A round on anchor-set assignments: the kernel's sets, and every edge's
image of the set at its source.›
definition sem_round :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ (nat ⇒ nat set) ⇒ nat ⇒ nat set› where
‹sem_round T kn ν a = kset a kn ∪ ⋃{eff_set (of_rel q) (ν c) |c q. tedge T c a q}›
lemma sem_round_mono: ‹(⋀c. ν c ⊆ μ c) ⟹ sem_round T kn ν a ⊆ sem_round T kn μ a›
proof -
assume le: ‹⋀c. ν c ⊆ μ c›
have ‹eff_set (of_rel q) (ν c) ⊆ eff_set (of_rel q) (μ c)› for q c by (rule eff_set_mono[OF le])
then show ?thesis unfolding sem_round_def by fast
qed
lemma UN_keys_slk:
assumes d: ‹distinct (map fst N)› and f: ‹⋀c. f c {} = {}›
shows ‹(⋃(c, R) ∈ set N. f c (irep_set R)) = (⋃c. f c (irep_set (slk N c)))›
proof (intro equalityI subsetI)
fix x assume ‹x ∈ (⋃(c, R) ∈ set N. f c (irep_set R))›
then obtain c R where ‹(c, R) ∈ set N› ‹x ∈ f c (irep_set R)› by blast
with d have ‹x ∈ f c (irep_set (slk N c))› by (simp add: slk_in)
then show ‹x ∈ (⋃c. f c (irep_set (slk N c)))› by blast
next
fix x assume ‹x ∈ (⋃c. f c (irep_set (slk N c)))›
then obtain c where x: ‹x ∈ f c (irep_set (slk N c))› by blast
show ‹x ∈ (⋃(c, R) ∈ set N. f c (irep_set R))›
proof (cases ‹c ∈ fst ` set N›)
case True
then obtain R where ‹(c, R) ∈ set N› by force
with d x show ?thesis by (auto simp: slk_in)
next
case False
with x f show ?thesis by (simp add: slk_notin)
qed
qed
lemma sround_distinct: ‹distinct (map fst (sround T kn N))›
unfolding sround_def by (rule fold_sins_distinct) simp
lemma siter_distinct: ‹distinct (map fst (siter T kn t))›
by (cases t) (simp_all add: sround_distinct)
lemma sround_sem:
assumes ok: ‹ntl_ok T› and d: ‹distinct (map fst N)›
shows ‹irep_set (slk (sround T kn N) a) = sem_round T kn (λc. irep_set (slk N c)) a›
proof -
let ?f = ‹λc S. ⋃{eff_set (of_rel q) S |q. tedge T c a q}›
have ‹irep_set (slk (sround T kn N) a) = kset a kn ∪ (⋃(c, R) ∈ set N. kset a (sslot_nx T c R))›
by (simp add: sround_def fold_sins_set kset_filter_ne kset_concat_map)
also have ‹(⋃(c, R) ∈ set N. kset a (sslot_nx T c R)) = (⋃(c, R) ∈ set N. ?f c (irep_set R))›
by (simp add: sslot_kset_tedge[OF ok])
also have ‹… = (⋃c. ?f c (irep_set (slk N c)))›
by (rule UN_keys_slk[OF d]) auto
finally show ?thesis by (auto simp: sem_round_def)
qed
subsection ‹Paths and their transfers›
text ‹The transfer of a path in the closure graph, from a kernel nonterminal
‹b›: the composition of the relations on its edges.›
inductive treach :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ eff ⇒ bool› for T b where
treach_refl: ‹treach T b b eid›
| treach_edge: ‹treach T b c e ⟹ tedge T c a q ⟹ treach T b a (ecomp (of_rel q) e)›
definition tpaths :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒ nat ⇒ nat set› where
‹tpaths T kn a = ⋃{eff_set e (irep_set R) |b R e. (b, R) ∈ set kn ∧ treach T b a e}›
lemma kset_le_tpaths: ‹kset a kn ⊆ tpaths T kn a›
proof
fix x assume ‹x ∈ kset a kn›
then obtain R where R: ‹(a, R) ∈ set kn› and x: ‹x ∈ irep_set R› by (auto simp: kset_def)
have ‹eff_set eid (irep_set R) ∈ {eff_set e (irep_set R') |b R' e. (b, R') ∈ set kn ∧ treach T b a e}›
using R treach_refl[of T a] by blast
with x show ‹x ∈ tpaths T kn a› unfolding tpaths_def eff_set_id by blast
qed
lemma sem_round_tpaths: ‹sem_round T kn (tpaths T kn) a ⊆ tpaths T kn a›
proof -
have ‹eff_set (of_rel q) (tpaths T kn c) ⊆ tpaths T kn a› if ‹tedge T c a q› for c q
proof
fix x assume ‹x ∈ eff_set (of_rel q) (tpaths T kn c)›
then obtain b R e where ‹(b, R) ∈ set kn› ‹treach T b c e›
‹x ∈ eff_set (of_rel q) (eff_set e (irep_set R))›
unfolding tpaths_def by (auto simp: eff_set_UN)
with that show ‹x ∈ tpaths T kn a›
unfolding tpaths_def by (blast intro: treach_edge eff_set_comp[THEN equalityD2, THEN subsetD])
qed
then show ?thesis unfolding sem_round_def using kset_le_tpaths by blast
qed
lemma siter_le_tpaths:
assumes ‹ntl_ok T›
shows ‹irep_set (slk (siter T kn t) a) ⊆ tpaths T kn a›
proof (induction t arbitrary: a)
case (Suc t)
have ‹irep_set (slk (siter T kn (Suc t)) a) = sem_round T kn (λc. irep_set (slk (siter T kn t) c)) a›
by (simp add: sround_sem[OF assms siter_distinct])
also have ‹… ⊆ sem_round T kn (tpaths T kn) a›
by (rule sem_round_mono) (rule Suc.IH)
also have ‹… ⊆ tpaths T kn a› by (rule sem_round_tpaths)
finally show ?case .
qed simp
text ‹Conversely, a set assignment that a round does not enlarge contains every
path's image.›
lemma tpaths_le_post:
assumes post: ‹⋀a. sem_round T kn ν a ⊆ ν a›
shows ‹tpaths T kn a ⊆ ν a›
proof -
have ‹eff_set e (irep_set R) ⊆ ν a› if ‹treach T b a e› ‹(b, R) ∈ set kn› for b a e R
using that(1)
proof induction
case treach_refl
have ‹irep_set R ⊆ kset b kn› using that(2) by (auto simp: kset_def)
also have ‹… ⊆ ν b› using post[of b] by (simp add: sem_round_def)
finally show ?case by simp
next
case (treach_edge c e a q)
have ‹eff_set (ecomp (of_rel q) e) (irep_set R) = eff_set (of_rel q) (eff_set e (irep_set R))›
by (rule eff_set_comp)
also have ‹… ⊆ eff_set (of_rel q) (ν c)› by (rule eff_set_mono[OF treach_edge.IH])
also have ‹… ⊆ ν a› using post[of a] treach_edge.hyps(2) unfolding sem_round_def by blast
finally show ?case .
qed
then show ?thesis unfolding tpaths_def by blast
qed
text ‹So the fixpoint the sparse closure computes is the union of the path
images, whenever its loop stops.›
definition sfix_loop :: ‹('n, 't) stab ⇒ (nat × indrep) list ⇒
((nat × indrep) list × (nat × indrep) list) option› where
‹sfix_loop T kn = while_option (λ(N, N'). ¬ ssub N' N)
(λ(N, N'). (N', sround T kn N')) ([], sround T kn [])›
lemma ssub_le:
assumes ‹ssub N' N› shows ‹irep_set (slk N' a) ⊆ irep_set (slk N a)›
proof (cases ‹map_of N' a›)
case (Some R)
then have ‹(a, R) ∈ set N'› by (rule map_of_SomeD)
with assms Some show ?thesis by (auto simp: ssub_def list_all_iff slk_def)
qed (simp add: slk_def)
lemma sfix_tpaths:
assumes ok: ‹ntl_ok T› and stop: ‹sfix_loop T kn ≠ None›
shows ‹irep_set (slk (sfix T kn) a) = tpaths T kn a›
proof -
obtain N N' where loop: ‹sfix_loop T kn = Some (N, N')› using stop by auto
let ?P = ‹λp. ∃t. fst p = siter T kn t ∧ snd p = siter T kn (Suc t)›
have ‹?P (N, N')›
proof (rule while_option_rule[OF _ loop[unfolded sfix_loop_def]])
fix p assume ‹?P p›
then obtain t where ‹fst p = siter T kn t› ‹snd p = siter T kn (Suc t)› by blast
then show ‹?P ((λ(N, N'). (N', sround T kn N')) p)›
by (intro exI[of _ ‹Suc t›]) (simp add: case_prod_beta)
qed (intro exI[of _ 0]; simp)
then obtain t where N: ‹N = siter T kn t› and N': ‹N' = siter T kn (Suc t)› by auto
have sub: ‹ssub N' N› using while_option_stop[OF loop[unfolded sfix_loop_def]] by simp
have fx: ‹sfix T kn = N› using loop by (simp add: sfix_def sfix_loop_def)
have post: ‹sem_round T kn (λc. irep_set (slk N c)) b ⊆ irep_set (slk N b)› for b
using ssub_le[OF sub, of b] by (simp add: N N' sround_sem[OF ok siter_distinct])
show ?thesis
unfolding fx using siter_le_tpaths[OF ok, of kn t a] tpaths_le_post[OF post, of a]
by (auto simp: N)
qed
subsection ‹The saturated transfer table›
text ‹For each source nonterminal ‹b›, a row with the join of the transfers of
all paths from ‹b› to each nonterminal: the least fixpoint of the edges,
reached by iteration, since the transfer order has no infinite ascending
chains. The equations have the shape of Eq.~(4.1) of DeRemer and Pennello,
cf.~\<^cite>‹‹Sect.~4.1› in "deremer1982-lalr-lookahead"›, with transfers in place of
sets and a composition along each edge. They are solved by plain iteration,
not by the traversal ‹Digraph› given there.›
definition hd_nt :: ‹('n, 't) prec ⇒ (nat × irel) option› where
‹hd_nt r = (case rrhs r of (Nt a, q) # _ ⇒ Some (a, q) | _ ⇒ None)›
lemma hd_nt_eq: ‹hd_nt r = Some (a, q) ⟷ (∃rest. rrhs r = (Nt a, q) # rest)›
by (auto simp: hd_nt_def split: list.split sym.split prod.split)
definition tin :: ‹('n, 't) stab ⇒ nat ⇒ (nat × irel) list› where
‹tin T a = concat (map (λc. List.map_filter (λk. case hd_nt (s_recs T !! k) of
Some (a', q) ⇒ if a' = a then Some (c, q) else None | None ⇒ None) (ntl T c))
[0..<s_np T])›
lemma set_tin: ‹a < s_np T ⟹ set (tin T a) = {(c, q). tedge T c a q}›
proof -
have c: ‹(case h of Some (a', q') ⇒ if a' = a then Some (x, q') else None | None ⇒ None) = Some (y, q)
⟷ h = Some (a, q) ∧ y = x› for h :: ‹(nat × irel) option› and x y :: nat and q
by (cases h) (auto split: if_splits)
assume ‹a < s_np T›
then show ?thesis
by (auto simp: tin_def tedge_def in_map_filter c hd_nt_eq[symmetric] simp del: IArray.sub_def)
qed
definition tr_step :: ‹('n, 't) stab ⇒ eff list ⇒ eff list› where
‹tr_step T row = map (λa. fold ejoin (map (λ(c, q). ecomp (of_rel q) (row ! c)) (tin T a)) (row ! a))
[0..<s_np T]›
definition tinit :: ‹nat ⇒ nat ⇒ eff list› where
‹tinit n b = map (λa. if a = b then eid else ebot) [0..<n]›
definition trow_loop :: ‹('n, 't) stab ⇒ nat ⇒ eff list option› where
‹trow_loop T b = while_option (λrow. tr_step T row ≠ row) (tr_step T) (tinit (s_np T) b)›
definition trow :: ‹('n, 't) stab ⇒ nat ⇒ eff list› where
‹trow T b = the (trow_loop T b)›
lemma length_tr_step [simp]: ‹length (tr_step T row) = s_np T›
by (simp add: tr_step_def)
lemma tr_step_nth: ‹a < s_np T ⟹
tr_step T row ! a = fold ejoin (map (λ(c, q). ecomp (of_rel q) (row ! c)) (tin T a)) (row ! a)›
by (simp add: tr_step_def)
lemma tr_step_inc: ‹length row = s_np T ⟹ list_all2 ele row (tr_step T row)›
by (simp add: list_all2_conv_all_nth tr_step_nth ele_fold_ejoin)
lemma trow_loop_Some: ‹trow_loop T b ≠ None›
proof -
let ?P = ‹λrow. length row = s_np T›
have ‹{(t, s). (?P s ∧ tr_step T s ≠ s) ∧ t = tr_step T s} ⊆ {(ys, xs). list_all2 ele xs ys ∧ xs ≠ ys}›
using tr_step_inc by fastforce
then have ‹wf {(t, s). (?P s ∧ tr_step T s ≠ s) ∧ t = tr_step T s}›
by (rule wf_subset[OF wf_eff_list_inc])
then have ‹∃r. trow_loop T b = Some r›
unfolding trow_loop_def by (rule wf_while_option_Some) (simp_all add: tinit_def)
then show ?thesis by auto
qed
text ‹The semantic invariant of the iteration: every entry is below the paths,
and the source's entry contains the identity.›
definition tpath_set :: ‹('n, 't) stab ⇒ nat ⇒ nat ⇒ nat set ⇒ nat set› where
‹tpath_set T b a S = ⋃{eff_set e S |e. treach T b a e}›
lemma tpath_set_edge:
assumes ‹tedge T c a q›
shows ‹eff_set (of_rel q) (tpath_set T b c S) ⊆ tpath_set T b a S›
proof
fix x assume ‹x ∈ eff_set (of_rel q) (tpath_set T b c S)›
then obtain e where e: ‹treach T b c e› and x: ‹x ∈ eff_set (of_rel q) (eff_set e S)›
unfolding tpath_set_def eff_set_UN by blast
have ‹eff_set (ecomp (of_rel q) e) S ∈ {eff_set e S |e. treach T b a e}›
using treach_edge[OF e assms] by blast
with x show ‹x ∈ tpath_set T b a S› unfolding tpath_set_def eff_set_comp by blast
qed
definition trow_inv :: ‹('n, 't) stab ⇒ nat ⇒ eff list ⇒ bool› where
‹trow_inv T b row ⟷ length row = s_np T ∧
(∀a < s_np T. ∀S. eff_set (row ! a) S ⊆ tpath_set T b a S) ∧
(∀S. b < s_np T ⟶ S ⊆ eff_set (row ! b) S)›
lemma trow_inv_init: ‹trow_inv T b (tinit (s_np T) b)›
proof -
have ‹S ⊆ tpath_set T b b S› for S
proof -
have ‹eff_set eid S ∈ {eff_set e S |e. treach T b b e}› using treach_refl[of T b] by blast
then show ?thesis unfolding tpath_set_def eff_set_id by blast
qed
then show ?thesis by (simp add: trow_inv_def tinit_def)
qed
lemma tr_step_set:
assumes ‹a < s_np T›
shows ‹eff_set (tr_step T row ! a) S =
eff_set (row ! a) S ∪ ⋃{eff_set (of_rel q) (eff_set (row ! c) S) |c q. tedge T c a q}›
proof -
have ‹eff_set (tr_step T row ! a) S =
eff_set (row ! a) S ∪ (⋃(c, q) ∈ set (tin T a). eff_set (of_rel q) (eff_set (row ! c) S))›
using assms by (simp add: tr_step_nth eff_set_fold_ejoin case_prod_beta eff_set_comp)
also have ‹(⋃(c, q) ∈ set (tin T a). eff_set (of_rel q) (eff_set (row ! c) S)) =
⋃{eff_set (of_rel q) (eff_set (row ! c) S) |c q. tedge T c a q}›
using assms by (auto simp: set_tin)
finally show ?thesis .
qed
lemma trow_inv_step:
assumes inv: ‹trow_inv T b row›
shows ‹trow_inv T b (tr_step T row)›
unfolding trow_inv_def
proof (intro conjI allI impI)
show ‹length (tr_step T row) = s_np T› by simp
next
fix a S assume a: ‹a < s_np T›
have ‹eff_set (of_rel q) (eff_set (row ! c) S) ⊆ tpath_set T b a S› if e: ‹tedge T c a q› for c q
proof -
have ‹c < s_np T› using e by (simp add: tedge_def)
with inv have ‹eff_set (row ! c) S ⊆ tpath_set T b c S› by (simp add: trow_inv_def)
then have ‹eff_set (of_rel q) (eff_set (row ! c) S) ⊆ eff_set (of_rel q) (tpath_set T b c S)›
by (rule eff_set_mono)
also have ‹… ⊆ tpath_set T b a S› by (rule tpath_set_edge[OF e])
finally show ?thesis .
qed
moreover have ‹eff_set (row ! a) S ⊆ tpath_set T b a S› using inv a by (simp add: trow_inv_def)
ultimately show ‹eff_set (tr_step T row ! a) S ⊆ tpath_set T b a S›
unfolding tr_step_set[OF a] by blast
next
fix S assume b: ‹b < s_np T›
with inv have ‹S ⊆ eff_set (row ! b) S› by (simp add: trow_inv_def)
then show ‹S ⊆ eff_set (tr_step T row ! b) S› unfolding tr_step_set[OF b] by blast
qed
lemma trow_some: obtains r where ‹trow_loop T b = Some r› ‹trow T b = r›
using trow_loop_Some[of T b] by (auto simp: trow_def)
lemma trow_inv_trow: ‹trow_inv T b (trow T b)›
proof -
obtain r where r: ‹trow_loop T b = Some r› and t: ‹trow T b = r› by (rule trow_some)
have ‹trow_inv T b r›
using while_option_rule[where P = ‹trow_inv T b›, OF trow_inv_step r[unfolded trow_loop_def]
trow_inv_init] .
with t show ?thesis by simp
qed
lemma tr_step_trow: ‹tr_step T (trow T b) = trow T b›
proof -
obtain r where r: ‹trow_loop T b = Some r› and t: ‹trow T b = r› by (rule trow_some)
from while_option_stop[OF r[unfolded trow_loop_def]] t show ?thesis by simp
qed
lemma trow_sem:
assumes b: ‹b < s_np T› and a: ‹a < s_np T›
shows ‹eff_set (trow T b ! a) S = tpath_set T b a S›
proof
show ‹eff_set (trow T b ! a) S ⊆ tpath_set T b a S›
using trow_inv_trow[of T b] a by (simp add: trow_inv_def)
have ‹eff_set e S ⊆ eff_set (trow T b ! a') S› if ‹treach T b a' e› for a' e
using that
proof induction
case treach_refl
then show ?case using trow_inv_trow[of T b] b by (simp add: trow_inv_def)
next
case (treach_edge c e a q)
have a': ‹a < s_np T› using treach_edge.hyps(2) by (simp add: tedge_def)
have ‹eff_set (ecomp (of_rel q) e) S = eff_set (of_rel q) (eff_set e S)› by (rule eff_set_comp)
also have ‹… ⊆ eff_set (of_rel q) (eff_set (trow T b ! c) S)›
by (rule eff_set_mono[OF treach_edge.IH])
also have ‹… ⊆ eff_set (tr_step T (trow T b) ! a) S›
using treach_edge.hyps(2) unfolding tr_step_set[OF a'] by blast
finally show ?case by (simp only: tr_step_trow)
qed
then show ‹tpath_set T b a S ⊆ eff_set (trow T b ! a) S› unfolding tpath_set_def by blast
qed
text ‹The closure's anchor set of a numbered nonterminal, from the kernel
without a fixpoint.›
lemma sfix_trow:
assumes ok: ‹ntl_ok T› and stop: ‹sfix_loop T kn ≠ None›
and kn: ‹⋀b R. (b, R) ∈ set kn ⟹ b < s_np T› and a: ‹a < s_np T›
shows ‹irep_set (slk (sfix T kn) a) = (⋃(b, R) ∈ set kn. eff_set (trow T b ! a) (irep_set R))›
proof -
have ‹irep_set (slk (sfix T kn) a) = tpaths T kn a› by (rule sfix_tpaths[OF ok stop])
also have ‹… = (⋃(b, R) ∈ set kn. tpath_set T b a (irep_set R))›
unfolding tpaths_def tpath_set_def by blast
also have ‹… = (⋃(b, R) ∈ set kn. eff_set (trow T b ! a) (irep_set R))›
by (rule SUP_cong[OF refl]) (auto simp: trow_sem[OF kn a])
finally show ?thesis .
qed
subsection ‹Applying a transfer›
text ‹The least anchor of a non-empty set, and a transfer applied to a set.›
fun imin :: ‹indrep ⇒ nat› where
‹imin (FinRep []) = 0›
| ‹imin (FinRep (x # xs)) = fold min xs x›
| ‹imin (UpRep xs n) = fold min xs n›
lemma fold_min_le_iff: ‹fold min ys a ≤ i ⟷ a ≤ i ∨ (∃y ∈ set ys. y ≤ i)› for ys :: ‹nat list›
using Min.set_eq_fold[of a ys, symmetric] by (simp add: Min_le_iff)
lemma imin_le_iff: ‹irep_set R ≠ {} ⟹ imin R ≤ i ⟷ (∃j ∈ irep_set R. j ≤ i)›
proof (cases R)
case (FinRep xs)
assume ‹irep_set R ≠ {}›
with FinRep show ?thesis by (cases xs) (auto simp: fold_min_le_iff)
next
case (UpRep xs n)
then show ?thesis by (auto simp: fold_min_le_iff intro: le_trans)
qed
lemma sh_imin:
assumes ne: ‹irep_set R ≠ {}›
shows ‹sh d (irep_set R) = {m. imin R + d ≤ m}›
proof -
have l: ‹imin R ≤ j› if ‹j ∈ irep_set R› for j
using imin_le_iff[OF ne, of j] that by blast
obtain j⇩0 where j⇩0: ‹j⇩0 ∈ irep_set R› ‹j⇩0 ≤ imin R›
using imin_le_iff[OF ne, of ‹imin R›] by blast
with l have ‹j⇩0 = imin R› by (simp add: le_antisym)
with j⇩0 l show ?thesis
by (auto simp: sh_def intro: le_trans[OF add_right_mono])
qed
definition eapp :: ‹eff ⇒ indrep ⇒ indrep› where
‹eapp e R = (if irep_nonempty R then (case e of (i, s, c) ⇒
let R⇩1 = (if i then R else FinRep []);
R⇩2 = (case s of None ⇒ R⇩1 | Some d ⇒ cup (imin R + d) R⇩1)
in (case c of None ⇒ R⇩2 | Some d ⇒ cup d R⇩2))
else FinRep [])›
lemma eapp_set [simp]: ‹irep_set (eapp e R) = eff_set e (irep_set R)›
proof (cases ‹irep_set R = {}›)
case False
obtain i s c where e: ‹e = (i, s, c)› by (cases e)
show ?thesis
using False sh_imin[OF False]
by (cases s; cases c) (auto simp: eapp_def e eff_set.simps cn_def)
qed (simp add: eapp_def)
subsection ‹The tables›
text ‹The items of state ‹j›: its LR(0) closure, in the order \<^const>‹creach›
lists them. A frame of the driver is a state with one anchor set per item.
An item is a ∗‹slot› when the closure adds it: dot ‹0› of a grammar
production. The others, the ∗‹kernel positions›, get their anchors from the
predecessor frame; a slot gets its anchors from the kernel positions, through
the transfer of the closure graph (\<^const>‹trow›).›
definition vits :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒ nat ⇒ ('n, 't) citem list› where
‹vits G sts j = (if j < length sts then creach G (sts ! j) else [])›
definition is_slot :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem ⇒ bool› where
‹is_slot G it ⟷ snd it = 0 ∧ fst it ∈ set (iprods G)›
definition getR :: ‹indrep list ⇒ nat ⇒ indrep› where
‹getR av k = (if k < length av then av ! k else FinRep [])›
definition iget :: ‹'a iarray ⇒ nat ⇒ 'a ⇒ 'a› where
‹iget xs k d = (if k < IArray.length xs then xs !! k else d)›
definition nnum :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 'n ⇒ nat› where
‹nnum G Shn B = ntidx (map fst (eprods G Shn)) B›
text ‹The nonterminal after an item's dot, if the grammar has productions for it,
with the relation it carries.›
definition vnext_nt :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem ⇒ ('n × irel) option› where
‹vnext_nt G it = (case it of (p, m) ⇒ if m < length (snd p) then
(case snd p ! m of (Nt B, q) ⇒ if B ∈ fst ` set (iprods G) then Some (B, q) else None
| _ ⇒ None) else None)›
text ‹The contributions to a slot: per kernel position whose item expects a
nonterminal, the transfer from that position's anchors to the slot's.›
definition vcontrib :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) stab ⇒ ('n, 't) citem list ⇒
('n, 't) citem ⇒ (nat × eff) list› where
‹vcontrib G Shn T its it = (if is_slot G it then
List.map_filter (λkk. if is_slot G (its ! kk) then None else
(case vnext_nt G (its ! kk) of None ⇒ None
| Some (B, q) ⇒ Some (kk, ecomp (trow T (nnum G Shn B) ! nnum G Shn (fst (fst it))) (of_rel q))))
[0..<length its]
else [])›
text ‹The kernel of a successor under ‹X›: per item of the successor state, the
position of its predecessor in the state left and the relation of the symbol
crossed.›
definition vkmap :: ‹('n, 't) citem list ⇒ ('n, 't) sym ⇒ ('n, 't) citem list ⇒
(nat × irel) option list› where
‹vkmap its X its' = map (λ(p, m). if 0 < m ∧ m ≤ length (snd p) ∧ fst (snd p ! (m - 1)) = X
then Some (ntidx its (p, m - 1), snd (snd p ! (m - 1))) else None) its'›
definition ventry :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
nat ⇒ ('n, 't) sym ⇒ (nat × (nat × irel) option list) option› where
‹ventry G gt sts j X = (let j' = dnext gt sts j X in
if j' < length sts then Some (j', vkmap (vits G sts j) X (vits G sts j')) else None)›
text ‹The completed items of a state, each at its first position, with the
number of the nonterminal it reduces to; the reduce cells per token and at the
end of the input, by position.›
definition vcomps :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list ⇒ (nat × nat × ('n × ('n, 't) rhs)) list› where
‹vcomps G Shn its = List.map_filter (λs. case its ! s of (pr, m) ⇒
if m = length (snd pr) ∧ ntidx its (pr, m) = s then Some (s, nnum G Shn (fst pr), pr) else None)
[0..<length its]›
definition vcells :: ‹('n, 't) citem list ⇒ nat ⇒ ('n, 't) lacell list ⇒ 't option ⇒ (nat × wrel) list› where
‹vcells its j cells t = List.map_filter (λ(i', (pr, n), t', τ).
if i' = j ∧ n = length (snd pr) ∧ t' = t then Some (ntidx its (pr, n), τ) else None) cells›
text ‹The tokens the tables number: the grammar's terminals and those of the
reduce cells.›
definition vtoks :: ‹('n, 't) is_cfg ⇒ ('n, 't) lacell list list ⇒ 't list› where
‹vtoks G redtab = remdups ([a. Tm a ← gram_syms G] @
List.map_filter (λ(i', itm, t, τ). t) (concat redtab))›