Theory LR_Driver

(* Author: Basil Fürer *)

theory LR_Driver
  imports LR
begin

section ‹A complete deterministic LR driver with set-valued anchors›

text ‹
  A driver that guesses a single anchor column per reduce is incomplete.
  This driver gives the reduce a ∗‹set-valued› goto: the reduced
  nonterminal carries the set of all anchors its completed item admits, and
  each parent item keeps the anchors compatible with some of them.  The
  frames are the item-wise union of all single-anchor GLR frames, acceptance
  is exact, and no anchor is guessed.  Reduce licensing tests the LALR cell's
  width relation against that anchor set, so the remaining nondeterminism is
  the layout/LALR nondeterminism of the grammar.

  The driver follows Knuth's parsing method
  cite‹‹Sect.~II, Eqs.~(17)--(23)› in "knuth1965-lr-translation"›: a stack of
  state sets, a closure, a shift or a reduce, and the next state set.  The
  items are those of Adams' finite representation for indentation-sensitive
  grammars cite‹‹Sects.~5.5--5.6› in "adams2013"›.  Adams keeps one
  indentation set per item, and annotates closure items with the relation that
  leads to them cite‹‹Sect.~5.8› in "adams2013"›; the anchor sets and the
  cached closures below do the same.  Adams removes the nondeterminism by
  restricting to LR(k) grammars (Sect.~5.6); here that restriction is the
  operational hypothesis ‹mdet› of the completeness proof.
›

subsection ‹Closure-cached machine steps›

text ‹Frame closures are computed once, when the frame is pushed, and
  cached in a stack running in lockstep with the frame stack; the cache
  invariant ‹cstk_ok› says the two agree.›

definition cstk_ok :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list list ⇒
    ('n, 't) xitem list list ⇒ bool› where
  ‹cstk_ok G Xs cstk ⟷ list_all2 (λf c. c = xclosure_auto G f) Xs cstk›

lemma cstk_ok_len: ‹cstk_ok G Xs cstk ⟹ length cstk = length Xs›
  unfolding cstk_ok_def by (simp add: list_all2_conv_all_nth)

lemma cstk_ok_nth:
  ‹cstk_ok G Xs cstk ⟹ k < length Xs ⟹ cstk ! k = xclosure_auto G (Xs ! k)›
  unfolding cstk_ok_def by (auto simp: list_all2_conv_all_nth)

lemma cstk_ok_hd:
  ‹cstk_ok G Xs cstk ⟹ Xs ≠ [] ⟹ hd cstk = xclosure_auto G (hd Xs)›
  using cstk_ok_len cstk_ok_nth[of G Xs cstk 0]
  by (metis hd_conv_nth length_0_conv length_greater_0_conv)

lemma cstk_ok_drop:
  ‹cstk_ok G Xs cstk ⟹ cstk_ok G (drop k Xs) (drop k cstk)›
  unfolding cstk_ok_def by (rule list_all2_dropI)

