Theory LR_Prec_Parse

(* Author: Basil Fürer *)

theory LR_Prec_Parse
  imports LR_Parser TIGER_Grammar.LR_Prec
begin

text ‹The parser of the restricted grammar, stated against the grammar the user
  wrote.  All of it is inherited from the driver theorems on
  term‹restrict G d›; const‹plain_ast› drops the unit nodes of the chains and
  restores the original nonterminal names.

  In the terms of Klint and Visser, const‹prec_ok› generates a filter, and the
  restricted grammar with ‹plain orig_name› as translation shows it context-free
  cite‹‹Def.~4.8› in "klint1994-disambiguation-filters"› once the checks pass;
  ‹prec_ok_unique› says the filter is completely disambiguating
  cite‹‹Def.~4.2› in "klint1994-disambiguation-filters"›, up to const‹erase›.
  The informal counterparts are cite‹‹Thms.~6.1, 6.4› in "adams2017-tree-automata"›:
  intersection with a bottom-up deterministic automaton adds no ambiguity and no
  LR(k) conflicts.  Here nothing is inferred from the automaton: determinism and
  the conflict check are premises on the restricted grammar.›

section ‹Freshness of the shift name›

lemma sub_nts: ‹(X, i) ∈ set (sub nm r ks) ⟹ X = Nt y ⟹ ∃c. y = nm c›
  by (auto simp: sub_def split: sym.splits)

lemma cprods_names:
  assumes ‹(m, r) ∈ set (cprods P as key C nm L)›
  shows ‹∃c. m = nm c› and ‹(X, i) ∈ set r ⟹ X = Nt y ⟹ ∃c. y = nm c›
  using assms by (auto simp: cprods_def Let_def dest: sub_nts[OF _ refl])

lemma restrict_names:
  ‹CHR ''#'' ∈ set (istart (restrict G d))›
  ‹(m, r) ∈ set (iprods (restrict G d)) ⟹ CHR ''#'' ∈ set m›
  ‹(m, r) ∈ set (iprods (restrict G d)) ⟹ (Nt y, i) ∈ set r ⟹ CHR ''#'' ∈ set y›
  by (auto simp: restrict_alt restrict_gen_def Let_def dest: cprods_names(1) cprods_names(2)[OF _ _ refl])

theorem fresh_name_restrict:
  assumes ‹CHR ''#'' ∉ set Shn›
  shows ‹fresh_name (restrict G d) Shn›
  using assms restrict_names[where G = G and d = d] unfolding fresh_name_def by fastforce

section ‹Unit chains on grammars without layout›

text ‹const‹restrict› writes its unit chains with const‹Eq›. If that is the only
  relation of the grammar besides const‹Any›, and it stands on nonterminals only, the
  indices of the nodes are not observable: a tree of the grammar with all relations
  const‹Any› is a tree of the original one with one index everywhere (‹rind›).
  So the parser is built from ‹restricted›, which then passes const‹ii› and gets
  the simple driver. The check is a computation on the restricted grammar, nothing about
  const‹restrict› is needed.›

definition rany :: ‹('n, 't) is_cfg ⇒ ('n, 't) is_cfg› where
  ‹rany H = H⦇iprods := map (λ(n, r). (n, map (λ(X, _). (X, Any)) r)) (iprods H)⦈›

definition rels_free :: ‹('n, 't) is_cfg ⇒ bool› where
  ‹rels_free H ⟷ list_all (λ(m, r). list_all (λ(X, a). a = Any ∨ a = Eq ∧
     (case X of Nt _ ⇒ True | Tm _ ⇒ False)) r) (iprods H)›

definition relax :: ‹('n, 't) is_cfg ⇒ ('n, 't) is_cfg› where
  ‹relax H = (if rels_free H then rany H else H)›

