Theory LR_Driver
theory LR_Driver
imports LR
begin
section ‹A complete deterministic LR driver with set-valued anchors›
text ‹
A driver that guesses a single anchor column per reduce is incomplete.
This driver gives the reduce a ∗‹set-valued› goto: the reduced
nonterminal carries the set of all anchors its completed item admits, and
each parent item keeps the anchors compatible with some of them. The
frames are the item-wise union of all single-anchor GLR frames, acceptance
is exact, and no anchor is guessed. Reduce licensing tests the LALR cell's
width relation against that anchor set, so the remaining nondeterminism is
the layout/LALR nondeterminism of the grammar.
The driver follows Knuth's parsing method
\<^cite>‹‹Sect.~II, Eqs.~(17)--(23)› in "knuth1965-lr-translation"›: a stack of
state sets, a closure, a shift or a reduce, and the next state set. The
items are those of Adams' finite representation for indentation-sensitive
grammars \<^cite>‹‹Sects.~5.5--5.6› in "adams2013"›. Adams keeps one
indentation set per item, and annotates closure items with the relation that
leads to them \<^cite>‹‹Sect.~5.8› in "adams2013"›; the anchor sets and the
cached closures below do the same. Adams removes the nondeterminism by
restricting to LR(k) grammars (Sect.~5.6); here that restriction is the
operational hypothesis ‹mdet› of the completeness proof.
›
subsection ‹Closure-cached machine steps›
text ‹Frame closures are computed once, when the frame is pushed, and
cached in a stack running in lockstep with the frame stack; the cache
invariant ‹cstk_ok› says the two agree.›
definition cstk_ok :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list list ⇒
('n, 't) xitem list list ⇒ bool› where
‹cstk_ok G Xs cstk ⟷ list_all2 (λf c. c = xclosure_auto G f) Xs cstk›
lemma cstk_ok_len: ‹cstk_ok G Xs cstk ⟹ length cstk = length Xs›
unfolding cstk_ok_def by (simp add: list_all2_conv_all_nth)
lemma cstk_ok_nth:
‹cstk_ok G Xs cstk ⟹ k < length Xs ⟹ cstk ! k = xclosure_auto G (Xs ! k)›
unfolding cstk_ok_def by (auto simp: list_all2_conv_all_nth)
lemma cstk_ok_hd:
‹cstk_ok G Xs cstk ⟹ Xs ≠ [] ⟹ hd cstk = xclosure_auto G (hd Xs)›
using cstk_ok_len cstk_ok_nth[of G Xs cstk 0]
by (metis hd_conv_nth length_0_conv length_greater_0_conv)
lemma cstk_ok_drop:
‹cstk_ok G Xs cstk ⟹ cstk_ok G (drop k Xs) (drop k cstk)›
unfolding cstk_ok_def by (rule list_all2_dropI)
lemma cstk_ok_push:
‹cstk_ok G Xs cstk ⟹ cstk_ok G (f # Xs) (xclosure_auto G f # cstk)›
unfolding cstk_ok_def by simp
text ‹Liveness of a configuration, and the sentinel-safe table plumbing
the driver consults (\<^const>‹la_next› over the goto table; the reduce
cells of \<^const>‹la_fix› bucketed by state).›
fun tok_of :: ‹('t × nat) list ⇒ 't option› where
‹tok_of [] = None›
| ‹tok_of ((a, _) # _) = Some a›
definition dlive :: ‹('n, 't) gconfig ⇒ bool› where
‹dlive gc = (case gc of (Xs, w) ⇒ Xs ≠ [] ∧ live (hd Xs))›
text ‹Sentinel-safe successor lookup.›
definition dnext :: ‹(('n, 't) sym × nat) list list ⇒
('n, 't) citem list list ⇒ nat ⇒ ('n, 't) sym ⇒ nat› where
‹dnext gt sts i X = (if i < length gt then la_next gt sts i X else length sts)›
text ‹Completed cells, bucketed by state index; the reduce cells of the
driver are those of \<^const>‹la_fix›.›
definition cell_buckets :: ‹('n, 't) lacell list ⇒ nat ⇒ ('n, 't) lacell list list› where
‹cell_buckets L n = (let rt = filter (λ(i, itm, t, τ).
snd itm = length (snd (fst itm))) L
in map (λi. filter (λ(i', itm, t, τ). i' = i) rt) [0..<n])›
definition red_buckets :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat ⇒ ('n, 't) lacell list list› where
‹red_buckets G Shn n = cell_buckets (la_fix G Shn) n›
text ‹The ‹parser› command defines the reduce table over its constants for the
automaton and the goto table, which \<^const>‹la_fix› would build again.›
lemma red_buckets_tables:
assumes ‹pr0_states G Shn = sts› and ‹pgtab G sts = gt›
shows ‹red_buckets G Shn (length sts) = cell_buckets (la_fix_gen G Shn gt sts) (length sts)›
using assms unfolding red_buckets_def la_fix_def by simp
text ‹Auxiliary reasoning about \<^const>‹xclosure_auto› and \<^const>‹xgoto›.
The closure only adds slot items (dot at ‹0›), so a kernel item found
in a closure was already in the frame.›
lemma xclosure_auto_kernel:
assumes ‹m > 0› and ‹((pr, m, R)) ∈ set (xclosure_auto G xs)›
shows ‹((pr, m, R)) ∈ set xs›
proof -
have ‹((pr, m, R)) ∈ set (xslots G xs (xiter G xs (xfuel G xs)))›
using assms(2) by (simp add: xclosure_auto_def xclosure_def)
then show ?thesis
by (cases rule: xslots_memE) (use assms(1) in simp_all)
qed
text ‹The extraction lemma for the option ccpo: on a chain, whenever the
pointwise least upper bound is \<^const>‹Some›, some chain element is.
Follows from the shape of \<^text>‹fun_lub› and \<^text>‹flat_lub›.›
subsection ‹Set-valued indentation operations›
text ‹Preimage of an indentation set under a relation: the parent anchors
compatible with some child anchor in ‹R›,
‹{i. ∃j ∈ R. irel_sat r j i}›. For \<^const>‹Gt› and \<^const>‹Ge› this is
the downward closure of the maximum, or everything if ‹R› is unbounded.›
fun irep_pre :: ‹irel ⇒ indrep ⇒ indrep› where
‹irep_pre Eq R = R›
| ‹irep_pre Gt (FinRep xs) = FinRep (filter (λi. list_ex (λx. i < x) xs) [0..<fold max xs 0])›
| ‹irep_pre Gt (UpRep xs n) = UpRep [] 0›
| ‹irep_pre Ge (FinRep xs) = FinRep (filter (λi. list_ex (λx. i ≤ x) xs) [0..<Suc (fold max xs 0)])›
| ‹irep_pre Ge (UpRep xs n) = UpRep [] 0›
| ‹irep_pre Any R = (if irep_nonempty R then UpRep [] 0 else FinRep [])›
lemma fold_max_acc: ‹a ≤ fold max xs (a :: nat)›
proof (induction xs arbitrary: a)
case (Cons y ys)
have ‹a ≤ max y a› by simp
also have ‹… ≤ fold max ys (max y a)› by (rule Cons.IH)
finally show ?case by simp
qed simp
lemma fold_max_ge: ‹x ∈ set xs ⟹ x ≤ fold max xs (a :: nat)›
proof (induction xs arbitrary: a)
case (Cons y ys)
show ?case
proof (cases ‹x = y›)
case True
have ‹y ≤ max y a› by simp
also have ‹… ≤ fold max ys (max y a)› by (rule fold_max_acc)
finally show ?thesis using True by simp
next
case False
with Cons show ?thesis by simp
qed
qed simp
lemma irep_pre_correct [simp]:
‹irep_set (irep_pre r R) = {i. ∃j ∈ irep_set R. irel_sat r j i}›
proof (cases r)
case Eq then show ?thesis by auto
next
case Gt
show ?thesis
proof (cases R)
case (FinRep xs)
have bnd: ‹⋀i. ∃x∈set xs. i < x ⟹ i < fold max xs 0›
using fold_max_ge[of _ xs 0] by (auto intro: less_le_trans)
then show ?thesis using Gt FinRep by (auto simp: list_ex_iff)
next
case (UpRep xs n)
have ‹∃xa ∈ set xs ∪ {m. n ≤ m}. x < xa› for x
by (rule bexI[of _ ‹Suc (max n x)›]) auto
then show ?thesis using Gt UpRep by auto
qed
next
case Ge
show ?thesis
proof (cases R)
case (FinRep xs)
have bnd: ‹⋀i j. j ∈ set xs ⟹ i ≤ j ⟹ i ≤ fold max xs 0›
using fold_max_ge[of _ xs 0] by (auto intro: le_trans)
then show ?thesis using Ge FinRep
by (auto simp: list_ex_iff intro: bnd le_neq_implies_less)
next
case (UpRep xs n)
have ‹∃xa ∈ set xs ∪ {m. n ≤ m}. x ≤ xa› for x
by (rule bexI[of _ ‹max n x›]) auto
then show ?thesis using Ge UpRep by auto
qed
next
case Any
then show ?thesis by (cases R) auto
qed
text ‹Intersection of two indentation sets.›
fun irep_inter :: ‹indrep ⇒ indrep ⇒ indrep› where
‹irep_inter (FinRep xs) R = FinRep (filter (λi. irep_mem i R) xs)›
| ‹irep_inter (UpRep xs n) (FinRep ys) = FinRep (filter (λi. irep_mem i (UpRep xs n)) ys)›
| ‹irep_inter (UpRep xs n) (UpRep ys m) =
UpRep (filter (λi. irep_mem i (UpRep ys m)) xs @ filter (λi. irep_mem i (UpRep xs n)) ys)
(max n m)›
lemma irep_inter_correct [simp]:
‹irep_set (irep_inter R⇩1 R⇩2) = irep_set R⇩1 ∩ irep_set R⇩2›
by (cases R⇩1; cases R⇩2) auto
text ‹Existence of an anchor in ‹R› related by a \<^typ>‹wrel› to a column.›
fun wsat_up :: ‹wrel ⇒ nat ⇒ nat ⇒ bool› where
‹wsat_up WEq c n ⟷ n ≤ c›
| ‹wsat_up WGe c n ⟷ n ≤ c›
| ‹wsat_up WGt c n ⟷ n < c›
| ‹wsat_up WLe c n ⟷ True›
| ‹wsat_up WLt c n ⟷ True›
| ‹wsat_up WAny c n ⟷ True›
lemma wsat_up_correct: ‹wsat_up τ c n ⟷ (∃j ≥ n. wsat τ c j)›
by (cases τ) (auto intro: exI[of _ ‹Suc (max c n)›] exI[of _ ‹max c n›])
fun irep_ex_wsat :: ‹wrel ⇒ nat ⇒ indrep ⇒ bool› where
‹irep_ex_wsat τ c (FinRep xs) = list_ex (wsat τ c) xs›
| ‹irep_ex_wsat τ c (UpRep xs n) = (list_ex (wsat τ c) xs ∨ wsat_up τ c n)›
lemma irep_ex_wsat_correct [simp]:
‹irep_ex_wsat τ c R ⟷ (∃j ∈ irep_set R. wsat τ c j)›
by (cases R) (auto simp: list_ex_iff wsat_up_correct)
subsection ‹Set-valued goto›
text ‹Advance the dot over ‹X› whose anchor is known to lie in ‹RA›; every
item keeps the anchors compatible with some element of ‹RA›. For a terminal
‹RA› is the singleton of its column and this is \<^const>‹xgoto› up to the
list representation of the indentation sets.›
definition lgoto :: ‹('n, 't) xitem list ⇒ ('n, 't) sym ⇒ indrep ⇒ ('n, 't) xitem list› where
‹lgoto xs X RA =
map (λ(pr, m, R). (pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA)))
(filter (λ(pr, m, R). m < length (snd pr) ∧ fst (snd pr ! m) = X) xs)›
lemma lgoto_dot_pos: ‹((pr, m, R)) ∈ set (lgoto xs X RA) ⟹ m > 0›
unfolding lgoto_def by (auto simp: image_iff)
lemma lgoto_kernel_step:
assumes ‹((pr, Suc m, R')) ∈ set (lgoto xs X RA)›
obtains R where ‹((pr, m, R)) ∈ set xs›
and ‹m < length (snd pr)›
and ‹fst (snd pr ! m) = X›
and ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) RA)›
using assms unfolding lgoto_def by (auto simp: image_iff)
lemma lgoto_memI:
assumes ‹((pr, m, R)) ∈ set xs› and ‹m < length (snd pr)› and ‹fst (snd pr ! m) = X›
shows ‹((pr, Suc m, irep_inter R (irep_pre (snd (snd pr ! m)) RA))) ∈ set (lgoto xs X RA)›
using assms unfolding lgoto_def by force
text ‹The anchor set of a reduce: the union over the completed items of the
production in the closure (there is one, but the union needs no
distinctness argument).›
definition red_set :: ‹('n, 't) xitem list ⇒ 'n × ('n, 't) rhs ⇒ indrep› where
‹red_set CL pr = foldr (λ(pr', m, R) acc.
if pr' = pr ∧ m = length (snd pr) then irep_union R acc else acc) CL (FinRep [])›
lemma red_set_correct:
‹irep_set (red_set CL pr) =
⋃ {irep_set R | R. ((pr, length (snd pr), R)) ∈ set CL}›
unfolding red_set_def
by (induction CL) (auto split: prod.splits if_splits)
lemma red_set_nonempty_iff:
‹irep_nonempty (red_set CL pr) ⟷
(∃R. ((pr, length (snd pr), R)) ∈ set CL ∧ irep_nonempty R)›
by (auto simp: red_set_correct)
subsection ‹The set-anchored machine›
text ‹Actions carry no anchor: a reduce is determined by its production. The
step reads the frame closures off a cache stack running in lockstep with the
frame stack; \<^text>‹mstep› is the cache-free form.›