Theory LR_Prod
theory LR_Prod
imports LR_Tok
begin
section ‹Candidate tables›
text ‹The trie step filters the completed productions of a state by its
lookahead cell at every step. Here the filtered lists are computed once, per
state and lookahead, and the driver reads its reduce candidates off that
table: the reduce function ‹Reduce› of an LR automaton
\<^cite>‹‹Sect.~2.2› in "deremer1982-lalr-lookahead"›.›
subsection ‹Maps and entries of tries›
fun mapk_num :: ‹(num ⇒ 'a ⇒ 'b option) ⇒ 'a ntrie ⇒ 'b ntrie› where
‹mapk_num g NTip = NTip›
| ‹mapk_num g (NNode x l r) = NNode (Option.bind x (g num.One))
(mapk_num (λk. g (num.Bit0 k)) l) (mapk_num (λk. g (num.Bit1 k)) r)›
lemma lookup_mapk_num: ‹lookup_num (mapk_num g t) k = Option.bind (lookup_num t k) (g k)›
proof (induction t arbitrary: g k)
case (NNode x l r)
then show ?case by (cases k) auto
qed simp
definition tab_mapk :: ‹(nat ⇒ 'a ⇒ 'b option) ⇒ 'a ntab ⇒ 'b ntab› where
‹tab_mapk f t = (case t of NTab z tr ⇒
NTab (Option.bind z (f 0)) (mapk_num (λk. f (nat_of_num k)) tr))›
lemma tlookup_tab_mapk: ‹tlookup (tab_mapk f t) n = Option.bind (tlookup t n) (f n)›
proof (cases t)
case (NTab z tr)
show ?thesis
proof (cases ‹n = 0›)
case False
then have n: ‹nat_of_num (num_of_nat n) = n› using num_of_nat_inverse by simp
show ?thesis using False unfolding NTab tab_mapk_def tlookup_def
by (simp add: lookup_mapk_num n)
qed (simp add: NTab tab_mapk_def tlookup_def)
qed
fun entries_num :: ‹(num ⇒ nat) ⇒ 'a ntrie ⇒ (nat × 'a) list› where
‹entries_num f NTip = []›
| ‹entries_num f (NNode x l r) = (case x of None ⇒ [] | Some a ⇒ [(f num.One, a)]) @
entries_num (λk. f (num.Bit0 k)) l @ entries_num (λk. f (num.Bit1 k)) r›
lemma entries_num_complete:
‹lookup_num t k = Some a ⟹ (f k, a) ∈ set (entries_num f t)›
proof (induction t arbitrary: f k)
case (NNode x l r)
show ?case
proof (cases k)
case (Bit0 k')
then show ?thesis using NNode.prems NNode.IH(1)[of k' ‹λk. f (num.Bit0 k)›] by simp
next
case (Bit1 k')
then show ?thesis using NNode.prems NNode.IH(2)[of k' ‹λk. f (num.Bit1 k)›] by simp
qed (use NNode.prems in simp)
qed simp
definition tentries :: ‹'a ntab ⇒ (nat × 'a) list› where
‹tentries t = (case t of NTab z tr ⇒
(case z of None ⇒ [] | Some a ⇒ [(0, a)]) @ entries_num nat_of_num tr)›
lemma tentries_complete: ‹tlookup t n = Some a ⟹ (n, a) ∈ set (tentries t)›
proof (cases t)
case (NTab z tr)
assume h: ‹tlookup t n = Some a›
show ?thesis
proof (cases ‹n = 0›)
case False
then have n: ‹nat_of_num (num_of_nat n) = n› using num_of_nat_inverse by simp
from h False have ‹lookup_num tr (num_of_nat n) = Some a› unfolding NTab tlookup_def by simp
from entries_num_complete[OF this, of nat_of_num] show ?thesis
unfolding NTab tentries_def n by simp
qed (use h in ‹simp add: NTab tentries_def tlookup_def›)
qed
definition trow :: ‹'a ntab ntab ⇒ nat ⇒ 'a ntab› where
‹trow t i = (case tlookup t i of None ⇒ NTab None NTip | Some r ⇒ r)›
lemma jget_trow: ‹jget t i k = tlookup (trow t i) k›
unfolding jget_def trow_def tlookup_def by (simp split: option.splits)
subsection ‹The candidate tables and their step›