Theory TIGER_Lexer.TIGER_Lexed

(* Author: Basil Fürer *)

theory TIGER_Lexed
  imports TIGER_Token.TIGER_Token
begin

text ‹What the lexer adds to the token interface of theory‹TIGER_Token.TIGER_Token›:
  positions, from which the lexer computes the spans, and its output, tokens with their
  trailing trivia. The parser needs neither.›

section ‹Positions›

text ‹A position is a line, a column and a character offset, all counted from ‹0›. The
  spans store the start position and the text, so the stop position of a span is
  derived from its text by ‹advance_list› (half-open: the stop position is the
  first one past the span).›

record pos =
  line :: nat
  col :: nat
  off :: nat

definition advance :: ‹('ch ⇒ bool) ⇒ 'ch ⇒ pos ⇒ pos› where
  ‹advance is_newline c p = (if is_newline c
     then ⦇line = Suc (line p), col = 0, off = Suc (off p)⦈
     else p⦇col := Suc (col p), off := Suc (off p)⦈)›

text ‹const‹advance› moves past one character. The newline test is a parameter
  (the character type is arbitrary).›

primrec advance_list :: ‹('ch ⇒ bool) ⇒ 'ch list ⇒ pos ⇒ pos› where
  ‹advance_list is_newline [] p = p›
| ‹advance_list is_newline (c # w) p = advance_list is_newline w (advance is_newline c p)›

lemma off_advance[simp]: ‹off (advance is_newline c p) = Suc (off p)›
  by (simp add: advance_def)

lemma off_advance_list[simp]: ‹off (advance_list is_newline w p) = off p + length w›
  by (induct w arbitrary: p) simp_all

lemma off_le_advance_list: ‹off p ≤ off (advance_list is_newline w p)›
  by simp

lemma advance_list_append[simp]:
  ‹advance_list is_newline (u @ v) p = advance_list is_newline v (advance_list is_newline u p)›
  by (induct u arbitrary: p) simp_all

definition span_at :: ‹pos ⇒ 'ch list ⇒ 'ch span› where
  ‹span_at p w = ⦇s_line = line p, s_col = col p, s_off = off p, s_len = length w, s_txt = w⦈›

text ‹const‹span_at› is the span of the text ‹w› starting at ‹p›. It is well formed:
  it ends where const‹advance_list› stops.›

lemma span_at_stop: ‹s_off (span_at p w) + s_len (span_at p w) = off (advance_list is_newline w p)›
  by (simp add: span_at_def)

section ‹Lexer output›

text ‹A lexed token is a parser token (const‹tok› is its kind, const‹s_txt› of its
  span its text) extended by its trailing trivia, the comments and whitespace up to the
  next token. The parser accepts the extension unchanged (see the token record in
  theory‹TIGER_Token.TIGER_Token›).›

record ('tok, 'ch) lex_token = ‹('tok, 'ch) token› +
  trivia :: ‹'ch list›

datatype ('tok, 'ch) lexed = Lexed (header: ‹'ch list›) (toks: ‹('tok, 'ch) lex_token list›)

text ‹A lexed source is its leading trivia and its tokens. ‹source› gives back
  the text it was lexed from:›

definition source :: ‹('tok, 'ch) lexed ⇒ 'ch list› where
  ‹source l = header l @ concat (map (λt. s_txt (span t) @ trivia t) (toks l))›

end