Theory TIGER_Lexer.TIGER_Lexed
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›