lemma cstk_ok_push:
  ‹cstk_ok G Xs cstk ⟹ cstk_ok G (f # Xs) (xclosure_auto G f # cstk)›
  unfolding cstk_ok_def by simp

text ‹Liveness of a configuration, and the sentinel-safe table plumbing
  the driver consults (const‹la_next› over the goto table; the reduce
  cells of const‹la_fix› bucketed by state).›

fun tok_of :: ‹('t × nat) list ⇒ 't option› where
  ‹tok_of [] = None›
| ‹tok_of ((a, _) # _) = Some a›

definition dlive :: ‹('n, 't) gconfig ⇒ bool› where
  ‹dlive gc = (case gc of (Xs, w) ⇒ Xs ≠ [] ∧ live (hd Xs))›


text ‹Sentinel-safe successor lookup.›

definition dnext :: ‹(('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ nat ⇒ ('n, 't) sym ⇒ nat› where
  ‹dnext gt sts i X = (if i < length gt then la_next gt sts i X else length sts)›


text ‹Completed cells, bucketed by state index; the reduce cells of the
  driver are those of const‹la_fix›.›

definition cell_buckets :: ‹('n, 't) lacell list ⇒ nat ⇒ ('n, 't) lacell list list› where
  ‹cell_buckets L n = (let rt = filter (λ(i, itm, t, τ).
         snd itm = length (snd (fst itm))) L
     in map (λi. filter (λ(i', itm, t, τ). i' = i) rt) [0..<n])›

definition red_buckets :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat ⇒ ('n, 't) lacell list list› where
  ‹red_buckets G Shn n = cell_buckets (la_fix G Shn) n›

text ‹The ‹parser› command defines the reduce table over its constants for the
  automaton and the goto table, which const‹la_fix› would build again.›

lemma red_buckets_tables:
  assumes ‹pr0_states G Shn = sts› and ‹pgtab G sts = gt›
  shows ‹red_buckets G Shn (length sts) = cell_buckets (la_fix_gen G Shn gt sts) (length sts)›
  using assms unfolding red_buckets_def la_fix_def by simp


text ‹Auxiliary reasoning about const‹xclosure_auto› and const‹xgoto›.
  The closure only adds slot items (dot at ‹0›), so a kernel item found
  in a closure was already in the frame.›

lemma xclosure_auto_kernel:
  assumes ‹m > 0› and ‹((pr, m, R)) ∈ set (xclosure_auto G xs)›
  shows ‹((pr, m, R)) ∈ set xs›
proof -
  have ‹((pr, m, R)) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
    using assms(2) by (simp add: xclosure_auto_def xclosure_def)
  then show ?thesis
    by (cases rule: xslots_memE) (use assms(1) in simp_all)
qed

text ‹The extraction lemma for the option ccpo: on a chain, whenever the
  pointwise least upper bound is const‹Some›, some chain element is.
  Follows from the shape of text‹fun_lub› and text‹flat_lub›.›

subsection ‹Set-valued indentation operations›

text ‹Preimage of an indentation set under a relation: the parent anchors
  compatible with some child anchor in ‹R›,
  ‹{i. ∃j ∈ R. irel_sat r j i}›. For const‹Gt› and const‹Ge› this is
  the downward closure of the maximum, or everything if ‹R› is unbounded.›
fun irep_pre :: ‹irel ⇒ indrep ⇒ indrep› where
  ‹irep_pre Eq R = R›
| ‹irep_pre Gt (FinRep xs) = FinRep (filter (λi. list_ex (λx. i < x) xs) [0..<fold max xs 0])›
| ‹irep_pre Gt (UpRep xs n) = UpRep [] 0›
| ‹irep_pre Ge (FinRep xs) = FinRep (filter (λi. list_ex (λx. i ≤ x) xs) [0..<Suc (fold max xs 0)])›
| ‹irep_pre Ge (UpRep xs n) = UpRep [] 0›
| ‹irep_pre Any R = (if irep_nonempty R then UpRep [] 0 else FinRep [])›

lemma fold_max_acc: ‹a ≤ fold max xs (a :: nat)›
proof (induction xs arbitrary: a)
  case (Cons y ys)
  have ‹a ≤ max y a› by simp
  also have ‹… ≤ fold max ys (max y a)› by (rule Cons.IH)
  finally show ?case by simp
qed simp

lemma fold_max_ge: ‹x ∈ set xs ⟹ x ≤ fold max xs (a :: nat)›
proof (induction xs arbitrary: a)
  case (Cons y ys)
  show ?case
  proof (cases ‹x = y›)
    case True
    have ‹y ≤ max y a› by simp
    also have ‹… ≤ fold max ys (max y a)› by (rule fold_max_acc)
    finally show ?thesis using True by simp
  next
    case False
    with Cons show ?thesis by simp
  qed
qed simp

lemma irep_pre_correct [simp]:
  ‹irep_set (irep_pre r R) = {i. ∃j ∈ irep_set R. irel_sat r j i}›
proof (cases r)
  case Eq then show ?thesis by auto
next
  case Gt
  show ?thesis
  proof (cases R)
    case (FinRep xs)
    have bnd: ‹⋀i. ∃x∈set xs. i < x ⟹ i < fold max xs 0›
      using fold_max_ge[of _ xs 0] by (auto intro: less_le_trans)
    then show ?thesis using Gt FinRep by (auto simp: list_ex_iff)
  next
    case (UpRep xs n)
    have ‹∃xa ∈ set xs ∪ {m. n ≤ m}. x < xa› for x
      by (rule bexI[of _ ‹Suc (max n x)›]) auto
    then show ?thesis using Gt UpRep by auto
  qed
next
  case Ge
  show ?thesis
  proof (cases R)
    case (FinRep xs)
    have bnd: ‹⋀i j. j ∈ set xs ⟹ i ≤ j ⟹ i ≤ fold max xs 0›
      using fold_max_ge[of _ xs 0] by (auto intro: le_trans)
    then show ?thesis using Ge FinRep
      by (auto simp: list_ex_iff intro: bnd le_neq_implies_less)
  next
    case (UpRep xs n)
    have ‹∃xa ∈ set xs ∪ {m. n ≤ m}. x ≤ xa› for x
      by (rule bexI[of _ ‹max n x›]) auto
    then show ?thesis using Ge UpRep by auto
  qed
next
  case Any
  then show ?thesis by (cases R) auto
qed

text ‹Intersection of two indentation sets.›

fun irep_inter :: ‹indrep ⇒ indrep ⇒ indrep› where
  ‹irep_inter (FinRep xs) R = FinRep (filter (λi. irep_mem i R) xs)›
| ‹irep_inter (UpRep xs n) (FinRep ys) = FinRep (filter (λi. irep_mem i (UpRep xs n)) ys)›
| ‹irep_inter (UpRep xs n) (UpRep ys m) =
     UpRep (filter (λi. irep_mem i (UpRep ys m)) xs @ filter (λi. irep_mem i (UpRep xs n)) ys)
           (max n m)›

lemma irep_inter_correct [simp]:
  ‹irep_set (irep_inter R1 R2) = irep_set R1 ∩ irep_set R2›
  by (cases R1; cases R2) auto

text ‹Existence of an anchor in ‹R› related by a typ‹wrel› to a column.›

fun wsat_up :: ‹wrel ⇒ nat ⇒ nat ⇒ bool› where
  ‹wsat_up WEq c n ⟷ n ≤ c›
| ‹wsat_up WGe c n ⟷ n ≤ c›
| ‹wsat_up WGt c n ⟷ n < c›
| ‹wsat_up WLe c n ⟷ True›
| ‹wsat_up WLt c n ⟷ True›
| ‹wsat_up WAny c n ⟷ True›

lemma wsat_up_correct: ‹wsat_up τ c n ⟷ (∃j ≥ n. wsat τ c j)›
  by (cases τ) (auto intro: exI[of _ ‹Suc (max c n)›] exI[of _ ‹max c n›])

fun irep_ex_wsat :: ‹wrel ⇒ nat ⇒ indrep ⇒ bool› where
  ‹irep_ex_wsat τ c (FinRep xs) = list_ex (wsat τ c) xs›
| ‹irep_ex_wsat τ c (UpRep xs n) = (list_ex (wsat τ c) xs ∨ wsat_up τ c n)›

lemma irep_ex_wsat_correct [simp]:
  ‹irep_ex_wsat τ c R ⟷ (∃j ∈ irep_set R. wsat τ c j)›
  by (cases R) (auto simp: list_ex_iff wsat_up_correct)

subsection ‹Set-valued goto›

text ‹Advance the dot over ‹X› whose anchor is known to lie in ‹RA›; every
  item keeps the anchors compatible with some element of ‹RA›. For a terminal
  ‹RA› is the singleton of its column and this is const‹xgoto› up to the
  list representation of the indentation sets.›

definition lgoto :: ‹('n, 't) xitem list ⇒ ('n, 't) sym ⇒ indrep ⇒ ('n, 't) xitem list› where
  ‹lgoto xs X RA =
     map (λ(pr, m, R). (pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA)))
       (filter (λ(pr, m, R). m < length (snd pr) ∧ fst (snd pr ! m) = X) xs)›

lemma lgoto_dot_pos: ‹((pr, m, R)) ∈ set (lgoto xs X RA) ⟹ m > 0›
  unfolding lgoto_def by (auto simp: image_iff)

lemma lgoto_kernel_step:
  assumes ‹((pr, Suc m, R')) ∈ set (lgoto xs X RA)›
  obtains R where ‹((pr, m, R)) ∈ set xs›
    and ‹m < length (snd pr)›
    and ‹fst (snd pr ! m) = X›
    and ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
  using assms unfolding lgoto_def by (auto simp: image_iff)

lemma lgoto_memI:
  assumes ‹((pr, m, R)) ∈ set xs› and ‹m < length (snd pr)› and ‹fst (snd pr ! m) = X›
  shows ‹((pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA))) ∈ set (lgoto xs X RA)›
  using assms unfolding lgoto_def by force

text ‹The anchor set of a reduce: the union over the completed items of the
  production in the closure (there is one, but the union needs no
  distinctness argument).›

definition red_set :: ‹('n, 't) xitem list ⇒ 'n × ('n, 't) rhs ⇒ indrep› where
  ‹red_set CL pr = foldr (λ(pr', m, R) acc.
      if pr' = pr ∧ m = length (snd pr) then irep_union R acc else acc) CL (FinRep [])›

lemma red_set_correct:
  ‹irep_set (red_set CL pr) =
     ⋃ {irep_set R | R. ((pr, length (snd pr), R)) ∈ set CL}›
  unfolding red_set_def
  by (induction CL) (auto split: prod.splits if_splits)

lemma red_set_nonempty_iff:
  ‹irep_nonempty (red_set CL pr) ⟷
     (∃R. ((pr, length (snd pr), R)) ∈ set CL ∧ irep_nonempty R)›
  by (auto simp: red_set_correct)

subsection ‹The set-anchored machine›

text ‹Actions carry no anchor: a reduce is determined by its production. The
  step reads the frame closures off a cache stack running in lockstep with the
  frame stack; text‹mstep› is the cache-free form.›

datatype ('n, 't) dact = DShift | DReduce ‹'n × ('n, 't) rhs›

definition mstep_cached :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list list ⇒
    ('n, 't) gconfig ⇒ ('n, 't) dact ⇒ ('n, 't) gconfig option› where
  ‹mstep_cached G cstk gc act = (case gc of (Xs, w) ⇒ (case act of
      DShift ⇒ (case w of [] ⇒ None | (a, c) # w' ⇒
        (if Xs = [] then None
         else Some (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')))
    | DReduce pr ⇒
        (if Xs = [] ∨ ¬ length (snd pr) < length Xs then None
         else let R = red_set (hd cstk) pr in
           if irep_nonempty R
           then Some (lgoto (cstk ! length (snd pr)) (Nt (fst pr)) R
                      # drop (length (snd pr)) Xs, w)
           else None)))›

text ‹For the code, the depth test of a reduce without const‹length›, which
  walks the whole stack: a chain of ‹n› reduces at depth ‹n› would cost
  ‹O(n2)›.›

lemma mstep_cached_code [code]:
  ‹mstep_cached G cstk gc act = (case gc of (Xs, w) ⇒ (case act of
      DShift ⇒ (case w of [] ⇒ None | (a, c) # w' ⇒
        (if Xs = [] then None
         else Some (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')))
    | DReduce pr ⇒
        (if drop (length (snd pr)) Xs = [] then None
         else let R = red_set (hd cstk) pr in
           if irep_nonempty R
           then Some (lgoto (cstk ! length (snd pr)) (Nt (fst pr)) R
                      # drop (length (snd pr)) Xs, w)
           else None)))›
  unfolding mstep_cached_def by (auto split: prod.splits dact.splits)

definition mstep ::‹('n, 't) is_cfg ⇒ ('n, 't) gconfig ⇒ ('n, 't) dact ⇒
    ('n, 't) gconfig option› where
  ‹mstep G gc act = mstep_cached G (map (xclosure_auto G) (fst gc)) gc act›

lemma mstep_shift_shape:
  assumes ‹mstep_cached G cstk (Xs, w) DShift = Some gc'›
  obtains a c w' where ‹w = (a, c) # w'› and ‹Xs ≠ []›
    and ‹gc' = (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')›
  using assms unfolding mstep_cached_def by (auto split: list.splits if_splits)

lemma mstep_reduce_shape:
  assumes ‹mstep_cached G cstk (Xs, w) (DReduce pr) = Some gc'›
  obtains ‹length (snd pr) < length Xs› and ‹irep_nonempty (red_set (hd cstk) pr)›
    and ‹gc' = (lgoto (cstk ! length (snd pr)) (Nt (fst pr)) (red_set (hd cstk) pr)
                # drop (length (snd pr)) Xs, w)›
  using assms unfolding mstep_cached_def by (auto simp: Let_def split: if_splits)

fun mrun :: ‹('n, 't) is_cfg ⇒ ('n, 't) dact list ⇒ ('n, 't) gconfig ⇒ ('n, 't) gconfig option› where
  ‹mrun G [] gc = Some gc›
| ‹mrun G (act # acts) gc = (case mstep G gc act of None ⇒ None | Some gc' ⇒ mrun G acts gc')›

definition mcompletes :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) dact list ⇒ ('n, 't) gconfig ⇒ bool› where
  ‹mcompletes G Shn acts gc ⟷
     (case mrun G acts gc of None ⇒ False | Some gc' ⇒ gfinal G Shn gc')›

text ‹Configurations reachable from an initial one with any input.›

inductive mreach :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) gconfig ⇒ bool› for G Shn where
  mreach_init: ‹mreach G Shn ([xinit G Shn], w)›
| mreach_step: ‹mreach G Shn gc ⟹ mstep G gc act = Some gc' ⟹ mreach G Shn gc'›

subsection ‹The deterministic driver›

text ‹Driver state: machine configuration, closure cache, state-index stack,
  remaining spanned input, tree stack.›

type_synonym ('m, 'ch, 'n, 't) dst =
  ‹('n, 't) gconfig × ('n, 't) xitem list list × nat list × ('m, 'ch, 't) tword ×
   ('m, 'ch, 'n, 't) ast list›

text ‹Candidate actions at state index ‹i› with its reduce cells. A reduce of
  ‹pr› is offered when the closure completes ‹pr› with a non-empty anchor set
  ‹RS› and some cell for ‹(i, pr)› names the current token (or end of input)
  with a width relation that some anchor in ‹RS› satisfies against the token's
  column. The shift comes first whenever input remains.

  The candidates are the moves an LR automaton offers in DeRemer and
  Pennello's formulation cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›:
  a read where ‹Next› is defined and the reduces in ‹Reduce›, here restricted by
  the LALR cells and the anchor sets.  Unlike there, the shift is offered
  without a table lookup, and ‹dpick› below takes the first candidate
  whose machine step succeeds with a live successor.›

definition dlic :: ‹nat ⇒ ('n, 't) lacell list ⇒ ('t × nat) list ⇒
    'n × ('n, 't) rhs ⇒ indrep ⇒ bool› where
  ‹dlic i cells w pr RS ⟷ list_ex (λ(i', itm, t, τ).
       i' = i ∧ itm = (pr, length (snd pr)) ∧
       (case w of [] ⇒ t = None
                | (a, c) # _ ⇒ t = Some a ∧ irep_ex_wsat τ c RS)) cells›

definition dcands :: ‹('n, 't) is_cfg ⇒ nat ⇒ ('n, 't) lacell list ⇒ ('n, 't) xitem list ⇒
    ('n, 't) gconfig ⇒ ('n, 't) dact list› where
  ‹dcands G i cells CL gc = (case gc of (Xs, w) ⇒
     if Xs = [] then [] else
     let comps = remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL));
         reds = map DReduce (filter (λpr. let RS = red_set CL pr in
                    irep_nonempty RS ∧ dlic i cells w pr RS) comps)
     in (case w of [] ⇒ reds | _ ⇒ DShift # reds))›

fun dpick :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list list ⇒ ('n, 't) gconfig ⇒
    ('n, 't) dact list ⇒ (('n, 't) dact × ('n, 't) gconfig) option› where
  ‹dpick G cstk gc [] = None›
| ‹dpick G cstk gc (act # acts) =
     (case mstep_cached G cstk gc act of
        Some gc' ⇒ (if dlive gc' then Some (act, gc') else dpick G cstk gc acts)
      | None ⇒ dpick G cstk gc acts)›

text ‹One driver step.  A shift consumes a token; a reduce pops one entry per
  right-hand side symbol, as in Knuth's Eq.~(21)
  cite‹‹Sect.~II› in "knuth1965-lr-translation"›.  Both then push the state
  reached under the new symbol, as in Knuth's Step~3, Eq.~(23).  The reduce
  is the reduce action of the interpreter of Jourdan, Pottier and Leroy
  cite‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›, with the tree stack
  in place of their semantic values.›

definition dstep :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst option› where
  ‹dstep G gt sts redtab st = (case st of (gc, cstk, istk, v, tstk) ⇒
     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 (case dpick G cstk gc (dcands G i cells CL gc) of
        None ⇒ None
      | Some (act, gc') ⇒ Some (case act of
          DShift ⇒ (gc',
              xclosure_auto G (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk,
              tl v,
              Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc',
              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,
              v,
              Node (fst pr) (rev (take (length (snd pr)) tstk))
                # drop (length (snd pr)) tstk))))›

fun drun :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ nat ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option› where
  ‹drun G Shn gt sts redtab 0 st = (case st of (gc, cstk, istk, v, tstk) ⇒
     if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
     else None)›
| ‹drun G Shn gt sts redtab (Suc n) st = (case st of (gc, cstk, istk, v, tstk) ⇒
     if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
     else (case dstep G gt sts redtab st of
             None ⇒ None
           | Some st' ⇒ drun G Shn gt sts redtab n st'))›

partial_function (option) drunwf ::
  ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹drunwf G Shn gt sts redtab st =
     (case st of (gc, cstk, istk, v, tstk) ⇒
        if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
        else Option.bind (dstep G gt sts redtab st) (drunwf G Shn gt sts redtab))›

lemmas drunwf_simps [simp] = drunwf.simps

text ‹Not a code equation: generated code runs text‹drun_hist›, which ends a
  run that revisits a configuration (text‹drunwf_code› below).›

text ‹Entry points over the precise automaton: the six tables the
  text‹parser› command defines as constants, so generated code computes
  each once (text‹dparse_via_tables› below).›

definition dinit :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒ ('m, 'ch, 't) tword ⇒
    ('m, 'ch, 'n, 't) dst› where
  ‹dinit G Shn sts w = (([xinit G Shn], tcols w), [xclosure_auto G (xinit G Shn)],
     [st_find sts (lr0_start G Shn)], w, [])›

definition dparsen :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
    ('m, 'ch, 'n, 't) ast option› where
  ‹dparsen G Shn fuel w = (let sts = pr0_states G Shn; gt = pgtab G sts;
       redtab = red_buckets G Shn (length sts)
     in drun G Shn gt sts redtab fuel (dinit G Shn sts w))›

definition dparse :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('m, 'ch, 't) tword ⇒
    ('m, 'ch, 'n, 't) ast option› where
  ‹dparse G Shn w = (let sts = pr0_states G Shn; gt = pgtab G sts;
       redtab = red_buckets G Shn (length sts)
     in drunwf G Shn gt sts redtab (dinit G Shn sts w))›

text ‹Table inlining for the code generator: the six tables become constants,
  each defined by its term over the ones before it (or by its value under
  text‹parser_literal_tables›), and the driver is applied to those
  constants, so exported code computes each table once when it loads and each
  step is O(frame). The backend's text‹lr_build_parse› consumes this
  equation.›

lemma dparse_via_tables:
  assumes st:  ‹pr0_states G Shn = sts›
    and   gt:  ‹pgtab G sts = gtab›
    and   rt:  ‹red_buckets G Shn (length sts) = redtab›
    and   xi:  ‹xinit G Shn = xin›
    and   xc:  ‹xclosure_auto G xin = xclos›
    and   i0:  ‹st_find sts (lr0_start G Shn) = i0›
  shows ‹dparse G Shn w =
     drunwf G Shn gtab sts redtab (([xin], tcols w), [xclos], [i0], w, [])›
  unfolding dparse_def dinit_def Let_def
  by (simp add: st gt rt xi xc i0)

lemma drun_imp_drunwf:
  ‹drun G Shn gt sts redtab n st = Some t ⟹ drunwf G Shn gt sts redtab st = Some t›
  by (induction n arbitrary: st)
     (auto split: prod.splits option.splits if_splits list.splits)

subsection ‹Iterating the driver, and the bridge to const‹drun››

text ‹const‹drun› stops at the first const‹gfinal› state, so it does
  not compose across a subtree. text‹dsteps› is the ‹n›-fold iteration of
  const‹dstep›; it composes, and text‹drun_of_dsteps› converts a
  completed chain back into a const‹drun› result.›

fun dsteps :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ nat ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dst option› where
  ‹dsteps G gt sts redtab 0 st = Some st›
| ‹dsteps G gt sts redtab (Suc n) st =
     (case dstep G gt sts redtab st of
        None ⇒ None | Some st' ⇒ dsteps G gt sts redtab n st')›

lemma dsteps_Suc_step:
  ‹dstep G gt sts redtab st = Some st1 ⟹
     dsteps G gt sts redtab (Suc k) st = dsteps G gt sts redtab k st1›
  by simp

lemma drun_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 ⟹
   drun G Shn gt sts redtab n st = Some t›
proof (induction n arbitrary: st)
  case 0
  then have ‹st' = st› by simp
  then show ?case using 0 by (cases st) (auto split: list.splits)
next
  case (Suc n)
  have nf: ‹¬ gfinal G Shn (fst st)›
    using Suc.prems(2)[rule_format, of 0] by simp
  from Suc.prems(1) obtain st1 where
      sp: ‹dstep G gt sts redtab st = Some st1›
    and rest_run: ‹dsteps G gt sts redtab n st1 = Some st'›
    by (auto split: option.splits)
  have shift: ‹∀k < n. ∃stk. dsteps G gt sts redtab k st1 = Some stk ∧
                  ¬ gfinal G Shn (fst stk)›
  proof (intro allI impI)
    fix k assume ‹k < n›
    then have ‹Suc k < Suc n› by simp
    from Suc.prems(2)[rule_format, OF this] obtain stk where
        e: ‹dsteps G gt sts redtab (Suc k) st = Some stk›
      and nfk: ‹¬ gfinal G Shn (fst stk)› by blast
    show ‹∃stk. dsteps G gt sts redtab k st1 = Some stk ∧ ¬ gfinal G Shn (fst stk)›
      using e nfk unfolding dsteps_Suc_step[OF sp] by blast
  qed
  from Suc.IH[OF rest_run shift Suc.prems(3) Suc.prems(4)]
  have ‹drun G Shn gt sts redtab n st1 = Some t› .
  then show ?case using nf sp by (cases st) simp
qed

subsection ‹Shape of reachable stacks›

text ‹Every frame above the bottom is the set-valued goto of the closure of
  the frame below on a labelled symbol; ‹α› lists the labels, top first.›

definition dshape :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list list ⇒
    (('n, 't) sym × indrep) list ⇒ bool› where
  ‹dshape G Shn Xs α ⟷
     length Xs = length α + 1 ∧ Xs ! length α = xinit G Shn ∧
     (∀k < length α. Xs ! k =
        lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k)))›

lemma dshape_init: ‹dshape G Shn [xinit G Shn] []›
  unfolding dshape_def by simp

lemma dshape_push:
  assumes sh: ‹dshape G Shn Xs α› and ne: ‹Xs ≠ []›
  shows ‹dshape G Shn (lgoto (xclosure_auto G (hd Xs)) X RA # Xs) ((X, RA) # α)›
proof -
  have lenX: ‹length Xs = length α + 1› and bot: ‹Xs ! length α = xinit G Shn›
    and shp: ‹∀k < length α. Xs ! k =
        lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
    using sh unfolding dshape_def by auto
  have hd_eq: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
  show ?thesis unfolding dshape_def
  proof (intro conjI allI impI)
    fix k assume ‹k < length ((X, RA) # α)›
    then show ‹(lgoto (xclosure_auto G (hd Xs)) X RA # Xs) ! k =
        lgoto (xclosure_auto G ((lgoto (xclosure_auto G (hd Xs)) X RA # Xs) ! Suc k))
          (fst (((X, RA) # α) ! k)) (snd (((X, RA) # α) ! k))›
      using shp hd_eq by (cases k) auto
  qed (use lenX bot in auto)
qed

lemma dshape_reduce:
  assumes sh: ‹dshape G Shn Xs α› and k_lt: ‹k < length Xs›
  shows ‹dshape G Shn (lgoto (xclosure_auto G (Xs ! k)) X RA # drop k Xs) ((X, RA) # drop k α)›
proof -
  have lenX: ‹length Xs = length α + 1› and bot: ‹Xs ! length α = xinit G Shn›
    and shp: ‹∀k < length α. Xs ! k =
        lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
    using sh unfolding dshape_def by auto
  have k_le: ‹k ≤ length α› using k_lt lenX by simp
  show ?thesis unfolding dshape_def
  proof (intro conjI allI impI)
    show ‹length (lgoto (xclosure_auto G (Xs ! k)) X RA # drop k Xs) = length ((X, RA) # drop k α) + 1›
      using lenX k_le by simp
    show ‹(lgoto (xclosure_auto G (Xs ! k)) X RA # drop k Xs) ! length ((X, RA) # drop k α) = xinit G Shn›
      using lenX k_le bot by simp
    fix k' assume k'_lt: ‹k' < length ((X, RA) # drop k α)›
    show ‹(lgoto (xclosure_auto G (Xs ! k)) X RA # drop k Xs) ! k' =
        lgoto (xclosure_auto G ((lgoto (xclosure_auto G (Xs ! k)) X RA # drop k Xs) ! Suc k'))
          (fst (((X, RA) # drop k α) ! k')) (snd (((X, RA) # drop k α) ! k'))›
    proof (cases k')
      case 0
      then show ?thesis using k_lt by simp
    next
      case (Suc j)
      with k'_lt have j_lt: ‹k + j < length α› by simp
      then show ?thesis using shp Suc lenX by (simp add: add.commute)
    qed
  qed
qed

text ‹Every item of a closure on a shaped stack is a grammar production or
  the fresh start production (the latter only through the bottom frame).›

lemma dshape_prods:
  assumes sh: ‹dshape G Shn Xs α›
  shows ‹d ≤ length α ⟹ ((pr, m, R)) ∈ set (xclosure_auto G (Xs ! d)) ⟹
         pr ∈ set (iprods G) ∨ pr = start_prod G Shn›
proof (induct m arbitrary: d R)
  case 0
  have item: ‹((pr, 0, R)) ∈ set (xclosure_auto G (Xs ! d))› by fact
  have d_le: ‹d ≤ length α› by fact
  have item_slot:
    ‹((pr, 0, R)) ∈ set (xslots G (Xs ! d) (xiter G (Xs ! d) (xfuel G (Xs ! d))))›
    using item unfolding xclosure_auto_def xclosure_def by simp
  show ?case
  proof (cases rule: xslots_memE[OF item_slot])
    case 1
    show ?thesis
    proof (cases ‹d = length α›)
      case True
      then have ‹((pr, 0, R)) ∈ set (xinit G Shn)›
        using 1 sh unfolding dshape_def by simp
      then show ?thesis unfolding xinit_def start_prod_def by simp
    next
      case False
      then have d_lt: ‹d < length α› using d_le by simp
      have ‹Xs ! d = lgoto (xclosure_auto G (Xs ! Suc d)) (fst (α ! d)) (snd (α ! d))›
        using sh d_lt unfolding dshape_def by blast
      with 1 have ‹((pr, 0, R)) ∈ set (lgoto (xclosure_auto G (Xs ! Suc d)) (fst (α ! d)) (snd (α ! d)))›
        by simp
      from lgoto_dot_pos[OF this] show ?thesis by simp
    qed
  next
    case (2 p)
    then show ?thesis using nth_mem by force
  qed
next
  case (Suc n)
  have item: ‹((pr, Suc n, R)) ∈ set (xclosure_auto G (Xs ! d))› by fact
  have d_le: ‹d ≤ length α› by fact
  from xclosure_auto_kernel[OF _ item] have item_ker: ‹((pr, Suc n, R)) ∈ set (Xs ! d)› by simp
  show ?case
  proof (cases ‹d = length α›)
    case True
    then have ‹((pr, Suc n, R)) ∈ set (xinit G Shn)›
      using item_ker sh unfolding dshape_def by simp
    then show ?thesis unfolding xinit_def by simp
  next
    case False
    then have d_lt: ‹d < length α› using d_le by simp
    have Xs_d: ‹Xs ! d = lgoto (xclosure_auto G (Xs ! Suc d)) (fst (α ! d)) (snd (α ! d))›
      using sh d_lt unfolding dshape_def by blast
    from lgoto_kernel_step[OF item_ker[unfolded Xs_d]]
    obtain R1 where ‹((pr, n, R1)) ∈ set (xclosure_auto G (Xs ! Suc d))› by blast
    from Suc.hyps[OF _ this] d_lt show ?thesis by simp
  qed
qed

lemma lgoto_Nt_Shn_empty:
  assumes fn: ‹fresh_name G Shn› and sh: ‹dshape G Shn Xs α› and d_lt: ‹d < length Xs›
  shows ‹lgoto (xclosure_auto G (Xs ! d)) (Nt Shn) RA = []›
proof -
  have d_le: ‹d ≤ length α› using d_lt sh unfolding dshape_def by simp
  have no_match: ‹¬ (m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn)›
    if mem: ‹((pr, m, R)) ∈ set (xclosure_auto G (Xs ! d))› for pr m R
  proof (rule notI)
    assume A: ‹m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn›
    from dshape_prods[OF sh d_le mem]
    show False
    proof
      assume ‹pr ∈ set (iprods G)›
      then have ‹(fst pr, snd pr) ∈ set (iprods G)› by simp
      moreover have ‹snd pr ! m ∈ set (snd pr)› using A by simp
      ultimately show False
        using fn A unfolding fresh_name_def by (cases ‹snd pr ! m›) fastforce
    next
      assume ‹pr = start_prod G Shn›
      then show False using A fn unfolding start_prod_def fresh_name_def
        by (cases m) auto
    qed
  qed
  show ?thesis unfolding lgoto_def using no_match
    by (auto simp: filter_empty_conv case_prod_beta)
qed

text ‹Past-symbols descent on a shaped stack: an item at dot ‹m› in the
  closure of frame ‹d› was built over the ‹m› labels below, each compatible
  with every anchor the item still admits, from a dot-0 item admitting the
  same anchor.›

lemma past_symbols_set:
  assumes sh: ‹dshape G Shn Xs α›
  shows ‹m + d ≤ length α ⟹ ((pr, m, R)) ∈ set (xclosure_auto G (Xs ! d)) ⟹
         j ∈ irep_set R ⟹
         list_all2 (λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
                   (take m (snd pr)) (rev (map ((!) α) [d..<d + m])) ∧
         (∃R0. ((pr, 0, R0)) ∈ set (xclosure_auto G (Xs ! (d + m))) ∧ j ∈ irep_set R0)›
proof (induct m arbitrary: d R)
  case 0
  then show ?case by auto
next
  case (Suc n)
  have bnd: ‹Suc n + d ≤ length α› and item: ‹((pr, Suc n, R)) ∈ set (xclosure_auto G (Xs ! d))›
    and jmem: ‹j ∈ irep_set R› by fact+
  have d_lt: ‹d < length α› using bnd by simp
  from xclosure_auto_kernel[OF _ item] have item_ker: ‹((pr, Suc n, R)) ∈ set (Xs ! d)› by simp
  have Xs_d: ‹Xs ! d = lgoto (xclosure_auto G (Xs ! Suc d)) (fst (α ! d)) (snd (α ! d))›
    using sh d_lt unfolding dshape_def by blast
  from lgoto_kernel_step[OF item_ker[unfolded Xs_d]]
  obtain R1 where item1: ‹((pr, n, R1)) ∈ set (xclosure_auto G (Xs ! Suc d))›
    and n_lt: ‹n < length (snd pr)›
    and Xeq: ‹fst (snd pr ! n) = fst (α ! d)›
    and Req: ‹R = irep_inter R1 (irep_pre (snd (snd pr ! n)) (snd (α ! d)))›
    by blast
  from jmem[unfolded Req] have j1: ‹j ∈ irep_set R1›
    and jsat: ‹∃j' ∈ irep_set (snd (α ! d)). irel_sat (snd (snd pr ! n)) j' j›
    by auto
  have bnd': ‹n + Suc d ≤ length α› using bnd by simp
  from Suc.hyps[OF bnd' item1 j1]
  have IH: ‹list_all2 (λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
              (take n (snd pr)) (rev (map ((!) α) [Suc d..<Suc d + n]))›
    and R0: ‹∃R0. ((pr, 0, R0)) ∈ set (xclosure_auto G (Xs ! (Suc d + n))) ∧ j ∈ irep_set R0›
    by auto
  have take_expand: ‹take (Suc n) (snd pr) = take n (snd pr) @ [snd pr ! n]›
    using n_lt by (simp add: take_Suc_conv_app_nth)
  have rev_expand:
    ‹rev (map ((!) α) [d..<d + Suc n]) = rev (map ((!) α) [Suc d..<Suc d + n]) @ [α ! d]›
    by (simp add: Suc_le_eq upt_rec)
  have last_pair: ‹(λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
       (snd pr ! n) (α ! d)›
    using Xeq jsat by (cases ‹α ! d›) auto
  show ?case
  proof (intro conjI)
    show ‹list_all2 (λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
            (take (Suc n) (snd pr)) (rev (map ((!) α) [d..<d + Suc n]))›
      unfolding take_expand rev_expand
      by (rule list_all2_appendI[OF IH]) (simp add: last_pair)
    show ‹∃R0. ((pr, 0, R0)) ∈ set (xclosure_auto G (Xs ! (d + Suc n))) ∧ j ∈ irep_set R0›
      using R0 by simp
  qed
qed

subsection ‹Realizability of the tree stack›

text ‹An AST realizes a labelled symbol when every anchor of the label is the
  root indentation of some wellformed annotation of the AST.›

definition realizes :: ‹('n, 't) is_cfg ⇒ ('m, 'ch, 'n, 't) ast ⇒ ('n, 't) sym × indrep ⇒ bool› where
  ‹realizes G a XR ⟷
     (∀j ∈ irep_set (snd XR). ∃pt. wf_ptree G pt ∧ erase pt = a ∧ proot pt = (fst XR, j))›

fun ayield :: ‹('m, 'ch, 'n, 't) ast ⇒ ('m, 'ch, 't) tword› where
  ‹ayield (Leaf t) = [t]›
| ‹ayield (Node A ts) = concat (map ayield ts)›

lemma pyield_erase: ‹pyield pt = ayield (erase pt)›
  by (induction pt) (auto simp: map_concat cong: map_cong)

lemma realizes_leaf: ‹realizes G (Leaf t) (Tm (tok t), FinRep [s_col (token.span t)])›
  unfolding realizes_def
  by (auto intro!: exI[of _ ‹PLeaf t›] wf_ptree.wf_leaf)

text ‹Choosing realizations for the children of a reduce.›

lemma reduce_realizes:
  assumes sh: ‹dshape G Shn Xs α›
    and real: ‹⋀k. k < length α ⟹ realizes G (ts ! k) (α ! k)›
    and len_ts: ‹length ts = length α›
    and mem: ‹((pr, length (snd pr), R)) ∈ set (xclosure_auto G (Xs ! 0))›
    and k_le: ‹length (snd pr) ≤ length α›
    and j: ‹j ∈ irep_set R›
    and pr_ip: ‹pr ∈ set (iprods G)›
  shows ‹∃pt. wf_ptree G pt ∧ erase pt = Node (fst pr) (rev (take (length (snd pr)) ts)) ∧
              proot pt = (Nt (fst pr), j)›
proof -
  let ?k = ‹length (snd pr)›
  from past_symbols_set[OF sh, of ?k 0 pr R j] k_le mem j
  have la: ‹list_all2 (λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
              (snd pr) (rev (map ((!) α) [0..<?k]))› by simp
  have map_take: ‹map ((!) α) [0..<?k] = take ?k α›
    using k_le by (intro nth_equalityI) auto
  have la': ‹list_all2 (λXr (X, RA). X = fst Xr ∧ (∃j' ∈ irep_set RA. irel_sat (snd Xr) j' j))
              (snd pr) (rev (take ?k α))›
    using la map_take by simp
  have ex: ‹∀p < ?k. ∃pt. wf_ptree G pt ∧ erase pt = rev (take ?k ts) ! p ∧
              fst (proot pt) = fst (snd pr ! p) ∧ irel_sat (snd (snd pr ! p)) (snd (proot pt)) j›
  proof (intro allI impI)
    fix p assume p_lt: ‹p < ?k›
    have idx: ‹rev (take ?k α) ! p = α ! (?k - Suc p)›
      using p_lt k_le by (simp add: rev_nth)
    have idx_ts: ‹rev (take ?k ts) ! p = ts ! (?k - Suc p)›
      using p_lt k_le len_ts by (simp add: rev_nth)
    obtain X RA where XRA: ‹α ! (?k - Suc p) = (X, RA)› by (cases ‹α ! (?k - Suc p)›)
    from list_all2_nthD[OF la', of p] p_lt
    have ‹X = fst (snd pr ! p)› and ‹∃j' ∈ irep_set RA. irel_sat (snd (snd pr ! p)) j' j›
      using idx XRA by auto
    then obtain j' where j'mem: ‹j' ∈ irep_set RA› and sat: ‹irel_sat (snd (snd pr ! p)) j' j›
      and Xeq: ‹X = fst (snd pr ! p)› by blast
    have ‹realizes G (ts ! (?k - Suc p)) (X, RA)›
      using real[of ‹?k - Suc p›] p_lt k_le XRA by simp
    then obtain pt where ‹wf_ptree G pt› ‹erase pt = ts ! (?k - Suc p)› ‹proot pt = (X, j')›
      unfolding realizes_def using j'mem by auto
    then show ‹∃pt. wf_ptree G pt ∧ erase pt = rev (take ?k ts) ! p ∧
              fst (proot pt) = fst (snd pr ! p) ∧ irel_sat (snd (snd pr ! p)) (snd (proot pt)) j›
      using idx_ts Xeq sat by auto
  qed
  from ex obtain f where f: ‹∀p < ?k. wf_ptree G (f p) ∧ erase (f p) = rev (take ?k ts) ! p ∧
              fst (proot (f p)) = fst (snd pr ! p) ∧ irel_sat (snd (snd pr ! p)) (snd (proot (f p))) j›
    by (metis (no_types, lifting))
  let ?pts = ‹map f [0..<?k]›
  have la2: ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧ irel_sat (snd Xr) (snd (proot pt)) j ∧
                wf_ptree G pt) (snd pr) ?pts›
    using f by (auto simp: list_all2_conv_all_nth)
  have wf: ‹wf_ptree G (PNode (fst pr) j ?pts)›
    using wf_ptree.wf_node[OF _ la2] pr_ip by (cases pr) auto
  have er: ‹map erase ?pts = rev (take ?k ts)›
    using f len_ts k_le by (intro nth_equalityI) auto
  show ?thesis
    by (intro exI[of _ ‹PNode (fst pr) j ?pts›]) (use wf er in simp)
qed

subsection ‹The driver invariant and soundness›

text ‹The invariant has the parts of Barthwal's stack invariants for her SLR
  parser cite‹‹Defs.~5.4.2--5.4.4› in "barthwal2010-thesis-cfl-hol4"›:
  ‹dshape› says that each frame is the goto of the frame below it under the
  symbol pushed on it (‹validItem_inv›, Def.~5.4.3); ‹realizes› says that each
  tree on the stack is a wellformed tree for its symbol (‹validptree_inv›,
  Def.~5.4.2); and the last conjunct says that the yields of the trees followed
  by the remaining input give the whole input (‹leaves_eq_inv›, Def.~5.4.4).
  Jourdan, Pottier and Leroy state the last two as one relation between stack
  and consumed word cite‹‹Sect.~3.1› in "jourdan2012-validating-lr1"›.
  The closure cache, the state indices and the anchor sets ‹RAs› have no
  counterpart there.›

definition dinv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 'n, 't) dst ⇒ bool› where
  ‹dinv G Shn w st ⟷ (case st of (gc, cstk, istk, v, tstk) ⇒ (case gc of (Xs, w') ⇒
     cstk_ok G Xs cstk ∧ length istk = length Xs ∧ w' = tcols v ∧
     (∃RAs. length RAs = length tstk ∧
            dshape G Shn Xs (zip (map asym tstk) RAs) ∧
            (∀k < length tstk. realizes G (tstk ! k) (asym (tstk ! k), RAs ! k)) ∧
            w = concat (map ayield (rev tstk)) @ v)))›

lemma dinv_init: ‹dinv G Shn w (dinit G Shn sts w)›
  unfolding dinv_def dinit_def
  by (auto simp: cstk_ok_def dshape_init intro!: exI[of _ ‹[]›])

lemma dpick_sound:
  ‹dpick G cstk gc acts = Some (act, gc') ⟹
     act ∈ set acts ∧ mstep_cached G cstk gc act = Some gc' ∧ dlive gc'›
  by (induction acts) (auto split: option.splits if_splits)

lemma dstep_inv:
  assumes fn: ‹fresh_name G Shn›
    and inv: ‹dinv G Shn w st›
    and sp: ‹dstep G gt sts redtab st = Some st'›
  shows ‹dinv G Shn w st'›
proof -
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  obtain Xs w' where gc: ‹gc = (Xs, w')› by (cases gc)
  from inv[unfolded st gc dinv_def] obtain RAs where
      okc: ‹cstk_ok G Xs cstk› and len_i: ‹length istk = length Xs› and w': ‹w' = tcols v›
    and lenR: ‹length RAs = length tstk›
    and sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
    and real: ‹∀k < length tstk. realizes G (tstk ! k) (asym (tstk ! k), RAs ! k)›
    and yld: ‹w = concat (map ayield (rev tstk)) @ v›
    by auto
  have lenX: ‹length Xs = length tstk + 1› using sh lenR unfolding dshape_def by simp
  have Xs_ne: ‹Xs ≠ []› using lenX by auto
  define i where ‹i = (case istk of [] ⇒ length sts | j # _ ⇒ j)›
  define cells where ‹cells = (if i < length redtab then redtab ! i else [])›
  define CL where ‹CL = (case cstk of [] ⇒ [] | c # _ ⇒ c)›
  from sp[unfolded st gc dstep_def Let_def] obtain act gc' where
      pick: ‹dpick G cstk (Xs, w') (dcands G i cells CL (Xs, w')) = Some (act, gc')›
    and st': ‹st' = (case act of
          DShift ⇒ (gc', xclosure_auto G (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk, tl v, Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc', 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,
              v, Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk))›
    unfolding i_def cells_def CL_def by (auto split: option.splits)
  from dpick_sound[OF pick] have ms: ‹mstep_cached G cstk (Xs, w') act = Some gc'› and live: ‹dlive gc'›
    by auto
  show ?thesis
  proof (cases act)
    case DShift
    from mstep_shift_shape[OF ms[unfolded DShift]] obtain a c w'' where
        w'_eq: ‹w' = (a, c) # w''›
      and gc': ‹gc' = (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w'')› by blast
    from w' w'_eq obtain t0 v' where v: ‹v = t0 # v'› and a: ‹a = tok t0›
      and c: ‹c = s_col (token.span t0)› and w'': ‹w'' = tcols v'›
      by (cases v) auto
    have hdc: ‹hd cstk = xclosure_auto G (hd Xs)› using cstk_ok_hd[OF okc Xs_ne] .
    let ?F = ‹lgoto (xclosure_auto G (hd Xs)) (Tm a) (FinRep [c])›
    have st'_eq: ‹st' = ((?F # Xs, w''), xclosure_auto G ?F # cstk,
        dnext gt sts i (Tm (tok (hd v))) # istk, v', Leaf t0 # tstk)›
      using st' gc' hdc v unfolding DShift by simp
    have sh': ‹dshape G Shn (?F # Xs) (zip (map asym (Leaf t0 # tstk)) (FinRep [c] # RAs))›
      using dshape_push[OF sh Xs_ne, of ‹Tm a› ‹FinRep [c]›] a by simp
    have real': ‹∀k < length (Leaf t0 # tstk).
        realizes G ((Leaf t0 # tstk) ! k) (asym ((Leaf t0 # tstk) ! k), (FinRep [c] # RAs) ! k)›
    proof (intro allI impI)
      fix k assume ‹k < length (Leaf t0 # tstk)›
      then show ‹realizes G ((Leaf t0 # tstk) ! k)
          (asym ((Leaf t0 # tstk) ! k), (FinRep [c] # RAs) ! k)›
        using real realizes_leaf[of G t0] c by (cases k) auto
    qed
    have yld': ‹w = concat (map ayield (rev (Leaf t0 # tstk))) @ v'›
      using yld v by simp
    show ?thesis unfolding st'_eq dinv_def
      using cstk_ok_push[OF okc] len_i w'' lenR sh' real' yld'
      by (auto intro!: exI[of _ ‹FinRep [c] # RAs›])
  next
    case (DReduce pr)
    let ?k = ‹length (snd pr)›
    let ?RS = ‹red_set (hd cstk) pr›
    from mstep_reduce_shape[OF ms[unfolded DReduce]] have k_lt: ‹?k < length Xs›
      and RS_ne: ‹irep_nonempty ?RS›
      and gc': ‹gc' = (lgoto (cstk ! ?k) (Nt (fst pr)) ?RS # drop ?k Xs, w')› by blast+
    have hdc: ‹hd cstk = xclosure_auto G (hd Xs)› using cstk_ok_hd[OF okc Xs_ne] .
    have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
    have ck: ‹cstk ! ?k = xclosure_auto G (Xs ! ?k)› using cstk_ok_nth[OF okc k_lt] .
    from RS_ne obtain R where memR: ‹((pr, ?k, R)) ∈ set (xclosure_auto G (Xs ! 0))›
      and R_ne: ‹irep_nonempty R›
      unfolding red_set_nonempty_iff hdc hd0 by blast
    let ?F = ‹lgoto (xclosure_auto G (Xs ! ?k)) (Nt (fst pr)) ?RS›
    have gc'_eq: ‹gc' = (?F # drop ?k Xs, w')› using gc' ck by simp
    have pr_ip: ‹pr ∈ set (iprods G)›
    proof -
      from dshape_prods[OF sh _ memR] have ‹pr ∈ set (iprods G) ∨ pr = start_prod G Shn› by simp
      moreover have ‹pr ≠ start_prod G Shn›
      proof
        assume ‹pr = start_prod G Shn›
        then have ‹fst pr = Shn› unfolding start_prod_def by simp
        then have ‹?F = []› using lgoto_Nt_Shn_empty[OF fn sh k_lt] by simp
        then show False using live unfolding gc'_eq dlive_def live_def by simp
      qed
      ultimately show ?thesis by simp
    qed
    let ?node = ‹Node (fst pr) (rev (take ?k tstk))›
    let ?tstk' = ‹?node # drop ?k tstk›
    let ?RAs' = ‹?RS # drop ?k RAs›
    have st'_eq: ‹st' = ((?F # drop ?k Xs, w'), xclosure_auto G ?F # drop ?k cstk,
        dnext gt sts (istk ! ?k) (Nt (fst pr)) # drop ?k istk, v, ?tstk')›
      using st' gc'_eq unfolding DReduce by simp
    have k_le: ‹?k ≤ length tstk› using k_lt lenX by simp
    have zip_drop: ‹zip (map asym ?tstk') ?RAs' =
        (Nt (fst pr), ?RS) # drop ?k (zip (map asym tstk) RAs)›
      by (simp add: drop_map drop_zip)
    have sh': ‹dshape G Shn (?F # drop ?k Xs) (zip (map asym ?tstk') ?RAs')›
      unfolding zip_drop using dshape_reduce[OF sh k_lt] .
    have real_node: ‹realizes G ?node (Nt (fst pr), ?RS)›
      unfolding realizes_def
    proof (intro ballI)
      fix j assume ‹j ∈ irep_set (snd (Nt (fst pr), ?RS))›
      then obtain R' where memR': ‹((pr, ?k, R')) ∈ set (xclosure_auto G (Xs ! 0))›
        and j: ‹j ∈ irep_set R'›
        by (auto simp: red_set_correct hdc hd0)
      have real_z: ‹⋀k'. k' < length (zip (map asym tstk) RAs) ⟹
          realizes G (tstk ! k') (zip (map asym tstk) RAs ! k')›
        using real lenR by simp
      have len_eq: ‹length tstk = length (zip (map asym tstk) RAs)› using lenR by simp
      have k_le': ‹?k ≤ length (zip (map asym tstk) RAs)› using k_le lenR by simp
      from reduce_realizes[OF sh real_z len_eq memR' k_le' j pr_ip]
      show ‹∃pt. wf_ptree G pt ∧ erase pt = ?node ∧ proot pt = (fst (Nt (fst pr), ?RS), j)›
        by simp
    qed
    have real': ‹∀k' < length ?tstk'. realizes G (?tstk' ! k') (asym (?tstk' ! k'), ?RAs' ! k')›
    proof (intro allI impI)
      fix k' assume ‹k' < length ?tstk'›
      then show ‹realizes G (?tstk' ! k') (asym (?tstk' ! k'), ?RAs' ! k')›
        using real_node real lenR k_le by (cases k') auto
    qed
    have yld': ‹w = concat (map ayield (rev ?tstk')) @ v›
    proof -
      have rv: ‹rev (drop ?k tstk) @ rev (take ?k tstk) = rev tstk›
        by (metis append_take_drop_id rev_append)
      have ‹concat (map ayield (rev ?tstk')) =
            concat (map ayield (rev (drop ?k tstk) @ rev (take ?k tstk)))› by simp
      then show ?thesis using yld rv by simp
    qed
    show ?thesis unfolding st'_eq dinv_def
      using cstk_ok_push[OF cstk_ok_drop[OF okc]] len_i w' lenR k_le sh' real' yld' lenX k_lt
      by (auto intro!: exI[of _ ?RAs'])
  qed
qed

lemma dinv_final:
  assumes fn: ‹fresh_name G Shn›
    and inv: ‹dinv G Shn w st›
    and fin: ‹gfinal G Shn (fst st)›
  shows ‹∃t. (case st of (_, _, _, _, tstk) ⇒ tstk) = [t] ∧
             ast_of G (Nt (istart G)) (istart_ind G) t w›
proof -
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  obtain Xs w' where gc: ‹gc = (Xs, w')› by (cases gc)
  from inv[unfolded st gc dinv_def] obtain RAs where
      w': ‹w' = tcols v›
    and lenR: ‹length RAs = length tstk›
    and sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
    and real: ‹∀k < length tstk. realizes G (tstk ! k) (asym (tstk ! k), RAs ! k)›
    and yld: ‹w = concat (map ayield (rev tstk)) @ v›
    by auto
  have lenX: ‹length Xs = length tstk + 1› using sh lenR unfolding dshape_def by simp
  from fin[unfolded st gc] obtain pr R where w'_nil: ‹w' = []› and Xs_ne: ‹Xs ≠ []›
    and item: ‹((pr, Suc 0, R)) ∈ set (hd Xs)› and prShn: ‹fst pr = Shn›
    and i0: ‹irep_mem (istart_ind G) R›
    unfolding gfinal_def by (auto simp: list_ex_iff)
  have v_nil: ‹v = []› using w' w'_nil by (cases v) auto
  have tstk_ne: ‹tstk ≠ []›
  proof
    assume ‹tstk = []›
    then have ‹Xs = [xinit G Shn]› using lenX sh unfolding dshape_def by (cases Xs) auto
    then show False using item unfolding xinit_def by simp
  qed
  then have len_pos: ‹0 < length tstk› by simp
  have Xs0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) (asym (tstk ! 0)) (RAs ! 0)›
    using sh len_pos lenR unfolding dshape_def by simp
  have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
  from lgoto_kernel_step[OF item[unfolded hd0 Xs0]] obtain R1 where
      item1: ‹((pr, 0, R1)) ∈ set (xclosure_auto G (Xs ! Suc 0))›
    and lt: ‹0 < length (snd pr)›
    and X0: ‹fst (snd pr ! 0) = asym (tstk ! 0)›
    and Req: ‹R = irep_inter R1 (irep_pre (snd (snd pr ! 0)) (RAs ! 0))› by blast
  have one_le: ‹Suc 0 ≤ length (zip (map asym tstk) RAs)› using len_pos lenR by (cases tstk) auto
  from dshape_prods[OF sh one_le item1] have pr_start: ‹pr = start_prod G Shn›
    using prShn fn unfolding fresh_name_def by force
  then have snd_pr: ‹snd pr = [(Nt (istart G), Eq)]› unfolding start_prod_def by simp
  have sym0: ‹asym (tstk ! 0) = Nt (istart G)› using X0 snd_pr by simp
  have i0_RA: ‹istart_ind G ∈ irep_set (RAs ! 0)› using i0 Req snd_pr by auto
  from real[rule_format, OF len_pos] i0_RA sym0 obtain pt where
      wf: ‹wf_ptree G pt› and er: ‹erase pt = tstk ! 0›
    and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    unfolding realizes_def by auto
  have len1: ‹length tstk = 1›
  proof -
    have ‹((pr, 0, R1)) ∈ set (Xs ! Suc 0)›
    proof -
      have ‹((pr, 0, R1)) ∈ set (xslots G (Xs ! Suc 0) (xiter G (Xs ! Suc 0) (xfuel G (Xs ! Suc 0))))›
        using item1 unfolding xclosure_auto_def xclosure_def by simp
      then show ?thesis
      proof (cases rule: xslots_memE)
        case (2 p)
        then have ‹pr ∈ set (iprods G)› using nth_mem by force
        then show ?thesis using pr_start fn unfolding start_prod_def fresh_name_def by force
      qed
    qed
    moreover have ‹¬ Suc 0 < length tstk›
    proof
      assume ‹Suc 0 < length tstk›
      then have ‹Xs ! Suc 0 = lgoto (xclosure_auto G (Xs ! Suc (Suc 0)))
          (asym (tstk ! Suc 0)) (RAs ! Suc 0)›
        using sh lenR unfolding dshape_def by simp
      with ‹((pr, 0, R1)) ∈ set (Xs ! Suc 0)› show False using lgoto_dot_pos by fastforce
    qed
    ultimately show ?thesis using len_pos by (cases tstk) auto
  qed
  then obtain t where tstk_eq: ‹tstk = [t]› by (cases tstk) auto
  have ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
    unfolding ast_of_def using wf er rt yld tstk_eq v_nil
    by (auto simp: pyield_erase intro!: exI[of _ pt])
  then show ?thesis using tstk_eq unfolding st by simp
qed

theorem drun_sound_ast:
  assumes fn: ‹fresh_name G Shn›
  shows ‹drun G Shn gt sts redtab n st = Some t ⟹ dinv G Shn w st ⟹
         ast_of G (Nt (istart G)) (istart_ind G) t w›
proof (induction n arbitrary: st)
  case 0
  then have fin: ‹gfinal G Shn (fst st)›
    by (cases st) (auto split: if_splits)
  from dinv_final[OF fn 0(2) fin] 0(1) fin show ?case
    by (cases st) (auto split: if_splits)
next
  case (Suc n)
  show ?case
  proof (cases ‹gfinal G Shn (fst st)›)
    case True
    from dinv_final[OF fn Suc.prems(2) True] Suc.prems(1) True show ?thesis
      by (cases st) (auto split: if_splits)
  next
    case False
    with Suc.prems(1) obtain st1 where
        sp: ‹dstep G gt sts redtab st = Some st1›
      and rn: ‹drun G Shn gt sts redtab n st1 = Some t›
      by (cases st) (auto split: option.splits if_splits)
    from dstep_inv[OF fn Suc.prems(2) sp] have ‹dinv G Shn w st1› .
    from Suc.IH[OF rn this] show ?thesis .
  qed
qed

theorem dparsen_sound_ast:
  assumes fn: ‹fresh_name G Shn› and rec: ‹dparsen G Shn fuel w = Some t›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
  using drun_sound_ast[OF fn rec[unfolded dparsen_def Let_def] dinv_init] .

subsection ‹The fuel-free driver›

text ‹const‹drun› takes fuel, like the interpreter of Jourdan, Pottier and
  Leroy cite‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›; const‹drunwf›
  has none.  Every result of const‹drunwf› is a result of const‹drun›
  for some fuel, so soundness carries over.  Their completeness theorem states
  that enough fuel exists cite‹‹Sect.~3.3, Thm.~3› in "jourdan2012-validating-lr1"›;
  completeness here is stated for const‹dparse›, which takes no fuel.›

lemma drunwf_imp_drun_ex:
  assumes ‹drunwf G Shn gt sts redtab st = Some t›
  shows ‹∃n. drun G Shn gt sts redtab n st = Some t›
proof (rule drunwf.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab st t)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)›
    by (cases st)
  show ?case
  proof (cases ‹gfinal G Shn gc›)
    case True
    with "1"(2)[unfolded st] obtain rest where ‹tstk = t # rest›
      by (cases tstk) auto
    with True have ‹drun G Shn gt sts redtab 0 st = Some t›
      unfolding st by simp
    then show ?thesis by blast
  next
    case False
    with "1"(2)[unfolded st] obtain st1 where
        sp: ‹dstep G gt sts redtab (gc, cstk, istk, v, tstk) = Some st1›
      and rec: ‹f G Shn gt sts redtab st1 = Some t›
      by (auto simp: bind_eq_Some_conv)
    from "1"(1)[OF rec] obtain n where
      ‹drun G Shn gt sts redtab n st1 = Some t› ..
    with False sp have ‹drun G Shn gt sts redtab (Suc n) st = Some t›
      unfolding st by simp
    then show ?thesis by blast
  qed
qed

subsection ‹Repeated configurations: the code equation of const‹drunwf››

text ‹const‹drunwf› is a least fixed point: a run that revisits a
  configuration denotes const‹None›, but its unfolding equation, run as
  code, never returns.  Such runs exist for grammars the static check rejects
  (the command still emits their parser, with text‹mdet› as a premise):
  a unit self-loop ‹B = B› whose reduce is licensed at the end of the input
  rebuilds the frame it just popped.  Generated code therefore runs
  text‹drun_hist›, which records the configurations visited since the last
  shift and gives up on a repeat; text‹drunwf_code› proves the two equal.
  The control part of a state is everything but the tree stack, and two
  states between the same shifts share the input, so only the stacks are
  compared.  A chain of reduces that grows the stack without bound is not
  caught.  Jourdan, Pottier and Leroy point to the same cause, unit and empty
  productions that do not shrink the stack, and bound their interpreter by
  fuel instead cite‹‹Sect.~2.5› in "jourdan2012-validating-lr1"›.›

type_synonym ('m, 'ch, 'n, 't) dctrl_t =
  ‹('n, 't) gconfig × ('n, 't) xitem list list × nat list × ('m, 'ch, 't) tword›

type_synonym ('n, 't) dkey = ‹('n, 't) xitem list list × ('n, 't) xitem list list × nat list›

definition dctrl :: ‹('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) dctrl_t› where
  ‹dctrl st = (case st of (gc, cstk, istk, v, tstk) ⇒ (gc, cstk, istk, v))›

definition ckey :: ‹('m, 'ch, 'n, 't) dctrl_t ⇒ ('n, 't) dkey› where
  ‹ckey c = (case c of ((Xs, w), cstk, istk, v) ⇒ (Xs, cstk, istk))›

definition cwv :: ‹('m, 'ch, 'n, 't) dctrl_t ⇒ ('t × nat) list × ('m, 'ch, 't) tword› where
  ‹cwv c = (case c of ((Xs, w), cstk, istk, v) ⇒ (w, v))›

lemma ctrl_eqI: ‹ckey c = ckey d ⟹ cwv c = cwv d ⟹ c = d›
  unfolding ckey_def cwv_def by (cases c; cases d) auto

text ‹const‹dstep›, with the action it took.›

definition dstep_act :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ (('n, 't) dact × ('m, 'ch, 'n, 't) dst) option› where
  ‹dstep_act G gt sts redtab st = (case st of (gc, cstk, istk, v, tstk) ⇒
     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 (case dpick G cstk gc (dcands G i cells CL gc) of
        None ⇒ None
      | Some (act, gc') ⇒ Some (act, case act of
          DShift ⇒ (gc',
              xclosure_auto G (hd (fst gc')) # cstk,
              dnext gt sts i (Tm (tok (hd v))) # istk,
              tl v,
              Leaf (hd v) # tstk)
        | DReduce pr ⇒ (gc',
              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,
              v,
              Node (fst pr) (rev (take (length (snd pr)) tstk))
                # drop (length (snd pr)) tstk))))›

lemma dstep_eq_dstep_act:
  ‹dstep G gt sts redtab st = map_option snd (dstep_act G gt sts redtab st)›
  unfolding dstep_def dstep_act_def
  by (auto simp: Let_def split: prod.splits option.splits dact.splits)

lemma dstep_act_dctrl:
  assumes ‹dctrl st1 = dctrl st2›
  shows ‹rel_option (λ(a, s) (b, t). a = b ∧ dctrl s = dctrl t)
           (dstep_act G gt sts redtab st1) (dstep_act G gt sts redtab st2)›
proof -
  obtain gc cstk istk v tstk where s1: ‹st1 = (gc, cstk, istk, v, tstk)› by (cases st1)
  obtain gc' cstk' istk' v' tstk' where s2: ‹st2 = (gc', cstk', istk', v', tstk')› by (cases st2)
  from assms have eq: ‹gc' = gc› ‹cstk' = cstk› ‹istk' = istk› ‹v' = v›
    unfolding s1 s2 dctrl_def by auto
  show ?thesis unfolding s1 s2 eq dstep_act_def dctrl_def
    by (auto simp: Let_def split: option.splits dact.splits)
qed

lemma dstep_act_reduce_wv:
  assumes ‹dstep_act G gt sts redtab st = Some (DReduce pr, st')›
  shows ‹cwv (dctrl st') = cwv (dctrl st)›
proof -
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  from assms obtain gc' where pick: ‹dpick G cstk gc (dcands G (case istk of [] ⇒ length sts | j # _ ⇒ j)
        (if (case istk of [] ⇒ length sts | j # _ ⇒ j) < length redtab
         then redtab ! (case istk of [] ⇒ length sts | j # _ ⇒ j) else [])
        (case cstk of [] ⇒ [] | c # _ ⇒ c) gc) = Some (DReduce pr, gc')›
    and st': ‹st' = (gc', 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, v,
              Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)›
    unfolding st dstep_act_def by (auto simp: Let_def split: option.splits dact.splits)
  from dpick_sound[OF pick] have ‹mstep_cached G cstk gc (DReduce pr) = Some gc'› by simp
  then have ‹snd gc' = w›
    unfolding mstep_cached_def gc by (auto simp: Let_def split: if_splits)
  then show ?thesis unfolding st st' gc cwv_def dctrl_def by (cases gc') auto
qed

text ‹The step on control parts, with const‹gfinal› ending a run as
  const‹drun› does; text‹crel› is its graph, and a cycle in it makes
  every fuelled run fail.›

definition cnext :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dctrl_t ⇒ (('n, 't) dact × ('m, 'ch, 'n, 't) dctrl_t) option› where
  ‹cnext G Shn gt sts redtab c = (case c of (gc, cstk, istk, v) ⇒
     if gfinal G Shn gc then None
     else map_option (λ(a, st'). (a, dctrl st')) (dstep_act G gt sts redtab (gc, cstk, istk, v, [])))›

lemma cnext_dstep_act:
  assumes ‹¬ gfinal G Shn (fst (dctrl st))›
  shows ‹cnext G Shn gt sts redtab (dctrl st) =
         map_option (λ(a, st'). (a, dctrl st')) (dstep_act G gt sts redtab st)›
proof -
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  have ‹dctrl (gc, cstk, istk, v, []) = dctrl st› unfolding st dctrl_def by simp
  have rel: ‹rel_option (λ(a, s) (b, t). a = b ∧ dctrl s = dctrl t)
      (dstep_act G gt sts redtab (gc, cstk, istk, v, [])) (dstep_act G gt sts redtab st)›
    by (rule dstep_act_dctrl) (simp add: st dctrl_def)
  show ?thesis using assms rel unfolding st cnext_def
    by (cases ‹dstep_act G gt sts redtab (gc, cstk, istk, v, [])›;
        cases ‹dstep_act G gt sts redtab (gc, cstk, istk, v, tstk)›)
       (auto simp: dctrl_def)
qed

definition crel :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dctrl_t ⇒ ('m, 'ch, 'n, 't) dctrl_t ⇒ bool› where
  ‹crel G Shn gt sts redtab c d ⟷ (∃a. cnext G Shn gt sts redtab c = Some (a, d))›

lemma crel_det: ‹crel G Shn gt sts redtab c d ⟹ crel G Shn gt sts redtab c e ⟹ d = e›
  unfolding crel_def by auto

lemma crel_not_final:
  ‹crel G Shn gt sts redtab (dctrl st) e ⟹ ¬ gfinal G Shn (fst (dctrl st))›
  unfolding crel_def cnext_def dctrl_def by (cases st) auto

lemma crel_step:
  assumes ‹crel G Shn gt sts redtab (dctrl st) e›
  obtains a st' where ‹dstep_act G gt sts redtab st = Some (a, st')› ‹dctrl st' = e›
proof -
  from assms obtain a where
    ‹map_option (λ(a, st'). (a, dctrl st')) (dstep_act G gt sts redtab st) = Some (a, e)›
    unfolding crel_def cnext_dstep_act[OF crel_not_final[OF assms]] by blast
  then show thesis by (cases ‹dstep_act G gt sts redtab st›) (auto intro: that)
qed

lemma drun_on_cycle_None:
  assumes ‹(crel G Shn gt sts redtab)++ c (dctrl st)› ‹(crel G Shn gt sts redtab)++ (dctrl st) c›
  shows ‹drun G Shn gt sts redtab n st = None›
  using assms
proof (induction n arbitrary: st)
  case (0 st)
  from converse_tranclpE[OF "0.prems"(2)] obtain e where ‹crel G Shn gt sts redtab (dctrl st) e›
    by blast
  from crel_not_final[OF this] show ?case by (cases st) (auto simp: dctrl_def)
next
  case (Suc n st)
  from converse_tranclpE[OF Suc.prems(2)] obtain e where e: ‹crel G Shn gt sts redtab (dctrl st) e›
    by blast
  note nf = crel_not_final[OF e]
  from crel_step[OF e] obtain a st' where
    step: ‹dstep_act G gt sts redtab st = Some (a, st')› and st': ‹dctrl st' = e› by blast
  have ce: ‹(crel G Shn gt sts redtab)++ c e›
    using Suc.prems(1) e by (rule tranclp.trancl_into_trancl)
  have ec: ‹(crel G Shn gt sts redtab)++ e c›
  proof (rule converse_tranclpE[OF Suc.prems(2)])
    assume ‹crel G Shn gt sts redtab (dctrl st) c›
    from crel_det[OF e this] have ‹e = c› .
    then show ?thesis using Suc.prems by (auto intro: tranclp_trans)
  next
    fix e' assume ‹crel G Shn gt sts redtab (dctrl st) e'› ‹(crel G Shn gt sts redtab)++ e' c›
    with crel_det[OF e] show ?thesis by blast
  qed
  have ‹drun G Shn gt sts redtab (Suc n) st = drun G Shn gt sts redtab n st'›
    using nf step by (cases st) (auto simp: dctrl_def dstep_eq_dstep_act)
  also have ‹… = None› using Suc.IH[OF ce[unfolded st'[symmetric]] ec[unfolded st'[symmetric]]] .
  finally show ?case .
qed

lemma drunwf_on_cycle_None:
  assumes ‹(crel G Shn gt sts redtab)++ c (dctrl st)› ‹(crel G Shn gt sts redtab)++ (dctrl st) c›
  shows ‹drunwf G Shn gt sts redtab st = None›
  using drunwf_imp_drun_ex[of G Shn gt sts redtab st] drun_on_cycle_None[OF assms]
  by (cases ‹drunwf G Shn gt sts redtab st›) auto

text ‹The driver with a history of the configurations since the last shift.›

partial_function (option) drun_hist ::
  ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) dkey list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹drun_hist G Shn gt sts redtab seen st =
     (case st of (gc, cstk, istk, v, tstk) ⇒
        if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
        else if ckey (dctrl st) ∈ set seen then None
        else Option.bind (dstep_act G gt sts redtab st) (λ(a, st').
               drun_hist G Shn gt sts redtab
                 (if a = DShift then [] else ckey (dctrl st) # seen) st'))›

lemmas drun_hist_simps [code] = drun_hist.simps

text ‹Every recorded configuration precedes the current one in text‹crel›
  and shares its input, so a repeat is a cycle.›

definition hist_ok :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) dkey list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ bool› where
  ‹hist_ok G Shn gt sts redtab seen st ⟷
     (∀k ∈ set seen. ∃c. ckey c = k ∧ cwv c = cwv (dctrl st) ∧
        (crel G Shn gt sts redtab)++ c (dctrl st))›

lemma hist_ok_Nil [simp]: ‹hist_ok G Shn gt sts redtab [] st›
  unfolding hist_ok_def by simp

lemma hist_ok_seen_cycle:
  assumes ‹hist_ok G Shn gt sts redtab seen st› ‹ckey (dctrl st) ∈ set seen›
  shows ‹drunwf G Shn gt sts redtab st = None›
proof -
  from assms obtain c where ‹ckey c = ckey (dctrl st)› ‹cwv c = cwv (dctrl st)›
    and r: ‹(crel G Shn gt sts redtab)++ c (dctrl st)› unfolding hist_ok_def by blast
  from ctrl_eqI[OF this(1,2)] r have ‹(crel G Shn gt sts redtab)++ (dctrl st) (dctrl st)› by simp
  from drunwf_on_cycle_None[OF this this] show ?thesis .
qed

lemma hist_ok_step:
  assumes ok: ‹hist_ok G Shn gt sts redtab seen st›
    and nf: ‹¬ gfinal G Shn (fst (dctrl st))›
    and step: ‹dstep_act G gt sts redtab st = Some (a, st')›
  shows ‹hist_ok G Shn gt sts redtab (if a = DShift then [] else ckey (dctrl st) # seen) st'›
proof (cases ‹a = DShift›)
  case True
  then show ?thesis by simp
next
  case False
  then obtain pr where a: ‹a = DReduce pr› by (cases a) auto
  have r: ‹crel G Shn gt sts redtab (dctrl st) (dctrl st')›
    unfolding crel_def cnext_dstep_act[OF nf] step by simp
  have wv: ‹cwv (dctrl st') = cwv (dctrl st)› using dstep_act_reduce_wv step[unfolded a] .
  show ?thesis
  proof (unfold hist_ok_def, intro ballI)
    fix k assume ‹k ∈ set (if a = DShift then [] else ckey (dctrl st) # seen)›
    with False have ‹k = ckey (dctrl st) ∨ k ∈ set seen› by simp
    then show ‹∃c. ckey c = k ∧ cwv c = cwv (dctrl st') ∧ (crel G Shn gt sts redtab)++ c (dctrl st')›
    proof
      assume ‹k = ckey (dctrl st)›
      then show ?thesis using r wv
        by (intro exI[where x = ‹dctrl st›] conjI) (simp_all add: tranclp.r_into_trancl)
    next
      assume ‹k ∈ set seen›
      with ok obtain c where ‹ckey c = k› ‹cwv c = cwv (dctrl st)›
        and ‹(crel G Shn gt sts redtab)++ c (dctrl st)› unfolding hist_ok_def by blast
      then show ?thesis using r wv
        by (intro exI[where x = c] conjI) (simp_all add: tranclp.trancl_into_trancl)
    qed
  qed
qed

lemma drun_hist_imp_drunwf:
  assumes ‹drun_hist G Shn gt sts redtab seen st = Some t›
  shows ‹hist_ok G Shn gt sts redtab seen st ⟶ drunwf G Shn gt sts redtab st = Some t›
proof (rule drun_hist.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab seen st t)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹gfinal G Shn gc›)
    case True
    with "1"(2)[unfolded st] obtain rest where ‹tstk = t # rest› by (cases tstk) auto
    with True show ?thesis unfolding st by simp
  next
    case False
    have nf: ‹¬ gfinal G Shn (fst (dctrl st))› using False unfolding st dctrl_def by simp
    show ?thesis
    proof
      assume ok: ‹hist_ok G Shn gt sts redtab seen st›
      from False "1"(2) have nk: ‹ckey (dctrl st) ∉ set seen›
        unfolding st by (auto split: if_splits)
      from False nk "1"(2) obtain a st1 where
          step: ‹dstep_act G gt sts redtab st = Some (a, st1)›
        and rec: ‹f G Shn gt sts redtab (if a = DShift then [] else ckey (dctrl st) # seen) st1 = Some t›
        unfolding st by (auto simp: bind_eq_Some_conv)
      from "1"(1)[OF rec] hist_ok_step[OF ok nf step]
      have ‹drunwf G Shn gt sts redtab st1 = Some t› by blast
      with False step show ‹drunwf G Shn gt sts redtab st = Some t›
        unfolding st by (simp add: dstep_eq_dstep_act)
    qed
  qed
qed

lemma drun_imp_drun_hist:
  assumes ‹drun G Shn gt sts redtab n st = Some t› ‹hist_ok G Shn gt sts redtab seen st›
  shows ‹drun_hist G Shn gt sts redtab seen st = Some t›
  using assms
proof (induction n arbitrary: st seen)
  case (0 st seen)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  show ?case using "0.prems"(1) unfolding st
    by (subst drun_hist_simps) (auto split: if_splits list.splits)
next
  case (Suc n st seen)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹gfinal G Shn gc›)
    case True
    with Suc.prems(1) show ?thesis unfolding st
      by (subst drun_hist_simps) (auto split: list.splits)
  next
    case False
    with Suc.prems(1) obtain st1 where sp: ‹dstep G gt sts redtab st = Some st1›
      and rec: ‹drun G Shn gt sts redtab n st1 = Some t›
      unfolding st by (auto split: option.splits)
    from sp obtain a where step: ‹dstep_act G gt sts redtab st = Some (a, st1)›
      unfolding dstep_eq_dstep_act by (cases ‹dstep_act G gt sts redtab st›) auto
    have nf: ‹¬ gfinal G Shn (fst (dctrl st))› using False unfolding st dctrl_def by simp
    have nk: ‹ckey (dctrl st) ∉ set seen›
    proof
      assume ‹ckey (dctrl st) ∈ set seen›
      from hist_ok_seen_cycle[OF Suc.prems(2) this] drun_imp_drunwf[OF Suc.prems(1)]
      show False by simp
    qed
    from Suc.IH[OF rec hist_ok_step[OF Suc.prems(2) nf step]]
    have ih: ‹drun_hist G Shn gt sts redtab (if a = DShift then [] else ckey (dctrl st) # seen) st1
        = Some t› .
    show ?thesis using False nk step ih unfolding st
      by (subst drun_hist_simps) simp
  qed
qed

theorem drunwf_eq_drun_hist:
  assumes ‹hist_ok G Shn gt sts redtab seen st›
  shows ‹drunwf G Shn gt sts redtab st = drun_hist G Shn gt sts redtab seen st›
proof (cases ‹drun_hist G Shn gt sts redtab seen st›)
  case None
  show ?thesis
  proof (cases ‹drunwf G Shn gt sts redtab st›)
    case (Some t)
    from drunwf_imp_drun_ex[OF Some] obtain n where ‹drun G Shn gt sts redtab n st = Some t› ..
    from drun_imp_drun_hist[OF this assms] None show ?thesis by simp
  qed (simp only: None)
next
  case (Some t)
  from drun_hist_imp_drunwf[OF Some] assms show ?thesis using Some by simp
qed

theorem drunwf_code [code]:
  ‹drunwf G Shn gt sts redtab st = drun_hist G Shn gt sts redtab [] st›
  by (rule drunwf_eq_drun_hist) simp

subsection ‹The driver without a history›

text ‹The history costs a whole-stack comparison against every configuration
  since the last shift, which makes a reduce cascade of length ‹n› cost
  ‹O(n3)› (a right-recursive list closing).  A run can only revisit a
  configuration without shifting when the grammar has a derivation
  ‹A ⇒+ A› that consumes nothing: the reduces of such a cycle never pop
  below some depth, and between two reduces that reach it they turn the
  nonterminal on top of that depth into another one over symbols built from
  nothing.  For a grammar without such a derivation the text‹parser›
  command uses text‹drun_nh›, the unfolding of const‹drunwf› under
  its own name, so that it can carry the unfolding as its code equation.
  It equals const‹drunwf› for every grammar; only the termination of
  the generated code depends on the grammar check, and that check is not
  proved.  Termination on inputs outside the language is also left open for
  the validated LR(1) parsers of Jourdan, Pottier and Leroy
  cite‹‹Sect.~7› in "jourdan2012-validating-lr1"› and for Barthwal's SLR
  parser cite‹‹Sect.~7.1› in "barthwal2010-thesis-cfl-hol4"›.›

partial_function (option) drun_nh ::
  ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ ('m, 'ch, 'n, 't) ast option›
  where
  ‹drun_nh G Shn gt sts redtab st =
     (case st of (gc, cstk, istk, v, tstk) ⇒
        if gfinal G Shn gc then (case tstk of t # _ ⇒ Some t | [] ⇒ None)
        else Option.bind (dstep G gt sts redtab st) (drun_nh G Shn gt sts redtab))›

lemmas drun_nh_simps [code] = drun_nh.simps

lemma drun_nh_imp_drunwf:
  assumes ‹drun_nh G Shn gt sts redtab st = Some t›
  shows ‹drunwf G Shn gt sts redtab st = Some t›
proof (rule drun_nh.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab st t)
  obtain gc cstk istk v tstk where st: ‹st = (gc, cstk, istk, v, tstk)› by (cases st)
  show ?case
  proof (cases ‹gfinal G Shn gc›)
    case True
    with "1"(2) show ?thesis unfolding st by (simp split: list.splits)
  next
    case False
    with "1"(2) obtain st1 where sp: ‹dstep G gt sts redtab st = Some st1›
      and rec: ‹f G Shn gt sts redtab st1 = Some t›
      unfolding st by (auto simp: bind_eq_Some_conv)
    ― ‹one unfolding: with text‹drunwf_simps› the simplifier keeps going›
    have ‹drunwf G Shn gt sts redtab st = drunwf G Shn gt sts redtab st1›
      using False sp unfolding st by (subst drunwf.simps) (simp del: drunwf_simps)
    from this "1"(1)[OF rec] show ?thesis by (rule trans)
  qed
qed

lemma drunwf_imp_drun_nh:
  assumes ‹drunwf G Shn gt sts redtab st = Some t›
  shows ‹drun_nh G Shn gt sts redtab st = Some t›
proof (rule drunwf.raw_induct[OF _ assms], goal_cases)
  case (1 f G Shn gt sts redtab st t)
  then show ?case by (subst drun_nh.simps, cases st) (auto simp: bind_eq_Some_conv split: if_splits)
qed

theorem drunwf_eq_drun_nh:
  ‹drunwf G Shn gt sts redtab st = drun_nh G Shn gt sts redtab st›
  by (metis drun_nh_imp_drunwf drunwf_imp_drun_nh not_Some_eq)

text ‹text‹dparse_via_tables› over text‹drun_nh›.›

lemma dparse_via_tables_nh:
  assumes st:  ‹pr0_states G Shn = sts›
    and   gt:  ‹pgtab G sts = gtab›
    and   rt:  ‹red_buckets G Shn (length sts) = redtab›
    and   xi:  ‹xinit G Shn = xin›
    and   xc:  ‹xclosure_auto G xin = xclos›
    and   i0:  ‹st_find sts (lr0_start G Shn) = i0›
  shows ‹dparse G Shn w =
     drun_nh G Shn gtab sts redtab (([xin], tcols w), [xclos], [i0], w, [])›
  by (subst dparse_via_tables[OF st gt rt xi xc i0]) (rule drunwf_eq_drun_nh)

lemma dparse_imp_dparsen_ex:
  assumes ‹dparse G Shn w = Some t›
  shows ‹∃fuel. dparsen G Shn fuel w = Some t›
  using assms drunwf_imp_drun_ex
  by (fastforce simp: dparse_def dparsen_def Let_def)

theorem dparse_sound_ast:
  assumes fn: ‹fresh_name G Shn› and rec: ‹dparse G Shn w = Some t›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
  using dparse_imp_dparsen_ex[OF rec] dparsen_sound_ast[OF fn] by blast

theorem dparse_sound:
  assumes ‹fresh_name G Shn› and ‹dparse G Shn w = Some t›
  shows ‹w ∈ ilang G›
  using dparse_sound_ast[OF assms] by (auto simp: ilang_iff_ast)

section ‹Completeness›

subsection ‹Traces of parse trees›

text ‹The action trace of a wellformed parse tree: a leaf shifts, a node runs
  its children and reduces by its production.  This is the depth-first
  traversal in the proof idea of the completeness theorem of Jourdan, Pottier
  and Leroy cite‹‹Sect.~3.3, Thm.~3› in "jourdan2012-validating-lr1"›, where
  a shift visits a leaf and a reduce visits a node.›

inductive mtrace :: ‹('n, 't) is_cfg ⇒ ('m, 'ch, 'n, 't) ptree ⇒ ('n, 't) dact list ⇒ bool›
  for G where
  mt_leaf: ‹mtrace G (PLeaf t) [DShift]›
| mt_node: ‹(A, rhs) ∈ set (iprods G) ⟹
    list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
      irel_sat (snd Xr) (snd (proot pt)) i) rhs pts ⟹
    list_all2 (mtrace G) pts trs ⟹
    mtrace G (PNode A i pts) (concat trs @ [DReduce (A, rhs)])›

lemma mtrace_ex_list:
  ‹∀pt ∈ set pts. ∃tr. mtrace G pt tr ⟹ ∃trs. list_all2 (mtrace G) pts trs›
proof (induction pts)
  case Nil
  show ?case by (auto intro: exI[of _ ‹[]›])
next
  case (Cons pt pts')
  from Cons.prems obtain tr where tr: ‹mtrace G pt tr› by auto
  from Cons.prems Cons.IH obtain trs where trs: ‹list_all2 (mtrace G) pts' trs› by auto
  from tr trs show ?case by (auto intro: exI[of _ ‹tr # trs›])
qed

lemma mtrace_ex: ‹wf_ptree G pt ⟹ ∃acts. mtrace G pt acts›
proof (induction pt)
  case (PLeaf t)
  show ?case by (intro exI[of _ ‹[DShift]›]) (rule mt_leaf)
next
  case (PNode A i pts)
  from PNode.prems obtain rhs where
    prod: ‹(A, rhs) ∈ set (iprods G)› and
    all2: ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
      irel_sat (snd Xr) (snd (proot pt)) i ∧ wf_ptree G pt) rhs pts›
    by (auto elim: wf_ptree.cases)
  from all2 have ‹∀pt ∈ set pts. wf_ptree G pt›
    by (auto simp: list_all2_conv_all_nth set_conv_nth)
  with PNode.IH have ‹∀pt ∈ set pts. ∃tr. mtrace G pt tr› by auto
  from mtrace_ex_list[OF this] obtain trs where trs: ‹list_all2 (mtrace G) pts trs› by blast
  from all2 have all2': ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
      irel_sat (snd Xr) (snd (proot pt)) i) rhs pts›
    by (auto elim!: list_all2_mono)
  from mt_node[OF prod all2' trs] show ?case ..
qed

lemma mtrace_node_last:
  assumes ‹mtrace G (PNode A i pts) acts›
  obtains rhs trs where ‹acts = concat trs @ [DReduce (A, rhs)]›
    and ‹(A, rhs) ∈ set (iprods G)›
    and ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧ irel_sat (snd Xr) (snd (proot pt)) i) rhs pts›
    and ‹list_all2 (mtrace G) pts trs›
  using assms by (cases rule: mtrace.cases) auto

subsection ‹Closure slots carry the relational images›

lemma xclosure_auto_kernel_sub: ‹set xs ⊆ set (xclosure_auto G xs)›
  unfolding xclosure_auto_def xclosure_def xslots_def by simp

lemma xclosure_auto_slot:
  assumes mem: ‹((pr, m, R)) ∈ set (xclosure_auto G xs)›
    and m_lt: ‹m < length (snd pr)›
    and nxt: ‹fst (snd pr ! m) = Nt B›
    and brhs: ‹(B, brhs) ∈ set (iprods G)›
    and j: ‹j ∈ irep_set R›
    and sat: ‹irel_sat (snd (snd pr ! m)) j' j›
  shows ‹∃R'. (((B, brhs), 0, R')) ∈ set (xclosure_auto G xs) ∧ j' ∈ irep_set R'›
proof -
  let ?cls = ‹xiter G xs (xfuel G xs)›
  have stable: ‹xstable G xs ?cls› by (rule xfuel_stable)
  obtain p where p: ‹p < length (iprods G)› and ip: ‹iprods G ! p = (B, brhs)›
    using brhs by (metis in_set_conv_nth)
  have len: ‹length ?cls = length (iprods G)› by simp
  have mem': ‹((pr, m, R)) ∈ set (xslots G xs ?cls)›
    using mem unfolding xclosure_auto_def xclosure_def .
  obtain A rhs where pr: ‹pr = (A, rhs)› by (cases pr)
  have img: ‹j' ∈ ximg (iprods G ! p) (pr, m, R)›
    unfolding ip pr using m_lt nxt j sat pr by auto
  have ‹xround G xs ?cls ! p = fold (xcontrib (iprods G ! p)) (xslots G xs ?cls) (?cls ! p)›
    by (rule xround_nth[OF len p])
  then have ‹j' ∈ irep_set (xround G xs ?cls ! p)›
    using fold_xcontrib_set[of ‹iprods G ! p› ‹xslots G xs ?cls› ‹?cls ! p›] img mem' by auto
  then have j'_slot: ‹j' ∈ irep_set (?cls ! p)›
    using xstableD[OF stable len p] by blast
  have ‹(iprods G ! p, 0, ?cls ! p) ∈ set (xslots G xs ?cls)›
    by (rule xslots_slot[OF p]) (simp add: len p)
  then show ?thesis
    using j'_slot ip unfolding xclosure_auto_def xclosure_def by auto
qed

subsection ‹The runtime tables are the precise ones›

text ‹The driver indexes its frames by const‹pr0_states›, the automaton of
  the reachable closure const‹creach›.  A frame's closure
  const‹xclosure_auto› has a slot for every production, but only its live
  slots (a non-empty anchor set) matter to the driver, and
  ‹xclosure_auto_live_creach› places every live slot in const‹creach› of
  any state covering the frame's live kernel items.  So a precise state covers
  each frame's live core, and the goto table resolves every live symbol after a
  dot.›

lemma cell_buckets_red_buckets: ‹cell_buckets (la_fix G Shn) n = red_buckets G Shn n›
  by (simp add: red_buckets_def)

subsection ‹The table contract›

text ‹What the completeness proof needs from the three tables: the start
  state is present, the state list is closed under goto through the reachable
  closure const‹creach›, the goto table resolves every symbol after a dot
  of a reachable item, and the cell table contains the start cell and is
  closed under const‹la_cell›.

  The first three play the part of conditions 2 and 4--6 of the completeness
  validator of Jourdan, Pottier and Leroy
  cite‹‹Sect.~3.3› in "jourdan2012-validating-lr1"›: the start items are in
  the initial state, item sets are closed, and the successor under a symbol
  holds the items with the dot moved past it.  The correspondence is loose.
  Their states carry LR(1) items and a goto entry may be undefined; here the
  states are LR(0) cores, the goto table must resolve every symbol after a
  reachable dot, and lookahead lives in the cell table.  The contract is not
  checked by a validator: ‹tables_ok_concrete› proves it for the tables the
  driver uses.›

definition tables_ok :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) lacell list ⇒ bool› where
  ‹tables_ok G Shn sts gt L ⟷
     (∃t ∈ set sts. set t = set (lr0_start G Shn)) ∧
     (∀s ∈ set sts. ∀X ∈ set (gram_syms G). ∃t ∈ set sts. set t = set (cgoto (creach G s) X)) ∧
     (∀s ∈ set sts. set s ⊆ cuniv G Shn) ∧
     length gt = length sts ∧
     (∀i < length sts. ∀pr m. (pr, m) ∈ set (creach G (sts ! i)) ⟶ m < length (snd pr) ⟶
         map_of (gt ! i) (fst (snd pr ! m)) =
           Some (st_find sts (cgoto (creach G (sts ! i)) (fst (snd pr ! m))))) ∧
     set (la_start G Shn sts) ⊆ set L ∧
     set (la_step G (ffix G) (nullables G) gt sts L) = set L›

theorem tables_ok_concrete:
  ‹tables_ok G Shn (pr0_states G Shn) (pgtab G (pr0_states G Shn)) (la_fix G Shn)›
  unfolding tables_ok_def
proof (intro conjI)
  show ‹∃t ∈ set (pr0_states G Shn). set t = set (lr0_start G Shn)›
    using pr0_states_start[of G Shn]
    by (auto simp: ccore_def xinit_def lr0_start_def start_prod_def)
  show ‹∀s ∈ set (pr0_states G Shn). ∀X ∈ set (gram_syms G).
      ∃t ∈ set (pr0_states G Shn). set t = set (cgoto (creach G s) X)›
    by (intro ballI pr0_states_closed)
  show ‹∀s ∈ set (pr0_states G Shn). set s ⊆ cuniv G Shn›
    by (intro ballI pr0_states_univ)
  show ‹length (pgtab G (pr0_states G Shn)) = length (pr0_states G Shn)› by simp
  show ‹∀i < length (pr0_states G Shn). ∀pr m.
      (pr, m) ∈ set (creach G (pr0_states G Shn ! i)) ⟶ m < length (snd pr) ⟶
      map_of (pgtab G (pr0_states G Shn) ! i) (fst (snd pr ! m)) =
        Some (st_find (pr0_states G Shn)
                (cgoto (creach G (pr0_states G Shn ! i)) (fst (snd pr ! m))))›
    by (intro allI impI pgtab_lookup)
  show ‹set (la_start G Shn (pr0_states G Shn)) ⊆ set (la_fix G Shn)›
    by (rule la_fix_start)
  show ‹set (la_step G (ffix G) (nullables G) (pgtab G (pr0_states G Shn))
        (pr0_states G Shn) (la_fix G Shn)) = set (la_fix G Shn)›
    using la_fix_stable[of G Shn] by simp
qed

text ‹A symbol after a dot of a frame-closure item of a tabulated state is
  resolved by the goto table to a tabulated state.›

lemma dnext_resolve:
  assumes tab: ‹tables_ok G Shn sts gt L› and i_lt: ‹i < length sts›
    and mem: ‹(pr, m) ∈ set (creach G (sts ! i))› and m_lt: ‹m < length (snd pr)›
  shows ‹dnext gt sts i (fst (snd pr ! m)) < length sts›
    and ‹set (sts ! dnext gt sts i (fst (snd pr ! m))) =
      set (cgoto (creach G (sts ! i)) (fst (snd pr ! m)))›
    and ‹dnext gt sts i (fst (snd pr ! m)) = la_next gt sts i (fst (snd pr ! m))›
proof -
  let ?X = ‹fst (snd pr ! m)›
  have s_in: ‹sts ! i ∈ set sts› using i_lt by simp
  have univ: ‹set (sts ! i) ⊆ cuniv G Shn› using tab s_in unfolding tables_ok_def by blast
  have ‹(pr, m) ∈ cuniv G Shn› using creach_univ[OF univ] mem by blast
  from cuniv_next_gram_syms[OF this m_lt] have X_sym: ‹?X ∈ set (gram_syms G)› .
  obtain t where ‹t ∈ set sts› and ‹set t = set (cgoto (creach G (sts ! i)) ?X)›
    using tab s_in X_sym unfolding tables_ok_def by blast
  from st_find_found[OF this]
  have sf_lt: ‹st_find sts (cgoto (creach G (sts ! i)) ?X) < length sts›
    and sf_set: ‹set (sts ! st_find sts (cgoto (creach G (sts ! i)) ?X)) =
      set (cgoto (creach G (sts ! i)) ?X)›
    by auto
  have lookup: ‹map_of (gt ! i) ?X = Some (st_find sts (cgoto (creach G (sts ! i)) ?X))›
    using tab i_lt mem m_lt unfolding tables_ok_def by blast
  have len_gt: ‹length gt = length sts› using tab unfolding tables_ok_def by blast
  have la: ‹la_next gt sts i ?X = st_find sts (cgoto (creach G (sts ! i)) ?X)›
    unfolding la_next_def lookup using sf_lt by simp
  have dn: ‹dnext gt sts i ?X = la_next gt sts i ?X›
    unfolding dnext_def using i_lt len_gt by simp
  show ‹dnext gt sts i ?X < length sts› using dn la sf_lt by simp
  show ‹set (sts ! dnext gt sts i ?X) = set (cgoto (creach G (sts ! i)) ?X)›
    using dn la sf_set by simp
  show ‹dnext gt sts i ?X = la_next gt sts i ?X› by (rule dn)
qed

subsection ‹Cell-table closure, by rule›

lemma la_cell_goto_mem:
  ‹m < length (snd pr) ⟹
   (la_next gt sts i (fst (snd pr ! m)), (pr, Suc m), t, τ) ∈ set (la_cell G ft ns gt sts (i, (pr, m), t, τ))›
  by simp

lemma la_cell_first_mem:
  assumes ‹m < length (snd pr)› and ‹fst (snd pr ! m) = Nt B› and ‹br ∈ set (iprods G)› and ‹fst br = B›
    and ‹(a, σ) ∈ set (fscan ft ns (drop (Suc m) (snd pr)))›
  shows ‹(i, (br, 0), Some a, wcomp (winv (w_of (snd (snd pr ! m)))) (wemb σ))
           ∈ set (la_cell G ft ns gt sts (i, (pr, m), t, τ))›
  using assms by (force simp: Let_def)

lemma la_cell_inherit_mem:
  assumes ‹m < length (snd pr)› and ‹fst (snd pr ! m) = Nt B› and ‹br ∈ set (iprods G)› and ‹fst br = B›
    and ‹list_all (λ(X, r). nsym ns X) (drop (Suc m) (snd pr))›
  shows ‹(i, (br, 0), t, wcomp (winv (w_of (snd (snd pr ! m)))) τ)
           ∈ set (la_cell G ft ns gt sts (i, (pr, m), t, τ))›
  using assms by (force simp: Let_def)

lemma tables_ok_cell:
  assumes ‹tables_ok G Shn sts gt L› and ‹c ∈ set L›
    and ‹x ∈ set (la_cell G (ffix G) (nullables G) gt sts c)›
  shows ‹x ∈ set L›
proof -
  have ‹x ∈ set (la_step G (ffix G) (nullables G) gt sts L)›
    unfolding la_step_def using assms(2,3) by auto
  then show ?thesis using assms(1) unfolding tables_ok_def by blast
qed

subsection ‹The driver's index stack tracks the frames›

text ‹A non-empty set-valued goto witnesses a dotted occurrence of the goto
  symbol in the source frame's core, as text‹dnext_resolve› needs.
  const‹dpick› only commits to const‹dlive› successors, and
  const‹dlive› forces the new frame non-empty, so every driver step supplies
  that witness.›

definition didx_ok :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒
    ('n, 't) xitem list list ⇒ nat list ⇒ bool› where
  ‹didx_ok G sts Xs istk ⟷ length istk = length Xs ∧
     (∀k < length Xs. lcore (Xs ! k) ≠ {} ⟶
        istk ! k < length sts ∧ lcore (Xs ! k) ⊆ set (sts ! (istk ! k)))›

lemma didx_okD:
  ‹didx_ok G sts Xs istk ⟹ k < length Xs ⟹ lcore (Xs ! k) ≠ {} ⟹
     istk ! k < length sts ∧ lcore (Xs ! k) ⊆ set (sts ! (istk ! k))›
  unfolding didx_ok_def by blast

lemma didx_ok_len: ‹didx_ok G sts Xs istk ⟹ length istk = length Xs›
  unfolding didx_ok_def by blast

lemma didx_ok_init:
  assumes tab: ‹tables_ok G Shn sts gt L›
  shows ‹didx_ok G sts [xinit G Shn] [st_find sts (lr0_start G Shn)]›
proof -
  obtain t where t: ‹t ∈ set sts› and te: ‹set t = set (lr0_start G Shn)›
    using tab unfolding tables_ok_def by blast
  from st_find_found[OF t te] have lt: ‹st_find sts (lr0_start G Shn) < length sts›
    and eq: ‹set (sts ! st_find sts (lr0_start G Shn)) = set (lr0_start G Shn)› by auto
  show ?thesis unfolding didx_ok_def using lt eq by (simp add: lcore_xinit)
qed

text ‹The step case: a live item of the goto frame comes from a live item of
  the source closure, which lies in const‹creach› of the tracked state, so
  the lookup resolves and the target state covers the goto frame's live core.›

lemma didx_ok_push:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and ok: ‹didx_ok G sts Xs istk›
    and d_lt: ‹d < length Xs›
  shows ‹didx_ok G sts (lgoto (xclosure_auto G (Xs ! d)) X RA # drop d Xs)
           (dnext gt sts (istk ! d) X # drop d istk)›
proof -
  let ?F = ‹lgoto (xclosure_auto G (Xs ! d)) X RA›
  let ?j = ‹dnext gt sts (istk ! d) X›
  have len: ‹length istk = length Xs› by (rule didx_ok_len[OF ok])
  have top: ‹?j < length sts ∧ lcore ?F ⊆ set (sts ! ?j)› if live': ‹lcore ?F ≠ {}›
  proof -
    from live' obtain pr0 n0 R0' j0 where
      g0: ‹(pr0, n0, R0') ∈ set ?F› and j0: ‹j0 ∈ irep_set R0'›
      unfolding lcore_def by auto
    obtain m0 where n0: ‹n0 = Suc m0› using lgoto_dot_pos[OF g0] by (cases n0) auto
    from lgoto_kernel_step[OF g0[unfolded n0]] obtain R0 where
      src0: ‹(pr0, m0, R0) ∈ set (xclosure_auto G (Xs ! d))›
      and m0_lt: ‹m0 < length (snd pr0)› and X0: ‹fst (snd pr0 ! m0) = X›
      and R0': ‹R0' = irep_inter R0 (irep_pre (snd (snd pr0 ! m0)) RA)› .
    have j0R0: ‹j0 ∈ irep_set R0› using j0 unfolding R0' by auto
    have f_live: ‹lcore (Xs ! d) ≠ {}› by (rule closure_live_kernel[OF src0 j0R0])
    from didx_okD[OF ok d_lt f_live] have p_lt: ‹istk ! d < length sts›
      and cover: ‹lcore (Xs ! d) ⊆ set (sts ! (istk ! d))› by auto
    have kern: ‹⋀pr m R. (pr, m, R) ∈ set (Xs ! d) ⟹ irep_nonempty R ⟹
        (pr, m) ∈ set (sts ! (istk ! d))›
      using cover by (fastforce simp: lcore_def)
    have src0_cr: ‹(pr0, m0) ∈ set (creach G (sts ! (istk ! d)))›
      by (rule xclosure_auto_live_creach[OF kern src0 j0R0])
    have j_lt: ‹?j < length sts›
      and j_set: ‹set (sts ! ?j) = set (cgoto (creach G (sts ! (istk ! d))) X)›
      using dnext_resolve[OF tab p_lt src0_cr m0_lt] X0 by auto
    have cov': ‹lcore ?F ⊆ set (sts ! ?j)›
    proof
      fix c assume ‹c ∈ lcore ?F›
      then obtain pr2 n2 R2' where ceq: ‹c = (pr2, n2)›
        and g2: ‹(pr2, n2, R2') ∈ set ?F› and ne2: ‹irep_nonempty R2'›
        unfolding lcore_def by blast
      obtain j2 where j2: ‹j2 ∈ irep_set R2'› using ne2 by auto
      obtain m2 where n2: ‹n2 = Suc m2› using lgoto_dot_pos[OF g2] by (cases n2) auto
      from lgoto_kernel_step[OF g2[unfolded n2]] obtain R2 where
        src2: ‹(pr2, m2, R2) ∈ set (xclosure_auto G (Xs ! d))›
        and m2_lt: ‹m2 < length (snd pr2)› and X2: ‹fst (snd pr2 ! m2) = X›
        and R2': ‹R2' = irep_inter R2 (irep_pre (snd (snd pr2 ! m2)) RA)› .
      have j2R2: ‹j2 ∈ irep_set R2› using j2 unfolding R2' by auto
      have ‹(pr2, m2) ∈ set (creach G (sts ! (istk ! d)))›
        by (rule xclosure_auto_live_creach[OF kern src2 j2R2])
      from cgoto_memI[OF this m2_lt X2] show ‹c ∈ set (sts ! ?j)›
        unfolding ceq n2 j_set by simp
    qed
    show ?thesis using j_lt cov' by blast
  qed
  show ?thesis
    unfolding didx_ok_def
  proof (rule conjI)
    show ‹length (?j # drop d istk) = length (?F # drop d Xs)› using len by simp
  next
    show ‹∀k < length (?F # drop d Xs). lcore ((?F # drop d Xs) ! k) ≠ {} ⟶
        (?j # drop d istk) ! k < length sts ∧
        lcore ((?F # drop d Xs) ! k) ⊆ set (sts ! ((?j # drop d istk) ! k))›
    proof (intro allI impI)
      fix k assume k_lt: ‹k < length (?F # drop d Xs)›
        and lv: ‹lcore ((?F # drop d Xs) ! k) ≠ {}›
      show ‹(?j # drop d istk) ! k < length sts ∧
          lcore ((?F # drop d Xs) ! k) ⊆ set (sts ! ((?j # drop d istk) ! k))›
      proof (cases k)
        case 0
        show ?thesis unfolding 0 using top lv[unfolded 0] by simp
      next
        case (Suc k0)
        have k0: ‹d + k0 < length Xs› using k_lt Suc d_lt by simp
        have i1: ‹(?j # drop d istk) ! Suc k0 = istk ! (d + k0)› using k0 len by simp
        have i2: ‹(?F # drop d Xs) ! Suc k0 = Xs ! (d + k0)› using k0 by simp
        show ?thesis unfolding Suc i1 i2 using didx_okD[OF ok k0] lv Suc i2 by simp
      qed
    qed
  qed
qed

text ‹A live closure item of the top frame lies in the reachable closure of the
  tracked state, and that state is in range.›

lemma didx_ok_creach:
  assumes ok: ‹didx_ok G sts Xs istk› and ne: ‹Xs ≠ []›
    and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (hd Xs))› and jR: ‹j ∈ irep_set R›
  shows ‹hd istk < length sts› and ‹(pr, m) ∈ set (creach G (sts ! hd istk))›
proof -
  have istk_ne: ‹istk ≠ []› using ok ne by (auto dest: didx_ok_len)
  have hd: ‹istk ! 0 = hd istk› ‹Xs ! 0 = hd Xs›
    using istk_ne ne by (simp_all add: hd_conv_nth)
  have live: ‹lcore (hd Xs) ≠ {}› by (rule closure_live_kernel[OF mem jR])
  from didx_okD[OF ok, of 0] ne live hd have lt: ‹hd istk < length sts›
    and cover: ‹lcore (hd Xs) ⊆ set (sts ! hd istk)› by auto
  show ‹hd istk < length sts› by (rule lt)
  have kern: ‹⋀pr' m' R'. (pr', m', R') ∈ set (hd Xs) ⟹ irep_nonempty R' ⟹
      (pr', m') ∈ set (sts ! hd istk)›
    using cover by (fastforce simp: lcore_def)
  show ‹(pr, m) ∈ set (creach G (sts ! hd istk))›
    by (rule xclosure_auto_live_creach[OF kern mem jR])
qed

lemma dlive_lcore: ‹dlive (X # Xs, w) ⟷ lcore X ≠ {}›
  unfolding dlive_def by (simp add: live_lcore)

lemma didx_ok_hd_lt:
  assumes ok: ‹didx_ok G sts Xs istk› and lv: ‹dlive (Xs, w)›
  shows ‹hd istk < length sts›
proof -
  have ne: ‹Xs ≠ []› and live: ‹lcore (Xs ! 0) ≠ {}›
    using lv unfolding dlive_def live_lcore by (auto simp: hd_conv_nth)
  have istk_ne: ‹istk ≠ []› using ok ne by (auto dest: didx_ok_len)
  show ?thesis using didx_okD[OF ok _ live] ne istk_ne by (simp add: hd_conv_nth)
qed

subsection ‹Cell propagation: down to an item's children›

text ‹A cell for an item with term‹Nt B› after the dot gives every
  production of term‹B› a dot-0 cell in the same state, re-anchored through
  the occurrence's relation: with the FIRST token of the remaining right-hand
  side, or, when that remainder is nullable, with the parent's own token
  inherited.›

lemma cell_child_first:
  assumes tab: ‹tables_ok G Shn sts gt L› and cell: ‹(i, (pr, m), t, τ) ∈ set L›
    and m_lt: ‹m < length (snd pr)› and nxt: ‹fst (snd pr ! m) = Nt B›
    and br: ‹br ∈ set (iprods G)› and brB: ‹fst br = B›
    and fs: ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) (drop (Suc m) (snd pr)))›
  shows ‹(i, (br, 0), Some a, wcomp (winv (w_of (snd (snd pr ! m)))) (wemb σ)) ∈ set L›
  by (rule tables_ok_cell[OF tab cell la_cell_first_mem[OF m_lt nxt br brB fs]])

lemma cell_child_inherit:
  assumes tab: ‹tables_ok G Shn sts gt L› and cell: ‹(i, (pr, m), t, τ) ∈ set L›
    and m_lt: ‹m < length (snd pr)› and nxt: ‹fst (snd pr ! m) = Nt B›
    and br: ‹br ∈ set (iprods G)› and brB: ‹fst br = B›
    and nul: ‹list_all (λ(X, r). nsym (nullables G) X) (drop (Suc m) (snd pr))›
  shows ‹(i, (br, 0), t, wcomp (winv (w_of (snd (snd pr ! m)))) τ) ∈ set L›
  by (rule tables_ok_cell[OF tab cell la_cell_inherit_mem[OF m_lt nxt br brB nul]])

text ‹The relation side of both: composing the occurrence's inverse relation
  with the child-side relation lands the token's column against the child's
  anchor. This packages text‹wcomp_sound›, text‹winv_sound› and
  text‹w_of_sound›.›

lemma wsat_reanchor:
  assumes sat: ‹irel_sat r jc j› and tj: ‹wsat τ c j›
  shows ‹wsat (wcomp (winv (w_of r)) τ) c jc›
  by (rule wcomp_sound[OF tj winv_sound[OF w_of_sound[OF sat]]])

subsection ‹The index-carrying machine›

type_synonym ('n, 't) icfg = ‹('n, 't) gconfig × nat list›

definition imstep :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) icfg ⇒ ('n, 't) dact ⇒ ('n, 't) icfg option› where
  ‹imstep G gt sts ic act = (case ic of ((Xs, w), istk) ⇒
     (case mstep G (Xs, w) act of None ⇒ None
      | Some gc' ⇒ Some (gc', (case act of
          DShift ⇒ dnext gt sts (hd istk) (Tm (fst (hd w))) # istk
        | DReduce pr ⇒ dnext gt sts (istk ! length (snd pr)) (Nt (fst pr))
                         # drop (length (snd pr)) istk))))›

fun imrun :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) dact list ⇒ ('n, 't) icfg ⇒ ('n, 't) icfg option› where
  ‹imrun G gt sts [] ic = Some ic›
| ‹imrun G gt sts (act # acts) ic =
     (case imstep G gt sts ic act of None ⇒ None | Some ic' ⇒ imrun G gt sts acts ic')›

lemma imrun_append:
  ‹imrun G gt sts (as @ bs) ic =
     (case imrun G gt sts as ic of None ⇒ None | Some ic' ⇒ imrun G gt sts bs ic')›
  by (induction as arbitrary: ic) (auto split: option.splits)

lemma imstep_mstep: ‹imstep G gt sts ic act = Some ic' ⟹ mstep G (fst ic) act = Some (fst ic')›
  unfolding imstep_def by (auto split: prod.splits option.splits)

lemma imrun_mrun: ‹imrun G gt sts as ic = Some ic' ⟹ mrun G as (fst ic) = Some (fst ic')›
  by (induction as arbitrary: ic) (auto split: option.splits dest: imstep_mstep)

subsection ‹Reachability of the index-carrying machine›

text ‹The configurations the driver can be in: from the initial frame and the
  start state, by steps whose successor is const‹dlive›.  The determinism
  hypothesis below is stated over these, since the index of a frame is the one
  the driver built, not a function of the frame.›

inductive imreach :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) icfg ⇒ bool› for G Shn gt sts where
  imreach_init: ‹imreach G Shn gt sts (([xinit G Shn], w), [st_find sts (lr0_start G Shn)])›
| imreach_step: ‹imreach G Shn gt sts ic ⟹ imstep G gt sts ic act = Some ic' ⟹
    dlive (fst ic') ⟹ imreach G Shn gt sts ic'›

lemma imreach_dlive: ‹imreach G Shn gt sts ic ⟹ dlive (fst ic)›
  by (induction rule: imreach.induct)
     (auto simp: dlive_lcore lcore_xinit lr0_start_def)

text ‹The index invariant along the machine: each step pushes through
  const‹dnext› from a frame the stack tracks.›

lemma imstep_didx_ok:
  assumes tab: ‹tables_ok G Shn sts gt L› and ok: ‹didx_ok G sts Xs istk›
    and step: ‹imstep G gt sts ((Xs, w), istk) act = Some ((Xs', w'), istk')›
  shows ‹didx_ok G sts Xs' istk'›
proof (cases act)
  case DShift
  have ms: ‹mstep G (Xs, w) DShift = Some (Xs', w')›
    using imstep_mstep[OF step] DShift by simp
  from mstep_shift_shape[OF ms[unfolded mstep_def, simplified]]
  obtain a c w'' where w: ‹w = (a, c) # w''› and ne: ‹Xs ≠ []›
    and Xs': ‹(Xs', w') = (lgoto (hd (map (xclosure_auto G) Xs)) (Tm a) (FinRep [c]) # Xs, w'')›
    using ms unfolding mstep_def by (metis prod.inject)
  have istk': ‹istk' = dnext gt sts (hd istk) (Tm a) # istk›
    using step[unfolded imstep_def DShift w] ms[unfolded w] by simp
  have istk_ne: ‹istk ≠ []› using ne didx_ok_len[OF ok] by auto
  have hd0: ‹Xs ! 0 = hd Xs› and i0: ‹istk ! 0 = hd istk›
    using ne istk_ne by (simp_all add: hd_conv_nth)
  have ‹didx_ok G sts (lgoto (xclosure_auto G (Xs ! 0)) (Tm a) (FinRep [c]) # drop 0 Xs)
      (dnext gt sts (istk ! 0) (Tm a) # drop 0 istk)›
    by (rule didx_ok_push[OF tab ok]) (use ne in simp)
  then show ?thesis using Xs' istk' ne hd0 i0 by (simp add: hd_map)
next
  case (DReduce pr)
  let ?k = ‹length (snd pr)›
  have ms: ‹mstep G (Xs, w) (DReduce pr) = Some (Xs', w')›
    using imstep_mstep[OF step] DReduce by simp
  from ms[unfolded mstep_def]
  have k_lt: ‹?k < length Xs›
    and Xs': ‹Xs' = lgoto (map (xclosure_auto G) Xs ! ?k) (Nt (fst pr))
                     (red_set (hd (map (xclosure_auto G) Xs)) pr) # drop ?k Xs›
    unfolding mstep_cached_def by (auto simp: Let_def split: if_splits)
  have istk': ‹istk' = dnext gt sts (istk ! ?k) (Nt (fst pr)) # drop ?k istk›
    using step unfolding imstep_def DReduce by (simp add: ms)
  have nth_map: ‹map (xclosure_auto G) Xs ! ?k = xclosure_auto G (Xs ! ?k)›
    using k_lt by simp
  show ?thesis unfolding Xs' istk' nth_map by (rule didx_ok_push[OF tab ok k_lt])
qed

lemma imreach_didx_ok:
  assumes tab: ‹tables_ok G Shn sts gt L›
  shows ‹imreach G Shn gt sts ic ⟹ didx_ok G sts (fst (fst ic)) (snd ic)›
proof (induction rule: imreach.induct)
  case (imreach_init w)
  show ?case using didx_ok_init[OF tab] by simp
next
  case (imreach_step ic act ic')
  obtain gc istk where ic: ‹ic = (gc, istk)› by (cases ic)
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  obtain gc' istk' where ic': ‹ic' = (gc', istk')› by (cases ic')
  obtain Xs' w' where gc': ‹gc' = (Xs', w')› by (cases gc')
  show ?case
    using imstep_didx_ok[OF tab imreach_step.IH[unfolded ic gc, simplified]
        imreach_step.hyps(2)[unfolded ic gc ic' gc']]
    unfolding ic' gc' by simp
qed

subsection ‹Licensing of the reduces along a run›

definition dlic_L :: ‹nat ⇒ ('n, 't) lacell list ⇒ ('t × nat) list ⇒ 'n × ('n, 't) rhs ⇒ indrep ⇒ bool› where
  ‹dlic_L i L w pr RS ⟷ (∃t τ. (i, (pr, length (snd pr)), t, τ) ∈ set L ∧
       (case w of [] ⇒ t = None | (a, c) # _ ⇒ t = Some a ∧ irep_ex_wsat τ c RS))›

lemma dlic_buckets:
  assumes i_lt: ‹i < n›
  shows ‹dlic i (cell_buckets L n ! i) w pr RS ⟷ dlic_L i L w pr RS›
proof -
  let ?P = ‹λ(i', itm, t, τ). i' = i ∧ itm = (pr, length (snd pr)) ∧
       (case w of [] ⇒ t = None
                | (a, c) # _ ⇒ t = Some a ∧ irep_ex_wsat τ c RS)›
  have nth: ‹cell_buckets L n ! i = filter (λ(i', itm, t, τ). i' = i)
      (filter (λ(i, itm, t, τ). snd itm = length (snd (fst itm))) L)›
    unfolding cell_buckets_def Let_def using i_lt by simp
  have keep: ‹?P c ⟹ (case c of (i', itm, t, τ) ⇒ snd itm = length (snd (fst itm))) ∧
                      (case c of (i', itm, t, τ) ⇒ i' = i)› for c
    by (cases c) auto
  have a: ‹dlic i (cell_buckets L n ! i) w pr RS ⟷ (∃c ∈ set (cell_buckets L n ! i). ?P c)›
    unfolding dlic_def by (simp add: list_ex_iff)
  have b: ‹(∃c ∈ set (cell_buckets L n ! i). ?P c) ⟷ (∃c ∈ set L. ?P c)›
  proof
    assume ‹∃c ∈ set (cell_buckets L n ! i). ?P c›
    then obtain cc where ‹cc ∈ set (cell_buckets L n ! i)› and cp: ‹?P cc› by blast
    then have ‹cc ∈ set L› unfolding nth by simp
    with cp show ‹∃c ∈ set L. ?P c› by blast
  next
    assume ‹∃c ∈ set L. ?P c›
    then obtain cc where cm: ‹cc ∈ set L› and cp: ‹?P cc› by blast
    obtain i' itm t τ where ceq: ‹cc = (i', itm, t, τ)› by (cases cc)
    from cp ceq have e1: ‹i' = i› and e2: ‹itm = (pr, length (snd pr))› by auto
    have ‹cc ∈ set (cell_buckets L n ! i)›
      unfolding nth using cm ceq e1 e2 by simp
    with cp show ‹∃c ∈ set (cell_buckets L n ! i). ?P c› by blast
  qed
  have c: ‹(∃c ∈ set L. ?P c) ⟷ dlic_L i L w pr RS›
  proof
    assume ‹∃c ∈ set L. ?P c›
    then obtain cc where cm: ‹cc ∈ set L› and cp: ‹?P cc› by blast
    obtain i' itm t τ where ceq: ‹cc = (i', itm, t, τ)› by (cases cc)
    from cp ceq have e1: ‹i' = i› and e2: ‹itm = (pr, length (snd pr))›
      and wc: ‹case w of [] ⇒ t = None
                       | (a, cl) # _ ⇒ t = Some a ∧ irep_ex_wsat τ cl RS› by auto
    show ‹dlic_L i L w pr RS›
      unfolding dlic_L_def using cm ceq e1 e2 wc by auto
  next
    assume ‹dlic_L i L w pr RS›
    then obtain t τ where m: ‹(i, (pr, length (snd pr)), t, τ) ∈ set L›
      and wc: ‹case w of [] ⇒ t = None
                       | (a, cl) # _ ⇒ t = Some a ∧ irep_ex_wsat τ cl RS›
      unfolding dlic_L_def by blast
    show ‹∃c ∈ set L. ?P c›
      by (rule bexI[of _ ‹(i, (pr, length (snd pr)), t, τ)›]) (use m wc in auto)
  qed
  show ?thesis using a b c by simp
qed

definition lic_at :: ‹('n, 't) is_cfg ⇒ ('n, 't) lacell list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) icfg ⇒ 'n × ('n, 't) rhs ⇒ bool› where
  ‹lic_at G L sts ic pr ⟷ (case ic of ((Xs, w), istk) ⇒
     hd istk < length sts ∧ dlic_L (hd istk) L w pr (red_set (xclosure_auto G (hd Xs)) pr))›

subsection ‹Nullability of an empty-yield subtree›

text ‹A wellformed parse tree with empty yield has a nullable root symbol (via
  text‹derives_iff_ptree› and text‹nullables_complete›); the
  ``all later siblings are nullable'' case of the licensing argument needs this.›

lemma wf_ptree_nullable_root:
  fixes pts :: ‹('m, 'ch, 'n, 't) ptree list›
  assumes ‹wf_ptree G (PNode A j pts)› and ‹pyield (PNode A j pts) = []›
  shows ‹A ∈ set (nullables G)›
proof -
  have ‹∃pt. wf_ptree G pt ∧ proot pt = (Nt A, j) ∧ pyield pt = ([] :: ('m, 'ch, 't) tword)›
    using assms by (intro exI[of _ ‹PNode A j pts›]) simp
  then have ‹infG G ⊢ [Nt (A, j)] ⇒* map Tm (tcols ([] :: ('m, 'ch, 't) tword))›
    unfolding derives_iff_ptree by blast
  then obtain n where ‹infG G ⊢ [Nt (A, j)] ⇒(n) []›
    by (auto dest!: rtranclp_imp_relpowp)
  from nullables_complete[OF this] show ?thesis .
qed

lemma wf_ptree_nsym_of_empty_yield:
  ‹wf_ptree G pt ⟹ pyield pt = [] ⟹ nsym (nullables G) (fst (proot pt))›
  by (cases pt) (auto simp: nsym_def dest: wf_ptree_nullable_root)

subsection ‹The lookahead of a subtree's continuation›

text ‹text‹cell_ok G L i pr rest j›: state ‹i› has a dot-0 cell for ‹pr›
  whose token is what follows the subtree and whose relation places that
  token's column against the subtree's own anchor ‹j›. This is the context a
  subtree inherits from its parent and what licenses its reduce.›

definition cell_ok :: ‹('n, 't) lacell list ⇒ nat ⇒ 'n × ('n, 't) rhs ⇒ nat ⇒
    ('t × nat) list ⇒ nat ⇒ bool› where
  ‹cell_ok L i pr m rest j ⟷ (∃τ. (i, (pr, m), tok_of rest, τ) ∈ set L ∧
     (case rest of [] ⇒ True | (a, c) # _ ⇒ wsat τ c j))›

lemma cell_ok_dlic:
  assumes ‹cell_ok L i pr (length (snd pr)) rest j› and ‹j ∈ irep_set RS›
  shows ‹dlic_L i L rest pr RS›
  using assms unfolding cell_ok_def dlic_L_def
  by (cases rest) (auto intro!: bexI[of _ j])

text ‹Down to a child: the parent's cell for ‹(pr, m)› gives the child's
  production a dot-0 cell in the same state, with the child's own anchor as
  reference. Case split on whether the material after the child in the parent's
  right-hand side yields a token (FIRST) or is nullable (inherit).›

lemma cell_ok_child:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and cell: ‹cell_ok L i pr m rest j›
    and m_lt: ‹m < length (snd pr)›
    and nxt: ‹fst (snd pr ! m) = Nt B›
    and br: ‹br ∈ set (iprods G)› and brB: ‹fst br = B›
    and sat: ‹irel_sat (snd (snd pr ! m)) jc j›
    and split: ‹restc = suf @ rest›
    and suf_first:
      ‹suf ≠ [] ⟹ ∃σ. (fst (hd suf), σ) ∈ set (fscan (ffix G) (nullables G) (drop (Suc m) (snd pr)))
                       ∧ csat σ (snd (hd suf)) j›
    and suf_null: ‹suf = [] ⟹ list_all (λ(X, r). nsym (nullables G) X) (drop (Suc m) (snd pr))›
  shows ‹cell_ok L i br 0 restc jc›
proof (cases suf)
  case Nil
  from cell obtain τ where mem: ‹(i, (pr, m), tok_of rest, τ) ∈ set L›
    and rel: ‹case rest of [] ⇒ True | (a, c) # _ ⇒ wsat τ c j›
    unfolding cell_ok_def by blast
  from cell_child_inherit[OF tab mem m_lt nxt br brB suf_null[OF Nil]]
  have ‹(i, (br, 0), tok_of rest, wcomp (winv (w_of (snd (snd pr ! m)))) τ) ∈ set L› .
  moreover have ‹case rest of [] ⇒ True
      | (a, c) # _ ⇒ wsat (wcomp (winv (w_of (snd (snd pr ! m)))) τ) c jc›
    using rel wsat_reanchor[OF sat] by (cases rest) auto
  ultimately show ?thesis using split Nil unfolding cell_ok_def by auto
next
  case (Cons x v)
  obtain a c where x: ‹x = (a, c)› by (cases x)
  from cell obtain τ where mem: ‹(i, (pr, m), tok_of rest, τ) ∈ set L›
    unfolding cell_ok_def by blast
  from suf_first[OF _] Cons x obtain σ where
      fs: ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) (drop (Suc m) (snd pr)))›
    and cs: ‹csat σ c j› by auto
  from cell_child_first[OF tab mem m_lt nxt br brB fs]
  have inL: ‹(i, (br, 0), Some a, wcomp (winv (w_of (snd (snd pr ! m)))) (wemb σ)) ∈ set L› .
  have ‹wsat (wcomp (winv (w_of (snd (snd pr ! m)))) (wemb σ)) c jc›
    by (rule wsat_reanchor[OF sat wemb_sound[OF cs]])
  moreover have ‹tok_of restc = Some a› using split Cons x by simp
  ultimately show ?thesis using inL split Cons x unfolding cell_ok_def by auto
qed

subsection ‹What const‹dcands› offers›

text ‹The shift is offered unconditionally while input remains, so the shift
  case of ``the driver follows the trace'' needs no licensing. A reduce is
  offered iff the frame closure completes the production with a non-empty
  anchor set and the cell table licenses it.›

lemma dcands_shift:
  assumes ‹fst gc ≠ []› and ‹snd gc ≠ []›
  shows ‹DShift ∈ set (dcands G i cells CL gc)›
  using assms unfolding dcands_def by (cases gc) (auto simp: Let_def split: list.splits)

lemma dcands_reduceI:
  assumes ne: ‹fst gc ≠ []›
    and comp: ‹(pr, length (snd pr), R) ∈ set CL›
    and RS_ne: ‹irep_nonempty (red_set CL pr)›
    and lic: ‹dlic i cells (snd gc) pr (red_set CL pr)›
  shows ‹DReduce pr ∈ set (dcands G i cells CL gc)›
proof -
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  have ‹pr ∈ set (remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL)))›
    using comp by force
  then have ‹DReduce pr ∈ set (map DReduce (filter (λpr. let RS = red_set CL pr in
                  irep_nonempty RS ∧ dlic i cells w pr RS)
                (remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL)))))›
    using RS_ne lic gc by (simp add: Let_def)
  then show ?thesis
    using ne unfolding dcands_def gc by (cases w) (simp_all add: Let_def)
qed

lemma dcands_reduceD:
  assumes ‹DReduce pr ∈ set (dcands G i cells CL gc)›
  shows ‹(∃R. (pr, length (snd pr), R) ∈ set CL) ∧
         irep_nonempty (red_set CL pr) ∧ dlic i cells (snd gc) pr (red_set CL pr)›
proof -
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  from assms have ne: ‹Xs ≠ []› unfolding dcands_def gc by (auto split: if_splits)
  from assms have
    ‹pr ∈ set (filter (λpr. let RS = red_set CL pr in
        irep_nonempty RS ∧ dlic i cells w pr RS)
        (remdups (map fst (filter (λ(pr, m, R). m = length (snd pr)) CL))))›
    unfolding dcands_def gc using ne
    by (cases w) (auto simp: Let_def)
  then show ?thesis unfolding gc by (force simp: Let_def)
qed

subsection ‹Determinism: the hypothesis const‹dpick› needs›

text ‹
  The obligation const‹dpick› needs is stated operationally, without
  reference to a static report: at a reachable configuration no two distinct
  candidates may both have live successors. A conflict report is a sufficient
  condition for this, not its definition.

  The static conditions in the literature are of that kind: Knuth requires the
  shift set ‹Z› and the reduce sets ‹Zp› of
  cite‹‹Sect.~II, Eqs.~(19)--(20)› in "knuth1965-lr-translation"› to be
  disjoint, and DeRemer and Pennello call a state inconsistent when it has a
  read-reduce or a reduce-reduce conflict
  cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›.  Both are conditions on
  states; ‹mdet› is a condition on reachable configurations, which
  include the anchor sets and the input columns.
›

definition mdet :: ‹('n, 't) is_cfg ⇒ 'n ⇒ bool› where
  ‹mdet G Shn ⟷ (∀gc istk i redtab CL a1 a2 gc1 gc2.
      imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (gc, istk) ⟶
      i = hd istk ⟶
      redtab = red_buckets G Shn (length (pr0_states G Shn)) ! i ⟶
      CL = xclosure_auto G (hd (fst gc)) ⟶
      a1 ∈ set (dcands G i redtab CL gc) ⟶
      a2 ∈ set (dcands G i redtab CL gc) ⟶
      a1 ≠ a2 ⟶
      mstep G gc a1 = Some gc1 ⟶ mstep G gc a2 = Some gc2 ⟶
      dlive gc1 ⟶ dlive gc2 ⟶ False)›

text ‹Its consequence for const‹dpick›: if the trace's action is offered and
  its successor is live, const‹dpick› commits to that action, since no
  earlier candidate survives the const‹dlive› test.›

lemma dpick_forced:
  assumes det: ‹mdet G Shn›
    and ireach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (gc, istk)›
    and ieq: ‹i = hd istk›
    and req: ‹redtab = red_buckets G Shn (length (pr0_states G Shn)) ! i›
    and CL: ‹CL = xclosure_auto G (hd (fst gc))›
    and okc: ‹cstk = map (xclosure_auto G) (fst gc)›
    and a_mem: ‹a ∈ set (dcands G i redtab CL gc)›
    and step: ‹mstep G gc a = Some gc'› and live: ‹dlive gc'›
  shows ‹dpick G cstk gc (dcands G i redtab CL gc) = Some (a, gc')›
proof -
  obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
  have mc: ‹⋀act. mstep_cached G cstk gc act = mstep G gc act›
    unfolding okc gc mstep_def by simp
  have aux: ‹⋀acts. set acts ⊆ set (dcands G i redtab CL gc) ⟹ a ∈ set acts ⟹
             dpick G cstk gc acts = Some (a, gc')›
  proof -
    fix acts
    show ‹set acts ⊆ set (dcands G i redtab CL gc) ⟹ a ∈ set acts ⟹
          dpick G cstk gc acts = Some (a, gc')›
    proof (induction acts)
      case Nil then show ?case by simp
    next
      case (Cons act' rest)
      from Cons.prems have act'_mem: ‹act' ∈ set (dcands G i redtab CL gc)›
        and rest_sub: ‹set rest ⊆ set (dcands G i redtab CL gc)› by auto
      show ?case
      proof (cases ‹act' = a›)
        case True
        then show ?thesis using step live mc by simp
      next
        case ne: False
        with Cons.prems(2) have a_rest: ‹a ∈ set rest› by simp
        show ?thesis
        proof (cases ‹mstep_cached G cstk gc act'›)
          case None
          then show ?thesis using Cons.IH[OF rest_sub a_rest] by simp
        next
          case (Some gc'')
          show ?thesis
          proof (cases ‹dlive gc''›)
            case True
            have ‹mstep G gc act' = Some gc''› using Some mc by simp
            from det[unfolded mdet_def, rule_format,
                     OF ireach ieq req CL act'_mem a_mem ne this step True live]
            show ?thesis ..
          next
            case False
            then show ?thesis using Some Cons.IH[OF rest_sub a_rest] by simp
          qed
        qed
      qed
    qed
  qed
  show ?thesis by (rule aux[OF subset_refl a_mem])
qed

subsection ‹Completeness reduces to non-failure›

text ‹Soundness recovers the const‹ast_of› property of whatever tree comes
  back, so the completeness obligation is only that the driver does not get
  stuck. This removes the tree-stack and const‹realizes› components from
  the remaining induction.›

lemma dparse_complete_of_ne:
  assumes fn: ‹fresh_name G Shn›
    and ne: ‹dparse G Shn w ≠ None›
  shows ‹∃t. dparse G Shn w = Some t ∧
             ast_of G (Nt (istart G)) (istart_ind G) t w›
proof -
  from ne obtain t where p: ‹dparse G Shn w = Some t› by auto
  from dparse_sound_ast[OF fn p] show ?thesis using p by blast
qed

subsection ‹The root cell›

text ‹The base case of the recursion: the start cell
  ‹(i0, (start_prod, 0), None, WAny)› inherits to every production of
  term‹istart G› with relation ‹wcomp (winv (w_of Eq)) WAny = WAny›, because
  the material after the dot in const‹start_prod› is empty and hence
  vacuously nullable.›

lemma cell_ok_root:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and i0: ‹i0 = st_find sts (lr0_start G Shn)›
    and br: ‹br ∈ set (iprods G)› and brS: ‹fst br = istart G›
  shows ‹cell_ok L i0 br 0 [] j›
proof -
  have start_mem: ‹(i0, (start_prod G Shn, 0), None, WAny) ∈ set L›
    using tab i0 unfolding tables_ok_def la_start_def by auto
  have m_lt: ‹0 < length (snd (start_prod G Shn))›
    unfolding start_prod_def by simp
  have nxt: ‹fst (snd (start_prod G Shn) ! 0) = Nt (istart G)›
    unfolding start_prod_def by simp
  have nul: ‹list_all (λ(X, r). nsym (nullables G) X)
        (drop (Suc 0) (snd (start_prod G Shn)))›
    unfolding start_prod_def by simp
  from cell_child_inherit[OF tab start_mem m_lt nxt br brS nul]
  have ‹(i0, (br, 0), None,
          wcomp (winv (w_of (snd (snd (start_prod G Shn) ! 0)))) WAny) ∈ set L› .
  then have ‹(i0, (br, 0), None, WAny) ∈ set L›
    unfolding start_prod_def by simp
  then show ?thesis unfolding cell_ok_def by auto
qed

subsection ‹A driveable action list›

text ‹Everything the deterministic driver needs of a machine action list,
  bundled into one predicate: at every position the index-carrying machine
  steps, the successor is const‹dlive›, and a reduce is licensed by the cell
  table. It is the only hypothesis the bridge below takes about the trace.›

definition mdrive :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list ⇒ ('n, 't) dact list ⇒
    ('n, 't) icfg ⇒ bool› where
  ‹mdrive G gt sts L acts ic ⟷
     (∀p < length acts. ∃icp ic'. imrun G gt sts (take p acts) ic = Some icp ∧
        imstep G gt sts icp (acts ! p) = Some ic' ∧ dlive (fst ic') ∧
        (∀pr. acts ! p = DReduce pr ⟶ lic_at G L sts icp pr))›

lemma mdrive_Nil [simp]: ‹mdrive G gt sts L [] ic›
  unfolding mdrive_def by simp

lemma mdrive_ConsD:
  assumes ‹mdrive G gt sts L (act # acts) ic›
  shows ‹∃ic1. imstep G gt sts ic act = Some ic1 ∧ dlive (fst ic1) ∧
      (∀pr. act = DReduce pr ⟶ lic_at G L sts ic pr) ∧
      mdrive G gt sts L acts ic1›
proof -
  from assms[unfolded mdrive_def, rule_format, of 0] obtain ic1 where
      st: ‹imstep G gt sts ic act = Some ic1› and lv: ‹dlive (fst ic1)›
    and lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ic pr› by auto
  have ‹mdrive G gt sts L acts ic1›
    unfolding mdrive_def
  proof (intro allI impI)
    fix p assume p: ‹p < length acts›
    then have ‹Suc p < length (act # acts)› by simp
    from assms[unfolded mdrive_def, rule_format, OF this] obtain icp ic' where
        r: ‹imrun G gt sts (take (Suc p) (act # acts)) ic = Some icp›
      and s: ‹imstep G gt sts icp ((act # acts) ! Suc p) = Some ic'›
      and l: ‹dlive (fst ic')›
      and c: ‹∀pr. (act # acts) ! Suc p = DReduce pr ⟶ lic_at G L sts icp pr› by blast
    have r': ‹imrun G gt sts (take p acts) ic1 = Some icp› using r st by simp
    have s': ‹imstep G gt sts icp (acts ! p) = Some ic'› using s by simp
    have c': ‹∀pr. acts ! p = DReduce pr ⟶ lic_at G L sts icp pr› using c by simp
    show ‹∃icp ic'. imrun G gt sts (take p acts) ic1 = Some icp ∧
        imstep G gt sts icp (acts ! p) = Some ic' ∧ dlive (fst ic') ∧
        (∀pr. acts ! p = DReduce pr ⟶ lic_at G L sts icp pr)›
      using r' s' l c' by blast
  qed
  with st lv lc show ?thesis by blast
qed

lemma mdrive_ConsI:
  assumes st: ‹imstep G gt sts ic act = Some ic1› and lv: ‹dlive (fst ic1)›
    and lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ic pr›
    and rest: ‹mdrive G gt sts L acts ic1›
  shows ‹mdrive G gt sts L (act # acts) ic›
  unfolding mdrive_def
proof (intro allI impI)
  fix p assume p: ‹p < length (act # acts)›
  show ‹∃icp ic'. imrun G gt sts (take p (act # acts)) ic = Some icp ∧
      imstep G gt sts icp ((act # acts) ! p) = Some ic' ∧ dlive (fst ic') ∧
      (∀pr. (act # acts) ! p = DReduce pr ⟶ lic_at G L sts icp pr)›
  proof (cases p)
    case 0
    have r0: ‹imrun G gt sts (take 0 (act # acts)) ic = Some ic› by simp
    have s0: ‹imstep G gt sts ic ((act # acts) ! 0) = Some ic1› using st by simp
    have c0: ‹∀pr. (act # acts) ! 0 = DReduce pr ⟶ lic_at G L sts ic pr› using lc by simp
    show ?thesis unfolding 0 using r0 s0 lv c0 by blast
  next
    case (Suc q)
    then have q: ‹q < length acts› using p by simp
    from rest[unfolded mdrive_def, rule_format, OF q] obtain icp ic' where
        r: ‹imrun G gt sts (take q acts) ic1 = Some icp›
      and s: ‹imstep G gt sts icp (acts ! q) = Some ic'›
      and l: ‹dlive (fst ic')›
      and c: ‹∀pr. acts ! q = DReduce pr ⟶ lic_at G L sts icp pr› by blast
    have r': ‹imrun G gt sts (take (Suc q) (act # acts)) ic = Some icp› using r st by simp
    have s': ‹imstep G gt sts icp ((act # acts) ! Suc q) = Some ic'› using s by simp
    have c': ‹∀pr. (act # acts) ! Suc q = DReduce pr ⟶ lic_at G L sts icp pr› using c by simp
    show ?thesis unfolding Suc using r' s' l c' by blast
  qed
qed

lemma mdrive_append:
  assumes as: ‹mdrive G gt sts L as ic›
    and run: ‹imrun G gt sts as ic = Some ic'›
    and bs: ‹mdrive G gt sts L bs ic'›
  shows ‹mdrive G gt sts L (as @ bs) ic›
  using as run
proof (induction as arbitrary: ic)
  case Nil then show ?case using bs by simp
next
  case (Cons act as)
  from mdrive_ConsD[OF Cons.prems(1)] obtain ic1 where
      st: ‹imstep G gt sts ic act = Some ic1› and lv: ‹dlive (fst ic1)›
    and lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ic pr›
    and rest: ‹mdrive G gt sts L as ic1› by blast
  have ‹imrun G gt sts as ic1 = Some ic'› using Cons.prems(2) st by simp
  from Cons.IH[OF rest this] show ?case
    by (simp add: mdrive_ConsI[OF st lv lc])
qed
subsection ‹The driver state tracks the index-carrying machine›

text ‹The closure cache mirrors the frame stack, the index stack tracks the
  frames (const‹didx_ok›), the spanned input is the raw input's
  const‹tcols›, and the tree stack has one entry per non-initial frame. All
  four are preserved by a step, and all four hold at const‹dinit›.›

definition dfollow_ok :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒
    ('m, 'ch, 'n, 't) dst ⇒ bool› where
  ‹dfollow_ok G sts st ⟷ (case st of ((Xs, w), cstk, istk, v, tstk) ⇒
      cstk = map (xclosure_auto G) Xs ∧ didx_ok G sts Xs istk ∧
      w = tcols v ∧ Suc (length tstk) = length Xs)›

lemma cell_buckets_length [simp]: ‹length (cell_buckets L n) = n›
  unfolding cell_buckets_def Let_def by simp

lemma red_buckets_length [simp]: ‹length (red_buckets G Shn n) = n›
  by (simp add: red_buckets_def)

lemma live_nonempty: ‹live xs ⟹ xs ≠ []›
  unfolding live_def by auto

text ‹The remaining input and the tree stack after a step depend only on the
  action: a shift consumes the next token and pushes its leaf, a reduce
  folds the right-hand side.›

fun tstep :: ‹('n, 't) dact ⇒ ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list ⇒
    ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list› where
  ‹tstep DShift (v, tstk) = (tl v, Leaf (hd v) # tstk)›
| ‹tstep (DReduce pr) (v, tstk) =
     (v, Node (fst pr) (rev (take (length (snd pr)) tstk)) # drop (length (snd pr)) tstk)›

text ‹The driver takes the trace's action: it is among the candidates, and
  const‹dpick› commits to it.  The new state is explicit.  The pick is a premise of
  text‹dstep_of_dpick›; under const‹mdet› it is forced (text‹dpick_forced›).›

lemma dstep_of_dpick:
  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 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›
    and pick_of: ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w)) ⟹
      dpick G cstk (Xs, w) (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w))
        = Some (act, gc')›
  shows ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w)) ∧
         (∃v' tstk'. (v', tstk') = tstep act (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 inv have cstk_eq: ‹cstk = map (xclosure_auto G) Xs›
    and ok: ‹didx_ok G sts Xs istk› and vw: ‹w = tcols v›
    and lens: ‹Suc (length tstk) = length Xs›
    unfolding dfollow_ok_def by auto
  have len_i: ‹length istk = length Xs› by (rule didx_ok_len[OF ok])
  have ms: ‹mstep G (Xs, w) act = Some gc'›
    using imstep_mstep[of G gt sts ‹((Xs, w), istk)› act ‹(gc', istk')›] step by simp
  have msc: ‹mstep_cached G cstk (Xs, w) act = Some gc'›
    using ms unfolding mstep_def cstk_eq by simp
  have Xs_ne: ‹Xs ≠ []›
    using msc unfolding mstep_cached_def
    by (auto split: dact.splits list.splits if_splits)
  then have istk_ne: ‹istk ≠ []› using len_i by auto
  have hd_cstk: ‹hd cstk = xclosure_auto G (hd Xs)›
    using cstk_eq Xs_ne by (simp add: hd_map)
  have i_lt: ‹hd istk < length sts›
    using didx_ok_hd_lt[OF ok] imreach_dlive[OF ireach] by simp
  have gc'_ne: ‹fst gc' ≠ []› and gc'_live: ‹live (hd (fst gc'))›
    using live unfolding dlive_def by (cases gc'; simp)+
  let ?i = ‹hd istk› and ?CL = ‹xclosure_auto G (hd Xs)›
  let ?cells = ‹cell_buckets L (length sts) ! ?i›
  have rt': ‹redtab = cell_buckets L (length sts)›
    unfolding rt Lc stc by (rule cell_buckets_red_buckets[symmetric])
  have req: ‹?cells = red_buckets G Shn (length (pr0_states G Shn)) ! ?i›
    unfolding Lc stc by (simp add: cell_buckets_red_buckets)
  have ireach': ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk)›
    using ireach unfolding gtc stc .
  have cells_eq: ‹(if ?i < length redtab then redtab ! ?i else []) = ?cells›
    using i_lt rt' by simp
  have CL_eq: ‹(case cstk of [] ⇒ [] | c # _ ⇒ c) = ?CL›
    using cstk_eq Xs_ne hd_cstk by (cases cstk) auto
  have i_eq: ‹(case istk of [] ⇒ length sts | j # _ ⇒ j) = ?i›
    using istk_ne by (cases istk) auto
  have cstk_eq': ‹cstk = map (xclosure_auto G) (fst (Xs, w))› using cstk_eq by simp
  have cells_rt: ‹redtab ! ?i = ?cells› using rt' by simp
  show ?thesis
  proof (cases act)
    case DShift
    have sh: ‹mstep_cached G cstk (Xs, w) DShift = Some gc'› using msc DShift by simp
    obtain a c w' where w_eq: ‹w = (a, c) # w'›
      and gc'_eq: ‹gc' = (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')›
      using sh unfolding mstep_cached_def by (auto split: list.splits if_splits)
    have v_ne: ‹v ≠ []› using vw w_eq by auto
    then obtain t0 v0 where v_eq: ‹v = t0 # v0› by (cases v) auto
    have a_eq: ‹a = tok t0› and w'_eq: ‹w' = tcols v0›
      using vw w_eq v_eq unfolding tcols_def by auto
    have offered: ‹DShift ∈ set (dcands G ?i ?cells ?CL (Xs, w))›
      by (rule dcands_shift) (use Xs_ne w_eq in auto)
    have pick: ‹dpick G cstk (Xs, w) (dcands G ?i ?cells ?CL (Xs, w)) = Some (DShift, gc')›
      using pick_of offered DShift cells_rt by simp
    have dstep_eq: ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk) =
        Some (gc', xclosure_auto G (hd (fst gc')) # cstk,
              dnext gt sts ?i (Tm (tok (hd v))) # istk, tl v, Leaf (hd v) # tstk)›
      unfolding dstep_def rt' by (simp add: Let_def i_eq CL_eq i_lt pick)
    have istk'_eq: ‹istk' = dnext gt sts ?i (Tm a) # istk›
      using step ms unfolding imstep_def DShift by (simp add: w_eq)
    have cstk'_eq: ‹xclosure_auto G (hd (fst gc')) # cstk = map (xclosure_auto G) (fst gc')›
      using gc'_eq cstk_eq by simp
    have i0: ‹istk ! 0 = hd istk› using istk_ne by (simp add: hd_conv_nth)
    have x0: ‹Xs ! 0 = hd Xs› using Xs_ne by (simp add: hd_conv_nth)
    have push: ‹didx_ok G sts (fst gc') istk'›
      using didx_ok_push[OF tab ok, of 0 ‹Tm a› ‹FinRep [c]›] Xs_ne
        gc'_live[unfolded gc'_eq] gc'_eq istk'_eq
      by (simp add: i0 x0 hd_cstk live_nonempty)
    show ?thesis
    proof (intro conjI exI)
      show ‹act ∈ set (dcands G ?i (redtab ! ?i) ?CL (Xs, w))›
        using offered unfolding DShift cells_rt .
      show ‹(tl v, Leaf (hd v) # tstk) = tstep act (v, tstk)›
        unfolding DShift by simp
      show ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk) =
          Some (gc', map (xclosure_auto G) (fst gc'), istk', tl v, Leaf (hd v) # tstk)›
        unfolding dstep_eq cstk'_eq istk'_eq using a_eq v_eq by simp
      show ‹dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk',
              tl v, Leaf (hd v) # tstk)›
        unfolding dfollow_ok_def using push gc'_eq w'_eq v_eq lens by simp
    qed
  next
    case (DReduce pr)
    let ?k = ‹length (snd pr)›
    have red: ‹mstep_cached G cstk (Xs, w) (DReduce pr) = Some gc'› using msc DReduce by simp
    have k_lt: ‹?k < length Xs› and RS_ne: ‹irep_nonempty (red_set (hd cstk) pr)›
      and gc'_eq: ‹gc' = (lgoto (cstk ! ?k) (Nt (fst pr)) (red_set (hd cstk) pr) # drop ?k Xs, w)›
      using red unfolding mstep_cached_def by (auto simp: Let_def split: if_splits)
    have RS_ne': ‹irep_nonempty (red_set ?CL pr)› using RS_ne hd_cstk by simp
    obtain R where compR: ‹(pr, ?k, R) ∈ set ?CL›
      using RS_ne' unfolding red_set_nonempty_iff by auto
    have dlicL: ‹dlic_L ?i L w pr (red_set ?CL pr)›
      using lic DReduce unfolding lic_at_def by simp
    have dlic': ‹dlic ?i ?cells w pr (red_set ?CL pr)›
      by (rule dlic_buckets[OF i_lt, THEN iffD2, OF dlicL])
    have offered: ‹DReduce pr ∈ set (dcands G ?i ?cells ?CL (Xs, w))›
      by (rule dcands_reduceI[OF _ compR RS_ne']) (use Xs_ne dlic' in auto)
    have pick: ‹dpick G cstk (Xs, w) (dcands G ?i ?cells ?CL (Xs, w)) = Some (DReduce pr, gc')›
      using pick_of offered DReduce cells_rt by simp
    have dstep_eq: ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk) =
        Some (gc', xclosure_auto G (hd (fst gc')) # drop ?k cstk,
              dnext gt sts (istk ! ?k) (Nt (fst pr)) # drop ?k istk, v,
              Node (fst pr) (rev (take ?k tstk)) # drop ?k tstk)›
      unfolding dstep_def rt' by (simp add: Let_def i_eq CL_eq i_lt pick)
    have istk'_eq: ‹istk' = dnext gt sts (istk ! ?k) (Nt (fst pr)) # drop ?k istk›
      using step ms unfolding imstep_def DReduce by simp
    have cstk'_eq: ‹xclosure_auto G (hd (fst gc')) # drop ?k cstk =
        map (xclosure_auto G) (fst gc')›
      using gc'_eq cstk_eq by (simp add: drop_map)
    have cstk_k: ‹cstk ! ?k = xclosure_auto G (Xs ! ?k)› using cstk_eq k_lt by simp
    have push: ‹didx_ok G sts (fst gc') istk'›
      using didx_ok_push[OF tab ok k_lt, of ‹Nt (fst pr)› ‹red_set (hd cstk) pr›]
        gc'_live[unfolded gc'_eq] gc'_eq istk'_eq cstk_k
      by (simp add: live_nonempty)
    show ?thesis
    proof (intro conjI exI)
      show ‹act ∈ set (dcands G ?i (redtab ! ?i) ?CL (Xs, w))›
        using offered unfolding DReduce cells_rt .
      show ‹(v, Node (fst pr) (rev (take ?k tstk)) # drop ?k tstk) = tstep act (v, tstk)›
        unfolding DReduce by simp
      show ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk) =
          Some (gc', map (xclosure_auto G) (fst gc'), istk', v,
                Node (fst pr) (rev (take ?k tstk)) # drop ?k tstk)›
        unfolding dstep_eq cstk'_eq istk'_eq by simp
      show ‹dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v,
              Node (fst pr) (rev (take ?k tstk)) # drop ?k tstk)›
        unfolding dfollow_ok_def using push gc'_eq vw lens k_lt by simp
    qed
  qed
qed

lemma dstep_of_imstep_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'. (v', tstk') = tstep act (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 -
  have ‹cstk = map (xclosure_auto G) (fst (Xs, w))› using inv unfolding dfollow_ok_def by auto
  moreover have ‹mstep G (Xs, w) act = Some gc'›
    using imstep_mstep[of G gt sts ‹((Xs, w), istk)› act ‹(gc', istk')›] step by simp
  moreover have ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ((Xs, w), istk)›
    using ireach unfolding gtc stc .
  moreover have ‹redtab ! hd istk = red_buckets G Shn (length (pr0_states G Shn)) ! hd istk›
    unfolding rt stc ..
  ultimately show ?thesis
    by (intro dstep_of_dpick[OF tab stc gtc Lc rt ireach inv step live lic] dpick_forced[OF det _ refl])
       (simp_all add: live)
qed

lemma dstep_of_imstep:
  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 ‹∃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')›
  using dstep_of_imstep_exact[OF assms] by blast

subsection ‹Iterating: the driver follows the whole run›

lemma dsteps_of_mdrive:
  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›
  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) ⟹
     ∃gc' istk' v' tstk'. imrun G gt sts acts (gc, istk) = 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') ∧
        dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
proof (induction acts arbitrary: gc istk cstk v tstk)
  case Nil
  obtain Xs w where gc_eq: ‹gc = (Xs, w)› by (cases gc)
  have ‹cstk = map (xclosure_auto G) (fst gc)›
    using Nil.prems(3) gc_eq unfolding dfollow_ok_def by simp
  then show ?case using Nil.prems(3) by auto
next
  case (Cons act acts)
  obtain Xs w where gc_eq: ‹gc = (Xs, w)› 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, w), istk) act = Some (gc1, istk1)›
    using st0 gc_eq ic1 by simp
  have lv: ‹dlive gc1› using lv0 ic1 by simp
  have lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ((Xs, w), istk) pr›
    using lc0 gc_eq by simp
  have ireach: ‹imreach G Shn gt sts ((Xs, w), istk)› using Cons.prems(2) gc_eq by simp
  have inv: ‹dfollow_ok G sts ((Xs, w), cstk, istk, v, tstk)›
    using Cons.prems(3) gc_eq by simp
  from dstep_of_imstep[OF tab stc gtc Lc rt det ireach inv st lv lc] obtain v1 tstk1 where
      ds: ‹dstep G gt sts redtab ((Xs, w), 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 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
  from Cons.IH[OF rest ireach1 inv1] obtain gc' istk' v' tstk' where
      ir: ‹imrun G gt sts acts (gc1, istk1) = Some (gc', istk')›
    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')›
    and inv': ‹dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
    by blast
  show ?case
  proof (intro exI conjI)
    show ‹imrun G gt sts (act # acts) (gc, istk) = Some (gc', istk')›
      using st0 ic1 ir by simp
    show ‹dsteps G gt sts redtab (length (act # acts)) (gc, cstk, istk, v, tstk) =
        Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
      using ds dr gc_eq by simp
  qed (rule inv')
qed

subsection ‹From a completed chain to const‹drunwf››

text ‹Every const‹dstep› pushes, so any state the driver reaches has a
  non-empty tree stack. Together with ``the start is not final'' that is all
  const‹drunwf› needs: it may stop at an earlier
  const‹gfinal› than the chain does, but it never returns const‹None›.
  Since completeness reduces to non-failure (text‹dparse_complete_of_ne›),
  that suffices.›

lemma dstep_tstk_ne:
  ‹dstep G gt sts redtab st = Some st' ⟹
     (case st' of (gc, cstk, istk, v, tstk) ⇒ tstk) ≠ []›
  unfolding dstep_def
  by (auto simp: Let_def split: option.splits prod.splits dact.splits)

lemma drunwf_ne_of_dsteps:
  ‹dsteps G gt sts redtab n st = Some st' ⟹ gfinal G Shn (fst st') ⟹
   ¬ gfinal G Shn (fst st) ⟹ drunwf G Shn gt sts redtab st ≠ None›
proof (induction n arbitrary: st)
  case 0 then show ?case by simp
next
  case (Suc n)
  from Suc.prems(1) obtain st1 where
      sp: ‹dstep G gt sts redtab st = Some st1›
    and rn: ‹dsteps G gt sts redtab n st1 = Some st'›
    by (auto split: option.splits)
  have unf: ‹drunwf G Shn gt sts redtab st = drunwf G Shn gt sts redtab st1›
    using Suc.prems(3) sp by (cases st) simp
  show ?case
  proof (cases ‹gfinal G Shn (fst st1)›)
    case True
    have ‹(case st1 of (gc, cstk, istk, v, tstk) ⇒ tstk) ≠ []›
      by (rule dstep_tstk_ne[OF sp])
    then show ?thesis unfolding unf using True by (cases st1) (auto split: list.splits)
  next
    case False
    from Suc.IH[OF rn Suc.prems(2) False] show ?thesis unfolding unf .
  qed
qed

subsection ‹The driver is complete for any licensed, deterministic trace›

lemma dfollow_ok_dinit:
  ‹dfollow_ok G (pr0_states G Shn) (dinit G Shn (pr0_states G Shn) w)›
  unfolding dfollow_ok_def dinit_def using didx_ok_init[OF tables_ok_concrete] by simp

lemma not_gfinal_xinit: ‹¬ gfinal G Shn ([xinit G Shn], u)›
  unfolding gfinal_def xinit_def start_prod_def by simp

theorem dparse_ne_of_mdrive:
  assumes det: ‹mdet G Shn›
    and drv: ‹mdrive G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (la_fix G Shn)
                acts (([xinit G Shn], tcols w), [st_find (pr0_states G Shn) (lr0_start G Shn)])›
    and fin: ‹mcompletes G Shn acts ([xinit G Shn], tcols w)›
  shows ‹dparse G Shn w ≠ None›
proof -
  let ?sts = ‹pr0_states G Shn› and ?gt = ‹pgtab G (pr0_states G Shn)›
  let ?L = ‹la_fix G Shn› and ?redtab = ‹red_buckets G Shn (length (pr0_states G Shn))›
  have tab: ‹tables_ok G Shn ?sts ?gt ?L› by (rule tables_ok_concrete)
  have rt: ‹?redtab = red_buckets G Shn (length ?sts)› by (rule refl)
  let ?ist = ‹[st_find ?sts (lr0_start G Shn)]›
  have inv: ‹dfollow_ok G ?sts (([xinit G Shn], tcols w),
      [xclosure_auto G (xinit G Shn)], ?ist, w, [])›
    using dfollow_ok_dinit[of G Shn w] unfolding dinit_def .
  from dsteps_of_mdrive[OF tab refl refl refl rt det drv imreach_init inv]
  obtain gc' istk' v' tstk' where
      ir: ‹imrun G ?gt ?sts acts (([xinit G Shn], tcols w), ?ist) = Some (gc', istk')›
    and dr: ‹dsteps G ?gt ?sts ?redtab (length acts)
              (([xinit G Shn], tcols w), [xclosure_auto G (xinit G Shn)], ?ist, w, []) =
                Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')› by blast
  have mr: ‹mrun G acts ([xinit G Shn], tcols w) = Some gc'›
    using imrun_mrun[OF ir] by simp
  have gf: ‹gfinal G Shn gc'› using fin mr unfolding mcompletes_def by simp
  have ‹drunwf G Shn ?gt ?sts ?redtab
      (([xinit G Shn], tcols w), [xclosure_auto G (xinit G Shn)], ?ist, w, []) ≠ None›
    by (rule drunwf_ne_of_dsteps[OF dr _ ]) (use gf not_gfinal_xinit in simp_all)
  then show ?thesis unfolding dparse_def dinit_def Let_def by simp
qed

theorem dparse_complete_of_mdrive:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn›
    and drv: ‹mdrive G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (la_fix G Shn)
                acts (([xinit G Shn], tcols w), [st_find (pr0_states G Shn) (lr0_start G Shn)])›
    and fin: ‹mcompletes G Shn acts ([xinit G Shn], tcols w)›
  shows ‹∃t. dparse G Shn w = Some t ∧ ast_of G (Nt (istart G)) (istart_ind G) t w›
  by (rule dparse_complete_of_ne[OF fn dparse_ne_of_mdrive[OF det drv fin]])



section ‹The licensing recursion›

subsection ‹A subtree list derives its yield›

text ‹const‹anntree› turns a const‹wf_ptree› into a const‹parse_tree› of
  const‹infG›, so text‹derives_fringe_if_parse_tree› gives the derivation of
  its yield; text‹derives_concat› lifts that to a list of siblings.›

lemma wf_ptree_derives:
  ‹wf_ptree G pt ⟹ infG G ⊢ [annsym (proot pt)] ⇒* map Tm (tcols (pyield pt))›
  using derives_fringe_if_parse_tree[of ‹infG G› ‹anntree pt›] by simp

lemma wf_ptree_list_derives:
  assumes ‹∀pt ∈ set pts. wf_ptree G pt›
  shows ‹infG G ⊢ map (λpt. annsym (proot pt)) pts ⇒*
           map Tm (tcols (concat (map pyield pts)))›
proof -
  have e1: ‹concat (map (λpt. [annsym (proot pt)]) pts) = map (λpt. annsym (proot pt)) pts›
    by (induction pts) auto
  have e2: ‹concat (map (λpt. map Tm (tcols (pyield pt))) pts) =
      map Tm (tcols (concat (map pyield pts)))›
    by (induction pts) auto
  have ‹infG G ⊢ concat (map (λpt. [annsym (proot pt)]) pts) ⇒*
        concat (map (λpt. map Tm (tcols (pyield pt))) pts)›
    by (rule derives_concat) (use assms wf_ptree_derives in blast)
  then show ?thesis unfolding e1 e2 .
qed

text ‹The roots of the siblings annotate the right-hand-side suffix they were
  matched against.›

lemma annotates_of_kids:
  assumes ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
      irel_sat (snd Xr) (snd (proot pt)) j) sfx pts›
  shows ‹annotates j sfx (map (λpt. annsym (proot pt)) pts)›
  unfolding annotates_def using assms
proof (induction rule: list_all2_induct)
  case Nil
  show ?case by simp
next
  case (Cons Xr sfx' pt pts')
  obtain X r where Xr: ‹Xr = (X, r)› by (cases Xr)
  have ‹annsym (proot pt) = annsym (X, snd (proot pt))›
    using Cons.hyps(1) Xr by (cases ‹proot pt›) simp
  then show ?case using Cons.hyps(1) Cons.IH Xr by auto
qed

subsection ‹The two cases of text‹cell_ok_child›, supplied from the siblings›

lemma kids_first:
  assumes kids: ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
        irel_sat (snd Xr) (snd (proot pt)) j) sfx pts›
    and wf: ‹∀pt ∈ set pts. wf_ptree G pt›
    and yield: ‹tcols (concat (map pyield pts)) = (a, cl) # V›
  shows ‹∃σ. (a, σ) ∈ set (fscan (ffix G) (nullables G) sfx) ∧ csat σ cl j›
proof -
  have ann: ‹annotates j sfx (map (λpt. annsym (proot pt)) pts)›
    by (rule annotates_of_kids[OF kids])
  have ‹infG G ⊢ map (λpt. annsym (proot pt)) pts ⇒* map Tm (tcols (concat (map pyield pts)))›
    by (rule wf_ptree_list_derives[OF wf])
  then have ‹infG G ⊢ map (λpt. annsym (proot pt)) pts ⇒* Tm (a, cl) # map Tm V›
    unfolding yield by simp
  then obtain n where ‹infG G ⊢ map (λpt. annsym (proot pt)) pts ⇒(n) Tm (a, cl) # map Tm V›
    by (auto simp: rtranclp_power)
  from fscan_complete[OF this ann] show ?thesis .
qed

lemma kids_null:
  assumes kids: ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
        irel_sat (snd Xr) (snd (proot pt)) j) sfx pts›
    and wf: ‹∀pt ∈ set pts. wf_ptree G pt›
    and yield: ‹concat (map pyield pts) = []›
  shows ‹list_all (λ(X, r). nsym (nullables G) X) sfx›
proof -
  have len: ‹length pts = length sfx› using kids by (simp add: list_all2_lengthD)
  have ‹∀p < length sfx. nsym (nullables G) (fst (sfx ! p))›
  proof (intro allI impI)
    fix p assume p: ‹p < length sfx›
    then have mem: ‹pts ! p ∈ set pts› using len by simp
    have ‹pyield (pts ! p) = []› using yield p len by simp
    from wf_ptree_nsym_of_empty_yield[OF _ this] wf mem
    have ‹nsym (nullables G) (fst (proot (pts ! p)))› by blast
    then show ‹nsym (nullables G) (fst (sfx ! p))›
      using list_all2_nthD[OF kids p] by simp
  qed
  then show ?thesis by (simp add: list_all_length case_prod_beta)
qed

subsection ‹A frame slot for a symbol: what makes the pushed frame live›

text ‹The pushed frame term‹lgoto CL X RA› is const‹live› iff the
  source frame closure has an item with ‹X› after the dot whose anchor is
  compatible with some anchor of term‹RA›. That witness is available at every
  push the tree recursion makes: for a child it is the parent's own item, and
  for the root it is the start item of const‹xinit›.›

definition slot_ok :: ‹('n, 't) xitem list ⇒ ('n, 't) sym ⇒ nat ⇒ bool› where
  ‹slot_ok CL X j ⟷ (∃pr m R j'. (pr, m, R) ∈ set CL ∧ m < length (snd pr) ∧
      fst (snd pr ! m) = X ∧ j' ∈ irep_set R ∧ irel_sat (snd (snd pr ! m)) j j')›

lemma slot_okI:
  ‹(pr, m, R) ∈ set CL ⟹ m < length (snd pr) ⟹ fst (snd pr ! m) = X ⟹
   j' ∈ irep_set R ⟹ irel_sat (snd (snd pr ! m)) j j' ⟹ slot_ok CL X j›
  unfolding slot_ok_def by blast

lemma slot_ok_live:
  assumes slot: ‹slot_ok CL X j› and j: ‹j ∈ irep_set RA›
  shows ‹live (lgoto CL X RA)›
proof -
  from slot obtain pr m R j' where
      mem: ‹(pr, m, R) ∈ set CL› and m_lt: ‹m < length (snd pr)›
    and Xeq: ‹fst (snd pr ! m) = X› and j'R: ‹j' ∈ irep_set R›
    and sat: ‹irel_sat (snd (snd pr ! m)) j j'› unfolding slot_ok_def by blast
  let ?R' = ‹irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
  have inl: ‹(pr, Suc m, ?R') ∈ set (lgoto CL X RA)›
    by (rule lgoto_memI[OF mem m_lt Xeq])
  have ne: ‹irep_nonempty ?R'› using j'R j sat by auto
  show ?thesis unfolding live_def list_ex_iff
    by (intro bexI[of _ ‹(pr, Suc m, ?R')›]) (use inl ne in auto)
qed

lemma slot_ok_dlive:
  ‹slot_ok CL X j ⟹ j ∈ irep_set RA ⟹ dlive (lgoto CL X RA # Ys, u)›
  unfolding dlive_def by (simp add: slot_ok_live)

subsection ‹Moving the cell along with the index stack›

lemma cell_ok_step:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and cell: ‹cell_ok L i pr m rest j›
    and m_lt: ‹m < length (snd pr)›
  shows ‹cell_ok L (la_next gt sts i (fst (snd pr ! m))) pr (Suc m) rest j›
proof -
  from cell obtain τ where mem: ‹(i, (pr, m), tok_of rest, τ) ∈ set L›
    and rel: ‹case rest of [] ⇒ True | (a, c) # _ ⇒ wsat τ c j›
    unfolding cell_ok_def by auto
  have step: ‹(la_next gt sts i (fst (snd pr ! m)), (pr, Suc m), tok_of rest, τ)
        ∈ set (la_cell G (ffix G) (nullables G) gt sts (i, (pr, m), tok_of rest, τ))›
    by (rule la_cell_goto_mem[OF m_lt])
  from tables_ok_cell[OF tab mem step]
  have ‹(la_next gt sts i (fst (snd pr ! m)), (pr, Suc m), tok_of rest, τ) ∈ set L› .
  then show ?thesis using rel unfolding cell_ok_def by auto
qed

subsection ‹The context a subtree inherits, with the slot witness›

text ‹‹nctx› is the context a subtree inherits: besides the machine-side
  context (the closure of the top frame holds the node's production at dot 0,
  admitting the node's anchor) and the cell-side context, it carries the
  const‹slot_ok› witness that makes the frame the subtree pushes
  const‹live›.›

definition nctx :: ‹('n, 't) is_cfg ⇒ ('n, 't) lacell list ⇒ nat ⇒
    ('m, 'ch, 'n, 't) ptree ⇒ ('n, 't) dact list ⇒
    ('n, 't) xitem list list ⇒ ('t × nat) list ⇒ bool› where
  ‹nctx G L i pt acts Xs rest ⟷
     slot_ok (xclosure_auto G (hd Xs)) (fst (proot pt)) (snd (proot pt)) ∧
     (∀A j pts. pt = PNode A j pts ⟶
        (∃pr R0. acts ≠ [] ∧ last acts = DReduce pr ∧
           (pr, 0, R0) ∈ set (xclosure_auto G (hd Xs)) ∧ j ∈ irep_set R0 ∧
           cell_ok L i pr 0 rest j))›

lemma nctx_slot: ‹nctx G L i pt acts Xs rest ⟹
    slot_ok (xclosure_auto G (hd Xs)) (fst (proot pt)) (snd (proot pt))›
  unfolding nctx_def by simp

lemma nctx_node:
  assumes ‹nctx G L i (PNode A j pts) acts Xs rest›
  shows ‹∃pr R0. acts ≠ [] ∧ last acts = DReduce pr ∧
      (pr, 0, R0) ∈ set (xclosure_auto G (hd Xs)) ∧ j ∈ irep_set R0 ∧
      cell_ok L i pr 0 rest j›
  using assms unfolding nctx_def by simp

subsection ‹The licensing recursion›

text ‹Running the first ‹c› children of a node: the index stack grows in
  lockstep with the frame stack, the node's item advances to dot ‹c›, and
  its cell moves with the index.›

lemma mtrace_mdrive_kids:
  assumes tab: ‹tables_ok G Shn sts gt L›
    and kids: ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧
      irel_sat (snd Xr) (snd (proot pt)) i) rhs pts›
    and kids_tr: ‹list_all2 (mtrace G) pts trs›
    and wf_kids: ‹∀q ∈ set pts. wf_ptree G q›
    and IH: ‹⋀c Xs' istk' rest'. c < length pts ⟹ wf_ptree G (pts ! c) ⟹ Xs' ≠ [] ⟹
       didx_ok G sts Xs' istk' ⟹ nctx G L (hd istk') (pts ! c) (trs ! c) Xs' rest' ⟹
       ∃RA. snd (proot (pts ! c)) ∈ irep_set RA ∧
         mdrive G gt sts L (trs ! c) ((Xs', tcols (pyield (pts ! c)) @ rest'), istk') ∧
         imrun G gt sts (trs ! c) ((Xs', tcols (pyield (pts ! c)) @ rest'), istk') =
           Some ((lgoto (xclosure_auto G (hd Xs')) (fst (proot (pts ! c))) RA # Xs', rest'),
                 dnext gt sts (hd istk') (fst (proot (pts ! c))) # istk')›
    and Xs_ne: ‹Xs ≠ []› and ok0: ‹didx_ok G sts Xs istk›
    and item0: ‹((A, rhs), 0, R0) ∈ set (xclosure_auto G (hd Xs))›
    and i0: ‹i ∈ irep_set R0›
    and cell0: ‹cell_ok L (hd istk) (A, rhs) 0 rest i›
    and c_le: ‹c ≤ length pts›
  shows ‹∃Xsc istkc Rc.
        imrun G gt sts (concat (take c trs))
            ((Xs, tcols (concat (map pyield pts)) @ rest), istk) =
          Some ((Xsc, tcols (concat (map pyield (drop c pts))) @ rest), istkc) ∧
        mdrive G gt sts L (concat (take c trs))
            ((Xs, tcols (concat (map pyield pts)) @ rest), istk) ∧
        drop c Xsc = Xs ∧ length Xsc = c + length Xs ∧
        drop c istkc = istk ∧ length istkc = c + length istk ∧
        didx_ok G sts Xsc istkc ∧
        ((A, rhs), c, Rc) ∈ set (xclosure_auto G (hd Xsc)) ∧ i ∈ irep_set Rc ∧
        cell_ok L (hd istkc) (A, rhs) c rest i›
proof -
  have len_pr: ‹length pts = length rhs› using kids by (simp add: list_all2_lengthD)
  have len_tr: ‹length trs = length pts› using kids_tr by (simp add: list_all2_lengthD)
  show ?thesis using c_le
  proof (induction c)
    case 0
    show ?case
      by (intro exI[of _ Xs] exI[of _ istk] exI[of _ R0])
         (use item0 i0 cell0 ok0 in simp)
  next
    case (Suc c)
    then have c_lt: ‹c < length pts› by simp
    from Suc.IH[OF Suc_leD[OF Suc.prems]] obtain Xsc istkc Rc where
        run_c: ‹imrun G gt sts (concat (take c trs))
            ((Xs, tcols (concat (map pyield pts)) @ rest), istk) =
          Some ((Xsc, tcols (concat (map pyield (drop c pts))) @ rest), istkc)›
      and drv_c: ‹mdrive G gt sts L (concat (take c trs))
            ((Xs, tcols (concat (map pyield pts)) @ rest), istk)›
      and drop_c: ‹drop c Xsc = Xs› and len_c: ‹length Xsc = c + length Xs›
      and dropi_c: ‹drop c istkc = istk› and leni_c: ‹length istkc = c + length istk›
      and ok_c: ‹didx_ok G sts Xsc istkc›
      and item_c: ‹((A, rhs), c, Rc) ∈ set (xclosure_auto G (hd Xsc))›
      and i_c: ‹i ∈ irep_set Rc›
      and cell_c: ‹cell_ok L (hd istkc) (A, rhs) c rest i› by blast
    have Xsc_ne: ‹Xsc ≠ []› using len_c Xs_ne by auto
    have istkc_ne: ‹istkc ≠ []› using Xsc_ne ok_c by (auto dest: didx_ok_len)
    let ?pt = ‹pts ! c› and ?tr = ‹trs ! c›
    have kid_c: ‹fst (proot ?pt) = fst (rhs ! c) ∧ irel_sat (snd (rhs ! c)) (snd (proot ?pt)) i›
      using list_all2_nthD[OF kids, of c] c_lt len_pr by auto
    have c_rhs: ‹c < length (snd (A, rhs))› using c_lt len_pr by simp
    have wf_c: ‹wf_ptree G ?pt› using wf_kids c_lt by simp
    let ?suf = ‹tcols (concat (map pyield (drop (Suc c) pts)))›
    let ?rest_c = ‹?suf @ rest›
    ― ‹the slot witness for the child›
    have slot_c: ‹slot_ok (xclosure_auto G (hd Xsc)) (fst (proot ?pt)) (snd (proot ?pt))›
      by (rule slot_okI[OF item_c c_rhs _ i_c]) (use kid_c in simp_all)
    ― ‹the cell for the child, both cases›
    have kids_sfx: ‹list_all2 (λXr q. fst (proot q) = fst Xr ∧
          irel_sat (snd Xr) (snd (proot q)) i) (drop (Suc c) rhs) (drop (Suc c) pts)›
      using kids by (rule list_all2_dropI)
    have wf_sfx: ‹∀q ∈ set (drop (Suc c) pts). wf_ptree G q›
      using wf_kids by (meson in_set_dropD)
    have first_c: ‹?suf ≠ [] ⟹ ∃σ. (fst (hd ?suf), σ)
          ∈ set (fscan (ffix G) (nullables G) (drop (Suc c) (snd (A, rhs))))
          ∧ csat σ (snd (hd ?suf)) i›
    proof -
      assume ne: ‹?suf ≠ []›
      obtain a cl V where sf: ‹?suf = (a, cl) # V› using ne by (cases ?suf) auto
      from kids_first[OF kids_sfx wf_sfx sf] show ?thesis using sf by simp
    qed
    have null_c: ‹?suf = [] ⟹
        list_all (λ(X, r). nsym (nullables G) X) (drop (Suc c) (snd (A, rhs)))›
    proof -
      assume e: ‹?suf = []›
      then have ‹concat (map pyield (drop (Suc c) pts)) = []› unfolding tcols_def by simp
      from kids_null[OF kids_sfx wf_sfx this] show ?thesis by simp
    qed
    have ctx_c: ‹nctx G L (hd istkc) ?pt ?tr Xsc ?rest_c›
      unfolding nctx_def
    proof (intro conjI allI impI)
      show ‹slot_ok (xclosure_auto G (hd Xsc)) (fst (proot ?pt)) (snd (proot ?pt))›
        by (rule slot_c)
    next
      fix B jc pts' assume pt_eq: ‹?pt = PNode B jc pts'›
      have tr_c: ‹mtrace G ?pt ?tr› using kids_tr c_lt by (auto simp: list_all2_conv_all_nth)
      from mtrace_node_last[OF tr_c[unfolded pt_eq]] obtain brhs trs' where
          tr_eq: ‹?tr = concat trs' @ [DReduce (B, brhs)]›
        and brhs: ‹(B, brhs) ∈ set (iprods G)› by blast
      have nxt: ‹fst (snd (A, rhs) ! c) = Nt B› using kid_c pt_eq by simp
      have sat: ‹irel_sat (snd (snd (A, rhs) ! c)) jc i› using kid_c pt_eq by simp
      from xclosure_auto_slot[OF item_c c_rhs nxt brhs i_c sat]
      obtain R' where R': ‹((B, brhs), 0, R') ∈ set (xclosure_auto G (hd Xsc))›
        and jcR': ‹jc ∈ irep_set R'› by blast
      have cell_kid: ‹cell_ok L (hd istkc) (B, brhs) 0 ?rest_c jc›
        by (rule cell_ok_child[OF tab cell_c c_rhs nxt brhs _ sat refl first_c null_c]) simp
      show ‹∃pr R0. ?tr ≠ [] ∧ last ?tr = DReduce pr ∧
          (pr, 0, R0) ∈ set (xclosure_auto G (hd Xsc)) ∧ jc ∈ irep_set R0 ∧
          cell_ok L (hd istkc) pr 0 ?rest_c jc›
        using tr_eq R' jcR' cell_kid by auto
    qed
    from IH[OF c_lt wf_c Xsc_ne ok_c ctx_c] obtain RA where
        jc_RA: ‹snd (proot ?pt) ∈ irep_set RA›
      and drv_kid: ‹mdrive G gt sts L ?tr ((Xsc, tcols (pyield ?pt) @ ?rest_c), istkc)›
      and run_kid: ‹imrun G gt sts ?tr ((Xsc, tcols (pyield ?pt) @ ?rest_c), istkc) =
          Some ((lgoto (xclosure_auto G (hd Xsc)) (fst (proot ?pt)) RA # Xsc, ?rest_c),
                dnext gt sts (hd istkc) (fst (proot ?pt)) # istkc)› by blast
    let ?F = ‹lgoto (xclosure_auto G (hd Xsc)) (fst (proot ?pt)) RA›
    let ?j = ‹dnext gt sts (hd istkc) (fst (proot ?pt))›
    have yield_split: ‹tcols (concat (map pyield (drop c pts))) @ rest =
        tcols (pyield ?pt) @ ?rest_c›
      using c_lt by (simp add: Cons_nth_drop_Suc[symmetric])
    have take_Suc: ‹concat (take (Suc c) trs) = concat (take c trs) @ ?tr›
      using c_lt len_tr by (simp add: take_Suc_conv_app_nth)
    have run': ‹imrun G gt sts (concat (take (Suc c) trs))
        ((Xs, tcols (concat (map pyield pts)) @ rest), istk) = Some ((?F # Xsc, ?rest_c), ?j # istkc)›
      by (simp only: take_Suc imrun_append run_c option.case yield_split run_kid)
    have drv': ‹mdrive G gt sts L (concat (take (Suc c) trs))
        ((Xs, tcols (concat (map pyield pts)) @ rest), istk)›
      unfolding take_Suc by (rule mdrive_append[OF drv_c run_c drv_kid[unfolded yield_split[symmetric]]])
    have item': ‹((A, rhs), Suc c, irep_inter Rc (irep_pre (snd (snd (A, rhs) ! c)) RA))
        ∈ set ?F›
      using lgoto_memI[OF item_c, of ‹fst (proot ?pt)› RA] c_rhs kid_c by simp
    have i': ‹i ∈ irep_set (irep_inter Rc (irep_pre (snd (snd (A, rhs) ! c)) RA))›
      using i_c jc_RA kid_c by auto
    have F_ne: ‹?F ≠ []› using item' by auto
    have x0: ‹Xsc ! 0 = hd Xsc› and iq0: ‹istkc ! 0 = hd istkc›
      using Xsc_ne istkc_ne by (simp_all add: hd_conv_nth)
    have push: ‹didx_ok G sts (?F # Xsc) (?j # istkc)›
      using didx_ok_push[OF tab ok_c, of 0 ‹fst (proot ?pt)› RA] Xsc_ne F_ne x0 iq0 by simp
    ― ‹the cell moves with the index›
    have i_lt_c: ‹hd istkc < length sts›
      by (rule didx_ok_creach(1)[OF ok_c Xsc_ne item_c i_c])
    have core_c: ‹((A, rhs), c) ∈ set (creach G (sts ! hd istkc))›
      by (rule didx_ok_creach(2)[OF ok_c Xsc_ne item_c i_c])
    have dn: ‹?j = la_next gt sts (hd istkc) (fst (snd (A, rhs) ! c))›
      using dnext_resolve(3)[OF tab i_lt_c core_c c_rhs] kid_c by simp
    have cell': ‹cell_ok L ?j (A, rhs) (Suc c) rest i›
      unfolding dn by (rule cell_ok_step[OF tab cell_c c_rhs])
    have item'': ‹((A, rhs), Suc c, irep_inter Rc (irep_pre (snd (snd (A, rhs) ! c)) RA))
        ∈ set (xclosure_auto G ?F)›
      using item' xclosure_auto_kernel_sub[of ?F G] by blast
    show ?case
      by (intro exI[of _ ‹?F # Xsc›] exI[of _ ‹?j # istkc›]
                exI[of _ ‹irep_inter Rc (irep_pre (snd (snd (A, rhs) ! c)) RA)›])
         (use run' drv' drop_c len_c dropi_c leni_c push item'' i' cell' in simp)
  qed
qed

lemma mtrace_mdrive:
  assumes tab: ‹tables_ok G Shn sts gt L›
  shows ‹mtrace G pt acts ⟹ wf_ptree G pt ⟹ Xs ≠ [] ⟹ didx_ok G sts Xs istk ⟹
     nctx G L (hd istk) pt acts Xs rest ⟹
     ∃RA. snd (proot pt) ∈ irep_set RA ∧
       mdrive G gt sts L acts ((Xs, tcols (pyield pt) @ rest), istk) ∧
       imrun G gt sts acts ((Xs, tcols (pyield pt) @ rest), istk) =
         Some ((lgoto (xclosure_auto G (hd Xs)) (fst (proot pt)) RA # Xs, rest),
               dnext gt sts (hd istk) (fst (proot pt)) # istk)›
proof (induction arbitrary: Xs istk rest rule: mtrace.induct)
  case (mt_leaf t)
  let ?c = ‹s_col (token.span t)›
  let ?RA = ‹FinRep [?c]›
  have istk_ne: ‹istk ≠ []› using mt_leaf.prems(2,3) by (auto dest: didx_ok_len)
  have w: ‹tcols (pyield (PLeaf t)) @ rest = (tok t, ?c) # rest›
    unfolding tcols_def by simp
  have ms: ‹mstep G (Xs, (tok t, ?c) # rest) DShift =
      Some (lgoto (xclosure_auto G (hd Xs)) (Tm (tok t)) ?RA # Xs, rest)›
    unfolding mstep_def mstep_cached_def using mt_leaf.prems(2) by (simp add: hd_map)
  have im: ‹imstep G gt sts ((Xs, (tok t, ?c) # rest), istk) DShift =
      Some ((lgoto (xclosure_auto G (hd Xs)) (Tm (tok t)) ?RA # Xs, rest),
            dnext gt sts (hd istk) (Tm (tok t)) # istk)›
    unfolding imstep_def by (simp add: ms)
  have slot: ‹slot_ok (xclosure_auto G (hd Xs)) (Tm (tok t)) ?c›
    using nctx_slot[OF mt_leaf.prems(4)] by simp
  have live: ‹dlive (fst ((lgoto (xclosure_auto G (hd Xs)) (Tm (tok t)) ?RA # Xs, rest),
      dnext gt sts (hd istk) (Tm (tok t)) # istk))›
    using slot_ok_dlive[OF slot, of ?RA] by simp
  have drv: ‹mdrive G gt sts L [DShift] ((Xs, (tok t, ?c) # rest), istk)›
    by (rule mdrive_ConsI[OF im live _ mdrive_Nil]) simp
  show ?case
    by (intro exI[of _ ?RA]) (use drv im w in simp)
next
  case (mt_node A rhs i pts trs)
  note prod = mt_node.hyps(1) and kids = mt_node.hyps(2)
  note wf = mt_node.prems(1) and Xs_ne = mt_node.prems(2)
    and ok0 = mt_node.prems(3) and ctx = mt_node.prems(4)
  have kids_tr: ‹list_all2 (mtrace G) pts trs›
    using mt_node.IH by (auto simp: list_all2_conv_all_nth)
  have len_pr: ‹length pts = length rhs› using kids by (simp add: list_all2_lengthD)
  have len_tr: ‹length trs = length pts› using kids_tr by (simp add: list_all2_lengthD)
  have wf_kids: ‹∀q ∈ set pts. wf_ptree G q›
    using wf by (auto elim!: wf_ptree.cases simp: list_all2_conv_all_nth set_conv_nth)
  have IH: ‹⋀c Xs' istk' rest'. c < length pts ⟹ wf_ptree G (pts ! c) ⟹ Xs' ≠ [] ⟹
       didx_ok G sts Xs' istk' ⟹ nctx G L (hd istk') (pts ! c) (trs ! c) Xs' rest' ⟹
       ∃RA. snd (proot (pts ! c)) ∈ irep_set RA ∧
         mdrive G gt sts L (trs ! c) ((Xs', tcols (pyield (pts ! c)) @ rest'), istk') ∧
         imrun G gt sts (trs ! c) ((Xs', tcols (pyield (pts ! c)) @ rest'), istk') =
           Some ((lgoto (xclosure_auto G (hd Xs')) (fst (proot (pts ! c))) RA # Xs', rest'),
                 dnext gt sts (hd istk') (fst (proot (pts ! c))) # istk')›
    using mt_node.IH by (auto simp: list_all2_conv_all_nth)
  have istk0_ne: ‹istk ≠ []› using Xs_ne ok0 by (auto dest: didx_ok_len)
  have slot0: ‹slot_ok (xclosure_auto G (hd Xs)) (Nt A) i›
    using nctx_slot[OF ctx] by simp
  from nctx_node[OF ctx] obtain pr R0 where
      last_pr: ‹last (concat trs @ [DReduce (A, rhs)]) = DReduce pr›
    and item0': ‹(pr, 0, R0) ∈ set (xclosure_auto G (hd Xs))› and i0: ‹i ∈ irep_set R0›
    and cell0': ‹cell_ok L (hd istk) pr 0 rest i› by blast
  have pr_eq: ‹pr = (A, rhs)› using last_pr by simp
  note item0 = item0'[unfolded pr_eq] and cell0 = cell0'[unfolded pr_eq]
  from mtrace_mdrive_kids[OF tab kids kids_tr wf_kids IH Xs_ne ok0 item0 i0 cell0 order.refl]
  obtain Xsn istkn Rn where
      run_n: ‹imrun G gt sts (concat trs) ((Xs, tcols (concat (map pyield pts)) @ rest), istk) =
        Some ((Xsn, rest), istkn)›
    and drv_n: ‹mdrive G gt sts L (concat trs)
        ((Xs, tcols (concat (map pyield pts)) @ rest), istk)›
    and drop_n: ‹drop (length pts) Xsn = Xs› and len_n: ‹length Xsn = length pts + length Xs›
    and dropi_n: ‹drop (length pts) istkn = istk›
    and leni_n: ‹length istkn = length pts + length istk›
    and ok_n: ‹didx_ok G sts Xsn istkn›
    and item_n: ‹((A, rhs), length pts, Rn) ∈ set (xclosure_auto G (hd Xsn))›
    and i_n: ‹i ∈ irep_set Rn›
    and cell_n: ‹cell_ok L (hd istkn) (A, rhs) (length pts) rest i›
    using len_tr by auto
  have Xsn_ne: ‹Xsn ≠ []› using len_n Xs_ne by auto
  have istkn_ne: ‹istkn ≠ []› using Xsn_ne ok_n by (auto dest: didx_ok_len)
  have k_lt: ‹length rhs < length Xsn› using len_n len_pr Xs_ne by simp
  let ?RS = ‹red_set (xclosure_auto G (hd Xsn)) (A, rhs)›
  have RS_i: ‹i ∈ irep_set ?RS›
    using item_n i_n len_pr by (auto simp: red_set_correct)
  then have RS_ne: ‹irep_nonempty ?RS› by auto
  have nth_n: ‹Xsn ! length rhs = hd Xs›
    using drop_n len_pr Xs_ne by (metis hd_drop_conv_nth k_lt)
  have ki_lt: ‹length rhs < length istkn› using leni_n len_pr istk0_ne by simp
  have dropi_n': ‹drop (length rhs) istkn = istk› using dropi_n len_pr by simp
  have nthi_n: ‹istkn ! length rhs = hd istk›
    using dropi_n' istk0_ne by (metis hd_drop_conv_nth ki_lt)
  have red: ‹mstep G (Xsn, rest) (DReduce (A, rhs)) =
      Some (lgoto (xclosure_auto G (hd Xs)) (Nt A) ?RS # Xs, rest)›
    unfolding mstep_def mstep_cached_def using k_lt RS_ne Xsn_ne nth_n drop_n len_pr
    by (simp add: Let_def hd_map)
  have imred: ‹imstep G gt sts ((Xsn, rest), istkn) (DReduce (A, rhs)) =
      Some ((lgoto (xclosure_auto G (hd Xs)) (Nt A) ?RS # Xs, rest),
            dnext gt sts (hd istk) (Nt A) # istk)›
    unfolding imstep_def by (simp add: red nthi_n dropi_n')
  have live: ‹dlive (fst ((lgoto (xclosure_auto G (hd Xs)) (Nt A) ?RS # Xs, rest),
      dnext gt sts (hd istk) (Nt A) # istk))›
    using slot_ok_dlive[OF slot0 RS_i] by simp
  have in_lt: ‹hd istkn < length sts›
    by (rule didx_ok_creach(1)[OF ok_n Xsn_ne item_n i_n])
  have cell_n': ‹cell_ok L (hd istkn) (A, rhs) (length (snd (A, rhs))) rest i›
    using cell_n len_pr by simp
  have lic: ‹lic_at G L sts ((Xsn, rest), istkn) (A, rhs)›
    unfolding lic_at_def using in_lt cell_ok_dlic[OF cell_n' RS_i] by simp
  have drv_red: ‹mdrive G gt sts L [DReduce (A, rhs)] ((Xsn, rest), istkn)›
    by (rule mdrive_ConsI[OF imred live _ mdrive_Nil]) (use lic in simp)
  have drv_all: ‹mdrive G gt sts L (concat trs @ [DReduce (A, rhs)])
      ((Xs, tcols (concat (map pyield pts)) @ rest), istk)›
    by (rule mdrive_append[OF drv_n run_n drv_red])
  have run_all: ‹imrun G gt sts (concat trs @ [DReduce (A, rhs)])
      ((Xs, tcols (concat (map pyield pts)) @ rest), istk) =
        Some ((lgoto (xclosure_auto G (hd Xs)) (Nt A) ?RS # Xs, rest),
              dnext gt sts (hd istk) (Nt A) # istk)›
    by (simp only: imrun_append run_n option.case imrun.simps imred)
  show ?case
    by (intro exI[of _ ?RS]) (use drv_all run_all RS_i in simp)
qed

subsection ‹The root context, and completeness of const‹dparse››



lemma slot_ok_xinit: ‹slot_ok (xclosure_auto G (xinit G Shn)) (Nt (istart G)) (istart_ind G)›
proof -
  have ‹(start_prod G Shn, 0, FinRep [istart_ind G]) ∈ set (xclosure_auto G (xinit G Shn))›
    using xclosure_auto_kernel_sub[of ‹xinit G Shn› G]
    unfolding xinit_def start_prod_def by auto
  then show ?thesis
    by (rule slot_okI) (simp_all add: start_prod_def)
qed

text ‹At the root, the context is the start item's dot-0 slot of the initial
  frame with the root cell; the trace then drives the machine from the
  initial configuration to the accepting one.›

lemma mtrace_root:
  assumes wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and tr: ‹mtrace G pt acts›
  shows ‹∃RA. istart_ind G ∈ irep_set RA ∧
    mdrive G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (la_fix G Shn) acts
      (([xinit G Shn], tcols (pyield pt)), [st_find (pr0_states G Shn) (lr0_start G Shn)]) ∧
    imrun G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) acts
      (([xinit G Shn], tcols (pyield pt)), [st_find (pr0_states G Shn) (lr0_start G Shn)]) =
      Some ((lgoto (xclosure_auto G (xinit G Shn)) (Nt (istart G)) RA # [xinit G Shn], []),
            dnext (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
              (st_find (pr0_states G Shn) (lr0_start G Shn)) (Nt (istart G))
            # [st_find (pr0_states G Shn) (lr0_start G Shn)])›
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)›
  have tab: ‹tables_ok G Shn ?sts ?gt ?L› by (rule tables_ok_concrete)
  obtain pts where pt: ‹pt = PNode (istart G) (istart_ind G) pts›
    using rt by (cases pt) auto
  from mtrace_node_last[OF tr[unfolded pt]] obtain rhs trs where
      acts_eq: ‹acts = concat trs @ [DReduce (istart G, rhs)]›
    and prod: ‹(istart G, rhs) ∈ set (iprods G)› by blast
  have xinit_item: ‹((start_prod G Shn, 0, FinRep [istart_ind G])) ∈ set (xclosure_auto G (xinit G Shn))›
    using xclosure_auto_kernel_sub[of ‹xinit G Shn› G] unfolding xinit_def start_prod_def by auto
  have ctx: ‹nctx G ?L ?i0 pt acts [xinit G Shn] []›
    unfolding nctx_def
  proof (intro conjI allI impI)
    show ‹slot_ok (xclosure_auto G (hd [xinit G Shn])) (fst (proot pt)) (snd (proot pt))›
      using slot_ok_xinit rt by simp
  next
    fix A j pts' assume ‹pt = PNode A j pts'›
    then have A: ‹A = istart G› and j: ‹j = istart_ind G› using pt by auto
    from xclosure_auto_slot[OF xinit_item _ _ prod, of ‹istart_ind G› ‹istart_ind G›]
    obtain R' where R': ‹((istart G, rhs), 0, R') ∈ set (xclosure_auto G (xinit G Shn))›
      and jR': ‹istart_ind G ∈ irep_set R'› unfolding start_prod_def by auto
    have cell: ‹cell_ok ?L ?i0 (istart G, rhs) 0 [] (istart_ind G)›
      by (rule cell_ok_root[OF tab refl prod]) simp
    show ‹∃pr R0. acts ≠ [] ∧ last acts = DReduce pr ∧
        (pr, 0, R0) ∈ set (xclosure_auto G (hd [xinit G Shn])) ∧ j ∈ irep_set R0 ∧
        cell_ok ?L ?i0 pr 0 [] j›
      using acts_eq R' jR' cell j by auto
  qed
  have ne: ‹[xinit G Shn] ≠ []› by simp
  have ok0: ‹didx_ok G ?sts [xinit G Shn] [?i0]› by (rule didx_ok_init[OF tab])
  have ctx': ‹nctx G ?L (hd [?i0]) pt acts [xinit G Shn] []› using ctx by simp
  from mtrace_mdrive[OF tab tr wf ne ok0 ctx'] show ?thesis using rt by simp
qed

lemma mdrive_root:
  assumes wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and tr: ‹mtrace G pt acts›
  shows ‹mdrive G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (la_fix G Shn) acts
           (([xinit G Shn], tcols (pyield pt)), [st_find (pr0_states G Shn) (lr0_start G Shn)])›
  using mtrace_root[OF wf rt tr] by blast

theorem mtrace_completes:
  assumes wf: ‹wf_ptree G pt› and tr: ‹mtrace G pt acts›
    and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
  shows ‹mcompletes G Shn acts ([xinit G Shn], tcols (pyield pt))›
proof -
  from mtrace_root[OF wf rt tr] obtain RA where
      i0: ‹istart_ind G ∈ irep_set RA›
    and run': ‹imrun G (pgtab G (pr0_states G Shn)) (pr0_states G Shn) acts
      (([xinit G Shn], tcols (pyield pt)), [st_find (pr0_states G Shn) (lr0_start G Shn)]) =
      Some ((lgoto (xclosure_auto G (xinit G Shn)) (Nt (istart G)) RA # [xinit G Shn], []),
            dnext (pgtab G (pr0_states G Shn)) (pr0_states G Shn)
              (st_find (pr0_states G Shn) (lr0_start G Shn)) (Nt (istart G))
            # [st_find (pr0_states G Shn) (lr0_start G Shn)])› by blast
  have run: ‹mrun G acts ([xinit G Shn], tcols (pyield pt)) =
      Some (lgoto (xclosure_auto G (xinit G Shn)) (Nt (istart G)) RA # [xinit G Shn], [])›
    using imrun_mrun[OF run'] by simp
  have xinit_item: ‹((start_prod G Shn, 0, FinRep [istart_ind G])) ∈ set (xclosure_auto G (xinit G Shn))›
    using xclosure_auto_kernel_sub[of ‹xinit G Shn› G] unfolding xinit_def start_prod_def by auto
  have fin_item: ‹((start_prod G Shn, Suc 0,
      irep_inter (FinRep [istart_ind G]) (irep_pre Eq RA)))
      ∈ set (lgoto (xclosure_auto G (xinit G Shn)) (Nt (istart G)) RA)›
    using lgoto_memI[OF xinit_item, of ‹Nt (istart G)› RA] unfolding start_prod_def by simp
  have ‹gfinal G Shn (lgoto (xclosure_auto G (xinit G Shn)) (Nt (istart G)) RA # [xinit G Shn], [])›
    unfolding gfinal_def using fin_item i0
    by (auto simp: list_ex_iff start_prod_def intro!: bexI[where x = ‹(start_prod G Shn, Suc 0,
      irep_inter (FinRep [istart_ind G]) (irep_pre Eq RA))›])
  then show ?thesis unfolding mcompletes_def run by simp
qed

theorem dparse_complete:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
  shows ‹∃t. dparse G Shn (pyield pt) = Some t ∧
             ast_of G (Nt (istart G)) (istart_ind G) t (pyield pt)›
proof -
  from mtrace_ex[OF wf] obtain acts where tr: ‹mtrace G pt acts› by blast
  show ?thesis
    by (rule dparse_complete_of_mdrive[OF fn det mdrive_root[OF wf rt tr] mtrace_completes[OF wf tr rt]])
qed

corollary dparse_complete_lang:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn› and w: ‹w ∈ ilang G›
  shows ‹∃t. dparse G Shn w = Some t ∧ ast_of G (Nt (istart G)) (istart_ind G) t w›
proof -
  from w have ‹infG G ⊢ [Nt (istart G, istart_ind G)] ⇒* map Tm (tcols w)›
    unfolding ilang_derives .
  from iffD1[OF derives_iff_ptree this] obtain pt where
      wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and y: ‹pyield pt = w› by blast
  from dparse_complete[OF fn det wf rt] show ?thesis unfolding y .
qed

corollary dparse_iff_lang:
  assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn›
  shows ‹dparse G Shn w ≠ None ⟷ w ∈ ilang G›
proof
  assume ‹dparse G Shn w ≠ None›
  then obtain t where ‹dparse G Shn w = Some t› by auto
  from dparse_sound[OF fn this] show ‹w ∈ ilang G› .
next
  assume ‹w ∈ ilang G›
  from dparse_complete_lang[OF fn det this] show ‹dparse G Shn w ≠ None› by auto
qed


section ‹Summary›

text ‹const‹dparse› is sound unconditionally and complete under
  const‹fresh_name› and const‹mdet›:
  ▪ text‹dparse_sound_ast› / text‹dparse_sound›
  ▪ text‹dparse_complete› / text‹dparse_complete_lang›
  ▪ text‹dparse_iff_lang›: ‹dparse G Shn w ≠ None ⟷ w ∈ ilang G›

  The static sufficient condition for const‹mdet› from a conflict
  report is the subject of
  text‹LR_Det›; the backend text‹LR_Parser› uses
  const‹dparse› through text‹dparse_via_tables›.

  Compare Barthwal's soundness and completeness theorems for her SLR parser
  cite‹‹Thms.~5.4.3--5.4.4› in "barthwal2010-thesis-cfl-hol4"› and those of
  Jourdan, Pottier and Leroy for validated LR(1) automata
  cite‹‹Thms.~1 and~3› in "jourdan2012-validating-lr1"›.  Barthwal's
  theorems both assume that the SLR conflict check passed, and Jourdan et
  al.'s soundness, like text‹dparse_sound›, assumes nothing about the
  automaton.  Their completeness assumes a validator check and enough fuel;
  completeness here assumes const‹mdet› and needs no fuel.›


end