Theory TIGER_Token
theory TIGER_Token
imports Main
begin
section ‹Source spans›
text ‹
Lexer-to-parser interface: each token is paired with the source span it
occupies. Only the column \<^text>‹s_col› enters the indentation logic; it is
the indentation of a terminal in \<^cite>‹‹Sect.~2› in "adams2013"›. The
remaining fields serve diagnostics.
›
record 'ch span =
s_line :: nat
s_col :: nat
s_off :: nat
s_len :: nat
s_txt :: ‹'ch list›
section ‹Parser input: extensible tokens›
record ('tok, 'ch) token =
tok :: 'tok
span :: ‹'ch span›
notation token.make (‹⟨_; _⟩›)
text ‹The parser consumes a list of tokens. The record fixes only what the
parser reads: the token class \<^const>‹tok› and the lexeme \<^const>‹span›.
A client extends it with further fields (trailing trivia, source file,
…) through the usual record extension
⬚‹record my_token = (my_tok, char) token + trailing :: …›
and the parser is agnostic to the extension: it copies each token into
the corresponding AST leaf, where the extra fields are available to the
semantic actions of the ⬚‹grammar› command. All parser
constants are stated over the scheme type \<^typ>‹('tok, 'ch, 'm) token_scheme›
with the extension type \<^text>‹'m› free (\<^typ>‹unit› for the plain record).›
type_synonym ('m, 'ch, 'tok) tword = ‹('tok, 'ch, 'm) token_scheme list›
definition tcols :: ‹('m, 'ch, 'tok) tword ⇒ ('tok × nat) list› where
‹tcols w = map (λt. (tok t, s_col (span t))) w›
text ‹Layout machinery reads a token word through \<^const>‹tcols›, which
keeps the indentation column of each token and drops the rest of its span
and any extension fields. The result is a word over terminals annotated with
their columns, the input of an indentation-sensitive grammar
\<^cite>‹‹Sect.~2› in "adams2013"›.›
lemma tcols_Nil [simp]: ‹tcols [] = []›
and tcols_Cons [simp]: ‹tcols (t # w) = (tok t, s_col (span t)) # tcols w›
by (simp_all add: tcols_def)
lemma length_tcols [simp]: ‹length (tcols w) = length w›
and tcols_append [simp]: ‹tcols (u @ v) = tcols u @ tcols v›
and tcols_take: ‹tcols (take n w) = take n (tcols w)›
and tcols_drop: ‹tcols (drop n w) = drop n (tcols w)›
by (simp_all add: tcols_def take_map drop_map)
text ‹Anchor column of a word: the column of its first token, or ‹0› for
the empty word (which is never the outermost anchor of a well-indented
derivation).›
definition col_of :: ‹('m, 'ch, 't) tword ⇒ nat› where
‹col_of w = (case w of [] ⇒ 0 | x # _ ⇒ s_col (span x))›
lemma col_of_Nil[simp]: ‹col_of [] = 0›
by (simp add: col_of_def)
lemma col_of_Cons[simp]: ‹col_of (x # xs) = s_col (span x)›
by (simp add: col_of_def)
end