Theory LR

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

theory LR
  imports TIGER_Grammar_Model.Indentation_Sensitive "HOL-Library.While_Combinator" "HOL-Library.RBT"
    "HOL-Library.IArray"
begin

section ‹Fuel-free GLR steps›

text ‹
  The table layer: the LR(0) automaton over the cores of the ‹k = 0›
  frames, the column-relative first table, and per-item LALR(1) lookahead
  cells relating the token's column to the item's anchor.  The cells stand
  in for the lookahead tuples of cite‹‹Sect.~5.6› in "adams2013"›: the parser of
  text‹LR_Driver› is LALR(1)-style, not the canonical LR(1) instance of
  cite‹‹Alg.~8› in "adams2013"›; text‹LR_Det› shows that the cells cover its lookahead.

  The GLR machine of text‹Indentation_Sensitive› section 5 is a
  checker whose steps carry explicit closure fuel.  This section removes the
  fuel by searching for the least sufficient one, which exists by
  text‹xcls_stable_ex›.
›

subsection ‹The least satisfying number, executably›

text ‹The least ‹n› with ‹P n›, by const‹while_option›; defined
  whenever a witness exists.  Every fuelled fixpoint of this theory uses it.›

definition nat_search :: ‹(nat ⇒ bool) ⇒ nat› where
  ‹nat_search P = the (while_option (λn. ¬ P n) Suc 0)›

lemma nat_search_Some:
  assumes ‹P k›
  shows ‹while_option (λn. ¬ P n) Suc 0 = Some (nat_search P)›
proof -
  have ‹n ≤ k ⟹ ¬ P n ⟹ Suc n ≤ k ∧ k - Suc n < k - n› for n
    using assms by (cases ‹n = k›) auto
  then obtain t where t: ‹while_option (λn. ¬ P n) Suc 0 = Some t›
    using measure_while_option_Some[of ‹λn. n ≤ k› ‹λn. ¬ P n› Suc ‹λn. k - n› 0]
    by auto
  then show ?thesis
    by (simp add: nat_search_def)
qed

lemma nat_search_sat:
  assumes ‹P k›
  shows ‹P (nat_search P)›
  using while_option_stop[OF nat_search_Some[of P, OF assms]] by simp

subsection ‹Fuel-free closure›

definition xfuel :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat› where
  ‹xfuel G xs = nat_search (λt. xstable G xs (xiter G xs t))›

definition xclosure_auto :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list› where
  ‹xclosure_auto G xs = xclosure G (xfuel G xs) xs›

lemma xfuel_stable: ‹xstable G xs (xiter G xs (xfuel G xs))›
proof -
  obtain fuel where ‹xstable G xs (xiter G xs fuel)›
    using xcls_stable_ex by blast
  from nat_search_sat[of ‹λt. xstable G xs (xiter G xs t)›, OF this]
  show ?thesis by (simp add: xfuel_def)
qed

text ‹Executably, the rounds are iterated once, each computed once: the search
  for the fuel would recompute them from scratch for every candidate.›

lemma xclosure_auto_code [code]:
  ‹xclosure_auto G xs = xslots G xs (fst (the (while_option
     (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
     (xiter G xs 0, xround G xs (xiter G xs 0)))))›
proof -
  obtain k where ‹xstable G xs (xiter G xs k)›
    using xcls_stable_ex by blast
  then have ‹while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0 = Some (xfuel G xs)›
    unfolding xfuel_def by (rule nat_search_Some)
  moreover have
    ‹map_option (λt. (xiter G xs t, xiter G xs (Suc t)))
       (while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0) =
     while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
       (xiter G xs 0, xiter G xs (Suc 0))›
    by (rule while_option_commute
        [where f = ‹λt. (xiter G xs t, xiter G xs (Suc t))› and s = 0])
      (simp_all add: xstable_def)
  ultimately have
    ‹Some (xiter G xs (xfuel G xs), xiter G xs (Suc (xfuel G xs))) =
     while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
       (xiter G xs 0, xround G xs (xiter G xs 0))›
    by simp
  from this[symmetric] show ?thesis
    by (simp add: xclosure_auto_def xclosure_def)
qed

subsection ‹Acceptance›

text ‹Acceptance condition on a configuration: the post-const‹grun›
  condition of const‹gaccepts›; the driver of text‹LR_Driver›
  uses it.›

definition gfinal :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) gconfig ⇒ bool› where
  ‹gfinal G Shn gc ⟷ (case gc of (Ys, v) ⇒ v = [] ∧ Ys ≠ [] ∧
      list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧
                irep_mem (istart_ind G) R) (hd Ys))›

section ‹LR(0) core tabulation›

text ‹
  The indentation sets of items are input-dependent; their
  ∗‹cores› (production and dot) are not: const‹xgoto› advances dots
  regardless of the goto label, and const‹xclosure› adds one
  dot-text‹0› slot per production unconditionally.  So the finitely many
  reachable cores can be tabulated at grammar-declaration time, giving the
  state skeleton for LR(k) tables and conflict reporting; the runtime
  indentation sets refine it per input.
›


text ‹After Knuth cite‹‹Sect.~II, Steps~1 and~3› in "knuth1965-lr-translation"› (the state sets), DeRemer and
  Pennello cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"› (the LR(0) automaton ‹(K, Next, Reduce)›) and
  Barthwal cite‹‹Sect.~5.5.1, Def.~5.5.4› in "barthwal2010-thesis-cfl-hol4"› (the worklist ‹visit›, with the
  unseen part of the finite universe as measure).›
subsection ‹Cores of frames›

type_synonym ('n, 't) citem = ‹('n × ('n, 't) rhs) × nat›

definition ccore :: ‹('n, 't) xitem list ⇒ ('n, 't) citem list› where
  ‹ccore xs = remdups (map (λ(pr, m, R). (pr, m)) xs)›

definition cgoto :: ‹('n, 't) citem list ⇒ ('n, 't) sym ⇒ ('n, 't) citem list› where
  ‹cgoto cs X = remdups (map (λ(pr, m). (pr, Suc m))
     (filter (λ(pr, m). m < length (snd pr) ∧ fst (snd pr ! m) = X) cs))›

definition cclosure :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
  ‹cclosure G cs = remdups (cs @ map (λpr. (pr, 0)) (iprods G))›

subsection ‹The finite universe of cores›

definition start_prod :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 'n × ('n, 't) rhs› where
  ‹start_prod G Shn = (Shn, [(Nt (istart G), Eq)])›

definition cuniv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem set› where
  ‹cuniv G Shn = (SIGMA pr : insert (start_prod G Shn) (set (iprods G)).
     {..length (snd pr)})›

lemma finite_cuniv: ‹finite (cuniv G Shn)›
  unfolding cuniv_def by (intro finite_SigmaI) auto

lemma cgoto_cclosure_univ:
  assumes ‹set s ⊆ cuniv G Shn›
  shows ‹set (cgoto (cclosure G s) X) ⊆ cuniv G Shn›
proof
  fix c assume ‹c ∈ set (cgoto (cclosure G s) X)›
  then obtain pr m where c: ‹c = (pr, Suc m)› and m: ‹m < length (snd pr)›
    and mem: ‹(pr, m) ∈ set s ∪ (λpr. (pr, 0)) ` set (iprods G)›
    unfolding cgoto_def cclosure_def by auto
  have ‹pr ∈ insert (start_prod G Shn) (set (iprods G))›
    using mem assms unfolding cuniv_def by auto
  then show ‹c ∈ cuniv G Shn›
    using m unfolding c cuniv_def by auto
qed

definition gram_syms :: ‹('n, 't) is_cfg ⇒ ('n, 't) syms› where
  ‹gram_syms G =
     remdups (Nt (istart G) # concat (map (λ(A, rhs). map fst rhs) (iprods G)))›

subsection ‹Worklist subset construction›

text ‹States are core lists, compared up to their sets; text‹cinserts› adds
  the successors not yet seen.›

fun cinserts :: ‹('n, 't) citem list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) citem list list› where
  ‹cinserts seen [] acc = acc›
| ‹cinserts seen (t # ts) acc =
     (if list_ex (λu. set u = set t) (seen @ acc)
      then cinserts seen ts acc
      else cinserts seen ts (t # acc))›

lemma cinserts_superset: ‹set acc ⊆ set (cinserts seen ts acc)›
  by (induction seen ts acc rule: cinserts.induct) auto

lemma cinserts_elems:
  ‹set (cinserts seen ts acc) ⊆ set ts ∪ set acc›
  by (induction seen ts acc rule: cinserts.induct) auto

lemma cinserts_covers:
  ‹t ∈ set ts ⟹ ∃u ∈ set (seen @ cinserts seen ts acc). set u = set t›
proof (induction seen ts acc rule: cinserts.induct)
  case (2 seen t' ts acc)
  show ?case
  proof (cases ‹t = t'›)
    case True
    show ?thesis
    proof (cases ‹list_ex (λu. set u = set t') (seen @ acc)›)
      case True
      then obtain u where u: ‹u ∈ set (seen @ acc)› and ‹set u = set t'›
        by (auto simp: list_ex_iff)
      then have ‹u ∈ set (seen @ cinserts seen ts acc)›
        using cinserts_superset by fastforce
      then show ?thesis using ‹set u = set t'› ‹t = t'› True by auto
    next
      case False
      have ‹t' ∈ set (cinserts seen ts (t' # acc))›
        using cinserts_superset by fastforce
      then show ?thesis using False ‹t = t'› by auto
    qed
  next
    case False
    with "2.prems" have t: ‹t ∈ set ts› by simp
    show ?thesis
    proof (cases ‹list_ex (λu. set u = set t') (seen @ acc)›)
      case True
      from "2.IH"(1)[OF True t] show ?thesis using True by simp
    next
      case False
      from "2.IH"(2)[OF False t] show ?thesis using False by simp
    qed
  qed
qed simp

lemma cinserts_distinct:
  ‹distinct (map set (seen @ acc)) ⟹
   distinct (map set (seen @ cinserts seen ts acc))›
proof (induction seen ts acc rule: cinserts.induct)
  case (2 seen t ts acc)
  show ?case
  proof (cases ‹list_ex (λu. set u = set t) (seen @ acc)›)
    case True
    then show ?thesis using "2.IH"(1) "2.prems" by simp
  next
    case False
    have ‹distinct (map set (seen @ t # acc))›
      using "2.prems" False by (auto simp: list_ex_iff image_iff)
    then show ?thesis using "2.IH"(2) False by simp
  qed
qed simp

subsection ‹The worklist subset construction, generic in the closure›

text ‹The subset construction as a worklist over states (lists of cores),
  parametrised by the closure ‹cl› taken before each goto:
  const‹cclosure› for the LR(0) automaton text‹lr0_states›,
  text‹creach› for the precise automaton text‹pr0_states› of
  text‹LR_Det›.  The invariant and the termination measure only need
  that a goto through the closure stays inside const‹cuniv›.  The
  const‹while_option› scaffold is shared with the cell saturation below.›

lemma while_option_the_inv:
  fixes f :: ‹'s ⇒ nat›
  assumes init: ‹P s0›
    and step: ‹⋀s. P s ⟹ b s ⟹ P (c s) ∧ f (c s) < f s›
  shows ‹P (the (while_option b c s0)) ∧ ¬ b (the (while_option b c s0))›
proof -
  obtain t where t: ‹while_option b c s0 = Some t›
    using measure_while_option_Some[where P = P and b = b and c = c and s = s0 and f = f]
      init step by blast
  have ‹P t›
    by (rule while_option_rule[where P = P, OF _ t init]) (use step in blast)
  with while_option_stop[OF t] show ?thesis by (simp add: t)
qed

definition wl_step :: ‹('n, 't) is_cfg ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
    ('n, 't) citem list list × ('n, 't) citem list list ⇒
    ('n, 't) citem list list × ('n, 't) citem list list› where
  ‹wl_step G cl = (λ(visited, work). case work of
      [] ⇒ (visited, [])
    | s # ws ⇒ (s # visited,
        cinserts (s # visited) (map (cgoto (cl s)) (gram_syms G)) ws))›

definition wl_inv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
    ('n, 't) citem set set ⇒
    ('n, 't) citem list list × ('n, 't) citem list list ⇒ bool› where
  ‹wl_inv G Shn cl S0 = (λ(visited, work).
     distinct (map set (visited @ work)) ∧
     (∀s ∈ set (visited @ work). set s ⊆ cuniv G Shn) ∧
     S0 ⊆ set ` set (visited @ work) ∧
     (∀s ∈ set visited. ∀X ∈ set (gram_syms G).
        ∃t ∈ set (visited @ work). set t = set (cgoto (cl s) X)))›

lemma wl_step_inv:
  assumes univ: ‹⋀s X. set s ⊆ cuniv G Shn ⟹ set (cgoto (cl s) X) ⊆ cuniv G Shn›
    and inv: ‹wl_inv G Shn cl S0 (visited, work)› and ne: ‹work ≠ []›
  shows ‹wl_inv G Shn cl S0 (wl_step G cl (visited, work))›
