Theory LR_Sparse
theory LR_Sparse
imports LR_Fast "HOL-Library.IArray"
begin
section ‹Sparse closures for the set-anchored driver›
text ‹A closure of \<^const>‹dclosure› has one slot per production, but on
a grammar of 286 items only about nine have a non-empty anchor set. No
driver operation observes the empty ones: \<^const>‹live› and
\<^const>‹gfinal› look at non-empty items only, \<^const>‹red_set› unions
anchor sets, \<^const>‹lgoto› maps an empty item to an empty one, and a
round's image of an empty set is empty. The sparse driver keeps only the
non-empty items, computes a closure's rounds per nonterminal instead of per
production, and refers to productions and symbols by numbers.
The one observation that could depend on empty items is the order of the
reduce candidates (\<^const>‹dcands›: \<^const>‹remdups› keeps the last
occurrence). It does not, because the closures the driver builds are
∗‹coherent›: items with the same production and dot have the same anchor
set (‹coh›), so a production that has a non-empty complete item has only
non-empty ones. Coherence needs the start production to be no production of
the grammar, which \<^const>‹fresh_name› provides. Items known to have the same
indentation set can share one representation \<^cite>‹‹Sect.~5.8› in "adams2013"›; coherence is
such a fact, used here only to drop empty items.›
subsection ‹Productions as records›
text ‹The productions of the grammar and the start production, in one list;
the start production gets the last position.›
definition eprods :: ‹('n, 't) is_cfg ⇒ 'n ⇒ ('n × ('n, 't) rhs) list› where
‹eprods G Shn = iprods G @ [(Shn, [(Nt (istart G), Eq)])]›
fun symid :: ‹'n list ⇒ ('n, 't) sym ⇒ (nat, 't) sym› where
‹symid ns (Nt B) = Nt (ntidx ns B)›
| ‹symid ns (Tm a) = Tm a›
text ‹A production's record: its number (the first position of the production),
the number of its left-hand side (the first position of a production with that
left-hand side), its right-hand side over numbered nonterminals, and the
production itself, for the tree and the reduce cells.›
type_synonym ('n, 't) prec = ‹nat × nat × ((nat, 't) sym × irel) list × 'n × ('n, 't) rhs›
type_synonym ('n, 't) sitem = ‹('n, 't) prec × nat × indrep›
definition mkrec :: ‹('n × ('n, 't) rhs) list ⇒ 'n × ('n, 't) rhs ⇒ ('n, 't) prec› where
‹mkrec ps p = (ntidx ps p, ntidx (map fst ps) (fst p),
map (λ(X, r). (symid (map fst ps) X, r)) (snd p), p)›
definition rpid :: ‹('n, 't) prec ⇒ nat› where ‹rpid r = fst r›
definition rlhs :: ‹('n, 't) prec ⇒ nat› where ‹rlhs r = fst (snd r)›
definition rrhs :: ‹('n, 't) prec ⇒ ((nat, 't) sym × irel) list› where ‹rrhs r = fst (snd (snd r))›
definition rprod :: ‹('n, 't) prec ⇒ 'n × ('n, 't) rhs› where ‹rprod r = snd (snd (snd r))›
lemma mkrec_sel [simp]:
‹rpid (mkrec ps p) = ntidx ps p›
‹rlhs (mkrec ps p) = ntidx (map fst ps) (fst p)›
‹rrhs (mkrec ps p) = map (λ(X, r). (symid (map fst ps) X, r)) (snd p)›
‹rprod (mkrec ps p) = p›
by (simp_all add: mkrec_def rpid_def rlhs_def rrhs_def rprod_def)
fun sdec :: ‹('n, 't) sitem ⇒ ('n, 't) xitem› where
‹sdec (r, m, R) = (rprod r, m, R)›
text ‹Every record of a sparse item list is a table record.›
definition swf :: ‹('n × ('n, 't) rhs) list ⇒ ('n, 't) sitem list ⇒ bool› where
‹swf ps xs ⟷ (∀(r, m, R) ∈ set xs. r ∈ mkrec ps ` set ps)›
subsubsection ‹Numbering›
lemma ntidx_less: ‹ntidx xs x < length xs ⟷ x ∈ set xs›
by (induction xs) auto
lemma ntidx_nth: ‹x ∈ set xs ⟹ xs ! ntidx xs x = x›
by (induction xs) auto
lemma ntidx_notin: ‹x ∉ set xs ⟹ ntidx xs x = length xs›
by (induction xs) auto
lemma ntidx_append_in: ‹x ∈ set xs ⟹ ntidx (xs @ ys) x = ntidx xs x›
by (induction xs) auto
lemma ntidx_append_notin: ‹x ∉ set xs ⟹ ntidx (xs @ ys) x = length xs + ntidx ys x›
by (induction xs) auto
lemma ntidx_nth_le: ‹k < length xs ⟹ ntidx xs (xs ! k) ≤ k›
proof (induction xs arbitrary: k)
case (Cons a xs)
then show ?case by (cases k) auto
qed simp
subsection ‹The tables›
text ‹Per grammar: the records by position, for each nonterminal number the
positions of its productions, the number of productions, the goto table and the
reduce cells over numbered symbols and productions, and the number of
states.›