Theory LR_Parser

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

theory LR_Parser
  imports TIGER_Grammar.LR_Plain TIGER_Grammar.LR_Sparse TIGER_Grammar.LR_Vec TIGER_Grammar.LR_Diag TIGER_Grammar.LR_Recover Grammar_Command
  keywords "parser_error_states" :: diag
begin

section ‹Parser-facing theorems: ‹dparse› composed with a decoder›

text ‹The backend (text‹Grammar_Command›) defines each generated parser
  as ‹λw. Option.bind (dparse G Shn w) dec›, where ‹dec› maps the raw
  ‹ast› to the grammar's carrier type.  Soundness of the composition is
  unconditional modulo const‹fresh_name› (discharged by construction of
  ‹Shn›); completeness additionally needs const‹mdet›
  cite‹‹Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› cite‹‹Thm.~3› in "jourdan2012-validating-lr1"›, which
  text‹rlalr_sufficient› reduces to ∗‹evaluation› of the static
  check const‹rlalr_conflicts›, so the emitted ‹.complete› theorem is
  hypothesis-free whenever the check computes ‹[]›.›

theorem dparse_bind_sound:
  assumes fn: ‹fresh_name G Shn›
    and rec: ‹Option.bind (dparse G Shn w) dec = Some x›
  shows ‹w ∈ ilang G›
proof (cases ‹dparse G Shn w›)
  case None with rec show ?thesis by simp
next
  case (Some t) show ?thesis using dparse_sound[OF fn Some] .
qed

theorem dparse_bind_complete:
  assumes fn: ‹fresh_name G Shn›
    and det: ‹mdet G Shn›
    and mem: ‹w ∈ ilang G›
    and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
                         ∃x. dec t = Some x›
  shows ‹∃x. Option.bind (dparse G Shn w) dec = Some x›
proof -
  from dparse_complete_lang[OF fn det mem] obtain t where
      parsed: ‹dparse G Shn w = Some t›
    and ao: ‹ast_of G (Nt (istart G)) (istart_ind G) t w› by blast
  from dec_total[OF ao] obtain x where ‹dec t = Some x› by blast
  with parsed show ?thesis by simp
qed

theorem dparse_bind:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn›
    and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
                        ∃x. dec t = Some x›
  shows ‹w ∈ ilang G ⟷ (∃x. Option.bind (dparse G Shn w) dec = Some x)›
proof
  assume ‹w ∈ ilang G›
  from dparse_bind_complete[OF fn det this dec_total] show
    ‹∃x. Option.bind (dparse G Shn w) dec = Some x› .
next
  assume ‹∃x. Option.bind (dparse G Shn w) dec = Some x›
  then obtain x where ‹Option.bind (dparse G Shn w) dec = Some x› ..
  from dparse_bind_sound[OF fn this] show ‹w ∈ ilang G› .
qed

subsection ‹Schematic forms for the backend's text‹define››

lemma dparse_sound_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
    and fn:   ‹fresh_name G Shn›
    and rec:  ‹parse_fn w = Some x›
  shows ‹w ∈ ilang G›
  by (metis body fn rec dparse_bind_sound)

lemma dparse_complete_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
    and fn:   ‹fresh_name G Shn›
    and det:  ‹mdet G Shn›
    and mem:  ‹w ∈ ilang G›
    and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
                         ∃x. dec t = Some x›
  shows ‹∃x. parse_fn w = Some x›
  using body dparse_bind_complete[OF fn det mem dec_total] by simp

section ‹Exact completeness: the driver returns the erasure of the tree›

text ‹text‹dparse_complete› only says that the driver returns ∗‹some› tree
  of the word.  Relating a generated parser to the relation family of
  ⬚‹grammar (relation)› needs more: the tree it returns must be the
  erasure of the tree the relation exhibits, i.e.\ the word must have a
  unique parse.  const‹mdet› does not give this.  The conflict report
  ignores the start production, so a configuration that ∗‹accepts› may
  still license a live reduce: a cycle ‹S ⇒⁺ S› through the start symbol,
  where the driver stops at the first accepting configuration and a second
  tree continues.  text‹acc_conflicts› is the missing static check: an
  LR(0) state holding the completed start item together with an
  end-of-input reduce cell of another production.  Together with
  const‹mdet› it pins the driver's answer to term‹erase pt›
  (text‹dparse_complete_exact›), and every parse tree of a word erases to
  the same ast (text‹ast_of_unique›).

  The uniqueness argument is that of Jourdan et al.
  cite‹‹Sect.~3.4, Thm.~4› in "jourdan2012-validating-lr1"›: the driver is a function, and
  by completeness it returns the value of each of two parses, so the two agree.  Barthwal
  cite‹‹Sect.~5.4.5, Thm.~5.4.5› in "barthwal2010-thesis-cfl-hol4"› proves that a grammar
  whose SLR machine is built without conflicts is unambiguous.  Here uniqueness holds up
  to erasure: two trees of a word give the same ast.›

subsection ‹The tree stack along an action list›

text ‹The tree-stack component of the driver depends only on the actions
  taken: a shift pushes the leaf of the next token, a reduce folds the
  right-hand side.  Along the trace of a tree it builds the tree's erasure.›

