Theory Compose_Tests

(* Author: Basil Fürer *)

theory Compose_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

section ‹Composition by reference›

text ‹A grammar may use a nonterminal ‹a.X› of an earlier grammar ‹a›. The productions
  of ‹a› reachable from ‹X› are copied under the names ‹a.Y›, so the new grammar is
  closed and goes through the same definitions as any other. With ‹(relation)› on both,
  ‹b.a_X_iff› links the copied relation to the original one.›

fun toks :: ‹nat ⇒ 'tok list ⇒ ('tok, unit) token list› where
  ‹toks i [] = []›
| ‹toks i (x # xs) = ⦇tok = x, span = span.make 0 i i 1 []⦈ # toks (Suc (Suc i)) xs›

datatype c_tok = CNum | CPlus | CStar | CLP | CRP | CSemi | CLB | CRB

datatype ex = N | Add ex ex | Mul ex ex

subsection ‹Two layers›

grammar (relation) cexp =
  tokens ‹c_tok›
  terminals "+" = ‹CPlus› and "*" = ‹CStar› and "(" = ‹CLP› and ")" = ‹CRP›
  productions
    E :: ‹ex› = E "+" T ⇒ ‹Add› | T
  and
    T :: ‹ex› = T "*" F ⇒ ‹Mul› | F
  and
    F :: ‹ex› = CNum ⇒ ‹λ_. N› | "(" E ")"

grammar (relation) cstm =
  tokens ‹c_tok›
  terminals ";" = ‹CSemi›
  productions
    S :: ‹ex list› = cexp.E ⇒ ‹λe. [e]› | S ";" cexp.E ⇒ ‹λs e. s @ [e]›

text ‹The productions are those of ‹cstm›, then those of ‹cexp› under the new names, in
  the order of ‹cexp›.›

lemma ‹cstm =
  is_cfg.make
   [(''S'', [(Nt ''cexp.E'', Any)]),
    (''S'', [(Nt ''S'', Any), (Tm CSemi, Any), (Nt ''cexp.E'', Any)]),
    (''cexp.E'', [(Nt ''cexp.E'', Any), (Tm CPlus, Any), (Nt ''cexp.T'', Any)]),
    (''cexp.E'', [(Nt ''cexp.T'', Any)]),
    (''cexp.T'', [(Nt ''cexp.T'', Any), (Tm CStar, Any), (Nt ''cexp.F'', Any)]),
    (''cexp.T'', [(Nt ''cexp.F'', Any)]),
    (''cexp.F'', [(Tm CNum, Any)]),
    (''cexp.F'', [(Tm CLP, Any), (Nt ''cexp.E'', Any), (Tm CRP, Any)])]
   ''S'' 0›
  by (simp only: cstm_def)

ML ‹val _ = @{thms cstm.cexp_E_iff}›

lemma ‹cstm_cexp_E w x ⟷ cexp_E w x›
  by (fact cstm.cexp_E_iff)

parser cstm_parse for cstm and cstm_parse_e for cstm (cexp.E)

parser_check ‹cstm_parse (toks 0 [CNum, CPlus, CNum, CSemi, CNum, CStar, CNum]) =
  Some [Add N N, Mul N N]›

parser_check ‹cstm_parse_e (toks 0 [CLP, CNum, CPlus, CNum, CRP, CStar, CNum]) =
  Some (Mul (Add N N) N)›

text ‹What the entry of the copy proves is a fact about the original grammar.›

lemma ‹cstm_parse_e w = Some x ⟹ cexp_E w x›
  using cstm_parse_e.sound cstm.cexp_E_iff by blast

lemma ‹cexp_E w x ⟹ cstm_parse_e w = Some x›
  using cstm_parse_e.complete cstm.cexp_E_iff by blast

subsection ‹A copy of a copy; one nonterminal along two paths›

text ‹‹cblk› uses ‹cstm.S›, which uses ‹cexp.E›, and ‹cexp.E› directly: ‹cexp.E›,
  ‹cexp.T›, ‹cexp.F› are copied once. ‹"("› is not declared here: the spellings of
  the copied productions' terminals come with them.›

grammar (relation) cblk =
  tokens ‹c_tok›
  terminals "{" = ‹CLB› and "}" = ‹CRB›
  productions
    B :: ‹ex list›
      = "{" cstm.S "}"
      | "(" cexp.E ")" ⇒ ‹λe. [e]›

lemma ‹cblk =
  is_cfg.make
   [(''B'', [(Tm CLB, Any), (Nt ''cstm.S'', Any), (Tm CRB, Any)]),
    (''B'', [(Tm CLP, Any), (Nt ''cexp.E'', Any), (Tm CRP, Any)]),
    (''cstm.S'', [(Nt ''cexp.E'', Any)]),
    (''cstm.S'', [(Nt ''cstm.S'', Any), (Tm CSemi, Any), (Nt ''cexp.E'', Any)]),
    (''cexp.E'', [(Nt ''cexp.E'', Any), (Tm CPlus, Any), (Nt ''cexp.T'', Any)]),
    (''cexp.E'', [(Nt ''cexp.T'', Any)]),
    (''cexp.T'', [(Nt ''cexp.T'', Any), (Tm CStar, Any), (Nt ''cexp.F'', Any)]),
    (''cexp.T'', [(Nt ''cexp.F'', Any)]),
    (''cexp.F'', [(Tm CNum, Any)]),
    (''cexp.F'', [(Tm CLP, Any), (Nt ''cexp.E'', Any), (Tm CRP, Any)])]
   ''B'' 0›
  by (simp only: cblk_def)

lemma
  ‹cblk_cstm_S w x ⟷ cstm_S w x›
  ‹cblk_cexp_E w y ⟷ cexp_E w y›
  by (fact cblk.cstm_S_iff cblk.cexp_E_iff)+

parser cblk_parse for cblk

parser_check ‹cblk_parse (toks 0 [CLB, CNum, CSemi, CLP, CNum, CPlus, CNum, CRP, CRB]) =
  Some [N, Add N N]›

subsection ‹Precedence declarations travel with the copied productions›

grammar pexp =
  tokens ‹c_tok›
  terminals "+" = ‹CPlus› and "*" = ‹CStar› and "(" = ‹CLP› and ")" = ‹CRP›
  precedence left "*" > left "+"
  productions
    E :: ‹ex›
      = E "+" E ⇒ ‹Add›
      | E "*" E ⇒ ‹Mul›
      | CNum ⇒ ‹λ_. N›
      | "(" E ")"

text ‹‹puse› declares nothing; the levels of ‹pexp› apply to its copy of ‹pexp.E›.›

grammar puse =
  tokens ‹c_tok›
  terminals "{" = ‹CLB› and "}" = ‹CRB›
  productions
    P :: ‹ex› = "{" pexp.E "}"

ML ‹
  val (_, gr) = Grammar_Common.check_grammar context ("puse", Position.none);
  assert (#prec gr = SOME {chains = [[("left", [(1, false)]), ("left", [(2, false)])]],
    forbids = []})
