Theory Ast_Tests

(* Author: Basil Fürer *)

theory Ast_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

section ‹⬚‹parser (ast)›: the tree, no decoder›

text ‹⬚‹parser (ast) p for G› returns the tree of const‹dparse› and ignores the
  actions: ‹p.sound› says the tree is the erasure of a parse tree of the word,
  ‹p.complete› that the erasure of every parse tree is returned for its yield.›

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›

text ‹A token at a line and a column.›

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

datatype a_tok = AId | APlus | AStar | ANum | AKw | AErr

text ‹The tree without the token records, for the checks.›

datatype ('n, 't) tr = TL 't | TN 'n ‹('n, 't) tr list›

fun shape :: ‹('m, 'ch, 'n, 't) ast ⇒ ('n, 't) tr› where
  ‹shape (Leaf x) = TL (tok x)›
| ‹shape (Node n ts) = TN n (map shape ts)›

ML ‹
  (* the premises of a theorem, but for the ones of the grammar *)
  fun nprems ctxt name = Thm.nprems_of (Proof_Context.get_thm ctxt name);
›


subsection ‹Layout-free›

text ‹With a relation, which ‹(ast)› does not read, and an entry.›

grammar (relation) ae =
  tokens ‹a_tok›
  terminals "+" = ‹APlus›
  productions
    E :: ‹nat› = E "+" T ⇒ ‹(+)› | T
  and
    T :: ‹nat› = AId ⇒ ‹λ_. 1› | AErr ⇒ ‹λ_. 0›

parser (ast) ae_parse for ae recover AErr and ae_t for ae (T)

ML ‹val _ = @{thms ae_parse.sound ae_parse.complete ae_parse.sound_lang ae_parse.complete_lang ae_parse_recover.no_error}›

ML ‹
  assert (nprems context unchecked_name‹ae_parse.sound› = 1);
  assert (nprems context unchecked_name‹ae_parse.complete› = 2);
  assert (nprems context unchecked_name‹ae_parse.complete_lang› = 1);
  assert (nprems context unchecked_name‹ae_parse_recover.no_error› = 2);
›

parser_check ‹map_option shape (ae_parse (toks 0 [AId, APlus, AId])) =
  Some (TN ''E'' [TN ''E'' [TN ''T'' [TL AId]], TL APlus, TN ''T'' [TL AId]])›
parser_check ‹ae_parse (toks 0 [AId, AId]) = None›
parser_check ‹isl (ae_parse_diag (toks 0 [AId, AId]))›
parser_check ‹map_option shape (snd (ae_parse_recover (toks 0 [AId, APlus, APlus, AId]))) =
  Some (TN ''E'' [TN ''E'' [TN ''E'' [TN ''T'' [TL AId]], TL APlus, TN ''T'' [TL AErr]],
    TL APlus, TN ''T'' [TL AId]])›

text ‹The decoding parser of the same grammar is unchanged.›

parser ae_value for ae

parser_check ‹ae_value (toks 0 [AId, APlus, AId]) = Some 2›
ML ‹val _ = @{thms ae_value.sound}›

parser_check ‹map_option shape (ae_t (toks 0 [AId])) = Some (TN ''T'' [TL AId])›
ML ‹val _ = @{thms ae_t.sound ae_t.complete}›


subsection ‹Layout›

grammar ab =
  tokens ‹a_tok›
  productions
    Ds :: ‹nat list› = Decl⇧= ⇒ ‹λx. [x]› | Ds⇧= Decl⇧= ⇒ ‹λxs x. xs @ [x]›
  and
    Decl :: ‹nat› = AId⇧= ⇒ ‹λ_. 1› | AKw⇧= Ds⇧> ⇒ ‹λ_ ds. sum_list ds›

parser (ast, no_diagnostics) ab_parse for ab

ML ‹
  assert (nprems context unchecked_name‹ab_parse.sound› = 1);
  assert (nprems context unchecked_name‹ab_parse.complete› = 2);
›

text ‹The column decides the tree: the second ‹AId› in column 0 is a declaration of
  its own, in column 2 one of the block.›

parser_check ‹map_option shape (ab_parse [tk 0 0 AKw, tk 1 2 AId, tk 2 0 AId]) =
  Some (TN ''Ds'' [TN ''Ds'' [TN ''Decl'' [TL AKw, TN ''Ds'' [TN ''Decl'' [TL AId]]]],
    TN ''Decl'' [TL AId]])›
parser_check ‹map_option shape (ab_parse [tk 0 0 AKw, tk 1 2 AId, tk 2 2 AId]) =
  Some (TN ''Ds'' [TN ''Decl'' [TL AKw,
    TN ''Ds'' [TN ''Ds'' [TN ''Decl'' [TL AId]], TN ''Decl'' [TL AId]]]])›
parser_check ‹ab_parse [tk 0 0 AKw, tk 1 0 AId] = None›


subsection ‹Precedence declarations›

text ‹The tree speaks of the grammar as written, not of the restricted one.›

grammar ap =
  tokens ‹a_tok›
  terminals "+" = ‹APlus› and "*" = ‹AStar›
  precedence left "*" > left "+"
  productions
    E :: ‹nat› = E "+" E ⇒ ‹(+)› | E "*" E ⇒ ‹(*)› | ANum ⇒ ‹λ_. 1›

parser (ast) ap_parse for ap

ML ‹val _ = @{thms ap_parse.sound ap_parse.complete}›

ML ‹
  assert (nprems context unchecked_name‹ap_parse.sound› = 1);
  assert (nprems context unchecked_name‹ap_parse.complete› = 3);
›

parser_check ‹map_option shape (ap_parse (toks 0 [ANum, APlus, ANum, AStar, ANum])) =
  Some (TN ''E'' [TN ''E'' [TL ANum], TL APlus,
    TN ''E'' [TN ''E'' [TL ANum], TL AStar, TN ''E'' [TL ANum]]])›

end