fun tsteps :: ‹('n, 't) dact list ⇒ ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list ⇒
    (('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list) option› where
  ‹tsteps [] s = Some s›
| ‹tsteps (DShift # acts) (v, tstk) =
     (case v of [] ⇒ None | t # v' ⇒ tsteps acts (v', Leaf t # tstk))›
| ‹tsteps (DReduce pr # acts) (v, tstk) =
     tsteps acts (v, Node (fst pr) (rev (take (length (snd pr)) tstk))
                     # drop (length (snd pr)) tstk)›

lemma tsteps_append:
  ‹tsteps (as @ bs) s = (case tsteps as s of None ⇒ None | Some s' ⇒ tsteps bs s')›
  by (induction as s rule: tsteps.induct) (auto split: list.splits)

lemma tsteps_concat:
  assumes ‹list_all2 (λpt tr. ∀rest tstk.
      tsteps tr (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)) pts trs›
  shows ‹tsteps (concat trs) (concat (map pyield pts) @ rest, tstk) =
           Some (rest, rev (map erase pts) @ tstk)›
  using assms
proof (induction arbitrary: rest tstk rule: list_all2_induct)
  case Nil show ?case by simp
next
  case (Cons pt pts tr trs)
  show ?case
    unfolding concat.simps list.map(2) tsteps_append append_assoc
    using Cons.hyps(1)[rule_format, of ‹concat (map pyield pts) @ rest› tstk] Cons.IH by simp
qed

lemma tsteps_mtrace:
  ‹mtrace G pt acts ⟹ tsteps acts (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)›
proof (induction arbitrary: rest tstk rule: mtrace.induct)
  case (mt_leaf t) show ?case by simp
next
  case (mt_node A rhs i pts trs)
  have kids: ‹list_all2 (λpt tr. ∀rest tstk.
      tsteps tr (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)) pts trs›
    using mt_node.IH by (rule list_all2_mono) blast
  have lenp: ‹length pts = length rhs› using mt_node.hyps(2) by (simp add: list_all2_lengthD)
  show ?case
    by (simp add: tsteps_append tsteps_concat[OF kids] lenp)
qed

subsection ‹One step of the driver, along the trace›

text ‹text‹dstep_of_imstep_exact› in terms of const‹tsteps›: the shift
  case has input left, since the machine shifted.›

lemma dstep_exact:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and stc: ‹sts = pr0_states G Shn›
    and gtc: ‹gt = pgtab G sts›
    and Lc: ‹L = la_fix G Shn›
    and rt: ‹redtab = red_buckets G Shn (length sts)›
    and det: ‹mdet G Shn›
    and ireach: ‹imreach G Shn gt sts ((Xs, w), istk)›
    and inv: ‹dfollow_ok G sts ((Xs, w), cstk, istk, v, tstk)›
    and step: ‹imstep G gt sts ((Xs, w), istk) act = Some (gc', istk')›
    and live: ‹dlive gc'›
    and lic: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ((Xs, w), istk) pr›
  shows ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w)) ∧
         (∃v' tstk'. tsteps [act] (v, tstk) = Some (v', tstk') ∧
            dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk)
              = Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk') ∧
            dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk'))›
proof -
  from dstep_of_imstep_exact[OF assms] obtain v' tstk' where
      cand: ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w))›
    and ts: ‹(v', tstk') = tstep act (v, tstk)›
    and ds: ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk)
              = Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
    and inv': ‹dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
    by blast
  have v_ne: ‹v ≠ []› if sh: ‹act = DShift›
  proof -
    have ‹w = tcols v› using inv unfolding dfollow_ok_def by simp
    moreover have ‹w ≠ []›
      using step unfolding sh imstep_def mstep_def mstep_cached_def
      by (auto split: list.splits)
    ultimately show ‹v ≠ []› by auto
  qed
  have ‹tsteps [act] (v, tstk) = Some (v', tstk')›
    using ts v_ne by (cases act) (auto split: list.splits)
  with cand ds inv' show ?thesis by blast
qed

subsection ‹The driver follows the trace without stopping early›

lemma dsteps_trace:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and stc: ‹sts = pr0_states G Shn›
    and gtc: ‹gt = pgtab G sts›
    and Lc: ‹L = la_fix G Shn›
    and rt: ‹redtab = red_buckets G Shn (length sts)›
    and det: ‹mdet G Shn› and fn: ‹fresh_name G Shn› and chk: ‹acc_conflicts G Shn = []›
  shows ‹mdrive G gt sts L acts (gc, istk) ⟹ imreach G Shn gt sts (gc, istk) ⟹
     dfollow_ok G sts (gc, cstk, istk, v, tstk) ⟹ dinv G Shn w (gc, cstk, istk, v, tstk) ⟹
     tsteps acts (v, tstk) = Some (v', tstk') ⟹
     (∀k < length acts. ∃stk. dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some stk ∧
         ¬ gfinal G Shn (fst stk)) ∧
     (∃gc'. mrun G acts gc = Some gc' ∧
        (∃istk'. dsteps G gt sts redtab (length acts) (gc, cstk, istk, v, tstk)
          = Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')))›
proof (induction acts arbitrary: gc istk cstk v tstk)
  case Nil
  have ‹cstk = map (xclosure_auto G) (fst gc)›
    using Nil.prems(3) unfolding dfollow_ok_def by (cases gc) simp
  then show ?case using Nil.prems(5) by auto
next
  case (Cons act acts)
  obtain Xs u where gc: ‹gc = (Xs, u)› by (cases gc)
  from mdrive_ConsD[OF Cons.prems(1)] obtain ic1 where
      st0: ‹imstep G gt sts (gc, istk) act = Some ic1› and lv0: ‹dlive (fst ic1)›
    and lc0: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts (gc, istk) pr›
    and rest0: ‹mdrive G gt sts L acts ic1› by blast
  obtain gc1 istk1 where ic1: ‹ic1 = (gc1, istk1)› by (cases ic1)
  have st: ‹imstep G gt sts ((Xs, u), istk) act = Some (gc1, istk1)›
    using st0 gc ic1 by simp
  have lv: ‹dlive gc1› using lv0 ic1 by simp
  have lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ((Xs, u), istk) pr›
    using lc0 gc by simp
  have ireach: ‹imreach G Shn gt sts ((Xs, u), istk)› using Cons.prems(2) gc by simp
  have inv: ‹dfollow_ok G sts ((Xs, u), cstk, istk, v, tstk)›
    using Cons.prems(3) gc by simp
  from dstep_exact[OF tab stc gtc Lc rt det ireach inv st lv lc] obtain v1 tstk1 where
      cand: ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, u))›
    and ts1: ‹tsteps [act] (v, tstk) = Some (v1, tstk1)›
    and ds: ‹dstep G gt sts redtab ((Xs, u), cstk, istk, v, tstk) =
            Some (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1)›
    and inv1: ‹dfollow_ok G sts (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1)›
    by blast
  have ms: ‹mstep G gc act = Some gc1›
    using imstep_mstep[of G gt sts ‹(gc, istk)› act ic1] st0 ic1 by simp
  have notfin: ‹¬ gfinal G Shn (Xs, u)›
  proof
    assume fin: ‹gfinal G Shn (Xs, u)›
    then have u: ‹u = []› unfolding gfinal_def by simp
    obtain pr where act: ‹act = DReduce pr›
    proof (cases act)
      case DShift
      with ms u have False unfolding mstep_def mstep_cached_def gc by simp
      then show ?thesis ..
    qed
    have ok: ‹didx_ok G (pr0_states G Shn) Xs istk›
      using Cons.prems(3) gc stc unfolding dfollow_ok_def by simp
    show False
      by (rule no_reduce_at_final[OF fn chk Cons.prems(4)[unfolded gc] ok fin
            cand[unfolded act rt stc] ms[unfolded gc act] lv])
  qed
  have dinv1: ‹dinv G Shn w (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1)›
    by (rule dstep_inv[OF fn Cons.prems(4)[unfolded gc] ds])
  have ireach1: ‹imreach G Shn gt sts (gc1, istk1)›
    using imreach_step[OF Cons.prems(2) st0 lv0] ic1 by simp
  have rest: ‹mdrive G gt sts L acts (gc1, istk1)› using rest0 ic1 by simp
  have ts_rest: ‹tsteps acts (v1, tstk1) = Some (v', tstk')›
    using Cons.prems(5) ts1 tsteps_append[of ‹[act]› acts ‹(v, tstk)›] by simp
  from Cons.IH[OF rest ireach1 inv1 dinv1 ts_rest] obtain gc' istk' where
      nf: ‹∀k < length acts. ∃stk. dsteps G gt sts redtab k
            (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1) = Some stk ∧
            ¬ gfinal G Shn (fst stk)›
    and mr: ‹mrun G acts gc1 = Some gc'›
    and dr: ‹dsteps G gt sts redtab (length acts)
              (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1) =
                Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
    by blast
  have ds': ‹dstep G gt sts redtab (gc, cstk, istk, v, tstk) =
      Some (gc1, map (xclosure_auto G) (fst gc1), istk1, v1, tstk1)›
    using ds gc by simp
  have A: ‹∀k < length (act # acts). ∃stk.
      dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some stk ∧ ¬ gfinal G Shn (fst stk)›
  proof (intro allI impI)
    fix k assume k: ‹k < length (act # acts)›
    show ‹∃stk. dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some stk ∧
        ¬ gfinal G Shn (fst stk)›
    proof (cases k)
      case 0
      then show ?thesis using notfin gc by simp
    next
      case (Suc k')
      then have ‹k' < length acts› using k by simp
      then show ?thesis
        using nf[rule_format, of k'] unfolding Suc dsteps_Suc_step[OF ds'] by simp
    qed
  qed
  have B: ‹mrun G (act # acts) gc = Some gc'› using ms mr by simp
  have C: ‹dsteps G gt sts redtab (Suc (length acts)) (gc, cstk, istk, v, tstk) =
      Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
    unfolding dsteps_Suc_step[OF ds'] by (rule dr)
  from A B C show ?case by auto
qed

lemma drunwf_of_dsteps:
  ‹dsteps G gt sts redtab n st = Some st' ⟹
   (∀k < n. ∃stk. dsteps G gt sts redtab k st = Some stk ∧ ¬ gfinal G Shn (fst stk)) ⟹
   gfinal G Shn (fst st') ⟹
   (case st' of (gc, cstk, istk, v, tstk) ⇒ tstk) = t # rest ⟹
   drunwf G Shn gt sts redtab st = Some t›
  by (rule drun_imp_drunwf[OF drun_of_dsteps])

subsection ‹The licensed run of a tree, from the root›

subsection ‹Exact completeness and uniqueness of the parse›

theorem dparse_complete_exact:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn› and chk: ‹acc_conflicts G Shn = []›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
  shows ‹dparse G Shn (pyield pt) = Some (erase pt)›
proof -
  let ?sts = ‹pr0_states G Shn› and ?gt = ‹pgtab G (pr0_states G Shn)›
  let ?L = ‹la_fix G Shn› and ?i0 = ‹st_find (pr0_states G Shn) (lr0_start G Shn)›
  let ?redtab = ‹red_buckets G Shn (length (pr0_states G Shn))›
  let ?w = ‹pyield pt›
  let ?st = ‹(([xinit G Shn], tcols ?w), [xclosure_auto G (xinit G Shn)], [?i0], ?w,
             [] :: ('m, 'ch, 'n, 't) ast list)›
  have tab: ‹tables_ok G Shn ?sts ?gt ?L› by (rule tables_ok_concrete)
  from mtrace_ex[OF wf] obtain acts where tr: ‹mtrace G pt acts› by blast
  have drv: ‹mdrive G ?gt ?sts ?L acts (([xinit G Shn], tcols ?w), [?i0])›
    by (rule mdrive_root[OF wf rt tr])
  have fin: ‹mcompletes G Shn acts ([xinit G Shn], tcols ?w)›
    by (rule mtrace_completes[OF wf tr rt])
  have inv: ‹dfollow_ok G ?sts ?st›
    using dfollow_ok_dinit[of G Shn ?w] unfolding dinit_def .
  have dinv: ‹dinv G Shn ?w ?st›
    using dinv_init[of G Shn ?w ?sts] unfolding dinit_def .
  have ts: ‹tsteps acts (?w, []) = Some ([], [erase pt])›
    using tsteps_mtrace[OF tr, of ‹[]› ‹[]›] by simp
  from dsteps_trace[OF tab refl refl refl refl det fn chk drv imreach_init inv dinv ts]
  obtain gc' istk' where
      nf: ‹∀k < length acts. ∃stk. dsteps G ?gt ?sts ?redtab k ?st = Some stk ∧
             ¬ gfinal G Shn (fst stk)›
    and mr: ‹mrun G acts ([xinit G Shn], tcols ?w) = Some gc'›
    and ds: ‹dsteps G ?gt ?sts ?redtab (length acts) ?st =
             Some (gc', map (xclosure_auto G) (fst gc'), istk', [], [erase pt])› by blast
  have gf: ‹gfinal G Shn gc'› using fin mr unfolding mcompletes_def by simp
  have ‹drunwf G Shn ?gt ?sts ?redtab ?st = Some (erase pt)›
    by (rule drunwf_of_dsteps[OF ds nf]) (use gf in simp_all)
  then show ?thesis unfolding dparse_def dinit_def Let_def by simp
qed

corollary ast_of_unique:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn› and chk: ‹acc_conflicts G Shn = []›
    and a: ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
    and b: ‹ast_of G (Nt (istart G)) (istart_ind G) t' w›
  shows ‹t = t'›
proof -
  from a obtain pt where ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)›
    ‹erase pt = t› ‹pyield pt = w› unfolding ast_of_def by blast
  then have 1: ‹dparse G Shn w = Some t› using dparse_complete_exact[OF fn det chk] by blast
  from b obtain pt' where ‹wf_ptree G pt'› ‹proot pt' = (Nt (istart G), istart_ind G)›
    ‹erase pt' = t'› ‹pyield pt' = w› unfolding ast_of_def by blast
  then have 2: ‹dparse G Shn w = Some t'› using dparse_complete_exact[OF fn det chk] by blast
  from 1 2 show ?thesis by simp
qed

subsection ‹Parser-facing forms: the relation family›

text ‹For ⬚‹grammar (relation)› the backend states soundness and
  completeness against the relation ‹P› of the start symbol.  The two
  ‹bridge› premises are per-grammar lemmas proved at parser-definition
  time (🗏‹parser_rel_bridge.ML›): a decoded value satisfies the relation, and
  the relation exhibits a tree the decoder maps to the value.›

lemma dparse_rel_sound_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
    and fn: ‹fresh_name G Shn›
    and bridge: ‹⋀pt x. wf_ptree G pt ⟹ proot pt = (Nt (istart G), istart_ind G) ⟹
                  dec (erase pt) = Some x ⟹ P (pyield pt) x›
    and rec: ‹parse_fn w = Some x›
  shows ‹P w x›
proof -
  from rec body obtain t where p: ‹dparse G Shn w = Some t› and d: ‹dec t = Some x›
    by (auto simp: bind_eq_Some_conv)
  from dparse_sound_ast[OF fn p] obtain pt where
      ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)› ‹erase pt = t› ‹pyield pt = w›
    unfolding ast_of_def by blast
  with bridge[of pt x] d show ?thesis by simp
qed

lemma dparse_rel_complete_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
    and fn: ‹fresh_name G Shn›
    and det: ‹mdet G Shn›
    and chk: ‹acc_conflicts G Shn = []›
    and bridge: ‹⋀w x. P w x ⟹ ∃pt. wf_ptree G pt ∧ proot pt = (Nt (istart G), istart_ind G) ∧
                  pyield pt = w ∧ dec (erase pt) = Some x›
    and rel: ‹P w x›
  shows ‹parse_fn w = Some x›
proof -
  from bridge[OF rel] obtain pt where wf: ‹wf_ptree G pt›
    and rt: ‹proot pt = (Nt (istart G), istart_ind G)› and y: ‹pyield pt = w›
    and d: ‹dec (erase pt) = Some x› by blast
  from dparse_complete_exact[OF fn det chk wf rt] have ‹dparse G Shn w = Some (erase pt)›
    by (simp add: y)
  with d body show ?thesis by simp
qed

subsection ‹Parser-facing forms: the tree›

text ‹For ⬚‹parser (ast)› the decoder is const‹Some›: the parser returns the
  tree of const‹dparse›, and the theorems speak of it. Soundness: the tree is the
  erasure of a parse tree of the word; completeness: the erasure of every parse tree is
  returned for its yield, which also makes the tree unique.›

lemma dparse_ast_sound_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
    and fn: ‹fresh_name G Shn›
    and rec: ‹parse_fn w = Some t›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
  using rec by (simp add: body dparse_sound_ast[OF fn])

lemma dparse_ast_complete_lang_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
    and fn: ‹fresh_name G Shn›
    and det: ‹mdet G Shn›
    and mem: ‹w ∈ ilang G›
  shows ‹∃t. parse_fn w = Some t›
  by (rule dparse_complete_generic[OF body fn det mem]) simp

lemma dparse_ast_complete_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
    and fn: ‹fresh_name G Shn›
    and det: ‹mdet G Shn›
    and chk: ‹acc_conflicts G Shn = []›
    and wf: ‹wf_ptree G pt›
    and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
  shows ‹parse_fn (pyield pt) = Some (erase pt)›
  using dparse_complete_exact[OF fn det chk wf rt] by (simp add: body)

lemma recover_no_error_ast_generic:
  assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
    and fn: ‹fresh_name G Shn›
    and rec: ‹parse_fn w = Some t›
    and none: ‹∀y ∈ set w. tok y ≠ e›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w ∧ e ∉ set (atoks t)›
  using recover_no_error_generic[OF body fn rec none] by simp


section ‹Explaining the reports›

text ‹Diagnostics for the ⬚‹parser› command, after Menhir's
  ‹.conflicts› file cite‹‹Sect.~6› in "pottier2026-menhir-manual"›: for every pair the checks return, the items of the
  state, a symbol path from the start state with a sample input
  (nonterminals expanded to shortest terminal words), the conflicting
  actions with the column relation each imposes on the lookahead against the
  state's anchor, and a bounded search for an annotated word on which the
  driver has two live candidates, a witness that the ambiguity is real and
  not an over-approximation of the check.  Nothing here enters a proof; the
  checks themselves are untouched.  Productions are reported by their index
  in const‹iprods›, which the command maps back to the source.›

subsection ‹Shortest terminal words›

fun syms_word :: ‹('n × 't list) list ⇒ ('n, 't) sym list ⇒ 't list option› where
  ‹syms_word tab [] = Some []›
| ‹syms_word tab (Tm a # xs) = map_option ((#) a) (syms_word tab xs)›
| ‹syms_word tab (Nt A # xs) = (case map_of tab A of
     None ⇒ None | Some w ⇒ map_option ((@) w) (syms_word tab xs))›

definition mw_step :: ‹('n, 't) is_cfg ⇒ ('n × 't list) list ⇒ ('n × 't list) list› where
  ‹mw_step G tab = fold (λ(A, rhs) tab'. case syms_word tab (map fst rhs) of
       None ⇒ tab'
     | Some w ⇒ (case map_of tab' A of
         None ⇒ (A, w) # tab'
       | Some w' ⇒ if length w < length w' then (A, w) # tab' else tab'))
     (iprods G) tab›

text ‹A shortest word has a derivation tree of height at most the number of
  nonterminals (a repeated nonterminal on a path can be cut), so this many
  rounds reach the fixpoint.›

definition min_words :: ‹('n, 't) is_cfg ⇒ ('n × 't list) list› where
  ‹min_words G = (mw_step G ^^ Suc (length (iprods G))) []›

subsection ‹Paths through an automaton›

fun path_bfs :: ‹('a ⇒ (('n, 't) sym × 'a) list) ⇒ 'a ⇒ nat ⇒
    'a list ⇒ ('a × ('n, 't) sym list) list ⇒ ('n, 't) sym list option› where
  ‹path_bfs succ tgt 0 seen wk = None›
| ‹path_bfs succ tgt (Suc n) seen [] = None›
| ‹path_bfs succ tgt (Suc n) seen ((i, p) # wk) =
     (if i = tgt then Some (rev p)
      else (let succs = fold (λ(X, j) acc.
              if j ∈ set seen ∨ j ∈ set (map fst wk) ∨ j ∈ set (map fst acc) then acc
              else acc @ [(j, X # p)]) (succ i) []
        in path_bfs succ tgt n (i # seen) (wk @ succs)))›

definition prod_no :: ‹('n, 't) is_cfg ⇒ 'n × ('n, 't) rhs ⇒ nat› where
  ‹prod_no G pr = (case filter (λ(i, q). q = pr) (zip [0..<length (iprods G)] (iprods G)) of
     [] ⇒ length (iprods G) | (i, _) # _ ⇒ i)›

subsection ‹The conflicting actions of a reported state›

datatype 't xact = XShift 't wrel | XReduce nat wrel

text ‹The pairs of const‹ipairs_at› that fire under
  const‹ifire›, plus the end-of-input reduce/reduce pairs of
  const‹rr_none_at›, with the actions kept: each carries the relation of
  the lookahead's column to the indentation of the acting item's left-hand
  side.›

definition rpairs_explained :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) witem list list ⇒ ('n, 't) lacell list ⇒ nat ⇒
    ('t option × 't xact × 't xact) list› where
  ‹rpairs_explained G Shn sp wrs L i =
     (let reds = ireds_gen Shn (wrs ! i) L i;
         shifts = ishifts (wrs ! i);
         fires = (λc1 c2. ifire Shn wrs (pgtab G sp) (anchored_nts G) (ifuel wrs)
             [] [(i, c1, c2)]);
         rr = concat (map (λ(t, (pr, m, τ)).
                List.map_filter (λ(t', (pr', m', τ')).
                  if prod_no G pr < prod_no G pr' ∧ t' = t ∧
                     (t = None ∨ fires (pr, m, τ) (pr', m', τ'))
                  then Some (t, XReduce (prod_no G pr) τ, XReduce (prod_no G pr') τ')
                  else None) reds) reds);
         sr = concat (map (λ(t, (pr, m, τ)). case t of None ⇒ [] | Some a ⇒
                List.map_filter (λ(a', (pr', m', τ')).
                  if a' = a ∧ fires (pr, m, τ) (pr', m', τ')
                  then Some (t, XReduce (prod_no G pr) τ, XShift a τ') else None) shifts) reds)
     in remdups (rr @ sr))›

text ‹The search is budgeted: at most three columns, at most 48 annotated
  words per conflict over all its lookaheads (a witness of a real ambiguity
  is typically among the first few; the budget bounds the cost of the
  over-approximating case).

  All column assignments of a token sequence, and the first of a list
  of annotated words on which the driver reaches an admissible configuration
  (for the report: one in the reported state) with two live
  candidates: the word, how many tokens remain unread there, and the
  candidates (const‹None› for a shift, the production index for a
  reduce).  The exploration runs over precomputed tables and a frontier,
  never recomputing the automaton per configuration.›

fun layouts :: ‹'t list ⇒ nat list ⇒ ('t × nat) list list› where
  ‹layouts [] cs = [[]]›
| ‹layouts (a # as) cs = concat (map (λw. map (λc. (a, c) # w) cs) (layouts as cs))›

definition ncols :: ‹nat ⇒ nat› where
  ‹ncols k = (case filter (λc. c ^ k ≤ 32) [2..<4] of [] ⇒ 2 | cs ⇒ last cs)›

definition wit_cands :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) lacell list list ⇒
    ('n, 't) gconfig × ('n, 't) xitem list list × nat list ⇒
    (('n, 't) dact × ('n, 't) gconfig × ('n, 't) xitem list list × nat list) list› where
  ‹wit_cands G sts gt redtab = (λ(gc, cstk, istk).
     let i = (case istk of [] ⇒ length sts | j # _ ⇒ j);
         cells = (if i < length redtab then redtab ! i else []);
         CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)
     in List.map_filter (λa. case mstep_cached G cstk gc a of
            Some gc' ⇒
              (if dlive gc'
               then Some (a, gc', (case a of
                      DShift ⇒ (xclosure_auto G (hd (fst gc')) # cstk,
                                dnext gt sts i (Tm (fst (hd (snd gc)))) # istk)
                    | DReduce pr ⇒ (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)))
               else None)
          | None ⇒ None)
          (dcands G i cells CL gc))›

fun wit_search :: ‹('st ⇒ (('n, 't) dact × 'st) list) ⇒ ('st ⇒ bool) ⇒ nat ⇒
    'st list ⇒ ('st × ('n, 't) dact list) option› where
  ‹wit_search cands ok 0 fr = None›
| ‹wit_search cands ok (Suc n) fr =
     (if fr = [] then None
      else (let cs = map (λst. (st, cands st)) fr in
        case filter (λ(st, c). ok st ∧ 1 < length c) cs of
          (st, c) # _ ⇒ Some (st, map fst c)
        | [] ⇒ wit_search cands ok n (remdups (concat (map (λ(st, c). map snd c) cs)))))›

fun first_witness :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list × ('n, 't) xitem list × nat ⇒
    (('n, 't) gconfig × ('n, 't) xitem list list × nat list ⇒
      (('n, 't) dact × ('n, 't) gconfig × ('n, 't) xitem list list × nat list) list) ⇒
    (('n, 't) gconfig × ('n, 't) xitem list list × nat list ⇒ bool) ⇒
    nat ⇒ ('t × nat) list list ⇒ (('t × nat) list × nat × nat option list) option› where
  ‹first_witness G init cands ok n [] = None›
| ‹first_witness G init cands ok n (w # ws) =
     (case init of (xi, xc, i0) ⇒
      (case wit_search cands ok n [(([xi], w), [xc], [i0])] of
        None ⇒ first_witness G init cands ok n ws
      | Some ((gc, _, _), acts) ⇒ Some (w, length (snd gc),
          map (λa. case a of DShift ⇒ None | DReduce pr ⇒ Some (prod_no G pr)) acts)))›

subsection ‹The explanations of a reported state›

text ‹Three levels, each over the one before: the symbol path from the start
  state to a reported state (all the report shows under
  ⬚‹[[grammar_explain = false]]›); the items of the state and the
  conflicting action pairs; and the sample input (nonterminals expanded to
  shortest terminal words) with a layout witness for the sample extended by
  each conflict lookahead.  The command searches witnesses in the first
  ⬚‹[[grammar_explain_states]]› reported states only and stops at the second
  level for the rest; the functions themselves are total on any state list.›

definition explain_paths :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list ⇒
    (nat × ('n, 't) sym list option) list› where
  ‹explain_paths G Shn is = (let sp = pr0_states G Shn; gp = pgtab G sp
     in map (λi. (i, path_bfs (λj. if j < length gp then gp ! j else []) i
          (Suc (length sp)) [] [(p0start G Shn, [])])) is)›

definition explain_rp_brief :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list ⇒
    (nat × (nat × nat) list × ('n, 't) sym list option ×
     ('t option × 't xact × 't xact) list) list› where
  ‹explain_rp_brief G Shn is = (let sp = pr0_states G Shn; L = la_fix G Shn;
       wrs = map (wreach G) sp
     in map (λ(i, path). let
          items = (if i < length sp then map (λ(pr, m). (prod_no G pr, m)) (sp ! i) else []);
          prs = (if i < length sp then rpairs_explained G Shn sp wrs L i else [])
        in (i, items, path, prs)) (explain_paths G Shn is))›

definition explain_rp :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list ⇒
    (nat × (nat × nat) list × ('n, 't) sym list option × 't list option ×
     ('t option × 't xact × 't xact) list ×
     (('t × nat) list × nat × nat option list) option) list› where
  ‹explain_rp G Shn is = (let
       sp = pr0_states G Shn; gp = pgtab G sp; mw = min_words G;
       cands = wit_cands G sp gp (red_buckets G Shn (length sp));
       xi = xinit G Shn; init = (xi, xclosure_auto G xi, p0start G Shn)
     in map (λ(i, items, path, prs). let
          sample = (case path of None ⇒ None | Some p ⇒ syms_word mw p);
          wit = (case sample of None ⇒ None | Some w ⇒
                  (let ws = map (λt. case t of None ⇒ w | Some a ⇒ w @ [a])
                              (remdups (map fst prs));
                       cs = [0..<ncols (length w + 1)]
                   in first_witness G init cands
                        (λ(_, _, istk). istk ≠ [] ∧ hd istk = i) (4 * (length w + 2) + 8)
                        (take 48 (concat (map (λu. layouts u cs) ws)))))
        in (i, items, path, sample, prs, wit)) (explain_rp_brief G Shn is))›

text ‹For const‹acc_conflicts›: the state, the productions reduced at end
  of input next to the completed start item, and the path to it in the
  automaton.›

definition explain_acc :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list ⇒
    (nat × nat list × ('n, 't) sym list option × 't list option) list› where
  ‹explain_acc G Shn is = (let
       sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix G Shn; mw = min_words G
     in map (λi. let
          prs = remdups (List.map_filter (λ(i', (pr, m), t, τ).
                  if i' = i ∧ m = length (snd pr) ∧ t = None ∧ pr ≠ start_prod G Shn
                  then Some (prod_no G pr) else None) L);
          path = path_bfs (λj. if j < length gp then gp ! j else []) i
                   (Suc (length sp)) [] [(p0start G Shn, [])];
          sample = (case path of None ⇒ None | Some p ⇒ syms_word mw p)
        in (i, prs, path, sample)) is)›


section ‹The checks of the ⬚‹parser› command›

text ‹The command evaluates these five values and nothing else: the two conflict
  reports, the symbol paths of the reported states (the report's cheapest level,
  const‹explain_paths›, over the automaton the checks have built), whether the
  grammar has no layout annotations (const‹ii›, the simple driver's condition)
  and whether every reduce cell with a token is unconstrained in width
  (const‹wany_ok›). The ‹let› shares the automaton, its goto table and the
  saturated cells between them. The tables themselves stay
  symbolic: the parser's table constants are defined by their terms
  (text‹lr_build_parse›), so the generated code computes each once when it loads, and
  no table is rebuilt as a term, which cost more than computing it.›

definition lr_checks :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 't list ⇒ nat list × nat list ×
    bool × bool × (nat × ('n, 't) sym list option) list × nat list› where
  ‹lr_checks G Shn ctrs =
     (let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
          ants = anchored_nts G; wrs = map (wreach G) sp; fuel = ifuel wrs;
          p0 = p0start G Shn; s0 = start_prod G Shn;
          confs = filter (rlalr_conflict_at_gen Shn wrs gp ants fuel L) [0..<length sp]
      in (confs,
          filter (λi. (s0, Suc 0) ∈ set (sp ! i) ∧
                    list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                              t = None ∧ pr ≠ s0) L)
            [0..<length sp],
          ii G, wany_ok (cell_buckets L (length sp)),
          map (λi. (i, path_bfs (λj. if j < length gp then gp ! j else []) i
               (Suc (length sp)) [] [(p0, [])])) confs,
          map (ntidx (vtoks G (cell_buckets L (length sp)))) ctrs))›

theorem lr_checks_eq:
  ‹lr_checks G Shn ctrs =
     (rlalr_conflicts G Shn, acc_conflicts G Shn, ii G,
      wany_ok (red_buckets G Shn (length (pr0_states G Shn))),
      explain_paths G Shn (rlalr_conflicts G Shn), vnums G Shn ctrs)›
  by (simp add: lr_checks_def vnums_def explain_paths_def red_buckets_def la_fix_def
        rlalr_conflicts_code acc_conflicts_code Let_def)


text ‹The simple driver's table construction needs one more value: the numbers of
  the token constructors (const‹pnum›). They are computed from the tables the
  parser's constants are defined by, in the same shape, so the backend turns the
  evaluated equation into one over its constants by rewriting with their definitions.›

definition lr_simple_checks :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 't list ⇒ nat list› where
  ‹lr_simple_checks G Shn ctrs =
     (let sts = pr0_states G Shn; gt = pgtab G sts; redtab = red_buckets G Shn (length sts);
          pc = pcomps G sts; pf = pfins Shn sts;
          K = ktabs_of (jtabs_of (mk_ltabs gt sts redtab pc pf))
      in map (pnum (ptabs_of K)) ctrs)›

text ‹Under text‹parser_literal_tables›, the simple driver's code equation names
  two tables beyond the token numbers: its start state and its action table.›

definition lr_simple_tables :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat × ('n, 't) ptabs› where
  ‹lr_simple_tables G Shn =
     (let sts = pr0_states G Shn; gt = pgtab G sts; redtab = red_buckets G Shn (length sts)
      in (st_find sts (lr0_start G Shn),
          ptabs_of (ktabs_of (jtabs_of (mk_ltabs gt sts redtab (pcomps G sts) (pfins Shn sts))))))›

lemma lr_simple_tables_eq:
  ‹lr_simple_tables G Shn =
     (st_find (pr0_states G Shn) (lr0_start G Shn),
      ptabs_of (ktabs_of (jtabs_of (mk_ltabs (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
        (red_buckets G Shn (length (pr0_states G Shn))) (pcomps G (pr0_states G Shn))
        (pfins Shn (pr0_states G Shn))))))›
  by (simp add: lr_simple_tables_def Let_def)

text ‹The checks and the simple driver's values in one evaluation: the token numbers
  and, if ‹lit›, the two tables above, only if the simple driver applies, from the
  automaton, goto table and cells the checks have built. The evaluation of
  const‹lr_simple_checks› alone would build them again.›

definition lr_checks_simple :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 't list ⇒ bool ⇒
    (nat list × nat list × bool × bool × (nat × ('n, 't) sym list option) list ×
     nat list) × (nat list × (nat × ('n, 't) ptabs) option) option› where
  ‹lr_checks_simple G Shn ctrs lit =
     (let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
          ants = anchored_nts G; wrs = map (wreach G) sp; fuel = ifuel wrs;
          p0 = p0start G Shn; s0 = start_prod G Shn;
          confs = filter (rlalr_conflict_at_gen Shn wrs gp ants fuel L) [0..<length sp];
          redtab = cell_buckets L (length sp); iok = ii G; wok = wany_ok redtab
      in ((confs,
           filter (λi. (s0, Suc 0) ∈ set (sp ! i) ∧
                     list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                               t = None ∧ pr ≠ s0) L)
             [0..<length sp],
           iok, wok,
           map (λi. (i, path_bfs (λj. if j < length gp then gp ! j else []) i
                (Suc (length sp)) [] [(p0, [])])) confs,
           map (ntidx (vtoks G redtab)) ctrs),
          if iok ∧ confs = [] ∧ wok
          then (let P = ptabs_of (ktabs_of (jtabs_of
                          (mk_ltabs gp sp redtab (pcomps G sp) (pfins Shn sp))))
                in Some (map (pnum P) ctrs,
                         if lit then Some (st_find sp (lr0_start G Shn), P) else None))
          else None))›

lemma lr_checks_simple_eq:
  ‹lr_checks_simple G Shn ctrs lit =
     (lr_checks G Shn ctrs,
      if ii G ∧ fst (lr_checks G Shn ctrs) = [] ∧
         wany_ok (red_buckets G Shn (length (pr0_states G Shn)))
      then Some (lr_simple_checks G Shn ctrs, if lit then Some (lr_simple_tables G Shn) else None)
      else None)›
  by (simp add: lr_checks_simple_def lr_checks_def lr_simple_checks_def lr_simple_tables_def
        red_buckets_def la_fix_def Let_def)

lemma lr_checks_simple_checks:
  ‹lr_checks_simple G Shn ctrs lit = (c, s) ⟹ lr_checks G Shn ctrs = c›
  by (simp add: lr_checks_simple_eq)

lemma lr_checks_simple_nums:
  ‹lr_checks_simple G Shn ctrs lit = (c, Some (ns, x)) ⟹ lr_simple_checks G Shn ctrs = ns›
  by (simp add: lr_checks_simple_eq split: if_splits)

lemma lr_checks_simple_tables:
  ‹lr_checks_simple G Shn ctrs lit = (c, Some (ns, Some t)) ⟹ lr_simple_tables G Shn = t›
  by (simp add: lr_checks_simple_eq split: if_splits)

text ‹Under text‹parser_literal_tables›, the tables of the state-indexed driver
  are evaluated as well, in one evaluation.›

definition lr_vec_tables :: ‹('n, 't) is_cfg ⇒ 'n ⇒
    ('n, 't) stab × ('n, 't) vtab × ('n, 't) vktab × ('n, 't) sitem list × ('n, 't) sitem list› where
  ‹lr_vec_tables G Shn =
     (let sts = pr0_states G Shn; gt = pgtab G sts; rt = red_buckets G Shn (length sts);
          T = mk_stab G Shn gt sts rt; V = mk_vtab G Shn T sts gt rt; kin = sinit T
      in (T, V, mk_vktab V, kin, sclosure T kin))›

lemma lr_vec_tables_eq:
  ‹lr_vec_tables G Shn =
     (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
        (red_buckets G Shn (length (pr0_states G Shn))),
      mk_vtab G Shn
        (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
           (red_buckets G Shn (length (pr0_states G Shn))))
        (pr0_states G Shn) (pgtab G (pr0_states G Shn))
        (red_buckets G Shn (length (pr0_states G Shn))),
      mk_vktab (mk_vtab G Shn
        (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
           (red_buckets G Shn (length (pr0_states G Shn))))
        (pr0_states G Shn) (pgtab G (pr0_states G Shn))
        (red_buckets G Shn (length (pr0_states G Shn)))),
      sinit (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
        (red_buckets G Shn (length (pr0_states G Shn)))),
      sclosure (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
          (red_buckets G Shn (length (pr0_states G Shn))))
        (sinit (mk_stab G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
          (red_buckets G Shn (length (pr0_states G Shn))))))›
  by (simp add: lr_vec_tables_def Let_def)

section ‹Coverage of the errors of a parser›

text ‹What 🗏‹lr_reach.ML› reads, as numbers, so that the tables are evaluated once:
  the automaton, the pairs of a state and a terminal whose action depends on the columns, and
  the driver as a function on words of terminals with their columns. Nothing here is
  proved, and nothing depends on it but warnings and the skeleton of an ‹errors› block
  cite‹‹Sect.~3› in "pottier2016-lr1-reachability"›.

  The states hold kernels, so a shift counts as decided by the columns if its terminal
  has a relation anywhere in the grammar. A reduction does if its cell has a relation,
  or if the left-hand side occurs with one, as the goto then narrows the anchors.›

definition lr_rel_syms :: ‹('n, 't) is_cfg ⇒ ('n, 't) sym list› where
  ‹lr_rel_syms G = remdups (concat (map (λ(A, rhs).
     map fst (filter (λ(X, r). r ≠ Any) rhs)) (iprods G)))›

definition lr_dep :: ‹('n, 't) is_cfg ⇒ 't list ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) lacell list list ⇒ nat list› where
  ‹lr_dep G ts gt rt = (let ss = lr_rel_syms G in
     concat (map (λ(i, row). concat (map (λ(X, _). (case X of
         Tm a ⇒ if X ∈ set ss then [i, ntidx ts a] else []
       | Nt _ ⇒ [])) row)) (zip [0..<length gt] gt)) @
     concat (map (λr. concat (map (λ(i, (pr, m), t, τ).
       if τ ≠ WAny ∨ Nt (fst pr) ∈ set ss
       then [i, case t of None ⇒ length ts | Some a ⇒ ntidx ts a] else []) r)) rt))›

text ‹‹on_error_reduce› cite‹‹Sect.~4› in "pottier2016-lr1-reachability"›:
  in the second run on a rejected word a state reduces a production of a named
  nonterminal on every terminal it has no action on. The production is the lowest one the
  state can reduce. The parser and its tables stay as they are.›

definition oer_prods :: ‹'n list ⇒ ('n, 't) is_cfg ⇒ ('n, 't) lacell list ⇒
    ('n × ('n, 't) rhs) list› where
  ‹oer_prods As G row = filter (λpr. fst pr ∈ set As ∧
     list_ex (λ(_, (pr', _), _, _). pr' = pr) row) (iprods G)›

definition oer_row :: ‹'n list ⇒ ('n, 't) is_cfg ⇒ 't list ⇒ nat ⇒ bool ⇒
    (('n, 't) sym × nat) list ⇒ ('n, 't) lacell list ⇒ ('n, 't) lacell list› where
  ‹oer_row As G ts i fin gr row = (case oer_prods As G row of
       [] ⇒ row
     | pr # _ ⇒
         row @ map (λz. (i, (pr, length (snd pr)), z, WAny))
           (filter (λz. ¬ list_ex (λ(_, _, t, _). t = z) row ∧
              (case z of None ⇒ ¬ fin | Some a ⇒ map_of gr (Tm a) = None))
            (None # map Some ts)))›

definition oer_cells :: ‹'n list ⇒ ('n, 't) is_cfg ⇒ 't list ⇒ bool list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) lacell list list› where
  ‹oer_cells As G ts pf gt rt =
     map (λ(i, fin, gr, row). oer_row As G ts i fin gr row) (zip [0..<length rt] (zip pf (zip gt rt)))›

definition oer_diag :: ‹('w ⇒ 'e + 'x) ⇒ ('w ⇒ 'e + 'x) ⇒ 'w ⇒ 'e + 'x› where
  ‹oer_diag f g w = (case f w of
     Inr x ⇒ Inr x
   | Inl e ⇒ (case g w of Inl e' ⇒ Inl e' | Inr _ ⇒ Inl e))›

lemma oer_diag_Inr_iff: ‹oer_diag f g w = Inr x ⟷ f w = Inr x›
  by (simp add: oer_diag_def split: sum.split)

text ‹In the recovery the plan stays that of the parser's tables, and the report is the
  one of ‹oer_diag›, with the repair of the plan.›

definition oer_stop :: ‹(nat ⇒ 'w ⇒ (('n, 't, 'ch, 'm) perr × 'p) option) ⇒
    ('w ⇒ ('n, 't, 'ch, 'm) perr + 'x) ⇒ nat ⇒ 'w ⇒ (('n, 't, 'ch, 'm) perr × 'p) option› where
  ‹oer_stop stop g b w = map_option (λ(e, pl).
     (case g w of Inl e' ⇒ e'⦇pe_repair := pe_repair e⦈ | Inr _ ⇒ e, pl)) (stop b w)›

text ‹For the pruning of the candidates that depend on columns (🗏‹lr_reach.ML›), the
  relations of the productions, the kernels, and the relation of each reduce cell, as numbers.
  A kernel item of no production of the grammar (the start item) gets the number of
  productions.›

definition lr_irel_code :: ‹irel ⇒ nat› where
  ‹lr_irel_code r = (case r of Eq ⇒ 0 | Gt ⇒ 1 | Ge ⇒ 2 | Any ⇒ 3)›

definition lr_wrel_code :: ‹wrel ⇒ nat› where
  ‹lr_wrel_code τ = (case τ of WEq ⇒ 0 | WGe ⇒ 1 | WGt ⇒ 2 | WLe ⇒ 3 | WLt ⇒ 4 | WAny ⇒ 5)›

definition lr_view :: ‹'n list ⇒ ('n, 't) is_cfg ⇒ bool list ⇒ nat ⇒ 't list ⇒
    ('n, 't) citem list list ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) lacell list list ⇒
    integer list list› where
  ‹lr_view As G pf i0 ts sts gt rt = (let
     nts = remdups (map fst (iprods G)); nt = length ts;
     prs = zip (iprods G) [0..<length (iprods G)];
     pnum = (λpr. case map_of prs pr of None ⇒ length (iprods G) | Some p ⇒ p);
     sc = (λX. case X of Tm a ⇒ ntidx ts a | Nt A ⇒ nt + 1 + ntidx nts A)
   in map (map integer_of_nat)
     [[length sts, nt, length nts, i0],
      concat (map (λ(i, row). concat (map (λ(X, j). [i, sc X, j]) row)) (zip [0..<length gt] gt)),
      concat (map (λ(A, rhs). ntidx nts A # length rhs # map (sc ∘ fst) rhs) (iprods G)),
      concat (map (λr. concat (map (λ(i, (pr, m), t, τ). case map_of prs pr of None ⇒ []
            | Some p ⇒ [i, p, case t of None ⇒ nt | Some a ⇒ ntidx ts a]) r)) rt),
      map fst (filter snd (zip [0..<length sts] pf)),
      lr_dep G ts gt rt,
      concat (map (λ(i, r). if Suc 0 < length (oer_prods As G r) then [i] else [])
        (zip [0..<length rt] rt)),
      concat (map (λ(A, rhs). length rhs # map (lr_irel_code ∘ snd) rhs) (iprods G)),
      concat (map (λ(i, k). i # length k # concat (map (λ(pr, m). [pnum pr, m]) k))
        (zip [0..<length sts] sts)),
      concat (map (λr. concat (map (λ(i, (pr, m), t, τ). [i, pnum pr, m,
          case t of None ⇒ nt | Some a ⇒ ntidx ts a, lr_wrel_code τ]) r)) rt)])›

fun reach_pairs :: ‹integer list ⇒ (nat × nat) list› where
  ‹reach_pairs (a # b # r) = (nat_of_integer a, nat_of_integer b) # reach_pairs r›
| ‹reach_pairs _ = []›

text ‹A rejected word as numbers, ‹[]› for an accepted one: the end of the input is
  term‹length ts›, and a terminal of no production the number after it.›

definition reach_enc :: ‹'t list ⇒ (nat × 't option × nat × nat × nat) option ⇒ integer list› where
  ‹reach_enc ts r = (case r of
     None ⇒ []
   | Some (st, tk, sh, idx, depth) ⇒ map integer_of_nat
       [st, case tk of None ⇒ length ts
          | Some a ⇒ if a ∈ set ts then ntidx ts a else Suc (length ts),
        sh, idx, depth])›

definition reach_fn :: ‹(('t, 'ch, 'm) token_scheme list ⇒ ('n, 't, 'ch, 'm) perr + 'x) ⇒
    ('t ⇒ string ⇒ nat ⇒ ('t, 'ch, 'm) token_scheme) ⇒ ('t × string) list ⇒
    integer list ⇒ integer list› where
  ‹reach_fn probe mk tss is =
     reach_enc (map fst tss) (diag_probe (probe (map (λ(t, c).
       (case tss ! t of (a, s) ⇒ mk a s c)) (reach_pairs is))))›

text ‹The checks with the errors of the words of an ‹errors› block, in one evaluation:
  the words run on the state-indexed driver over the automaton of the checks, as the
  parser's ‹p_probe› runs them over its constants, so that the tables are built once.
  The errors are not proved, only the checks: they are the first component. A grammar
  for the simple driver gets no errors here.›

definition lr_checks_keys :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 't list ⇒ 't list ⇒
    ('m, 'ch, 't) tword list ⇒ (nat list × nat list × bool × bool ×
      (nat × ('n, 't) sym list option) list × nat list) × integer list list› where
  ‹lr_checks_keys G Shn ctrs ts ws =
     (let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
          ants = anchored_nts G; wrs = map (wreach G) sp; fuel = ifuel wrs;
          p0 = p0start G Shn; s0 = start_prod G Shn;
          confs = filter (rlalr_conflict_at_gen Shn wrs gp ants fuel L) [0..<length sp];
          rt = cell_buckets L (length sp); i = ii G; wa = wany_ok rt
      in ((confs,
           filter (λi. (s0, Suc 0) ∈ set (sp ! i) ∧
                     list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
                               t = None ∧ pr ≠ s0) L)
             [0..<length sp],
           i, wa,
           map (λi. (i, path_bfs (λj. if j < length gp then gp ! j else []) i
                (Suc (length sp)) [] [(p0, [])])) confs,
           map (ntidx (vtoks G rt)) ctrs),
          if i ∧ confs = [] ∧ wa then []
          else
            (let T = mk_stab G Shn gp sp rt; V = mk_vtab G Shn T sp gp rt; kin = sinit T;
                 i0 = st_find sp (lr0_start G Shn)
             in map (λw. reach_enc ts (diag_probe
                  (vdiag V T kin (sclosure T kin) i0 [] (λ_. Some ()) w))) ws)))›

lemma lr_checks_keys_fst: ‹fst (lr_checks_keys G Shn ctrs ts ws) = lr_checks G Shn ctrs›
  by (simp add: lr_checks_keys_def lr_checks_def Let_def)

section ‹The LR backend of the ⬚‹parser› command›

text ‹The freshness of the start symbol as a list check: the simplifier proves this form for a
  concrete grammar quickly, whereas const‹fresh_name›'s image and bounded quantifiers over
  the grammar's productions take it minutes on a large grammar.›

lemma fresh_name_list_all:
  ‹fresh_name G Shn ⟷ Shn ≠ istart G ∧
     list_all (λ(A, rhs). A ≠ Shn ∧ list_all (λ(X, r). X ≠ Nt Shn) rhs) (iprods G)›
  unfolding fresh_name_def list_all_iff by (auto simp: image_iff split: prod.splits) blast+

ML_file ‹lr_reach.ML›
ML_file ‹lr_util.ML›
ML_file ‹lr_diag.ML›
ML_file ‹lr_build.ML›
ML_file ‹lr.ML›

end