Theory Grammar_Command
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