Theory LR_Recover
theory LR_Recover
imports LR_Diag
begin
section ‹Recovering from a rejected word›
text ‹A rejected word is rewritten into one that parses, and the verified parser
runs on the result. The user adds an ordinary error token to the token type and
alternatives such as ‹Expr = … | ERR›, so the grammar stays an ordinary grammar,
and \<^text>‹parser (diagnostics) p for G recover ERR› defines ‹p_repair›, the
rewriter, and ‹p_recover›. The tree of a rewritten word is a tree of that word:
‹p.sound› is the whole story, and nothing is proved about the rewriter.
The rewriter follows the ‹error› token of ocamlyacc \<^cite>‹‹Sect.~17.4.4› in "leroy2026-ocaml-manual"›. At a stop, it pops the stack to a
configuration that can shift the error token, skips the input until the parser
can continue after that token, and replaces the tokens popped and skipped by one
error token. Popped entries give the input they cover by the number of their
tokens. Then it starts over on the new word, for the next error.
Where no error token fits, or the grammar has none, it searches for a repair
sequence as in CPCT+ \<^cite>‹"diekmann2020-dont-panic"›: tokens inserted, deleted and
kept. See ‹rcpct›.›
subsection ‹A plan›
text ‹What the search needs from a driver, on a configuration ‹'c› without tokens:
the configuration past the shift of a terminal at a column, whether the end of
the input is accepted, the stack with its top entry popped, and the columns
to try. ‹ro_can› is a test of a terminal before it is tried at the columns: one that
fails it may be skipped, so it is ‹False› only where every column fails.›
record ('c, 't) rops =
ro_adv :: ‹'c ⇒ 't × nat ⇒ 'c option›
ro_end :: ‹'c ⇒ bool›
ro_pop :: ‹'c ⇒ 'c option›
ro_cols :: ‹'c ⇒ nat list›
ro_can :: ‹'c ⇒ 't ⇒ bool›
text ‹As \<^const>‹dtrial›, but it returns the configuration past the shift.›
partial_function (option) dadv ::
‹('c ⇒ (('n, 't) dact × 'c) option) ⇒ ('c ⇒ bool) ⇒ ('c ⇒ 'k list) ⇒
'k list option × nat × nat ⇒ 'c ⇒ 'c option›
where
‹dadv ctl fin key d c =
(if fin c ∨ fst d = Some (key c) then None
else (case ctl c of
None ⇒ None
| Some (act, c') ⇒
if act = DShift then Some c' else dadv ctl fin key (bupd d (key c)) c'))›
lemmas dadv_simps [code] = dadv.simps
text ‹The first column at which ‹f› succeeds.›
fun rfirst :: ‹(nat ⇒ 'c option) ⇒ nat list ⇒ (nat × 'c) option› where
‹rfirst f [] = None›
| ‹rfirst f (k # ks) = (case f k of Some c ⇒ Some (k, c) | None ⇒ rfirst f ks)›
text ‹How many tokens to skip until the parser can continue: skipping none means
that the error token is inserted.›
fun rskip :: ‹('c, 't) rops ⇒ 'c ⇒ nat ⇒ ('t × nat) list ⇒ nat option› where
‹rskip ops c s [] = (if ro_end ops c then Some s else None)›
| ‹rskip ops c s (x # xs) = (if ro_adv ops c x ≠ None then Some s else rskip ops c (Suc s) xs)›
text ‹The column of the error token: the column of the input it replaces if it
fits there. Otherwise the nearest one that fits, so that a misplaced token can be
replaced: this is the only field of the error token's span that may differ from
the input, as the parser reads it from there. Between two tried columns acceptance
is constant, see \<^const>‹lreps›.›
definition rhere :: ‹('c, 't) rops ⇒ 't ⇒ nat ⇒ ('t × nat) list ⇒ 'c ⇒ (nat × nat) option› where
‹rhere ops e k xs c =
(case rfirst (λr. ro_adv ops c (e, r))
(k # sort_key (λr. if r ≤ k then k - r else r - k) (ro_cols ops c)) of
None ⇒ None
| Some (k', c') ⇒ map_option (λs. (k', s)) (rskip ops c' 0 xs))›
definition alen :: ‹('m, 'ch, 'n, 't) ast ⇒ nat› where
‹alen t = length (aspans t [])›
text ‹The column of the input at index ‹a›, at the end of the input right after
the last token.›
definition rcol :: ‹('m, 'ch, 't) tword ⇒ nat ⇒ nat› where
‹rcol w a = (if a < length w then s_col (span (w ! a))
else let s = span (last w) in s_col s + s_len s)›
text ‹A plan: replace the tokens from index ‹a› up to ‹b› by an error token at
column ‹k›. The stack goes down from the configuration ‹c› at index ‹i›; the
index ‹a› follows it, and the first configuration that works is taken, so the
innermost construct takes the error.›
type_synonym rplan = ‹nat × nat × nat›
fun rsearch :: ‹('c, 't) rops ⇒ 't ⇒ ('m, 'ch, 't) tword ⇒ nat ⇒ nat ⇒ 'c ⇒
('m, 'ch, 'n, 't) ast list ⇒ rplan option› where
‹rsearch ops e w i a c [] =
map_option (λ(k, s). (a, i + s, k)) (rhere ops e (rcol w a) (tcols (drop i w)) c)›
| ‹rsearch ops e w i a c (t # ts) =
(case rhere ops e (rcol w a) (tcols (drop i w)) c of
Some (k, s) ⇒ Some (a, i + s, k)
| None ⇒ (case ro_pop ops c of
None ⇒ None
| Some c' ⇒ rsearch ops e w i (a - alen t) c' ts))›
subsection ‹The new word›
text ‹The span of the error token at column ‹k›: it runs from the first replaced
token to the last, with their text. If nothing is replaced it is empty, in
front of the token at ‹a› or after the last token.›
definition rspan :: ‹('m, 'ch, 't) tword ⇒ nat ⇒ ('t, 'ch, 'm) token_scheme list ⇒ nat ⇒ 'ch span› where
‹rspan w a ss k = (case ss of
[] ⇒ if a < length w
then (span (w ! a))⦇s_col := k, s_len := 0, s_txt := []⦈
else let s = span (last w) in
s⦇s_col := k, s_off := s_off s + s_len s, s_len := 0, s_txt := []⦈
| f # _ ⇒ let l = span (last ss) in
(span f)⦇s_col := k, s_len := s_off l + s_len l - s_off (span f),
s_txt := concat (map (s_txt ∘ span) ss)⦈)›
text ‹The error token is a replaced token or a neighbour with its terminal and span
changed, so a token record extended by the user keeps its fields.›
definition rsplice :: ‹'t ⇒ rplan ⇒ ('m, 'ch, 't) tword ⇒ ('m, 'ch, 't) tword› where
‹rsplice e p w = (case p of (a, b, k) ⇒
let ss = take (b - a) (drop a w);
x = (if ss ≠ [] then last ss else if a < length w then w ! a else last w)
in take a w @ [x⦇tok := e, span := rspan w a ss k⦈] @ drop b w)›
subsection ‹Repair sequences›
text ‹The search of \<^cite>‹‹Fig.~6, Sect.~5› in "diekmann2020-dont-panic"› over configurations
‹'c›, for the configuration after the last shift. A node holds a configuration,
the input left, the number of tokens kept in a row and the repair so far, last
step first. Keeping a token costs 0, inserting or deleting one costs 1, and a
delete is not followed by an insert (Fig.~6, line~12). A node succeeds at the
end of the input if that is accepted, or after ‹rnshifts› tokens kept.
‹rnshifts› is their ‹Nshifts›, 3 as in Corchuelo et al.
\<^cite>‹‹Sect.~4.1› in "diekmann2020-dont-panic"›.
Their reduction-only step (CR Shift 3, Fig.~7) is not needed: \<^const>‹ro_adv› runs from
the configuration after the last shift with the terminal as lookahead, so it does
the reductions that terminal licenses. Reductions it does not license would give
a word the parser rejects, and this search rewrites words.
Compatible nodes are merged \<^cite>‹‹Sect.~5.2› in "diekmann2020-dont-panic"›, see ‹rkey›. HOL has no clock,
so a budget of nodes replaces their timeout \<^cite>‹‹Sect.~5.4› in "diekmann2020-dont-panic"›: ‹rnodes› nodes for
the whole word, so that several stops do not add up. It counts the nodes searched,
which take most of the time of a repair, and merged nodes are free. An inserted
terminal takes the column of the token it stands in front of if it fits there,
otherwise the nearest that fits, as the error token does in \<^const>‹rhere›.›
definition rnshifts :: nat where ‹rnshifts = 3›
definition rntry :: nat where ‹rntry = 250›
definition rnodes :: nat where ‹rnodes = 240›
type_synonym ('c, 't) rnode = ‹'c × ('t × nat) list × nat × 't rop list›
definition rsuccess :: ‹('c, 't) rops ⇒ ('c, 't) rnode ⇒ bool› where
‹rsuccess ops nd = (case nd of (c, xs, n, _) ⇒ rnshifts ≤ n ∨ (xs = [] ∧ ro_end ops c))›
text ‹The neighbours of a node, at cost 0 and at cost 1. ‹ke› is the column at the
end of the input. The terminals ‹ts› are tried in their order, which is the
order of the ties in the ranking.›
definition rnbrs :: ‹('c, 't) rops ⇒ 't list ⇒ nat ⇒ ('c, 't) rnode ⇒
('c, 't) rnode list × ('c, 't) rnode list› where
‹rnbrs ops ts ke nd = (case nd of (c, xs, n, os) ⇒
let k = (case xs of [] ⇒ ke | x # _ ⇒ snd x);
cs = k # sort_key (λr. if r ≤ k then k - r else r - k) (ro_cols ops c);
ins = (case os of RDel _ # _ ⇒ []
| _ ⇒ List.map_filter (λt. if ¬ ro_can ops c t then None
else map_option (λ(r, c'). (c', xs, 0, RIns t r # os))
(rfirst (λr. ro_adv ops c (t, r)) cs)) ts)
in (case xs of
[] ⇒ ([], ins)
| x # xs' ⇒
(case ro_adv ops c x of None ⇒ [] | Some c' ⇒ [(c', xs', Suc n, RKeep # os)],
ins @ [(c, xs', 0, RDel (fst x) # os)])))›
text ‹In the search of \<^cite>‹‹Fig.~6› in "diekmann2020-dont-panic"›, a node of a key already seen has the same future at no less cost, so
it is dropped, and the first in the search stays: the search picks one repair, so
it needs no parent pointer trees. A key is that of \<^cite>‹‹Sect.~5.2› in "diekmann2020-dont-panic"›: the configuration, the
input left, the tokens kept in a row, and whether the repair ends in a delete. It
adds the inserted terminals of ‹av›, as they count in the ranking.›
fun rinserted :: ‹'t rop ⇒ 't list› where
‹rinserted (RIns t k) = [t]›
| ‹rinserted _ = []›
definition ravoided :: ‹'t list ⇒ 't rop list ⇒ nat› where
‹ravoided av os = length (filter (λt. t ∈ set av) (concat (map rinserted os)))›
fun rdeleted :: ‹'t rop list ⇒ bool› where
‹rdeleted (RDel _ # _) = True›
| ‹rdeleted _ = False›
type_synonym 'c rkey = ‹'c × nat × nat × bool × nat›
definition rkey :: ‹'t list ⇒ ('c, 't) rnode ⇒ 'c rkey› where
‹rkey av nd = (case nd of (c, xs, n, os) ⇒ (c, length xs, n, rdeleted os, ravoided av os))›
text ‹All nodes of one cost: the budget left, the nodes of the next cost, the
successes in the order of the search, and the keys seen. Their complete set is
the point of \<^cite>‹‹Sect.~5.1› in "diekmann2020-dont-panic"›, so the level is finished after the first one. If the
budget runs out the successes so far stand.›
fun rlevel :: ‹('c, 't) rops ⇒ 't list ⇒ 't list ⇒ nat ⇒ nat ⇒ ('c, 't) rnode list ⇒
('c, 't) rnode list ⇒ ('c, 't) rnode list ⇒ 'c rkey list ⇒
nat × ('c, 't) rnode list × ('c, 't) rnode list × 'c rkey list› where
‹rlevel ops ts av ke 0 cur nx ok vs = (0, [], rev ok, vs)›
| ‹rlevel ops ts av ke (Suc b) [] nx ok vs = (Suc b, rev nx, rev ok, vs)›
| ‹rlevel ops ts av ke (Suc b) (nd # cur) nx ok vs =
(let k = rkey av nd in
if k ∈ set vs then rlevel ops ts av ke (Suc b) cur nx ok vs
else if rsuccess ops nd then rlevel ops ts av ke b cur nx (nd # ok) (k # vs)
else (case rnbrs ops ts ke nd of
(zs, os) ⇒ rlevel ops ts av ke b (zs @ cur) (rev os @ nx) ok (k # vs)))›
text ‹The patterns on ‹b› and on ‹cur› together do not survive the preprocessing of
‹Code_Target_Numeral›, where ‹0› is no constructor.›
lemma rlevel_code [code]:
‹rlevel ops ts av ke b cur nx ok vs = (if b = 0 then (0, [], rev ok, vs) else case cur of
[] ⇒ (b, rev nx, rev ok, vs)
| nd # cur' ⇒
let k = rkey av nd in
if k ∈ set vs then rlevel ops ts av ke b cur' nx ok vs
else if rsuccess ops nd then rlevel ops ts av ke (b - 1) cur' nx (nd # ok) (k # vs)
else (case rnbrs ops ts ke nd of
(zs, os) ⇒ rlevel ops ts av ke (b - 1) (zs @ cur') (rev os @ nx) ok (k # vs)))›
by (cases b; cases cur) (simp_all add: Let_def)
fun rcost :: ‹nat ⇒ ('c, 't) rops ⇒ 't list ⇒ 't list ⇒ nat ⇒ nat ⇒ ('c, 't) rnode list ⇒
'c rkey list ⇒ nat × ('c, 't) rnode list› where
‹rcost 0 ops ts av ke b cur vs = (b, [])›
| ‹rcost (Suc f) ops ts av ke b cur vs = (case rlevel ops ts av ke b cur [] [] vs of
(b', nx, ok, vs') ⇒ if ok ≠ [] ∨ nx = [] then (b', ok) else rcost f ops ts av ke b' nx vs')›
text ‹The ranking of \<^cite>‹‹Sect.~5.3› in "diekmann2020-dont-panic"›: how far parsing continues, up to \<^const>‹rntry›
tokens, then fewer inserted terminals of ‹av› (‹%avoid_insert› \<^cite>‹‹Sect.~7.3› in "diekmann2020-dont-panic"›), then
the first in the search, where they choose at random.›
fun rreach :: ‹('c, 't) rops ⇒ nat ⇒ 'c ⇒ ('t × nat) list ⇒ nat ⇒ nat› where
‹rreach ops 0 c xs s = s›
| ‹rreach ops (Suc f) c xs s = (case xs of
[] ⇒ if ro_end ops c then Suc s else s
| x # xs' ⇒ (case ro_adv ops c x of None ⇒ s | Some c' ⇒ rreach ops f c' xs' (Suc s)))›
fun rkept :: ‹'t rop ⇒ bool› where
‹rkept RKeep = True›
| ‹rkept _ = False›
definition rrank :: ‹('c, 't) rops ⇒ 't list ⇒ nat ⇒ ('c, 't) rnode ⇒ nat × nat› where
‹rrank ops av n nd = (case nd of (c, xs, _, os) ⇒
(rreach ops rntry c xs (n - length xs),
ravoided av os))›
definition rbest :: ‹('c, 't) rops ⇒ 't list ⇒ nat ⇒ ('c, 't) rnode ⇒ ('c, 't) rnode list ⇒
('c, 't) rnode› where
‹rbest ops av n nd nds = fst (fold (λy (b, br).
let yr = rrank ops av n y
in if fst br < fst yr ∨ (fst br = fst yr ∧ snd yr < snd br) then (y, yr) else (b, br))
nds (nd, rrank ops av n nd))›
text ‹The best repair of the input ‹xs› from ‹c› within ‹b› nodes, without its
trailing kept tokens, and the nodes left.›
definition rcpct :: ‹('c, 't) rops ⇒ 't list ⇒ 't list ⇒ nat ⇒ nat ⇒ 'c ⇒ ('t × nat) list ⇒
nat × 't rop list option› where
‹rcpct ops ts av b ke c xs = (case rcost (Suc b) ops ts av ke b [(c, xs, 0, [])] [] of
(b', oks) ⇒ (b', case oks of
[] ⇒ None
| nd # nds ⇒ (case rbest ops av (length xs) nd nds of (_, _, _, os) ⇒
(case rev (dropWhile rkept os) of [] ⇒ None | r ⇒ Some r))))›
text ‹The default token of an inserted terminal, as for the error token: a neighbour
with its terminal and span changed. A user's ‹repair_token› ignores the neighbour.›
definition rtoken :: ‹('t, 'ch, 'm) token_scheme ⇒ 't ⇒ 'ch span ⇒ ('t, 'ch, 'm) token_scheme› where
‹rtoken x t s = x⦇tok := t, span := s⦈›
definition rtoken_user :: ‹('t ⇒ 'ch span ⇒ ('t, 'ch, 'm) token_scheme) ⇒
('t, 'ch, 'm) token_scheme ⇒ 't ⇒ 'ch span ⇒ ('t, 'ch, 'm) token_scheme› where
‹rtoken_user f x = f›
text ‹The word from index ‹a› on, under a repair.›
fun rapply :: ‹(('t, 'ch, 'm) token_scheme ⇒ 't ⇒ 'ch span ⇒ ('t, 'ch, 'm) token_scheme) ⇒
('m, 'ch, 't) tword ⇒ nat ⇒ 't rop list ⇒ ('m, 'ch, 't) tword› where
‹rapply mk w a [] = drop a w›
| ‹rapply mk w a (RKeep # os) = (w ! a) # rapply mk w (Suc a) os›
| ‹rapply mk w a (RDel _ # os) = rapply mk w (Suc a) os›
| ‹rapply mk w a (RIns t k # os) =
mk (if a < length w then w ! a else last w) t (rspan w a [] k) # rapply mk w a os›
subsection ‹The rewriter›
text ‹The tokens that must be shifted after an error token before the next error
is reported, as the three tokens of ocamlyacc \<^cite>‹‹Sect.~17.4.4› in "leroy2026-ocaml-manual"›. A stop before that is recovered from in the
same way, but it is taken for a consequence of the last recovery. A repair needs
no such quiet: it succeeded by keeping \<^const>‹rnshifts› tokens or at the end.›
definition rquiet :: nat where ‹rquiet = 3›
text ‹How to recover: the error token, and for repairs the terminals that may not
be inserted without need (‹av›) and the token of an inserted terminal.›
record ('t, 'ch, 'm) rmode =
rm_err :: ‹'t option›
rm_repair :: ‹('t list × (('t, 'ch, 'm) token_scheme ⇒ 't ⇒ 'ch span ⇒ ('t, 'ch, 'm) token_scheme)) option›
text ‹The new word at a stop at index ‹i›, from the configuration ‹c› with the AST
stack ‹tr›, with the index from which errors count again and the nodes left of
‹b›: a repair over the terminals ‹ts›, which the error records, otherwise the
error token if it fits. A repair comes first as it keeps the input, where the error
token drops what it stands for. The empty word has no neighbour to make a token from.›
definition rfix :: ‹('c, 't) rops ⇒ ('t, 'ch, 'm) rmode ⇒ 't list ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒ nat ⇒ 'c ⇒
('m, 'ch, 'n, 't) ast list ⇒ ('n, 't, 'ch, 'm) perr ⇒
('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option› where
‹rfix ops rm ts b w i c tr x =
(if w = [] then (x, None)
else (let (b', r) = (case rm_repair rm of
None ⇒ (b, None)
| Some (av, mk) ⇒ (case rcpct ops ts av b (rcol w (length w)) c (tcols (drop i w)) of
(b', r) ⇒ (b', map_option (Pair mk) r)))
in (case r of
Some (mk, os) ⇒ (x⦇pe_repair := os⦈, Some (take i w @ rapply mk w i os, 0, b'))
| None ⇒ (case Option.bind (rm_err rm) (λe. map_option (Pair e) (rsearch ops e w i i c tr)) of
None ⇒ (x, None)
| Some (e, p) ⇒ (x, Some (rsplice e p w, fst p + 1 + rquiet, b'))))))›
text ‹A stop of the word ‹w› within ‹b› nodes, ‹None› if it is accepted. Each round replaces or
skips the offending token, or inserts tokens that are followed by it, so the
input left at the stop gets shorter; the round stops if it does not (the
trials read one lookahead, as the parser, but where the vector driver has a
conflict they need not agree with it), and there are at most as many rounds as
tokens plus one. The errors are in the order of the input, the first is always
reported, and each index is one of the original word.›
fun rloop :: ‹(nat ⇒ ('m, 'ch, 't) tword ⇒ (('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option) ⇒
nat ⇒ nat ⇒ nat ⇒ nat ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr list ⇒
('n, 't, 'ch, 'm) perr list × ('m, 'ch, 't) tword› where
‹rloop stop 0 left safe n b w es = (rev es, w)›
| ‹rloop stop (Suc f) left safe n b w es = (case stop b w of
None ⇒ (rev es, w)
| Some (x, pl) ⇒
let i = pe_index x;
es' = (if safe ≤ i ∨ es = [] then x⦇pe_index := i + n - length w⦈ # es else es);
left' = length w - i
in (case pl of
Some (w', sf, b') ⇒ if left' < left
then rloop stop f left' sf n b' w' es'
else (rev es', w)
| None ⇒ (rev es', w)))›
definition repair :: ‹(nat ⇒ ('m, 'ch, 't) tword ⇒ (('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option) ⇒
('m, 'ch, 't) tword ⇒ ('n, 't, 'ch, 'm) perr list × ('m, 'ch, 't) tword› where
‹repair stop w = rloop stop (Suc (length w)) (Suc (length w)) 0 (length w) rnodes w []›
text ‹The parser with recovery: a word ‹p› accepts costs what ‹p› costs and gives no
errors. Otherwise ‹p› runs on the rewritten word, and the errors are not empty.›
definition precover :: ‹('w ⇒ 'x option) ⇒ ('w ⇒ 'e list × 'w) ⇒ 'w ⇒ 'e list × 'x option› where
‹precover p rep w = (case p w of
Some x ⇒ ([], Some x)
| None ⇒ (case rep w of
([], _) ⇒ ([], None)
| (e # es, w') ⇒ (e # es, p w')))›
lemma precover_clean:
assumes ‹f ≡ precover p rep› and ‹f w = ([], Some x)›
shows ‹p w = Some x›
using assms by (auto simp: precover_def split: option.splits prod.splits list.splits)
subsection ‹The adapters›
text ‹A stop of the engine: the error, and the plan from the configuration after
the last shift, before the reductions the offending token triggered, as the
trials of the expected terminals. A cycle has no plan.›
definition rstop :: ‹('n, 't, 'ch, 'm) perr ⇒
('c × ('m, 'ch, 'n, 't) ast list ⇒ ('n, 't, 'ch, 'm) perr × ('w × nat × nat) option) ⇒
('c, ('m, 'ch, 'n, 't) ast) dstop option ⇒ (('n, 't, 'ch, 'm) perr × ('w × nat × nat) option) option› where
‹rstop x pl r = (case r of
None ⇒ Some (x, None)
| Some (DDone _) ⇒ None
| Some (DStuck NoAction _ sh) ⇒ Some (pl sh)
| Some (DStuck _ _ _) ⇒ Some (x, None))›
text ‹The layout-free adapter, on the stack of states.›
definition pops :: ‹('n, 't) ptabs ⇒ ('t ⇒ nat) ⇒ (nat list, 't) rops› where
‹pops P f =
⦇ro_adv = λstk x. map_option fst
(dadv (pctl P) (pfinal P) fst (None, 1, 1) (ptrial f stk (Some (fst x)))),
ro_end = λstk. dtrial (pctl P) (pfinal P) fst (None, 1, 1) (ptrial f stk None) = Some True,
ro_pop = λstk. (case stk of _ # y # ys ⇒ Some (y # ys) | _ ⇒ None),
ro_cols = λ_. [],
ro_can = λ_ _. True⦈›
definition prstop :: ‹('n, 't) ptabs ⇒ nat ⇒ ('t ⇒ nat) ⇒ 't list ⇒ ('t, 'ch, 'm) rmode ⇒
nat ⇒ ('m, 'ch, 't) tword ⇒ (('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹prstop P i0 f ts rm b w =
(let r = pdiag_run P i0 f w;
x = dperr pstate snd fst (pexpect P f ts) (length w) r
in rstop x (λsh. rfix (pops P f) rm ts b w (length w - length (snd (fst sh))) (fst (fst sh)) (snd sh) x) r)›
text ‹The set-anchored adapter, over the step at the token type of the trials.›
definition lpop :: ‹('m, 'ch, 'p, 't) lcfg ⇒ ('m, 'ch, 'p, 't) lcfg option› where
‹lpop c = (case c of (((Xs, w), cstk, istk, v), n) ⇒
(case Xs of _ # _ # _ ⇒ Some (((tl Xs, w), tl cstk, tl istk, v), n - 1) | _ ⇒ None))›
definition lops :: ‹(unit, unit, 'p, 'n, 't) astep ⇒ (('p, 't) agconfig ⇒ bool) ⇒
((unit, unit, 'p, 't) lcfg, 't) rops› where
‹lops stp fin =
⦇ro_adv = λc x. dadv (lctl stp) (lfin fin) lkey (None, 1, 1) (ltrial c (Some x)),
ro_end = λc. ltry stp fin c None,
ro_pop = lpop,
ro_cols = lreps,
ro_can = λ_ _. True⦈›
definition lrstop :: ‹('m, 'ch, 'p, 'n, 't) astep ⇒ (unit, unit, 'p, 'n, 't) astep ⇒
(('p, 't) agconfig ⇒ bool) ⇒ 'p aitem list ⇒ 'p aitem list ⇒ nat ⇒ 't list ⇒ ('t, 'ch, 'm) rmode ⇒
nat ⇒ ('m, 'ch, 't) tword ⇒ (('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹lrstop stp stpu fin xin xclos i⇩0 ts rm b w =
(let r = ldiag_run stp fin xin xclos i⇩0 w;
x = ldperr stpu fin ts (length w) r
in rstop x (λsh. rfix (lops stpu fin) rm ts b w (length w - length (linp (fst sh)))
(ltrial (fst sh) None) (snd sh) x) r)›
definition drstop :: ‹('n, 't) is_cfg ⇒ 'n ⇒ (('n, 't) sym × nat) list list ⇒
('n, 't) citem list list ⇒ ('n, 't) lacell list list ⇒ ('n, 't) xitem list ⇒
('n, 't) xitem list ⇒ nat ⇒ 't list ⇒ ('t, 'ch, 'm) rmode ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
(('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹drstop G Shn gt sts redtab xin xclos i⇩0 ts rm b w =
lrstop (dstep_act G gt sts redtab) (dstep_act G gt sts redtab) (gfinal G Shn) xin xclos i⇩0 ts rm b w›
definition srstop :: ‹('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list ⇒ nat ⇒
't list ⇒ ('t, 'ch, 'm) rmode ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
(('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹srstop T kin kcl i⇩0 ts rm b w =
lrstop (sdstep_dact T) (sdstep_dact T) (sgfinal T) kin kcl i⇩0 ts rm b w›
text ‹The vector adapter. Where the run meets a conflict it restarts on the sparse
driver, as the parser does.›
partial_function (option) vadv :: ‹('n, 't) vtab ⇒ vcfg ⇒ vcfg option› where
‹vadv V c = (case c of (fs, w) ⇒ (case fs of [] ⇒ None | (j, av) # _ ⇒
(case vpick_n V c (vcands_n V j av w) of
None ⇒ None
| Some (a, c') ⇒ (case a of VShift ⇒ Some c' | VReduce _ _ _ ⇒ vadv V c'))))›
lemmas vadv_simps [code] = vadv.simps
text ‹The search tries every terminal at every column it tells apart, and on a large grammar
most of these trials fail at all of them. A trial that succeeds has, on the stack of states
alone, a shift of the terminal or a reduction listed for it as lookahead whose goto
exists, and so on down to a shift: ‹vshiftable›, without the columns and the frames, true
when its fuel runs out. It is the \<^const>‹ro_can› of the adapter, checked once per
terminal and node (‹vops_f_can›); ‹vshiftable_s› is the same on states kept in front of
the frames, so the frames are not copied.›
fun vhd :: ‹nat list ⇒ nat option› where
‹vhd [] = None›
| ‹vhd (j # _) = Some j›
fun vshiftable :: ‹('n, 't) vtab ⇒ nat ⇒ nat ⇒ nat list ⇒ bool› where
‹vshiftable V a 0 js = True›
| ‹vshiftable V a (Suc n) js = (case vhd js of None ⇒ False | Some j ⇒
iget (iget (v_sh V) j (IArray [])) a None ≠ None ∨
list_ex (λ(s, b, pr). list_ex (λ(s', _). s' = s) (iget (iget (v_cl V) j (IArray [])) a []) ∧
(let js' = drop (length (snd pr)) js in
case vhd js' of None ⇒ False
| Some j⇩0 ⇒ (case iget (iget (v_go V) j⇩0 (IArray [])) b None of None ⇒ False
| Some e ⇒ vshiftable V a n (fst e # js'))))
(iget (v_cp V) j []))›
fun vhd_s :: ‹nat list ⇒ vframes ⇒ nat option› where
‹vhd_s (j # _) fs = Some j›
| ‹vhd_s [] [] = None›
| ‹vhd_s [] ((j, _) # _) = Some j›
fun vshiftable_s :: ‹('n, 't) vtab ⇒ nat ⇒ nat ⇒ nat list ⇒ vframes ⇒ bool› where
‹vshiftable_s V a 0 js fs = True›
| ‹vshiftable_s V a (Suc n) js fs = (case vhd_s js fs of None ⇒ False | Some j ⇒
iget (iget (v_sh V) j (IArray [])) a None ≠ None ∨
list_ex (λ(s, b, pr). list_ex (λ(s', _). s' = s) (iget (iget (v_cl V) j (IArray [])) a []) ∧
(let m = length (snd pr); js' = drop m js; fs' = (if m ≤ length js then fs else drop (m - length js) fs) in
case vhd_s js' fs' of None ⇒ False
| Some j⇩0 ⇒ (case iget (iget (v_go V) j⇩0 (IArray [])) b None of None ⇒ False
| Some e ⇒ vshiftable_s V a n (fst e # js') fs')))
(iget (v_cp V) j []))›
lemma vhd_s: ‹vhd_s js fs = vhd (js @ map fst fs)›
by (cases js; cases fs) auto
lemma vshiftable_s: ‹vshiftable_s V a n js fs = vshiftable V a n (js @ map fst fs)›
proof (induction n arbitrary: js fs)
case (Suc n)
have d: ‹drop m js @ map fst (if m ≤ length js then fs else drop (m - length js) fs) =
drop m (js @ map fst fs)› for m
by (simp add: drop_map)
show ?case
unfolding vshiftable_s.simps vshiftable.simps Let_def vhd_s Suc.IH append_Cons d ..
qed simp
lemma vpick_n_Some: ‹vpick_n V c acts = Some (act, c') ⟹ act ∈ set acts ∧ vmstep_n V c act = Some c'›
by (induction acts) (auto split: option.splits)
lemma vgo_fst: ‹vgo V e av RA = Some f ⟹ fst f = fst e›
by (auto simp: vgo_def Let_def split: prod.splits if_splits)
lemma vadv_vshiftable:
assumes ‹vadv V (fs, [(a, r)]) = Some c'›
shows ‹vshiftable V a n (map fst fs)›
proof -
have ‹V = V ⟶ (∀fs'. (fs, [(a, r)]) = (fs', [(a, r)]) ⟶ (∀n. vshiftable V a n (map fst fs')))›
proof (rule vadv.raw_induct[OF _ assms, where P = ‹λV' x y. V' = V ⟶
(∀fs. x = (fs, [(a, r)]) ⟶ (∀n. vshiftable V a n (map fst fs)))›], goal_cases)
case (1 adv V' x y)
show ?case
proof (intro impI allI)
fix fs n
assume V': ‹V' = V› and x: ‹x = (fs, [(a, r)])›
show ‹vshiftable V a n (map fst fs)›
proof (cases n)
case (Suc n')
from 1(2) V' x obtain j av fs⇩1 act c⇩1 where fs: ‹fs = (j, av) # fs⇩1›
and pk: ‹vpick_n V x (vcands_n V j av [(a, r)]) = Some (act, c⇩1)›
and rest: ‹(case act of VShift ⇒ Some c⇩1 | VReduce _ _ _ ⇒ adv V c⇩1) = Some y›
by (auto split: list.splits option.splits prod.splits)
from vpick_n_Some[OF pk] have mem: ‹act ∈ set (vcands_n V j av [(a, r)])›
and st: ‹vmstep_n V x act = Some c⇩1› by auto
show ?thesis
proof (cases act)
case VShift
with st x fs show ?thesis
by (auto simp: Suc vmstep_n_def split: option.splits)
next
case (VReduce s b pr)
from mem VReduce obtain τ where cp: ‹(s, b, pr) ∈ set (iget (v_cp V) j [])›
and cl: ‹(s, τ) ∈ set (iget (iget (v_cl V) j (IArray [])) a [])›
by (auto simp: vcands_n_def vlic_n_def Let_def list_ex_iff)
have h: ‹(case drop (length (snd pr)) fs of [] ⇒ None
| (j⇩0, av⇩0) # _ ⇒ (case iget (iget (v_go V) j⇩0 (IArray [])) b None of None ⇒ None
| Some e ⇒ map_option (λf. (f # drop (length (snd pr)) fs, [(a, r)])) (vgo V e av⇩0 (getR av s)))) =
Some c⇩1›
using st unfolding x VReduce vmstep_n_def Let_def fs by simp
obtain j⇩0 av⇩0 fs⇩0 where dr: ‹drop (length (snd pr)) fs = (j⇩0, av⇩0) # fs⇩0›
using h by (cases ‹drop (length (snd pr)) fs›) auto
obtain e where go: ‹iget (iget (v_go V) j⇩0 (IArray [])) b None = Some e›
using h dr by (auto split: option.splits)
obtain f where g: ‹vgo V e av⇩0 (getR av s) = Some f›
and c1: ‹c⇩1 = (f # (j⇩0, av⇩0) # fs⇩0, [(a, r)])›
using h dr go by auto
from rest VReduce have ‹adv V c⇩1 = Some y› by simp
from 1(1)[OF this] c1 have ‹vshiftable V a n' (map fst (f # (j⇩0, av⇩0) # fs⇩0))› by blast
then have ih: ‹vshiftable V a n' (fst e # j⇩0 # map fst fs⇩0)›
using vgo_fst[OF g] by simp
have dm: ‹drop (length (snd pr)) (map fst fs) = j⇩0 # map fst fs⇩0›
using dr by (simp add: drop_map)
have mf: ‹map fst fs = j # map fst fs⇩1› by (simp add: fs)
show ?thesis
unfolding Suc vshiftable.simps mf[symmetric]
using cp cl go ih dm mf by (fastforce simp: list_ex_iff Let_def)
qed
qed simp
qed
qed
then show ?thesis by simp
qed
lemma vadv_None: ‹¬ vshiftable V a n (map fst fs) ⟹ vadv V (fs, [(a, r)]) = None›
using vadv_vshiftable by fastforce
definition vops :: ‹('n, 't) vtab ⇒ (vcfg, 't) rops› where
‹vops V =
⦇ro_adv = λc x. vadv V (fst c, [(vnum V (fst x), snd x)]),
ro_end = λc. vtry V c None,
ro_pop = λc. (case fst c of _ # g # gs ⇒ Some (g # gs, snd c) | _ ⇒ None),
ro_cols = λc. col_reps (concat (map (λ(j, av). concat (map irep_ends av)) (fst c))),
ro_can = λc t. vshiftable_s V (vnum V t) 32 [] (fst c)⦈›
definition vrstop :: ‹('n, 't) vtab ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒ ('n, 't) sitem list ⇒
nat ⇒ 't list ⇒ ('t, 'ch, 'm) rmode ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
(('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹vrstop V T kin kcl i⇩0 ts rm b w =
(let st = ([v_av0 V], vtcols V w, w, [])
in (case vdrun V st st of
Some (VDone _) ⇒ None
| Some (VStuck s sh) ⇒ (case sh of (fs, u, v, tstk) ⇒
Some (rfix (vops V) rm ts b w (length w - length v) (fs, []) tstk
(vperr V ts (length w) s sh)))
| _ ⇒ srstop T kin kcl i⇩0 ts rm b w))›
text ‹The same with the tokens numbered by ‹f›, as \<^const>‹vkdiag_f›: the search
numbers a token at every step it tries, and the stop the whole word per round.›
definition vops_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ (vcfg, 't) rops› where
‹vops_f V f =
⦇ro_adv = λc x. vadv V (fst c, [(f (fst x), snd x)]),
ro_end = λc. vtry_f V f c None,
ro_pop = λc. (case fst c of _ # g # gs ⇒ Some (g # gs, snd c) | _ ⇒ None),
ro_cols = λc. col_reps (concat (map (λ(j, av). concat (map irep_ends av)) (fst c))),
ro_can = λc t. vshiftable_s V (f t) 32 [] (fst c)⦈›
definition vrstop_f :: ‹('n, 't) vtab ⇒ ('t ⇒ nat) ⇒ ('n, 't) stab ⇒ ('n, 't) sitem list ⇒
('n, 't) sitem list ⇒ nat ⇒ 't list ⇒ ('t, 'ch, 'm) rmode ⇒ nat ⇒ ('m, 'ch, 't) tword ⇒
(('n, 't, 'ch, 'm) perr × (('m, 'ch, 't) tword × nat × nat) option) option› where
‹vrstop_f V f T kin kcl i⇩0 ts rm b w =
(let st = ([v_av0 V], vtnum f w, w, [])
in (case vdrun V st st of
Some (VDone _) ⇒ None
| Some (VStuck s sh) ⇒ (case sh of (fs, u, v, tstk) ⇒
Some (rfix (vops_f V f) rm ts b w (length w - length v) (fs, []) tstk
(vperr_f V f ts (length w) s sh)))
| _ ⇒ srstop T kin kcl i⇩0 ts rm b w))›
lemma vops_f_vnum: ‹vops_f V (vnum V) = vops V›
by (simp add: vops_f_def vops_def vtry_f_vnum)
lemma vops_f_can: ‹¬ ro_can (vops_f V f) c t ⟹ ro_adv (vops_f V f) c (t, r) = None›
by (simp add: vops_f_def vshiftable_s vadv_None)
lemma vrstop_f_eq: ‹vnum V = f ⟹ vrstop V = vrstop_f V f›
by (hypsubst, unfold vrstop_f_def vrstop_def vops_f_vnum vperr_f_vnum vtcols_vtnum) (rule refl)
subsection ‹The diagnostics of a grammar with error productions›
text ‹The error token is not offered to the user: it is left out of the candidates
for the expected terminals, and the messages summarise them over the grammar
without the productions that use it.›
definition no_err :: ‹'t ⇒ ('n, 't) is_cfg ⇒ ('n, 't) is_cfg› where
‹no_err e G = G⦇iprods := filter (λ(A, rhs). Tm e ∉ fst ` set rhs) (iprods G)⦈›
subsection ‹Trees without error nodes›
text ‹The terminals at the leaves of a tree. An error node is a node with a leaf of
the error token.›
fun atoks :: ‹('m, 'ch, 'n, 't) ast ⇒ 't list› where
‹atoks (Leaf x) = [tok x]›
| ‹atoks (Node n ts) = concat (map atoks ts)›
lemma atoks_erase: ‹atoks (erase pt) = map tok (pyield pt)›
by (induction pt) (simp_all add: map_concat comp_def cong: map_cong)
lemma recover_no_error_generic:
assumes body: ‹parse_fn = (λw. Option.bind (dparse G Shn w) dec)›
and fn: ‹fresh_name G Shn›
and rec: ‹parse_fn w = Some x›
and none: ‹∀y ∈ set w. tok y ≠ e›
shows ‹∃t. dec t = Some x ∧ ast_of G (Nt (istart G)) (istart_ind G) t w ∧ e ∉ set (atoks t)›
proof -
from rec body obtain t where p: ‹dparse G Shn w = Some t› and d: ‹dec t = Some x›
by (auto simp: bind_eq_Some_conv)
from dparse_sound_ast[OF fn p] have a: ‹ast_of G (Nt (istart G)) (istart_ind G) t w› .
then obtain pt where ‹erase pt = t› ‹pyield pt = w›
unfolding ast_of_def by blast
with atoks_erase[of pt] none have ‹e ∉ set (atoks t)› by auto
with a d show ?thesis by blast
qed
end