Theory LR
theory LR
imports TIGER_Grammar_Model.Indentation_Sensitive "HOL-Library.While_Combinator" "HOL-Library.RBT"
"HOL-Library.IArray"
begin
section ‹Fuel-free GLR steps›
text ‹
The table layer: the LR(0) automaton over the cores of the ‹k = 0›
frames, the column-relative first table, and per-item LALR(1) lookahead
cells relating the token's column to the item's anchor. The cells stand
in for the lookahead tuples of \<^cite>‹‹Sect.~5.6› in "adams2013"›: the parser of
\<^text>‹LR_Driver› is LALR(1)-style, not the canonical LR(1) instance of
\<^cite>‹‹Alg.~8› in "adams2013"›; \<^text>‹LR_Det› shows that the cells cover its lookahead.
The GLR machine of \<^text>‹Indentation_Sensitive› section 5 is a
checker whose steps carry explicit closure fuel. This section removes the
fuel by searching for the least sufficient one, which exists by
\<^text>‹xcls_stable_ex›.
›
subsection ‹The least satisfying number, executably›
text ‹The least ‹n› with ‹P n›, by \<^const>‹while_option›; defined
whenever a witness exists. Every fuelled fixpoint of this theory uses it.›
definition nat_search :: ‹(nat ⇒ bool) ⇒ nat› where
‹nat_search P = the (while_option (λn. ¬ P n) Suc 0)›
lemma nat_search_Some:
assumes ‹P k›
shows ‹while_option (λn. ¬ P n) Suc 0 = Some (nat_search P)›
proof -
have ‹n ≤ k ⟹ ¬ P n ⟹ Suc n ≤ k ∧ k - Suc n < k - n› for n
using assms by (cases ‹n = k›) auto
then obtain t where t: ‹while_option (λn. ¬ P n) Suc 0 = Some t›
using measure_while_option_Some[of ‹λn. n ≤ k› ‹λn. ¬ P n› Suc ‹λn. k - n› 0]
by auto
then show ?thesis
by (simp add: nat_search_def)
qed
lemma nat_search_sat:
assumes ‹P k›
shows ‹P (nat_search P)›
using while_option_stop[OF nat_search_Some[of P, OF assms]] by simp
subsection ‹Fuel-free closure›
definition xfuel :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ nat› where
‹xfuel G xs = nat_search (λt. xstable G xs (xiter G xs t))›
definition xclosure_auto :: ‹('n, 't) is_cfg ⇒ ('n, 't) xitem list ⇒ ('n, 't) xitem list› where
‹xclosure_auto G xs = xclosure G (xfuel G xs) xs›
lemma xfuel_stable: ‹xstable G xs (xiter G xs (xfuel G xs))›
proof -
obtain fuel where ‹xstable G xs (xiter G xs fuel)›
using xcls_stable_ex by blast
from nat_search_sat[of ‹λt. xstable G xs (xiter G xs t)›, OF this]
show ?thesis by (simp add: xfuel_def)
qed
text ‹Executably, the rounds are iterated once, each computed once: the search
for the fuel would recompute them from scratch for every candidate.›
lemma xclosure_auto_code [code]:
‹xclosure_auto G xs = xslots G xs (fst (the (while_option
(λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
(xiter G xs 0, xround G xs (xiter G xs 0)))))›
proof -
obtain k where ‹xstable G xs (xiter G xs k)›
using xcls_stable_ex by blast
then have ‹while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0 = Some (xfuel G xs)›
unfolding xfuel_def by (rule nat_search_Some)
moreover have
‹map_option (λt. (xiter G xs t, xiter G xs (Suc t)))
(while_option (λt. ¬ xstable G xs (xiter G xs t)) Suc 0) =
while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
(xiter G xs 0, xiter G xs (Suc 0))›
by (rule while_option_commute
[where f = ‹λt. (xiter G xs t, xiter G xs (Suc t))› and s = 0])
(simp_all add: xstable_def)
ultimately have
‹Some (xiter G xs (xfuel G xs), xiter G xs (Suc (xfuel G xs))) =
while_option (λ(cls, nxt). ¬ list_all2 irep_subset nxt cls) (λ(cls, nxt). (nxt, xround G xs nxt))
(xiter G xs 0, xround G xs (xiter G xs 0))›
by simp
from this[symmetric] show ?thesis
by (simp add: xclosure_auto_def xclosure_def)
qed
subsection ‹Acceptance›
text ‹Acceptance condition on a configuration: the post-\<^const>‹grun›
condition of \<^const>‹gaccepts›; the driver of \<^text>‹LR_Driver›
uses it.›
definition gfinal :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) gconfig ⇒ bool› where
‹gfinal G Shn gc ⟷ (case gc of (Ys, v) ⇒ v = [] ∧ Ys ≠ [] ∧
list_ex (λ(pr, m, R). fst pr = Shn ∧ m = Suc 0 ∧
irep_mem (istart_ind G) R) (hd Ys))›
section ‹LR(0) core tabulation›
text ‹
The indentation sets of items are input-dependent; their
∗‹cores› (production and dot) are not: \<^const>‹xgoto› advances dots
regardless of the goto label, and \<^const>‹xclosure› adds one
dot-\<^text>‹0› slot per production unconditionally. So the finitely many
reachable cores can be tabulated at grammar-declaration time, giving the
state skeleton for LR(k) tables and conflict reporting; the runtime
indentation sets refine it per input.
›
text ‹After Knuth \<^cite>‹‹Sect.~II, Steps~1 and~3› in "knuth1965-lr-translation"› (the state sets), DeRemer and
Pennello \<^cite>‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"› (the LR(0) automaton ‹(K, Next, Reduce)›) and
Barthwal \<^cite>‹‹Sect.~5.5.1, Def.~5.5.4› in "barthwal2010-thesis-cfl-hol4"› (the worklist ‹visit›, with the
unseen part of the finite universe as measure).›
subsection ‹Cores of frames›
type_synonym ('n, 't) citem = ‹('n × ('n, 't) rhs) × nat›
definition ccore :: ‹('n, 't) xitem list ⇒ ('n, 't) citem list› where
‹ccore xs = remdups (map (λ(pr, m, R). (pr, m)) xs)›
definition cgoto :: ‹('n, 't) citem list ⇒ ('n, 't) sym ⇒ ('n, 't) citem list› where
‹cgoto cs X = remdups (map (λ(pr, m). (pr, Suc m))
(filter (λ(pr, m). m < length (snd pr) ∧ fst (snd pr ! m) = X) cs))›
definition cclosure :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
‹cclosure G cs = remdups (cs @ map (λpr. (pr, 0)) (iprods G))›
subsection ‹The finite universe of cores›
definition start_prod :: ‹('n, 't) is_cfg ⇒ 'n ⇒ 'n × ('n, 't) rhs› where
‹start_prod G Shn = (Shn, [(Nt (istart G), Eq)])›
definition cuniv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem set› where
‹cuniv G Shn = (SIGMA pr : insert (start_prod G Shn) (set (iprods G)).
{..length (snd pr)})›
lemma finite_cuniv: ‹finite (cuniv G Shn)›
unfolding cuniv_def by (intro finite_SigmaI) auto
lemma cgoto_cclosure_univ:
assumes ‹set s ⊆ cuniv G Shn›
shows ‹set (cgoto (cclosure G s) X) ⊆ cuniv G Shn›
proof
fix c assume ‹c ∈ set (cgoto (cclosure G s) X)›
then obtain pr m where c: ‹c = (pr, Suc m)› and m: ‹m < length (snd pr)›
and mem: ‹(pr, m) ∈ set s ∪ (λpr. (pr, 0)) ` set (iprods G)›
unfolding cgoto_def cclosure_def by auto
have ‹pr ∈ insert (start_prod G Shn) (set (iprods G))›
using mem assms unfolding cuniv_def by auto
then show ‹c ∈ cuniv G Shn›
using m unfolding c cuniv_def by auto
qed
definition gram_syms :: ‹('n, 't) is_cfg ⇒ ('n, 't) syms› where
‹gram_syms G =
remdups (Nt (istart G) # concat (map (λ(A, rhs). map fst rhs) (iprods G)))›
subsection ‹Worklist subset construction›
text ‹States are core lists, compared up to their sets; \<^text>‹cinserts› adds
the successors not yet seen.›
fun cinserts :: ‹('n, 't) citem list list ⇒ ('n, 't) citem list list ⇒
('n, 't) citem list list ⇒ ('n, 't) citem list list› where
‹cinserts seen [] acc = acc›
| ‹cinserts seen (t # ts) acc =
(if list_ex (λu. set u = set t) (seen @ acc)
then cinserts seen ts acc
else cinserts seen ts (t # acc))›
lemma cinserts_superset: ‹set acc ⊆ set (cinserts seen ts acc)›
by (induction seen ts acc rule: cinserts.induct) auto
lemma cinserts_elems:
‹set (cinserts seen ts acc) ⊆ set ts ∪ set acc›
by (induction seen ts acc rule: cinserts.induct) auto
lemma cinserts_covers:
‹t ∈ set ts ⟹ ∃u ∈ set (seen @ cinserts seen ts acc). set u = set t›
proof (induction seen ts acc rule: cinserts.induct)
case (2 seen t' ts acc)
show ?case
proof (cases ‹t = t'›)
case True
show ?thesis
proof (cases ‹list_ex (λu. set u = set t') (seen @ acc)›)
case True
then obtain u where u: ‹u ∈ set (seen @ acc)› and ‹set u = set t'›
by (auto simp: list_ex_iff)
then have ‹u ∈ set (seen @ cinserts seen ts acc)›
using cinserts_superset by fastforce
then show ?thesis using ‹set u = set t'› ‹t = t'› True by auto
next
case False
have ‹t' ∈ set (cinserts seen ts (t' # acc))›
using cinserts_superset by fastforce
then show ?thesis using False ‹t = t'› by auto
qed
next
case False
with "2.prems" have t: ‹t ∈ set ts› by simp
show ?thesis
proof (cases ‹list_ex (λu. set u = set t') (seen @ acc)›)
case True
from "2.IH"(1)[OF True t] show ?thesis using True by simp
next
case False
from "2.IH"(2)[OF False t] show ?thesis using False by simp
qed
qed
qed simp
lemma cinserts_distinct:
‹distinct (map set (seen @ acc)) ⟹
distinct (map set (seen @ cinserts seen ts acc))›
proof (induction seen ts acc rule: cinserts.induct)
case (2 seen t ts acc)
show ?case
proof (cases ‹list_ex (λu. set u = set t) (seen @ acc)›)
case True
then show ?thesis using "2.IH"(1) "2.prems" by simp
next
case False
have ‹distinct (map set (seen @ t # acc))›
using "2.prems" False by (auto simp: list_ex_iff image_iff)
then show ?thesis using "2.IH"(2) False by simp
qed
qed simp
subsection ‹The worklist subset construction, generic in the closure›
text ‹The subset construction as a worklist over states (lists of cores),
parametrised by the closure ‹cl› taken before each goto:
\<^const>‹cclosure› for the LR(0) automaton \<^text>‹lr0_states›,
\<^text>‹creach› for the precise automaton \<^text>‹pr0_states› of
\<^text>‹LR_Det›. The invariant and the termination measure only need
that a goto through the closure stays inside \<^const>‹cuniv›. The
\<^const>‹while_option› scaffold is shared with the cell saturation below.›
lemma while_option_the_inv:
fixes f :: ‹'s ⇒ nat›
assumes init: ‹P s⇩0›
and step: ‹⋀s. P s ⟹ b s ⟹ P (c s) ∧ f (c s) < f s›
shows ‹P (the (while_option b c s⇩0)) ∧ ¬ b (the (while_option b c s⇩0))›
proof -
obtain t where t: ‹while_option b c s⇩0 = Some t›
using measure_while_option_Some[where P = P and b = b and c = c and s = s⇩0 and f = f]
init step by blast
have ‹P t›
by (rule while_option_rule[where P = P, OF _ t init]) (use step in blast)
with while_option_stop[OF t] show ?thesis by (simp add: t)
qed
definition wl_step :: ‹('n, 't) is_cfg ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
('n, 't) citem list list × ('n, 't) citem list list ⇒
('n, 't) citem list list × ('n, 't) citem list list› where
‹wl_step G cl = (λ(visited, work). case work of
[] ⇒ (visited, [])
| s # ws ⇒ (s # visited,
cinserts (s # visited) (map (cgoto (cl s)) (gram_syms G)) ws))›
definition wl_inv :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
('n, 't) citem set set ⇒
('n, 't) citem list list × ('n, 't) citem list list ⇒ bool› where
‹wl_inv G Shn cl S⇩0 = (λ(visited, work).
distinct (map set (visited @ work)) ∧
(∀s ∈ set (visited @ work). set s ⊆ cuniv G Shn) ∧
S⇩0 ⊆ set ` set (visited @ work) ∧
(∀s ∈ set visited. ∀X ∈ set (gram_syms G).
∃t ∈ set (visited @ work). set t = set (cgoto (cl s) X)))›
lemma wl_step_inv:
assumes univ: ‹⋀s X. set s ⊆ cuniv G Shn ⟹ set (cgoto (cl s) X) ⊆ cuniv G Shn›
and inv: ‹wl_inv G Shn cl S⇩0 (visited, work)› and ne: ‹work ≠ []›
shows ‹wl_inv G Shn cl S⇩0 (wl_step G cl (visited, work))›
proof -
obtain s ws where work: ‹work = s # ws› using ne by (cases work) auto
define succs where ‹succs = map (cgoto (cl s)) (gram_syms G)›
define nw where ‹nw = cinserts (s # visited) succs ws›
have res: ‹wl_step G cl (visited, work) = (s # visited, nw)›
unfolding wl_step_def work succs_def nw_def by simp
have dst: ‹distinct (map set (visited @ work))›
and unv: ‹∀u ∈ set (visited @ work). set u ⊆ cuniv G Shn›
and s⇩0: ‹S⇩0 ⊆ set ` set (visited @ work)›
and cov: ‹∀u ∈ set visited. ∀X ∈ set (gram_syms G).
∃t ∈ set (visited @ work). set t = set (cgoto (cl u) X)›
using inv unfolding wl_inv_def by auto
have dst': ‹distinct (map set ((s # visited) @ nw))›
unfolding nw_def
by (rule cinserts_distinct) (use dst work in auto)
have sub: ‹set (visited @ work) ⊆ set ((s # visited) @ nw)›
using cinserts_superset[of ws ‹s # visited› succs]
unfolding nw_def work by auto
have unv': ‹∀u ∈ set ((s # visited) @ nw). set u ⊆ cuniv G Shn›
proof
fix u assume ‹u ∈ set ((s # visited) @ nw)›
then consider ‹u ∈ set (visited @ work)› | ‹u ∈ set succs›
using cinserts_elems[of ‹s # visited› succs ws] work
unfolding nw_def by auto
then show ‹set u ⊆ cuniv G Shn›
proof cases
case 1 then show ?thesis using unv by blast
next
case 2
then obtain X where ‹u = cgoto (cl s) X›
unfolding succs_def by auto
then show ?thesis
using univ unv work by fastforce
qed
qed
have s⇩0': ‹S⇩0 ⊆ set ` set ((s # visited) @ nw)›
by (rule subset_trans[OF s⇩0 image_mono[OF sub]])
have cov': ‹∀u ∈ set (s # visited). ∀X ∈ set (gram_syms G).
∃t ∈ set ((s # visited) @ nw). set t = set (cgoto (cl u) X)›
proof (intro ballI)
fix u X assume u: ‹u ∈ set (s # visited)› and X: ‹X ∈ set (gram_syms G)›
show ‹∃t ∈ set ((s # visited) @ nw). set t = set (cgoto (cl u) X)›
proof (cases ‹u = s›)
case True
have ‹cgoto (cl s) X ∈ set succs›
using X unfolding succs_def by auto
from cinserts_covers[OF this, of ‹s # visited› ws]
show ?thesis unfolding nw_def True by auto
next
case False
with u have ‹u ∈ set visited› by simp
from cov[rule_format, OF this X] obtain t where
‹t ∈ set (visited @ work)› and ‹set t = set (cgoto (cl u) X)›
by blast
then show ?thesis using sub by blast
qed
qed
show ?thesis unfolding res wl_inv_def
using dst' unv' s⇩0' cov' by simp
qed
lemma wl_step_card:
assumes inv: ‹wl_inv G Shn cl S⇩0 (visited, work)› and ne: ‹work ≠ []›
shows ‹card (set ` set (fst (wl_step G cl (visited, work))))
= Suc (card (set ` set visited))›
proof -
obtain s ws where work: ‹work = s # ws› using ne by (cases work) auto
have ‹set s ∉ set ` set visited›
using inv unfolding wl_inv_def work by (auto simp: image_iff)
moreover have ‹finite (set ` set visited)› by simp
ultimately show ?thesis
unfolding wl_step_def work by (simp add: Let_def)
qed
definition lr0_start :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list› where
‹lr0_start G Shn = [(start_prod G Shn, 0)]›
definition lr0_init :: ‹('n, 't) is_cfg ⇒ 'n ⇒
('n, 't) citem list list × ('n, 't) citem list list› where
‹lr0_init G Shn = ([], [lr0_start G Shn, []])›
lemma wl_inv_init:
‹wl_inv G Shn cl {set (lr0_start G Shn), {}} (lr0_init G Shn)›
unfolding wl_inv_def lr0_init_def lr0_start_def cuniv_def start_prod_def
by auto
definition wl_states :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) citem list ⇒ ('n, 't) citem list) ⇒
('n, 't) citem list list› where
‹wl_states G Shn cl =
fst (the (while_option (λ(v, w). w ≠ []) (wl_step G cl) (lr0_init G Shn)))›
lemma wl_states_inv:
assumes univ: ‹⋀s X. set s ⊆ cuniv G Shn ⟹ set (cgoto (cl s) X) ⊆ cuniv G Shn›
shows ‹wl_inv G Shn cl {set (lr0_start G Shn), {}} (wl_states G Shn cl, [])›
proof -
let ?P = ‹wl_inv G Shn cl {set (lr0_start G Shn), {}}›
let ?t = ‹the (while_option (λ(v, w). w ≠ []) (wl_step G cl) (lr0_init G Shn))›
have ‹?P ?t ∧ ¬ (case ?t of (v, w) ⇒ w ≠ [])›
proof (rule while_option_the_inv[where P = ?P and b = ‹λ(v, w). w ≠ []›
and c = ‹wl_step G cl› and f = ‹λ(v, w). card (Pow (cuniv G Shn)) - card (set ` set v)›])
show ‹?P (lr0_init G Shn)› by (rule wl_inv_init)
next
fix st assume inv: ‹?P st› and b: ‹case st of (v, w) ⇒ w ≠ []›
obtain v w where st: ‹st = (v, w)› by (cases st)
have card_lt: ‹card (set ` set v) < card (Pow (cuniv G Shn))›
proof -
have ‹set ` set (fst (wl_step G cl (v, w))) ⊆ Pow (cuniv G Shn)›
using wl_step_inv[OF univ inv[unfolded st] b[unfolded st, simplified]]
unfolding wl_inv_def by (cases ‹wl_step G cl (v, w)›) auto
then have ‹card (set ` set (fst (wl_step G cl (v, w)))) ≤ card (Pow (cuniv G Shn))›
by (intro card_mono) (simp add: finite_cuniv)
then show ?thesis
using wl_step_card[OF inv[unfolded st] b[unfolded st, simplified]] by simp
qed
show ‹?P (wl_step G cl st) ∧
(case wl_step G cl st of (v, w) ⇒ card (Pow (cuniv G Shn)) - card (set ` set v))
< (case st of (v, w) ⇒ card (Pow (cuniv G Shn)) - card (set ` set v))›
using wl_step_inv[OF univ inv[unfolded st]] wl_step_card[OF inv[unfolded st]] b card_lt
unfolding st by (cases ‹wl_step G cl (v, w)›) auto
qed
then show ?thesis unfolding wl_states_def by (cases ?t) auto
qed
subsection ‹The LR(0) automaton›
definition lr0_states :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n, 't) citem list list› where
‹lr0_states G Shn = wl_states G Shn (cclosure G)›
lemma ccore_xinit: ‹set (ccore (xinit G Shn)) = set (lr0_start G Shn)›
unfolding ccore_def xinit_def lr0_start_def start_prod_def by simp
subsection ‹Reachable closure and conflict reporting›
text ‹\<^const>‹cclosure› adds a dot-\<^text>‹0› slot for every production
(dead slots carry empty \<^typ>‹indrep›s at runtime), so at core level an
\<^text>‹ε›-production looks completed in every state. Conflict diagnostics
need the classic ∗‹reachable› closure: only productions of nonterminals
that occur after a dot. One production can be added per round, so
\<^term>‹length (iprods G)› rounds saturate.
This is the ‹Closure› of DeRemer and Pennello
\<^cite>‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"› and the closure of Knuth's Step~1
\<^cite>‹‹Sect.~II, Eq.~(18)› in "knuth1965-lr-translation"› without its lookahead strings.›
definition creach_step :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
‹creach_step G cs = remdups (cs @ concat (map (λpr.
if list_ex (λ(pr', m). m < length (snd pr') ∧ fst (snd pr' ! m) = Nt (fst pr)) cs
then [(pr, 0)] else []) (iprods G)))›
definition creach :: ‹('n, 't) is_cfg ⇒ ('n, 't) citem list ⇒ ('n, 't) citem list› where
‹creach G cs = (creach_step G ^^ Suc (length (iprods G))) cs›
text ‹Evaluated as defined, \<^const>‹creach› takes all the rounds its fuel allows, one
per production, for every state; the code equation stops at the first round that
changes nothing.›
fun fuel_fix :: ‹('a ⇒ 'a) ⇒ nat ⇒ 'a ⇒ 'a› where
‹fuel_fix f n x = (if n = 0 then x else let y = f x in if y = x then x else fuel_fix f (n - 1) y)›
declare fuel_fix.simps [simp del]
lemma fuel_fix_funpow: ‹fuel_fix f n x = (f ^^ n) x›
proof (induction f n x rule: fuel_fix.induct)
case (1 f n x)
show ?case
proof (cases n)
case 0
then show ?thesis by (simp add: fuel_fix.simps)
next
case (Suc m)
show ?thesis
proof (cases ‹f x = x›)
case True
then have ‹(f ^^ k) x = x› for k by (induction k) simp_all
with True Suc show ?thesis by (simp add: fuel_fix.simps)
next
case False
have ‹fuel_fix f n x = fuel_fix f m (f x)›
using Suc False by (subst fuel_fix.simps) simp
also have ‹… = (f ^^ m) (f x)›
using 1 Suc False by simp
also have ‹… = (f ^^ n) x›
using Suc by (simp add: funpow_swap1)
finally show ?thesis .
qed
qed
qed
lemma creach_code [code]:
‹creach G cs = fuel_fix (creach_step G) (Suc (length (iprods G))) cs›
unfolding creach_def fuel_fix_funpow ..
lemma creach_step_mono: ‹set cs ⊆ set (creach_step G cs)›
unfolding creach_step_def by auto
lemma creach_funpow_mono: ‹set cs ⊆ set ((creach_step G ^^ k) cs)›
proof (induction k arbitrary: cs)
case (Suc k)
have ‹set cs ⊆ set (creach_step G cs)› by (rule creach_step_mono)
also have ‹… ⊆ set ((creach_step G ^^ k) (creach_step G cs))› by (rule Suc.IH)
finally show ?case by (simp add: funpow_swap1)
qed simp
lemma creach_superset: ‹set cs ⊆ set (creach G cs)›
unfolding creach_def by (rule creach_funpow_mono)
lemma creach_step_sound:
‹set (creach_step G cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
unfolding creach_step_def by (auto split: if_splits)
lemma creach_funpow_sound:
‹set ((creach_step G ^^ k) cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
proof (induction k arbitrary: cs)
case (Suc k)
have ‹set ((creach_step G ^^ Suc k) cs)
= set ((creach_step G ^^ k) (creach_step G cs))›
by (simp add: funpow_swap1)
also have ‹… ⊆ set (creach_step G cs) ∪ (λpr. (pr, 0)) ` set (iprods G)›
by (rule Suc.IH)
also have ‹… ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
using creach_step_sound by fastforce
finally show ?case .
qed simp
lemma creach_sound:
‹set (creach G cs) ⊆ set (cclosure G cs)›
proof -
have ‹set (creach G cs) ⊆ set cs ∪ (λpr. (pr, 0)) ` set (iprods G)›
unfolding creach_def by (rule creach_funpow_sound)
also have ‹… = set (cclosure G cs)›
unfolding cclosure_def by auto
finally show ?thesis .
qed
subsection ‹Cores stay in the universe›
text ‹Goto and closure keep cores inside \<^const>‹cuniv›, and all next symbols of
cores in \<^const>‹cuniv› are in \<^const>‹gram_syms›.›
lemma cgoto_memI:
‹(pr, m) ∈ set cs ⟹ m < length (snd pr) ⟹ fst (snd pr ! m) = X ⟹ (pr, Suc m) ∈ set (cgoto cs X)›
unfolding cgoto_def by force
lemma cgoto_set_mono: ‹set cs ⊆ set cs' ⟹ set (cgoto cs X) ⊆ set (cgoto cs' X)›
unfolding cgoto_def by auto
lemma cclosure_univ:
‹set cs ⊆ cuniv G Shn ⟹ set (cclosure G cs) ⊆ cuniv G Shn›
unfolding cclosure_def cuniv_def by auto
lemma creach_univ:
assumes ‹set s ⊆ cuniv G Shn›
shows ‹set (creach G s) ⊆ cuniv G Shn›
using creach_sound[of G s] cclosure_univ[OF assms] by blast
lemma gram_syms_iprods:
‹(A, rhs) ∈ set (iprods G) ⟹ m < length rhs ⟹ fst (rhs ! m) ∈ set (gram_syms G)›
unfolding gram_syms_def by force
lemma cuniv_next_gram_syms:
assumes ‹(pr, m) ∈ cuniv G Shn› and ‹m < length (snd pr)›
shows ‹fst (snd pr ! m) ∈ set (gram_syms G)›
proof -
from assms(1) consider ‹pr = start_prod G Shn› | ‹pr ∈ set (iprods G)›
unfolding cuniv_def by auto
then show ?thesis
proof cases
case 1
then show ?thesis using assms(2) unfolding start_prod_def gram_syms_def by simp
next
case 2
then show ?thesis using gram_syms_iprods[of ‹fst pr› ‹snd pr› G m] assms(2) by simp
qed
qed
section ‹Column-relative first sets: LR(k) lookahead, phase 1›
text ‹
Deterministic LR parsing of an II-CFG needs ∗‹column-relative›
lookahead: a spine ends where the next token's column says so, not where
its class does. A lookahead entry is a token class paired with a
\<^typ>‹cirel› relating the token's column to the indentation of the item
that carries it. The executable first-set layer:
▪ \<^text>‹cwiden›: composed relations widened into a four-element class
universe, keeping the fixpoints finite. Over-approximating is the safe
direction throughout: lookahead only prunes reduce actions;
▪ \<^text>‹nullables›: executable nullability, complete against the
derivations of the infinite grammar \<^const>‹infG›;
▪ \<^text>‹ffix›: the first-token table, one saturation fixpoint,
complete against the derivations of \<^const>‹infG›: every first token
an annotated right-hand side derives is found, with a relation its
column satisfies (‹fscan_complete› below).
A nonterminal ‹A› is nullable in \<^cite>‹‹Def.~1› in "adams2013"› if
‹A⇩i ⇒⇧* ε› for all ‹i›; ‹nullables_complete› asks for a derivation at
one indentation only. The first table is Knuth's ‹H⇩k›
\<^cite>‹‹Sect.~II› in "knuth1965-lr-translation"› at ‹k = 1›, with a column
relation on each token. As in Jourdan et al.
\<^cite>‹‹Sect.~3.3› in "jourdan2012-validating-lr1"›, first and nullable are least
fixpoints of the standard equations; here they are computed, not checked as part of a
certificate.
›
subsection ‹Widening composed relations›
text ‹By \<^cite>‹‹Lemma~2› in "adams2013"› a composition of relations is one of six
classes, but ‹>⇧n› and ‹>⇧n⋆› carry a number, so there are
infinitely many. ‹cwiden› keeps four: ‹>⇧n› becomes
‹>⇧1› (or ‹≥› when ‹n = 0›) and ‹>⇧n⋆› becomes
‹⋆›. Lemma~2 is exact; the widening only weakens
(‹csat_cwiden›).›
fun cwiden :: ‹cirel ⇒ cirel› where
‹cwiden (CGt n) = (if n = 0 then CGe else CGt 1)›
| ‹cwiden (CGtAny n) = CAny›
| ‹cwiden c = c›
lemma csat_cwiden: ‹csat c k i ⟹ csat (cwiden c) k i›
by (cases c) auto
lemma cwiden_range: ‹cwiden c ∈ {CEq, CGe, CGt 1, CAny}›
by (cases c) auto
subsection ‹Bounded saturation of monotone list fixpoints›
text ‹A set-extensional, monotone step that stays inside a finite universe
saturates within \<^term>‹card U› rounds.›
lemma funpow_saturates:
fixes f :: ‹'a list ⇒ 'a list› and U :: ‹'a set›
assumes ext: ‹⋀xs ys. set xs = set ys ⟹ set (f xs) = set (f ys)›
and mono: ‹⋀xs. set xs ⊆ set (f xs)›
and inU: ‹⋀xs. set xs ⊆ U ⟹ set (f xs) ⊆ U›
and fin: ‹finite U›
and istart: ‹set xs⇩0 ⊆ U›
and N: ‹card U ≤ N›
shows ‹set (f ((f ^^ N) xs⇩0)) = set ((f ^^ N) xs⇩0)›
proof -
have iterU: ‹set ((f ^^ k) xs⇩0) ⊆ U› for k
by (induction k) (use istart inU in auto)
show ?thesis
proof (cases ‹∃k < N. set (f ((f ^^ k) xs⇩0)) = set ((f ^^ k) xs⇩0)›)
case True
then obtain k where k: ‹k < N›
and st: ‹set (f ((f ^^ k) xs⇩0)) = set ((f ^^ k) xs⇩0)› by blast
have stab: ‹set ((f ^^ (k + d)) xs⇩0) = set ((f ^^ k) xs⇩0)› for d
proof (induction d)
case (Suc d)
have ‹set ((f ^^ (k + Suc d)) xs⇩0) = set (f ((f ^^ (k + d)) xs⇩0))›
by simp
also have ‹… = set (f ((f ^^ k) xs⇩0))›
by (rule ext[OF Suc.IH])
finally show ?case using st by simp
qed simp
have NN: ‹set ((f ^^ N) xs⇩0) = set ((f ^^ k) xs⇩0)›
using stab[of ‹N - k›] k by simp
then show ?thesis using ext[OF NN] st by simp
next
case False
have grow: ‹k ≤ N ⟹ k ≤ card (set ((f ^^ k) xs⇩0))› for k
proof (induction k)
case (Suc k)
have ne: ‹set (f ((f ^^ k) xs⇩0)) ≠ set ((f ^^ k) xs⇩0)›
using False Suc.prems by auto
have ‹set ((f ^^ k) xs⇩0) ⊂ set (f ((f ^^ k) xs⇩0))›
using mono ne by blast
then have ‹card (set ((f ^^ k) xs⇩0)) < card (set (f ((f ^^ k) xs⇩0)))›
by (intro psubset_card_mono)
(use inU[OF iterU[of k]] fin finite_subset in auto)
then show ?case using Suc by simp
qed simp
have ‹N ≤ card (set ((f ^^ N) xs⇩0))› using grow by simp
moreover have ‹card (set ((f ^^ N) xs⇩0)) ≤ card U›
by (intro card_mono fin iterU)
ultimately have ‹card (set ((f ^^ N) xs⇩0)) = card U› using N by simp
then have full: ‹set ((f ^^ N) xs⇩0) = U›
by (intro card_subset_eq fin iterU)
have ‹set (f ((f ^^ N) xs⇩0)) ⊆ U›
by (rule inU[OF iterU])
then show ?thesis using full mono[of ‹(f ^^ N) xs⇩0›] by auto
qed
qed
subsection ‹Saturation bounded by the increment, not the universe›
lemma funpow_saturates_delta:
fixes f :: ‹'a list ⇒ 'a list› and D :: ‹'a set›
assumes ext: ‹⋀xs ys. set xs = set ys ⟹ set (f xs) = set (f ys)›
and mono: ‹⋀xs. set xs ⊆ set (f xs)›
and delta: ‹⋀xs. set (f xs) ⊆ set xs ∪ D›
and fin: ‹finite D›
and N: ‹card D ≤ N›
shows ‹set (f ((f ^^ N) xs⇩0)) = set ((f ^^ N) xs⇩0)›
proof -
have chain: ‹set ((f ^^ k) xs⇩0) ⊆ set ((f ^^ Suc k) xs⇩0)› for k
using mono by simp
have incr: ‹set xs⇩0 ⊆ set ((f ^^ k) xs⇩0)› for k
by (induction k) (use chain in auto)
have inD: ‹set ((f ^^ k) xs⇩0) ⊆ set xs⇩0 ∪ D› for k
by (induction k) (use delta in auto)
show ?thesis
proof (cases ‹∃k < N. set (f ((f ^^ k) xs⇩0)) = set ((f ^^ k) xs⇩0)›)
case True
then obtain k where k: ‹k < N›
and st: ‹set (f ((f ^^ k) xs⇩0)) = set ((f ^^ k) xs⇩0)› by blast
have stab: ‹set ((f ^^ (k + d)) xs⇩0) = set ((f ^^ k) xs⇩0)› for d
proof (induction d)
case (Suc d)
have ‹set ((f ^^ (k + Suc d)) xs⇩0) = set (f ((f ^^ (k + d)) xs⇩0))›
by (simp add: funpow_swap1)
also have ‹… = set (f ((f ^^ k) xs⇩0))› by (rule ext[OF Suc.IH])
also have ‹… = set ((f ^^ k) xs⇩0)› by (rule st)
finally show ?case .
qed simp
have ‹set ((f ^^ N) xs⇩0) = set ((f ^^ k) xs⇩0)›
using stab[of ‹N - k›] k by simp
then show ?thesis using st ext by metis
next
case False
have strict: ‹k < N ⟹ set ((f ^^ k) xs⇩0) ⊂ set ((f ^^ Suc k) xs⇩0)› for k
using False chain by (simp add: psubset_eq) blast
have card_ge: ‹k ≤ N ⟹ k ≤ card (set ((f ^^ k) xs⇩0) - set xs⇩0)› for k
proof (induction k)
case (Suc k)
have fk: ‹finite (set ((f ^^ k) xs⇩0) - set xs⇩0)› by simp
have sub: ‹set ((f ^^ k) xs⇩0) - set xs⇩0 ⊂ set ((f ^^ Suc k) xs⇩0) - set xs⇩0›
using strict[of k] Suc.prems incr[of k] by auto
have ‹k ≤ card (set ((f ^^ k) xs⇩0) - set xs⇩0)› using Suc by simp
moreover have ‹card (set ((f ^^ k) xs⇩0) - set xs⇩0)
< card (set ((f ^^ Suc k) xs⇩0) - set xs⇩0)›
by (rule psubset_card_mono) (use sub in auto)
ultimately show ?case by simp
qed simp
have dsub: ‹set ((f ^^ N) xs⇩0) - set xs⇩0 ⊆ D› using inD by auto
have ‹N ≤ card (set ((f ^^ N) xs⇩0) - set xs⇩0)› by (rule card_ge) simp
moreover have ‹card (set ((f ^^ N) xs⇩0) - set xs⇩0) ≤ card D›
by (rule card_mono[OF fin dsub])
ultimately have eqD: ‹set ((f ^^ N) xs⇩0) - set xs⇩0 = D›
using N card_subset_eq[OF fin dsub] by simp
have ‹set (f ((f ^^ N) xs⇩0)) ⊆ set ((f ^^ N) xs⇩0)›
using delta[of ‹(f ^^ N) xs⇩0›] eqD by auto
with mono show ?thesis by blast
qed
qed
subsection ‹Executable nullability›
definition nsym :: ‹'n list ⇒ ('n, 't) sym ⇒ bool› where
‹nsym ns X = (case X of Nt B ⇒ B ∈ set ns | Tm _ ⇒ False)›
definition nstep :: ‹('n, 't) is_cfg ⇒ 'n list ⇒ 'n list› where
‹nstep G ns = remdups (map fst (filter (λ(A, rhs).
list_all (λ(X, r). nsym ns X) rhs) (iprods G)) @ ns)›
definition nullables :: ‹('n, 't) is_cfg ⇒ 'n list› where
‹nullables G = (nstep G ^^ Suc (length (remdups (map fst (iprods G))))) []›
text ‹The code stops at the fixpoint, which comes after a few steps, not one per
nonterminal.›
lemma nullables_code [code]:
‹nullables G = fuel_fix (nstep G) (Suc (length (remdups (map fst (iprods G))))) []›
unfolding nullables_def fuel_fix_funpow ..
lemma nsym_ext: ‹set ns = set ns' ⟹ nsym ns X = nsym ns' X›
unfolding nsym_def by (cases X) auto
lemma nstep_ext:
‹set ns = set ns' ⟹ set (nstep G ns) = set (nstep G ns')›
unfolding nstep_def using nsym_ext[of ns ns']
by (auto simp: list_all_iff case_prod_beta)
lemma nstep_mono: ‹set ns ⊆ set (nstep G ns)›
unfolding nstep_def by auto
lemma nstep_inU:
‹set ns ⊆ fst ` set (iprods G) ⟹ set (nstep G ns) ⊆ fst ` set (iprods G)›
unfolding nstep_def by force
lemma nullables_stable:
‹set (nstep G (nullables G)) = set (nullables G)›
unfolding nullables_def
proof (rule funpow_saturates[where U = ‹fst ` set (iprods G)›])
show ‹⋀xs ys. set xs = set ys ⟹ set (nstep G xs) = set (nstep G ys)›
by (rule nstep_ext)
show ‹⋀xs. set xs ⊆ set (nstep G xs)›
by (rule nstep_mono)
show ‹⋀xs. set xs ⊆ fst ` set (iprods G) ⟹
set (nstep G xs) ⊆ fst ` set (iprods G)›
by (rule nstep_inU)
show ‹finite (fst ` set (iprods G))› by simp
show ‹set [] ⊆ fst ` set (iprods G)› by simp
show ‹card (fst ` set (iprods G)) ≤ Suc (length (remdups (map fst (iprods G))))›
by (metis card_set eq_imp_le le_SucI set_map)
qed
lemma nullables_closed:
assumes ‹(A, rhs) ∈ set (iprods G)›
and ‹list_all (λ(X, r). nsym (nullables G) X) rhs›
shows ‹A ∈ set (nullables G)›
proof -
have ‹A ∈ set (nstep G (nullables G))›
unfolding nstep_def using assms by force
then show ?thesis using nullables_stable by fastforce
qed
text ‹
Completeness against \<^const>‹infG›, through the erased grammar: a
derivation of \<^text>‹eps› erases to one of
\<^term>‹set (derel (iprods G))›, where nullability is the library's
\<^const>‹Nullable›, and the fixpoint above is closed under its introduction
rule.
›
lemma nsym_nullables:
assumes ‹Nullable (set (derel (iprods G))) X›
shows ‹nsym (nullables G) X›
using assms
proof (induction rule: Nullable.induct)
case (NullableSym A w)
from NullableSym.hyps obtain rhs where p: ‹(A, rhs) ∈ set (iprods G)›
and w: ‹w = map fst rhs› unfolding derel_def by auto
have ‹list_all (λ(X, r). nsym (nullables G) X) rhs›
using NullableSym.IH unfolding w by (auto simp: list_all_iff case_prod_beta)
from nullables_closed[OF p this] show ?case by (simp add: nsym_def)
qed
lemma nullables_complete:
assumes ‹(infG G) ⊢ [Nt (B, j)] ⇒(n) []›
shows ‹B ∈ set (nullables G)›
proof -
have ‹set (derel (iprods G)) ⊢ [Nt B] ⇒* []›
using derives_unann[OF relpowp_imp_rtranclp[OF assms]] by simp
from nsym_nullables[OF nullable_if[OF this]] show ?thesis
by (simp add: nsym_def)
qed
subsection ‹The first-token table›
text ‹A flat table of triples: nonterminal, token class, and the widened
relation of the token's column to the nonterminal's own indentation.›
type_synonym ('n, 't) ftab = ‹('n × 't × cirel) list›
definition flook :: ‹('n, 't) ftab ⇒ 'n ⇒ ('t × cirel) list› where
‹flook tab B = map (λ(_, a, ρ). (a, ρ)) (filter (λ(B', _, _). B' = B) tab)›
lemma flookI: ‹(B, a, ρ) ∈ set tab ⟹ (a, ρ) ∈ set (flook tab B)›
unfolding flook_def by force
lemma flookD: ‹(a, ρ) ∈ set (flook tab B) ⟹ (B, a, ρ) ∈ set tab›
unfolding flook_def by auto
fun fscan :: ‹('n, 't) ftab ⇒ 'n list ⇒ ('n, 't) rhs ⇒ ('t × cirel) list› where
‹fscan tab ns [] = []›
| ‹fscan tab ns ((X, r) # rest) =
(case X of
Tm a ⇒ [(a, cwiden (cirel_of r))]
| Nt B ⇒ map (λ(a, ρ). (a, cwiden (ccomp (cirel_of r) ρ))) (flook tab B))
@ (if nsym ns X then fscan tab ns rest else [])›
definition fstep :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab ⇒ ('n, 't) ftab› where
‹fstep G tab = remdups (tab @ concat (map (λ(B, rhs).
map (λ(a, σ). (B, a, σ)) (fscan tab (nullables G) rhs)) (iprods G)))›
definition ffix :: ‹('n, 't) is_cfg ⇒ ('n, 't) ftab› where
‹ffix G = the (while_option (λtab. length (fstep G tab) ≠ length tab)
(fstep G) [])›
definition funiv :: ‹('n, 't) is_cfg ⇒ ('n × 't × cirel) set› where
‹funiv G = fst ` set (iprods G) × set (gram_terms G) × {CEq, CGe, CGt 1, CAny}›
lemma finite_funiv: ‹finite (funiv G)›
unfolding funiv_def by auto
lemma fscan_inU:
assumes tab: ‹set tab ⊆ funiv G›
and terms: ‹⋀a r. (Tm a, r) ∈ set rhs ⟹ a ∈ set (gram_terms G)›
and mem: ‹(a, σ) ∈ set (fscan tab ns rhs)›
shows ‹a ∈ set (gram_terms G) ∧ σ ∈ {CEq, CGe, CGt 1, CAny}›
using terms mem
proof (induction rhs)
case Nil
then show ?case by simp
next
case (Cons Xr rest)
obtain X r where Xr: ‹Xr = (X, r)› by (cases Xr)
from Cons.prems(2) consider
(head) ‹(a, σ) ∈ set (case X of
Tm b ⇒ [(b, cwiden (cirel_of r))]
| Nt B ⇒ map (λ(b, ρ). (b, cwiden (ccomp (cirel_of r) ρ))) (flook tab B))›
| (tail) ‹(a, σ) ∈ set (fscan tab ns rest)›
unfolding Xr by (auto split: if_splits)
then show ?case
proof cases
case head
show ?thesis
proof (cases X)
case (Tm b)
then show ?thesis
using head Cons.prems(1)[of b r] cwiden_range Xr by auto
next
case (Nt B)
from head obtain ρ where ‹(a, ρ) ∈ set (flook tab B)›
and σ: ‹σ = cwiden (ccomp (cirel_of r) ρ)›
unfolding Nt by auto
from flookD[OF this(1)] have ‹(B, a, ρ) ∈ set tab› .
then have ‹a ∈ set (gram_terms G)›
using tab unfolding funiv_def by auto
then show ?thesis using cwiden_range σ by auto
qed
next
case tail
then show ?thesis using Cons.IH Cons.prems(1) by fastforce
qed
qed
lemma fstep_mono: ‹set tab ⊆ set (fstep G tab)›
unfolding fstep_def by auto
lemma fstep_inU:
assumes ‹set tab ⊆ funiv G›
shows ‹set (fstep G tab) ⊆ funiv G›
proof
fix x assume ‹x ∈ set (fstep G tab)›
then consider ‹x ∈ set tab›
| B rhs a σ where ‹(B, rhs) ∈ set (iprods G)›
and ‹(a, σ) ∈ set (fscan tab (nullables G) rhs)› and ‹x = (B, a, σ)›
unfolding fstep_def by fastforce
then show ‹x ∈ funiv G›
proof cases
case 1
then show ?thesis using assms by blast
next
case 2
have ‹a ∈ set (gram_terms G) ∧ σ ∈ {CEq, CGe, CGt 1, CAny}›
using fscan_inU[OF assms _ 2(2)] gram_termsI[OF 2(1)] by blast
then show ?thesis
using 2 unfolding funiv_def by force
qed
qed
lemma fstep_distinct: ‹distinct (fstep G tab)›
unfolding fstep_def by simp
text ‹Saturation loops: iterate until the (always distinct) table stops
growing.›
lemma while_table_saturates_from:
fixes step :: ‹'x list ⇒ 'x list› and U :: ‹'x set›
assumes mono: ‹⋀tab. set tab ⊆ set (step tab)›
and dst: ‹⋀tab. distinct (step tab)›
and inU: ‹⋀tab. set tab ⊆ U ⟹ set (step tab) ⊆ U›
and fin: ‹finite U›
and istart: ‹set tab⇩0 ⊆ U› and dst⇩0: ‹distinct tab⇩0›
shows ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step tab⇩0 = Some t ∧
set (step t) = set t ∧ set t ⊆ U›
proof -
define P where ‹P = (λtab :: 'x list. set tab ⊆ U ∧ distinct tab)›
define f where ‹f = (λtab :: 'x list. card U - card (set tab))›
have stepP: ‹P (step tab) ∧ f (step tab) < f tab›
if Ptab: ‹P tab› and b: ‹length (step tab) ≠ length tab› for tab
proof -
have PU: ‹set (step tab) ⊆ U›
using Ptab inU unfolding P_def by blast
have cs: ‹card (set (step tab)) = length (step tab)›
using dst by (simp add: distinct_card)
have ct: ‹card (set tab) = length tab›
using Ptab unfolding P_def by (simp add: distinct_card)
have le: ‹card (set tab) ≤ card (set (step tab))›
by (intro card_mono) (auto simp: mono)
have lt: ‹card (set tab) < card (set (step tab))›
using le b cs ct by simp
have ltU: ‹card (set tab) < card U›
using lt card_mono[OF fin PU] by simp
have ‹f (step tab) < f tab›
unfolding f_def using lt ltU by (simp add: diff_less_mono2)
then show ?thesis using PU dst unfolding P_def by simp
qed
have P⇩0: ‹P tab⇩0› using istart dst⇩0 unfolding P_def by simp
have Some: ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step tab⇩0 = Some t›
by (rule measure_while_option_Some[where P = P and f = f])
(use stepP P⇩0 in ‹auto simp: P_def›)
then obtain t where t:
‹while_option (λtab. length (step tab) ≠ length tab) step tab⇩0 = Some t› by blast
have Pt: ‹P t›
by (rule while_option_rule[OF _ t]) (use stepP P⇩0 in ‹auto simp: P_def›)
have stop: ‹length (step t) = length t›
using while_option_stop[OF t] by simp
have ‹card (set t) = card (set (step t))›
using stop Pt dst unfolding P_def by (simp add: distinct_card)
then have ‹set t = set (step t)›
by (intro card_subset_eq) (auto simp: mono)
then show ?thesis using t Pt unfolding P_def by auto
qed
lemma while_table_saturates:
fixes step :: ‹'x list ⇒ 'x list› and U :: ‹'x set›
assumes ‹⋀tab. set tab ⊆ set (step tab)›
and ‹⋀tab. distinct (step tab)›
and ‹⋀tab. set tab ⊆ U ⟹ set (step tab) ⊆ U›
and ‹finite U›
shows ‹∃t. while_option (λtab. length (step tab) ≠ length tab) step [] = Some t ∧
set (step t) = set t ∧ set t ⊆ U›
by (rule while_table_saturates_from[OF assms]) simp_all
lemma ffix_while:
‹∃t. while_option (λtab. length (fstep G tab) ≠ length tab) (fstep G) [] = Some t ∧
set (fstep G t) = set t ∧ set t ⊆ funiv G›
by (rule while_table_saturates[OF fstep_mono fstep_distinct fstep_inU finite_funiv])
lemma ffix_stable: ‹set (fstep G (ffix G)) = set (ffix G)›
proof -
obtain t where t: ‹while_option (λtab. length (fstep G tab) ≠ length tab)
(fstep G) [] = Some t›
and st: ‹set (fstep G t) = set t›
using ffix_while by blast
show ?thesis unfolding ffix_def t by (simp add: st)
qed
lemma ffix_inU: ‹set (ffix G) ⊆ funiv G›
proof -
obtain t where t: ‹while_option (λtab. length (fstep G tab) ≠ length tab)
(fstep G) [] = Some t›
and U: ‹set t ⊆ funiv G›
using ffix_while by blast
show ?thesis unfolding ffix_def t by (simp add: U)
qed
lemma ffix_closed:
assumes ‹(B, rhs) ∈ set (iprods G)›
and ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) rhs)›
shows ‹(B, a, σ) ∈ set (ffix G)›
proof -
have ‹(B, a, σ) ∈ set (fstep G (ffix G))›
unfolding fstep_def using assms by force
then show ?thesis using ffix_stable by blast
qed
subsection ‹Completeness of the first-token table›
lemma fscan_complete:
assumes ‹(infG G) ⊢ arhs ⇒(n) Tm (a, c) # V›
and ‹annotates j rhs arhs›
shows ‹∃σ. (a, σ) ∈ set (fscan (ffix G) (nullables G) rhs) ∧ csat σ c j›
using assms
proof (induction n arbitrary: rhs arhs j V rule: less_induct)
case (less n)
have ‹arhs ≠ []›
using less.prems(1) deriven_from_empty by fastforce
then obtain Xr rest where rhs: ‹rhs = Xr # rest›
using less.prems(2) unfolding annotates_def
by (cases rhs) auto
obtain X r where Xr: ‹Xr = (X, r)› by (cases Xr)
from less.prems(2) obtain Y arest where arhs: ‹arhs = Y # arest›
and Y: ‹∃j⇩1. Y = annsym (X, j⇩1) ∧ irel_sat r j⇩1 j›
and annrest: ‹annotates j rest arest›
unfolding rhs Xr by (cases arhs) (auto simp: annotates_def)
have ‹(infG G) ⊢ [Y] @ arest ⇒(n) Tm (a, c) # V›
using less.prems(1) unfolding arhs by simp
from iffD1[OF deriven_appendD this]
obtain n⇩1 n⇩2 w⇩1 w⇩2 where n: ‹n = n⇩1 + n⇩2› and w: ‹Tm (a, c) # V = w⇩1 @ w⇩2›
and d⇩1: ‹(infG G) ⊢ [Y] ⇒(n⇩1) w⇩1›
and d⇩2: ‹(infG G) ⊢ arest ⇒(n⇩2) w⇩2›
by blast
obtain j⇩1 where Yj: ‹Y = annsym (X, j⇩1)› and sat: ‹irel_sat r j⇩1 j›
using Y by blast
show ?case
proof (cases w⇩1)
case Nil
have XN: ‹nsym (nullables G) X›
proof (cases X)
case (Tm b)
then show ?thesis using d⇩1 Nil Yj by (fastforce simp: deriven_Tm_Cons)
next
case (Nt C)
have ‹(infG G) ⊢ [Nt (C, j⇩1)] ⇒(n⇩1) []›
using d⇩1 Yj Nt unfolding Nil by simp
from nullables_complete[OF this] show ?thesis
using Nt unfolding nsym_def by simp
qed
have n⇩1: ‹n⇩1 ≠ 0› using d⇩1 Nil Yj by (cases n⇩1) auto
then have n⇩2: ‹n⇩2 < n› using n by simp
have d⇩2': ‹(infG G) ⊢ arest ⇒(n⇩2) Tm (a, c) # V›
using d⇩2 w unfolding Nil by simp
from less.IH[OF n⇩2 d⇩2' annrest]
obtain σ where ‹(a, σ) ∈ set (fscan (ffix G) (nullables G) rest)›
and ‹csat σ c j› by blast
then show ?thesis
unfolding rhs Xr using XN by auto
next
case (Cons y w⇩1')
have y: ‹y = Tm (a, c)› and V: ‹V = w⇩1' @ w⇩2›
using w unfolding Cons by auto
show ?thesis
proof (cases X)
case (Tm b)
have YT: ‹Y = Tm (b, j⇩1)› using Yj Tm by simp
have ‹w⇩1 = [Tm (b, j⇩1)]›
using d⇩1[unfolded YT] by (simp add: deriven_Tm_Cons)
then have ab: ‹a = b› and cj: ‹c = j⇩1›
using Cons y by auto
have ‹csat (cirel_of r) c j› using sat cj by simp
then have ‹csat (cwiden (cirel_of r)) c j› by (rule csat_cwiden)
then show ?thesis
unfolding rhs Xr using Tm ab by auto
next
case (Nt C)
have YN: ‹Y = Nt (C, j⇩1)› using Yj Nt by simp
obtain m⇩1 where n⇩1: ‹n⇩1 = Suc m⇩1›
using d⇩1 Cons y YN by (cases n⇩1) auto
from relpowp_Suc_D2[OF d⇩1[unfolded n⇩1 YN]] obtain v where
st: ‹infG G ⊢ [Nt (C, j⇩1)] ⇒ v›
and dv: ‹(infG G) ⊢ v ⇒(m⇩1) Tm (a, c) # w⇩1'›
unfolding Cons y by blast
from st obtain brhs' where
pr: ‹((C, j⇩1), brhs') ∈ infG G› and v: ‹v = brhs'›
by (auto simp: derive_singleton)
from pr[unfolded infG_alt] obtain brhs where
brhs: ‹(C, brhs) ∈ set (iprods G)› and annb: ‹annotates j⇩1 brhs brhs'›
by blast
have ‹m⇩1 < n› using n n⇩1 by simp
from less.IH[OF this dv[unfolded v] annb]
obtain ρ where mem: ‹(a, ρ) ∈ set (fscan (ffix G) (nullables G) brhs)›
and satρ: ‹csat ρ c j⇩1› by blast
have inffix: ‹(C, a, ρ) ∈ set (ffix G)›
by (rule ffix_closed[OF brhs mem])
have ‹csat (cwiden (ccomp (cirel_of r) ρ)) c j›
proof -
have ‹csat (ccomp (cirel_of r) ρ) c j›
unfolding csat_ccomp using satρ sat by auto
then show ?thesis by (rule csat_cwiden)
qed
then show ?thesis
unfolding rhs Xr using Nt flookI[OF inffix] by force
qed
qed
qed
section ‹LR tables and conflict reports›
text ‹
The layers on top of the LR(0) automaton and the lookahead tables: the
canonical per-item LALR cells and the conflict report over them; the
driver that parses with the cells at runtime follows in
\<^text>‹LR_Driver›.
›
subsection ‹Live frames›
definition live :: ‹('n, 't) xitem list ⇒ bool› where
‹live xs = list_ex (λ(pr, m, R). irep_nonempty R) xs›
section ‹Column-aware conflict analysis›
text ‹
Follow cells relate token columns to the indentations of different
items, which are pairwise incomparable, so a token-level report could
compare token classes only. For a sharper check every item
is related to a ∗‹common anchor›, the indentation label of the goto
that built the state. Composing these paths needs inverse relations,
which \<^typ>‹cirel› lacks, so the analysis runs in a small
two-directional class algebra \<^text>‹wrel›. That algebra is the verified
core: embedding, inversion and composition only weaken, and
\<^text>‹wdisjoint› detects only disjoint pairs, so pruning a conflict
pair is justified.
Adams \<^cite>‹‹Sect.~5.8› in "adams2013"› observes that the items of one state can
carry different indentation sets, so one set shared by the whole state is not enough.
The common anchor shares no set: each item keeps its own relation to the anchor.
›
subsection ‹The two-directional class algebra›