›

parser puse_parse for puse

parser_check ‹puse_parse (toks 0 [CLB, CNum, CPlus, CNum, CStar, CNum, CRB]) = Some (Add N (Mul N N))›

parser_check ‹puse_parse (toks 0 [CLB, CNum, CStar, CNum, CPlus, CNum, CRB]) = Some (Add (Mul N N) N)›

parser_check ‹puse_parse (toks 0 [CLB, CNum, CPlus, CNum, CPlus, CNum, CRB]) = Some (Add (Add N N) N)›

subsection ‹Layout: the copy keeps its annotations, the link keeps the indentation›

datatype l_tok = LDo | LId | LSemi

grammar (relation) ldo =
  tokens ‹l_tok›
  terminals "do" = ‹LDo›
  productions
      Expr :: ‹nat›
        = LId⇧>          ⇒ ‹λ_. 0›
        | "do"⇧> Stmts⇧> ⇒ ‹λn. n›
    and
      Stmts :: ‹nat›
        = Stmt⇧=          ⇒ ‹λ_. 1›
        | Stmts⇧= Stmt⇧= ⇒ ‹λn _. Suc n›
    and
      Stmt :: ‹nat›
        = LId⇧=          ⇒ ‹λ_. 0›
        | "do"⇧= Stmts⇧> ⇒ ‹λn. n›

