Theory LR_Tok

(* Author: Basil Fürer, Dmitriy Traytel *)

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) = i0›
    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 [] ([i0], map (jenc J) w, [])›
  unfolding dparse_via_trie_tables[OF static st gt rt pcs pfs i0 lt jt] xrun_jctl2 ..

end