Theory Regression_Tests
theory Regression_Tests
imports TIGER_Grammar.LR_Parser Parser_Check
begin
section ‹Command-level regression tests›
definition tu :: ‹nat ⇒ 'tok ⇒ char list ⇒ ('tok, unit) token› where
‹tu i x u = ⦇tok = x, span = span.make 0 i 0 (length u) []⦈›
subsection ‹Aligned ‹do› blocks: unconditional completeness + layout›
datatype do_tok = DDo | DId
grammar (relation) do =
tokens ‹do_tok›
terminals "do" = ‹DDo›
productions
Expr :: ‹unit›
= DId⇧> ⇒ ‹λ_. ()›
| "do"⇧> BStmts⇧> ⇒ ‹λ_. ()›
and
BStmts :: ‹unit›
= BExpr⇧= ⇒ ‹λ_. ()›
| BStmts⇧= BExpr⇧= ⇒ ‹λ_ _. ()›
and
BExpr :: ‹unit›
= DId⇧= ⇒ ‹λ_. ()›
| "do"⇧= BStmts⇧> ⇒ ‹λ_. ()›
parser do_parse2 for do
text ‹Accepted and rejected layouts of \<^cite>‹‹Sect.~5.7› in "adams2013"›.›
parser_check ‹do_parse2 [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x''] = Some ()›
parser_check ‹do_parse2
[tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 2 DId ''y''] = None›
parser_check ‹do_parse2
[tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 4 DId ''y''] = Some ()›
parser_check ‹do_parse2
[tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 7 DId ''y''] = Some ()›
text ‹ The emitted theorems are hypothesis-free: no mentions of \<^const>‹mdet› or \<^const>‹fresh_name›.›
lemma ‹w ∈ ilang do ⟹ ∃x. do_parse2 w = Some x›
by (fact do_parse2.complete_lang)
text ‹With ‹(relation)›, ‹.sound› / ‹.complete› are stated against the
relation of the start symbol, also hypothesis-free: the accept/reduce
check \<^const>‹acc_conflicts› is empty as well.›
lemma ‹do_parse2 w = Some x ⟹ do_Expr 0 w x›
by (fact do_parse2.sound)
lemma ‹do_Expr 0 w x ⟹ do_parse2 w = Some x›
by (fact do_parse2.complete)
subsection ‹The accept/reduce check: a cycle through the start symbol›
text ‹\<^const>‹mdet› alone does not make the relational ‹.complete› true: the
conflict report ignores the start production, so a grammar with
‹S ⇒⁺ S› passes it, while the relation assigns two values to one word
and the driver returns the first parse. \<^const>‹acc_conflicts› must be
non-empty here, and the command keeps it as an assumption (expected
warning).›
grammar (relation) cyc =
tokens ‹do_tok›
productions
S :: ‹nat› = A ⇒ ‹λa. a + 1› | DId ⇒ ‹λ_. 0›
and
A :: ‹nat› = S ⇒ ‹λs. s›
parser cyc_parse for cyc
text ‹The code equation runs on the action table over the states, and
numbers the tokens by a case distinction.›
ML ‹val _ = \<^const_name>‹cyc_parse_ptabs››
parser_check ‹cyc_parse_tnum DId = pnum cyc_parse_ptabs DId›
parser_check ‹acc_conflicts cyc ''!'' ≠ []›
parser_check ‹map (λ(_, prs, _, _). prs) (explain_acc cyc ''!'' (acc_conflicts cyc ''!'')) = [[2]]›
lemma cyc_two_values:
‹cyc_S [tu 1 DId ''x''] 0› ‹cyc_S [tu 1 DId ''x''] 1›
proof -
show 0: ‹cyc_S [tu 1 DId ''x''] 0› unfolding tu_def by (intro cyc.intros)
have ‹cyc_S [tu 1 DId ''x''] (0 + 1)› by (intro cyc.intros 0)
then show ‹cyc_S [tu 1 DId ''x''] 1› by simp
qed
parser_check ‹cyc_parse [tu 1 DId ''x''] = Some 0›
text ‹So ‹cyc_S w x ⟹ cyc_parse w = Some x› is false, and ‹.complete› still
carries the check as a hypothesis:›
lemma ‹acc_conflicts cyc ''!'' = [] ⟹ cyc_S w x ⟹ cyc_parse w = Some x›
by (fact cyc_parse.complete)
text ‹The simple driver on integer indices (‹parser_int_tables›): the same
parser, whose code equation runs on the integer tables ‹cyc_parse_int_ztabs›.›
declare [[parser_int_tables]]
parser cyc_parse_int for cyc
declare [[parser_int_tables = false]]
ML ‹val _ = \<^const_name>‹cyc_parse_int_ztabs››
parser_check ‹cyc_parse_int [tu 1 DId ''x''] = Some 0› ‹cyc_parse_int [tu 1 DDo ''do''] = None›
text ‹The simple driver on evaluated tables (‹parser_literal_tables›): the start
state and the action table its code equation names are literals, so that exported
code computes no table when it loads. Without diagnostics both come with the checks.›
declare [[parser_literal_tables]]
parser cyc_parse_lit for cyc
parser (no_diagnostics) cyc_parse_lit_nd for cyc
declare [[parser_literal_tables = false]]
ML ‹
\<^assert> (forall (fn th => not (exists_Const (fn (c, _) =>
member (op =) [\<^const_name>‹ptabs_of›, \<^const_name>‹st_find›] c) (Thm.prop_of th)))
@{thms cyc_parse_lit_ptabs_def cyc_parse_lit_i0_def
cyc_parse_lit_nd_ptabs_def cyc_parse_lit_nd_i0_def})
›
parser_check ‹cyc_parse_lit [tu 1 DId ''x''] = Some 0› ‹cyc_parse_lit [tu 1 DDo ''do''] = None›
‹cyc_parse_lit_nd [tu 1 DId ''x''] = Some 0› ‹cyc_parse_lit_nd [tu 1 DDo ''do''] = None›
subsection ‹The rejection path: an ambiguous grammar keeps ‹mdet››
text ‹The ISWIM productions of \<^cite>‹‹Fig.~2› in "adams2013"›, with ‹WExpr›
for the desugared ‹|expr|›. They apply Landin's offside rule
\<^cite>‹‹Sect.~6, item~(4c)› in "landin1966-next-700"› to the right-hand side of
‹where› only.›