Theory Grammar_Command

(* Author: Basil Fürer, Dmitriy Traytel *)

theory Grammar_Command
  imports TIGER_Grammar_Model.Grammar_Base
  keywords "grammar" :: thy_decl
    and "tokens" "terminals" "productions"
    and "^=" "^>=" "^>" "*"
    and "⇒" "=>"
    and "parser" :: thy_decl
    and "for"
begin

section ‹The grammar and parser commands›

text ‹The commands are described in the manual, the theory ‹TIGER› of the session
  ‹TIGER› (▩‹TIGER.thy›).›

subsection ‹The span of a yield›

text ‹An alternative that writes ‹@span› passes its action the span of its yield,
  from the first token to the last (‹word_span›): line, column and offset of
  the first token, the length up to the end of the last, and the concatenated texts of
  the tokens. The decoders compute it on the children of a node
  (‹yield_span›), the relation on the word; ‹ast_yield_erase› makes the two
  agree.›

fun ast_yield :: ‹('m, 'ch, 'n, 'tok) ast ⇒ ('m, 'ch, 'tok) tword› where
  ‹ast_yield (Leaf t) = [t]›
| ‹ast_yield (Node n ts) = concat (map ast_yield ts)›

definition word_span :: ‹('m, 'ch, 'tok) tword ⇒ 'ch span› where
  ‹word_span w =
    (case w of
      [] ⇒ ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 0, s_txt = []⦈
    | t # _ ⇒
        ⦇s_line = s_line (span t), s_col = s_col (span t), s_off = s_off (span t),
         s_len = s_off (span (last w)) + s_len (span (last w)) - s_off (span t),
         s_txt = concat (map (s_txt ∘ span) w)⦈)›

definition yield_span :: ‹('m, 'ch, 'n, 'tok) ast list ⇒ 'ch span› where
  ‹yield_span xs = word_span (concat (map ast_yield xs))›

lemma ast_yield_erase [simp]: ‹ast_yield (erase pt) = pyield pt›
  by (induction pt) (simp_all cong: map_cong)

(*<*)
fun ast_first :: ‹('m, 'ch, 'n, 'tok) ast list ⇒ ('tok, 'ch, 'm) token_scheme option› where
  ‹ast_first [] = None›
| ‹ast_first (Leaf t # _) = Some t›
| ‹ast_first (Node _ ts # xs) = (case ast_first ts of None ⇒ ast_first xs | r ⇒ r)›

fun ast_last :: ‹('m, 'ch, 'n, 'tok) ast list ⇒ ('tok, 'ch, 'm) token_scheme option› where
  ‹ast_last [] = None›
| ‹ast_last (x # xs) =
    (case ast_last xs of
      None ⇒ (case x of Leaf t ⇒ Some t | Node _ ts ⇒ ast_last ts)
    | r ⇒ r)›

fun hd_opt :: ‹'a list ⇒ 'a option› where
  ‹hd_opt [] = None›
| ‹hd_opt (x # _) = Some x›

lemma hd_opt_append: ‹hd_opt (a @ b) = (case hd_opt a of None ⇒ hd_opt b | r ⇒ r)›
  by (cases a) auto

lemma hd_opt_rev: ‹hd_opt (rev c) = (if c = [] then None else Some (last c))›
  by (induction c) (auto simp: hd_opt_append split: option.split)

lemma ast_first_yield: ‹ast_first xs = hd_opt (concat (map ast_yield xs))›
  by (induction xs rule: ast_first.induct) (auto simp: hd_opt_append split: option.split)

lemma ast_last_yield: ‹ast_last xs = hd_opt (rev (concat (map ast_yield xs)))›
  by (induction xs rule: ast_last.induct) (auto simp: hd_opt_append split: option.split ast.split)

text ‹The texts by an accumulator: on a left-recursive spine, ‹concat (map ast_yield xs)›
  would rebuild the left-nested appends at every node.›

fun ast_txts :: ‹('m, 'ch, 'n, 'tok) ast list ⇒ 'ch list ⇒ 'ch list› where
  ‹ast_txts [] acc = acc›
| ‹ast_txts (Leaf t # xs) acc = s_txt (span t) @ ast_txts xs acc›
| ‹ast_txts (Node _ ts # xs) acc = ast_txts ts (ast_txts xs acc)›

lemma ast_txts_yield:
  ‹ast_txts xs acc = concat (map (s_txt ∘ span) (concat (map ast_yield xs))) @ acc›
  by (induction xs acc rule: ast_txts.induct) simp_all

lemma yield_span_code [code]:
  ‹yield_span xs =
    (case ast_first xs of
      None ⇒ ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 0, s_txt = []⦈
    | Some t ⇒
        (case ast_last xs of
          None ⇒ undefined
        | Some z ⇒
            ⦇s_line = s_line (span t), s_col = s_col (span t), s_off = s_off (span t),
             s_len = s_off (span z) + s_len (span z) - s_off (span t),
             s_txt = ast_txts xs []⦈))›
proof -
  obtain c where c: ‹concat (map ast_yield xs) = c› by blast
  show ?thesis
    unfolding yield_span_def word_span_def ast_first_yield ast_last_yield ast_txts_yield c
    by (cases c) (simp_all add: hd_opt_rev del: rev.simps)
qed
(*>*)

(*<*)
ML_file ‹grammar_common.ML›
ML_file ‹grammar_ptree_induct.ML›
ML_file ‹grammar_defs.ML›
ML_file ‹grammar_rel.ML›
ML_file ‹grammar_expand.ML›
ML_file ‹grammar_elab.ML›
ML_file ‹grammar_syntax.ML›

ML_file ‹parser_dec_total.ML›
ML_file ‹parser_rel_bridge.ML›
ML_file ‹parser_generators.ML›

hide_fact
  lang_of_complete
  wf_ptree_Tm_leaf
  erase_Nt_E2
  proot_Tm_E
  case_ast_Nt_None
(*>*)

subsection ‹The prelude›

text ‹Generic templates, used as ‹List(X)›, ‹Sep1(X, S)› and so on.›

grammar Grammar_Prelude =
  productions
    List(X) :: ‹'x list› = ⇒ ‹[]› | List(X) X ⇒ ‹λxs x. xs @ [x]›
  and
    List1(X) :: ‹'x list› = X ⇒ ‹λx. [x]› | List1(X) X ⇒ ‹λxs x. xs @ [x]›
  and
    Opt(X) :: ‹'x option› = ⇒ ‹None› | X ⇒ ‹Some›
  and
    Sep1(X, S) :: ‹'x list› = X ⇒ ‹λx. [x]› | Sep1(X, S) S X ⇒ ‹λxs x. xs @ [x]›
  and
    Sep(X, S) :: ‹'x list› = ⇒ ‹[]› | Sep1(X, S)

end