definition restricted :: ‹(string, 't) is_cfg ⇒ (string, 't) prec_decl ⇒ (string, 't) is_cfg› where
  ‹restricted G d = relax (restrict G d)›

lemma relax_sel[simp]: ‹istart (relax H) = istart H› ‹istart_ind (relax H) = istart_ind H›
  by (simp_all add: relax_def rany_def)

fun rind :: ‹nat ⇒ ('m, 'ch, 'n, 't) ptree ⇒ ('m, 'ch, 'n, 't) ptree› where
  ‹rind c (PLeaf t) = PLeaf t›
| ‹rind c (PNode n i ts) = PNode n c (map (rind c) ts)›

lemma pyield_rind[simp]: ‹pyield (rind c t) = pyield t›
  by (induction c t rule: rind.induct) (auto intro!: arg_cong[of _ _ concat])

lemma erase_rind[simp]: ‹erase (rind c t) = erase t›
  by (induction c t rule: rind.induct) auto

lemma fst_proot_rind[simp]: ‹fst (proot (rind c t)) = fst (proot t)›
  by (cases t) auto

lemma wf_rany: ‹wf_ptree H t ⟹ wf_ptree (rany H) t›
proof (induction rule: wf_ptree.induct)
  case (wf_leaf t)
  show ?case by (rule wf_ptree.wf_leaf)
next
  case (wf_node A rhs i pts)
  have ‹(A, map (λ(X, _). (X, Any)) rhs) ∈ set (iprods (rany H))›
    using wf_node.hyps by (force simp: rany_def)
  then show ?case
    by (rule wf_ptree.wf_node)
      (use wf_node.IH in ‹auto simp: list_all2_conv_all_nth case_prod_beta›)
qed

lemma wf_rind:
  assumes ‹wf_ptree (rany H) t›
    and rels: ‹⋀m r X a. (m, r) ∈ set (iprods H) ⟹ (X, a) ∈ set r ⟹ a = Any ∨ a = Eq ∧ (∃y. X = Nt y)›
  shows ‹wf_ptree H (rind c t)›
  using assms(1)
proof (induction rule: wf_ptree.induct)
  case (wf_leaf t)
  show ?case by (auto intro: wf_ptree.wf_leaf)
next
  case (wf_node A rhs i pts)
  from wf_node.hyps obtain r where r: ‹(A, r) ∈ set (iprods H)›
    ‹rhs = map (λ(X, _). (X, Any)) r› by (auto simp: rany_def)
  have len: ‹length pts = length r› using list_all2_lengthD[OF wf_node.IH] r(2) by simp
  have ‹list_all2 (λXr pt. fst (proot pt) = fst Xr ∧ irel_sat (snd Xr) (snd (proot pt)) c ∧
      wf_ptree H pt) r (map (rind c) pts)›
  proof (rule list_all2_all_nthI)
    show ‹length r = length (map (rind c) pts)› using len by simp
  next
    fix k assume k: ‹k < length r›
    obtain X a where ra: ‹r ! k = (X, a)› by fastforce
    have m: ‹(X, a) ∈ set r› using k ra by (metis nth_mem)
    have ih: ‹fst (proot (pts ! k)) = X› ‹wf_ptree H (rind c (pts ! k))›
      using list_all2_nthD[OF wf_node.IH, of k] k r(2) ra by (auto simp: case_prod_beta)
    have ‹irel_sat a (snd (proot (rind c (pts ! k)))) c›
      using rels[OF r(1) m] ih(1) by (cases ‹pts ! k›) auto
    then show ‹fst (proot (map (rind c) pts ! k)) = fst (r ! k) ∧
        irel_sat (snd (r ! k)) (snd (proot (map (rind c) pts ! k))) c ∧
        wf_ptree H (map (rind c) pts ! k)›
      using k len ra ih by simp
  qed
  with r(1) show ?case by (auto intro: wf_ptree.wf_node)
qed

lemma wf_relax: ‹wf_ptree H t ⟹ wf_ptree (relax H) t›
  by (simp add: relax_def wf_rany)

lemma relax_tree:
  assumes wf: ‹wf_ptree (relax H) t› and rt: ‹proot t = (Nt n, i)›
  shows ‹∃t'. wf_ptree H t' ∧ proot t' = (Nt n, i) ∧ pyield t' = pyield t ∧ erase t' = erase t›
proof (cases ‹rels_free H›)
  case False
  with assms show ?thesis by (auto simp: relax_def)
next
  case True
  have rels: ‹a = Any ∨ a = Eq ∧ (∃y. X = Nt y)›
    if ‹(m, r) ∈ set (iprods H)› ‹(X, a) ∈ set r› for m r X a
    using True that unfolding rels_free_def list_all_iff by (cases X) fastforce+
  have ‹wf_ptree H (rind i t)›
    using wf_rind[of H t, OF _ rels] wf True by (simp add: relax_def)
  moreover have ‹proot (rind i t) = (Nt n, i)› using rt by (cases t) auto
  ultimately show ?thesis by (intro exI[of _ ‹rind i t›]) simp
qed

lemma ii_relax: ‹rels_free H ⟹ ii (relax H)›
  by (auto simp: ii_def relax_def rany_def list_all_iff)

lemma fresh_name_relax: ‹fresh_name H Shn ⟹ fresh_name (relax H) Shn›
  unfolding fresh_name_def relax_def rany_def by (auto split: if_splits) (force+)

theorem fresh_name_restricted:
  assumes ‹CHR ''#'' ∉ set Shn›
  shows ‹fresh_name (restricted G d) Shn›
  unfolding restricted_def by (rule fresh_name_relax[OF fresh_name_restrict[OF assms]])

section ‹Between the two grammars›

lemma accepts_root:
  fixes t :: ‹('m, 'ch, 'n, 't) ptree›
  assumes ‹proot t = (Nt (istart G), j)›
  shows ‹prec_run G (compile G d) (pq0 G) t ⟷ prec_ok G d t›
  by (rule accepts_iff_prec_ok) (use assms in simp)

context
  fixes G :: ‹(string, 't) is_cfg› and d :: ‹(string, 't) prec_decl›
  assumes ns: ‹no_self_unit G›
begin

lemma restrict_ptree_sound:
  fixes pt' :: ‹('m, 'ch, string, 't) ptree›
  assumes wf: ‹wf_ptree (restrict G d) pt'›
    and rt: ‹proot pt' = (Nt (istart (restrict G d)), istart_ind (restrict G d))›
  shows ‹wf_ptree G (plain orig_name pt') ∧ proot (plain orig_name pt') = (Nt (istart G), istart_ind G) ∧
    prec_ok G d (plain orig_name pt')›
proof -
  obtain Q and cls :: ‹_ ⇒ string› where r: ‹restrict_ok G (compile G d) (pq0 G) Q cls (restrict G d) orig_name›
    using restrict_correct[OF ns] by blast
  interpret r: restrict_ok G ‹compile G d› ‹pq0 G› Q cls ‹restrict G d› orig_name by (fact r)
  have ‹prec_run G (compile G d) (pq0 G) (plain orig_name pt') ∧
      proot (plain orig_name pt') = (Nt (orig_name (istart (restrict G d))), snd (proot pt'))›
    by (rule r.restrict_sound[OF wf]) (use rt r.start in auto)
  then have run: ‹prec_run G (compile G d) (pq0 G) (plain orig_name pt')›
    and root: ‹proot (plain orig_name pt') = (Nt (istart G), istart_ind G)›
    using r.start rt by auto
  have ‹prec_ok G d (plain orig_name pt')›
    using accepts_root[OF root] run by blast
  with run root prec_run_wf[OF run] show ?thesis by blast
qed

lemma restrict_ptree_complete:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and ok: ‹prec_ok G d pt›
  shows ‹∃pt'. wf_ptree (restrict G d) pt' ∧
    proot pt' = (Nt (istart (restrict G d)), istart_ind (restrict G d)) ∧ plain orig_name pt' = pt›
proof -
  obtain Q and cls :: ‹_ ⇒ string› where r: ‹restrict_ok G (compile G d) (pq0 G) Q cls (restrict G d) orig_name›
    using restrict_correct[OF ns] by blast
  interpret r: restrict_ok G ‹compile G d› ‹pq0 G› Q cls ‹restrict G d› orig_name by (fact r)
  have ‹prec_run G (compile G d) (pq0 G) pt›
    using accepts_root[OF rt] ok by blast
  from r.restrict_complete[OF this r.start(1)] rt r.start show ?thesis by auto
qed

lemma restricted_ptree_sound:
  fixes pt' :: ‹('m, 'ch, string, 't) ptree›
  assumes wf: ‹wf_ptree (restricted G d) pt'›
    and rt: ‹proot pt' = (Nt (istart (restricted G d)), istart_ind (restricted G d))›
  shows ‹∃pt. wf_ptree G pt ∧ proot pt = (Nt (istart G), istart_ind G) ∧
    pyield pt = pyield pt' ∧ erase pt = plain_ast orig_name (erase pt') ∧ prec_ok G d pt›
proof -
  from relax_tree[OF wf[unfolded restricted_def] rt[unfolded restricted_def relax_sel]]
  obtain s :: ‹('m, 'ch, string, 't) ptree› where s: ‹wf_ptree (restrict G d) s›
    ‹proot s = (Nt (istart (restrict G d)), istart_ind (restrict G d))›
    ‹pyield s = pyield pt'› ‹erase s = erase pt'› by blast
  from restrict_ptree_sound[OF s(1,2)] s(3,4) erase_plain[of orig_name s]
  show ?thesis by (intro exI[of _ ‹plain orig_name s›]) simp
qed

lemma restricted_ptree_complete:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)› ‹prec_ok G d pt›
  shows ‹∃pt'. wf_ptree (restricted G d) pt' ∧
    proot pt' = (Nt (istart (restricted G d)), istart_ind (restricted G d)) ∧
    plain orig_name pt' = pt›
  using restrict_ptree_complete[OF assms] wf_relax unfolding restricted_def relax_sel by blast

section ‹The driver›

theorem dparse_restrict_sound:
  assumes fn: ‹fresh_name (restricted G d) Shn›
    and p: ‹dparse (restricted G d) Shn w = Some t›
  shows ‹∃pt. wf_ptree G pt ∧ proot pt = (Nt (istart G), istart_ind G) ∧ pyield pt = w ∧
    erase pt = plain_ast orig_name t ∧ prec_ok G d pt›
proof -
  from dparse_sound_ast[OF fn p] obtain pt' where wf: ‹wf_ptree (restricted G d) pt'›
    and rt: ‹proot pt' = (Nt (istart (restricted G d)), istart_ind (restricted G d))›
    and e: ‹erase pt' = t› and y: ‹pyield pt' = w›
    unfolding ast_of_def by blast
  from restricted_ptree_sound[OF wf rt] e y show ?thesis by blast
qed

corollary dparse_restrict_ast:
  assumes ‹fresh_name (restricted G d) Shn› and ‹dparse (restricted G d) Shn w = Some t›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) (plain_ast orig_name t) w›
  using dparse_restrict_sound[OF assms] unfolding ast_of_def by metis

theorem dparse_restrict_complete:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes fn: ‹fresh_name (restricted G d) Shn› and det: ‹mdet (restricted G d) Shn›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and ok: ‹prec_ok G d pt›
  shows ‹∃t. dparse (restricted G d) Shn (pyield pt) = Some t›
proof -
  from restricted_ptree_complete[OF wf rt ok] obtain pt' where
    ‹wf_ptree (restricted G d) pt'›
    ‹proot pt' = (Nt (istart (restricted G d)), istart_ind (restricted G d))›
    ‹plain orig_name pt' = pt› by blast
  from dparse_complete[OF fn det this(1,2)] this(3) show ?thesis by auto
qed

theorem dparse_restrict_exact:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes fn: ‹fresh_name (restricted G d) Shn› and det: ‹mdet (restricted G d) Shn›
    and chk: ‹acc_conflicts (restricted G d) Shn = []›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and ok: ‹prec_ok G d pt›
  shows ‹∃t. dparse (restricted G d) Shn (pyield pt) = Some t ∧ plain_ast orig_name t = erase pt›
proof -
  from restricted_ptree_complete[OF wf rt ok] obtain pt' where
    w: ‹wf_ptree (restricted G d) pt'›
    and r: ‹proot pt' = (Nt (istart (restricted G d)), istart_ind (restricted G d))›
    and p: ‹plain orig_name pt' = pt› by blast
  have ‹dparse (restricted G d) Shn (pyield pt') = Some (erase pt')›
    using dparse_complete_exact[OF fn det chk w r] by simp
  then show ?thesis using p erase_plain[of orig_name pt'] by auto
qed

text ‹Uniqueness: two trees that satisfy the declaration and read the same word
  have the same ast.›

corollary prec_ok_unique:
  fixes pt pt2 :: ‹('m, 'ch, string, 't) ptree›
  assumes fn: ‹fresh_name (restricted G d) Shn› and det: ‹mdet (restricted G d) Shn›
    and chk: ‹acc_conflicts (restricted G d) Shn = []›
    and a: ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)› ‹prec_ok G d pt›
    and b: ‹wf_ptree G pt2› ‹proot pt2 = (Nt (istart G), istart_ind G)› ‹prec_ok G d pt2›
    and y: ‹pyield pt = pyield pt2›
  shows ‹erase pt = erase pt2›
  using dparse_restrict_exact[OF fn det chk a] dparse_restrict_exact[OF fn det chk b] y by force

end

section ‹Schematic forms for the backend›

text ‹A parser of a grammar with declarations is
  ‹λw. Option.bind (dparse Gr Shn w) (dec ∘ plain_ast orig_name)›, with ‹Gr› a constant
  defined as term‹restricted G d› and ‹dec› a decoder of ‹G›, so that the premises about
  ‹dec› are the ones of a grammar without declarations.›

definition prec_lang :: ‹(string, 't) is_cfg ⇒ (string, 't) prec_decl ⇒ ('m, 'ch, 't) tword set› where
  ‹prec_lang G d = {w. ∃pt :: ('m, 'ch, string, 't) ptree. wf_ptree G pt ∧
     proot pt = (Nt (istart G), istart_ind G) ∧ pyield pt = w ∧ prec_ok G d pt}›

lemma no_self_unitI:
  assumes ‹list_all (λp. case snd p of [(Nt m, r)] ⇒ m ≠ fst p | _ ⇒ True) (iprods G)›
  shows ‹no_self_unit G›
  using assms by (fastforce simp: no_self_unit_def list_all_iff)

context
  fixes G Gr :: ‹(string, 't) is_cfg› and d :: ‹(string, 't) prec_decl›
    and parse_fn and dec :: ‹('m, 'ch, string, 't) ast ⇒ 'x option› and Shn
  assumes body: ‹parse_fn = (λw. Option.bind (dparse Gr Shn w) (dec ∘ plain_ast orig_name))›
    and gr: ‹Gr = restricted G d›
    and ns: ‹no_self_unit G›
    and fn: ‹fresh_name Gr Shn›
begin

lemma parse_fn_tree:
  assumes rec: ‹parse_fn w = Some x›
  shows ‹∃pt :: ('m, 'ch, string, 't) ptree. wf_ptree G pt ∧
    proot pt = (Nt (istart G), istart_ind G) ∧ pyield pt = w ∧ prec_ok G d pt ∧
    dec (erase pt) = Some x›
proof -
  from rec obtain t where p: ‹dparse Gr Shn w = Some t› and de: ‹dec (plain_ast orig_name t) = Some x›
    by (auto simp: body bind_eq_Some_conv)
  from dparse_restrict_sound[OF ns fn[unfolded gr] p[unfolded gr]] show ?thesis
    using de by metis
qed

lemma parse_fn_lang: ‹parse_fn w = Some x ⟹ w ∈ prec_lang G d›
  using parse_fn_tree unfolding prec_lang_def by blast

lemma parse_fn_complete_lang:
  assumes det: ‹mdet Gr Shn› and mem: ‹w ∈ prec_lang G d›
    and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹ ∃x. dec t = Some x›
  shows ‹∃x. parse_fn w = Some x›
proof -
  from mem obtain pt :: ‹('m, 'ch, string, 't) ptree› where wf: ‹wf_ptree G pt›
    and rt: ‹proot pt = (Nt (istart G), istart_ind G)› and y: ‹pyield pt = w›
    and ok: ‹prec_ok G d pt›
    unfolding prec_lang_def by blast
  from dparse_restrict_complete[OF ns fn[unfolded gr] det[unfolded gr] wf rt ok] y
  obtain t where p: ‹dparse (restricted G d) Shn w = Some t› by blast
  have ‹ast_of G (Nt (istart G)) (istart_ind G) (plain_ast orig_name t) w›
    by (rule dparse_restrict_ast[OF ns fn[unfolded gr] p])
  from dec_total[OF this] show ?thesis using p by (auto simp: body gr)
qed

lemma parse_fn_complete:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes det: ‹mdet Gr Shn› and chk: ‹acc_conflicts Gr Shn = []›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and ok: ‹prec_ok G d pt› and de: ‹dec (erase pt) = Some x›
  shows ‹parse_fn (pyield pt) = Some x›
  using dparse_restrict_exact[OF ns fn[unfolded gr] det[unfolded gr] chk[unfolded gr] wf rt ok] de
  by (auto simp: body gr)

lemma parse_fn_no_error:
  assumes rec: ‹parse_fn w = Some x› and none: ‹∀y ∈ set w. tok y ≠ e›
  shows ‹∃t. dec t = Some x ∧ ast_of G (Nt (istart G)) (istart_ind G) t w ∧ e ∉ set (atoks t)›
proof -
  from parse_fn_tree[OF rec] obtain pt :: ‹('m, 'ch, string, 't) ptree› where
    ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)› ‹pyield pt = w›
    ‹dec (erase pt) = Some x› by blast
  note pt = this
  have ne: ‹e ∉ set (atoks (erase pt))› using atoks_erase[of pt] none pt(3) by auto
  have ‹ast_of G (Nt (istart G)) (istart_ind G) (erase pt) w›
    unfolding ast_of_def using pt by blast
  with pt(4) ne show ?thesis by blast
qed

end

text ‹For ⬚‹parser (ast)›: the decoder is const‹Some›, the parser returns the tree
  of ‹G›'s names.›

context
  fixes G Gr :: ‹(string, 't) is_cfg› and d :: ‹(string, 't) prec_decl› and Shn
    and parse_fn :: ‹('m, 'ch, 't) tword ⇒ ('m, 'ch, string, 't) ast option›
  assumes body: ‹parse_fn = (λw. Option.bind (dparse Gr Shn w) (Some ∘ plain_ast orig_name))›
    and gr: ‹Gr = restricted G d›
    and ns: ‹no_self_unit G›
    and fn: ‹fresh_name Gr Shn›
begin

lemma parse_fn_ast_tree:
  assumes rec: ‹parse_fn w = Some t›
  shows ‹∃pt :: ('m, 'ch, string, 't) ptree. wf_ptree G pt ∧
    proot pt = (Nt (istart G), istart_ind G) ∧ pyield pt = w ∧ prec_ok G d pt ∧ erase pt = t›
  using parse_fn_tree[OF body gr ns fn rec] by simp

lemma parse_fn_ast_complete_lang:
  assumes det: ‹mdet Gr Shn› and mem: ‹w ∈ prec_lang G d›
  shows ‹∃t. parse_fn w = Some t›
  by (rule parse_fn_complete_lang[OF body gr ns fn det mem]) simp

lemma parse_fn_ast_complete:
  fixes pt :: ‹('m, 'ch, string, 't) ptree›
  assumes det: ‹mdet Gr Shn› and chk: ‹acc_conflicts Gr Shn = []›
    and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
    and ok: ‹prec_ok G d pt›
  shows ‹parse_fn (pyield pt) = Some (erase pt)›
  by (rule parse_fn_complete[OF body gr ns fn det chk wf rt ok]) simp

lemma parse_fn_ast_no_error:
  assumes rec: ‹parse_fn w = Some t› and none: ‹∀y ∈ set w. tok y ≠ e›
  shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w ∧ e ∉ set (atoks t)›
  using parse_fn_no_error[OF body gr ns fn rec none] by simp

end

ML_file ‹lr_prec.ML›

end