grammar (relation) lmain =
  tokens ‹l_tok›
  terminals ";" = ‹LSemi›
  productions
    M :: ‹nat list› = ldo.Expr⇧≥ ⇒ ‹λn. [n]› | M ";" ldo.Expr⇧≥ ⇒ ‹λms n. ms @ [n]›

lemma ‹lmain_ldo_Expr i w x ⟷ ldo_Expr i w x›
  by (fact lmain.ldo_Expr_iff)

parser lmain_parse for lmain

definition lt :: ‹nat ⇒ l_tok ⇒ (l_tok, unit) token› where
  ‹lt c x = ⦇tok = x, span = span.make 0 c 0 1 []⦈›

parser_check ‹lmain_parse [lt 1 LDo, lt 4 LId, lt 4 LId, lt 4 LSemi, lt 6 LId] = Some [2, 0]›

parser_check ‹lmain_parse [lt 1 LDo, lt 4 LId, lt 5 LId] = None›

subsection ‹Bare names: ‹open››

text ‹Under ‹open a›, a bare name that no local nonterminal or terminal class claims and
  that ‹a› defines is ‹a›'s: ‹copen› is ‹cstm› written without qualifiers.›

grammar copen = open cexp
  tokens ‹c_tok›
  terminals ";" = ‹CSemi›
  productions
    S :: ‹ex list› = E ⇒ ‹λe. [e]› | S ";" E ⇒ ‹λs e. s @ [e]›

lemma ‹copen =
  is_cfg.make
   [(''S'', [(Nt ''cexp.E'', Any)]),
    (''S'', [(Nt ''S'', Any), (Tm CSemi, Any), (Nt ''cexp.E'', Any)]),
    (''cexp.E'', [(Nt ''cexp.E'', Any), (Tm CPlus, Any), (Nt ''cexp.T'', Any)]),
    (''cexp.E'', [(Nt ''cexp.T'', Any)]),
    (''cexp.T'', [(Nt ''cexp.T'', Any), (Tm CStar, Any), (Nt ''cexp.F'', Any)]),
    (''cexp.T'', [(Nt ''cexp.F'', Any)]),
    (''cexp.F'', [(Tm CNum, Any)]),
    (''cexp.F'', [(Tm CLP, Any), (Nt ''cexp.E'', Any), (Tm CRP, Any)])]
   ''S'' 0›
  by (simp only: copen_def)

text ‹A local nonterminal comes first: ‹E› here is ‹cshadow›'s own, ‹T› is
  ‹cexp.T›; and ‹X+› over an opened name is one instance with ‹cexp.T+›.›

grammar cshadow = open cexp
  tokens ‹c_tok›
  terminals ";" = ‹CSemi›
  productions
    E :: ‹ex list› = T+ | ";" cexp.T+

