Theory LR_Det
theory LR_Det
imports LR_Driver
begin
section ‹The static sufficient condition for \<^const>‹mdet››
text ‹This theory proves ‹rlalr_conflicts G Shn = [] ⟹ mdet G Shn›
(\<^text>‹rlalr_sufficient›, at the end): an executable check on the
driver's tables implies the determinism premise of its completeness.
After Barthwal \<^cite>‹‹Def.~5.3.7, Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› (‹okSlr›: conflict
freedom is demanded on viable-prefix-reachable states only), DeRemer and
Pennello \<^cite>‹‹Sect.~3› in "deremer1982-lalr-lookahead"› (per-item lookahead) and Jourdan, Pottier and
Leroy \<^cite>‹‹Sect.~3.4, Thm.~4› in "jourdan2012-validating-lr1"› (a validator on the automaton; the validators imply
unambiguity).
In order: saturation of the anchored reachable closure; the precise
(viable-prefix) automaton \<^text>‹pr0_states› and its worklist; the
rigid-point conflict analysis \<^text>‹rlalr_conflicts›; tracking every
reachable configuration by the driver's index stack; the pooled width
invariant; the canonical tracked stack \<^text>‹strack› and its descent;
the soundness of the rigid-point walk, from which
\<^text>‹rlalr_sufficient› follows.›
section ‹Saturation of the anchored reachable closure›
text ‹The report and the check read the fuelled \<^const>‹wreach›, which is
total; this section shows it is saturated. The general argument:
\<^const>‹wreach_step› only emits dot-0 items, so regardless of the kernel the
chain grows by at most one item per production per \<^typ>‹wrel›, which is
\<^const>‹wreach›'s fuel. \<^text>‹funpow_saturates› bounds the chain by
\<^term>‹card U› for a universe \<^term>‹U› containing the start, too coarse
here; the variant below bounds it by the increment.›
subsection ‹\<^const>‹wreach_step› is extensional, monotone, and dot-0 bounded›
text ‹\<^const>‹wreach_step› inlines its contribution function; name it for the
set-level reasoning below.›
definition wcontrib :: ‹('n, 't) is_cfg ⇒ ('n, 't) witem ⇒ ('n, 't) witem list› where
‹wcontrib G = (λ(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 [])›
lemma wreach_step_alt:
‹wreach_step G ws = remdups (ws @ concat (map (wcontrib G) ws))›
unfolding wreach_step_def wcontrib_def by simp
lemma wreach_step_set:
‹set (wreach_step G xs) = set xs ∪ (⋃x ∈ set xs. set (wcontrib G x))›
unfolding wreach_step_alt by auto
lemma wreach_step_ext:
‹set xs = set ys ⟹ set (wreach_step G xs) = set (wreach_step G ys)›
by (simp add: wreach_step_set)
lemma wreach_step_mono: ‹set xs ⊆ set (wreach_step G xs)›
by (simp add: wreach_step_set)
text ‹Every item \<^const>‹wreach_step› emits sits at dot 0 on a production of
the grammar; this bounds the growth independently of the kernel.›
definition wdot0 :: ‹('n, 't) is_cfg ⇒ ('n, 't) witem list› where
‹wdot0 G = concat (map (λpr. map (λρ. (pr, 0, ρ))
[WEq, WGe, WGt, WLe, WLt, WAny]) (iprods G))›
lemma wdot0_mem: ‹pr ∈ set (iprods G) ⟹ (pr, 0, ρ) ∈ set (wdot0 G)›
unfolding wdot0_def by (cases ρ) force+
lemma length_wdot0: ‹length (wdot0 G) = length (iprods G) * 6›
proof -
have ‹length (concat (map (λpr. [(pr, 0, WEq), (pr, 0, WGe), (pr, 0, WGt),
(pr, 0, WLe), (pr, 0, WLt), (pr, 0, WAny)]) ps)) = length ps * 6›
for ps :: ‹('n × ('n, 't) rhs) list›
by (induction ps) auto
then show ?thesis unfolding wdot0_def by simp
qed
lemma wcontrib_simp:
‹wcontrib G (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 [])›
unfolding wcontrib_def by simp
lemma wcontrib_dot0:
assumes ‹y ∈ set (wcontrib G x)›
shows ‹y ∈ set (wdot0 G)›
proof -
obtain pr m ρ where x: ‹x = (pr, m, ρ)› by (cases x) auto
show ?thesis
proof (cases ‹m < length (snd pr)›)
case False
then show ?thesis using assms unfolding x wcontrib_simp by simp
next
case True
show ?thesis
proof (cases ‹fst (snd pr ! m)›)
case (Tm a)
then show ?thesis using assms True unfolding x wcontrib_simp by simp
next
case (Nt B)
have ‹y ∈ set (map (λbr. (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ))
(filter (λbr. fst br = B) (iprods G)))›
using assms True Nt unfolding x wcontrib_simp by simp
then obtain br where br: ‹br ∈ set (iprods G)›
and yeq: ‹y = (br, 0, wcomp (winv (w_of (snd (snd pr ! m)))) ρ)› by auto
show ?thesis unfolding yeq by (rule wdot0_mem[OF br])
qed
qed
qed
lemma wreach_step_delta: ‹set (wreach_step G xs) ⊆ set xs ∪ set (wdot0 G)›
by (auto simp: wreach_step_set dest: wcontrib_dot0)
subsection ‹Hence the fuelled \<^const>‹wreach› is saturated›
theorem wreach_stable: ‹set (wreach_step G (wreach G s)) = set (wreach G s)›
unfolding wreach_def
proof (rule funpow_saturates_delta[where D = ‹set (wdot0 G)›])
show ‹⋀xs ys. set xs = set ys ⟹ set (wreach_step G xs) = set (wreach_step G ys)›
by (rule wreach_step_ext)
show ‹⋀xs. set xs ⊆ set (wreach_step G xs)› by (rule wreach_step_mono)
show ‹⋀xs. set (wreach_step G xs) ⊆ set xs ∪ set (wdot0 G)›
by (rule wreach_step_delta)
show ‹finite (set (wdot0 G))› by simp
show ‹card (set (wdot0 G)) ≤ Suc (length (iprods G) * 6)›
using card_length[of ‹wdot0 G›] length_wdot0[of G] by simp
qed
lemma funpow_wreach_mono: ‹set xs ⊆ set ((wreach_step G ^^ k) xs)›
proof (induction k)
case (Suc k)
have ‹set ((wreach_step G ^^ k) xs) ⊆ set ((wreach_step G ^^ Suc k) xs)›
using wreach_step_mono by simp
with Suc show ?case by simp
qed simp
lemma wreach_kernel: ‹set (wkernel s) ⊆ set (wreach G s)›
unfolding wreach_def by (rule funpow_wreach_mono)
text ‹\<^const>‹wreach› is saturated, so it contains everything one
\<^const>‹wreach_step› would add.›
lemma wreach_emit:
assumes mem: ‹(pr', m', ρ') ∈ set (wreach G s)›
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, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ') ∈ set (wreach G s)›
proof -
have ‹(br, 0, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ')
∈ set (wcontrib G (pr', m', ρ'))›
unfolding wcontrib_simp using m_lt nxt br by simp
then have ‹(br, 0, wcomp (winv (w_of (snd (snd pr' ! m')))) ρ')
∈ set (wreach_step G (wreach G s))›
using mem by (auto simp: wreach_step_set)
then show ?thesis unfolding wreach_stable .
qed
section ‹The item-relative conflict analysis: diagnosis›
text ‹Why the entry-relative walk below cannot separate the remaining
states, on the state after ‹"type" LId TVars› of an ML-style signature
grammar (state 7 of \<^const>‹pr0_states›). Its kernel holds
‹Spec = "type"⇧= LId⇧> TVars⇧> ⋅›, the same production continued by
‹"=" Ty›, and ‹TVars = TVars⇧≥ ⋅ LId⇧≥›. The entry anchor is the anchor
of the ‹TVars› subtree just read, and \<^const>‹wreach› relates it to each
item's own indentation: ‹WGt› for the two ‹Spec› items (‹TVars⇧>›), ‹WGe›
for the ‹TVars› item (‹TVars⇧≥›). The shift cell on ‹LId› composes the
inverse of that ‹WGe› with the element relation ‹LId⇧≥›:
‹wcomp WLe WGe = WAny›. The token is at or right of the inner ‹TVars›'
indentation, which is at or left of the anchor; nothing relates the token
to the anchor. The reduce seeds on ‹LId› are the cells ‹WEq› (the next
spec of the same block) and ‹WLt› (the next spec of an enclosing block,
through ‹"module" UId ":" Sig⇧>›), each composed with ‹winv WGt›: ‹WLt›.
So the pair at the state is ‹(WLt, WAny)›, and no entry further back
recovers a class from ‹WAny›. The ‹WAny› is the item's: the shift side
is a relation to the ‹TVars› item's indentation, the reduce side a
relation to the ‹Spec› item's, and the entry anchor is ‹≥›-related to
the one and ‹>›-related to the other, so the anchor is the wrong
quantity to express either against.
Expressed against the ‹Spec› item's own indentation both sides are
exact. The reduce side already is: a cell relates the lookahead's column
to the completed item's left-hand-side indentation (‹WEq›, ‹WLt›). The
shift side is translated through the items that predicted it. The
‹TVars› item at dot 1 was predicted one entry back, in the state after
‹"type" LId› (state 8), whose kernel is the two ‹Spec› items at dot 2; the
predictors of ‹TVars› in that state's closure are those two items (through
‹TVars⇧>›: the ‹TVars› indentation is strictly right of the ‹Spec›'s) and
the ‹TVars› item itself (left recursion through ‹TVars⇧≥›, which only
repeats). The shift side becomes ‹wcomp WGt WGe = WGt› against the
‹Spec› item's indentation, the reduce side is ‹WEq› or ‹WLt› against the
same item's indentation, popped along the same entry, and the two are
\<^const>‹wdisjoint›.
The comparison is sound because the reference is one column. ‹Spec› is
anchored (‹anchored_nts› below: ‹"type"⇧=›), so in the real frame every
‹Spec› item at a dot ‹≥ 1› has the singleton pool ‹{column of "type"}›,
and two such items at the same dot in the same frame read that ‹"type"›
at the same entry; both sides' relations hold at that column, a disjoint
pair is impossible. At a nonterminal whose pool is not a singleton the
two sides may be satisfied at different pool elements and disjointness
proves nothing: that is the two-action layout of an unanchored
nonterminal (a constructor list, an arrow-type tail), which anchoring that
nonterminal removes. The other sound reference is the start item at the
start state, whose pool is ‹{istart_ind}›.
The walk that follows from this (the next section): a triple is a state
with two cursors, each an item of the state's closure and a class relating
the lookahead's column to the item's left-hand-side indentation. A cursor
at dot 0 is replaced by its predictors in the same state, the class
composed with the predicted position's relation; two cursors at kernel
items pop one entry along the same edge of the precise automaton (the
entry symbol is the symbol before both dots), the classes unchanged, and
where that entry is rigid both are first read against its column and a
disjoint pair is refuted. The ‹Spec› pair above is refuted one pop later,
at the state entered over ‹"type"›. At the start state both cursors predict
up to the start item and are compared there. No entry anchor, no
‹rho_classes›, no ‹tm_classes›.›
section ‹The item-relative conflict analysis›
text ‹Comparing the two sides of a candidate pair against a single shared
state anchor is unsound for \<^const>‹mdet›: a reduce-built frame pools
entry anchors, and the two sides can be live via different ones. The
comparison is sound only where both sides are read against one column: the
column of a shifted token, the anchor of an anchored nonterminal, or
‹istart_ind› at the start state. So the analysis keeps each side on its
item. A cursor is a \<^typ>‹('n, 't) witem› read item-relatively: in
‹(pr, m, σ)› the class ‹σ› relates the lookahead's column to the
indentation of the instance of ‹pr›'s left-hand side the item stands for.
A reduce seed is the completed item with its cell's relation, a shift seed
the item whose dotted terminal is the lookahead, with that terminal's
relation. The walk goes back through the entries of the precise automaton
as far as the start state: a cursor at dot 0 moves to the items that
predicted it (the predicting position's relation composes, the state stays);
two cursors at kernel items move together to every predecessor along the
state's entry, unchanged. \<^const>‹wdisjoint› runs where the entry is
rigid, both cursors read against the entry's column through the relation
of the symbol before their dots: a disjoint pair refutes the path, a pair
that is not disjoint walks on, since the entry that separates the two
sides may lie further back. A pair that reaches the start item undisjoint
is a conflict. The walk is a worklist over triples (state, cursor,
cursor) in a finite space; exhausted fuel reports a conflict, and so does a
triple with both classes ‹WAny›: nothing composes out of ‹WAny›, so
every descendant of such a triple is one, none is disjoint, and the walk
would only reach the start item undisjoint; returning at once saves the
walk.›
text ‹The analysis runs over the precise automaton (\<^const>‹pr0_states›
with the \<^const>‹pgtab› gotos and the \<^const>‹la_fix› cells): these
are the driver's own tables, so a cell that licenses a runtime reduce is one
of the cells inspected here.›
definition pin_edges :: ‹(('n, 't) sym × nat) list list ⇒ nat ⇒
(nat × ('n, 't) sym) list› where
‹pin_edges gt s = concat (map (λp.
map (λ(X, s'). (p, X)) (filter (λ(X, s'). s' = s) (gt ! p)))
[0..<length gt])›
text ‹All static reads below use \<^const>‹wreach›, the form the saturation
lemmas of this theory speak about; the classes it carries are not used.›
text ‹A nonterminal ‹A› is ‹anchored› when every ‹A›-production starts with
an ‹Eq›-related element that is a terminal or itself an anchored
nonterminal: any tree of ‹A› then admits exactly one anchor, the column of
its leftmost token (cf. the ‹anchored›/‹lead_refl› analysis of
‹Indentation_Sensitive› section 4). A reduce-goto over an anchored
nonterminal therefore carries a ‹rigid› entry anchor, a token column
shared by both sides of a pair, and the \<^const>‹wdisjoint› comparison
is sound there, as at a shift entry. Computed as a decreasing fixpoint
from the full nonterminal list.›
definition anchored_nts :: ‹('n, 't) is_cfg ⇒ 'n list› where
‹anchored_nts G = (let nts = remdups (map fst (iprods G));
ok = (λS (B, rhs). rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
(case fst (hd rhs) of Tm _ ⇒ True | Nt B' ⇒ B' ∈ set S));
step = (λS. filter (λA. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)) S)
in (step ^^ length nts) nts)›
definition irigid :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
‹irigid anc X ⟷ (case X of Tm _ ⇒ True | Nt B ⇒ B ∈ set anc)›
text ‹The walk reads the states' closures from ‹wrs›, the list of their
\<^const>‹wreach› lists, computed once for all states. The cursors that
predicted an ‹A›-item at dot 0 in state ‹s›: the items of ‹s› with
‹Nt A› at the dot, the class composed with that position's relation (the
predicted indentation relates by it to the predictor's).›
definition ipreds :: ‹('n, 't) witem list list ⇒ nat ⇒ 'n ⇒ wrel ⇒
('n, 't) witem list› where
‹ipreds wrs s A σ = remdups (List.map_filter (λ(pr, m, _).
if m < length (snd pr) ∧ fst (snd pr ! m) = Nt A
then Some (pr, m, wcomp (w_of (snd (snd pr ! m))) σ) else None)
(wrs ! s))›
text ‹Whether a closure holds an item, in any class.›
definition ihas :: ‹('n, 't) witem list ⇒ 'n × ('n, 't) rhs ⇒ nat ⇒ bool› where
‹ihas ws pr m ⟷ list_ex (λ(pr', m', _). pr' = pr ∧ m' = m) ws›
text ‹A kernel cursor read against the column of the state's entry, through
the relation of the symbol before its dot (the kernel item's pool was
filtered by that relation against the entry pool).›
definition itrans :: ‹('n, 't) witem ⇒ wrel› where
‹itrans = (λ(pr, m, σ). wcomp (winv (w_of (snd (snd pr ! (m - 1))))) σ)›
text ‹The walk's terminal triples: both classes ‹WAny›; two cursors on the
start item that are not disjoint against ‹istart_ind›; a triple no frame
can hold (one cursor on the start item, the other at a kernel item; two
kernel items with different symbols before the dot), reported rather than
carrying a proof that it is dead, which the precise automaton never
produces. Two cursors on the start item that are disjoint have no
successor.›
fun ifires :: ‹'n ⇒ 'n list ⇒ nat × ('n, 't) witem × ('n, 't) witem ⇒ bool› where
‹ifires Shn anc (s, (pr⇩1, m⇩1, σ⇩1), (pr⇩2, m⇩2, σ⇩2)) ⟷
σ⇩1 = WAny ∧ σ⇩2 = WAny ∨
(if m⇩1 = 0 ∧ fst pr⇩1 = Shn ∧ m⇩2 = 0 ∧ fst pr⇩2 = Shn then ¬ wdisjoint σ⇩1 σ⇩2
else if m⇩1 = 0 ∧ fst pr⇩1 ≠ Shn ∨ m⇩2 = 0 ∧ fst pr⇩2 ≠ Shn then False
else m⇩1 = 0 ∨ m⇩2 = 0 ∨ fst (snd pr⇩1 ! (m⇩1 - 1)) ≠ fst (snd pr⇩2 ! (m⇩2 - 1)))›
text ‹The successors of a triple: the left cursor at dot 0 predicted first,
then the right; two kernel cursors with the same symbol before the dot pop
together along every entry of the state whose source state holds both
popped items, unless the entry is rigid and they are disjoint against its
column.›
fun isuccs :: ‹'n ⇒ ('n, 't) witem list list ⇒ (('n, 't) sym × nat) list list ⇒
'n list ⇒ nat × ('n, 't) witem × ('n, 't) witem ⇒
(nat × ('n, 't) witem × ('n, 't) witem) list›
where
‹isuccs Shn wrs gt anc (s, (pr⇩1, m⇩1, σ⇩1), (pr⇩2, m⇩2, σ⇩2)) =
(if m⇩1 = 0 ∧ fst pr⇩1 = Shn ∧ m⇩2 = 0 ∧ fst pr⇩2 = Shn then []
else if m⇩1 = 0 ∧ fst pr⇩1 ≠ Shn
then map (λc. (s, c, (pr⇩2, m⇩2, σ⇩2))) (ipreds wrs s (fst pr⇩1) σ⇩1)
else if m⇩2 = 0 ∧ fst pr⇩2 ≠ Shn
then map (λc. (s, (pr⇩1, m⇩1, σ⇩1), c)) (ipreds wrs s (fst pr⇩2) σ⇩2)
else if m⇩1 = 0 ∨ m⇩2 = 0 then []
else (let X = fst (snd pr⇩1 ! (m⇩1 - 1)) in
if X ≠ fst (snd pr⇩2 ! (m⇩2 - 1)) ∨
irigid anc X ∧ wdisjoint (itrans (pr⇩1, m⇩1, σ⇩1)) (itrans (pr⇩2, m⇩2, σ⇩2))
then []
else List.map_filter (λ(p, X'). if X' = X ∧
ihas (wrs ! p) pr⇩1 (m⇩1 - 1) ∧ ihas (wrs ! p) pr⇩2 (m⇩2 - 1)
then Some (p, (pr⇩1, m⇩1 - 1, σ⇩1), (pr⇩2, m⇩2 - 1, σ⇩2)) else None)
(pin_edges gt s)))›
text ‹The walk: a worklist with a seen set, each triple popped at most once.›
primrec ifire :: ‹'n ⇒ ('n, 't) witem list list ⇒ (('n, 't) sym × nat) list list ⇒
'n list ⇒ nat ⇒ (nat × ('n, 't) witem × ('n, 't) witem) list ⇒
(nat × ('n, 't) witem × ('n, 't) witem) list ⇒ bool› where
‹ifire Shn wrs gt anc 0 seen work = True›
| ‹ifire Shn wrs gt anc (Suc n) seen work =
(case work of
[] ⇒ False
| t # wk ⇒
if ifires Shn anc t then True
else ifire Shn wrs gt anc n (t # seen)
(filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
(remdups (isuccs Shn wrs gt anc t)) @ wk))›
lemma ifire_Nil [simp]: ‹ifire Shn wrs gt anc (Suc n) seen [] = False›
by simp
lemma ifire_Cons [simp]:
‹ifire Shn wrs gt anc (Suc n) seen (t # wk) =
(if ifires Shn anc t then True
else ifire Shn wrs gt anc n (t # seen)
(filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
(remdups (isuccs Shn wrs gt anc t)) @ wk))›
by simp
text ‹Fuel for the triples the walk can visit: both cursors of a triple at
state ‹s› are items of ‹s›'s closure (the seeds and the predictions are
drawn from it, a pop is kept only if its target holds both items), each in
one of six classes, and the worklist pops a triple at most once. Naturals
are unary in the generated code, so the bound is the sum over the states of
the squared item counts, not a square of the grammar's size.›
definition ifuel :: ‹('n, 't) witem list list ⇒ nat› where
‹ifuel wrs = Suc (36 * sum_list (map (λws.
let n = length (remdups (map (λ(pr, m, _). (pr, m)) ws)) in n * n) wrs))›
text ‹Reduce seeds at a state: one per cell of a production completed in the
precise closure, the cursor's class the cell's own relation; the lookahead
stays with it. A completed production the precise context excludes seeds
nothing; the runtime's anchor filtering excludes it dynamically.›
definition ireds_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list ⇒ nat ⇒ ('t option × ('n, 't) witem) list› where
‹ireds_at G Shn sp L i =
(let ws = wreach G (sp ! i)
in List.map_filter (λ(i', (pr, m), t, τ).
if i' = i ∧ m = length (snd pr) ∧ fst pr ≠ Shn ∧
list_ex (λ(pr', m', ρ). pr' = pr ∧ m' = m) ws
then Some (t, (pr, m, τ)) else None) L)›
text ‹Shift seeds: the items with a terminal at the dot, the class that
terminal's relation.›
definition ishifts :: ‹('n, 't) witem list ⇒ ('t × ('n, 't) witem) list› where
‹ishifts ws = remdups (List.map_filter (λ(pr, m, ρ).
if m < length (snd pr)
then (case fst (snd pr ! m) of
Tm a ⇒ Some (a, (pr, m, w_of (snd (snd pr ! m)))) | Nt _ ⇒ None)
else None) ws)›
definition rr_none_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list ⇒ nat ⇒ bool› where
‹rr_none_at G Shn sp L i =
(let reds = ireds_at G Shn sp L i
in list_ex (λ(t, c). t = None ∧
list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None) reds) reds)›
definition ipairs_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list ⇒ nat ⇒ (('n, 't) witem × ('n, 't) witem) list› where
‹ipairs_at G Shn sp L i =
(let reds = ireds_at G Shn sp L i;
shifts = ishifts (wreach G (sp ! i));
srs = concat (map (λ(t, c). case t of
Some a ⇒ map (λ(a', c'). (c, c')) (filter (λ(a', c'). a' = a) shifts)
| None ⇒ []) reds);
rrs = concat (map (λ(t, c). List.map_filter (λ(t', c').
if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None) reds)
reds)
in remdups (srs @ rrs))›
definition rlalr_conflict_at :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list ⇒
('n, 't) lacell list ⇒ nat ⇒ bool› where
‹rlalr_conflict_at G Shn sp L i ⟷
rr_none_at G Shn sp L i ∨
list_ex (λ(c⇩1, c⇩2). ifire Shn (map (wreach G) sp) (pgtab G sp) (anchored_nts G)
(ifuel (map (wreach G) sp)) [] [(i, c⇩1, c⇩2)])
(ipairs_at G Shn sp L i)›
definition rlalr_conflicts :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
‹rlalr_conflicts G Shn = (let sp = pr0_states G Shn; L = la_fix G Shn in
filter (rlalr_conflict_at G Shn sp L) [0..<length sp])›
section ‹From a determinism violation to concrete witnesses›
text ‹Eliminations for the sufficiency proof: the negation of
\<^const>‹mdet› yields concrete witnesses, the cell that licensed each
reduce candidate and the closure item and anchor that keep each successor
alive.›
lemma liveE:
assumes ‹live xs›
obtains pr m R j where ‹(pr, m, R) ∈ set xs› and ‹j ∈ irep_set R›
using assms that unfolding live_def
by (fastforce simp: list_ex_iff)
lemma dliveE:
assumes ‹dlive (Xs, w)›
obtains pr m R j where ‹Xs ≠ []› and ‹(pr, m, R) ∈ set (hd Xs)›
and ‹j ∈ irep_set R›
using assms that unfolding dlive_def by (auto elim: liveE)
lemma dlicE:
assumes ‹dlic i cells ((a, c) # w') pr RS›
obtains τ where ‹(i, (pr, length (snd pr)), Some a, τ) ∈ set cells›
and ‹irep_ex_wsat τ c RS›
using assms that unfolding dlic_def by (fastforce simp: list_ex_iff)
lemma dlic_NilE:
assumes ‹dlic i cells [] pr RS›
obtains τ where ‹(i, (pr, length (snd pr)), None, τ) ∈ set cells›
using assms that unfolding dlic_def by (fastforce simp: list_ex_iff)
text ‹A live shift successor yields a closure item with the shifted terminal
at its dot and an anchor compatible with the token's column.›
lemma shift_live_srcE:
assumes step: ‹mstep_cached G cstk (Xs, w) DShift = Some gc'›
and live: ‹dlive gc'›
obtains a c w' pr m R j where
‹w = (a, c) # w'›
and ‹(pr, m, R) ∈ set (hd cstk)›
and ‹m < length (snd pr)›
and ‹fst (snd pr ! m) = Tm a›
and ‹j ∈ irep_set R›
and ‹irel_sat (snd (snd pr ! m)) c j›
proof -
from step obtain a c w' where
w: ‹w = (a, c) # w'› and Xs_ne: ‹Xs ≠ []›
and gc': ‹gc' = (lgoto (hd cstk) (Tm a) (FinRep [c]) # Xs, w')›
by (rule mstep_shift_shape)
from live obtain pr m' R' j where
itm: ‹(pr, m', R') ∈ set (lgoto (hd cstk) (Tm a) (FinRep [c]))›
and jR': ‹j ∈ irep_set R'›
unfolding gc' by (auto elim: dliveE)
obtain m where m': ‹m' = Suc m› using lgoto_dot_pos[OF itm] by (cases m') auto
from lgoto_kernel_step[OF itm[unfolded m']] obtain R where
src: ‹(pr, m, R) ∈ set (hd cstk)› and m_lt: ‹m < length (snd pr)›
and sym: ‹fst (snd pr ! m) = Tm a›
and R': ‹R' = irep_inter R (irep_pre (snd (snd pr ! m)) (FinRep [c]))› .
have jR: ‹j ∈ irep_set R› and jrel: ‹irel_sat (snd (snd pr ! m)) c j›
using jR' unfolding R' by auto
from that[OF w src m_lt sym jR jrel] show thesis .
qed
section ‹Tracking a reachable configuration›
text ‹The dynamic half of the sufficiency argument: every configuration the
indexed machine reaches is tracked, frame by frame, by the driver's own
index stack under \<^const>‹didx_ok›. A frame owes its obligations only
where it has a ‹live› (anchored) item: a dead frame never contributes a
candidate, and by ‹xclosure_auto_live_creach› over the empty kernel a
dead kernel has a dead closure. Where the pushed frame is live the table's
goto is the canonical successor index, so the index stack also records the
goto history the descent below walks.›
lemma dnext_st_find:
assumes tab: ‹tables_ok G Shn sts gt L›
and ok: ‹didx_ok G sts Xs istk›
and d_lt: ‹d < length Xs›
and live: ‹lcore (lgoto (xclosure_auto G (Xs ! d)) X RA) ≠ {}›
shows ‹dnext gt sts (istk ! d) X = st_find sts (cgoto (creach G (sts ! (istk ! d))) X)›
proof -
from live obtain pr⇩0 n⇩0 R⇩0' j⇩0 where
g0: ‹(pr⇩0, n⇩0, R⇩0') ∈ set (lgoto (xclosure_auto G (Xs ! d)) X RA)›
and j0: ‹j⇩0 ∈ irep_set R⇩0'›
unfolding lcore_def by auto
obtain m⇩0 where n0: ‹n⇩0 = Suc m⇩0› using lgoto_dot_pos[OF g0] by (cases n⇩0) auto
from lgoto_kernel_step[OF g0[unfolded n0]] obtain R⇩0 where
src0: ‹(pr⇩0, m⇩0, R⇩0) ∈ set (xclosure_auto G (Xs ! d))›
and m0_lt: ‹m⇩0 < length (snd pr⇩0)› and X0: ‹fst (snd pr⇩0 ! m⇩0) = X›
and R0': ‹R⇩0' = irep_inter R⇩0 (irep_pre (snd (snd pr⇩0 ! m⇩0)) RA)› .
have j0R0: ‹j⇩0 ∈ irep_set R⇩0› using j0 unfolding R0' by auto
have f_live: ‹lcore (Xs ! d) ≠ {}› by (rule closure_live_kernel[OF src0 j0R0])
from didx_okD[OF ok d_lt f_live] have p_lt: ‹istk ! d < length sts›
and cover: ‹lcore (Xs ! d) ⊆ set (sts ! (istk ! d))› by auto
have kern: ‹⋀pr m R. (pr, m, R) ∈ set (Xs ! d) ⟹ irep_nonempty R ⟹
(pr, m) ∈ set (sts ! (istk ! d))›
using cover by (fastforce simp: lcore_def)
have src0_cr: ‹(pr⇩0, m⇩0) ∈ set (creach G (sts ! (istk ! d)))›
by (rule xclosure_auto_live_creach[OF kern src0 j0R0])
have lookup0: ‹map_of (gt ! (istk ! d)) (fst (snd pr⇩0 ! m⇩0)) =
Some (st_find sts (cgoto (creach G (sts ! (istk ! d))) (fst (snd pr⇩0 ! m⇩0))))›
using tab p_lt src0_cr m0_lt unfolding tables_ok_def by blast
have lookup: ‹map_of (gt ! (istk ! d)) X =
Some (st_find sts (cgoto (creach G (sts ! (istk ! d))) X))›
using lookup0 unfolding X0 .
have gt_len: ‹length gt = length sts› using tab unfolding tables_ok_def by blast
show ?thesis
unfolding dnext_def la_next_def lookup option.case
using p_lt gt_len by (simp add: min_def st_find_le)
qed
text ‹A cell of the driver's reduce bucket ‹i› is a completed cell of
\<^const>‹la_fix› at index ‹i›.›
lemma red_buckets_memD:
assumes ‹i < n› and ‹c ∈ set (red_buckets G Shn n ! i)›
shows ‹c ∈ set (la_fix G Shn) ∧ fst c = i ∧
(case c of (i', itm, t, τ) ⇒ snd itm = length (snd (fst itm)))›
using assms unfolding red_buckets_def cell_buckets_def by (auto simp: Let_def)
section ‹Accept/reduce conflicts›
text ‹The case \<^const>‹rlalr_conflicts› ignores: the start production
completed next to an end-of-input reduce cell of another production, the
driver accepting where the relation of the grammar has a second value.›
definition acc_conflicts :: ‹('n, 't) is_cfg ⇒ 'n ⇒ nat list› where
‹acc_conflicts G Shn = (let sts = pr0_states G Shn in
filter (λi. (start_prod G Shn, Suc 0) ∈ set (sts ! i) ∧
list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
t = None ∧ pr ≠ start_prod G Shn) (la_fix G Shn))
[0..<length sts])›
text ‹Reducing by the start production is dead: nothing in the initial
closure expects \<^term>‹Nt Shn›.›
lemma lgoto_xinit_Shn:
assumes fn: ‹fresh_name G Shn›
shows ‹lgoto (xclosure_auto G (xinit G Shn)) (Nt Shn) RA = []›
proof -
have ‹¬ (m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn)›
if item: ‹(pr, m, R) ∈ set (xclosure_auto G (xinit G Shn))› for pr m R
proof
assume ‹m < length (snd pr) ∧ fst (snd pr ! m) = Nt Shn›
then have m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = Nt Shn› by auto
from dshape_prods[OF dshape_init, of 0 pr m R] item
have ‹pr ∈ set (iprods G) ∨ pr = start_prod G Shn› by simp
then show False
proof
assume prG: ‹pr ∈ set (iprods G)›
have ‹snd pr ! m ∈ set (snd pr)› using m by simp
with fn prG X show False
unfolding fresh_name_def by (cases pr; cases ‹snd pr ! m›) fastforce
next
assume ‹pr = start_prod G Shn›
with m X fn show False unfolding start_prod_def fresh_name_def by simp
qed
qed
then show ?thesis unfolding lgoto_def by (auto simp: filter_empty_conv)
qed
lemma final_shape:
assumes fn: ‹fresh_name G Shn›
and inv: ‹dinv G Shn w ((Xs, u), cstk, istk, v, tstk)›
and fin: ‹gfinal G Shn (Xs, u)›
shows ‹∃X. Xs = [X, xinit G Shn]›
proof -
have fin': ‹gfinal G Shn (fst ((Xs, u), cstk, istk, v, tstk))› using fin by simp
from dinv_final[OF fn inv fin'] obtain t where tstk: ‹tstk = [t]› by auto
from inv obtain RAs where lenR: ‹length RAs = length tstk›
and sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
unfolding dinv_def by auto
have ‹length Xs = 2› ‹Xs ! 1 = xinit G Shn›
using sh lenR tstk unfolding dshape_def by auto
then show ?thesis
by (cases Xs) (auto simp: length_Suc_conv)
qed
text ‹With an empty accept/reduce report, no live reduce is offered at an
accepting configuration.›
lemma no_reduce_at_final:
assumes fn: ‹fresh_name G Shn› and chk: ‹acc_conflicts G Shn = []›
and inv: ‹dinv G Shn w ((Xs, u), cstk, istk, v, tstk)›
and ok: ‹didx_ok G (pr0_states G Shn) Xs istk›
and fin: ‹gfinal G Shn (Xs, u)›
and cand: ‹DReduce pr ∈ set (dcands G (hd istk)
(red_buckets G Shn (length (pr0_states G Shn)) ! hd istk)
(xclosure_auto G (hd Xs)) (Xs, u))›
and step: ‹mstep G (Xs, u) (DReduce pr) = Some gc'› and live: ‹dlive gc'›
shows False
proof -
let ?sts = ‹pr0_states G Shn› and ?i = ‹hd istk›
from final_shape[OF fn inv fin] obtain X where Xs: ‹Xs = [X, xinit G Shn]› by blast
have u: ‹u = []› using fin unfolding gfinal_def by simp
have istk_ne: ‹istk ≠ []› using didx_ok_len[OF ok] Xs by auto
from fin obtain pr⇩0 R where item: ‹(pr⇩0, Suc 0, R) ∈ set X› and Shn: ‹fst pr⇩0 = Shn›
and mem: ‹irep_mem (istart_ind G) R›
unfolding gfinal_def Xs by (auto simp: list_ex_iff)
have lv: ‹(pr⇩0, Suc 0) ∈ lcore X› using lcoreI[OF item, of ‹istart_ind G›] mem by simp
have i_lt: ‹?i < length ?sts› and cover: ‹lcore X ⊆ set (?sts ! ?i)›
using didx_okD[OF ok, of 0] lv Xs istk_ne by (auto simp: hd_conv_nth)
from inv obtain RAs where sh: ‹dshape G Shn Xs (zip (map asym tstk) RAs)›
unfolding dinv_def by auto
have item': ‹(pr⇩0, Suc 0, R) ∈ set (xclosure_auto G (Xs ! 0))›
using item xclosure_auto_kernel_sub Xs by fastforce
have pr0: ‹pr⇩0 = start_prod G Shn›
using dshape_prods[OF sh _ item'] Shn fn unfolding fresh_name_def by force
have acc: ‹(start_prod G Shn, Suc 0) ∈ set (?sts ! ?i)›
using lv pr0 cover by blast
from dcands_reduceD[OF cand]
have ‹dlic ?i (red_buckets G Shn (length ?sts) ! ?i) u pr (red_set (xclosure_auto G (hd Xs)) pr)›
by simp
then obtain τ where
cell: ‹(?i, (pr, length (snd pr)), None, τ) ∈ set (red_buckets G Shn (length ?sts) ! ?i)›
unfolding dlic_def u by (auto simp: list_ex_iff)
then have cellL: ‹(?i, (pr, length (snd pr)), None, τ) ∈ set (la_fix G Shn)›
by (rule red_buckets_memD[OF i_lt, THEN conjunct1])
have ne: ‹pr ≠ start_prod G Shn›
proof
assume pr: ‹pr = start_prod G Shn›
have ‹gc' = (lgoto (xclosure_auto G (xinit G Shn)) (Nt Shn)
(red_set (xclosure_auto G X) pr) # [xinit G Shn], u)›
using step unfolding mstep_def mstep_cached_def Xs pr start_prod_def
by (auto simp: Let_def split: if_splits)
then have ‹gc' = ([] # [xinit G Shn], u)› by (simp add: lgoto_xinit_Shn[OF fn])
with live show False unfolding dlive_def live_def by simp
qed
have ‹?i ∈ set (acc_conflicts G Shn)›
unfolding acc_conflicts_def Let_def using i_lt acc cellL ne
by (auto simp: list_ex_iff intro!: bexI[where x = ‹(?i, (pr, length (snd pr)), None, τ)›])
with chk show False by simp
qed
section ‹Soundness of the item-relative walk: the worklist›
text ‹A ‹False› result of \<^const>‹ifire› can only arise from an exhausted
worklist (fuel exhaustion returns ‹True›), so it certifies that no triple
the successor relation \<^const>‹isuccs› reaches from the seed fires. The
worklist invariant: no seen triple fires, and every successor of a seen
triple is seen or still to do.›
lemma map_filterI:
‹x ∈ set xs ⟹ f x = Some y ⟹ y ∈ set (List.map_filter f xs)›
unfolding List.map_filter_def by force
lemma concat_map_memI:
‹x ∈ set xs ⟹ y ∈ set (g x) ⟹ y ∈ set (concat (map g xs))›
by auto
text ‹The worklist's closure: when the walk returns ‹False›, the triples
it saw form a set closed under \<^const>‹isuccs› none of which fires.›
lemma ifire_False_closed:
assumes res: ‹ifire Shn wrs gt anc n seen work = False›
and inv: ‹∀t ∈ set seen. ¬ ifires Shn anc t ∧
set (isuccs Shn wrs gt anc t) ⊆ set seen ∪ set work›
shows ‹∃S. set seen ∪ set work ⊆ S ∧
(∀t ∈ S. ¬ ifires Shn anc t ∧ set (isuccs Shn wrs gt anc t) ⊆ S)›
using res inv
proof (induction n arbitrary: seen work)
case 0
then show ?case by simp
next
case (Suc n)
show ?case
proof (cases work)
case Nil
with Suc.prems show ?thesis by (intro exI[of _ ‹set seen›]) auto
next
case (Cons t wk)
have nf: ‹¬ ifires Shn anc t› using Suc.prems Cons by (auto split: if_splits)
have rec: ‹ifire Shn wrs gt anc n (t # seen)
(filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
(remdups (isuccs Shn wrs gt anc t)) @ wk) = False›
using Suc.prems Cons nf by simp
have inv': ‹∀u ∈ set (t # seen). ¬ ifires Shn anc u ∧
set (isuccs Shn wrs gt anc u) ⊆ set (t # seen) ∪
set (filter (λt'. t' ∉ set (t # seen) ∧ t' ∉ set wk)
(remdups (isuccs Shn wrs gt anc t)) @ wk)›
using Suc.prems Cons nf by auto
from Suc.IH[OF rec inv'] Cons show ?thesis by auto
qed
qed
lemma ifire_False_sound:
assumes res: ‹ifire Shn wrs gt anc n seen work = False›
and inv: ‹∀t ∈ set seen. ¬ ifires Shn anc t ∧
set (isuccs Shn wrs gt anc t) ⊆ set seen ∪ set work›
and t0: ‹t⇩0 ∈ set seen ∪ set work›
and desc: ‹(λt t'. t' ∈ set (isuccs Shn wrs gt anc t))⇧*⇧* t⇩0 t'›
shows ‹¬ ifires Shn anc t'›
proof -
obtain S where sub: ‹set seen ∪ set work ⊆ S›
and cl: ‹∀t ∈ S. ¬ ifires Shn anc t ∧ set (isuccs Shn wrs gt anc t) ⊆ S›
using ifire_False_closed[OF res inv] by blast
have ‹t' ∈ S›
using desc t0 sub cl by (induction rule: rtranclp_induct) auto
with cl show ?thesis by blast
qed
theorem ifire_sound:
assumes res: ‹ifire Shn wrs gt anc n [] [t⇩0] = False›
and desc: ‹(λt t'. t' ∈ set (isuccs Shn wrs gt anc t))⇧*⇧* t⇩0 t'›
shows ‹¬ ifires Shn anc t'›
using ifire_False_sound[OF res _ _ desc] by auto
section ‹Stack shape along reachability, and anchor persistence›
lemma dshapeD:
assumes ‹dshape G Shn Xs α›
shows ‹length Xs = length α + 1› and ‹Xs ! length α = xinit G Shn›
and ‹⋀k. k < length α ⟹
Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
using assms unfolding dshape_def by auto
text ‹Every reachable stack is \<^const>‹dshape›-shaped (part of the
tracking invariant of \<^text>‹imreach_strack› below): each frame is the
\<^const>‹lgoto› of the closure of the frame below, along a recorded goto
history. Anchors of a kernel item persist from its prediction: descending
the dots, the item's anchor set only shrinks from the dot-0 slot in the
closure of the frame where it was predicted.›
lemma wkernel_memI:
‹(pr, m) ∈ set s ⟹
(pr, m, if m = 0 then WAny else w_of (snd (snd pr ! (m - 1)))) ∈ set (wkernel s)›
unfolding wkernel_def by force
lemma xclosure_auto_kernelD:
assumes ‹(pr, m, R) ∈ set (xclosure_auto G s)› and ‹1 ≤ m›
shows ‹(pr, m, R) ∈ set s›
proof -
have ‹(pr, m, R) ∈ set (xslots G s (xiter G s (xfuel G s)))›
using assms(1) unfolding xclosure_auto_def xclosure_def .
then show ?thesis
proof (rule xslots_memE)
assume ‹(pr, m, R) ∈ set s› then show ?thesis .
next
fix q assume ‹q < length (iprods G)›
and ‹q < length (xiter G s (xfuel G s))›
and ‹(pr, m, R) = (iprods G ! q, 0, xiter G s (xfuel G s) ! q)›
then show ?thesis using assms(2) by auto
qed
qed
text ‹A kernel item at dot ‹m ≥ 1› in frame ‹k› descends to the dot-0 slot of
the closure of frame ‹k + m›, its anchor set only shrinking.›
lemma dshape_persist:
assumes sh: ‹dshape G Shn Xs α›
shows ‹(pr, m, R) ∈ set (Xs ! k) ⟹ k < length Xs ⟹ 1 ≤ m ⟹
∃R⇩0. k + m < length Xs ∧ (pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! (k + m))) ∧
irep_set R ⊆ irep_set R⇩0›
proof (induction m arbitrary: k R)
case 0
then show ?case by simp
next
case (Suc m)
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have k_lt_a: ‹k < length α›
proof (rule ccontr)
assume ‹¬ k < length α›
then have ‹k = length α› using Suc.prems(2) lenX by simp
then have ‹(pr, Suc m, R) ∈ set (xinit G Shn)› using Suc.prems(1) bot by simp
then show False unfolding xinit_def by auto
qed
have frame: ‹Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
by (rule shp[OF k_lt_a])
from lgoto_kernel_step[OF Suc.prems(1)[unfolded frame]] obtain R' where
src: ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! Suc k))›
and Req: ‹R = irep_inter R' (irep_pre (snd (snd pr ! m)) (snd (α ! k)))› .
have sub: ‹irep_set R ⊆ irep_set R'› unfolding Req by auto
show ?case
proof (cases m)
case 0
have ‹Suc k < length Xs› using k_lt_a lenX by simp
then show ?thesis using src sub 0 by auto
next
case (Suc m')
have m_pos: ‹1 ≤ m› using Suc by simp
have src': ‹(pr, m, R') ∈ set (xslots G (Xs ! Suc k)
(xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k))))›
using src unfolding xclosure_auto_def xclosure_def .
have kern: ‹(pr, m, R') ∈ set (Xs ! Suc k)›
using src'
proof (rule xslots_memE)
assume ‹(pr, m, R') ∈ set (Xs ! Suc k)›
then show ?thesis .
next
fix q assume ‹q < length (iprods G)›
and ‹q < length (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)))›
and ‹(pr, m, R') = (iprods G ! q, 0, xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)) ! q)›
then show ?thesis using Suc by auto
qed
have Sk_lt: ‹Suc k < length Xs› using k_lt_a lenX by simp
from Suc.IH[OF kern Sk_lt m_pos] obtain R⇩0 where
‹Suc k + m < length Xs›
and s0: ‹(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! (Suc k + m)))›
and sub2: ‹irep_set R' ⊆ irep_set R⇩0› by blast
then show ?thesis using sub by fastforce
qed
qed
section ‹The pooled width invariant›
text ‹The per-item form of the width invariant: each anchored closure item
relates to ‹some› element of the frame's entry pool ‹P› by a ‹wreach›
class; different items may pick different pool elements, as the pooled
machine's frames demand. This is the observation of
\<^cite>‹‹Sect.~5.8› in "adams2013"› that the items of one item set can carry different
indentation sets, so one set shared by all of them is not enough.
First the closure preservation, by
\<^text>‹xiter_slot_induct›: every step reuses its source's pool element.›
lemma xiter_pool:
assumes kern: ‹⋀pr m R j. (pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹
∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
shows ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹
∃ρ l. (iprods G ! p, 0, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
proof (rule xiter_slot_induct[where Q = ‹λpr m j. ∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›,
OF kern])
fix pr m i j p
assume ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l i› and m: ‹m < length (snd pr)›
‹fst (snd pr ! m) = Nt (fst (iprods G ! p))› ‹p < length (iprods G)›
and rel: ‹irel_sat (snd (snd pr ! m)) j i›
then obtain ρ l where ‹(pr, m, ρ) ∈ set (wreach G s)› ‹l ∈ P› ‹wsat ρ l i› by blast
with wreach_emit[OF _ m(1,2)] m(3) wsat_reanchor[OF _ ‹wsat ρ l i›] rel
show ‹∃ρ l. (iprods G ! p, 0, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j› by fastforce
qed
text ‹The kernel hypothesis, per frame kind: an ‹lgoto›-built frame pools the
goto label's anchors, the bottom frame is pinned at ‹istart_ind›.›
lemma wanch_pool_lgoto:
assumes cover: ‹⋀pr m R j. (pr, m, R) ∈ set (lgoto CL X RA) ⟹ j ∈ irep_set R ⟹
(pr, m) ∈ set s›
and mem: ‹(pr, m, R) ∈ set (lgoto CL X RA)› and jR: ‹j ∈ irep_set R›
shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ irep_set RA ∧ wsat ρ l j›
proof -
obtain m⇩0 where m: ‹m = Suc m⇩0› using lgoto_dot_pos[OF mem] by (cases m) auto
from lgoto_kernel_step[OF mem[unfolded m]] obtain R⇩s where
m0_lt: ‹m⇩0 < length (snd pr)›
and Req: ‹R = irep_inter R⇩s (irep_pre (snd (snd pr ! m⇩0)) RA)› .
from jR obtain l where lRA: ‹l ∈ irep_set RA›
and rel: ‹irel_sat (snd (snd pr ! m⇩0)) l j›
unfolding Req by auto
have kmem: ‹(pr, m) ∈ set s› by (rule cover[OF mem jR])
have ‹(pr, m, w_of (snd (snd pr ! (m - 1)))) ∈ set (wkernel s)›
using wkernel_memI[OF kmem] unfolding m by simp
then have wmem: ‹(pr, m, w_of (snd (snd pr ! m⇩0))) ∈ set (wreach G s)›
using wreach_kernel unfolding m by auto
have ‹wsat (w_of (snd (snd pr ! m⇩0))) l j› by (rule w_of_sound[OF rel])
then show ?thesis using wmem lRA by blast
qed
lemma wanch_pool_xinit:
assumes mem: ‹(pr, m, R) ∈ set (xinit G Shn)› and jR: ‹j ∈ irep_set R›
and cover: ‹(pr, m) ∈ set s›
shows ‹∃ρ. (pr, m, ρ) ∈ set (wreach G s) ∧ wsat ρ (istart_ind G) j›
proof -
have m0: ‹m = 0› using mem unfolding xinit_def by auto
have ‹(pr, m, WAny) ∈ set (wkernel s)›
using wkernel_memI[OF cover] unfolding m0 by simp
then have ‹(pr, m, WAny) ∈ set (wreach G s)› using wreach_kernel by auto
then show ?thesis by auto
qed
section ‹The anchored-nonterminal fixpoint›
text ‹\<^const>‹anchored_nts› iterates a filter; each round either fixes the
list or strictly shortens it, so ‹length nts› rounds reach the greatest
fixpoint. The destructor: an anchored nonterminal's productions all start
with an ‹Eq›-related terminal or anchored nonterminal.›
lemma funpow_filter_fix:
fixes stp :: ‹'a list ⇒ 'a list›
assumes step: ‹⋀S. stp S = S ∨ length (stp S) < length S›
shows ‹stp ((stp ^^ n) S⇩0) = (stp ^^ n) S⇩0 ∨ length ((stp ^^ n) S⇩0) ≤ length S⇩0 - n›
proof (induction n)
case 0
then show ?case using step by auto
next
case (Suc n)
show ?case
proof (cases ‹stp ((stp ^^ n) S⇩0) = (stp ^^ n) S⇩0›)
case True
then have ‹(stp ^^ Suc n) S⇩0 = (stp ^^ n) S⇩0› by simp
then show ?thesis using True by simp
next
case False
with Suc.IH have len_n: ‹length ((stp ^^ n) S⇩0) ≤ length S⇩0 - n› by blast
from step[of ‹(stp ^^ n) S⇩0›] False
have ‹length (stp ((stp ^^ n) S⇩0)) < length ((stp ^^ n) S⇩0)› by blast
then have ‹length ((stp ^^ Suc n) S⇩0) ≤ length S⇩0 - Suc n›
using len_n by simp
then show ?thesis by blast
qed
qed
lemma funpow_filter_stable:
fixes stp :: ‹'a list ⇒ 'a list›
assumes step: ‹⋀S. stp S = S ∨ length (stp S) < length S›
and nil: ‹stp [] = []›
shows ‹stp ((stp ^^ length S⇩0) S⇩0) = (stp ^^ length S⇩0) S⇩0›
proof -
from funpow_filter_fix[OF step, of ‹length S⇩0› S⇩0]
consider ‹stp ((stp ^^ length S⇩0) S⇩0) = (stp ^^ length S⇩0) S⇩0›
| ‹length ((stp ^^ length S⇩0) S⇩0) = 0› by fastforce
then show ?thesis
proof cases
case 1
then show ?thesis .
next
case 2
then have ‹(stp ^^ length S⇩0) S⇩0 = []› by simp
then show ?thesis using nil by simp
qed
qed
lemma anchored_ntsD:
fixes G :: ‹('n, 't) is_cfg›
assumes A: ‹A ∈ set (anchored_nts G)› and pr: ‹(A, rhs) ∈ set (iprods G)›
shows ‹rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
(case fst (hd rhs) of Tm _ ⇒ True | Nt B ⇒ B ∈ set (anchored_nts G))›
proof -
define ok where ‹ok = (λS (B :: 'n, rhs :: ('n, 't) rhs). rhs ≠ [] ∧ snd (hd rhs) = Eq ∧
(case fst (hd rhs) of Tm _ ⇒ True | Nt B' ⇒ B' ∈ set S))›
define stp where ‹stp = (λS. filter (λA. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)) S)›
have step: ‹stp S = S ∨ length (stp S) < length S› for S
proof (cases ‹∀A ∈ set S. list_all (λp. fst p ≠ A ∨ ok S p) (iprods G)›)
case True
then have ‹stp S = S› unfolding stp_def by (simp add: filter_id_conv)
then show ?thesis ..
next
case False
then obtain A' where ‹A' ∈ set S›
and ‹¬ list_all (λp. fst p ≠ A' ∨ ok S p) (iprods G)› by blast
then have ‹length (stp S) < length S›
unfolding stp_def by (intro length_filter_less) auto
then show ?thesis ..
qed
have nil: ‹stp [] = []› unfolding stp_def by simp
have unf: ‹anchored_nts G = (stp ^^ length (remdups (map fst (iprods G))))
(remdups (map fst (iprods G)))›
unfolding anchored_nts_def stp_def ok_def Let_def by simp
have stable: ‹stp (anchored_nts G) = anchored_nts G›
unfolding unf by (rule funpow_filter_stable[OF step nil])
have ‹A ∈ set (stp (anchored_nts G))› using A stable by simp
then have ‹list_all (λp. fst p ≠ A ∨ ok (anchored_nts G) p) (iprods G)›
unfolding stp_def by simp
then have ‹ok (anchored_nts G) (A, rhs)›
using pr by (fastforce simp: list_all_iff)
then show ?thesis unfolding ok_def by simp
qed
section ‹Anchored pools are singletons›
lemma anchored_nts_sub: ‹set (anchored_nts G) ⊆ fst ` set (iprods G)›
proof -
have gen: ‹set ((stp ^^ k) S⇩0) ⊆ set S⇩0›
if sub: ‹⋀S. set (stp S) ⊆ set S› for stp :: ‹'x list ⇒ 'x list› and k S⇩0
proof (induction k)
case 0 then show ?case by simp
next
case (Suc k)
have ‹set ((stp ^^ Suc k) S⇩0) ⊆ set ((stp ^^ k) S⇩0)› using sub by simp
then show ?case using Suc.IH by blast
qed
show ?thesis
unfolding anchored_nts_def Let_def
by (rule subset_trans[OF gen]) auto
qed
lemma dshape_persist1:
assumes sh: ‹dshape G Shn Xs α›
shows ‹(pr, m, R) ∈ set (Xs ! k) ⟹ k < length Xs ⟹ 1 ≤ m ⟹
∃R⇩1. k + m - 1 < length α ∧ (pr, 1, R⇩1) ∈ set (Xs ! (k + m - 1)) ∧
irep_set R ⊆ irep_set R⇩1›
proof (induction m arbitrary: k R)
case 0
then show ?case by simp
next
case (Suc m)
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have k_lt_a: ‹k < length α›
proof (rule ccontr)
assume ‹¬ k < length α›
then have ‹k = length α› using Suc.prems(2) lenX by simp
then have ‹(pr, Suc m, R) ∈ set (xinit G Shn)› using Suc.prems(1) bot by simp
then show False unfolding xinit_def by auto
qed
show ?case
proof (cases m)
case 0
then show ?thesis using Suc.prems(1) k_lt_a by auto
next
case (Suc m')
have frame: ‹Xs ! k = lgoto (xclosure_auto G (Xs ! Suc k)) (fst (α ! k)) (snd (α ! k))›
by (rule shp[OF k_lt_a])
from lgoto_kernel_step[OF Suc.prems(1)[unfolded frame]] obtain R' where
src: ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! Suc k))›
and Req: ‹R = irep_inter R' (irep_pre (snd (snd pr ! m)) (snd (α ! k)))› .
have sub: ‹irep_set R ⊆ irep_set R'› unfolding Req by auto
have src'': ‹(pr, m, R') ∈ set (xslots G (Xs ! Suc k)
(xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k))))›
using src unfolding xclosure_auto_def xclosure_def .
have kern: ‹(pr, m, R') ∈ set (Xs ! Suc k)›
using src''
proof (rule xslots_memE)
assume ‹(pr, m, R') ∈ set (Xs ! Suc k)›
then show ?thesis .
next
fix q assume ‹q < length (iprods G)›
and ‹q < length (xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)))›
and ‹(pr, m, R') = (iprods G ! q, 0, xiter G (Xs ! Suc k) (xfuel G (Xs ! Suc k)) ! q)›
then show ?thesis using Suc by auto
qed
have Sk_lt: ‹Suc k < length Xs› using k_lt_a lenX by simp
have m_pos: ‹1 ≤ m› using Suc by simp
from Suc.IH[OF kern Sk_lt m_pos] obtain R⇩1 where
lt1: ‹Suc k + m - 1 < length α›
and s1: ‹(pr, 1, R⇩1) ∈ set (Xs ! (Suc k + m - 1))›
and sub1: ‹irep_set R' ⊆ irep_set R⇩1› by blast
have idx: ‹Suc k + m - 1 = k + Suc m - 1› using m_pos by simp
show ?thesis using lt1 s1 sub sub1 unfolding idx by blast
qed
qed
lemma irep_pre_Eq: ‹irep_set (irep_pre Eq L) = irep_set L›
by auto
text ‹The label of a reduce over an anchored nonterminal is bounded by a
single column: every completed instance descends to its dot-1 form, whose
‹Eq› first-symbol filter bounds it by the pool of the frame where the
first symbol was crossed: a shift column, or an anchored pool one level
down.›
lemma red_set_anchored_singleton:
assumes sh: ‹dshape G Shn Xs α› and ne: ‹Xs ≠ []›
and tmS: ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
and sng: ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
(∃c. irep_set (snd (α ! k)) ⊆ {c})›
and fresh: ‹fresh_name G Shn›
and anch: ‹fst pr ∈ set (anchored_nts G)›
shows ‹∃c. irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {c}›
proof (cases ‹∃R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ∧
irep_set R ≠ {}›)
case False
have ‹irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {0}›
using False by (fastforce simp: red_set_correct)
then show ?thesis by blast
next
case True
then obtain R⇩w where inst_w: ‹(pr, length (snd pr), R⇩w) ∈ set (xclosure_auto G (hd Xs))›
by blast
note lenX = dshapeD(1)[OF sh]
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have prG: ‹pr ∈ set (iprods G)›
proof -
have ‹pr ∈ set (iprods G) ∨ pr = start_prod G Shn›
using dshape_prods[OF sh _ inst_w[unfolded hd0]] by simp
moreover have ‹pr ≠ start_prod G Shn›
proof
assume ‹pr = start_prod G Shn›
then have ‹fst pr = Shn› unfolding start_prod_def by simp
then have ‹Shn ∈ set (anchored_nts G)› using anch by simp
then have ‹Shn ∈ fst ` set (iprods G)›
by (rule subsetD[OF anchored_nts_sub])
then show False using fresh unfolding fresh_name_def by auto
qed
ultimately show ?thesis by blast
qed
obtain A rhs where preq: ‹pr = (A, rhs)› by (cases pr)
from anchored_ntsD[OF anch[unfolded preq fst_conv] prG[unfolded preq]]
have rhs_ne: ‹rhs ≠ []› and hdEq: ‹snd (hd rhs) = Eq›
and hdok: ‹case fst (hd rhs) of Tm _ ⇒ True | Nt B ⇒ B ∈ set (anchored_nts G)›
by auto
define d where ‹d = length (snd pr)›
have d_pos: ‹1 ≤ d› unfolding d_def preq using rhs_ne by (cases rhs) auto
have one: ‹d - 1 < length α ∧ fst (α ! (d - 1)) = fst (snd pr ! 0) ∧
irep_set R ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
if inst: ‹(pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs))› for R
proof -
have inst': ‹(pr, length (snd pr), R) ∈ set (xslots G (hd Xs)
(xiter G (hd Xs) (xfuel G (hd Xs))))›
using inst unfolding xclosure_auto_def xclosure_def .
have kern: ‹(pr, length (snd pr), R) ∈ set (hd Xs)›
using inst'
proof (rule xslots_memE)
assume ‹(pr, length (snd pr), R) ∈ set (hd Xs)›
then show ?thesis .
next
fix q assume ‹q < length (iprods G)›
and ‹q < length (xiter G (hd Xs) (xfuel G (hd Xs)))›
and eq: ‹(pr, length (snd pr), R) =
(iprods G ! q, 0, xiter G (hd Xs) (xfuel G (hd Xs)) ! q)›
have ‹length (snd pr) = 0› using eq by auto
then show ?thesis using d_pos unfolding d_def by simp
qed
have k0_lt: ‹(0 :: nat) < length Xs› using ne by (cases Xs) auto
have dm: ‹1 ≤ length (snd pr)› using d_pos unfolding d_def by simp
from dshape_persist1[OF sh kern[unfolded hd0] k0_lt dm]
obtain R⇩1 where lt1: ‹0 + length (snd pr) - 1 < length α›
and s1: ‹(pr, 1, R⇩1) ∈ set (Xs ! (0 + length (snd pr) - 1))›
and sub1: ‹irep_set R ⊆ irep_set R⇩1› by blast
have idx: ‹0 + length (snd pr) - 1 = d - 1› unfolding d_def by simp
have lt': ‹d - 1 < length α› using lt1 unfolding idx .
have frame: ‹Xs ! (d - 1) =
lgoto (xclosure_auto G (Xs ! Suc (d - 1))) (fst (α ! (d - 1))) (snd (α ! (d - 1)))›
using sh lt' unfolding dshape_def by auto
have s1': ‹(pr, Suc 0, R⇩1) ∈ set (lgoto (xclosure_auto G (Xs ! Suc (d - 1)))
(fst (α ! (d - 1))) (snd (α ! (d - 1))))›
using s1 unfolding idx frame by simp
from lgoto_kernel_step[OF s1'] obtain R⇩0 where
src0: ‹(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! Suc (d - 1)))›
and m0: ‹0 < length (snd pr)›
and X0: ‹fst (snd pr ! 0) = fst (α ! (d - 1))›
and R1eq: ‹R⇩1 = irep_inter R⇩0 (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))› .
have sub2: ‹irep_set R⇩1 ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
unfolding R1eq by auto
have ‹irep_set R ⊆ irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1))))›
using sub1 sub2 by (rule subset_trans)
then show ?thesis using lt' X0 by simp
qed
from one[OF inst_w] have k1: ‹d - 1 < length α›
and Xa: ‹fst (α ! (d - 1)) = fst (snd pr ! 0)› by auto
have first_rel: ‹snd (snd pr ! 0) = Eq›
using hdEq rhs_ne unfolding preq by (simp add: hd_conv_nth)
have bound: ‹∃c. irep_set (irep_pre (snd (snd pr ! 0)) (snd (α ! (d - 1)))) ⊆ {c}›
proof (cases ‹fst (snd pr ! 0)›)
case (Tm b)
from tmS k1 Xa Tm obtain c where ‹snd (α ! (d - 1)) = FinRep [c]› by auto
then show ?thesis unfolding first_rel irep_pre_Eq by auto
next
case (Nt B)
have hd0': ‹fst (hd rhs) = fst (snd pr ! 0)›
using rhs_ne unfolding preq by (simp add: hd_conv_nth)
have Banch: ‹B ∈ set (anchored_nts G)›
using hdok unfolding hd0' Nt by simp
have ‹∃c. irep_set (snd (α ! (d - 1))) ⊆ {c}›
using sng[rule_format, of ‹d - 1› B] k1 Xa Nt Banch by simp
then obtain c where ‹irep_set (snd (α ! (d - 1))) ⊆ {c}› by blast
then show ?thesis unfolding first_rel irep_pre_Eq by auto
qed
have bound': ‹∃c. ∀R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ⟶
irep_set R ⊆ {c}›
using bound one by blast
then obtain c where c: ‹⋀R. (pr, length (snd pr), R) ∈ set (xclosure_auto G (hd Xs)) ⟹
irep_set R ⊆ {c}› by blast
have ‹irep_set (red_set (xclosure_auto G (hd Xs)) pr) ⊆ {c}›
using c by (fastforce simp: red_set_correct)
then show ?thesis by blast
qed
section ‹The canonical tracked stack›
text ‹The descent needs more than \<^const>‹didx_ok›: the goto history
(\<^const>‹dshape›), singleton pools on shift entries, the canonical bottom
index, and the ‹adjacency› tying each tracked index to the canonical goto
target of the index below along the recorded symbol. The bottom index and the
adjacency say what Barthwal's ‹validItem_inv›
\<^cite>‹‹Def.~5.4.3› in "barthwal2010-thesis-cfl-hol4"› says: the state of every
sub-stack is the one reached from the start state by reading its symbols. The safety
invariant of Jourdan et al. \<^cite>‹‹Sect.~3.2› in "jourdan2012-validating-lr1"›
describes only a statically known suffix of the stack; here every index is
tracked. The reachability
induction constructs exactly these witnesses.›
definition strack :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) xitem list list ⇒
(('n, 't) sym × indrep) list ⇒ nat list ⇒ bool› where
‹strack G Shn Xs α pstk ⟷
dshape G Shn Xs α ∧
didx_ok G (pr0_states G Shn) Xs pstk ∧
last pstk = p0start G Shn ∧
(∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])) ∧
(∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
(∃c. irep_set (snd (α ! k)) ⊆ {c})) ∧
(∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
(∀l ∈ irep_set (snd (α ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R⇩0)) ∧
(∀k < length α. pstk ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k))))›
lemma strackD:
assumes ‹strack G Shn Xs α pstk›
shows ‹dshape G Shn Xs α› and ‹didx_ok G (pr0_states G Shn) Xs pstk›
and ‹last pstk = p0start G Shn›
and ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
(∃c. irep_set (snd (α ! k)) ⊆ {c})›
and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
(∀l ∈ irep_set (snd (α ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R⇩0)›
and ‹∀k < length α. pstk ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k)))›
using assms unfolding strack_def by blast+
lemma strackI:
assumes ‹dshape G Shn Xs α› and ‹didx_ok G (pr0_states G Shn) Xs pstk›
and ‹last pstk = p0start G Shn›
and ‹∀k < length α. ∀a. fst (α ! k) = Tm a ⟶ (∃c. snd (α ! k) = FinRep [c])›
and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶ B ∈ set (anchored_nts G) ⟶
(∃c. irep_set (snd (α ! k)) ⊆ {c})›
and ‹∀k < length α. ∀B. fst (α ! k) = Nt B ⟶
(∀l ∈ irep_set (snd (α ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! Suc k)) ∧ l ∈ irep_set R⇩0)›
and ‹∀k < length α. pstk ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! Suc k))) (fst (α ! k)))›
shows ‹strack G Shn Xs α pstk›
using assms unfolding strack_def by blast
lemma strack_tl:
assumes tr: ‹strack G Shn Xs ((X⇩0, RA) # α') pstk›
shows ‹strack G Shn (tl Xs) α' (tl pstk)›
proof -
note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr] and lastp = strackD(3)[OF tr]
and tmS = strackD(4)[OF tr] and sng = strackD(5)[OF tr] and slot = strackD(6)[OF tr]
and adj = strackD(7)[OF tr]
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have Xs_ne: ‹Xs ≠ []› using lenX by auto
obtain x⇩0 Xr where Xs_eq: ‹Xs = x⇩0 # Xr› using Xs_ne by (cases Xs) auto
have nthX: ‹⋀k. tl Xs ! k = Xs ! Suc k› unfolding Xs_eq by simp
have len_tl: ‹length (tl Xs) = length α' + 1› using lenX by simp
have lenp: ‹length pstk = length Xs› by (rule didx_ok_len[OF mt])
obtain p⇩0 Pr where pstk_eq: ‹pstk = p⇩0 # Pr›
using lenp Xs_ne by (cases pstk) auto
have nthP: ‹⋀k. tl pstk ! k = pstk ! Suc k› unfolding pstk_eq by simp
have Pr_ne: ‹Pr ≠ []› using lenp lenX pstk_eq by auto
have sh': ‹dshape G Shn (tl Xs) α'›
unfolding dshape_def
proof (intro conjI)
show ‹length (tl Xs) = length α' + 1› by (rule len_tl)
show ‹tl Xs ! length α' = xinit G Shn› using bot by (simp add: nthX)
show ‹∀k < length α'. tl Xs ! k =
lgoto (xclosure_auto G (tl Xs ! Suc k)) (fst (α' ! k)) (snd (α' ! k))›
proof (intro allI impI)
fix k assume k: ‹k < length α'›
have ‹Suc k < length ((X⇩0, RA) # α')› using k by simp
from shp[OF this] show ‹tl Xs ! k =
lgoto (xclosure_auto G (tl Xs ! Suc k)) (fst (α' ! k)) (snd (α' ! k))›
by (simp add: nthX)
qed
qed
have mt': ‹didx_ok G (pr0_states G Shn) (tl Xs) (tl pstk)›
unfolding didx_ok_def
proof (intro conjI)
show ‹length (tl pstk) = length (tl Xs)› using lenp by (simp add: Xs_eq pstk_eq)
show ‹∀k < length (tl Xs). lcore (tl Xs ! k) ≠ {} ⟶
tl pstk ! k < length (pr0_states G Shn) ∧
lcore (tl Xs ! k) ⊆ set (pr0_states G Shn ! (tl pstk ! k))›
proof (intro allI impI)
fix k assume k: ‹k < length (tl Xs)› and lv: ‹lcore (tl Xs ! k) ≠ {}›
have sk: ‹Suc k < length Xs› using k unfolding Xs_eq by simp
show ‹tl pstk ! k < length (pr0_states G Shn) ∧
lcore (tl Xs ! k) ⊆ set (pr0_states G Shn ! (tl pstk ! k))›
using didx_okD[OF mt sk] lv by (simp add: nthX nthP)
qed
qed
have last': ‹last (tl pstk) = p0start G Shn›
using lastp Pr_ne unfolding pstk_eq by simp
have tmS': ‹∀k < length α'. ∀a. fst (α' ! k) = Tm a ⟶
(∃c. snd (α' ! k) = FinRep [c])›
proof (intro allI impI)
fix k a assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Tm a›
show ‹∃c. snd (α' ! k) = FinRep [c]›
using tmS[rule_format, of ‹Suc k› a] k t by simp
qed
have sng': ‹∀k < length α'. ∀B. fst (α' ! k) = Nt B ⟶
B ∈ set (anchored_nts G) ⟶ (∃c. irep_set (snd (α' ! k)) ⊆ {c})›
proof (intro allI impI)
fix k B assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Nt B›
and an: ‹B ∈ set (anchored_nts G)›
show ‹∃c. irep_set (snd (α' ! k)) ⊆ {c}›
using sng[rule_format, of ‹Suc k› B] k t an by simp
qed
have slot': ‹∀k < length α'. ∀B. fst (α' ! k) = Nt B ⟶
(∀l ∈ irep_set (snd (α' ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (tl Xs ! Suc k)) ∧ l ∈ irep_set R⇩0)›
proof (intro allI impI)
fix k B assume k: ‹k < length α'› and t: ‹fst (α' ! k) = Nt B›
have ‹∀l ∈ irep_set (snd (α' ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! Suc (Suc k))) ∧ l ∈ irep_set R⇩0›
using slot[rule_format, of ‹Suc k› B] k t by simp
then show ‹∀l ∈ irep_set (snd (α' ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (tl Xs ! Suc k)) ∧ l ∈ irep_set R⇩0›
by (simp add: nthX)
qed
have adj': ‹∀k < length α'. tl pstk ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (tl pstk ! Suc k))) (fst (α' ! k)))›
proof (intro allI impI)
fix k assume k: ‹k < length α'›
have ‹Suc k < length ((X⇩0, RA) # α')› using k by simp
from adj[rule_format, OF this]
show ‹tl pstk ! k = st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (tl pstk ! Suc k))) (fst (α' ! k)))›
by (simp add: nthP)
qed
show ?thesis
by (rule strackI[OF sh' mt' last' tmS' sng' slot' adj'])
qed
lemma strack_drop:
‹strack G Shn Xs α pstk ⟹ d ≤ length α ⟹
strack G Shn (drop d Xs) (drop d α) (drop d pstk)›
proof (induction d arbitrary: Xs α pstk)
case 0
then show ?case by simp
next
case (Suc d)
obtain X RA α' where α: ‹α = (X, RA) # α'›
using Suc.prems(2) by (cases α) auto
have tl: ‹strack G Shn (tl Xs) α' (tl pstk)›
by (rule strack_tl[OF Suc.prems(1)[unfolded α]])
have d_le: ‹d ≤ length α'› using Suc.prems(2) unfolding α by simp
from Suc.IH[OF tl d_le] show ?case unfolding α by (simp add: drop_Suc)
qed
text ‹Pushing a frame on a tracked stack: the new frame's index is the
canonical goto of the index below along the pushed symbol, the extended
index stack is checked by \<^const>‹didx_ok›, and the three per-label
conditions are checked for the pushed label only.›
lemma strack_push:
assumes tr: ‹strack G Shn Xs α pstk›
and NF: ‹NF = lgoto (xclosure_auto G (hd Xs)) X RA›
and p': ‹p' = st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! 0))) X)›
and mt': ‹didx_ok G (pr0_states G Shn) (NF # Xs) (p' # pstk)›
and tm: ‹⋀a. X = Tm a ⟹ ∃c. RA = FinRep [c]›
and sng: ‹⋀B. X = Nt B ⟹ B ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
and slot: ‹⋀B l. X = Nt B ⟹ l ∈ irep_set RA ⟹ ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G (hd Xs)) ∧ l ∈ irep_set R⇩0›
shows ‹strack G Shn (NF # Xs) ((X, RA) # α) (p' # pstk)›
proof -
note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr] and lastp = strackD(3)[OF tr]
and tmS = strackD(4)[OF tr] and sngI = strackD(5)[OF tr] and slotI = strackD(6)[OF tr]
and adj = strackD(7)[OF tr]
have ne: ‹Xs ≠ []› using dshapeD(1)[OF sh] by auto
have pstk_ne: ‹pstk ≠ []› using didx_ok_len[OF mt] ne by auto
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have sh': ‹dshape G Shn (NF # Xs) ((X, RA) # α)›
unfolding NF by (rule dshape_push[OF sh ne])
have last': ‹last (p' # pstk) = p0start G Shn› using lastp pstk_ne by simp
have tmS': ‹∀k < length ((X, RA) # α). ∀b. fst (((X, RA) # α) ! k) = Tm b ⟶
(∃c'. snd (((X, RA) # α) ! k) = FinRep [c'])›
using tmS tm by (auto simp: less_Suc_eq_0_disj nth_Cons')
have sng': ‹∀k < length ((X, RA) # α). ∀B. fst (((X, RA) # α) ! k) = Nt B ⟶
B ∈ set (anchored_nts G) ⟶ (∃c'. irep_set (snd (((X, RA) # α) ! k)) ⊆ {c'})›
using sngI sng by (auto simp: less_Suc_eq_0_disj nth_Cons')
have slot': ‹∀k < length ((X, RA) # α). ∀B. fst (((X, RA) # α) ! k) = Nt B ⟶
(∀l ∈ irep_set (snd (((X, RA) # α) ! k)). ∃pr R⇩0. fst pr = B ∧
(pr, 0, R⇩0) ∈ set (xclosure_auto G ((NF # Xs) ! Suc k)) ∧ l ∈ irep_set R⇩0)›
using slotI slot hd0 by (auto simp: less_Suc_eq_0_disj nth_Cons')
have adj': ‹∀k < length ((X, RA) # α). (p' # pstk) ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! ((p' # pstk) ! Suc k)))
(fst (((X, RA) # α) ! k)))›
proof (intro allI impI)
fix k assume ‹k < length ((X, RA) # α)›
then show ‹(p' # pstk) ! k =
st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! ((p' # pstk) ! Suc k)))
(fst (((X, RA) # α) ! k)))›
using adj p' by (cases k) auto
qed
show ?thesis by (rule strackI[OF sh' mt' last' tmS' sng' slot' adj'])
qed
text ‹Every configuration the indexed machine reaches carries a tracked
stack whose indices are the driver's own: a shift pushes the token's
singleton label, a reduce drops the handle and pushes the nonterminal with
its pooled anchors. The pushed index is the table's goto, which resolves
to the canonical successor because the pushed frame is live
(\<^text>‹dnext_st_find›); the singleton and slot conditions come from
\<^text>‹red_set_anchored_singleton› and \<^text>‹dshape_persist›.›
theorem imreach_strack:
assumes ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) ic›
and fresh: ‹fresh_name G Shn›
shows ‹∃α. strack G Shn (fst (fst ic)) α (snd ic)›
using assms(1)
proof (induction rule: imreach.induct)
case (imreach_init w)
have mt: ‹didx_ok G (pr0_states G Shn) [xinit G Shn]
[st_find (pr0_states G Shn) (lr0_start G Shn)]›
by (rule didx_ok_init[OF tables_ok_concrete])
have ‹strack G Shn [xinit G Shn] [] [st_find (pr0_states G Shn) (lr0_start G Shn)]›
unfolding strack_def using dshape_init mt by (simp add: p0start_def)
then show ?case by auto
next
case (imreach_step ic act ic')
let ?sts = ‹pr0_states G Shn› and ?gt = ‹pgtab G (pr0_states G Shn)›
note tab = tables_ok_concrete[of G Shn]
obtain gc istk where ic: ‹ic = (gc, istk)› by (cases ic)
obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
obtain gc' istk' where ic': ‹ic' = (gc', istk')› by (cases ic')
obtain α where tr: ‹strack G Shn Xs α istk›
using imreach_step.IH unfolding ic gc by auto
note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
and tmS = strackD(4)[OF tr] and sngI = strackD(5)[OF tr]
note lenXa = dshapeD(1)[OF sh]
have len: ‹length istk = length Xs› by (rule didx_ok_len[OF mt])
have lv': ‹dlive gc'› using imreach_step.hyps(3) unfolding ic' by simp
show ?case
proof (cases act)
case DShift
have step0: ‹imstep G ?gt ?sts ((Xs, w), istk) DShift = Some (gc', istk')›
using imreach_step.hyps(2) unfolding ic gc ic' DShift .
then have mstep: ‹mstep G (Xs, w) DShift = Some gc'›
and istk': ‹istk' = dnext ?gt ?sts (hd istk) (Tm (fst (hd w))) # istk›
unfolding imstep_def by (auto split: option.splits)
have step: ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) DShift = Some gc'›
using mstep unfolding mstep_def by simp
from mstep_shift_shape[OF step] obtain a c w' where
w: ‹w = (a, c) # w'› and ne: ‹Xs ≠ []›
and gc': ‹gc' = (lgoto (hd (map (xclosure_auto G) Xs)) (Tm a) (FinRep [c]) # Xs, w')› .
define NF where ‹NF = lgoto (xclosure_auto G (hd Xs)) (Tm a) (FinRep [c])›
define p' where ‹p' = dnext ?gt ?sts (hd istk) (Tm a)›
have gc'2: ‹fst gc' = NF # Xs›
unfolding gc' NF_def using ne by (simp add: hd_map)
have istk'2: ‹istk' = p' # istk› unfolding istk' p'_def w by simp
have z_lt: ‹0 < length Xs› using ne by simp
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have istk_ne: ‹istk ≠ []› using len ne by auto
have hdi: ‹hd istk = istk ! 0› using istk_ne by (simp add: hd_conv_nth)
have liveNF: ‹lcore NF ≠ {}›
using lv' ne unfolding gc' NF_def dlive_lcore by (simp add: hd_map)
have p'eq: ‹p' = st_find ?sts (cgoto (creach G (?sts ! (istk ! 0))) (Tm a))›
unfolding p'_def hdi
by (rule dnext_st_find[OF tab mt z_lt liveNF[unfolded NF_def hd0]])
have mt': ‹didx_ok G ?sts (NF # Xs) (p' # istk)›
using didx_ok_push[OF tab mt z_lt, where X = ‹Tm a› and RA = ‹FinRep [c]›]
unfolding NF_def p'_def hd0 hdi by simp
have ‹strack G Shn (NF # Xs) ((Tm a, FinRep [c]) # α) (p' # istk)›
by (rule strack_push[OF tr NF_def p'eq mt']) simp_all
then show ?thesis unfolding ic' fst_conv snd_conv gc'2 istk'2 by blast
next
case (DReduce pr)
define d where ‹d = length (snd pr)›
have step0: ‹imstep G ?gt ?sts ((Xs, w), istk) (DReduce pr) = Some (gc', istk')›
using imreach_step.hyps(2) unfolding ic gc ic' DReduce .
then have mstep: ‹mstep G (Xs, w) (DReduce pr) = Some gc'›
and istk': ‹istk' = dnext ?gt ?sts (istk ! d) (Nt (fst pr)) # drop d istk›
unfolding imstep_def d_def by (auto split: option.splits)
have step: ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) (DReduce pr) = Some gc'›
using mstep unfolding mstep_def by simp
have d_lt: ‹d < length Xs›
unfolding d_def by (rule mstep_reduce_shape[OF step]) blast
have gc'0: ‹gc' = (lgoto (map (xclosure_auto G) Xs ! d) (Nt (fst pr))
(red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
unfolding d_def by (rule mstep_reduce_shape[OF step]) blast
have ne: ‹Xs ≠ []› using d_lt by auto
have hdd: ‹hd (drop d Xs) = Xs ! d› using d_lt by (simp add: hd_drop_conv_nth)
define RA where ‹RA = red_set (xclosure_auto G (hd Xs)) pr›
define NF where ‹NF = lgoto (xclosure_auto G (hd (drop d Xs))) (Nt (fst pr)) RA›
define p' where ‹p' = dnext ?gt ?sts (istk ! d) (Nt (fst pr))›
have gc'2: ‹fst gc' = NF # drop d Xs›
unfolding gc'0 NF_def RA_def hdd using d_lt ne by (simp add: hd_map)
have istk'2: ‹istk' = p' # drop d istk› unfolding istk' p'_def ..
have d_le_a: ‹d ≤ length α› using d_lt lenXa by simp
have trd: ‹strack G Shn (drop d Xs) (drop d α) (drop d istk)›
by (rule strack_drop[OF tr d_le_a])
have pd: ‹drop d istk ! 0 = istk ! d› using len d_lt by simp
have liveNF: ‹lcore NF ≠ {}›
using lv' d_lt ne unfolding gc'0 NF_def RA_def hdd dlive_lcore by (simp add: hd_map)
have p'eq: ‹p' = st_find ?sts (cgoto (creach G (?sts ! (drop d istk ! 0))) (Nt (fst pr)))›
unfolding p'_def pd
by (rule dnext_st_find[OF tab mt d_lt liveNF[unfolded NF_def hdd]])
have mt': ‹didx_ok G ?sts (NF # drop d Xs) (p' # drop d istk)›
unfolding NF_def p'_def hdd by (rule didx_ok_push[OF tab mt d_lt])
have sng0: ‹fst pr ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
unfolding RA_def
by (rule red_set_anchored_singleton[OF sh ne tmS sngI fresh])
have slot0: ‹⋀l. l ∈ irep_set RA ⟹ ∃pra R⇩0. fst pra = fst pr ∧
(pra, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! d)) ∧ l ∈ irep_set R⇩0›
proof -
fix l assume l: ‹l ∈ irep_set RA›
then obtain R where R: ‹(pr, d, R) ∈ set (xclosure_auto G (hd Xs))›
and lR: ‹l ∈ irep_set R›
unfolding RA_def red_set_correct d_def[symmetric] by blast
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
show ‹∃pra R⇩0. fst pra = fst pr ∧
(pra, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! d)) ∧ l ∈ irep_set R⇩0›
proof (cases d)
case 0
have ‹(pr, 0, R) ∈ set (xclosure_auto G (Xs ! d))›
using R hd0 unfolding 0 by simp
then show ?thesis using lR by blast
next
case (Suc d')
have kern: ‹(pr, d, R) ∈ set (Xs ! 0)›
by (rule xclosure_auto_kernelD[OF R[unfolded hd0]]) (simp add: Suc)
have z_lt: ‹0 < length Xs› using ne by simp
have one_le: ‹1 ≤ d› using Suc by simp
from dshape_persist[OF sh kern z_lt one_le] obtain R⇩0 where
m0: ‹(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! (0 + d)))›
and sb: ‹irep_set R ⊆ irep_set R⇩0› by blast
have ‹(pr, 0, R⇩0) ∈ set (xclosure_auto G (Xs ! d))› using m0 by simp
then show ?thesis using sb lR by blast
qed
qed
have ‹strack G Shn (NF # drop d Xs) ((Nt (fst pr), RA) # drop d α) (p' # drop d istk)›
proof (rule strack_push[OF trd NF_def p'eq mt'])
show ‹⋀a. Nt (fst pr) = Tm a ⟹ ∃c. RA = FinRep [c]› by simp
show ‹⋀B. Nt (fst pr) = Nt B ⟹ B ∈ set (anchored_nts G) ⟹ ∃c. irep_set RA ⊆ {c}›
using sng0 by simp
show ‹⋀B l. Nt (fst pr) = Nt B ⟹ l ∈ irep_set RA ⟹ ∃pra R⇩0. fst pra = B ∧
(pra, 0, R⇩0) ∈ set (xclosure_auto G (hd (drop d Xs))) ∧ l ∈ irep_set R⇩0›
using slot0 unfolding hdd by simp
qed
then show ?thesis unfolding ic' fst_conv snd_conv gc'2 istk'2 by blast
qed
qed
section ‹The descent to the start state›
text ‹The entry pool of the top frame of a tracked stack: the goto label's
anchors, or ‹istart_ind› at the bottom frame.›
definition epool :: ‹('n, 't) is_cfg ⇒ (('n, 't) sym × indrep) list ⇒ nat set› where
‹epool G α = (case α of [] ⇒ {istart_ind G} | (X, RA) # _ ⇒ irep_set RA)›
lemma pin_edgesI:
‹p < length gt ⟹ (X, s) ∈ set (gt ! p) ⟹ (p, X) ∈ set (pin_edges gt s)›
unfolding pin_edges_def by fastforce
text ‹A cursor realised in a frame: its item is in the frame's closure with an
indentation the class holds at, for the lookahead column ‹c›.›
definition icur :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ ('n, 't) witem ⇒ bool›
where
‹icur G X c = (λ(pr, m, σ). ∃R j. (pr, m, R) ∈ set (xclosure_auto G X) ∧
j ∈ irep_set R ∧ wsat σ c j)›
text ‹A cursor realised in a frame at round ‹t› of its closure: the item is
among the frame's slots after ‹t› rounds, with an indentation the class holds
at for the lookahead column ‹c›. \<^const>‹icur› is the fuelled round. The
descent counts rounds down within a frame (a dot-0 item's indentation comes from
a predicting item of an earlier round) and frames down across a pop.›
definition icur_at :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat ⇒ nat ⇒
('n, 't) witem ⇒ bool› where
‹icur_at G X t c = (λ(pr, m, σ). ∃R j. (pr, m, R) ∈ set (xslots G X (xiter G X t)) ∧
j ∈ irep_set R ∧ wsat σ c j)›
lemma icur_at_fuel: ‹icur G X c cur ⟷ icur_at G X (xfuel G X) c cur›
unfolding icur_def icur_at_def xclosure_auto_def xclosure_def by (cases cur) simp
text ‹Where a slot's indentation comes from: an element of a dot-0 pool at round
‹t› is the image of an element of a predicting item's pool at an earlier round.›
lemma xiter_pred:
assumes p: ‹p < length (iprods G)› and j: ‹j ∈ irep_set (xiter G xs t ! p)›
shows ‹∃t' pr' m' R' j'. t' < t ∧ (pr', m', R') ∈ set (xslots G xs (xiter G xs t')) ∧
m' < length (snd pr') ∧ fst (snd pr' ! m') = Nt (fst (iprods G ! p)) ∧
j' ∈ irep_set R' ∧ irel_sat (snd (snd pr' ! m')) j j'›
proof -
have ‹p < length (iprods G) ⟹ j ∈ irep_set (xiter G xs t ! p) ⟹
∃t' pr' m' R' j'. t' < t ∧ (pr', m', R') ∈ set (xslots G xs (xiter G xs t')) ∧
m' < length (snd pr') ∧ fst (snd pr' ! m') = Nt (fst (iprods G ! p)) ∧
j' ∈ irep_set R' ∧ irel_sat (snd (snd pr' ! m')) j j'›
proof (induction t arbitrary: p j)
case 0
then show ?case by simp
next
case (Suc t)
have eq: ‹xiter G xs (Suc t) ! p =
fold (xcontrib (iprods G ! p)) (xslots G xs (xiter G xs t)) (xiter G xs t ! p)›
using xround_nth[OF xiter_length Suc.prems(1)] by simp
have ‹j ∈ irep_set (xiter G xs t ! p) ∪
⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs t)))›
using Suc.prems(2) unfolding eq fold_xcontrib_set .
then show ?case
proof
assume ‹j ∈ irep_set (xiter G xs t ! p)›
from Suc.IH[OF Suc.prems(1) this] show ?thesis by (meson less_SucI)
next
assume ‹j ∈ ⋃ (ximg (iprods G ! p) ` set (xslots G xs (xiter G xs t)))›
then show ?thesis by (fastforce split: if_splits)
qed
qed
from this[OF p j] show ?thesis .
qed
text ‹The pooled width invariant, at any round of \<^const>‹xclosure_auto›.›
lemma xslots_pool:
assumes kern: ‹⋀pr m R j. (pr, m, R) ∈ set xs ⟹ j ∈ irep_set R ⟹
∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
and mem: ‹(pr, m, R) ∈ set (xslots G xs (xiter G xs t))›
and jR: ‹j ∈ irep_set R›
shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G s) ∧ l ∈ P ∧ wsat ρ l j›
using mem
proof (rule xslots_memE)
assume mem2: ‹(pr, m, R) ∈ set xs›
from kern[OF mem2 jR] show ?thesis .
next
fix q assume q: ‹q < length (iprods G)›
and ‹q < length (xiter G xs t)›
and eq: ‹(pr, m, R) = (iprods G ! q, 0, xiter G xs t ! q)›
have ‹j ∈ irep_set (xiter G xs t ! q)› using jR eq by simp
from xiter_pool[OF kern q this] show ?thesis using eq by simp
qed
text ‹The frame-0 pooled width invariant, packaged: every item of the top frame's
slots at any round carries a ‹wreach› class at the tracked precise state,
anchored at some element of the top entry pool.›
lemma strack_pool_at:
assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
and mem: ‹(pr, m, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
and jR: ‹j ∈ irep_set R›
shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
l ∈ epool G α ∧ wsat ρ l j›
proof -
note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have Xs_ne: ‹Xs ≠ []› using lenX by auto
have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
have z_lt: ‹0 < length Xs› using Xs_ne by auto
have live0: ‹lcore (Xs ! 0) ≠ {}› using live hd0 by simp
have cover0: ‹lcore (Xs ! 0) ⊆ set (pr0_states G Shn ! (pstk ! 0))›
using didx_okD[OF mt z_lt live0] by blast
have kern0: ‹⋀pr' m' R' j'. (pr', m', R') ∈ set (Xs ! 0) ⟹
j' ∈ irep_set R' ⟹
∃ρ l. (pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
l ∈ epool G α ∧ wsat ρ l j'›
proof -
fix pr' m' R' j' assume a: ‹(pr', m', R') ∈ set (Xs ! 0)›
and b: ‹j' ∈ irep_set R'›
have cov: ‹(pr', m') ∈ set (pr0_states G Shn ! (pstk ! 0))›
by (rule lcore_subD[OF cover0 a b])
show ‹∃ρ l. (pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
l ∈ epool G α ∧ wsat ρ l j'›
proof (cases α)
case Nil
have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
from wanch_pool_xinit[OF a[unfolded x0] b cov] obtain ρ where
‹(pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
and ‹wsat ρ (istart_ind G) j'› by blast
then show ?thesis unfolding epool_def Nil by auto
next
case (Cons e α')
obtain X⇩0 RA where e: ‹e = (X⇩0, RA)› by (cases e)
have z_la: ‹0 < length α› unfolding Cons by simp
have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA›
using shp[OF z_la] unfolding Cons e by simp
have covL: ‹⋀pra ma Ra ja. (pra, ma, Ra)
∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA) ⟹
ja ∈ irep_set Ra ⟹
(pra, ma) ∈ set (pr0_states G Shn ! (pstk ! 0))›
proof -
fix pra ma Ra ja
assume aa: ‹(pra, ma, Ra)
∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA)›
and bb: ‹ja ∈ irep_set Ra›
have ‹(pra, ma, Ra) ∈ set (Xs ! 0)› using aa f0 by simp
then show ‹(pra, ma) ∈ set (pr0_states G Shn ! (pstk ! 0))›
using bb by (rule lcore_subD[OF cover0])
qed
have ex: ‹∃ρ l. (pr', m', ρ)
∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
l ∈ irep_set RA ∧ wsat ρ l j'›
by (rule wanch_pool_lgoto[OF _ a[unfolded f0] b]) (rule covL)
then show ?thesis unfolding epool_def Cons e by auto
qed
qed
show ?thesis
by (rule xslots_pool[OF _ mem[unfolded hd0] jR]) (rule kern0)
qed
lemma strack_pool:
assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (hd Xs))›
and jR: ‹j ∈ irep_set R›
shows ‹∃ρ l. (pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0))) ∧
l ∈ epool G α ∧ wsat ρ l j›
using mem unfolding xclosure_auto_def xclosure_def
by (rule strack_pool_at[OF tr live _ jR])
text ‹A dot-0 item of the fresh start name is the start item of the bottom frame,
whose pool is ‹{istart_ind}›: no production has the start name on its left (so it
is no slot), and every kernel item above the bottom frame has its dot past 0.›
lemma strack_start_item:
assumes tr: ‹strack G Shn Xs α pstk› and fresh: ‹fresh_name G Shn›
and mem: ‹(pr, 0, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
and shn: ‹fst pr = Shn›
shows ‹α = [] ∧ irep_set R = {istart_ind G}›
proof -
note sh = strackD(1)[OF tr]
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have Xs_ne: ‹Xs ≠ []› using lenX by auto
have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
have kern: ‹(pr, 0, R) ∈ set (hd Xs)›
proof (rule xslots_memE[OF mem])
assume ‹(pr, 0, R) ∈ set (hd Xs)›
then show ?thesis .
next
fix p assume ‹(pr, 0, R) = (iprods G ! p, 0, xiter G (hd Xs) t ! p)›
and ‹p < length (iprods G)›
then have ‹pr ∈ set (iprods G)› by auto
then have ‹Shn ∈ fst ` set (iprods G)› using shn by force
then show ?thesis using fresh unfolding fresh_name_def by blast
qed
show ?thesis
proof (cases α)
case Nil
have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
then show ?thesis using kern hd0 unfolding Nil xinit_def by auto
next
case (Cons e α')
obtain X⇩0 RA where e: ‹e = (X⇩0, RA)› by (cases e)
have z_la: ‹0 < length α› unfolding Cons by simp
have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA›
using shp[OF z_la] unfolding Cons e by simp
have ‹(pr, 0, R) ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA)›
using kern hd0 f0 by simp
from lgoto_dot_pos[OF this] show ?thesis by simp
qed
qed
text ‹A kernel item of the top frame is the goto image of an item of the frame
below: the symbol before its dot is the entry's, its pool is the lower item's
filtered by the dot's relation against the entry pool.›
lemma strack_pop:
assumes tr: ‹strack G Shn Xs α pstk›
and mem: ‹(pr, Suc m, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
and jR: ‹j ∈ irep_set R›
obtains X⇩0 RA α' R' l where ‹α = (X⇩0, RA) # α'› and ‹m < length (snd pr)›
and ‹fst (snd pr ! m) = X⇩0› and ‹(pr, m, R') ∈ set (xclosure_auto G (Xs ! 1))›
and ‹j ∈ irep_set R'› and ‹l ∈ irep_set RA› and ‹irel_sat (snd (snd pr ! m)) l j›
proof -
have sh: ‹dshape G Shn Xs α› using strackD(1)[OF tr] .
have len: ‹length Xs = length α + 1› by (rule dshapeD(1)[OF sh])
have last: ‹Xs ! length α = xinit G Shn› by (rule dshapeD(2)[OF sh])
have hd: ‹hd Xs = Xs ! 0› using len by (cases Xs) auto
have mem0: ‹(pr, Suc m, R) ∈ set (Xs ! 0)›
using mem unfolding hd by (auto dest: xslots_memE)
obtain X⇩0 RA α' where α: ‹α = (X⇩0, RA) # α'›
proof (cases α)
case Nil
then have ‹Xs ! 0 = xinit G Shn› using last by simp
with mem0 show thesis unfolding xinit_def by simp
next
case (Cons a α')
then show thesis using that by (cases a) auto
qed
have ‹0 < length α› unfolding α by simp
from dshapeD(3)[OF sh this] have X0eq:
‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) (fst (α ! 0)) (snd (α ! 0))› .
from mem0 have ‹(pr, Suc m, R) ∈ set (lgoto (xclosure_auto G (Xs ! 1)) X⇩0 RA)›
unfolding X0eq α by simp
from lgoto_kernel_step[OF this] obtain R⇩s where
m_lt: ‹m < length (snd pr)› and fstm: ‹fst (snd pr ! m) = X⇩0›
and Rs: ‹(pr, m, R⇩s) ∈ set (xclosure_auto G (Xs ! 1))›
and Req: ‹R = irep_inter R⇩s (irep_pre (snd (snd pr ! m)) RA)› .
from jR obtain l where ‹j ∈ irep_set R⇩s› and ‹l ∈ irep_set RA›
and ‹irel_sat (snd (snd pr ! m)) l j› unfolding Req by auto
then show thesis by (rule that[OF α m_lt fstm Rs, of l])
qed
text ‹The tracked indices of the two top frames are adjacent along the entry
symbol, so the edge is in \<^const>‹pin_edges›: the lower item is in the lower
state's LR(0) closure, hence the goto entry is in its row of the table.›
lemma strack_edge:
assumes tr: ‹strack G Shn Xs ((X⇩0, RA) # α') pstk›
and mem: ‹(pr, m, R) ∈ set (xclosure_auto G (Xs ! 1))› and jR: ‹j ∈ irep_set R›
and m: ‹m < length (snd pr)› and X: ‹fst (snd pr ! m) = X⇩0›
shows ‹pstk ! 1 < length (pr0_states G Shn) ∧
(pstk ! 1, X⇩0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
proof -
have live1: ‹lcore (Xs ! 1) ≠ {}› using closure_live_kernel[OF mem jR] .
have len: ‹length Xs = length ((X⇩0, RA) # α') + 1›
using dshapeD(1)[OF strackD(1)[OF tr]] .
then have lt: ‹1 < length Xs› by simp
have ok: ‹didx_ok G (pr0_states G Shn) Xs pstk› using strackD(2)[OF tr] .
from didx_okD[OF ok lt live1]
have lt1: ‹pstk ! 1 < length (pr0_states G Shn)›
and cover1: ‹lcore (Xs ! 1) ⊆ set (pr0_states G Shn ! (pstk ! 1))› by blast+
have kern: ‹⋀pr m R. (pr, m, R) ∈ set (Xs ! 1) ⟹ irep_nonempty R ⟹
(pr, m) ∈ set (pr0_states G Shn ! (pstk ! 1))›
using lcore_subD_ne[OF cover1] .
have creach: ‹(pr, m) ∈ set (creach G (pr0_states G Shn ! (pstk ! 1)))›
using xclosure_auto_live_creach[OF kern mem jR] .
have tab: ‹(X⇩0, st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! 1))) X⇩0))
∈ set (pgtab G (pr0_states G Shn) ! (pstk ! 1))›
using pgtab_mem[OF lt1 creach m] X by simp
have p0: ‹pstk ! 0 = st_find (pr0_states G Shn)
(cgoto (creach G (pr0_states G Shn ! (pstk ! 1))) X⇩0)›
using strackD(7)[OF tr, rule_format, of 0] by simp
show ?thesis
using lt1 tab p0 pin_edgesI[of ‹pstk ! 1› ‹pgtab G (pr0_states G Shn)›] by simp
qed
text ‹A rigid entry's pool is a singleton: a token's column, or an anchored
nonterminal's.›
lemma strack_rigid:
assumes tr: ‹strack G Shn Xs ((X⇩0, RA) # α') pstk›
and rig: ‹irigid (anchored_nts G) X⇩0›
shows ‹∃col. irep_set RA ⊆ {col}›
proof (cases X⇩0)
case (Tm a)
from strackD(4)[OF tr] Tm obtain c where ‹RA = FinRep [c]› by fastforce
then show ?thesis by simp
next
case (Nt B)
from rig Nt have ‹B ∈ set (anchored_nts G)› by (simp add: irigid_def)
with strackD(5)[OF tr] Nt show ?thesis by fastforce
qed
text ‹The prediction step: a realised dot-0 cursor of a production has a realised
predecessor among \<^const>‹ipreds›, at an earlier round of the same frame.›
lemma strack_predict:
assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
and cur: ‹icur_at G (hd Xs) t c (pr, 0, σ)› and shn: ‹fst pr ≠ Shn›
shows ‹∃t' cur'. t' < t ∧ icur_at G (hd Xs) t' c cur' ∧
cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0) (fst pr) σ)›
proof -
note sh = strackD(1)[OF tr] and mt = strackD(2)[OF tr]
note lenX = dshapeD(1)[OF sh] and bot = dshapeD(2)[OF sh] and shp = dshapeD(3)[OF sh]
have Xs_ne: ‹Xs ≠ []› using lenX by auto
have hd0: ‹hd Xs = Xs ! 0› using Xs_ne by (simp add: hd_conv_nth)
have z_lt: ‹0 < length Xs› using Xs_ne by auto
have live0: ‹lcore (Xs ! 0) ≠ {}› using live hd0 by simp
obtain R j where mem: ‹(pr, 0, R) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t))›
and jR: ‹j ∈ irep_set R› and wj: ‹wsat σ c j›
using cur unfolding icur_at_def by auto
have nokern: ‹(pr, 0, R) ∉ set (hd Xs)›
proof
assume kern: ‹(pr, 0, R) ∈ set (hd Xs)›
show False
proof (cases α)
case Nil
have x0: ‹Xs ! 0 = xinit G Shn› using bot unfolding Nil by simp
then show ?thesis using kern hd0 shn unfolding Nil xinit_def by auto
next
case (Cons e α')
obtain X⇩0 RA where e: ‹e = (X⇩0, RA)› by (cases e)
have z_la: ‹0 < length α› unfolding Cons by simp
have f0: ‹Xs ! 0 = lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA›
using shp[OF z_la] unfolding Cons e by simp
have ‹(pr, 0, R) ∈ set (lgoto (xclosure_auto G (Xs ! Suc 0)) X⇩0 RA)›
using kern hd0 f0 by simp
from lgoto_dot_pos[OF this] show False by simp
qed
qed
obtain p where p: ‹p < length (iprods G)› and pr: ‹pr = iprods G ! p›
and R: ‹R = xiter G (hd Xs) t ! p›
using mem nokern by (auto elim!: xslots_memE)
obtain t' pr' m' R' j' where tt: ‹t' < t›
and mem': ‹(pr', m', R') ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t'))›
and m': ‹m' < length (snd pr')› and nt: ‹fst (snd pr' ! m') = Nt (fst pr)›
and j'R: ‹j' ∈ irep_set R'› and rel: ‹irel_sat (snd (snd pr' ! m')) j j'›
using xiter_pred[OF p jR[unfolded R]] unfolding pr by blast
obtain ρ where rho: ‹(pr', m', ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
using strack_pool_at[OF tr live mem' j'R] by blast
have idx: ‹pstk ! 0 < length (pr0_states G Shn)›
using didx_okD[OF mt z_lt live0] by blast
have rho': ‹(pr', m', ρ) ∈ set (map (wreach G) (pr0_states G Shn) ! (pstk ! 0))›
using rho idx by simp
define cur' where ‹cur' = (pr', m', wcomp (w_of (snd (snd pr' ! m'))) σ)›
have ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0) (fst pr) σ)›
unfolding ipreds_def cur'_def set_remdups
by (rule map_filterI[OF rho']) (simp add: m' nt)
moreover have ‹icur_at G (hd Xs) t' c cur'›
unfolding icur_at_def cur'_def
using mem' j'R wcomp_sound[OF wj w_of_sound[OF rel]] by auto
ultimately show ?thesis using tt by blast
qed
text ‹The pop step: two realised kernel cursors have the entry symbol before
their dots, are not disjoint at a rigid entry, and pop to realised cursors of the
frame below along an edge of \<^const>‹pin_edges›, both items in the lower
state's closure.›
lemma strack_pop_step:
assumes tr: ‹strack G Shn Xs α pstk› and live: ‹lcore (hd Xs) ≠ {}›
and c1: ‹icur_at G (hd Xs) t⇩1 c (pr⇩1, Suc m⇩1, σ⇩1)›
and c2: ‹icur_at G (hd Xs) t⇩2 c (pr⇩2, Suc m⇩2, σ⇩2)›
shows ‹∃X⇩0 RA α'. α = (X⇩0, RA) # α' ∧
fst (snd pr⇩1 ! m⇩1) = X⇩0 ∧ fst (snd pr⇩2 ! m⇩2) = X⇩0 ∧
(irigid (anchored_nts G) X⇩0 ⟶
¬ wdisjoint (itrans (pr⇩1, Suc m⇩1, σ⇩1)) (itrans (pr⇩2, Suc m⇩2, σ⇩2))) ∧
strack G Shn (tl Xs) α' (tl pstk) ∧ lcore (hd (tl Xs)) ≠ {} ∧
icur G (hd (tl Xs)) c (pr⇩1, m⇩1, σ⇩1) ∧ icur G (hd (tl Xs)) c (pr⇩2, m⇩2, σ⇩2) ∧
(pstk ! 1, X⇩0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0)) ∧
ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩1 m⇩1 ∧
ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩2 m⇩2›
proof -
from c1 obtain R⇩1 j⇩1 where
mem1: ‹(pr⇩1, Suc m⇩1, R⇩1) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t⇩1))›
and j1: ‹j⇩1 ∈ irep_set R⇩1› and w1: ‹wsat σ⇩1 c j⇩1›
by (auto simp: icur_at_def)
from c2 obtain R⇩2 j⇩2 where
mem2: ‹(pr⇩2, Suc m⇩2, R⇩2) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t⇩2))›
and j2: ‹j⇩2 ∈ irep_set R⇩2› and w2: ‹wsat σ⇩2 c j⇩2›
by (auto simp: icur_at_def)
obtain X⇩0 RA α' R⇩1' l⇩1 where α1: ‹α = (X⇩0, RA) # α'›
and lt1: ‹m⇩1 < length (snd pr⇩1)› and X1: ‹fst (snd pr⇩1 ! m⇩1) = X⇩0›
and mem1': ‹(pr⇩1, m⇩1, R⇩1') ∈ set (xclosure_auto G (Xs ! 1))›
and j1': ‹j⇩1 ∈ irep_set R⇩1'› and l1: ‹l⇩1 ∈ irep_set RA›
and rel1: ‹irel_sat (snd (snd pr⇩1 ! m⇩1)) l⇩1 j⇩1›
by (rule strack_pop[OF tr mem1 j1])
obtain X⇩0' RA' α'' R⇩2' l⇩2 where α2: ‹α = (X⇩0', RA') # α''›
and lt2: ‹m⇩2 < length (snd pr⇩2)› and X2: ‹fst (snd pr⇩2 ! m⇩2) = X⇩0'›
and mem2': ‹(pr⇩2, m⇩2, R⇩2') ∈ set (xclosure_auto G (Xs ! 1))›
and j2': ‹j⇩2 ∈ irep_set R⇩2'› and l2: ‹l⇩2 ∈ irep_set RA'›
and rel2: ‹irel_sat (snd (snd pr⇩2 ! m⇩2)) l⇩2 j⇩2›
by (rule strack_pop[OF tr mem2 j2])
from α1 α2 have eq: ‹X⇩0' = X⇩0› ‹RA' = RA› by simp_all
have tr1: ‹strack G Shn Xs ((X⇩0, RA) # α') pstk› using tr unfolding α1 .
have tr': ‹strack G Shn (tl Xs) α' (tl pstk)› using strack_tl[OF tr1] .
have len: ‹length Xs = length α + 1› using dshapeD(1)[OF strackD(1)[OF tr]] .
have lenp: ‹length pstk = length Xs› using didx_ok_len[OF strackD(2)[OF tr]] .
have hdtl: ‹hd (tl Xs) = Xs ! 1› using len α1 by (cases Xs; cases ‹tl Xs›) auto
have tlp: ‹tl pstk ! 0 = pstk ! 1› using lenp len α1 by (cases pstk) auto
have rig: ‹irigid (anchored_nts G) X⇩0 ⟹
¬ wdisjoint (itrans (pr⇩1, Suc m⇩1, σ⇩1)) (itrans (pr⇩2, Suc m⇩2, σ⇩2))›
proof -
assume rg: ‹irigid (anchored_nts G) X⇩0›
from strack_rigid[OF tr1 rg] obtain col where sub: ‹irep_set RA ⊆ {col}› ..
with l1 l2 eq have lc: ‹l⇩1 = col› ‹l⇩2 = col› by auto
have s1: ‹wsat (itrans (pr⇩1, Suc m⇩1, σ⇩1)) c l⇩1›
using wcomp_sound[OF w1 winv_sound[OF w_of_sound[OF rel1]]] by (simp add: itrans_def)
have s2: ‹wsat (itrans (pr⇩2, Suc m⇩2, σ⇩2)) c l⇩2›
using wcomp_sound[OF w2 winv_sound[OF w_of_sound[OF rel2]]] by (simp add: itrans_def)
show ‹¬ wdisjoint (itrans (pr⇩1, Suc m⇩1, σ⇩1)) (itrans (pr⇩2, Suc m⇩2, σ⇩2))›
by (rule wdisjoint_sound[where l = col, OF s1[unfolded lc(1)] s2[unfolded lc(2)]])
qed
have live': ‹lcore (hd (tl Xs)) ≠ {}›
unfolding hdtl by (rule closure_live_kernel[OF mem1' j1'])
have ic1: ‹icur G (hd (tl Xs)) c (pr⇩1, m⇩1, σ⇩1)›
using mem1' j1' w1 unfolding hdtl icur_def by auto
have ic2: ‹icur G (hd (tl Xs)) c (pr⇩2, m⇩2, σ⇩2)›
using mem2' j2' w2 unfolding hdtl icur_def by auto
have edge1: ‹pstk ! 1 < length (pr0_states G Shn) ∧
(pstk ! 1, X⇩0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
using strack_edge[OF tr1 mem1' j1' lt1 X1] .
have pool: ‹⋀pr m R j. (pr, m, R) ∈ set (xclosure_auto G (Xs ! 1)) ⟹
j ∈ irep_set R ⟹ ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr m›
proof -
fix pr m R j
assume mm: ‹(pr, m, R) ∈ set (xclosure_auto G (Xs ! 1))› and jj: ‹j ∈ irep_set R›
from strack_pool[OF tr' live' mm[folded hdtl] jj] obtain ρ where
‹(pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (tl pstk ! 0)))› by blast
then have ‹(pr, m, ρ) ∈ set (map (wreach G) (pr0_states G Shn) ! (pstk ! 1))›
using edge1 tlp by simp
then show ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr m›
unfolding ihas_def list_ex_iff by auto
qed
have h1: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩1 m⇩1›
by (rule pool[OF mem1' j1'])
have h2: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩2 m⇩2›
by (rule pool[OF mem2' j2'])
show ?thesis
using α1 X1 X2 eq rig tr' live' ic1 ic2 edge1 h1 h2 by auto
qed
text ‹One step of the descent: a realised triple fires, or has a realised
successor with fewer frames, or as many frames and fewer rounds.›
lemma strack_step:
assumes tr: ‹strack G Shn Xs α pstk› and fresh: ‹fresh_name G Shn›
and live: ‹lcore (hd Xs) ≠ {}›
and c1: ‹icur_at G (hd Xs) t⇩1 c cur⇩1› and c2: ‹icur_at G (hd Xs) t⇩2 c cur⇩2›
shows ‹ifires Shn (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2) ∨
(∃Xs' α' pstk' t⇩1' t⇩2' cur⇩1' cur⇩2'.
(pstk' ! 0, cur⇩1', cur⇩2') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2)) ∧
strack G Shn Xs' α' pstk' ∧ lcore (hd Xs') ≠ {} ∧
icur_at G (hd Xs') t⇩1' c cur⇩1' ∧ icur_at G (hd Xs') t⇩2' c cur⇩2' ∧
(length Xs' < length Xs ∨ length Xs' = length Xs ∧ t⇩1' + t⇩2' < t⇩1 + t⇩2))›
proof -
obtain pr⇩1 m⇩1 σ⇩1 where cur1: ‹cur⇩1 = (pr⇩1, m⇩1, σ⇩1)› by (cases cur⇩1) auto
obtain pr⇩2 m⇩2 σ⇩2 where cur2: ‹cur⇩2 = (pr⇩2, m⇩2, σ⇩2)› by (cases cur⇩2) auto
have len: ‹length Xs = length α + 1› using dshapeD(1)[OF strackD(1)[OF tr]] .
have plen: ‹length pstk = length Xs› using didx_ok_len[OF strackD(2)[OF tr]] .
have c1': ‹icur_at G (hd Xs) t⇩1 c (pr⇩1, m⇩1, σ⇩1)› using c1 cur1 by simp
have c2': ‹icur_at G (hd Xs) t⇩2 c (pr⇩2, m⇩2, σ⇩2)› using c2 cur2 by simp
consider (A) ‹m⇩1 = 0› ‹fst pr⇩1 ≠ Shn›
| (B) ‹¬ (m⇩1 = 0 ∧ fst pr⇩1 ≠ Shn)› ‹m⇩2 = 0› ‹fst pr⇩2 ≠ Shn›
| (C) ‹m⇩1 = 0› ‹fst pr⇩1 = Shn› ‹m⇩2 = 0› ‹fst pr⇩2 = Shn›
| (D1) ‹m⇩1 = 0› ‹fst pr⇩1 = Shn› ‹m⇩2 ≠ 0›
| (D2) ‹m⇩2 = 0› ‹fst pr⇩2 = Shn› ‹m⇩1 ≠ 0›
| (E) ‹m⇩1 ≠ 0› ‹m⇩2 ≠ 0›
by auto
then show ?thesis
proof cases
case A
have c1z: ‹icur_at G (hd Xs) t⇩1 c (pr⇩1, 0, σ⇩1)› using c1' A(1) by simp
obtain t' cur' where lt: ‹t' < t⇩1› and ic: ‹icur_at G (hd Xs) t' c cur'›
and mem: ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0)
(fst pr⇩1) σ⇩1)›
using strack_predict[OF tr live c1z A(2)] by blast
have succ: ‹(pstk ! 0, cur', cur⇩2) ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2))›
using mem A by (simp add: cur1 cur2)
show ?thesis using succ tr live ic c2 lt
by (intro disjI2 exI[of _ Xs] exI[of _ α] exI[of _ pstk] exI[of _ t'] exI[of _ t⇩2]
exI[of _ cur'] exI[of _ cur⇩2] conjI) auto
next
case B
have c2z: ‹icur_at G (hd Xs) t⇩2 c (pr⇩2, 0, σ⇩2)› using c2' B(2) by simp
obtain t' cur' where lt: ‹t' < t⇩2› and ic: ‹icur_at G (hd Xs) t' c cur'›
and mem: ‹cur' ∈ set (ipreds (map (wreach G) (pr0_states G Shn)) (pstk ! 0)
(fst pr⇩2) σ⇩2)›
using strack_predict[OF tr live c2z B(3)] by blast
have succ: ‹(pstk ! 0, cur⇩1, cur') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2))›
using mem B by (simp add: cur1 cur2 B(1))
show ?thesis using succ tr live ic c1 lt
by (intro disjI2 exI[of _ Xs] exI[of _ α] exI[of _ pstk] exI[of _ t⇩1] exI[of _ t']
exI[of _ cur⇩1] exI[of _ cur'] conjI) auto
next
case C
have c1z: ‹icur_at G (hd Xs) t⇩1 c (pr⇩1, 0, σ⇩1)› using c1' C(1) by simp
have c2z: ‹icur_at G (hd Xs) t⇩2 c (pr⇩2, 0, σ⇩2)› using c2' C(3) by simp
obtain R⇩1 j⇩1 where s1: ‹(pr⇩1, 0, R⇩1) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t⇩1))›
and j1: ‹j⇩1 ∈ irep_set R⇩1› and w1: ‹wsat σ⇩1 c j⇩1›
using c1z unfolding icur_at_def by auto
obtain R⇩2 j⇩2 where s2: ‹(pr⇩2, 0, R⇩2) ∈ set (xslots G (hd Xs) (xiter G (hd Xs) t⇩2))›
and j2: ‹j⇩2 ∈ irep_set R⇩2› and w2: ‹wsat σ⇩2 c j⇩2›
using c2z unfolding icur_at_def by auto
have r1: ‹irep_set R⇩1 = {istart_ind G}›
using strack_start_item[OF tr fresh s1 C(2)] by simp
have r2: ‹irep_set R⇩2 = {istart_ind G}›
using strack_start_item[OF tr fresh s2 C(4)] by simp
have ‹j⇩1 = j⇩2› using j1 j2 r1 r2 by simp
then have nd: ‹¬ wdisjoint σ⇩1 σ⇩2› using wdisjoint_sound w1 w2 by blast
show ?thesis using nd by (simp add: cur1 cur2 C)
next
case D1
show ?thesis using D1 by (simp add: cur1 cur2)
next
case D2
show ?thesis using D2 by (simp add: cur1 cur2)
next
case E
obtain m⇩1' where m1: ‹m⇩1 = Suc m⇩1'› using E(1) by (cases m⇩1) auto
obtain m⇩2' where m2: ‹m⇩2 = Suc m⇩2'› using E(2) by (cases m⇩2) auto
have c1s: ‹icur_at G (hd Xs) t⇩1 c (pr⇩1, Suc m⇩1', σ⇩1)› using c1' m1 by simp
have c2s: ‹icur_at G (hd Xs) t⇩2 c (pr⇩2, Suc m⇩2', σ⇩2)› using c2' m2 by simp
obtain X⇩0 RA α' where al: ‹α = (X⇩0, RA) # α'›
and x1: ‹fst (snd pr⇩1 ! m⇩1') = X⇩0› and x2: ‹fst (snd pr⇩2 ! m⇩2') = X⇩0›
and rig: ‹irigid (anchored_nts G) X⇩0 ⟶
¬ wdisjoint (itrans (pr⇩1, Suc m⇩1', σ⇩1)) (itrans (pr⇩2, Suc m⇩2', σ⇩2))›
and tr': ‹strack G Shn (tl Xs) α' (tl pstk)› and live': ‹lcore (hd (tl Xs)) ≠ {}›
and ic1: ‹icur G (hd (tl Xs)) c (pr⇩1, m⇩1', σ⇩1)›
and ic2: ‹icur G (hd (tl Xs)) c (pr⇩2, m⇩2', σ⇩2)›
and edge: ‹(pstk ! 1, X⇩0) ∈ set (pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0))›
and h1: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩1 m⇩1'›
and h2: ‹ihas (map (wreach G) (pr0_states G Shn) ! (pstk ! 1)) pr⇩2 m⇩2'›
using strack_pop_step[OF tr live c1s c2s] by blast
have hlen: ‹length Xs = length α' + 2› using len al by simp
have nth1: ‹tl pstk ! 0 = pstk ! 1› using plen hlen by (simp add: nth_tl)
have mf: ‹(pstk ! 1, (pr⇩1, m⇩1', σ⇩1), (pr⇩2, m⇩2', σ⇩2)) ∈ set (List.map_filter
(λ(p, X'). if X' = X⇩0 ∧ ihas (map (wreach G) (pr0_states G Shn) ! p) pr⇩1 m⇩1'
∧ ihas (map (wreach G) (pr0_states G Shn) ! p) pr⇩2 m⇩2'
then Some (p, (pr⇩1, m⇩1', σ⇩1), (pr⇩2, m⇩2', σ⇩2)) else None)
(pin_edges (pgtab G (pr0_states G Shn)) (pstk ! 0)))›
by (rule map_filterI[OF edge])
(simp add: h1[unfolded One_nat_def] h2[unfolded One_nat_def])
have succ: ‹(pstk ! 1, (pr⇩1, m⇩1', σ⇩1), (pr⇩2, m⇩2', σ⇩2)) ∈ set (isuccs Shn
(map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn)) (anchored_nts G)
(pstk ! 0, cur⇩1, cur⇩2))›
using rig mf by (simp add: cur1 cur2 m1 m2 x1 x2 cong: if_cong)
have ict1: ‹icur_at G (hd (tl Xs)) (xfuel G (hd (tl Xs))) c (pr⇩1, m⇩1', σ⇩1)›
using ic1 icur_at_fuel by blast
have ict2: ‹icur_at G (hd (tl Xs)) (xfuel G (hd (tl Xs))) c (pr⇩2, m⇩2', σ⇩2)›
using ic2 icur_at_fuel by blast
have shorter: ‹length (tl Xs) < length Xs› using hlen by simp
show ?thesis
using succ[folded nth1] tr' live' ict1 ict2 shorter by blast
qed
qed
text ‹The descent, by induction on the frames and then on the rounds: from a
tracked stack whose top frame realises both cursors of a triple, the walk's
successor relation reaches a triple that fires.›
lemma strack_fires_at:
‹∀Xs α pstk t⇩1 t⇩2 cur⇩1 cur⇩2. length Xs = n ⟶ t⇩1 + t⇩2 = k ⟶
strack G Shn Xs α pstk ⟶ fresh_name G Shn ⟶ lcore (hd Xs) ≠ {} ⟶
icur_at G (hd Xs) t⇩1 c cur⇩1 ⟶ icur_at G (hd Xs) t⇩2 c cur⇩2 ⟶
(∃t'. (λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) t))⇧*⇧* (pstk ! 0, cur⇩1, cur⇩2) t' ∧
ifires Shn (anchored_nts G) t')›
proof (induction n arbitrary: k rule: less_induct)
case (less n)
note IHn = less.IH
show ?case
proof (induction k rule: less_induct)
case (less k)
note IHk = less.IH
let ?R = ‹λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) t)›
show ?case
proof (intro allI impI)
fix Xs α pstk t⇩1 t⇩2 cur⇩1 cur⇩2
assume len: ‹length Xs = n› and sum: ‹t⇩1 + t⇩2 = k›
and tr: ‹strack G Shn Xs α pstk›
and fresh: ‹fresh_name G Shn› and live: ‹lcore (hd Xs) ≠ {}›
and c1: ‹icur_at G (hd Xs) t⇩1 c cur⇩1› and c2: ‹icur_at G (hd Xs) t⇩2 c cur⇩2›
from strack_step[OF tr fresh live c1 c2]
show ‹∃t'. ?R⇧*⇧* (pstk ! 0, cur⇩1, cur⇩2) t' ∧ ifires Shn (anchored_nts G) t'›
proof
assume ‹ifires Shn (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2)›
then show ?thesis by blast
next
assume ‹∃Xs' α' pstk' t⇩1' t⇩2' cur⇩1' cur⇩2'.
(pstk' ! 0, cur⇩1', cur⇩2') ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2)) ∧
strack G Shn Xs' α' pstk' ∧ lcore (hd Xs') ≠ {} ∧
icur_at G (hd Xs') t⇩1' c cur⇩1' ∧ icur_at G (hd Xs') t⇩2' c cur⇩2' ∧
(length Xs' < length Xs ∨ length Xs' = length Xs ∧ t⇩1' + t⇩2' < t⇩1 + t⇩2)›
then obtain Xs' α' pstk' t⇩1' t⇩2' cur⇩1' cur⇩2'
where succ: ‹(pstk' ! 0, cur⇩1', cur⇩2') ∈ set (isuccs Shn
(map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn))
(anchored_nts G) (pstk ! 0, cur⇩1, cur⇩2))›
and tr': ‹strack G Shn Xs' α' pstk'› and live': ‹lcore (hd Xs') ≠ {}›
and c1': ‹icur_at G (hd Xs') t⇩1' c cur⇩1'›
and c2': ‹icur_at G (hd Xs') t⇩2' c cur⇩2'›
and dec: ‹length Xs' < length Xs ∨
length Xs' = length Xs ∧ t⇩1' + t⇩2' < t⇩1 + t⇩2›
by blast
from dec have ‹∃t'. ?R⇧*⇧* (pstk' ! 0, cur⇩1', cur⇩2') t' ∧
ifires Shn (anchored_nts G) t'›
proof
assume lt: ‹length Xs' < length Xs›
from IHn[of ‹length Xs'› ‹t⇩1' + t⇩2'›] lt len
show ?thesis using tr' fresh live' c1' c2' by blast
next
assume ‹length Xs' = length Xs ∧ t⇩1' + t⇩2' < t⇩1 + t⇩2›
with IHk[of ‹t⇩1' + t⇩2'›] len sum
show ?thesis using tr' fresh live' c1' c2' by blast
qed
then show ?thesis using succ by (meson converse_rtranclp_into_rtranclp)
qed
qed
qed
qed
theorem strack_fires:
assumes tr: ‹strack G Shn Xs α pstk›
and fresh: ‹fresh_name G Shn›
and live: ‹lcore (hd Xs) ≠ {}›
and c1: ‹icur G (hd Xs) c cur⇩1› and c2: ‹icur G (hd Xs) c cur⇩2›
shows ‹∃t'. (λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) t))⇧*⇧* (pstk ! 0, cur⇩1, cur⇩2) t' ∧
ifires Shn (anchored_nts G) t'›
using strack_fires_at[rule_format, OF refl refl tr fresh live] c1 c2
unfolding icur_at_fuel by blast
section ‹Sufficiency of the item-relative check›
text ‹The final assembly: ‹rlalr_conflicts G Shn = []› plus
\<^const>‹fresh_name› implies \<^const>‹mdet›. A determinism violation
yields two live candidates at a tracked, live top frame; each candidate's
runtime license transports to a static seed at the tracked state
(\<^const>‹ireds_at› / \<^const>‹ishifts›) that the frame realises
(\<^const>‹icur›), the pair of cursors is in \<^const>‹ipairs_at›, the
empty report makes the walk return ‹False›, and ‹strack_fires› +
‹ifire_sound› close the contradiction. ‹None›/‹None› pairs are
refuted by \<^const>‹rr_none_at› directly; a reduce of the fresh start
name cannot have a live successor.›
text ‹Membership constructors for the static seeds.›
lemma ireds_at_memI:
assumes cell: ‹(i, (pr, length (snd pr)), t, τ) ∈ set L›
and shn: ‹fst pr ≠ Shn›
and wmem: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (sp ! i))›
shows ‹(t, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn sp L i)›
unfolding ireds_at_def Let_def
by (rule map_filterI[OF cell]) (use shn wmem in ‹auto simp: list_ex_iff›)
lemma ishifts_memI:
assumes ‹(pr, m, ρ) ∈ set ws› and ‹m < length (snd pr)›
and ‹fst (snd pr ! m) = Tm a›
shows ‹(a, (pr, m, w_of (snd (snd pr ! m)))) ∈ set (ishifts ws)›
unfolding ishifts_def set_remdups
by (rule map_filterI[OF assms(1)]) (use assms(2,3) in simp)
lemma ipairs_at_srI:
assumes red: ‹(Some a, c) ∈ set (ireds_at G Shn sp L i)›
and sh: ‹(a, c') ∈ set (ishifts (wreach G (sp ! i)))›
shows ‹(c, c') ∈ set (ipairs_at G Shn sp L i)›
proof -
have ‹(c, c') ∈ set (concat (map (λ(t, c). case t of
Some a ⇒ map (λ(a', c'). (c, c'))
(filter (λ(a', c'). a' = a) (ishifts (wreach G (sp ! i))))
| None ⇒ []) (ireds_at G Shn sp L i)))›
by (rule concat_map_memI[OF red]) (use sh in force)
then show ?thesis unfolding ipairs_at_def Let_def by simp
qed
lemma ipairs_at_rrI:
assumes r1: ‹(Some a, (pr⇩1, m⇩1, τ⇩1)) ∈ set (ireds_at G Shn sp L i)›
and r2: ‹(Some a, (pr⇩2, m⇩2, τ⇩2)) ∈ set (ireds_at G Shn sp L i)›
and ne: ‹pr⇩2 ≠ pr⇩1›
shows ‹((pr⇩1, m⇩1, τ⇩1), (pr⇩2, m⇩2, τ⇩2)) ∈ set (ipairs_at G Shn sp L i)›
proof -
have inner: ‹((pr⇩1, m⇩1, τ⇩1), (pr⇩2, m⇩2, τ⇩2)) ∈ set (List.map_filter (λ(t', c').
if fst c' ≠ fst (pr⇩1, m⇩1, τ⇩1) ∧ t' = Some a ∧ Some a ≠ None
then Some ((pr⇩1, m⇩1, τ⇩1), c') else None)
(ireds_at G Shn sp L i))›
by (rule map_filterI[OF r2]) (use ne in simp)
have ‹((pr⇩1, m⇩1, τ⇩1), (pr⇩2, m⇩2, τ⇩2)) ∈ set (concat (map (λ(t, c).
List.map_filter (λ(t', c').
if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None)
(ireds_at G Shn sp L i)) (ireds_at G Shn sp L i)))›
by (rule concat_map_memI[OF r1]) (use inner in simp)
then show ?thesis unfolding ipairs_at_def Let_def by simp
qed
lemma rr_none_atI:
assumes r1: ‹(None, (pr⇩1, m⇩1, τ⇩1)) ∈ set (ireds_at G Shn sp L i)›
and r2: ‹(None, (pr⇩2, m⇩2, τ⇩2)) ∈ set (ireds_at G Shn sp L i)›
and ne: ‹pr⇩2 ≠ pr⇩1›
shows ‹rr_none_at G Shn sp L i›
proof -
have inner: ‹list_ex (λ(t', c'). fst c' ≠ fst (pr⇩1, m⇩1, τ⇩1) ∧ t' = None)
(ireds_at G Shn sp L i)›
unfolding list_ex_iff by (rule bexI[OF _ r2]) (use ne in simp)
have outer: ‹list_ex (λ(t, c). t = None ∧
list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None)
(ireds_at G Shn sp L i)) (ireds_at G Shn sp L i)›
unfolding list_ex_iff
by (rule bexI[OF _ r1]) (use inner in ‹fastforce simp: list_ex_iff›)
show ?thesis unfolding rr_none_at_def Let_def using outer by simp
qed
lemma dcands_shift_or_reduce:
assumes ‹a ∈ set (dcands G i cells CL (Xs, w))›
shows ‹a = DShift ∧ w ≠ [] ∨ (∃pr. a = DReduce pr ∧
irep_nonempty (red_set CL pr) ∧ dlic i cells w pr (red_set CL pr))›
using assms unfolding dcands_def
by (auto simp: Let_def split: if_splits list.splits)
text ‹A reduce of the fresh start name has no live successor: the goto
frame's kernel items would need ‹Nt Shn› at a dot of the exposed frame's
closure, but ‹Shn› occurs in no grammar symbol.›
lemma shn_reduce_dead:
assumes tr: ‹strack G Shn Xs α pstk›
and fresh: ‹fresh_name G Shn›
and step: ‹mstep G (Xs, w) (DReduce pr) = Some gc'›
and shn: ‹fst pr = Shn›
and lv: ‹dlive gc'›
shows False
proof -
note mt = strackD(2)[OF tr]
have step': ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) (DReduce pr) = Some gc'›
using step unfolding mstep_def by simp
define d where ‹d = length (snd pr)›
have d_lt: ‹d < length Xs›
unfolding d_def by (rule mstep_reduce_shape[OF step']) blast
have gc': ‹gc' = (lgoto (map (xclosure_auto G) Xs ! d) (Nt (fst pr))
(red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
unfolding d_def by (rule mstep_reduce_shape[OF step']) blast
have lvt: ‹dlive (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
(red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs, w)›
using lv unfolding gc' shn using d_lt by simp
from lvt obtain pr⇩1 m⇩1 R⇩1 j⇩1 where
itm0: ‹(pr⇩1, m⇩1, R⇩1) ∈ set (hd (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
(red_set (hd (map (xclosure_auto G) Xs)) pr) # drop d Xs))›
and jR1: ‹j⇩1 ∈ irep_set R⇩1›
by (blast elim: dliveE)
have itm: ‹(pr⇩1, m⇩1, R⇩1) ∈ set (lgoto (xclosure_auto G (Xs ! d)) (Nt Shn)
(red_set (hd (map (xclosure_auto G) Xs)) pr))›
using itm0 by simp
obtain m⇩0 where m1: ‹m⇩1 = Suc m⇩0›
using lgoto_dot_pos[OF itm] by (cases m⇩1) auto
from lgoto_kernel_step[OF itm[unfolded m1]] obtain R⇩s where
src: ‹(pr⇩1, m⇩0, R⇩s) ∈ set (xclosure_auto G (Xs ! d))›
and m0lt: ‹m⇩0 < length (snd pr⇩1)›
and dsym: ‹fst (snd pr⇩1 ! m⇩0) = Nt Shn›
and Req: ‹R⇩1 = irep_inter R⇩s (irep_pre (snd (snd pr⇩1 ! m⇩0))
(red_set (hd (map (xclosure_auto G) Xs)) pr))› .
have jRs: ‹j⇩1 ∈ irep_set R⇩s› using jR1 unfolding Req by simp
have lived: ‹lcore (Xs ! d) ≠ {}› by (rule closure_live_kernel[OF src jRs])
have pd_lt: ‹pstk ! d < length (pr0_states G Shn)›
and coverd: ‹lcore (Xs ! d) ⊆ set (pr0_states G Shn ! (pstk ! d))›
using didx_okD[OF mt d_lt lived] by blast+
have kernD: ‹⋀pr' m' R'. (pr', m', R') ∈ set (Xs ! d) ⟹
irep_nonempty R' ⟹ (pr', m') ∈ set (pr0_states G Shn ! (pstk ! d))›
by (blast intro: lcore_subD_ne[OF coverd])
have srcC: ‹(pr⇩1, m⇩0) ∈ set (creach G (pr0_states G Shn ! (pstk ! d)))›
by (rule xclosure_auto_live_creach[OF kernD src jRs])
have crU: ‹set (creach G (pr0_states G Shn ! (pstk ! d))) ⊆ cuniv G Shn›
by (rule creach_univ[OF pr0_states_univ[OF nth_mem[OF pd_lt]]])
have ‹fst (snd pr⇩1 ! m⇩0) ∈ set (gram_syms G)›
by (rule dot_sym_gram[OF crU srcC m0lt])
then have inG: ‹Nt Shn ∈ set (gram_syms G)› unfolding dsym .
have ‹Nt Shn ∉ set (gram_syms G)›
proof
assume mem: ‹Nt Shn ∈ set (gram_syms G)›
show False
proof (cases ‹Nt Shn = Nt (istart G)›)
case True
then show False using fresh unfolding fresh_name_def by simp
next
case False
have inL: ‹Nt Shn ∈ set (concat (map (λ(A, y). map fst y) (iprods G)))›
using mem False unfolding gram_syms_def by (auto split: if_splits)
from inL obtain A rhs where pmem: ‹(A, rhs) ∈ set (iprods G)›
and inrhs: ‹Nt Shn ∈ set (map fst rhs)› by fastforce
from inrhs obtain e where emem: ‹e ∈ set rhs›
and efst: ‹fst e = Nt Shn› by auto
obtain X r where eeq: ‹e = (X, r)› by (cases e)
have ball2: ‹∀(X', r') ∈ set rhs. X' ≠ Nt Shn›
using fresh pmem unfolding fresh_name_def by fastforce
have ‹X ≠ Nt Shn› using ball2 emem unfolding eeq by fastforce
then show False using efst eeq by simp
qed
qed
then show False using inG by simp
qed
text ‹Each runtime license transports to a static seed at the tracked
state: the driver's reduce cell is a cell of \<^const>‹la_fix› at the
top frame's index, the item it licenses is in the top frame's closure with
an indentation the cell's relation holds at (\<^const>‹icur›), and
\<^text>‹strack_pool› places the item in the state's \<^const>‹wreach›.›
lemma reduce_seed_Some:
assumes tr: ‹strack G Shn Xs α pstk›
and live: ‹lcore (hd Xs) ≠ {}›
and ne: ‹Xs ≠ []›
and lic: ‹dlic (pstk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))
((a, c) # w') pr (red_set (xclosure_auto G (hd Xs)) pr)›
and shn: ‹fst pr ≠ Shn›
shows ‹∃τ. (Some a, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
(la_fix G Shn) (pstk ! 0)) ∧
icur G (hd Xs) c (pr, length (snd pr), τ)›
proof -
note mt = strackD(2)[OF tr]
have z_lt: ‹0 < length Xs› using ne by auto
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have i_lt: ‹pstk ! 0 < length (pr0_states G Shn)›
using didx_okD[OF mt z_lt] live unfolding hd0 by blast
from dlicE[OF lic] obtain τ where
cellb: ‹(pstk ! 0, (pr, length (snd pr)), Some a, τ)
∈ set (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))›
and sat: ‹irep_ex_wsat τ c (red_set (xclosure_auto G (hd Xs)) pr)› .
have cell: ‹(pstk ! 0, (pr, length (snd pr)), Some a, τ) ∈ set (la_fix G Shn)›
using red_buckets_memD[OF i_lt cellb] by blast
from sat obtain j⇩r where
jr: ‹j⇩r ∈ irep_set (red_set (xclosure_auto G (hd Xs)) pr)›
and wt: ‹wsat τ c j⇩r›
unfolding irep_ex_wsat_correct by blast
from jr obtain R⇩r where
mem: ‹(pr, length (snd pr), R⇩r) ∈ set (xclosure_auto G (hd Xs))›
and jrR: ‹j⇩r ∈ irep_set R⇩r›
unfolding red_set_correct by blast
from strack_pool[OF tr live mem jrR] obtain ρ where
wr: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
by blast
have ‹icur G (hd Xs) c (pr, length (snd pr), τ)›
unfolding icur_def using mem jrR wt by auto
then show ?thesis using ireds_at_memI[OF cell shn wr] by blast
qed
lemma reduce_seed_None:
assumes tr: ‹strack G Shn Xs α pstk›
and live: ‹lcore (hd Xs) ≠ {}›
and ne: ‹Xs ≠ []›
and lic: ‹dlic (pstk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))
[] pr (red_set (xclosure_auto G (hd Xs)) pr)›
and nonvac: ‹irep_nonempty (red_set (xclosure_auto G (hd Xs)) pr)›
and shn: ‹fst pr ≠ Shn›
shows ‹∃τ. (None, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
(la_fix G Shn) (pstk ! 0))›
proof -
note mt = strackD(2)[OF tr]
have z_lt: ‹0 < length Xs› using ne by auto
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have i_lt: ‹pstk ! 0 < length (pr0_states G Shn)›
using didx_okD[OF mt z_lt] live unfolding hd0 by blast
from dlic_NilE[OF lic] obtain τ where
cellb: ‹(pstk ! 0, (pr, length (snd pr)), None, τ)
∈ set (red_buckets G Shn (length (pr0_states G Shn)) ! (pstk ! 0))› .
have cell: ‹(pstk ! 0, (pr, length (snd pr)), None, τ) ∈ set (la_fix G Shn)›
using red_buckets_memD[OF i_lt cellb] by blast
obtain j⇩r where jr: ‹j⇩r ∈ irep_set (red_set (xclosure_auto G (hd Xs)) pr)›
using nonvac unfolding irep_nonempty_correct by blast
from jr obtain R⇩r where
mem: ‹(pr, length (snd pr), R⇩r) ∈ set (xclosure_auto G (hd Xs))›
and jrR: ‹j⇩r ∈ irep_set R⇩r›
unfolding red_set_correct by blast
from strack_pool[OF tr live mem jrR] obtain ρ where
wr: ‹(pr, length (snd pr), ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))›
by blast
show ?thesis using ireds_at_memI[OF cell shn wr] by blast
qed
lemma shift_seed:
assumes tr: ‹strack G Shn Xs α pstk›
and ne: ‹Xs ≠ []›
and step: ‹mstep G (Xs, w) DShift = Some gc'›
and lv: ‹dlive gc'›
shows ‹∃a c w' c⇩s. w = (a, c) # w' ∧
(a, c⇩s) ∈ set (ishifts (wreach G (pr0_states G Shn ! (pstk ! 0)))) ∧
icur G (hd Xs) c c⇩s›
proof -
have step': ‹mstep_cached G (map (xclosure_auto G) Xs) (Xs, w) DShift = Some gc'›
using step unfolding mstep_def by simp
from shift_live_srcE[OF step' lv] obtain a c w' pr m R j where
w: ‹w = (a, c) # w'›
and src0: ‹(pr, m, R) ∈ set (hd (map (xclosure_auto G) Xs))›
and m_lt: ‹m < length (snd pr)›
and sym: ‹fst (snd pr ! m) = Tm a›
and jR: ‹j ∈ irep_set R›
and rel: ‹irel_sat (snd (snd pr ! m)) c j› .
have src: ‹(pr, m, R) ∈ set (xclosure_auto G (hd Xs))›
using src0 ne by (simp add: hd_map)
have live0: ‹lcore (hd Xs) ≠ {}› by (rule closure_live_kernel[OF src jR])
from strack_pool[OF tr live0 src jR] obtain ρ where
wr: ‹(pr, m, ρ) ∈ set (wreach G (pr0_states G Shn ! (pstk ! 0)))› by blast
have memS: ‹(a, (pr, m, w_of (snd (snd pr ! m)))) ∈
set (ishifts (wreach G (pr0_states G Shn ! (pstk ! 0))))›
by (rule ishifts_memI[OF wr m_lt sym])
have ‹icur G (hd Xs) c (pr, m, w_of (snd (snd pr ! m)))›
unfolding icur_def using src jR w_of_sound[OF rel] by auto
then show ?thesis using w memS by blast
qed
text ‹The sufficiency theorem: an empty report makes the pooled machine
deterministic. Cf.\ Barthwal \<^cite>‹‹Thm.~5.4.4› in "barthwal2010-thesis-cfl-hol4"› (conflict freedom on
reachable states suffices) and Jourdan et al. \<^cite>‹‹Sect.~3.3› in "jourdan2012-validating-lr1"› (the
completeness validator); the item-relative walk replaces their single-anchor comparison,
which the test grammar ‹xag› refutes for the pooled machine. The index
the driver consulted is the top of the tracked stack, so the check at that
one index covers both candidates.›
theorem rlalr_sufficient:
assumes chk: ‹rlalr_conflicts G Shn = []› and fresh: ‹fresh_name G Shn›
shows ‹mdet G Shn›
unfolding mdet_def
proof (intro allI impI)
fix gc istk i redtab CL a⇩1 a⇩2 gc⇩1 gc⇩2
assume reach: ‹imreach G Shn (pgtab G (pr0_states G Shn)) (pr0_states G Shn) (gc, istk)›
and idef: ‹i = hd istk›
and rdef: ‹redtab = red_buckets G Shn (length (pr0_states G Shn)) ! i›
and cldef: ‹CL = xclosure_auto G (hd (fst gc))›
and c1: ‹a⇩1 ∈ set (dcands G i redtab CL gc)›
and c2: ‹a⇩2 ∈ set (dcands G i redtab CL gc)›
and ne12: ‹a⇩1 ≠ a⇩2›
and s1: ‹mstep G gc a⇩1 = Some gc⇩1› and s2: ‹mstep G gc a⇩2 = Some gc⇩2›
and lv1: ‹dlive gc⇩1› and lv2: ‹dlive gc⇩2›
obtain Xs w where gc: ‹gc = (Xs, w)› by (cases gc)
have ne: ‹Xs ≠ []› and live0: ‹lcore (hd Xs) ≠ {}›
using imreach_dlive[OF reach] unfolding gc dlive_def by (simp_all add: live_lcore)
have clX: ‹CL = xclosure_auto G (hd Xs)› using cldef unfolding gc by simp
from imreach_strack[OF reach fresh] obtain α where
tr: ‹strack G Shn Xs α istk› unfolding gc by auto
note mt = strackD(2)[OF tr]
have z_lt: ‹0 < length Xs› using ne by auto
have hd0: ‹hd Xs = Xs ! 0› using ne by (simp add: hd_conv_nth)
have istk_ne: ‹istk ≠ []› using didx_ok_len[OF mt] ne by auto
have hdi: ‹hd istk = istk ! 0› using istk_ne by (simp add: hd_conv_nth)
have i_lt: ‹istk ! 0 < length (pr0_states G Shn)›
using didx_okD[OF mt z_lt] live0 unfolding hd0 by blast
have cs1: ‹a⇩1 = DShift ∧ w ≠ [] ∨ (∃pr. a⇩1 = DReduce pr ∧
irep_nonempty (red_set CL pr) ∧ dlic i redtab w pr (red_set CL pr))›
using dcands_shift_or_reduce c1 unfolding gc by blast
have cs2: ‹a⇩2 = DShift ∧ w ≠ [] ∨ (∃pr. a⇩2 = DReduce pr ∧
irep_nonempty (red_set CL pr) ∧ dlic i redtab w pr (red_set CL pr))›
using dcands_shift_or_reduce c2 unfolding gc by blast
have nc: ‹¬ rlalr_conflict_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
proof
assume ‹rlalr_conflict_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
then have ‹istk ! 0 ∈ set (rlalr_conflicts G Shn)›
unfolding rlalr_conflicts_def Let_def using i_lt by simp
then show False using chk by simp
qed
have no_none: ‹¬ rr_none_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
using nc unfolding rlalr_conflict_at_def by (auto simp: list_ex_iff)
have walkF: ‹⋀c⇩1 c⇩2. (c⇩1, c⇩2) ∈ set (ipairs_at G Shn (pr0_states G Shn)
(la_fix G Shn) (istk ! 0)) ⟹
ifire Shn (map (wreach G) (pr0_states G Shn)) (pgtab G (pr0_states G Shn))
(anchored_nts G) (ifuel (map (wreach G) (pr0_states G Shn)))
[] [(istk ! 0, c⇩1, c⇩2)] = False›
using nc unfolding rlalr_conflict_at_def
by (auto simp: list_ex_iff simp del: ifire.simps ifire_Cons)
have kill: False if ‹(c⇩1, c⇩2) ∈ set (ipairs_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0))›
‹icur G (hd Xs) c c⇩1› ‹icur G (hd Xs) c c⇩2› for c c⇩1 c⇩2
proof -
from strack_fires[OF tr fresh live0 that(2,3)] obtain t' where
‹(λt t'. t' ∈ set (isuccs Shn (map (wreach G) (pr0_states G Shn))
(pgtab G (pr0_states G Shn)) (anchored_nts G) t))⇧*⇧* (istk ! 0, c⇩1, c⇩2) t'›
and ‹ifires Shn (anchored_nts G) t'› by blast
with ifire_sound[OF walkF[OF that(1)]] show False by simp
qed
have sr_case: False if ss: ‹mstep G gc DShift = Some gc⇩s› ‹dlive gc⇩s›
and sr: ‹mstep G gc (DReduce pr) = Some gc⇩r› ‹dlive gc⇩r›
and lic: ‹dlic i redtab w pr (red_set CL pr)› for gc⇩s gc⇩r pr
proof -
from shift_seed[OF tr ne ss(1)[unfolded gc] ss(2)] obtain a c w' c⇩s where
w: ‹w = (a, c) # w'›
and shm: ‹(a, c⇩s) ∈ set (ishifts (wreach G (pr0_states G Shn ! (istk ! 0))))›
and ics: ‹icur G (hd Xs) c c⇩s› by blast
have ‹fst pr ≠ Shn› using shn_reduce_dead[OF tr fresh sr(1)[unfolded gc] _ sr(2)] by blast
moreover have ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
((a, c) # w') pr (red_set (xclosure_auto G (hd Xs)) pr)›
using lic unfolding idef rdef clX w hdi by simp
ultimately obtain τ where
rdm: ‹(Some a, (pr, length (snd pr), τ)) ∈ set (ireds_at G Shn (pr0_states G Shn)
(la_fix G Shn) (istk ! 0))›
and icr: ‹icur G (hd Xs) c (pr, length (snd pr), τ)›
using reduce_seed_Some[OF tr live0 ne] by blast
show False by (rule kill[OF ipairs_at_srI[OF rdm shm] icr ics])
qed
consider
(SS) ‹a⇩1 = DShift› and ‹a⇩2 = DShift›
| (SR) pr⇩2 where ‹a⇩1 = DShift› ‹a⇩2 = DReduce pr⇩2›
‹irep_nonempty (red_set CL pr⇩2)› ‹dlic i redtab w pr⇩2 (red_set CL pr⇩2)›
| (RS) pr⇩1 where ‹a⇩2 = DShift› ‹a⇩1 = DReduce pr⇩1›
‹irep_nonempty (red_set CL pr⇩1)› ‹dlic i redtab w pr⇩1 (red_set CL pr⇩1)›
| (RR) pr⇩1 pr⇩2 where ‹a⇩1 = DReduce pr⇩1› ‹a⇩2 = DReduce pr⇩2›
‹irep_nonempty (red_set CL pr⇩1)› ‹dlic i redtab w pr⇩1 (red_set CL pr⇩1)›
‹irep_nonempty (red_set CL pr⇩2)› ‹dlic i redtab w pr⇩2 (red_set CL pr⇩2)›
using cs1 cs2 by blast
then show False
proof cases
case SS
then show False using ne12 by simp
next
case (SR pr⇩2)
show False by (rule sr_case[OF s1[unfolded SR(1)] lv1 s2[unfolded SR(2)] lv2 SR(4)])
next
case (RS pr⇩1)
show False by (rule sr_case[OF s2[unfolded RS(1)] lv2 s1[unfolded RS(2)] lv1 RS(4)])
next
case (RR pr⇩1 pr⇩2)
let ?R = ‹ireds_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
have prne: ‹pr⇩2 ≠ pr⇩1› using ne12 unfolding RR(1) RR(2) by auto
have shn1: ‹fst pr⇩1 ≠ Shn› using shn_reduce_dead[OF tr fresh s1[unfolded gc RR(1)] _ lv1] by blast
have shn2: ‹fst pr⇩2 ≠ Shn› using shn_reduce_dead[OF tr fresh s2[unfolded gc RR(2)] _ lv2] by blast
have lic1: ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
w pr⇩1 (red_set (xclosure_auto G (hd Xs)) pr⇩1)›
and lic2: ‹dlic (istk ! 0) (red_buckets G Shn (length (pr0_states G Shn)) ! (istk ! 0))
w pr⇩2 (red_set (xclosure_auto G (hd Xs)) pr⇩2)›
using RR(4,6) unfolding idef rdef clX hdi by simp_all
show False
proof (cases w)
case Nil
from reduce_seed_None[OF tr live0 ne lic1[unfolded Nil] RR(3)[unfolded clX] shn1]
reduce_seed_None[OF tr live0 ne lic2[unfolded Nil] RR(5)[unfolded clX] shn2]
obtain τ⇩1 τ⇩2 where ‹(None, (pr⇩1, length (snd pr⇩1), τ⇩1)) ∈ set ?R›
‹(None, (pr⇩2, length (snd pr⇩2), τ⇩2)) ∈ set ?R› by blast
then have ‹rr_none_at G Shn (pr0_states G Shn) (la_fix G Shn) (istk ! 0)›
using prne by (rule rr_none_atI)
with no_none show False by simp
next
case (Cons ac w')
then obtain a c where w: ‹w = (a, c) # w'› by (cases ac) simp
from reduce_seed_Some[OF tr live0 ne lic1[unfolded w] shn1] obtain τ⇩1 where
m1: ‹(Some a, (pr⇩1, length (snd pr⇩1), τ⇩1)) ∈ set ?R›
and ic1: ‹icur G (hd Xs) c (pr⇩1, length (snd pr⇩1), τ⇩1)› by blast
from reduce_seed_Some[OF tr live0 ne lic2[unfolded w] shn2] obtain τ⇩2 where
m2: ‹(Some a, (pr⇩2, length (snd pr⇩2), τ⇩2)) ∈ set ?R›
and ic2: ‹icur G (hd Xs) c (pr⇩2, length (snd pr⇩2), τ⇩2)› by blast
show False by (rule kill[OF ipairs_at_rrI[OF m1 m2 prne] ic1 ic2])
qed
qed
qed
section ‹Executable packaging: the automaton computed once›
text ‹The checks above are written for reading: each one names the
automaton, the goto tables and the saturated cell table it needs, and the
evaluator recomputes every one of them at every occurrence. At the size of
a real grammar that dominates the cost of the \<^text>‹parser›
command, so this section restates them against precomputed arguments, in
the manner of \<^const>‹la_fix_gen›, and proves the restatements
equal to the originals. Nothing changes meaning: the ‹_gen›
forms are definitions and every bridge below is a theorem.
\<^const>‹rlalr_conflict_at› is the worst offender - it names
\<^const>‹pgtab›, \<^const>‹anchored_nts›, the states' \<^const>‹wreach›
lists and \<^const>‹ifuel› under the \<^const>‹list_ex›, so they are
rebuilt once per candidate pair of every state. The restatement reads the
state's closure from the shared list, so it agrees with the original on the
states of the automaton only, which is all \<^const>‹rlalr_conflicts›
asks about.›
definition ireds_gen :: ‹'n ⇒ ('n, 't) witem list ⇒ ('n, 't) lacell list ⇒ nat ⇒
('t option × ('n, 't) witem) list› where
‹ireds_gen Shn ws L i =
List.map_filter (λ(i', (pr, m), t, τ).
if i' = i ∧ m = length (snd pr) ∧ fst pr ≠ Shn ∧
list_ex (λ(pr', m', ρ). pr' = pr ∧ m' = m) ws
then Some (t, (pr, m, τ)) else None) L›
lemma ireds_at_gen:
‹ireds_at G Shn sp L i = ireds_gen Shn (wreach G (sp ! i)) L i›
by (simp add: ireds_at_def ireds_gen_def Let_def)
definition rr_none_gen :: ‹('t option × ('n, 't) witem) list ⇒ bool› where
‹rr_none_gen reds =
list_ex (λ(t, c). t = None ∧
list_ex (λ(t', c'). fst c' ≠ fst c ∧ t' = None) reds) reds›
lemma rr_none_at_gen:
‹rr_none_at G Shn sp L i = rr_none_gen (ireds_at G Shn sp L i)›
by (simp add: rr_none_at_def rr_none_gen_def Let_def)
definition ipairs_gen :: ‹('n, 't) witem list ⇒ ('t option × ('n, 't) witem) list ⇒
(('n, 't) witem × ('n, 't) witem) list› where
‹ipairs_gen ws reds =
(let shifts = ishifts ws;
srs = concat (map (λ(t, c). case t of
Some a ⇒ map (λ(a', c'). (c, c')) (filter (λ(a', c'). a' = a) shifts)
| None ⇒ []) reds);
rrs = concat (map (λ(t, c). List.map_filter (λ(t', c').
if fst c' ≠ fst c ∧ t' = t ∧ t ≠ None then Some (c, c') else None) reds)
reds)
in remdups (srs @ rrs))›
lemma ipairs_at_gen:
‹ipairs_at G Shn sp L i = ipairs_gen (wreach G (sp ! i)) (ireds_at G Shn sp L i)›
by (simp add: ipairs_at_def ipairs_gen_def Let_def)
definition rlalr_conflict_at_gen :: ‹'n ⇒ ('n, 't) witem list list ⇒
(('n, 't) sym × nat) list list ⇒ 'n list ⇒ nat ⇒ ('n, 't) lacell list ⇒
nat ⇒ bool› where
‹rlalr_conflict_at_gen Shn wrs gp ants fuel L i ⟷
(let ws = wrs ! i; reds = ireds_gen Shn ws L i
in rr_none_gen reds ∨
list_ex (λ(c⇩1, c⇩2). ifire Shn wrs gp ants fuel [] [(i, c⇩1, c⇩2)])
(ipairs_gen ws reds))›
lemma rlalr_conflict_at_pointwise:
assumes ‹i < length sp›
shows ‹rlalr_conflict_at G Shn sp L i =
rlalr_conflict_at_gen Shn (map (wreach G) sp) (pgtab G sp) (anchored_nts G)
(ifuel (map (wreach G) sp)) L i›
using assms by (simp add: rlalr_conflict_at_def rlalr_conflict_at_gen_def Let_def
ireds_at_gen rr_none_at_gen ipairs_at_gen)
lemma rlalr_conflicts_code [code]:
‹rlalr_conflicts G Shn =
(let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
wrs = map (wreach G) sp
in filter (rlalr_conflict_at_gen Shn wrs gp (anchored_nts G) (ifuel wrs) L)
[0..<length sp])›
unfolding rlalr_conflicts_def la_fix_def Let_def
by (rule filter_cong[OF refl]) (simp add: rlalr_conflict_at_pointwise)
lemma acc_conflicts_code [code]:
‹acc_conflicts G Shn =
(let sts = pr0_states G Shn; L = la_fix_gen G Shn (pgtab G sts) sts;
p0 = start_prod G Shn
in filter (λi. (p0, Suc 0) ∈ set (sts ! i) ∧
list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
t = None ∧ pr ≠ p0) L)
[0..<length sts])›
by (simp add: acc_conflicts_def la_fix_def Let_def)
text ‹The bundle the \<^text>‹parser› command evaluates: the six
tables its parse body is specialised to, followed by the two conflict
reports it discharges \<^text>‹mdet› and the accept/reduce premise
with. Sharing across the eight components is the point - the automaton,
its goto table and the saturated cell table are each built once for all
of them.›
definition lr_tables :: ‹('n, 't) is_cfg ⇒ 'n ⇒
('n, 't) citem list list × (('n, 't) sym × nat) list list ×
('n, 't) lacell list list × ('n, 't) xitem list × ('n, 't) xitem list ×
nat × nat list × nat list› where
‹lr_tables G Shn =
(let sp = pr0_states G Shn; gp = pgtab G sp; L = la_fix_gen G Shn gp sp;
ants = anchored_nts G; wrs = map (wreach G) sp; fuel = ifuel wrs;
s0 = start_prod G Shn; xi = xinit G Shn
in (sp, gp, cell_buckets L (length sp), xi, xclosure_auto G xi,
st_find sp (lr0_start G Shn),
filter (rlalr_conflict_at_gen Shn wrs gp ants fuel L) [0..<length sp],
filter (λi. (s0, Suc 0) ∈ set (sp ! i) ∧
list_ex (λ(i', (pr, m), t, τ). i' = i ∧ m = length (snd pr) ∧
t = None ∧ pr ≠ s0) L)
[0..<length sp]))›
theorem lr_tables_eq:
‹lr_tables G Shn =
(pr0_states G Shn,
pgtab G (pr0_states G Shn),
red_buckets G Shn (length (pr0_states G Shn)),
xinit G Shn,
xclosure_auto G (xinit G Shn),
st_find (pr0_states G Shn) (lr0_start G Shn),
rlalr_conflicts G Shn,
acc_conflicts G Shn)›
by (simp add: lr_tables_def red_buckets_def la_fix_def rlalr_conflicts_code
acc_conflicts_code Let_def)
end