Theory LR_Parser
theory LR_Parser
imports TIGER_Grammar.LR_Plain TIGER_Grammar.LR_Sparse TIGER_Grammar.LR_Vec TIGER_Grammar.LR_Diag TIGER_Grammar.LR_Recover Grammar_Command
keywords "parser_error_states" :: diag
begin
section ‹Parser-facing theorems: ‹dparse› composed with a decoder›
text ‹The backend (\<^text>‹Grammar_Command›) defines each generated parser
as ‹λw. Option.bind (dparse G Shn w) dec›, where ‹dec› maps the raw
‹ast› to the grammar's carrier type. Soundness of the composition is
unconditional modulo \<^const>‹fresh_name› (discharged by construction of
‹Shn›); completeness additionally needs \<^const>‹mdet›
\<^cite>‹‹Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› \<^cite>‹‹Thm.~3› in "jourdan2012-validating-lr1"›, which
\<^text>‹rlalr_sufficient› reduces to ∗‹evaluation› of the static
check \<^const>‹rlalr_conflicts›, so the emitted ‹.complete› theorem is
hypothesis-free whenever the check computes ‹[]›.›
theorem dparse_bind_sound:
assumes fn: ‹fresh_name G Shn›
and rec: ‹Option.bind (dparse G Shn w) dec = Some x›
shows ‹w ∈ ilang G›
proof (cases ‹dparse G Shn w›)
case None with rec show ?thesis by simp
next
case (Some t) show ?thesis using dparse_sound[OF fn Some] .
qed
theorem dparse_bind_complete:
assumes fn: ‹fresh_name G Shn›
and det: ‹mdet G Shn›
and mem: ‹w ∈ ilang G›
and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
∃x. dec t = Some x›
shows ‹∃x. Option.bind (dparse G Shn w) dec = Some x›
proof -
from dparse_complete_lang[OF fn det mem] obtain t where
parsed: ‹dparse G Shn w = Some t›
and ao: ‹ast_of G (Nt (istart G)) (istart_ind G) t w› by blast
from dec_total[OF ao] obtain x where ‹dec t = Some x› by blast
with parsed show ?thesis by simp
qed
theorem dparse_bind:
assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn›
and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
∃x. dec t = Some x›
shows ‹w ∈ ilang G ⟷ (∃x. Option.bind (dparse G Shn w) dec = Some x)›
proof
assume ‹w ∈ ilang G›
from dparse_bind_complete[OF fn det this dec_total] show
‹∃x. Option.bind (dparse G Shn w) dec = Some x› .
next
assume ‹∃x. Option.bind (dparse G Shn w) dec = Some x›
then obtain x where ‹Option.bind (dparse G Shn w) dec = Some x› ..
from dparse_bind_sound[OF fn this] show ‹w ∈ ilang G› .
qed
subsection ‹Schematic forms for the backend's \<^text>‹define››
lemma dparse_sound_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
and fn: ‹fresh_name G Shn›
and rec: ‹parse_fn w = Some x›
shows ‹w ∈ ilang G›
by (metis body fn rec dparse_bind_sound)
lemma dparse_complete_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
and fn: ‹fresh_name G Shn›
and det: ‹mdet G Shn›
and mem: ‹w ∈ ilang G›
and dec_total: ‹⋀t. ast_of G (Nt (istart G)) (istart_ind G) t w ⟹
∃x. dec t = Some x›
shows ‹∃x. parse_fn w = Some x›
using body dparse_bind_complete[OF fn det mem dec_total] by simp
section ‹Exact completeness: the driver returns the erasure of the tree›
text ‹\<^text>‹dparse_complete› only says that the driver returns ∗‹some› tree
of the word. Relating a generated parser to the relation family of
⬚‹grammar (relation)› needs more: the tree it returns must be the
erasure of the tree the relation exhibits, i.e.\ the word must have a
unique parse. \<^const>‹mdet› does not give this. The conflict report
ignores the start production, so a configuration that ∗‹accepts› may
still license a live reduce: a cycle ‹S ⇒⁺ S› through the start symbol,
where the driver stops at the first accepting configuration and a second
tree continues. \<^text>‹acc_conflicts› is the missing static check: an
LR(0) state holding the completed start item together with an
end-of-input reduce cell of another production. Together with
\<^const>‹mdet› it pins the driver's answer to \<^term>‹erase pt›
(\<^text>‹dparse_complete_exact›), and every parse tree of a word erases to
the same ast (\<^text>‹ast_of_unique›).
The uniqueness argument is that of Jourdan et al.
\<^cite>‹‹Sect.~3.4, Thm.~4› in "jourdan2012-validating-lr1"›: the driver is a function, and
by completeness it returns the value of each of two parses, so the two agree. Barthwal
\<^cite>‹‹Sect.~5.4.5, Thm.~5.4.5› in "barthwal2010-thesis-cfl-hol4"› proves that a grammar
whose SLR machine is built without conflicts is unambiguous. Here uniqueness holds up
to erasure: two trees of a word give the same ast.›
subsection ‹The tree stack along an action list›
text ‹The tree-stack component of the driver depends only on the actions
taken: a shift pushes the leaf of the next token, a reduce folds the
right-hand side. Along the trace of a tree it builds the tree's erasure.›
fun tsteps :: ‹('n, 't) dact list ⇒ ('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list ⇒
(('m, 'ch, 't) tword × ('m, 'ch, 'n, 't) ast list) option› where
‹tsteps [] s = Some s›
| ‹tsteps (DShift # acts) (v, tstk) =
(case v of [] ⇒ None | t # v' ⇒ tsteps acts (v', Leaf t # tstk))›
| ‹tsteps (DReduce pr # acts) (v, tstk) =
tsteps acts (v, Node (fst pr) (rev (take (length (snd pr)) tstk))
# drop (length (snd pr)) tstk)›
lemma tsteps_append:
‹tsteps (as @ bs) s = (case tsteps as s of None ⇒ None | Some s' ⇒ tsteps bs s')›
by (induction as s rule: tsteps.induct) (auto split: list.splits)
lemma tsteps_concat:
assumes ‹list_all2 (λpt tr. ∀rest tstk.
tsteps tr (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)) pts trs›
shows ‹tsteps (concat trs) (concat (map pyield pts) @ rest, tstk) =
Some (rest, rev (map erase pts) @ tstk)›
using assms
proof (induction arbitrary: rest tstk rule: list_all2_induct)
case Nil show ?case by simp
next
case (Cons pt pts tr trs)
show ?case
unfolding concat.simps list.map(2) tsteps_append append_assoc
using Cons.hyps(1)[rule_format, of ‹concat (map pyield pts) @ rest› tstk] Cons.IH by simp
qed
lemma tsteps_mtrace:
‹mtrace G pt acts ⟹ tsteps acts (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)›
proof (induction arbitrary: rest tstk rule: mtrace.induct)
case (mt_leaf t) show ?case by simp
next
case (mt_node A rhs i pts trs)
have kids: ‹list_all2 (λpt tr. ∀rest tstk.
tsteps tr (pyield pt @ rest, tstk) = Some (rest, erase pt # tstk)) pts trs›
using mt_node.IH by (rule list_all2_mono) blast
have lenp: ‹length pts = length rhs› using mt_node.hyps(2) by (simp add: list_all2_lengthD)
show ?case
by (simp add: tsteps_append tsteps_concat[OF kids] lenp)
qed
subsection ‹One step of the driver, along the trace›
text ‹\<^text>‹dstep_of_imstep_exact› in terms of \<^const>‹tsteps›: the shift
case has input left, since the machine shifted.›
lemma dstep_exact:
assumes tab: ‹tables_ok G Shn sts gt L›
and stc: ‹sts = pr0_states G Shn›
and gtc: ‹gt = pgtab G sts›
and Lc: ‹L = la_fix G Shn›
and rt: ‹redtab = red_buckets G Shn (length sts)›
and det: ‹mdet G Shn›
and ireach: ‹imreach G Shn gt sts ((Xs, w), istk)›
and inv: ‹dfollow_ok G sts ((Xs, w), cstk, istk, v, tstk)›
and step: ‹imstep G gt sts ((Xs, w), istk) act = Some (gc', istk')›
and live: ‹dlive gc'›
and lic: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ((Xs, w), istk) pr›
shows ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w)) ∧
(∃v' tstk'. tsteps [act] (v, tstk) = Some (v', tstk') ∧
dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk)
= Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk') ∧
dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk'))›
proof -
from dstep_of_imstep_exact[OF assms] obtain v' tstk' where
cand: ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, w))›
and ts: ‹(v', tstk') = tstep act (v, tstk)›
and ds: ‹dstep G gt sts redtab ((Xs, w), cstk, istk, v, tstk)
= Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
and inv': ‹dfollow_ok G sts (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
by blast
have v_ne: ‹v ≠ []› if sh: ‹act = DShift›
proof -
have ‹w = tcols v› using inv unfolding dfollow_ok_def by simp
moreover have ‹w ≠ []›
using step unfolding sh imstep_def mstep_def mstep_cached_def
by (auto split: list.splits)
ultimately show ‹v ≠ []› by auto
qed
have ‹tsteps [act] (v, tstk) = Some (v', tstk')›
using ts v_ne by (cases act) (auto split: list.splits)
with cand ds inv' show ?thesis by blast
qed
subsection ‹The driver follows the trace without stopping early›
lemma dsteps_trace:
assumes tab: ‹tables_ok G Shn sts gt L›
and stc: ‹sts = pr0_states G Shn›
and gtc: ‹gt = pgtab G sts›
and Lc: ‹L = la_fix G Shn›
and rt: ‹redtab = red_buckets G Shn (length sts)›
and det: ‹mdet G Shn› and fn: ‹fresh_name G Shn› and chk: ‹acc_conflicts G Shn = []›
shows ‹mdrive G gt sts L acts (gc, istk) ⟹ imreach G Shn gt sts (gc, istk) ⟹
dfollow_ok G sts (gc, cstk, istk, v, tstk) ⟹ dinv G Shn w (gc, cstk, istk, v, tstk) ⟹
tsteps acts (v, tstk) = Some (v', tstk') ⟹
(∀k < length acts. ∃st⇩k. dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some st⇩k ∧
¬ gfinal G Shn (fst st⇩k)) ∧
(∃gc'. mrun G acts gc = Some gc' ∧
(∃istk'. dsteps G gt sts redtab (length acts) (gc, cstk, istk, v, tstk)
= Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')))›
proof (induction acts arbitrary: gc istk cstk v tstk)
case Nil
have ‹cstk = map (xclosure_auto G) (fst gc)›
using Nil.prems(3) unfolding dfollow_ok_def by (cases gc) simp
then show ?case using Nil.prems(5) by auto
next
case (Cons act acts)
obtain Xs u where gc: ‹gc = (Xs, u)› by (cases gc)
from mdrive_ConsD[OF Cons.prems(1)] obtain ic⇩1 where
st⇩0: ‹imstep G gt sts (gc, istk) act = Some ic⇩1› and lv⇩0: ‹dlive (fst ic⇩1)›
and lc⇩0: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts (gc, istk) pr›
and rest⇩0: ‹mdrive G gt sts L acts ic⇩1› by blast
obtain gc⇩1 istk⇩1 where ic⇩1: ‹ic⇩1 = (gc⇩1, istk⇩1)› by (cases ic⇩1)
have st: ‹imstep G gt sts ((Xs, u), istk) act = Some (gc⇩1, istk⇩1)›
using st⇩0 gc ic⇩1 by simp
have lv: ‹dlive gc⇩1› using lv⇩0 ic⇩1 by simp
have lc: ‹∀pr. act = DReduce pr ⟶ lic_at G L sts ((Xs, u), istk) pr›
using lc⇩0 gc by simp
have ireach: ‹imreach G Shn gt sts ((Xs, u), istk)› using Cons.prems(2) gc by simp
have inv: ‹dfollow_ok G sts ((Xs, u), cstk, istk, v, tstk)›
using Cons.prems(3) gc by simp
from dstep_exact[OF tab stc gtc Lc rt det ireach inv st lv lc] obtain v⇩1 tstk⇩1 where
cand: ‹act ∈ set (dcands G (hd istk) (redtab ! hd istk) (xclosure_auto G (hd Xs)) (Xs, u))›
and ts⇩1: ‹tsteps [act] (v, tstk) = Some (v⇩1, tstk⇩1)›
and ds: ‹dstep G gt sts redtab ((Xs, u), cstk, istk, v, tstk) =
Some (gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1)›
and inv⇩1: ‹dfollow_ok G sts (gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1)›
by blast
have ms: ‹mstep G gc act = Some gc⇩1›
using imstep_mstep[of G gt sts ‹(gc, istk)› act ic⇩1] st⇩0 ic⇩1 by simp
have notfin: ‹¬ gfinal G Shn (Xs, u)›
proof
assume fin: ‹gfinal G Shn (Xs, u)›
then have u: ‹u = []› unfolding gfinal_def by simp
obtain pr where act: ‹act = DReduce pr›
proof (cases act)
case DShift
with ms u have False unfolding mstep_def mstep_cached_def gc by simp
then show ?thesis ..
qed
have ok: ‹didx_ok G (pr0_states G Shn) Xs istk›
using Cons.prems(3) gc stc unfolding dfollow_ok_def by simp
show False
by (rule no_reduce_at_final[OF fn chk Cons.prems(4)[unfolded gc] ok fin
cand[unfolded act rt stc] ms[unfolded gc act] lv])
qed
have dinv⇩1: ‹dinv G Shn w (gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1)›
by (rule dstep_inv[OF fn Cons.prems(4)[unfolded gc] ds])
have ireach⇩1: ‹imreach G Shn gt sts (gc⇩1, istk⇩1)›
using imreach_step[OF Cons.prems(2) st⇩0 lv⇩0] ic⇩1 by simp
have rest: ‹mdrive G gt sts L acts (gc⇩1, istk⇩1)› using rest⇩0 ic⇩1 by simp
have ts_rest: ‹tsteps acts (v⇩1, tstk⇩1) = Some (v', tstk')›
using Cons.prems(5) ts⇩1 tsteps_append[of ‹[act]› acts ‹(v, tstk)›] by simp
from Cons.IH[OF rest ireach⇩1 inv⇩1 dinv⇩1 ts_rest] obtain gc' istk' where
nf: ‹∀k < length acts. ∃st⇩k. dsteps G gt sts redtab k
(gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1) = Some st⇩k ∧
¬ gfinal G Shn (fst st⇩k)›
and mr: ‹mrun G acts gc⇩1 = Some gc'›
and dr: ‹dsteps G gt sts redtab (length acts)
(gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1) =
Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
by blast
have ds': ‹dstep G gt sts redtab (gc, cstk, istk, v, tstk) =
Some (gc⇩1, map (xclosure_auto G) (fst gc⇩1), istk⇩1, v⇩1, tstk⇩1)›
using ds gc by simp
have A: ‹∀k < length (act # acts). ∃st⇩k.
dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some st⇩k ∧ ¬ gfinal G Shn (fst st⇩k)›
proof (intro allI impI)
fix k assume k: ‹k < length (act # acts)›
show ‹∃st⇩k. dsteps G gt sts redtab k (gc, cstk, istk, v, tstk) = Some st⇩k ∧
¬ gfinal G Shn (fst st⇩k)›
proof (cases k)
case 0
then show ?thesis using notfin gc by simp
next
case (Suc k')
then have ‹k' < length acts› using k by simp
then show ?thesis
using nf[rule_format, of k'] unfolding Suc dsteps_Suc_step[OF ds'] by simp
qed
qed
have B: ‹mrun G (act # acts) gc = Some gc'› using ms mr by simp
have C: ‹dsteps G gt sts redtab (Suc (length acts)) (gc, cstk, istk, v, tstk) =
Some (gc', map (xclosure_auto G) (fst gc'), istk', v', tstk')›
unfolding dsteps_Suc_step[OF ds'] by (rule dr)
from A B C show ?case by auto
qed
lemma drun⇩w⇩f_of_dsteps:
‹dsteps G gt sts redtab n st = Some st' ⟹
(∀k < n. ∃st⇩k. dsteps G gt sts redtab k st = Some st⇩k ∧ ¬ gfinal G Shn (fst st⇩k)) ⟹
gfinal G Shn (fst st') ⟹
(case st' of (gc, cstk, istk, v, tstk) ⇒ tstk) = t # rest ⟹
drun⇩w⇩f G Shn gt sts redtab st = Some t›
by (rule drun_imp_drun⇩w⇩f[OF drun_of_dsteps])
subsection ‹The licensed run of a tree, from the root›
subsection ‹Exact completeness and uniqueness of the parse›
theorem dparse_complete_exact:
assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn› and chk: ‹acc_conflicts G Shn = []›
and wf: ‹wf_ptree G pt› and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
shows ‹dparse G Shn (pyield pt) = Some (erase pt)›
proof -
let ?sts = ‹pr0_states G Shn› and ?gt = ‹pgtab G (pr0_states G Shn)›
let ?L = ‹la_fix G Shn› and ?i⇩0 = ‹st_find (pr0_states G Shn) (lr0_start G Shn)›
let ?redtab = ‹red_buckets G Shn (length (pr0_states G Shn))›
let ?w = ‹pyield pt›
let ?st = ‹(([xinit G Shn], tcols ?w), [xclosure_auto G (xinit G Shn)], [?i⇩0], ?w,
[] :: ('m, 'ch, 'n, 't) ast list)›
have tab: ‹tables_ok G Shn ?sts ?gt ?L› by (rule tables_ok_concrete)
from mtrace_ex[OF wf] obtain acts where tr: ‹mtrace G pt acts› by blast
have drv: ‹mdrive G ?gt ?sts ?L acts (([xinit G Shn], tcols ?w), [?i⇩0])›
by (rule mdrive_root[OF wf rt tr])
have fin: ‹mcompletes G Shn acts ([xinit G Shn], tcols ?w)›
by (rule mtrace_completes[OF wf tr rt])
have inv: ‹dfollow_ok G ?sts ?st›
using dfollow_ok_dinit[of G Shn ?w] unfolding dinit_def .
have dinv: ‹dinv G Shn ?w ?st›
using dinv_init[of G Shn ?w ?sts] unfolding dinit_def .
have ts: ‹tsteps acts (?w, []) = Some ([], [erase pt])›
using tsteps_mtrace[OF tr, of ‹[]› ‹[]›] by simp
from dsteps_trace[OF tab refl refl refl refl det fn chk drv imreach_init inv dinv ts]
obtain gc' istk' where
nf: ‹∀k < length acts. ∃st⇩k. dsteps G ?gt ?sts ?redtab k ?st = Some st⇩k ∧
¬ gfinal G Shn (fst st⇩k)›
and mr: ‹mrun G acts ([xinit G Shn], tcols ?w) = Some gc'›
and ds: ‹dsteps G ?gt ?sts ?redtab (length acts) ?st =
Some (gc', map (xclosure_auto G) (fst gc'), istk', [], [erase pt])› by blast
have gf: ‹gfinal G Shn gc'› using fin mr unfolding mcompletes_def by simp
have ‹drun⇩w⇩f G Shn ?gt ?sts ?redtab ?st = Some (erase pt)›
by (rule drun⇩w⇩f_of_dsteps[OF ds nf]) (use gf in simp_all)
then show ?thesis unfolding dparse_def dinit_def Let_def by simp
qed
corollary ast_of_unique:
assumes fn: ‹fresh_name G Shn› and det: ‹mdet G Shn› and chk: ‹acc_conflicts G Shn = []›
and a: ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
and b: ‹ast_of G (Nt (istart G)) (istart_ind G) t' w›
shows ‹t = t'›
proof -
from a obtain pt where ‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)›
‹erase pt = t› ‹pyield pt = w› unfolding ast_of_def by blast
then have 1: ‹dparse G Shn w = Some t› using dparse_complete_exact[OF fn det chk] by blast
from b obtain pt' where ‹wf_ptree G pt'› ‹proot pt' = (Nt (istart G), istart_ind G)›
‹erase pt' = t'› ‹pyield pt' = w› unfolding ast_of_def by blast
then have 2: ‹dparse G Shn w = Some t'› using dparse_complete_exact[OF fn det chk] by blast
from 1 2 show ?thesis by simp
qed
subsection ‹Parser-facing forms: the relation family›
text ‹For ⬚‹grammar (relation)› the backend states soundness and
completeness against the relation ‹P› of the start symbol. The two
‹bridge› premises are per-grammar lemmas proved at parser-definition
time (🗏‹parser_rel_bridge.ML›): a decoded value satisfies the relation, and
the relation exhibits a tree the decoder maps to the value.›
lemma dparse_rel_sound_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
and fn: ‹fresh_name G Shn›
and bridge: ‹⋀pt x. wf_ptree G pt ⟹ proot pt = (Nt (istart G), istart_ind G) ⟹
dec (erase pt) = Some x ⟹ P (pyield pt) x›
and rec: ‹parse_fn w = Some x›
shows ‹P w x›
proof -
from rec body obtain t where p: ‹dparse G Shn w = Some t› and d: ‹dec t = Some x›
by (auto simp: bind_eq_Some_conv)
from dparse_sound_ast[OF fn p] obtain pt where
‹wf_ptree G pt› ‹proot pt = (Nt (istart G), istart_ind G)› ‹erase pt = t› ‹pyield pt = w›
unfolding ast_of_def by blast
with bridge[of pt x] d show ?thesis by simp
qed
lemma dparse_rel_complete_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
and fn: ‹fresh_name G Shn›
and det: ‹mdet G Shn›
and chk: ‹acc_conflicts G Shn = []›
and bridge: ‹⋀w x. P w x ⟹ ∃pt. wf_ptree G pt ∧ proot pt = (Nt (istart G), istart_ind G) ∧
pyield pt = w ∧ dec (erase pt) = Some x›
and rel: ‹P w x›
shows ‹parse_fn w = Some x›
proof -
from bridge[OF rel] obtain pt where wf: ‹wf_ptree G pt›
and rt: ‹proot pt = (Nt (istart G), istart_ind G)› and y: ‹pyield pt = w›
and d: ‹dec (erase pt) = Some x› by blast
from dparse_complete_exact[OF fn det chk wf rt] have ‹dparse G Shn w = Some (erase pt)›
by (simp add: y)
with d body show ?thesis by simp
qed
subsection ‹Parser-facing forms: the tree›
text ‹For ⬚‹parser (ast)› the decoder is \<^const>‹Some›: the parser returns the
tree of \<^const>‹dparse›, and the theorems speak of it. Soundness: the tree is the
erasure of a parse tree of the word; completeness: the erasure of every parse tree is
returned for its yield, which also makes the tree unique.›
lemma dparse_ast_sound_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
and fn: ‹fresh_name G Shn›
and rec: ‹parse_fn w = Some t›
shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w›
using rec by (simp add: body dparse_sound_ast[OF fn])
lemma dparse_ast_complete_lang_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
and fn: ‹fresh_name G Shn›
and det: ‹mdet G Shn›
and mem: ‹w ∈ ilang G›
shows ‹∃t. parse_fn w = Some t›
by (rule dparse_complete_generic[OF body fn det mem]) simp
lemma dparse_ast_complete_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
and fn: ‹fresh_name G Shn›
and det: ‹mdet G Shn›
and chk: ‹acc_conflicts G Shn = []›
and wf: ‹wf_ptree G pt›
and rt: ‹proot pt = (Nt (istart G), istart_ind G)›
shows ‹parse_fn (pyield pt) = Some (erase pt)›
using dparse_complete_exact[OF fn det chk wf rt] by (simp add: body)
lemma recover_no_error_ast_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) Some)›
and fn: ‹fresh_name G Shn›
and rec: ‹parse_fn w = Some t›
and none: ‹∀y ∈ set w. tok y ≠ e›
shows ‹ast_of G (Nt (istart G)) (istart_ind G) t w ∧ e ∉ set (atoks t)›
using recover_no_error_generic[OF body fn rec none] by simp
section ‹Explaining the reports›
text ‹Diagnostics for the ⬚‹parser› command, after Menhir's
‹.conflicts› file \<^cite>‹‹Sect.~6› in "pottier2026-menhir-manual"›: for every pair the checks return, the items of the
state, a symbol path from the start state with a sample input
(nonterminals expanded to shortest terminal words), the conflicting
actions with the column relation each imposes on the lookahead against the
state's anchor, and a bounded search for an annotated word on which the
driver has two live candidates, a witness that the ambiguity is real and
not an over-approximation of the check. Nothing here enters a proof; the
checks themselves are untouched. Productions are reported by their index
in \<^const>‹iprods›, which the command maps back to the source.›
subsection ‹Shortest terminal words›
fun syms_word :: ‹('n × 't list) list ⇒ ('n, 't) sym list ⇒ 't list option› where
‹syms_word tab [] = Some []›
| ‹syms_word tab (Tm a # xs) = map_option ((#) a) (syms_word tab xs)›
| ‹syms_word tab (Nt A # xs) = (case map_of tab A of
None ⇒ None | Some w ⇒ map_option ((@) w) (syms_word tab xs))›
definition mw_step :: ‹('n, 't) is_cfg ⇒ ('n × 't list) list ⇒ ('n × 't list) list› where
‹mw_step G tab = fold (λ(A, rhs) tab'. case syms_word tab (map fst rhs) of
None ⇒ tab'
| Some w ⇒ (case map_of tab' A of
None ⇒ (A, w) # tab'
| Some w' ⇒ if length w < length w' then (A, w) # tab' else tab'))
(iprods G) tab›
text ‹A shortest word has a derivation tree of height at most the number of
nonterminals (a repeated nonterminal on a path can be cut), so this many
rounds reach the fixpoint.›
definition min_words :: ‹('n, 't) is_cfg ⇒ ('n × 't list) list› where
‹min_words G = (mw_step G ^^ Suc (length (iprods G))) []›
subsection ‹Paths through an automaton›
fun path_bfs :: ‹('a ⇒ (('n, 't) sym × 'a) list) ⇒ 'a ⇒ nat ⇒
'a list ⇒ ('a × ('n, 't) sym list) list ⇒ ('n, 't) sym list option› where
‹path_bfs succ tgt 0 seen wk = None›
| ‹path_bfs succ tgt (Suc n) seen [] = None›
| ‹path_bfs succ tgt (Suc n) seen ((i, p) # wk) =
(if i = tgt then Some (rev p)
else (let succs = fold (λ(X, j) acc.
if j ∈ set seen ∨ j ∈ set (map fst wk) ∨ j ∈ set (map fst acc) then acc
else acc @ [(j, X # p)]) (succ i) []
in path_bfs succ tgt n (i # seen) (wk @ succs)))›
definition prod_no :: ‹('n, 't) is_cfg ⇒ 'n × ('n, 't) rhs ⇒ nat› where
‹prod_no G pr = (case filter (λ(i, q). q = pr) (zip [0..<length (iprods G)] (iprods G)) of
[] ⇒ length (iprods G) | (i, _) # _ ⇒ i)›
subsection ‹The conflicting actions of a reported state›