lemma ‹cshadow =
  is_cfg.make
   [(''E'', [(Nt ''cexp.T+'', Any)]),
    (''E'', [(Tm CSemi, Any), (Nt ''cexp.T+'', Any)]),
    (''cexp.T+'', [(Nt ''cexp.T'', Any)]),
    (''cexp.T+'', [(Nt ''cexp.T+'', Any), (Nt ''cexp.T'', Any)]),
    (''cexp.T'', [(Nt ''cexp.T'', Any), (Tm CStar, Any), (Nt ''cexp.F'', Any)]),
    (''cexp.T'', [(Nt ''cexp.F'', Any)]),
    (''cexp.F'', [(Tm CNum, Any)]),
    (''cexp.F'', [(Tm CLP, Any), (Nt ''cexp.E'', Any), (Tm CRP, Any)]),
    (''cexp.E'', [(Nt ''cexp.E'', Any), (Tm CPlus, Any), (Nt ''cexp.T'', Any)]),
    (''cexp.E'', [(Nt ''cexp.T'', Any)])]
   ''E'' 0›
  by (simp only: cshadow_def)

subsection ‹Messages name a copy without its grammar›

text ‹‹cexp.T› shows as ‹T›. Where a local nonterminal and a copy would show alike, as
  ‹E› and ‹cexp.E› in ‹cshadow›, the copy keeps its qualifier.›

parser (diagnostics) cshadow_diag for cshadow

parser_check ‹(case cshadow_diag_diag (toks 0 [CLP, CNum, CNum]) of
    Inl e ⇒ pmsg_lines (perr_message cshadow_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:4: syntax error at '' @ squote ''CNum'',
   ''  expected: '' @ squote ''*'' @ '', '' @ squote '')'' @ '' or '' @ squote ''+'',
   ''  up to here: a T was recognised'']›
ML ‹
  assert (Grammar_Common.display_names context ["S", unchecked_name‹cexp.E›, unchecked_name‹cexp.T›, "cexp.T+"] =
    [(unchecked_name‹cexp.E›, "E"), (unchecked_name‹cexp.T›, "T"), ("cexp.T+", "T+")]);
  assert (Grammar_Common.display_names context ["E", unchecked_name‹cexp.E›, unchecked_name‹cexp.T›, "Q(cexp.T, \";\")"] =
    [(unchecked_name‹cexp.T›, "T"), ("Q(cexp.T, \";\")", "Q(T, \";\")")]);
›

subsection ‹Numbered nonterminals: ‹grammar_nat_labels››

text ‹Under ‹[[grammar_nat_labels]]› a nonterminal is a number in HOL, in the order of
  ‹#no›: the grammar's own in their order, then the copies. The numbers skip 1, which
  the simplifier would turn into ‹Suc 0›. Everything else is as with names,
  and messages still show the names.›

declare [[grammar_nat_labels]]

grammar (relation) nstm = open cexp
  tokens ‹c_tok›
  terminals ";" = ‹CSemi›
  productions
    S :: ‹ex list› = E ⇒ ‹λe. [e]› | S ";" E ⇒ ‹λs e. s @ [e]›

lemma ‹nstm =
  is_cfg.make
   [(0, [(Nt 2, Any)]),
    (0, [(Nt 0, Any), (Tm CSemi, Any), (Nt 2, Any)]),
    (2, [(Nt 2, Any), (Tm CPlus, Any), (Nt 3, Any)]),
    (2, [(Nt 3, Any)]),
    (3, [(Nt 3, Any), (Tm CStar, Any), (Nt 4, Any)]),
    (3, [(Nt 4, Any)]),
    (4, [(Tm CNum, Any)]),
    (4, [(Tm CLP, Any), (Nt 2, Any), (Tm CRP, Any)])]
   0 0›
  by (simp only: nstm_def)

lemma ‹nstm_cexp_E w x ⟷ cexp_E w x›
  by (fact nstm.cexp_E_iff)

parser nstm_parse for nstm and nstm_parse_e for nstm (cexp.E)

parser_check ‹nstm_parse (toks 0 [CNum, CPlus, CNum, CSemi, CNum, CStar, CNum]) =
  Some [Add N N, Mul N N]›

parser_check ‹nstm_parse_e (toks 0 [CLP, CNum, CPlus, CNum, CRP, CStar, CNum]) =
  Some (Mul (Add N N) N)›

