Theory LR_Prec_Parse
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