Theory LR_Plain

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

theory LR_Plain
  imports LR_Loop
begin

section ‹A plain action table›

text ‹The step on candidate tables (const‹kctl›) tries the shift and then
  the reduce candidates of the lookahead, which takes a lookup in the shift
  table, one in the table of candidates, and one in the table of productions
  per candidate. Here one table gives per state and lookahead the actions to try: the
  shift with its target if there is one (the step takes it before any
  reduce), otherwise the reduces, each with its production and the number of
  its left-hand side. A second table gives the reduces at the end of the
  input, where there is no shift. This is the action table of Jourdan et al.
  cite‹‹Sect.~2.4› in "jourdan2012-validating-lr1"›, and Knuth tabulates the same choice of
  shift or reduce per state set cite‹‹Sect.~III, Table~I› in "knuth1965-lr-translation"›.
  Here an entry is a list of actions rather than one, and the end of the input
  has its own table, where Jourdan et al. assume an infinite input stream.
  The step on these tables equals the step on
  candidate tables on every stack, so the run is the same.›

datatype ('n, 't) pact = PShift nat | PReduce ‹'n × ('n, 't) rhs› nat

datatype ('n, 't) ptabs = PTabs
  (pt_lal: ‹('t × nat) list›) (pt_miss: nat)
  (pt_A: ‹('n, 't) pact list ntab ntab›) (pt_E: ‹('n, 't) pact list ntab›)
  (pt_N: ‹nat ntab ntab›) (pt_pf: ‹bool ntab›)

subsection ‹The tables›

definition kred :: ‹('n, 't) ktabs ⇒ nat ⇒ ('n, 't) pact list› where
  ‹kred K j = (case tlookup (kt_prs K) j of None ⇒ [] | Some (pr, A) ⇒ [PReduce pr A])›

definition kreds :: ‹('n, 't) ktabs ⇒ nat list ⇒ ('n, 't) pact list› where
  ‹kreds K js = concat (map (kred K) js)›

definition pent :: ‹('n, 't) ktabs ⇒ nat ⇒ nat ⇒ ('n, 't) pact list› where
  ‹pent K k l = (case jget (kt_T K) k l of
     Some k' ⇒ [PShift k'] | None ⇒ kreds K (kcands K k l))›

definition tkeys :: ‹'a ntab ⇒ nat list› where
  ‹tkeys t = map fst (tentries t)›

definition ptabs_of :: ‹('n, 't) ktabs ⇒ ('n, 't) ptabs› where
  ‹ptabs_of K = PTabs (kt_lal K) (kt_miss K)
     (tab_of_assoc (map (λk. (k, tab_of_assoc (map (λl. (l, pent K k l))
         (remdups (tkeys (trow (kt_T K) k) @ tkeys (trow (kt_C K) k))))))
       (remdups (tkeys (kt_T K) @ tkeys (kt_C K)))))
     (tab_of_assoc (map (λk. (k, kreds K (kcands K k 0))) (tkeys (kt_C K))))
     (kt_N K) (kt_pf K)›

subsection ‹The step›

fun sfind :: ‹('a ⇒ 'b option) ⇒ 'a list ⇒ 'b option› where
  ‹sfind f [] = None›
| ‹sfind f (a # as) = (case f a of Some b ⇒ Some b | None ⇒ sfind f as)›

definition pcands :: ‹('n, 't) ptabs ⇒ nat ⇒ nat ⇒ ('n, 't) pact list› where
  ‹pcands P k l = (case jget (pt_A P) k l of None ⇒ [] | Some es ⇒ es)›

definition pecands :: ‹('n, 't) ptabs ⇒ nat ⇒ ('n, 't) pact list› where
  ‹pecands P k = (case tlookup (pt_E P) k of None ⇒ [] | Some es ⇒ es)›

definition ptarget :: ‹('n, 't) ptabs ⇒ nat list ⇒ ('n, 't) pact ⇒ (('n, 't) dact × nat list) option› where
  ‹ptarget P kstk a = (case a of
      PShift k' ⇒ Some (DShift, k' # kstk)
    | PReduce pr A ⇒ (case drop_as (snd pr) kstk of [] ⇒ None | k'' # rest ⇒
        map_option (λk'. (DReduce pr, k' # k'' # rest)) (jget (pt_N P) k'' A)))›

definition pctl :: ‹('n, 't) ptabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒
    (('n, 't) dact × nat list × (('t, 'ch, 'm) token_scheme × nat) list) option› where
  ‹pctl P c = (case c of (kstk, v) ⇒
     (case kstk of [] ⇒ None | k # _ ⇒
       (case v of
         [] ⇒ map_option (λ(a, stk'). (a, stk', v)) (sfind (ptarget P kstk) (pecands P k))
       | (_, l) # v' ⇒ map_option (λ(a, stk'). (a, stk', case a of DShift ⇒ v' | DReduce _ ⇒ v))
           (sfind (ptarget P kstk) (pcands P k l)))))›

definition pfinal :: ‹('n, 't) ptabs ⇒ nat list × (('t, 'ch, 'm) token_scheme × nat) list ⇒ bool› where
  ‹pfinal P c ⟷ (case c of (kstk, v) ⇒ v = [] ∧
     (case kstk of [] ⇒ False | k # _ ⇒ tlookup (pt_pf P) k = Some True))›

text ‹The number of a token, by a search in the list of terminals. The code
  equation takes any function equal to it: for tokens of a datatype whose
  constructors have no arguments, the ⬚‹parser› command defines one by
  a case distinction, proved equal constructor by constructor.›

definition pnum :: ‹('n, 't) ptabs ⇒ 't ⇒ nat› where
  ‹pnum P t = (case map_of (pt_lal P) t of Some l ⇒ l | None ⇒ pt_miss P)›

definition tenc :: ‹('t ⇒ nat) ⇒ ('t, 'ch, 'm) token_scheme ⇒ ('t, 'ch, 'm) token_scheme × nat› where
  ‹tenc f x = (x, f (tok x))›

subsection ‹Correctness›

lemma sfind_spick: ‹sfind f xs = map_option snd (spick f xs)›
  by (induction xs) (auto split: option.split)

lemma sfind_map: ‹sfind f (map g xs) = sfind (f ∘ g) xs›
  by (induction xs) (auto split: option.split)

lemma sfind_concat: ‹sfind f (concat (map h xs)) = sfind (λx. sfind f (h x)) xs›
proof (induction xs)
  case (Cons x xs)
  have ‹sfind f (ys @ zs) = (case sfind f ys of Some b ⇒ Some b | None ⇒ sfind f zs)› for ys zs
    by (induction ys) (auto split: option.split)
  then show ?case using Cons by (simp split: option.split)
qed simp

lemma tkeys_complete: ‹tlookup t n = Some a ⟹ n ∈ set (tkeys t)›
  unfolding tkeys_def using tentries_complete by force

lemma map_of_keys: ‹map_of (map (λk. (k, f k)) ks) k = (if k ∈ set ks then Some (f k) else None)›
  by (induction ks) auto

lemma jget_keys:
  assumes ‹jget t k l = Some a›
  shows ‹k ∈ set (tkeys t)› ‹l ∈ set (tkeys (trow t k))›
proof -
  from assms obtain r where ‹tlookup t k = Some r› unfolding jget_def by (auto split: option.splits)
  then show ‹k ∈ set (tkeys t)› by (rule tkeys_complete)
  from assms show ‹l ∈ set (tkeys (trow t k))› unfolding jget_trow by (rule tkeys_complete)
qed

lemma pent_Nil:
  assumes ‹jget (kt_T K) k l = None› ‹jget (kt_C K) k l = None›
  shows ‹pent K k l = []›
  using assms by (simp add: pent_def kcands_def kreds_def)

lemma pcands_ptabs_of: ‹pcands (ptabs_of K) k l = pent K k l›
proof -
  let ?ks = ‹remdups (tkeys (kt_T K) @ tkeys (kt_C K))›
  let ?ls = ‹remdups (tkeys (trow (kt_T K) k) @ tkeys (trow (kt_C K) k))›
  show ?thesis
  proof (cases ‹k ∈ set ?ks ∧ l ∈ set ?ls›)
    case True
    then show ?thesis
      by (simp add: pcands_def ptabs_of_def jget_def tlookup_tab_of_assoc map_of_keys del: set_remdups)
  next
    case False
    have T: ‹jget (kt_T K) k l = None› using jget_keys[of ‹kt_T K› k l] False by fastforce
    have C: ‹jget (kt_C K) k l = None› using jget_keys[of ‹kt_C K› k l] False by fastforce
    have ‹jget (pt_A (ptabs_of K)) k l = None ∨ jget (pt_A (ptabs_of K)) k l = Some []›
      using False pent_Nil[OF T C]
      by (auto simp: ptabs_of_def jget_def tlookup_tab_of_assoc map_of_keys simp del: set_remdups)
    then show ?thesis unfolding pcands_def pent_Nil[OF T C] by auto
  qed
qed

lemma pecands_ptabs_of: ‹pecands (ptabs_of K) k = kreds K (kcands K k 0)›
proof (cases ‹k ∈ set (tkeys (kt_C K))›)
  case False
  then have ‹jget (kt_C K) k 0 = None› using jget_keys[of ‹kt_C K› k 0] by (cases ‹jget (kt_C K) k 0›) auto
  then show ?thesis using False
    by (simp add: pecands_def ptabs_of_def tlookup_tab_of_assoc map_of_keys kcands_def kreds_def)
qed (simp add: pecands_def ptabs_of_def tlookup_tab_of_assoc map_of_keys)

lemma ktarget_reduce:
  ‹ktarget K kstk l (IReduce j) = sfind (ptarget (ptabs_of K) kstk) (kred K j)›
  by (auto simp: ktarget_def ptarget_def kred_def ptabs_of_def split: option.split list.split)

lemma ktarget_reduces:
  ‹sfind (ktarget K kstk l) (map IReduce js) = sfind (ptarget (ptabs_of K) kstk) (kreds K js)›
  unfolding sfind_map kreds_def sfind_concat by (simp add: o_def ktarget_reduce)

lemma case_dact_same: ‹(case a of DShift ⇒ tl [] | DReduce _ ⇒ []) = []›
  by (cases a) simp_all

theorem pctl_eq: ‹pctl (ptabs_of K) c = kctl K c›
proof -
  obtain kstk v where c: ‹c = (kstk, v)› by (cases c)
  show ?thesis
  proof (cases kstk)
    case (Cons k rest)
    have kc: ‹kctl K (kstk, v) = map_option (λ(a, stk'). (a, stk', case a of DShift ⇒ tl v | DReduce _ ⇒ v))
        (sfind (ktarget K kstk (case v of [] ⇒ 0 | (_, l) # _ ⇒ l))
          ((case v of [] ⇒ [] | _ ⇒ [IShift]) @ map IReduce (kcands K k (case v of [] ⇒ 0 | (_, l) # _ ⇒ l))))›
      unfolding kctl_def Cons sfind_spick by (simp add: Let_def option.map_comp split: option.split prod.split)
    show ?thesis
    proof (cases v)
      case Nil
      show ?thesis unfolding c kc unfolding Cons Nil
        by (simp add: pctl_def pecands_ptabs_of ktarget_reduces case_dact_same)
    next
      case (Cons x v')
      obtain t l where x: ‹x = (t, l)› by (cases x)
      show ?thesis
      proof (cases ‹jget (kt_T K) k l›)
        case None
        have ‹ktarget K kstk l IShift = None› using None ‹kstk = k # rest› by (simp add: ktarget_def)
        then show ?thesis unfolding c kc unfolding ‹kstk = k # rest› Cons x
          using None ‹kstk = k # rest›
          by (simp add: pctl_def pcands_ptabs_of pent_def ktarget_reduces ktarget_def cong: dact.case_cong)
      next
        case (Some k')
        then show ?thesis unfolding c kc unfolding ‹kstk = k # rest› Cons x
          by (simp add: pctl_def pcands_ptabs_of pent_def ptarget_def ktarget_def)
      qed
    qed
  qed (simp add: c pctl_def kctl_def)
qed

lemma pctl_eq_fun: ‹pctl (ptabs_of K) = kctl K›
  by (rule ext) (rule pctl_eq)

lemma ptabs_of_sel: ‹pt_lal (ptabs_of K) = kt_lal K› ‹pt_miss (ptabs_of K) = kt_miss K›
  ‹pt_N (ptabs_of K) = kt_N K› ‹pt_pf (ptabs_of K) = kt_pf K›
  unfolding ptabs_of_def ptabs.sel by (rule refl)+

lemma pfinal_eq: ‹pfinal (ptabs_of K) = kfinal K›
  by (rule ext) (unfold pfinal_def kfinal_def ptabs_of_sel, rule refl)

lemma tenc_eq: ‹tenc (pnum (ptabs_of K)) = kenc K›
  by (rule ext) (unfold tenc_def pnum_def kenc_def ptabs_of_sel, rule refl)

subsection ‹The code equation›

lemma dparse_via_plain:
  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›
    and kt: ‹ktabs_of J = K›
    and pt: ‹ptabs_of K = P› and tn: ‹pnum P = f›
  shows ‹dparse G Shn w = brun (pctl P) (pfinal P) fst (None, 1, 1) ([i0], map (tenc f) w, [])›
  unfolding tn[symmetric] pt[symmetric] pctl_eq_fun pfinal_eq tenc_eq
  by (rule dparse_via_prod_loop[OF static st gt rt pcs pfs i0 lt jt kt])

end