lemma ‹nstm_parse w = Some x ⟹ nstm_S w x› ‹nstm_S w x ⟹ nstm_parse w = Some x›
  by (fact nstm_parse.sound nstm_parse.complete)+

lemma ‹nstm_parse_e w = Some x ⟹ cexp_E w x›
  using nstm_parse_e.sound nstm.cexp_E_iff by blast

parser (diagnostics) nstm_diag for nstm

parser_check ‹(case nstm_diag_diag (toks 0 [CLP, CNum, CNum]) of
    Inl e ⇒ pmsg_lines (perr_message nstm_diag_info (λ_. []) e) | Inr _ ⇒ []) =
  [''0:4: syntax error at '' @ squote ''CNum'',
   ''  expected: '' @ squote ''+'' @ '', '' @ squote ''*'' @ '' or '' @ squote '')'']›

text ‹The messages name the nonterminals, not their numbers.›

parser_check ‹map (pi_nt nstm_diag_info) [0, 2, 3, 4] = [''S'', ''E'', ''T'', ''F'']›

text ‹Under layout.›

grammar (relation) nlay = open ldo
  tokens ‹l_tok›
  terminals ";" = ‹LSemi›
  productions
    M :: ‹nat list› = Expr⇧≥ ⇒ ‹λn. [n]› | M ";" Expr⇧≥ ⇒ ‹λms n. ms @ [n]›

parser nlay_parse for nlay

parser_check ‹nlay_parse [lt 1 LDo, lt 4 LId, lt 4 LId, lt 4 LSemi, lt 6 LId] = Some [2, 0]›

lemma ‹nlay_parse w = Some x ⟹ nlay_M 0 w x›
  by (fact nlay_parse.sound)

declare [[grammar_nat_labels = false]]

subsection ‹Errors›

ML ‹
fun command_error src =
  let val thy = theory in
    (fold Toplevel.command_exception (Outer_Syntax.parse_text thy (K {skip_theory = false, theory = thy}) Position.none src)
       (Toplevel.make_state (SOME (Context.Theory thy))); NONE)
    handle Runtime.EXCURSION_FAIL (exn, _) => SOME (Runtime.exn_message exn)
  end;

fun rejected frag src =
  (case command_error src of
    NONE => error ("accepted: " ^ src)
  | SOME msg =>
      if String.isSubstring frag msg then () else error ("unexpected: " ^ msg));
›

ML ‹
  val _ = assert (is_none (command_error
    "grammar ok = tokens c_tok productions X :: ex = cexp.E ⇒ ‹λe. e›"));
  val _ = rejected "has no nonterminal \"Q\""
    "grammar bad = tokens c_tok productions X :: ex = cexp.Q ⇒ ‹λe. e›";
  val _ = rejected "has the token type"
    "grammar bad = productions X :: ex = cexp.E ⇒ ‹λe. e›";
  val _ = rejected "a defined nonterminal has a plain name"
    "grammar bad = tokens c_tok productions a.X :: ex = cexp.E ⇒ ‹λe. e›";
  val _ = rejected "have one name \"cexp_E\""
    "grammar bad = tokens c_tok productions cexp_E :: ex = cexp.E ⇒ ‹λe. e›";
  val _ = rejected "The spelling \"+\""
    "grammar bad = tokens c_tok terminals \"+\" = CStar productions X :: ex = cexp.E ⇒ ‹λe. e›";
  val _ = rejected "is defined by the opened grammars \"cexp\", \"pexp\""
    "grammar bad = open cexp pexp tokens c_tok productions X :: ex = E ⇒ ‹λe. e›";
  val _ = rejected "is opened twice"
    "grammar bad = open cexp cexp tokens c_tok productions X :: ex = E ⇒ ‹λe. e›";
  val _ = rejected "Carrier inference"
    "grammar bad = tokens c_tok productions X :: ‹ex list› = cexp.E ⇒ ‹λe. Add e›";
›

end