Theory Reach_Tests
theory Reach_Tests
imports TIGER_Grammar.LR_Parser Parser_Check
begin
section ‹Coverage of the error states›
text ‹Sentences of the driver against 🗏‹../lr_reach.ML›: every word over the
terminals up to a length, cut at the first error, gives the same pairs of a state and
a terminal and the same shortest lengths as the engine.›
declare [[parser_errors_budget = 120]]
ML ‹
fun coverage_of ctxt name =
let
val cov = the (LR_Backend.get_coverage ctxt name);
val ((view, driver), _) = LR_Backend.evaluate_coverage ctxt (#coverage cov) [];
in (cov, view, driver) end;
fun brute ctxt name len =
let
val (cov, view, driver) = coverage_of ctxt name;
val hide = #hide cov;
val (v, _, _) = LR_Backend.dest_view view;
val nt = #nterms v;
val r = LR_Reach.run {hide = hide, seconds = 30.0} v;
fun key (s, z) = s * (nt + 1) + z;
fun enc w = maps (fn t => [t, 0]) (rev w);
val toks = filter (fn t => SOME t <> hide) (0 upto nt - 1);
val seen = Unsynchronized.ref Inttab.empty;
fun note k d = seen := Inttab.map_default (k, d) (fn e => Int.min (e, d)) (!seen);
fun step w =
(case driver (enc w) of
[] => true
| st :: tk :: _ :: idx :: _ => (note (key (st, tk)) idx; tk = nt)
| _ => raise Fail "driver");
fun layer n fr =
if n > len orelse null fr then ()
else
let val alive = filter step fr
in layer (n + 1) (if n = len then [] else maps (fn w => map (fn t => t :: w) toks) alive) end;
val _ = layer 0 [[]];
val eng = Inttab.make (map (fn {state, look, dist, ...} => (key (state, look), dist)) (#errors r));
val seen = Inttab.dest (!seen);
val missing = filter_out (Inttab.defined eng o fst) seen;
val wrong = filter (fn (k, d) => Inttab.lookup eng k <> SOME d andalso Inttab.defined eng k) seen;
val extra =
filter (fn {state, look, dist, ...} =>
(if look = nt then dist <= len else dist < len) andalso
not (AList.defined (op =) seen (key (state, look)))) (#errors r);
val _ = \<^assert> (#complete r andalso null missing andalso null wrong andalso null extra);
in (length (#errors r), #facts r) end;
›