proof -
  obtain s ws where work: ‹work = s # ws› using ne by (cases work) auto
  define succs where ‹succs = map (cgoto (cl s)) (gram_syms G)›
  define nw where ‹nw = cinserts (s # visited) succs ws›
  have res: ‹wl_step G cl (visited, work) = (s # visited, nw)›
    unfolding wl_step_def work succs_def nw_def by simp
  have dst: ‹distinct (map set (visited @ work))›
    and unv: ‹∀u ∈ set (visited @ work). set u ⊆ cuniv G Shn›
    and s0: ‹S0 ⊆ set ` set (visited @ work)›
    and cov: ‹∀u ∈ set visited. ∀X ∈ set (gram_syms G).
        ∃t ∈ set (visited @ work). set t = set (cgoto (cl u) X)›
    using inv unfolding wl_inv_def by auto
  have dst': ‹distinct (map set ((s # visited) @ nw))›
    unfolding nw_def
    by (rule cinserts_distinct) (use dst work in auto)
  have sub: ‹set (visited @ work) ⊆ set ((s # visited) @ nw)›
    using cinserts_superset[of ws ‹s # visited› succs]
    unfolding nw_def work by auto
  have unv': ‹∀u ∈ set ((s # visited) @ nw). set u ⊆ cuniv G Shn›
  proof
    fix u assume ‹u ∈ set ((s # visited) @ nw)›
    then consider ‹u ∈ set (visited @ work)› | ‹u ∈ set succs›
      using cinserts_elems[of ‹s # visited› succs ws] work
      unfolding nw_def by auto
    then show ‹set u ⊆ cuniv G Shn›
    proof cases
      case 1 then show ?thesis using unv by blast
    next
      case 2
      then obtain X where ‹u = cgoto (cl s) X›
        unfolding succs_def by auto
      then show ?thesis
        using univ unv work by fastforce
    qed
  qed
  have s0': ‹S0 ⊆ set ` set ((s # visited) @ nw)›
    by (rule subset_trans[OF s0 image_mono[OF sub]])
  have cov': ‹∀u ∈ set (s # visited). ∀X ∈ set (gram_syms G).
      ∃t ∈ set ((s # visited) @ nw). set t = set (cgoto (cl u) X)›
  proof (intro ballI)
    fix u X assume u: ‹u ∈ set (s # visited)› and X: ‹X ∈ set (gram_syms G)›
    show ‹∃t ∈ set ((s # visited) @ nw). set t = set (cgoto (cl u) X)›
    proof (cases ‹u = s›)
      case True
      have ‹cgoto (cl s) X ∈ set succs›
        using X unfolding succs_def by auto
      from cinserts_covers[OF this, of ‹s # visited› ws]
      show ?thesis unfolding nw_def True by auto
    next
      case False
      with u have ‹u ∈ set visited› by simp
      from cov[rule_format, OF this X] obtain t where
        ‹t ∈ set (visited @ work)› and ‹set t = set (cgoto (cl u) X)›
        by blast
      then show ?thesis using sub by blast
    qed
  qed
  show ?thesis unfolding res wl_inv_def
    using dst' unv' s0' cov' by simp
qed

lemma wl_step_card:
  assumes inv: ‹wl_inv G Shn cl S0 (visited, work)› and ne: ‹work ≠ []›
  shows ‹card (set ` set (fst (wl_step G cl (visited, work))))
       = Suc (card (set ` set visited))›
proof -
  obtain s ws where work: ‹work = s # ws› using ne by (cases work) auto
  have ‹set s ∉ set ` set visited›
    using inv unfolding wl_inv_def work by (auto simp: image_iff)
  moreover have ‹finite (set ` set visited)› by simp
  ultimately show ?thesis
    unfolding wl_step_def work by (simp add: Let_def)
qed

definition lr0_start :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list› where
  ‹lr0_start G Shn = [(start_prod G Shn, 0)]›

definition lr0_init :: ‹('n, 't) is_cfg ⇒ 'n ⇒
    ('n, 't) citem list list × ('n, 't) citem list list› where
  ‹lr0_init G Shn = ([], [lr0_start G Shn, []])›

lemma wl_inv_init:
  ‹wl_inv G Shn cl {set (lr0_start G Shn), {}} (lr0_init G Shn)›
  unfolding wl_inv_def lr0_init_def lr0_start_def cuniv_def start_prod_def
  by auto

definition wl_states :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
    ('n, 't) citem list list› where
  ‹wl_states G Shn cl =
     fst (the (while_option (λ(v, w). w ≠ []) (wl_step G cl) (lr0_init G Shn)))›

lemma wl_states_inv:
  assumes univ: ‹⋀s X. set s ⊆ cuniv G Shn ⟹ set (cgoto (cl s) X) ⊆ cuniv G Shn›
  shows ‹wl_inv G Shn cl {set (lr0_start G Shn), {}} (wl_states G Shn cl, [])›
proof -
  let ?P = ‹wl_inv G Shn cl {set (lr0_start G Shn), {}}›
  let ?t = ‹the (while_option (λ(v, w). w ≠ []) (wl_step G cl) (lr0_init G Shn))›
  have ‹?P ?t ∧ ¬ (case ?t of (v, w) ⇒ w ≠ [])›
  proof (rule while_option_the_inv[where P = ?P and b = ‹λ(v, w). w ≠ []›
        and c = ‹wl_step G cl› and f = ‹λ(v, w). card (Pow (cuniv G Shn)) - card (set ` set v)›])
    show ‹?P (lr0_init G Shn)› by (rule wl_inv_init)
  next
    fix st assume inv: ‹?P st› and b: ‹case st of (v, w) ⇒ w ≠ []›
    obtain v w where st: ‹st = (v, w)› by (cases st)
    have card_lt: ‹card (set ` set v) < card (Pow (cuniv G Shn))›
    proof -
      have ‹set ` set (fst (wl_step G cl (v, w))) ⊆ Pow (cuniv G Shn)›
        using wl_step_inv[OF univ inv[unfolded st] b[unfolded st, simplified]]
        unfolding wl_inv_def by (cases ‹wl_step G cl (v, w)›) auto
      then have ‹card (set ` set (fst (wl_step G cl (v, w)))) ≤ card (Pow (cuniv G Shn))›
        by (intro card_mono) (simp add: finite_cuniv)
      then show ?thesis
        using wl_step_card[OF inv[unfolded st] b[unfolded st, simplified]] by simp
    qed
    show ‹?P (wl_step G cl st) ∧
        (case wl_step G cl st of (v, w) ⇒ card (Pow (cuniv G Shn)) - card (set ` set v))
        < (case st of (v, w) ⇒ card (Pow (cuniv G Shn)) - card (set ` set v))›
      using wl_step_inv[OF univ inv[unfolded st]] wl_step_card[OF inv[unfolded st]] b card_lt
      unfolding st by (cases ‹wl_step G cl (v, w)›) auto
  qed
  then show ?thesis unfolding wl_states_def by (cases ?t) auto
qed

subsection ‹The LR(0) automaton›

definition lr0_states :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list› where
  ‹lr0_states G Shn = wl_states G Shn (cclosure G)›

lemma ccore_xinit: ‹set (ccore (xinit G Shn)) = set (lr0_start G Shn)›
  unfolding ccore_def xinit_def lr0_start_def start_prod_def by simp

subsection ‹Reachable closure and conflict reporting›

text ‹const‹cclosure› adds a dot-text‹0› slot for every production
  (dead slots carry empty typ‹indrep›s at runtime), so at core level an
  text‹ε›-production looks completed in every state.  Conflict diagnostics
  need the classic ∗‹reachable› closure: only productions of nonterminals
  that occur after a dot.  One production can be added per round, so
  term‹length (iprods G)› rounds saturate.

  This is the ‹Closure› of DeRemer and Pennello
  cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"› and the closure of Knuth's Step~1
  cite‹‹Sect.~II, Eq.~(18)› in "knuth1965-lr-translation"› without its lookahead strings.›

definition creach_step :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
  ‹creach_step G cs = remdups (cs @ concat (map (λpr.
       if list_ex (λ(pr', m). m < length (snd pr') ∧ fst (snd pr' ! m) = Nt (fst pr)) cs
       then [(pr, 0)] else []) (iprods G)))›

definition creach :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
  ‹creach G cs = (creach_step G ^^ Suc (length (iprods G))) cs›

text ‹Evaluated as defined, const‹creach› takes all the rounds its fuel allows, one
  per production, for every state; the code equation stops at the first round that
  changes nothing.›

fun fuel_fix :: ‹('a ⇒ 'a) ⇒ nat ⇒ 'a ⇒ 'a› where
  ‹fuel_fix f n x = (if n = 0 then x else let y = f x in if y = x then x else fuel_fix f (n - 1) y)›

declare fuel_fix.simps [simp del]

lemma fuel_fix_funpow: ‹fuel_fix f n x = (f ^^ n) x›
proof (induction f n x rule: fuel_fix.induct)
  case (1 f n x)
  show ?case
  proof (cases n)
    case 0
    then show ?thesis by (simp add: fuel_fix.simps)
  next
    case (Suc m)
    show ?thesis
    proof (cases ‹f x = x›)
      case True
      then have ‹(f ^^ k) x = x› for k by (induction k) simp_all
      with True Suc show ?thesis by (simp add: fuel_fix.simps)
    next
      case False
      have ‹fuel_fix f n x = fuel_fix f m (f x)›
        using Suc False by (subst fuel_fix.simps) simp
      also have ‹… = (f ^^ m) (f x)›
        using 1 Suc False by simp
      also have ‹… = (f ^^ n) x›
        using Suc by (simp add: funpow_swap1)
      finally show ?thesis .
    qed
  qed
qed

lemma creach_code [code]:
  ‹creach G cs = fuel_fix (creach_step G) (Suc (length (iprods G))) cs›
  unfolding creach_def fuel_fix_funpow ..

lemma creach_step_mono: ‹set cs ⊆ set (creach_step G cs)›
  unfolding creach_step_def by auto

lemma creach_funpow_mono: ‹set cs ⊆ set ((creach_step G ^^ k) cs)›
proof (induction k arbitrary: cs)
  case (Suc k)
  have ‹set cs ⊆ set (creach_step G cs)› by (rule creach_step_mono)
  also have ‹… ⊆ set ((creach_step G ^^ k) (creach_step G cs))› by (rule Suc.IH)
  finally show ?case by (simp add: funpow_swap1)
qed simp

lemma creach_superset: ‹set cs ⊆ set (creach G cs)›
  unfolding creach_def by (rule creach_funpow_mono)

lemma creach_step_sound:
  ‹set (creach_step G cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
  unfolding creach_step_def by (auto split: if_splits)

lemma creach_funpow_sound:
  ‹set ((creach_step G ^^ k) cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
proof (induction k arbitrary: cs)
  case (Suc k)
  have ‹set ((creach_step G ^^ Suc k) cs)
      = set ((creach_step G ^^ k) (creach_step G cs))›
    by (simp add: funpow_swap1)
  also have ‹… ⊆ set (creach_step G cs) ∪ (λpr. (pr, 0)) ` set (iprods G)›
    by (rule Suc.IH)
  also have ‹… ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
    using creach_step_sound by fastforce
  finally show ?case .
qed simp

lemma creach_sound:
  ‹set (creach G cs) ⊆ set (cclosure G cs)›
proof -
  have ‹set (creach G cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
    unfolding creach_def by (rule creach_funpow_sound)
  also have ‹… = set (cclosure G cs)›
    unfolding cclosure_def by auto
  finally show ?thesis .
qed

subsection ‹Cores stay in the universe›

text ‹Goto and closure keep cores inside const‹cuniv›, and all next symbols of
  cores in const‹cuniv› are in const‹gram_syms›.›

lemma cgoto_memI:
  ‹(pr, m) ∈ set cs ⟹ m < length (snd pr) ⟹ fst (snd pr ! m) = X ⟹ (pr, Suc m) ∈ set (cgoto cs X)›
  unfolding cgoto_def by force

lemma cgoto_set_mono: ‹set cs ⊆ set cs' ⟹ set (cgoto cs X) ⊆ set (cgoto cs' X)›
  unfolding cgoto_def by auto

lemma cclosure_univ:
  ‹set cs ⊆ cuniv G Shn ⟹ set (cclosure G cs) ⊆ cuniv G Shn›
  unfolding cclosure_def cuniv_def by auto

lemma creach_univ:
  assumes ‹set s ⊆ cuniv G Shn›
  shows ‹set (creach G s) ⊆ cuniv G Shn›
  using creach_sound[of G s] cclosure_univ[OF assms] by blast

lemma gram_syms_iprods:
  ‹(A, rhs) ∈ set (iprods G) ⟹ m < length rhs ⟹ fst (rhs ! m) ∈ set (gram_syms G)›
  unfolding gram_syms_def by force

lemma cuniv_next_gram_syms:
  assumes ‹(pr, m) ∈ cuniv G Shn› and ‹m < length (snd pr)›
  shows ‹fst (snd pr ! m) ∈ set (gram_syms G)›
proof -
  from assms(1) consider ‹pr = start_prod G Shn› | ‹pr ∈ set (iprods G)›
    unfolding cuniv_def by auto
  then show ?thesis
  proof cases
    case 1
    then show ?thesis using assms(2) unfolding start_prod_def gram_syms_def by simp
  next
    case 2
    then show ?thesis using gram_syms_iprods[of ‹fst pr› ‹snd pr› G m] assms(2) by simp
  qed
qed

section ‹Column-relative first sets: LR(k) lookahead, phase 1›

text ‹
  Deterministic LR parsing of an II-CFG needs ∗‹column-relative›
  lookahead: a spine ends where the next token's column says so, not where
  its class does. A lookahead entry is a token class paired with a
  typ‹cirel› relating the token's column to the indentation of the item
  that carries it. The executable first-set layer:

    ▪ text‹cwiden›: composed relations widened into a four-element class
      universe, keeping the fixpoints finite. Over-approximating is the safe
      direction throughout: lookahead only prunes reduce actions;
    ▪ text‹nullables›: executable nullability, complete against the
      derivations of the infinite grammar const‹infG›;
    ▪ text‹ffix›: the first-token table, one saturation fixpoint,
      complete against the derivations of const‹infG›: every first token
      an annotated right-hand side derives is found, with a relation its
      column satisfies (‹fscan_complete› below).

  A nonterminal ‹A› is nullable in cite‹‹Def.~1› in "adams2013"› if
  ‹Ai ⇒* ε› for all ‹i›; ‹nullables_complete› asks for a derivation at
  one indentation only.  The first table is Knuth's ‹Hk›
  cite‹‹Sect.~II› in "knuth1965-lr-translation"› at ‹k = 1›, with a column
  relation on each token.  As in Jourdan et al.
  cite‹‹Sect.~3.3› in "jourdan2012-validating-lr1"›, first and nullable are least
  fixpoints of the standard equations; here they are computed, not checked as part of a
  certificate.
›

subsection ‹Widening composed relations›

text ‹By cite‹‹Lemma~2› in "adams2013"› a composition of relations is one of six
  classes, but ‹>n› and ‹>n⋆› carry a number, so there are
  infinitely many.  ‹cwiden› keeps four: ‹>n› becomes
  ‹>1› (or ‹≥› when ‹n = 0›) and ‹>n⋆› becomes
  ‹⋆›.  Lemma~2 is exact; the widening only weakens
  (‹csat_cwiden›).›

fun cwiden :: ‹cirel ⇒ cirel› where
  ‹cwiden (CGt n) = (if n = 0 then CGe else CGt 1)›
| ‹cwiden (CGtAny n) = CAny›
| ‹cwiden c = c›

lemma csat_cwiden: ‹csat c k i ⟹ csat (cwiden c) k i›
  by (cases c) auto

lemma cwiden_range: ‹cwiden c ∈ {CEq, CGe, CGt 1, CAny}›
  by (cases c) auto

subsection ‹Bounded saturation of monotone list fixpoints›

text ‹A set-extensional, monotone step that stays inside a finite universe
  saturates within term‹card U› rounds.›

lemma funpow_saturates:
  fixes f :: ‹'a list ⇒ 'a list› and U :: ‹'a set›
  assumes ext: ‹⋀xs ys. set xs = set ys ⟹ set (f xs) = set (f ys)›
    and mono: ‹⋀xs. set xs ⊆ set (f xs)›
    and inU: ‹⋀xs. set xs ⊆ U ⟹ set (f xs) ⊆ U›
    and fin: ‹finite U›
    and istart: ‹set xs0 ⊆ U›
    and N: ‹card U ≤ N›
  shows ‹set (f ((f ^^ N) xs0)) = set ((f ^^ N) xs0)›
proof -
  have iterU: ‹set ((f ^^ k) xs0) ⊆ U› for k
    by (induction k) (use istart inU in auto)
  show ?thesis
  proof (cases ‹∃k < N. set (f ((f ^^ k) xs0)) = set ((f ^^ k) xs0)›)
    case True
    then obtain k where k: ‹k < N›
      and st: ‹set (f ((f ^^ k) xs0)) = set ((f ^^ k) xs0)› by blast
    have stab: ‹set ((f ^^ (k + d)) xs0) = set ((f ^^ k) xs0)› for d
    proof (induction d)
      case (Suc d)
      have ‹set ((f ^^ (k + Suc d)) xs0) = set (f ((f ^^ (k + d)) xs0))›
        by simp
      also have ‹… = set (f ((f ^^ k) xs0))›
        by (rule ext[OF Suc.IH])
      finally show ?case using st by simp
    qed simp
    have NN: ‹set ((f ^^ N) xs0) = set ((f ^^ k) xs0)›
      using stab[of ‹N - k›] k by simp
    then show ?thesis using ext[OF NN] st by simp
  next
    case False
    have grow: ‹k ≤ N ⟹ k ≤ card (set ((f ^^ k) xs0))› for k
    proof (induction k)
      case (Suc k)
      have ne: ‹set (f ((f ^^ k) xs0)) ≠ set ((f ^^ k) xs0)›
        using False Suc.prems by auto
      have ‹set ((f ^^ k) xs0) ⊂ set (f ((f ^^ k) xs0))›
        using mono ne by blast
      then have ‹card (set ((f ^^ k) xs0)) < card (set (f ((f ^^ k) xs0)))›
        by (intro psubset_card_mono)
           (use inU[OF iterU[of k]] fin finite_subset in auto)
      then show ?case using Suc by simp
    qed simp
    have ‹N ≤ card (set ((f ^^ N) xs0))› using grow by simp
    moreover have ‹card (set ((f ^^ N) xs0)) ≤ card U›
      by (intro card_mono fin iterU)
    ultimately have ‹card (set ((f ^^ N) xs0)) = card U› using N by simp
    then have full: ‹set ((f ^^ N) xs0) = U›
      by (intro card_subset_eq fin iterU)
    have ‹set (f ((f ^^ N) xs0)) ⊆ U›
      by (rule inU[OF iterU])
    then show ?thesis using full mono[of ‹(f ^^ N) xs0›] by auto
  qed
qed


subsection ‹Saturation bounded by the increment, not the universe›

lemma funpow_saturates_delta:
  fixes f :: ‹'a list ⇒ 'a list› and D :: ‹'a set›
  assumes ext: ‹⋀xs ys. set xs = set ys ⟹ set (f xs) = set (f ys)›
    and mono: ‹⋀xs. set xs ⊆ set (f xs)›
    and delta: ‹⋀xs. set (f xs) ⊆ set xs ∪ D›
    and fin: ‹finite D›
    and N: ‹card D ≤ N›
  shows ‹set (f ((f ^^ N) xs0)) = set ((f ^^ N) xs0)›
proof -
  have chain: ‹set ((f ^^ k) xs0) ⊆ set ((f ^^ Suc k) xs0)› for k
    using mono by simp
  have incr: ‹set xs0 ⊆ set ((f ^^ k) xs0)› for k
    by (induction k) (use chain in auto)
  have inD: ‹set ((f ^^ k) xs0) ⊆ set xs0 ∪ D› for k
    by (induction k) (use delta in auto)
  show ?thesis
  proof (cases ‹∃k < N. set (f ((f ^^ k) xs0)) = set ((f ^^ k) xs0)›)
    case True
    then obtain k where k: ‹k < N›
      and st: ‹set (f ((f ^^ k) xs0)) = set ((f ^^ k) xs0)› by blast
    have stab: ‹set ((f ^^ (k + d)) xs0) = set ((f ^^ k) xs0)› for d
    proof (induction d)
      case (Suc d)
      have ‹set ((f ^^ (k + Suc d)) xs0) = set (f ((f ^^ (k + d)) xs0))›
        by (simp add: funpow_swap1)
      also have ‹… = set (f ((f ^^ k) xs0))› by (rule ext[OF Suc.IH])
      also have ‹… = set ((f ^^ k) xs0)› by (rule st)
      finally show ?case .
    qed simp
    have ‹set ((f ^^ N) xs0) = set ((f ^^ k) xs0)›
      using stab[of ‹N - k›] k by simp
    then show ?thesis using st ext by metis
  next
    case False
    ― ‹no early fixed point: each of the first ‹N› steps strictly grows,
        so the increment exhausts term‹D››
    have strict: ‹k < N ⟹ set ((f ^^ k) xs0) ⊂ set ((f ^^ Suc k) xs0)› for k
      using False chain by (simp add: psubset_eq) blast
    have card_ge: ‹k ≤ N ⟹ k ≤ card (set ((f ^^ k) xs0) - set xs0)› for k
    proof (induction k)
      case (Suc k)
      have fk: ‹finite (set ((f ^^ k) xs0) - set xs0)› by simp
      have sub: ‹set ((f ^^ k) xs0) - set xs0 ⊂ set ((f ^^ Suc k) xs0) - set xs0›
        using strict[of k] Suc.prems incr[of k] by auto
      have ‹k ≤ card (set ((f ^^ k) xs0) - set xs0)› using Suc by simp
      moreover have ‹card (set ((f ^^ k) xs0) - set xs0)
            < card (set ((f ^^ Suc k) xs0) - set xs0)›
        by (rule psubset_card_mono) (use sub in auto)
      ultimately show ?case by simp
    qed simp
    have dsub: ‹set ((f ^^ N) xs0) - set xs0 ⊆ D› using inD by auto
    have ‹N ≤ card (set ((f ^^ N) xs0) - set xs0)› by (rule card_ge) simp
    moreover have ‹card (set ((f ^^ N) xs0) - set xs0) ≤ card D›
      by (rule card_mono[OF fin dsub])
    ultimately have eqD: ‹set ((f ^^ N) xs0) - set xs0 = D›
      using N card_subset_eq[OF fin dsub] by simp
    have ‹set (f ((f ^^ N) xs0)) ⊆ set ((f ^^ N) xs0)›
      using delta[of ‹(f ^^ N) xs0›] eqD by auto
    with mono show ?thesis by blast
  qed
qed
subsection ‹Executable nullability›

definition nsym :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
  ‹nsym ns X = (case X of Nt B ⇒ B ∈ set ns | Tm _ ⇒ False)›

definition nstep :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 'n list› where
  ‹nstep G ns = remdups (map fst (filter (λ(A, rhs).
      list_all (λ(X, r). nsym ns X) rhs) (iprods G)) @ ns)›

definition nullables :: ‹('n, 't) is_cfg ⇒ 'n list› where
  ‹nullables G = (nstep G ^^ Suc (length (remdups (map fst (iprods G))))) []›

text ‹The code stops at the fixpoint, which comes after a few steps, not one per
  nonterminal.›

lemma nullables_code [code]:
  ‹nullables G = fuel_fix (nstep G) (Suc (length (remdups (map fst (iprods G))))) []›
  unfolding nullables_def fuel_fix_funpow ..

lemma nsym_ext: ‹set ns = set ns' ⟹ nsym ns X = nsym ns' X›
  unfolding nsym_def by (cases X) auto

lemma nstep_ext:
  ‹set ns = set ns' ⟹ set (nstep G ns) = set (nstep G ns')›
  unfolding nstep_def using nsym_ext[of ns ns']
  by (auto simp: list_all_iff case_prod_beta)

lemma nstep_mono: ‹set ns ⊆ set (nstep G ns)›
  unfolding nstep_def by auto

lemma nstep_inU:
  ‹set ns ⊆ fst ` set (iprods G) ⟹ set (nstep G ns) ⊆ fst ` set (iprods G)›
  unfolding nstep_def by force

lemma nullables_stable:
  ‹set (nstep G (nullables G)) = set (nullables G)›
  unfolding nullables_def
proof (rule funpow_saturates[where U = ‹fst ` set (iprods G)›])
  show ‹⋀xs ys. set xs = set ys ⟹ set (nstep G xs) = set (nstep G ys)›
    by (rule nstep_ext)
  show ‹⋀xs. set xs ⊆ set (nstep G xs)›
    by (rule nstep_mono)
  show ‹⋀xs. set xs ⊆ fst ` set (iprods G) ⟹
      set (nstep G xs) ⊆ fst ` set (iprods G)›
    by (rule nstep_inU)
  show ‹finite (fst ` set (iprods G))› by simp
  show ‹set [] ⊆ fst ` set (iprods G)› by simp
  show ‹card (fst ` set (iprods G)) ≤ Suc (length (remdups (map fst (iprods G))))›
    by (metis card_set eq_imp_le le_SucI set_map)
qed

lemma nullables_closed:
  assumes ‹(A, rhs) ∈ set (iprods G)›
    and ‹list_all (λ(X, r). nsym (nullables G) X) rhs›
  shows ‹A ∈ set (nullables G)›
proof -
  have ‹A ∈ set (nstep G (nullables G))›
    unfolding nstep_def using assms by force
  then show ?thesis using nullables_stable by fastforce
qed

text ‹
  Completeness against const‹infG›, through the erased grammar: a
  derivation of text‹eps› erases to one of
  term‹set (derel (iprods G))›, where nullability is the library's
  const‹Nullable›, and the fixpoint above is closed under its introduction
  rule.
›

lemma nsym_nullables:
  assumes ‹Nullable (set (derel (iprods G))) X›
  shows ‹nsym (nullables G) X›
  using assms
proof (induction rule: Nullable.induct)
  case (NullableSym A w)
  from NullableSym.hyps obtain rhs where p: ‹(A, rhs) ∈ set (iprods G)›
    and w: ‹w = map fst rhs› unfolding derel_def by auto
  have ‹list_all (λ(X, r). nsym (nullables G) X) rhs›
    using NullableSym.IH unfolding w by (auto simp: list_all_iff case_prod_beta)
  from nullables_closed[OF p this] show ?case by (simp add: nsym_def)
qed

lemma nullables_complete:
  assumes ‹(infG G) ⊢ [Nt (B, j)] ⇒(n) []›
  shows ‹B ∈ set (nullables G)›
proof -
  have ‹set (derel (iprods G)) ⊢ [Nt B] ⇒* []›
    using derives_unann[OF relpowp_imp_rtranclp[OF assms]] by simp
  from nsym_nullables[OF nullable_if[OF this]] show ?thesis
    by (simp add: nsym_def)
qed

subsection ‹The first-token table›

text ‹A flat table of triples: nonterminal, token class, and the widened
  relation of the token's column to the nonterminal's own indentation.›

type_synonym ('n, 't) ftab = ‹('n × 't × cirel) list›

definition flook :: ‹('n, 't) ftab ⇒ 'n ⇒ ('t × cirel) list› where
  ‹flook tab B = map (λ(_, a, ρ). (a, ρ)) (filter (λ(B', _, _). B' = B) tab)›

lemma flookI: ‹(B, a, ρ) ∈ set tab ⟹ (a, ρ) ∈ set (flook tab B)›
  unfolding flook_def by force

lemma flookD: ‹(a, ρ) ∈ set (flook tab B) ⟹ (B, a, ρ) ∈ set tab›
  unfolding flook_def by auto

fun fscan :: ‹('n, 't) ftab ⇒ 'n list ⇒ ('n, 't) rhs ⇒ ('t × cirel) list› where
  ‹fscan tab ns [] = []›
| ‹fscan tab ns ((X, r) # rest) =
     (case X of
        Tm a ⇒ [(a, cwiden (cirel_of r))]
      | Nt B ⇒ map (λ(a, ρ). (a, cwiden (ccomp (cirel_of r) ρ))) (flook tab B))
     @ (if nsym ns X then fscan tab ns rest else [])›

definition fstep :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab ⇒ ('n, 't) ftab› where
  ‹fstep G tab = remdups (tab @ concat (map (λ(B, rhs).
      map (λ(a, σ). (B, a, σ)) (fscan tab (nullables G) rhs)) (iprods G)))›

definition ffix :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab› where
  ‹ffix G = the (while_option (λtab. length (fstep G tab) ≠ length tab)
      (fstep G) [])›

definition funiv :: ‹('n, 't) is_cfg ⇒ ('n × 't × cirel) set› where
  ‹funiv G = fst ` set (iprods G) × set (gram_terms G) × {CEq, CGe, CGt 1, CAny}›

lemma finite_funiv: ‹finite (funiv G)›
  unfolding funiv_def by auto

lemma fscan_inU:
  assumes tab: ‹set tab ⊆ funiv G›
    and terms: ‹⋀a r. (Tm a, r) ∈ set rhs ⟹ a ∈ set (gram_terms G)›
    and mem: ‹(a, σ) ∈ set (fscan tab ns rhs)›
  shows ‹a ∈ set (gram_terms G) ∧ σ ∈ {CEq, CGe, CGt 1, CAny}›
  using terms mem
proof (induction rhs)
  case Nil
  then show ?case by simp
next
  case (Cons Xr rest)
  obtain X r where Xr: ‹Xr = (X, r)› by (cases Xr)
  from Cons.prems(2) consider
      (head) ‹(a, σ) ∈ set (case X of
          Tm b ⇒ [(b, cwiden (cirel_of r))]
        | Nt B ⇒ map (λ(b, ρ). (b, cwiden (ccomp (cirel_of r) ρ))) (flook tab B))›
    | (tail) ‹(a, σ) ∈ set (fscan tab ns rest)›
    unfolding Xr by (auto split: if_splits)
  then show ?case
  proof cases
    case head
    show ?thesis
    proof (cases X)
      case (Tm b)
      then show ?thesis
        using head Cons.prems(1)[of b r] cwiden_range Xr by auto
    next
      case (Nt B)
      from head obtain ρ where ‹(a, ρ) ∈ set (flook tab B)›
        and σ: ‹σ = cwiden (ccomp (cirel_of r) ρ)›
        unfolding Nt by auto
      from flookD[OF this(1)] have ‹(B, a, ρ) ∈ set tab› .
      then have ‹a ∈ set (gram_terms G)›
        using tab unfolding funiv_def by auto
      then show ?thesis using cwiden_range σ by auto
    qed
  next
    case tail
    then show ?thesis using Cons.IH Cons.prems(1) by fastforce
  qed
qed

lemma fstep_mono: ‹set tab ⊆ set (fstep G tab)›
  unfolding fstep_def by auto

lemma fstep_inU:
  assumes ‹set tab ⊆ funiv G›
  shows ‹set (fstep G tab) ⊆ funiv G›
proof
  fix x assume ‹x ∈ set (fstep G tab)›
  then consider ‹x ∈ set tab›
    | B rhs a σ where ‹(B, rhs) ∈ set (iprods G)›
        and ‹(a, σ) ∈ set (fscan tab (nullables G) rhs)› and ‹x = (B, a, σ)›
    unfolding fstep_def by fastforce
  then show ‹x ∈ funiv G›
  proof cases
    case 1
    then show ?thesis using assms by blast
  next
    case 2
    have ‹a ∈ set (gram_terms G) ∧ σ ∈ {CEq, CGe, CGt 1, CAny}›
      using fscan_inU[OF assms _ 2(2)] gram_termsI[OF 2(1)] by blast
    then show ?thesis
      using 2 unfolding funiv_def by force
  qed
qed

lemma fstep_distinct: ‹distinct (fstep G tab)›
  unfolding fstep_def by simp

text ‹Saturation loops: iterate until the (always distinct) table stops
  growing.›

lemma while_table_saturates_from:
  fixes step :: ‹'x list ⇒ 'x list› and U :: ‹'x set›
  assumes mono: ‹⋀tab. set tab ⊆ set (step tab)›
    and dst: ‹⋀tab. distinct (step tab)›
    and inU: ‹⋀tab. set tab ⊆ U ⟹ set (step tab) ⊆ U›
    and fin: ‹finite U›
    and istart: ‹set tab0 ⊆ U› and dst0: ‹distinct tab0›
  shows ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step tab0 = Some t ∧
         set (step t) = set t ∧ set t ⊆ U›
proof -
  define P where ‹P = (λtab :: 'x list. set tab ⊆ U ∧ distinct tab)›
  define f where ‹f = (λtab :: 'x list. card U - card (set tab))›
  have stepP: ‹P (step tab) ∧ f (step tab) < f tab›
    if Ptab: ‹P tab› and b: ‹length (step tab) ≠ length tab› for tab
  proof -
    have PU: ‹set (step tab) ⊆ U›
      using Ptab inU unfolding P_def by blast
    have cs: ‹card (set (step tab)) = length (step tab)›
      using dst by (simp add: distinct_card)
    have ct: ‹card (set tab) = length tab›
      using Ptab unfolding P_def by (simp add: distinct_card)
    have le: ‹card (set tab) ≤ card (set (step tab))›
      by (intro card_mono) (auto simp: mono)
    have lt: ‹card (set tab) < card (set (step tab))›
      using le b cs ct by simp
    have ltU: ‹card (set tab) < card U›
      using lt card_mono[OF fin PU] by simp
    have ‹f (step tab) < f tab›
      unfolding f_def using lt ltU by (simp add: diff_less_mono2)
    then show ?thesis using PU dst unfolding P_def by simp
  qed
  have P0: ‹P tab0› using istart dst0 unfolding P_def by simp
  have Some: ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step tab0 = Some t›
    by (rule measure_while_option_Some[where P = P and f = f])
       (use stepP P0 in ‹auto simp: P_def›)
  then obtain t where t:
    ‹while_option (λtab. length (step tab) ≠ length tab) step tab0 = Some t› by blast
  have Pt: ‹P t›
    by (rule while_option_rule[OF _ t]) (use stepP P0 in ‹auto simp: P_def›)
  have stop: ‹length (step t) = length t›
    using while_option_stop[OF t] by simp
  have ‹card (set t) = card (set (step t))›
    using stop Pt dst unfolding P_def by (simp add: distinct_card)
  then have ‹set t = set (step t)›
    by (intro card_subset_eq) (auto simp: mono)
  then show ?thesis using t Pt unfolding P_def by auto
qed

lemma while_table_saturates:
  fixes step :: ‹'x list ⇒ 'x list› and U :: ‹'x set›
  assumes ‹⋀tab. set tab ⊆ set (step tab)›
    and ‹⋀tab. distinct (step tab)›
    and ‹⋀tab. set tab ⊆ U ⟹ set (step tab) ⊆ U›
    and ‹finite U›
  shows ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step [] = Some t ∧
         set (step t) = set t ∧ set t ⊆ U›
  by (rule while_table_saturates_from[OF assms]) simp_all

lemma ffix_while:
  ‹∃t. while_option (λtab. length (fstep G tab) ≠ length tab) (fstep G) [] = Some t ∧
   set (fstep G t) = set t ∧ set t ⊆ funiv G›
  by (rule while_table_saturates[OF fstep_mono fstep_distinct fstep_inU finite_funiv])

lemma ffix_stable: ‹set (fstep G (ffix G)) = set (ffix G)›
proof -
  obtain t where t: ‹while_option (λtab. length (fstep G tab) ≠ length tab)
      (fstep G) [] = Some t›
    and st: ‹set (fstep G t) = set t›
    using ffix_while by blast
  show ?thesis unfolding ffix_def t by (simp add: st)
qed

lemma ffix_inU: ‹set (ffix G) ⊆ funiv G›
proof -
  obtain t where t: ‹while_option (λtab. length (fstep G tab) ≠ length tab)
      (fstep G) [] = Some t›
    and U: ‹set t ⊆ funiv G›
    using ffix_while by blast
  show ?thesis unfolding ffix_def t by (simp add: U)
qed

lemma ffix_closed:
  assumes ‹(B, rhs) ∈ set (iprods G)›
    and ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) rhs)›
  shows ‹(B, a, σ) ∈ set (ffix G)›
proof -
  have ‹(B, a, σ) ∈ set (fstep G (ffix G))›
    unfolding fstep_def using assms by force
  then show ?thesis using ffix_stable by blast
qed

subsection ‹Completeness of the first-token table›

lemma fscan_complete:
  assumes ‹(infG G) ⊢ arhs ⇒(n) Tm (a, c) # V›
    and ‹annotates j rhs arhs›
  shows ‹∃σ. (a, σ) ∈ set (fscan (ffix G) (nullables G) rhs) ∧ csat σ c j›
  using assms
proof (induction n arbitrary: rhs arhs j V rule: less_induct)
  case (less n)
  have ‹arhs ≠ []›
    using less.prems(1) deriven_from_empty by fastforce
  then obtain Xr rest where rhs: ‹rhs = Xr # rest›
    using less.prems(2) unfolding annotates_def
    by (cases rhs) auto
  obtain X r where Xr: ‹Xr = (X, r)› by (cases Xr)
  from less.prems(2) obtain Y arest where arhs: ‹arhs = Y # arest›
    and Y: ‹∃j1. Y = annsym (X, j1) ∧ irel_sat r j1 j›
    and annrest: ‹annotates j rest arest›
    unfolding rhs Xr by (cases arhs) (auto simp: annotates_def)
  have ‹(infG G) ⊢ [Y] @ arest ⇒(n) Tm (a, c) # V›
    using less.prems(1) unfolding arhs by simp
  from iffD1[OF deriven_appendD this]
  obtain n1 n2 w1 w2 where n: ‹n = n1 + n2› and w: ‹Tm (a, c) # V = w1 @ w2›
    and d1: ‹(infG G) ⊢ [Y] ⇒(n1) w1›
    and d2: ‹(infG G) ⊢ arest ⇒(n2) w2›
    by blast
  obtain j1 where Yj: ‹Y = annsym (X, j1)› and sat: ‹irel_sat r j1 j›
    using Y by blast
  show ?case
  proof (cases w1)
    case Nil
    have XN: ‹nsym (nullables G) X›
    proof (cases X)
      case (Tm b)
      then show ?thesis using d1 Nil Yj by (fastforce simp: deriven_Tm_Cons)
    next
      case (Nt C)
      have ‹(infG G) ⊢ [Nt (C, j1)] ⇒(n1) []›
        using d1 Yj Nt unfolding Nil by simp
      from nullables_complete[OF this] show ?thesis
        using Nt unfolding nsym_def by simp
    qed
    have n1: ‹n1 ≠ 0› using d1 Nil Yj by (cases n1) auto
    then have n2: ‹n2 < n› using n by simp
    have d2': ‹(infG G) ⊢ arest ⇒(n2) Tm (a, c) # V›
      using d2 w unfolding Nil by simp
    from less.IH[OF n2 d2' annrest]
    obtain σ where ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) rest)›
      and ‹csat σ c j› by blast
    then show ?thesis
      unfolding rhs Xr using XN by auto
  next
    case (Cons y w1')
    have y: ‹y = Tm (a, c)› and V: ‹V = w1' @ w2›
      using w unfolding Cons by auto
    show ?thesis
    proof (cases X)
      case (Tm b)
      have YT: ‹Y = Tm (b, j1)› using Yj Tm by simp
      have ‹w1 = [Tm (b, j1)]›
        using d1[unfolded YT] by (simp add: deriven_Tm_Cons)
      then have ab: ‹a = b› and cj: ‹c = j1›
        using Cons y by auto
      have ‹csat (cirel_of r) c j› using sat cj by simp
      then have ‹csat (cwiden (cirel_of r)) c j› by (rule csat_cwiden)
      then show ?thesis
        unfolding rhs Xr using Tm ab by auto
    next
      case (Nt C)
      have YN: ‹Y = Nt (C, j1)› using Yj Nt by simp
      obtain m1 where n1: ‹n1 = Suc m1›
        using d1 Cons y YN by (cases n1) auto
      from relpowp_Suc_D2[OF d1[unfolded n1 YN]] obtain v where
        st: ‹infG G ⊢ [Nt (C, j1)] ⇒ v›
        and dv: ‹(infG G) ⊢ v ⇒(m1) Tm (a, c) # w1'›
        unfolding Cons y by blast
      from st obtain brhs' where
        pr: ‹((C, j1), brhs') ∈ infG G› and v: ‹v = brhs'›
        by (auto simp: derive_singleton)
      from pr[unfolded infG_alt] obtain brhs where
        brhs: ‹(C, brhs) ∈ set (iprods G)› and annb: ‹annotates j1 brhs brhs'›
        by blast
      have ‹m1 < n› using n n1 by simp
      from less.IH[OF this dv[unfolded v] annb]
      obtain ρ where mem: ‹(a, ρ) ∈ set (fscan (ffix G) (nullables G) brhs)›
        and satρ: ‹csat ρ c j1› by blast
      have inffix: ‹(C, a, ρ) ∈ set (ffix G)›
        by (rule ffix_closed[OF brhs mem])
      have ‹csat (cwiden (ccomp (cirel_of r) ρ)) c j›
      proof -
        have ‹csat (ccomp (cirel_of r) ρ) c j›
          unfolding csat_ccomp using satρ sat by auto
        then show ?thesis by (rule csat_cwiden)
      qed
      then show ?thesis
        unfolding rhs Xr using Nt flookI[OF inffix] by force
    qed
  qed
qed

section ‹LR tables and conflict reports›

text ‹
  The layers on top of the LR(0) automaton and the lookahead tables: the
  canonical per-item LALR cells and the conflict report over them; the
  driver that parses with the cells at runtime follows in
  text‹LR_Driver›.
›

subsection ‹Live frames›

definition live :: ‹('n, 't) xitem list ⇒ bool› where
  ‹live xs = list_ex (λ(pr, m, R). irep_nonempty R) xs›

section ‹Column-aware conflict analysis›

text ‹
  Follow cells relate token columns to the indentations of different
  items, which are pairwise incomparable, so a token-level report could
  compare token classes only. For a sharper check every item
  is related to a ∗‹common anchor›, the indentation label of the goto
  that built the state. Composing these paths needs inverse relations,
  which typ‹cirel› lacks, so the analysis runs in a small
  two-directional class algebra text‹wrel›. That algebra is the verified
  core: embedding, inversion and composition only weaken, and
  text‹wdisjoint› detects only disjoint pairs, so pruning a conflict
  pair is justified.

  Adams cite‹‹Sect.~5.8› in "adams2013"› observes that the items of one state can
  carry different indentation sets, so one set shared by the whole state is not enough.
  The common anchor shares no set: each item keeps its own relation to the anchor.
›

subsection ‹The two-directional class algebra›

datatype wrel = WEq | WGe | WGt | WLe | WLt | WAny

fun wsat :: ‹wrel ⇒ nat ⇒ nat ⇒ bool› where
  ‹wsat WEq k i ⟷ k = i›
| ‹wsat WGe k i ⟷ k ≥ i›
| ‹wsat WGt k i ⟷ k > i›
| ‹wsat WLe k i ⟷ k ≤ i›
| ‹wsat WLt k i ⟷ k < i›
| ‹wsat WAny k i ⟷ True›

fun w_of :: ‹irel ⇒ wrel› where
  ‹w_of Eq = WEq› | ‹w_of Gt = WGt› | ‹w_of Ge = WGe› | ‹w_of Any = WAny›

lemma w_of_sound: ‹irel_sat r k i ⟹ wsat (w_of r) k i›
  by (cases r) auto

fun wemb :: ‹cirel ⇒ wrel› where
  ‹wemb CEq = WEq›
| ‹wemb CGe = WGe›
| ‹wemb (CGt n) = (if n = 0 then WGe else WGt)›
| ‹wemb CAny = WAny›
| ‹wemb (CGtAny n) = WAny›

lemma wemb_sound: ‹csat σ k i ⟹ wsat (wemb σ) k i›
  by (cases σ) auto

fun winv :: ‹wrel ⇒ wrel› where
  ‹winv WEq = WEq› | ‹winv WGe = WLe› | ‹winv WGt = WLt›
| ‹winv WLe = WGe› | ‹winv WLt = WGt› | ‹winv WAny = WAny›

lemma winv_sound: ‹wsat τ k i ⟹ wsat (winv τ) i k›
  by (cases τ) auto

fun wcomp :: ‹wrel ⇒ wrel ⇒ wrel› where
  ‹wcomp WEq τ = τ›
| ‹wcomp τ WEq = τ›
| ‹wcomp WGe WGe = WGe›
| ‹wcomp WGe WGt = WGt›
| ‹wcomp WGt WGe = WGt›
| ‹wcomp WGt WGt = WGt›
| ‹wcomp WLe WLe = WLe›
| ‹wcomp WLe WLt = WLt›
| ‹wcomp WLt WLe = WLt›
| ‹wcomp WLt WLt = WLt›
| ‹wcomp τ1 τ2 = WAny›

lemma wcomp_sound:
  ‹wsat τ2 k j ⟹ wsat τ1 j i ⟹ wsat (wcomp τ1 τ2) k i›
  by (cases τ1; cases τ2) auto

fun wdisjoint :: ‹wrel ⇒ wrel ⇒ bool› where
  ‹wdisjoint WEq τ ⟷ τ = WGt ∨ τ = WLt›
| ‹wdisjoint WGt τ ⟷ τ = WEq ∨ τ = WLt ∨ τ = WLe›
| ‹wdisjoint WLt τ ⟷ τ = WEq ∨ τ = WGt ∨ τ = WGe›
| ‹wdisjoint WLe τ ⟷ τ = WGt›
| ‹wdisjoint WGe τ ⟷ τ = WLt›
| ‹wdisjoint WAny τ ⟷ False›

lemma wdisjoint_sound:
  ‹wsat τ1 c l ⟹ wsat τ2 c l ⟹ ¬ wdisjoint τ1 τ2›
  by (cases τ1; cases τ2) auto

subsection ‹Anchored reachable closures›

text ‹Items with a typ‹wrel› relating the state's incoming goto label to
  the item's left-hand-side indentation.  Kernel items read it off their
  just-dotted symbol; closure children compose through the position's
  relation.  Like const‹creach›, a diagnostic computation.
  This is the technique of cite‹‹Sect.~5.8› in "adams2013"›: indentation information is
  kept for the items before the closure, and an item the closure adds is annotated with the
  relation that leads to it.›

type_synonym ('n, 't) witem = ‹('n × ('n, 't) rhs) × nat × wrel›

definition wkernel :: ‹('n, 't) citem list ⇒ ('n, 't) witem list› where
  ‹wkernel s = map (λ(pr, m). (pr, m,
      if m = 0 then WAny else w_of (snd (snd pr ! (m - 1))))) s›

definition wreach_step :: ‹('n, 't) is_cfg ⇒ ('n, 't) witem list ⇒ ('n, 't) witem list› where
  ‹wreach_step G ws = remdups (ws @ concat (map (λ(pr, m, ρ).
      if m < length (snd pr)
      then (case fst (snd pr ! m) of
             Nt B ⇒ map (λbr. (br, 0,
                       wcomp (winv (w_of (snd (snd pr ! m)))) ρ))
                     (filter (λbr. fst br = B) (iprods G))
           | Tm _ ⇒ [])
      else []) ws))›

definition wreach :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) witem list› where
  ‹wreach G s = (wreach_step G ^^ Suc (length (iprods G) * 6)) (wkernel s)›

lemma wreach_code [code]:
  ‹wreach G s = fuel_fix (wreach_step G) (Suc (length (iprods G) * 6)) (wkernel s)›
  unfolding wreach_def fuel_fix_funpow ..

subsection ‹Anchored shift cells›

text ‹A shift cell relates the token's column to the state's common anchor
  through the dotted terminal's own relation.›

definition shift_cells :: ‹('n, 't) witem list ⇒ ('t × wrel) list› where
  ‹shift_cells ws = concat (map (λ(pr, m, ρ).
      if m < length (snd pr)
      then (case fst (snd pr ! m) of
             Tm a ⇒ [(a, wcomp (winv ρ) (w_of (snd (snd pr ! m))))]
           | Nt _ ⇒ [])
      else []) ws)›

section ‹Canonical per-item lookahead (LALR over the LR(0) automaton)›

text ‹
  A global FOLLOW table would lose the column information at every
  occurrence whose relation is not equality; lookahead is therefore
  computed per item, along the automaton:
  a cell text‹(state, item, token-or-end, τ)› says the token's column
  relates by text‹τ› to that item's own left-hand-side indentation.
  Cells are seeded at the start item, flow through closures (re-anchored
  through the occurrence's relation) and through gotos unchanged, in one
  saturation over the automaton, LALR-style.

  The tokens of the cells of a completed item ‹A → ω› at state ‹q› play the
  role of the set ‹LA(q, A → ω)› of DeRemer and Pennello
  cite‹‹Sect.~3› in "deremer1982-lalr-lookahead"›, each with a column relation.  The
  cells are found by propagation over items until nothing changes, the approach of the
  algorithms that cite‹‹Sect.~6.3› in "deremer1982-lalr-lookahead"› compares against,
  not by their ‹Digraph› over nonterminal transitions.
›

definition anch :: ‹'n × ('n, 't) rhs ⇒ nat ⇒ wrel› where
  ‹anch pr m = (if m = 0 then WAny else w_of (snd (snd pr ! (m - 1))))›

definition st_find :: ‹('n, 't) citem list list ⇒ ('n, 't) citem list ⇒ nat› where
  ‹st_find sts t = (case filter (λj. set (sts ! j) = set t) [0..<length sts]
     of [] ⇒ length sts | j # _ ⇒ j)›

text ‹Evaluated as defined, const‹st_find› indexes the list once per state, which is
  quadratic; the code equation walks it once.›

fun st_find_from :: ‹('n, 't) citem list list ⇒ ('n, 't) citem list ⇒ nat ⇒ nat› where
  ‹st_find_from [] t k = k›
| ‹st_find_from (s # ss) t k = (if set s = set t then k else st_find_from ss t (Suc k))›

lemma st_find_from_eq:
  ‹st_find_from ss t k = (case filter (λj. set (ss ! j) = set t) [0..<length ss]
     of [] ⇒ k + length ss | j # _ ⇒ k + j)›
proof (induction ss arbitrary: k)
  case Nil
  then show ?case by simp
next
  case (Cons s ss)
  have up: ‹[0..<length (s # ss)] = 0 # map Suc [0..<length ss]›
    by (simp only: length_Cons upt_conv_Cons[OF zero_less_Suc] map_Suc_upt)
  show ?case
  proof (cases ‹set s = set t›)
    case True
    then show ?thesis unfolding up by simp
  next
    case False
    have f: ‹filter (λj. set ((s # ss) ! j) = set t) [0..<length (s # ss)]
        = map Suc (filter (λj. set (ss ! j) = set t) [0..<length ss])›
      using False unfolding up by (simp add: filter_map comp_def)
    show ?thesis
      using False Cons.IH[of ‹Suc k›] unfolding f by (simp split: list.splits)
  qed
qed

lemma st_find_code [code]: ‹st_find sts t = st_find_from sts t 0›
  unfolding st_find_def st_find_from_eq by (simp split: list.splits)

lemma st_find_le: ‹st_find sts t ≤ length sts›
proof (cases ‹filter (λj. set (sts ! j) = set t) [0..<length sts]›)
  case Nil
  then show ?thesis unfolding st_find_def by simp
next
  case (Cons j rest)
  have ‹j ∈ set (filter (λj. set (sts ! j) = set t) [0..<length sts])›
    unfolding Cons by simp
  then have ‹j < length sts› by simp
  then show ?thesis unfolding st_find_def Cons by simp
qed

lemma st_find_found:
  assumes ‹t ∈ set sts› and ‹set t = set s›
  shows ‹st_find sts s < length sts ∧ set (sts ! st_find sts s) = set s›
proof -
  obtain j where j: ‹j < length sts› and tj: ‹sts ! j = t› using assms(1) by (metis in_set_conv_nth)
  have ‹j ∈ set (filter (λj. set (sts ! j) = set s) [0..<length sts])› using j tj assms(2) by simp
  then obtain j' rest where f: ‹filter (λj. set (sts ! j) = set s) [0..<length sts] = j' # rest›
    by (cases ‹filter (λj. set (sts ! j) = set s) [0..<length sts]›) auto
  have ‹j' ∈ set (filter (λj. set (sts ! j) = set s) [0..<length sts])› unfolding f by simp
  then have j'_ok: ‹j' < length sts ∧ set (sts ! j') = set s› by simp
  show ?thesis unfolding st_find_def f using j'_ok by simp
qed

type_synonym ('n, 't) lacell = ‹nat × ('n, 't) citem × 't option × wrel›

text ‹The FIRST table, the nullable set and a per-state goto table are
  computed once and passed as parameters.  The const‹min› in
  text‹la_next› makes the state bound hold by construction, so the
  saturation-universe proof does not depend on the goto table's contents.›

definition la_next :: ‹(('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    nat ⇒ ('n, 't) sym ⇒ nat› where
  ‹la_next gt sts i X =
     min (case map_of (gt ! i) X of Some j ⇒ j | None ⇒ length sts) (length sts)›

lemma la_next_le: ‹la_next gt sts i X ≤ length sts›
  unfolding la_next_def by simp

definition la_gtab :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒
    (('n, 't) sym × nat) list list› where
  ‹la_gtab G sts = map (λs. let cl = cclosure G s in
      map (λX. (X, st_find sts (cgoto cl X)))
        (remdups (concat (map (λ(pr, m).
           if m < length (snd pr) then [fst (snd pr ! m)] else []) cl)))) sts›

lemma map_of_map_pair:
  ‹map_of (map (λX. (X, f X)) xs) X = (if X ∈ set xs then Some (f X) else None)›
  by (induction xs) auto

definition la_start :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list› where
  ‹la_start G Shn sts =
     [(st_find sts (lr0_start G Shn), (start_prod G Shn, 0), None, WAny)]›

fun la_cell :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab ⇒ 'n list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell ⇒ ('n, 't) lacell list› where
  ‹la_cell G ft ns gt sts (i, (pr, m), t, τ) = (
      if m < length (snd pr)
      then (la_next gt sts i (fst (snd pr ! m)), (pr, Suc m), t, τ)
        # (case fst (snd pr ! m) of
             Nt B ⇒ (let back = winv (w_of (snd (snd pr ! m)));
                         la = map (λ(a, σ). (Some a, wcomp back (wemb σ)))
                                (fscan ft ns (drop (Suc m) (snd pr)))
                              @ (if list_all (λ(X, r). nsym ns X)
                                       (drop (Suc m) (snd pr))
                                 then [(t, wcomp back τ)] else [])
                     in concat (map (λbr.
                          if fst br = B
                          then map (λ(u, ρ). (i, (br, 0), u, ρ)) la
                          else []) (iprods G)))
           | Tm _ ⇒ [])
      else [])›

definition la_step :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab ⇒ 'n list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ ('n, 't) lacell list› where
  ‹la_step G ft ns gt sts L = remdups (L @ concat (map (la_cell G ft ns gt sts) L))›

lemma la_cell_cases:
  assumes ‹x ∈ set (la_cell G ft ns gt sts (i, (pr, m), t, τ))›
  obtains
    (goto) ‹m < length (snd pr)›
      and ‹x = (la_next gt sts i (fst (snd pr ! m)), (pr, Suc m), t, τ)›
  | (first) br a σ where ‹m < length (snd pr)› and ‹br ∈ set (iprods G)›
      and ‹(a, σ) ∈ set (fscan ft ns (drop (Suc m) (snd pr)))›
      and ‹x = (i, (br, 0), Some a, wcomp (winv (w_of (snd (snd pr ! m)))) (wemb σ))›
  | (inherit) br where ‹m < length (snd pr)› and ‹br ∈ set (iprods G)›
      and ‹x = (i, (br, 0), t, wcomp (winv (w_of (snd (snd pr ! m)))) τ)›
  using assms by (auto simp: Let_def split: sym.splits if_splits)

definition la_univ :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat ⇒ ('n, 't) lacell set› where
  ‹la_univ G Shn n =
     {0..n} × cuniv G Shn × (Some ` set (gram_terms G) ∪ {None}) × (UNIV :: wrel set)›

lemma UNIV_wrel: ‹(UNIV :: wrel set) = {WEq, WGe, WGt, WLe, WLt, WAny}›
  by (auto intro: wrel.exhaust)

lemma finite_la_univ: ‹finite (la_univ G Shn n)›
  unfolding la_univ_def UNIV_wrel by (intro finite_cartesian_product) (auto simp: finite_cuniv)

lemma la_step_mono: ‹set L ⊆ set (la_step G ft ns gt sts L)›
  unfolding la_step_def by auto

lemma cuniv_terms:
  assumes ‹(pr, m) ∈ cuniv G Shn›
    and ‹(Tm a, r) ∈ set (drop (Suc m) (snd pr))›
  shows ‹a ∈ set (gram_terms G)›
proof -
  have mem: ‹(Tm a, r) ∈ set (snd pr)›
    using assms(2) by (rule in_set_dropD)
  from assms(1) consider ‹pr = start_prod G Shn› | ‹pr ∈ set (iprods G)›
    unfolding cuniv_def by auto
  then show ?thesis
  proof cases
    case 1
    then show ?thesis using mem unfolding start_prod_def by auto
  next
    case 2
    then show ?thesis
      using gram_termsI[of ‹fst pr› ‹snd pr› G a r] mem by auto
  qed
qed

lemma la_cell_inU:
  assumes ft: ‹set ft ⊆ funiv G›
    and cin: ‹c ∈ la_univ G Shn (length sts)›
  shows ‹set (la_cell G ft ns gt sts c) ⊆ la_univ G Shn (length sts)›
proof
  fix x assume xc: ‹x ∈ set (la_cell G ft ns gt sts c)›
  obtain i q t τ where c4: ‹c = (i, q, t, τ)› using prod_cases4 by blast
  obtain pr m where q: ‹q = (pr, m)› by (cases q)
  have iu: ‹i ≤ length sts› and pru: ‹(pr, m) ∈ cuniv G Shn›
    and tu: ‹t ∈ Some ` set (gram_terms G) ∪ {None}›
    using cin unfolding c4 q la_univ_def by auto
  from xc[unfolded c4 q] show ‹x ∈ la_univ G Shn (length sts)›
  proof (cases rule: la_cell_cases)
    case goto
    have ‹(pr, Suc m) ∈ cuniv G Shn›
      using pru goto(1) unfolding cuniv_def by auto
    then show ?thesis
      using la_next_le tu goto(2)
      unfolding la_univ_def by auto
  next
    case (first br a σ)
    have a: ‹a ∈ set (gram_terms G)›
      using fscan_inU[OF ft _ first(3)] cuniv_terms[OF pru] by blast
    show ?thesis
      using iu first(2,4) a unfolding la_univ_def cuniv_def by auto
  next
    case (inherit br)
    show ?thesis
      using iu tu inherit(2,3) unfolding la_univ_def cuniv_def by auto
  qed
qed

text ‹The saturation runs as a worklist: every cell is expanded once, and
  only new cells enter the queue, where a fixpoint of const‹la_step›
  would re-expand the table each round.  Termination and the closure
  property follow the invariant-plus-measure scheme of the
  const‹lr0_states› worklist.›

definition la_wl :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab ⇒ 'n list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list × ('n, 't) lacell list ⇒
    ('n, 't) lacell list × ('n, 't) lacell list› where
  ‹la_wl G ft ns gt sts = (λ(dn, wk). case wk of
      [] ⇒ (dn, [])
    | c # ws ⇒ (c # dn,
        ws @ filter (λx. x ∉ set (c # dn) ∧ x ∉ set ws)
               (remdups (la_cell G ft ns gt sts c))))›

definition la_inv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) ftab ⇒ 'n list ⇒
    (('n, 't) sym × nat) list list ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list × ('n, 't) lacell list ⇒ bool› where
  ‹la_inv G Shn ft ns gt sts = (λ(dn, wk).
     distinct (dn @ wk) ∧
     set (dn @ wk) ⊆ la_univ G Shn (length sts) ∧
     set (la_start G Shn sts) ⊆ set (dn @ wk) ∧
     (∀c ∈ set dn. set (la_cell G ft ns gt sts c) ⊆ set (dn @ wk)))›

lemma la_wl_inv:
  assumes ft: ‹set ft ⊆ funiv G›
    and inv: ‹la_inv G Shn ft ns gt sts (dn, wk)› and ne: ‹wk ≠ []›
  shows ‹la_inv G Shn ft ns gt sts (la_wl G ft ns gt sts (dn, wk))›
proof -
  obtain c ws where wk: ‹wk = c # ws› using ne by (cases wk) auto
  define fresh where ‹fresh = filter (λx. x ∉ set (c # dn) ∧ x ∉ set ws)
      (remdups (la_cell G ft ns gt sts c))›
  have res: ‹la_wl G ft ns gt sts (dn, wk) = (c # dn, ws @ fresh)›
    unfolding la_wl_def wk fresh_def by simp
  have dst: ‹distinct (dn @ wk)›
    and unv: ‹set (dn @ wk) ⊆ la_univ G Shn (length sts)›
    and st: ‹set (la_start G Shn sts) ⊆ set (dn @ wk)›
    and cls: ‹∀c' ∈ set dn. set (la_cell G ft ns gt sts c') ⊆ set (dn @ wk)›
    using inv unfolding la_inv_def by auto
  have cinU: ‹c ∈ la_univ G Shn (length sts)› using unv wk by auto
  have dst': ‹distinct ((c # dn) @ ws @ fresh)›
    using dst unfolding wk fresh_def by auto
  have unv': ‹set ((c # dn) @ ws @ fresh) ⊆ la_univ G Shn (length sts)›
    using unv la_cell_inU[OF ft cinU] unfolding wk fresh_def by auto
  have sub: ‹set (dn @ wk) ⊆ set ((c # dn) @ ws @ fresh)›
    unfolding wk by auto
  have st': ‹set (la_start G Shn sts) ⊆ set ((c # dn) @ ws @ fresh)›
    using st sub by blast
  have cls': ‹∀c' ∈ set (c # dn).
      set (la_cell G ft ns gt sts c') ⊆ set ((c # dn) @ ws @ fresh)›
  proof
    fix c' assume ‹c' ∈ set (c # dn)›
    then consider ‹c' = c› | ‹c' ∈ set dn› by auto
    then show ‹set (la_cell G ft ns gt sts c') ⊆ set ((c # dn) @ ws @ fresh)›
    proof cases
      case 1
      show ?thesis
      proof
        fix x assume x: ‹x ∈ set (la_cell G ft ns gt sts c')›
        show ‹x ∈ set ((c # dn) @ ws @ fresh)›
        proof (cases ‹x ∈ set (c # dn) ∨ x ∈ set ws›)
          case True then show ?thesis by auto
        next
          case False
          then have ‹x ∈ set fresh› using x unfolding fresh_def 1 by auto
          then show ?thesis by auto
        qed
      qed
    next
      case 2
      then show ?thesis using cls sub by blast
    qed
  qed
  show ?thesis unfolding res la_inv_def using dst' unv' st' cls' by simp
qed

lemma la_inv_init:
  ‹la_inv G Shn ft ns gt sts ([], la_start G Shn sts)›
  unfolding la_inv_def la_start_def la_univ_def cuniv_def
  using st_find_le by auto

text ‹The saturated table over an arbitrary automaton ‹(gt, sts)›;
  text‹la_fix› is its instance at the coarse tables, and the
  context-precise analysis of text‹LR_Det› instantiates it at the
  precise ones.›

definition la_fix_gen :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
    ('n, 't) citem list list ⇒ ('n, 't) lacell list› where
  ‹la_fix_gen G Shn gt sts =
     fst (the (while_option (λ(dn, wk). wk ≠ []) (la_wl G (ffix G) (nullables G) gt sts)
       ([], la_start G Shn sts)))›

lemma la_fix_gen_inv:
  ‹la_inv G Shn (ffix G) (nullables G) gt sts (la_fix_gen G Shn gt sts, [])›
proof -
  let ?P = ‹la_inv G Shn (ffix G) (nullables G) gt sts›
  let ?c = ‹la_wl G (ffix G) (nullables G) gt sts›
  let ?t = ‹the (while_option (λ(dn, wk). wk ≠ []) ?c ([], la_start G Shn sts))›
  have ‹?P ?t ∧ ¬ (case ?t of (dn, wk) ⇒ wk ≠ [])›
  proof (rule while_option_the_inv[where P = ?P and b = ‹λ(dn, wk). wk ≠ []›
        and c = ?c and f = ‹λ(dn, wk). card (la_univ G Shn (length sts)) - length dn›])
    show ‹?P ([], la_start G Shn sts)› by (rule la_inv_init)
  next
    fix st assume inv: ‹?P st›
      and b: ‹case st of (dn, wk) ⇒ wk ≠ []›
    obtain dn wk where st: ‹st = (dn, wk)› by (cases st)
    obtain c ws where wk: ‹wk = c # ws› using b st by (cases wk) auto
    have inv': ‹?P (?c (dn, wk))›
      using la_wl_inv[OF ffix_inU inv[unfolded st]] b st by simp
    have fst_res: ‹fst (?c (dn, wk)) = c # dn›
      unfolding la_wl_def wk by simp
    have ‹distinct (c # dn)› and ‹set (c # dn) ⊆ la_univ G Shn (length sts)›
      using inv unfolding st wk la_inv_def by auto
    then have ‹length (c # dn) ≤ card (la_univ G Shn (length sts))›
      by (metis distinct_card card_mono finite_la_univ)
    then have dec: ‹card (la_univ G Shn (length sts)) - length (c # dn)
        < card (la_univ G Shn (length sts)) - length dn›
      by simp
    show ‹?P (?c st) ∧
        (case ?c st of
           (dn, wk) ⇒ card (la_univ G Shn (length sts)) - length dn)
        < (case st of (dn, wk) ⇒ card (la_univ G Shn (length sts)) - length dn)›
      using inv' dec fst_res unfolding st
      by (cases ‹?c (dn, wk)›) auto
  qed
  then show ?thesis unfolding la_fix_gen_def by (cases ?t) auto
qed

lemma la_fix_gen_stable:
  ‹set (la_step G (ffix G) (nullables G) gt sts (la_fix_gen G Shn gt sts))
   = set (la_fix_gen G Shn gt sts)›
proof -
  have cls: ‹∀c ∈ set (la_fix_gen G Shn gt sts).
      set (la_cell G (ffix G) (nullables G) gt sts c) ⊆ set (la_fix_gen G Shn gt sts)›
    using la_fix_gen_inv[of G Shn gt sts] unfolding la_inv_def by auto
  have ‹set (la_step G (ffix G) (nullables G) gt sts (la_fix_gen G Shn gt sts))
      ⊆ set (la_fix_gen G Shn gt sts)›
    unfolding la_step_def using cls by auto
  then show ?thesis using la_step_mono by blast
qed

lemma la_fix_gen_start: ‹set (la_start G Shn sts) ⊆ set (la_fix_gen G Shn gt sts)›
  using la_fix_gen_inv[of G Shn gt sts] unfolding la_inv_def by auto

subsection ‹A faster implementation of the saturation›

text ‹The worklist of const‹la_wl› tests every new cell for membership in
  the lists of expanded and queued cells, and appends to the queue: both are
  linear in the number of cells, which makes the saturation quadratic.  The
  implementation below keeps the same two lists, the queue as a pair of a
  front and a reversed back list, and indexes all cells seen so far by a
  cheap key in a red-black tree of buckets.  The key need not be injective:
  membership is decided in the bucket.  It computes the same lists step by
  step (‹la_fix_gen_fast›), so it is only a code equation.›

fun la_tindex :: ‹'t list ⇒ 't ⇒ nat› where
  ‹la_tindex [] a = 0›
| ‹la_tindex (b # bs) a = (if b = a then 0 else Suc (la_tindex bs a))›

text ‹The key of a cell combines its state, lookahead, the length of its
  right-hand side and its dot; ‹nt› is the number of terminals ‹ts›, computed once.
  A key that searched the productions would cost a linear scan per cell.›

definition la_key :: ‹nat × 't list ⇒ ('n, 't) lacell ⇒ integer› where
  ‹la_key pts c = (case pts of (nt, ts) ⇒ case c of (i, (pr, m), t, τ) ⇒
     ((of_nat i * (of_nat nt + 2)
        + of_nat (case t of None ⇒ 0 | Some a ⇒ Suc (la_tindex ts a)))
        * 64 + of_nat (min (length (snd pr)) 63)) * 8 + of_nat (min m 7))›

definition la_bucket :: ‹(integer, ('n, 't) lacell list) rbt ⇒ integer ⇒ ('n, 't) lacell list› where
  ‹la_bucket bk k = (case RBT.lookup bk k of None ⇒ [] | Some xs ⇒ xs)›

definition la_add :: ‹nat × 't list ⇒ ('n, 't) lacell ⇒ (integer, ('n, 't) lacell list) rbt ⇒
    (integer, ('n, 't) lacell list) rbt› where
  ‹la_add ts x bk = RBT.insert (la_key ts x) (x # la_bucket bk (la_key ts x)) bk›

lemma set_la_bucket_fold:
  ‹set (la_bucket (fold (la_add ts) xs bk) k) =
   set (la_bucket bk k) ∪ {x ∈ set xs. la_key ts x = k}›
  by (induction xs arbitrary: bk) (auto simp: la_add_def la_bucket_def split: option.splits)

type_synonym ('n, 't) la_fast =
  ‹('n, 't) lacell list × (integer, ('n, 't) lacell list) rbt ×
   ('n, 't) lacell list × ('n, 't) lacell list›

definition la_wl_fast :: ‹(('n, 't) lacell ⇒ ('n, 't) lacell list) ⇒
    nat × 't list ⇒ ('n, 't) la_fast ⇒ ('n, 't) la_fast› where
  ‹la_wl_fast cf ts = (λ(dn, bk, fr, bq).
     (let (fr', bq') = (if fr = [] then (rev bq, []) else (fr, bq)) in
      case fr' of
        [] ⇒ (dn, bk, [], [])
      | c # ws ⇒
          (let fresh = filter (λx. x ∉ set (la_bucket bk (la_key ts x)))
                         (remdups (cf c))
           in (c # dn, fold (la_add ts) fresh bk, ws, rev fresh @ bq'))))›

definition la_fast_abs :: ‹('n, 't) la_fast ⇒ ('n, 't) lacell list × ('n, 't) lacell list› where
  ‹la_fast_abs = (λ(dn, bk, fr, bq). (dn, fr @ rev bq))›

definition la_fast_inv :: ‹nat × 't list ⇒ ('n, 't) la_fast ⇒ bool› where
  ‹la_fast_inv ts = (λ(dn, bk, fr, bq).
     ∀x. x ∈ set (dn @ fr @ rev bq) ⟷ x ∈ set (la_bucket bk (la_key ts x)))›

lemma la_wl_fast_commute:
  assumes inv: ‹la_fast_inv ts s›
  shows ‹la_fast_inv ts (la_wl_fast (la_cell G ft ns gt sts) ts s)›
    and ‹(case la_fast_abs s of (dn, wk) ⇒ wk ≠ []) ⟹
         la_fast_abs (la_wl_fast (la_cell G ft ns gt sts) ts s) = la_wl G ft ns gt sts (la_fast_abs s)›
proof -
  obtain dn bk fr bq where s: ‹s = (dn, bk, fr, bq)› by (cases s) auto
  define fr' where ‹fr' = (if fr = [] then rev bq else fr)›
  define bq' where ‹bq' = (if fr = [] then [] else bq)›
  have q: ‹fr' @ rev bq' = fr @ rev bq› unfolding fr'_def bq'_def by simp
  have split: ‹(if fr = [] then (rev bq, []) else (fr, bq)) = (fr', bq')›
    unfolding fr'_def bq'_def by simp
  have inv': ‹∀x. x ∈ set (dn @ fr @ rev bq) ⟷ x ∈ set (la_bucket bk (la_key ts x))›
    using inv unfolding s la_fast_inv_def prod.case .
  have mem: ‹x ∈ set (dn @ fr' @ rev bq') ⟷ x ∈ set (la_bucket bk (la_key ts x))› for x
    unfolding q using spec[OF inv', of x] .
  show ‹la_fast_inv ts (la_wl_fast (la_cell G ft ns gt sts) ts s)›
  proof (cases fr')
    case Nil
    then have ‹fr = []› ‹bq = []› unfolding fr'_def by (auto split: if_splits)
    then show ?thesis using inv' unfolding s la_wl_fast_def la_fast_inv_def by (simp only: prod.case) simp
  next
    case (Cons c ws)
    let ?fresh = ‹filter (λx. x ∉ set (la_bucket bk (la_key ts x)))
                   (remdups (la_cell G ft ns gt sts c))›
    have step: ‹la_wl_fast (la_cell G ft ns gt sts) ts s = (c # dn, fold (la_add ts) ?fresh bk, ws, rev ?fresh @ bq')›
      using Cons unfolding s la_wl_fast_def fr'_def bq'_def by (cases fr) (simp_all add: Let_def)
    have ‹x ∈ set ((c # dn) @ ws @ rev (rev ?fresh @ bq')) ⟷
          x ∈ set (la_bucket (fold (la_add ts) ?fresh bk) (la_key ts x))› for x
      using mem[of x] unfolding set_la_bucket_fold Cons by auto
    then show ?thesis unfolding step la_fast_inv_def by (simp only: prod.case) blast
  qed
  assume ne: ‹case la_fast_abs s of (dn, wk) ⇒ wk ≠ []›
  have ‹fr' ≠ []›
    using ne unfolding s la_fast_abs_def fr'_def by (auto split: if_splits)
  then obtain c ws where Cons: ‹fr' = c # ws› by (cases fr') auto
  have wk: ‹fr @ rev bq = c # ws @ rev bq'› using q Cons by simp
  have filt: ‹filter (λx. x ∉ set (la_bucket bk (la_key ts x))) ys =
      filter (λx. x ∉ set (c # dn) ∧ x ∉ set (ws @ rev bq')) ys› for ys
  proof (rule filter_cong[OF refl])
    fix x
    show ‹(x ∉ set (la_bucket bk (la_key ts x))) = (x ∉ set (c # dn) ∧ x ∉ set (ws @ rev bq'))›
      using mem[of x] unfolding Cons by auto
  qed
  let ?fresh = ‹filter (λx. x ∉ set (la_bucket bk (la_key ts x)))
                 (remdups (la_cell G ft ns gt sts c))›
  have step: ‹la_wl_fast (la_cell G ft ns gt sts) ts s = (c # dn, fold (la_add ts) ?fresh bk, ws, rev ?fresh @ bq')›
    using Cons unfolding s la_wl_fast_def fr'_def bq'_def by (cases fr) (simp_all add: Let_def)
  show ‹la_fast_abs (la_wl_fast (la_cell G ft ns gt sts) ts s) = la_wl G ft ns gt sts (la_fast_abs s)›
    unfolding step unfolding s la_fast_abs_def la_wl_def
    by (simp add: wk filt)
qed

definition la_fast_start :: ‹'n ⇒ nat × 't list ⇒ ('n, 't) lacell list ⇒
    ('n, 't) la_fast› where
  ‹la_fast_start Shn ts st = ([], fold (la_add ts) st RBT.empty, st, [])›

lemma la_bucket_empty [simp]: ‹la_bucket RBT.empty k = []›
  by (simp add: la_bucket_def)

lemma la_fast_start: ‹la_fast_inv ts (la_fast_start Shn ts st)›
  ‹la_fast_abs (la_fast_start Shn ts st) = ([], st)›
  by (simp_all add: la_fast_inv_def la_fast_start_def la_fast_abs_def set_la_bucket_fold)

lemma la_fix_gen_fast:
  ‹la_fix_gen G Shn gt sts = (let ts = (length (gram_terms G), gram_terms G) in
     case while_option (λ(dn, bk, fr, bq). fr ≠ [] ∨ bq ≠ [])
       (la_wl_fast (la_cell G (ffix G) (nullables G) gt sts) ts) (la_fast_start Shn ts (la_start G Shn sts)) of
       Some s ⇒ fst (la_fast_abs s)
     | None ⇒ fst (the (while_option (λ(dn, wk). wk ≠ []) (la_wl G (ffix G) (nullables G) gt sts)
                ([], la_start G Shn sts))))›
proof -
  let ?ts = ‹(length (gram_terms G), gram_terms G)›
  let ?b = ‹λ(dn :: ('n, 't) lacell list, bk :: (integer, ('n, 't) lacell list) rbt,
             fr :: ('n, 't) lacell list, bq :: ('n, 't) lacell list). fr ≠ [] ∨ bq ≠ []›
  let ?c = ‹la_wl_fast (la_cell G (ffix G) (nullables G) gt sts) ?ts›
  have eq: ‹map_option la_fast_abs (while_option ?b ?c (la_fast_start Shn ?ts (la_start G Shn sts))) =
      while_option (λ(dn, wk). wk ≠ []) (la_wl G (ffix G) (nullables G) gt sts)
        (la_fast_abs (la_fast_start Shn ?ts (la_start G Shn sts)))›
  proof (rule while_option_commute_invariant[where P = ‹la_fast_inv ?ts›])
    show ‹la_fast_inv ?ts (?c s)› if ‹la_fast_inv ?ts s› for s
      using la_wl_fast_commute(1)[OF that] .
    show ‹?b s = (case la_fast_abs s of (dn, wk) ⇒ wk ≠ [])› for s :: ‹('n, 't) la_fast›
      by (cases s) (auto simp: la_fast_abs_def)
    show ‹la_fast_abs (?c s) = la_wl G (ffix G) (nullables G) gt sts (la_fast_abs s)›
      if ‹la_fast_inv ?ts s› and ‹?b s› for s
      using la_wl_fast_commute(2)[OF that(1)] that(2) by (cases s) (auto simp: la_fast_abs_def)
  qed (rule la_fast_start)
  show ?thesis
  proof (cases ‹while_option ?b ?c (la_fast_start Shn ?ts (la_start G Shn sts))›)
    case None
    then show ?thesis unfolding la_fix_gen_def Let_def by simp
  next
    case (Some s)
    with eq have ‹while_option (λ(dn, wk). wk ≠ []) (la_wl G (ffix G) (nullables G) gt sts)
        ([], la_start G Shn sts) = Some (la_fast_abs s)›
      unfolding la_fast_start(2) by simp
    with Some show ?thesis unfolding la_fix_gen_def Let_def by simp
  qed
qed

text ‹const‹la_cell› looks up the goto table per cell, by const‹nth› on a list
  and with term‹length sts› recomputed each time, and scans all productions for
  those of the nonterminal after the dot. The code equation passes the same cell
  function over an array and a table of the productions by nonterminal, both
  built once.›

fun la_cell_nx :: ‹('n, 't) ftab ⇒ 'n list ⇒ ('n ⇒ ('n × ('n, 't) rhs) list) ⇒
    (nat ⇒ ('n, 't) sym ⇒ nat) ⇒ ('n, 't) lacell ⇒ ('n, 't) lacell list› where
  ‹la_cell_nx ft ns po nx (i, (pr, m), t, τ) = (
      if m < length (snd pr)
      then (nx i (fst (snd pr ! m)), (pr, Suc m), t, τ)
        # (case fst (snd pr ! m) of
             Nt B ⇒ (let back = winv (w_of (snd (snd pr ! m)));
                         la = map (λ(a, σ). (Some a, wcomp back (wemb σ)))
                                (fscan ft ns (drop (Suc m) (snd pr)))
                              @ (if list_all (λ(X, r). nsym ns X)
                                       (drop (Suc m) (snd pr))
                                 then [(t, wcomp back τ)] else [])
                     in concat (map (λbr. map (λ(u, ρ). (i, (br, 0), u, ρ)) la) (po B)))
           | Tm _ ⇒ [])
      else [])›

definition la_ptab :: ‹('n, 't) is_cfg ⇒ ('n × ('n × ('n, 't) rhs) list) list› where
  ‹la_ptab G = map (λA. (A, filter (λbr. fst br = A) (iprods G))) (remdups (map fst (iprods G)))›

definition la_prods :: ‹('n × ('n × ('n, 't) rhs) list) list ⇒ 'n ⇒ ('n × ('n, 't) rhs) list› where
  ‹la_prods tab B = (case map_of tab B of None ⇒ [] | Some bs ⇒ bs)›

lemma la_prods_ptab: ‹la_prods (la_ptab G) B = filter (λbr. fst br = B) (iprods G)›
  unfolding la_prods_def la_ptab_def map_of_map_pair by (auto simp: image_iff intro!: filter_False[symmetric])

lemma concat_map_if_filter:
  ‹concat (map (λx. if P x then f x else []) xs) = concat (map f (filter P xs))›
  by (induction xs) auto

definition la_next_arr :: ‹(('n, 't) sym × nat) list iarray ⇒ nat ⇒ nat ⇒ ('n, 't) sym ⇒ nat› where
  ‹la_next_arr A n i X = min (case map_of (IArray.sub A i) X of Some j ⇒ j | None ⇒ n) n›

lemma la_cell_nx_eq:
  ‹la_cell G ft ns gt sts = la_cell_nx ft ns (la_prods (la_ptab G)) (la_next_arr (IArray gt) (length sts))›
proof
  fix c :: ‹('a, 'b) lacell›
  obtain i pr m t τ where c: ‹c = (i, (pr, m), t, τ)› by (cases c) auto
  show ‹la_cell G ft ns gt sts c = la_cell_nx ft ns (la_prods (la_ptab G)) (la_next_arr (IArray gt) (length sts)) c›
    unfolding c by (simp add: la_next_def la_next_arr_def la_prods_ptab concat_map_if_filter Let_def split: sym.split)
qed

lemma la_fix_gen_code [code]:
  ‹la_fix_gen G Shn gt sts = (let ts = (length (gram_terms G), gram_terms G);
       cf = la_cell_nx (ffix G) (nullables G) (la_prods (la_ptab G)) (la_next_arr (IArray gt) (length sts)) in
     case while_option (λ(dn, bk, fr, bq). fr ≠ [] ∨ bq ≠ [])
       (la_wl_fast cf ts) (la_fast_start Shn ts (la_start G Shn sts)) of
       Some s ⇒ fst (la_fast_abs s)
     | None ⇒ fst (the (while_option (λ(dn, wk). wk ≠ []) (la_wl G (ffix G) (nullables G) gt sts)
                ([], la_start G Shn sts))))›
  unfolding la_fix_gen_fast la_cell_nx_eq Let_def ..

subsection ‹The canonical conflict report›

text ‹Reduce lookahead comes from the canonical cells, the anchoring to the
  state's common reference column from const‹wreach›, which carries the
  anchor relation through closure chains. const‹anch› alone would widen
  every dot-0 item to const‹WAny›, and const‹wdisjoint› could never
  separate them. A completed cell whose item has several const‹wreach›
  instances is tested against each; an item without one falls back to
  const‹anch›.

  A state is inconsistent cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"› if a token
  allows both a shift and a reduction, or two reductions; Knuth's Step~2
  cite‹‹Sect.~II, Eqs.~(19)--(20)› in "knuth1965-lr-translation"› asks the shift set
  ‹Z› and the reduce sets ‹Zp› to be disjoint.  ‹ConfSR› and ‹ConfRR›
  below are these two kinds of overlap, kept only when const‹wdisjoint› cannot
  separate the two anchor relations.›

text ‹The test itself takes the state collection and its cell table as
  parameters, since it runs over two automata: the coarse one the machine
  builds, and the context-precise one of the next subsection.›

text ‹A report entry names the pair that fired: the completed item, the
  token both sides claim, and the two anchor relations const‹wdisjoint›
  failed to separate.›

datatype ('n, 't) lconf =
    ConfSR ‹'n × ('n, 't) rhs› 't wrel wrel
  | ConfRR ‹'n × ('n, 't) rhs› ‹'n × ('n, 't) rhs› ‹'t option› wrel wrel

text ‹Order of appearance in const‹iprods›. A reduce/reduce pair is
  reported in one direction only, by dropping the one whose mirror the test
  keeps. Two productions the grammar does not list keep both directions
  rather than neither, so the reported pairs change but the report is empty
  iff the underlying pairwise test finds nothing.›

definition pr_before :: ‹('n, 't) is_cfg ⇒ 'n × ('n, 't) rhs ⇒
    'n × ('n, 't) rhs ⇒ bool› where
  ‹pr_before G pr pr' = (pr ∈ set (takeWhile (λq. q ≠ pr') (iprods G)))›

text ‹Which candidate text‹dcands› lists first, hence the one the
  driver takes whenever both successors are live. The shift comes
  first as long as input remains, and a reported shift/reduce pair always
  carries a token, so text‹SideShift› is exact. Reduce order follows the
  frame closure, and const‹xslots› lists the kernel ahead of the dot-0
  slots: a completed item beats an text‹ε›-production, and two
  text‹ε›-productions go by their position in const‹iprods›. Two
  completed kernel items are ordered by the frame the run built, which a
  static report cannot know.›

datatype ('n, 't) lside =
    SideShift | SideReduce ‹'n × ('n, 't) rhs› | SideFrame

fun conf_first :: ‹('n, 't) is_cfg ⇒ ('n, 't) lconf ⇒ ('n, 't) lside› where
  ‹conf_first G (ConfSR pr a τ τ') = SideShift›
| ‹conf_first G (ConfRR pr pr' t τ τ') =
     (if snd pr ≠ [] ∧ snd pr' ≠ [] then SideFrame
      else if snd pr' = [] ∧ snd pr ≠ [] then SideReduce pr
      else if snd pr = [] ∧ snd pr' ≠ [] then SideReduce pr'
      else if pr_before G pr pr' then SideReduce pr
      else SideReduce pr')›

definition lalr_confs_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ ('n, 't) lconf list› where
  ‹lalr_confs_at G Shn sts L i =
     (let ws = wreach G (sts ! i);
          reds = concat (map (λ(i', (pr, m), t, τ).
              if i' = i ∧ m = length (snd pr) ∧ fst pr ≠ Shn
              then (case filter (λ(pr', m', ρ). pr' = pr ∧ m' = m) ws of
                      [] ⇒ [(pr, t, wcomp (winv (anch pr m)) τ)]
                    | insts ⇒ map (λ(pr', m', ρ).
                        (pr, t, wcomp (winv ρ) τ)) insts)
              else []) L);
          shifts = shift_cells ws
      in remdups
          (concat (map (λ(pr, t, τ). case t of
              Some a ⇒ map (λ(a', τ'). ConfSR pr a τ τ')
                (filter (λ(a', τ'). a' = a ∧ ¬ wdisjoint τ τ') shifts)
            | None ⇒ []) reds)
         @ concat (map (λ(pr, t, τ). map (λ(pr', t', τ'). ConfRR pr pr' t τ τ')
              (filter (λ(pr', t', τ'). pr' ≠ pr ∧ ¬ pr_before G pr' pr ∧ t' = t ∧
                 (case t of Some _ ⇒ ¬ wdisjoint τ τ' | None ⇒ True)) reds))
              reds)))›

definition lalr_conflict_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
    ('n, 't) lacell list ⇒ nat ⇒ bool› where
  ‹lalr_conflict_at G Shn sts L i = (lalr_confs_at G Shn sts L i ≠ [])›

subsection ‹The precise automaton›

text ‹const‹cclosure› predicts every production in every state, so a
  goto carries, besides the advanced kernel, one item per production whose
  right-hand side starts with the goto symbol.  Two states then agree as soon
  as their kernels do, and the cell propagation pools contexts that no viable
  prefix shares.  The items of a declaration, a specification and a
  refinement meet in the state after a name, and the report cannot tell such
  a meeting from a conflict.

  The precise automaton rebuilds the states with const‹creach› in place
  of const‹cclosure›, giving the classical viable-prefix states, the LR(0) parse
  tables ‹PT(G)› of cite‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›;
  text‹LR_Det› runs its rigid-point conflict analysis over them.
  Nothing on the parsing path changes: the machine keeps the coarse frames,
  whose typ‹indrep›s prune per input what the precise automaton
  separates statically.  A pair the precise automaton keeps apart is one
  text‹dcands› never offers together.›

definition pr0_states :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list› where
  ‹pr0_states G Shn = wl_states G Shn (creach G)›

definition pgtab :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list list ⇒
    (('n, 't) sym × nat) list list› where
  ‹pgtab G sts = map (λs. let cl = creach G s in
      map (λX. (X, st_find sts (cgoto cl X)))
        (remdups (concat (map (λ(pr, m).
           if m < length (snd pr) then [fst (snd pr ! m)] else []) cl)))) sts›


subsection ‹The precise automaton: its states›

text ‹const‹pr0_states› is the worklist construction of ‹LR› with the
  reachable closure const‹creach› in place of const‹cclosure›; the
  generic text‹wl_states_inv› gives goto-closedness, the start state and
  the universe bound once a goto through const‹creach› is known to stay
  in the universe.›

lemma cgoto_creach_univ:
  assumes ‹set s ⊆ cuniv G Shn›
  shows ‹set (cgoto (creach G s) X) ⊆ cuniv G Shn›
  using cgoto_set_mono[OF creach_sound] cgoto_cclosure_univ[OF assms] by blast

lemma pr0_states_inv:
  ‹wl_inv G Shn (creach G) {set (lr0_start G Shn), {}} (pr0_states G Shn, [])›
  unfolding pr0_states_def by (rule wl_states_inv[OF cgoto_creach_univ])

theorem pr0_states_closed:
  assumes ‹s ∈ set (pr0_states G Shn)› and ‹X ∈ set (gram_syms G)›
  shows ‹∃t ∈ set (pr0_states G Shn). set t = set (cgoto (creach G s) X)›
  using pr0_states_inv assms unfolding wl_inv_def by fastforce

theorem pr0_states_start:
  ‹∃t ∈ set (pr0_states G Shn). set t = set (ccore (xinit G Shn))›
proof -
  have ‹set (lr0_start G Shn) ∈ set ` set (pr0_states G Shn)›
    using pr0_states_inv[of G Shn] unfolding wl_inv_def by auto
  moreover have ‹set (ccore (xinit G Shn)) = set (lr0_start G Shn)›
    unfolding ccore_def xinit_def lr0_start_def start_prod_def by simp
  ultimately show ?thesis by auto
qed

lemma pr0_states_univ:
  ‹s ∈ set (pr0_states G Shn) ⟹ set s ⊆ cuniv G Shn›
  using pr0_states_inv[of G Shn] unfolding wl_inv_def by auto


subsection ‹The live part of a frame closure lies in the reachable closure›

text ‹The frame closure const‹xclosure_auto› predicts every production
  (dead slots carry empty typ‹indrep›s), but an item that carries an
  ‹anchor› was predicted through a chain of anchored items: its core lies in
  const‹creach› of any kernel covering the anchored kernel items.  This
  connects a runtime frame to the ‹precise› automaton state of its
  context.  First the const‹creach› lemmas: a set-level characterisation
  of the step, saturation of the fuelled closure (via
  ‹funpow_saturates_delta›), monotonicity, and the emit lemma.›

lemma creach_step_set:
  ‹set (creach_step G cs) = set cs ∪
     {(pr, 0) | pr. pr ∈ set (iprods G) ∧
        (∃pr' m'. (pr', m') ∈ set cs ∧ m' < length (snd pr') ∧
                  fst (snd pr' ! m') = Nt (fst pr))}›
  unfolding creach_step_def by (fastforce simp: list_ex_iff split: if_splits)

lemma creach_step_ext:
  ‹set cs = set cs' ⟹ set (creach_step G cs) = set (creach_step G cs')›
  by (simp add: creach_step_set)

lemma creach_step_dot0_delta:
  ‹set (creach_step G cs) ⊆ set cs ∪ set (map (λpr. (pr, 0)) (iprods G))›
  by (auto simp: creach_step_set)

theorem creach_stable: ‹set (creach_step G (creach G cs)) = set (creach G cs)›
  unfolding creach_def
proof (rule funpow_saturates_delta[where D = ‹set (map (λpr. (pr, 0)) (iprods G))›])
  show ‹⋀xs ys. set xs = set ys ⟹ set (creach_step G xs) = set (creach_step G ys)›
    by (rule creach_step_ext)
  show ‹⋀xs. set xs ⊆ set (creach_step G xs)› by (rule creach_step_mono)
  show ‹⋀xs. set (creach_step G xs) ⊆ set xs ∪ set (map (λpr. (pr, 0)) (iprods G))›
    by (rule creach_step_dot0_delta)
  show ‹finite (set (map (λpr. (pr, 0)) (iprods G)))› by simp
  show ‹card (set (map (λpr. (pr, 0)) (iprods G))) ≤ Suc (length (iprods G))›
    by (metis card_length length_map le_SucI)
qed

lemma creach_emit:
  assumes mem: ‹(pr', m') ∈ set (creach G cs)›
    and m_lt: ‹m' < length (snd pr')›
    and nxt: ‹fst (snd pr' ! m') = Nt (fst br)›
    and br: ‹br ∈ set (iprods G)›
  shows ‹(br, 0) ∈ set (creach G cs)›
proof -
  have ‹(br, 0) ∈ set (creach_step G (creach G cs))›
    unfolding creach_step_set using mem m_lt nxt br by blast
  then show ?thesis unfolding creach_stable .
qed

text ‹Induction on the round number of const‹xiter›: a slot with an anchor ‹j› was
  contributed by an anchored item, a kernel item or an earlier slot, whose anchor ‹i›
  relates to ‹j›. A property ‹Q› of the kernel's anchored items that every such step
  preserves holds of every slot.›

lemma xiter_slot_induct:
  assumes kern: ‹⋀pr m R i. (pr, m, R) ∈ set xs ⟹ i ∈ irep_set R ⟹ Q pr m i›
    and emit: ‹⋀pr m i j p. Q pr m i ⟹ m < length (snd pr) ⟹ fst (snd pr ! m) = Nt (fst (iprods G ! p)) ⟹
      p < length (iprods G) ⟹ irel_sat (snd (snd pr ! m)) j i ⟹ Q (iprods G ! p) 0 j›
  shows ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹ Q (iprods G ! p) 0 j›
proof (induction t arbitrary: p j)
  case (Suc t)
  have ‹length (xiter G xs t) = length (iprods G)› by simp
  then have ‹xiter G xs (Suc t) ! p =
      fold (xcontrib (iprods G ! p)) (xslots G xs (xiter G xs t)) (xiter G xs t ! p)›
    by (simp add: xround_nth Suc.prems(1))
  with Suc.prems(2) consider ‹j ∈ irep_set (xiter G xs t ! p)›
    | xit where ‹xit ∈ set (xslots G xs (xiter G xs t))› ‹j ∈ ximg (iprods G ! p) xit›
    by (auto simp: fold_xcontrib_set)
  then show ?case
  proof cases
    case 2
    obtain pr' m' R' where xit: ‹xit = (pr', m', R')› by (cases xit)
    from 2(2) obtain i where m: ‹m' < length (snd pr')› ‹fst (snd pr' ! m') = Nt (fst (iprods G ! p))›
      and iR: ‹i ∈ irep_set R'› and rel: ‹irel_sat (snd (snd pr' ! m')) j i›
      unfolding xit by (cases pr') (auto split: if_splits)
    from 2(1) have ‹Q pr' m' i›
    proof (rule xslots_memE)
      assume ‹xit ∈ set xs›
      with kern iR show ?thesis unfolding xit by blast
    qed (use Suc.IH iR xit in auto)
    from emit[OF this m Suc.prems(1) rel] show ?thesis .
  qed (rule Suc.IH[OF Suc.prems(1)])
qed simp

text ‹The live-closure lemma: a slot with a non-empty anchor set comes from a live kernel
  item.›

lemma xiter_live_creach:
  assumes kern: ‹⋀pr m R. (pr, m, R) ∈ set xs ⟹ irep_nonempty R ⟹ (pr, m) ∈ set s›
  shows ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹
     (iprods G ! p, 0) ∈ set (creach G s)›
proof (rule xiter_slot_induct[where Q = ‹λpr m _. (pr, m) ∈ set (creach G s)›])
  show ‹(pr, m) ∈ set (creach G s)› if ‹(pr, m, R) ∈ set xs› ‹i ∈ irep_set R› for pr m R i
    using kern[OF that(1)] that(2) creach_superset by (auto simp: creach_def creach_funpow_mono)
qed (auto intro: creach_emit)

theorem xclosure_auto_live_creach:
  assumes kern: ‹⋀pr m R. (pr, m, R) ∈ set xs ⟹ irep_nonempty R ⟹ (pr, m) ∈ set s›
    and mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)›
    and jR: ‹j ∈ irep_set R›
  shows ‹(pr, m) ∈ set (creach G s)›
proof -
  have mem': ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
    using mem unfolding xclosure_auto_def xclosure_def .
  show ?thesis
    using mem'
  proof (rule xslots_memE)
    assume mem2: ‹(pr, m, R) ∈ set xs›
    have ‹(pr, m) ∈ set s› using kern[OF mem2] jR by auto
    then show ?thesis using creach_superset by auto
  next
    fix q assume q: ‹q < length (iprods G)›
      and ‹q < length (xiter G xs (xfuel G xs))›
      and eq: ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs (xfuel G xs) ! q)›
    have ‹j ∈ irep_set (xiter G xs (xfuel G xs) ! q)› using jR eq by simp
    from xiter_live_creach[OF kern q this] show ?thesis using eq by simp
  qed
qed


subsection ‹The live core of a frame›

text ‹The live core of a frame: the items whose anchor set is non-empty.  A
  frame owes its obligations only there: a dead frame never contributes a
  candidate, and by ‹xclosure_auto_live_creach› over the empty kernel a dead
  kernel has a dead closure.›

definition lcore :: ‹('n, 't) xitem list ⇒ ('n, 't) citem set› where
  ‹lcore xs = {(pr, m) | pr m R. (pr, m, R) ∈ set xs ∧ irep_nonempty R}›

lemma lcoreI: ‹(pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹ (pr, m) ∈ lcore xs›
  unfolding lcore_def by (cases pr) auto

lemma lcore_subD:
  ‹lcore xs ⊆ S ⟹ (pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹ (pr, m) ∈ S›
  using lcoreI by blast

lemma lcore_subD_ne:
  ‹lcore xs ⊆ S ⟹ (pr, m, R) ∈ set xs ⟹ irep_nonempty R ⟹ (pr, m) ∈ S›
  unfolding irep_nonempty_correct using lcore_subD by blast

lemma live_lcore: ‹live xs ⟷ lcore xs ≠ {}›
  unfolding live_def lcore_def list_ex_iff by fastforce

lemma lcore_xinit: ‹lcore (xinit G Shn) = set (lr0_start G Shn)›
  unfolding lcore_def xinit_def lr0_start_def start_prod_def by auto

lemma creach_Nil [simp]: ‹set (creach G []) = {}›
proof -
  have ‹set ((creach_step G ^^ k) []) = {}› for k
    by (induction k) (auto simp: creach_step_set)
  then show ?thesis unfolding creach_def by blast
qed

text ‹A closure with an anchored item sits on a live kernel: by
  text‹xclosure_auto_live_creach› the item's core would otherwise lie in
  the reachable closure of the empty kernel.›

lemma closure_live_kernel:
  assumes mem: ‹(pr, m, R) ∈ set (xclosure_auto G xs)› and jR: ‹j ∈ irep_set R›
  shows ‹lcore xs ≠ {}›
proof
  assume dead: ‹lcore xs = {}›
  have kern: ‹⋀pr' m' R'. (pr', m', R') ∈ set xs ⟹ irep_nonempty R' ⟹
      (pr', m') ∈ set []›
    using dead by (auto simp: lcore_def)
  from xclosure_auto_live_creach[OF kern mem jR]
  have ‹(pr, m) ∈ set (creach G [])› .
  then show False by simp
qed

subsection ‹The precise goto table›

lemma dot_sym_gram:
  assumes univ: ‹set cs ⊆ cuniv G Shn›
    and mem: ‹(pr, m) ∈ set cs› and m: ‹m < length (snd pr)›
  shows ‹fst (snd pr ! m) ∈ set (gram_syms G)›
proof (cases ‹pr = start_prod G Shn›)
  case True
  then show ?thesis using m by (simp add: start_prod_def gram_syms_def)
next
  case False
  then have ‹pr ∈ set (iprods G)› using univ mem unfolding cuniv_def by auto
  then obtain A rhs where preq: ‹pr = (A, rhs)› and Ar: ‹(A, rhs) ∈ set (iprods G)›
    by (metis prod.collapse)
  moreover have ‹rhs ! m ∈ set rhs› using m preq by simp
  ultimately show ?thesis unfolding gram_syms_def by force
qed

lemma pgtab_len [simp]: ‹length (pgtab G sp) = length sp›
  unfolding pgtab_def by simp

lemma pgtab_mem:
  assumes p: ‹p < length sp›
    and mem: ‹(pr, m) ∈ set (creach G (sp ! p))› and m: ‹m < length (snd pr)›
  shows ‹(fst (snd pr ! m),
          st_find sp (cgoto (creach G (sp ! p)) (fst (snd pr ! m))))
         ∈ set (pgtab G sp ! p)›
proof -
  let ?f = ‹λ(pr, m). if m < length (snd pr) then [fst (snd pr ! m)] else []›
  have h1: ‹fst (snd pr ! m) ∈ set (?f (pr, m))› using m by simp
  have ‹fst (snd pr ! m) ∈ ⋃ (set ` ?f ` set (creach G (sp ! p)))›
    using h1 mem by blast
  then have ‹fst (snd pr ! m) ∈ set (concat (map ?f (creach G (sp ! p))))›
    by simp
  then show ?thesis unfolding pgtab_def using p by (simp add: Let_def)
qed

lemma pgtab_lookup:
  assumes ‹i < length sts› and ‹(pr, m) ∈ set (creach G (sts ! i))› and ‹m < length (snd pr)›
  shows ‹map_of (pgtab G sts ! i) (fst (snd pr ! m)) =
           Some (st_find sts (cgoto (creach G (sts ! i)) (fst (snd pr ! m))))›
proof -
  let ?f = ‹λ(pr, m). if m < length (snd pr) then [fst (snd pr ! m)] else []›
  have h1: ‹fst (snd pr ! m) ∈ set (?f (pr, m))› using assms(3) by simp
  have mem: ‹fst (snd pr ! m) ∈ set (concat (map ?f (creach G (sts ! i))))›
    unfolding set_concat set_map using h1 assms(2) by blast
  show ?thesis unfolding pgtab_def using assms(1) mem
    by (simp add: Let_def map_of_map_pair)
qed

lemma pgtab_none:
  assumes ‹i < length sts›
    and ‹⋀pr m. (pr, m) ∈ set (creach G (sts ! i)) ⟹ m < length (snd pr) ⟹ fst (snd pr ! m) ≠ X›
  shows ‹map_of (pgtab G sts ! i) X = None›
proof -
  let ?f = ‹λ(pr, m). if m < length (snd pr) then [fst (snd pr ! m)] else []›
  have ‹X ∉ set (concat (map ?f (creach G (sts ! i))))›
  proof
    assume ‹X ∈ set (concat (map ?f (creach G (sts ! i))))›
    then obtain pr m where ‹(pr, m) ∈ set (creach G (sts ! i))› ‹m < length (snd pr)›
      ‹fst (snd pr ! m) = X› by (auto split: if_splits)
    with assms(2) show False by blast
  qed
  then show ?thesis unfolding pgtab_def using assms(1)
    by (simp add: Let_def map_of_map_pair)
qed

text ‹The start state of the precise automaton.›

definition p0start :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat› where
  ‹p0start G Shn = st_find (pr0_states G Shn) (lr0_start G Shn)›

subsection ‹The cells of the precise automaton›

text ‹The driver's cell table: the lookahead cells over the precise automaton.
  The automaton is the expensive part of every table, so the code equation
  binds it once rather than building it for the goto table and again for the
  state list.›

definition la_fix :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) lacell list› where
  ‹la_fix G Shn = la_fix_gen G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn)›

lemma la_fix_code [code]:
  ‹la_fix G Shn = (let sts = pr0_states G Shn in la_fix_gen G Shn (pgtab G sts) sts)›
  by (simp add: la_fix_def Let_def)

abbreviation la_step0 :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) lacell list ⇒
    ('n, 't) lacell list› where
  ‹la_step0 G Shn ≡ la_step G (ffix G) (nullables G)
     (pgtab G (pr0_states G Shn)) (pr0_states G Shn)›

theorem la_fix_stable:
  ‹set (la_step0 G Shn (la_fix G Shn)) = set (la_fix G Shn)›
  unfolding la_fix_def by (rule la_fix_gen_stable)

lemma la_fix_start: ‹set (la_start G Shn (pr0_states G Shn)) ⊆ set (la_fix G Shn)›
  unfolding la_fix_def by (rule la_fix_gen_start)

text ‹The canonical conflict report over the precise automaton and its cells.›

definition lalr_conflicts :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
  ‹lalr_conflicts G Shn = (let sts = pr0_states G Shn in
     filter (lalr_conflict_at G Shn sts (la_fix G Shn)) [0..<length sts])›


end