Theory LR_Tok
theory LR_Tok
imports LR_Trie
begin
section ‹Numbering the tokens once›
text ‹The trie step numbers the lookahead token at every step, by a search
in the list of tokens of the tables. Here the input word is numbered once,
as a list of pairs of a token and its number, and the driver reads the
number off the input.›
definition xtree :: ‹('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒ ('n, 't) dact ⇒ 'w list ⇒
('m, 'ch, 'n, 't) ast list ⇒ ('m, 'ch, 'n, 't) ast list› where
‹xtree dec act v tstk = (case act of
DShift ⇒ Leaf (dec (hd v)) # tstk
| DReduce pr ⇒ Node (fst pr) (rev (take_as (snd pr) tstk)) # drop_as (snd pr) tstk)›
partial_function (option) xrun_hist ::
‹('k list × 'w list ⇒ (('n, 't) dact × 'k list × 'w list) option) ⇒
('k list × 'w list ⇒ bool) ⇒ ('w ⇒ ('t, 'ch, 'm) token_scheme) ⇒
'k list list ⇒ 'k list × 'w list × ('m, 'ch, 'n, 't) ast list ⇒
('m, 'ch, 'n, 't) ast option›
where
‹xrun_hist ctl fin dec 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').
xrun_hist ctl fin dec (if act = DShift then [] else stk # seen)
(stk', v', xtree dec act v tstk)))›
lemmas xrun_hist_simps [code] = xrun_hist.simps
text ‹\<^const>‹xrun_hist› on an encoded input computes \<^const>‹srun_hist›.›
locale input_transfer =
fixes enc :: ‹('t, 'ch, 'm) token_scheme ⇒ 'w› and dec :: ‹'w ⇒ ('t, 'ch, 'm) token_scheme›
and ctl1 :: ‹('m, 'ch, 't) sctl_t ⇒ (('n, 't) dact × ('m, 'ch, 't) sctl_t) option›
and fin1 :: ‹('m, 'ch, 't) sctl_t ⇒ bool›
and ctl2 :: ‹nat list × 'w list ⇒ (('n, 't) dact × nat list × 'w list) option›
and fin2 :: ‹nat list × 'w list ⇒ bool›
assumes dec: ‹⋀x. dec (enc x) = x›
and ctl: ‹⋀stk v. ctl2 (stk, map enc v) =
map_option (λ(a, stk', v'). (a, stk', map enc v')) (ctl1 (stk, v))›
and fin: ‹⋀stk v. fin2 (stk, map enc v) = fin1 (stk, v)›
and shift: ‹⋀stk v r. ctl1 (stk, v) = Some (DShift, r) ⟹ v ≠ []›
begin
lemma xtree_stree:
‹ctl1 (stk, v) = Some (a, r) ⟹ xtree dec a (map enc v) tstk = stree a v tstk›
using shift[of stk v] dec
by (cases a) (auto simp: xtree_def stree_code hd_map)
lemma s_imp_x:
assumes h: ‹srun_hist ctl1 fin1 seen st = Some t›
shows ‹xrun_hist ctl2 fin2 dec seen (fst st, map enc (fst (snd st)), snd (snd st)) = Some t›
proof -
have ‹ctl1 = ctl1 ⟶ fin1 = fin1 ⟶
xrun_hist ctl2 fin2 dec seen (fst st, map enc (fst (snd st)), snd (snd st)) = Some t›
proof (rule srun_hist.raw_induct[OF _ h, where P = ‹λctl fin seen st t. ctl = ctl1 ⟶ fin = fin1 ⟶
xrun_hist ctl2 fin2 dec seen (fst st, map enc (fst (snd st)), snd (snd st)) = Some t›], 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 = ctl1› and fi: ‹fin = fin1›
show ‹xrun_hist ctl2 fin2 dec seen (fst st, map enc (fst (snd st)), snd (snd st)) = Some t›
proof (cases ‹fin1 (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst xrun_hist.simps) (simp add: fin)
next
case False
from False "1"(2) have nk: ‹stk ∉ set seen› unfolding st c fi by (auto split: if_splits)
from False "1"(2) obtain a stk' v' where
sc: ‹ctl1 (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 ‹xrun_hist ctl2 fin2 dec (if a = DShift then [] else stk # seen)
(stk', map enc v', stree a v tstk) = Some t› by simp
then show ?thesis unfolding st using False nk sc xtree_stree[OF sc]
by (subst xrun_hist.simps) (simp add: fin ctl)
qed
qed
qed
then show ?thesis by blast
qed
lemma x_imp_s:
assumes h: ‹xrun_hist ctl2 fin2 dec seen st2 = Some t›
shows ‹st2 = (stk, map enc v, tstk) ⟹ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
proof -
have ‹ctl2 = ctl2 ⟶ fin2 = fin2 ⟶ dec = dec ⟶ (∀stk v tstk.
st2 = (stk, map enc v, tstk) ⟶ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›
proof (rule xrun_hist.raw_induct[OF _ h, where P = ‹λctl fin dc seen st2 t. ctl = ctl2 ⟶ fin = fin2 ⟶
dc = dec ⟶ (∀stk v tstk. st2 = (stk, map enc v, tstk) ⟶
srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t)›], goal_cases)
case (1 f ctl fin dc seen st2 t)
show ?case
proof (intro impI allI)
fix stk v tstk
assume c: ‹ctl = ctl2› and fi: ‹fin = fin2› and d: ‹dc = dec›
and st: ‹st2 = (stk, map enc v, tstk)›
show ‹srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t›
proof (cases ‹fin1 (stk, v)›)
case True
with "1"(2) show ?thesis unfolding st c fi by (subst srun_hist.simps) (simp add: fin)
next
case False
from False "1"(2) have nk: ‹stk ∉ set seen›
unfolding st c fi by (auto simp: fin split: if_splits)
from False "1"(2) obtain a stk' v2 where
sc: ‹ctl2 (stk, map enc v) = Some (a, stk', v2)›
and rec: ‹f ctl fin dc (if a = DShift then [] else stk # seen)
(stk', v2, xtree dc a (map enc v) tstk) = Some t›
unfolding st c fi by (auto simp: bind_eq_Some_conv fin split: if_splits)
from sc obtain v' where sc1: ‹ctl1 (stk, v) = Some (a, stk', v')› and v2: ‹v2 = map enc v'›
unfolding ctl by (auto split: prod.splits)
have ‹srun_hist ctl1 fin1 (if a = DShift then [] else stk # seen) (stk', v', stree a v tstk) = Some t›
using "1"(1)[OF rec] c fi d v2 xtree_stree[OF sc1] by simp
then show ?thesis using False nk sc1 by (subst srun_hist.simps) simp
qed
qed
qed
then show ‹st2 = (stk, map enc v, tstk) ⟹ srun_hist ctl1 fin1 seen (stk, v, tstk) = Some t› by blast
qed
theorem xrun_hist_eq:
‹xrun_hist ctl2 fin2 dec seen (stk, map enc v, tstk) = srun_hist ctl1 fin1 seen (stk, v, tstk)›
proof (cases ‹srun_hist ctl1 fin1 seen (stk, v, tstk)›)
case None
show ?thesis
proof (cases ‹xrun_hist ctl2 fin2 dec seen (stk, map enc v, tstk)›)
case (Some t)
from x_imp_s[OF Some refl] None show ?thesis by simp
qed (simp add: None)
next
case (Some t)
from s_imp_x[OF Some] Some show ?thesis by simp
qed
end
subsection ‹The trie step on numbered input›
definition jenc :: ‹('n, 't) jtabs ⇒ ('t, 'ch, 'm) token_scheme ⇒ ('t, 'ch, 'm) token_scheme × nat› where
‹jenc J x = (x, jla J [x])›
definition jctl2 :: ‹('n, 't) jtabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒
(('n, 't) dact × nat list × (('t, 'ch, 'm) token_scheme × nat) list) option› where
‹jctl2 J c = (case c of (stk, v) ⇒
(case stk of [] ⇒ None | i # _ ⇒
let l = (case v of [] ⇒ 0 | (_, l) # _ ⇒ l);
lics = jget (jt_lic J) i l;
comps = (case tlookup (jt_pc J) i of None ⇒ [] | Some cs ⇒ cs);
cands = (case v of [] ⇒ [] | _ ⇒ [IShift]) @ map IReduce (filter (jlicd lics) comps)
in (case spick (jtarget J stk l) cands of
None ⇒ None
| Some (IShift, q) ⇒ Some (DShift, q # stk, tl v)
| Some (IReduce j, q) ⇒ (case tlookup (jt_prs J) j of None ⇒ None | Some (pr, A) ⇒
Some (DReduce pr, q # drop_as (snd pr) stk, v)))))›
definition jfinal2 :: ‹('n, 't) jtabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒
bool› where
‹jfinal2 J c ⟷ (case c of (stk, v) ⇒ v = [] ∧
(case stk of [] ⇒ False | i # _ ⇒ tlookup (jt_pf J) i = Some True))›
lemma jla_enc: ‹(case map (jenc J) v of [] ⇒ 0 | (_, l) # _ ⇒ l) = jla J v›
unfolding jenc_def jla_def by (cases v) auto
lemma jctl2_eq:
‹jctl2 J (stk, map (jenc J) v) =
map_option (λ(a, stk', v'). (a, stk', map (jenc J) v')) (jctl J (stk, v))›
proof -
have cs: ‹(case map (jenc J) v of [] ⇒ [] | _ ⇒ [IShift]) = (case v of [] ⇒ [] | _ ⇒ [IShift])›
by (cases v) auto
show ?thesis
unfolding jctl2_def jctl_def prod.case jla_enc cs
by (auto simp: Let_def map_tl split: list.splits option.splits prod.splits iact.splits)
qed
lemma jfinal2_eq: ‹jfinal2 J (stk, map (jenc J) v) = jfinal J (stk, v)›
unfolding jfinal2_def jfinal_def by simp
lemma jctl_shift: ‹jctl J (stk, v) = Some (DShift, r) ⟹ v ≠ []›
unfolding jctl_def
by (auto simp: Let_def split: list.splits option.splits prod.splits iact.splits dest!: spick_SomeD)
theorem xrun_jctl2:
‹xrun_hist (jctl2 J) (jfinal2 J) fst seen (stk, map (jenc J) v, tstk) =
srun_hist (jctl J) (jfinal J) seen (stk, v, tstk)›
proof -
interpret input_transfer ‹jenc J› fst ‹jctl J› ‹jfinal J› ‹jctl2 J› ‹jfinal2 J›
by (rule input_transfer.intro) (simp add: jenc_def, rule jctl2_eq, rule jfinal2_eq, rule jctl_shift)
show ?thesis by (rule xrun_hist_eq)
qed
lemma dparse_via_trie_tok_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›
and lt: ‹mk_ltabs gtab sts redtab pc pf = L›
and jt: ‹jtabs_of L = J›
shows ‹dparse G Shn w = xrun_hist (jctl2 J) (jfinal2 J) fst [] ([i⇩0], map (jenc J) w, [])›
unfolding dparse_via_trie_tables[OF static st gt rt pcs pfs i0 lt jt] xrun_jctl2 ..
end