Theory TIGER_Token

(* Author: Basil Fürer *)

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