Theory TIGER_Spec
theory TIGER_Spec
imports TIGER_Regex TIGER_Lexed
begin
section ‹The lexer specification›
text ‹A lexer spec maps each mode to a prioritized list of rules. A rule is a regex over
syntactic predicates and an action. The action sees the matched text and the mode stack
(its head is the current mode) and returns the token kind, or \<^const>‹None› for
trivia, and the new stack \<^cite>‹‹Sect.~10› in "paxson2026-flex-manual"›. The judgments follow Verbatim
\<^cite>‹‹Figs.~3--4› in "egolf2021-verbatim-verified-lexer"›: the longest prefix, the
first rule matching it, and the driver, which stops with the unread residue and the
stack it stops in.
The judgments live in the context of ‹symbolic› and read a rule's regex through the
denotation ‹sem› of its predicates (\<^const>‹symbolic.lang›).
An empty match is never a match, and an action returning the empty stack is an error
(the driver stops before that step). Both make the driver total and deterministic.
Reps assumes instead that no token regex admits the empty word
\<^cite>‹‹Sect.~1› in "reps1998-maximal-munch-linear"›. Here a rule's regex
may accept it, and ‹match_rule› drops that match.›
record ('k, 'p, 'ch, 'm) rule =
match :: ‹'p rexp›
act :: ‹'ch list ⇒ 'm list ⇒ 'k option × 'm list›
type_synonym ('k, 'p, 'ch, 'm) lexer_spec = ‹'m ⇒ ('k, 'p, 'ch, 'm) rule list›
context symbolic
begin
inductive match_rule :: ‹('k, 'p, 'ch, 'm) rule ⇒ 'ch list ⇒ bool› where
match_ruleI: ‹⟦ p ∈ lang (match ρ); p ≠ [] ⟧ ⟹ match_rule ρ p›
text ‹A rule matches a nonempty word of its language
\<^cite>‹‹Fig.~4, FirstToken› in "egolf2021-verbatim-verified-lexer"›.›
inductive max_pref where
max_prefI:
‹⟦ s = p @ u; ρ ∈ set rs; match_rule ρ p;
⋀p' u' ρ'.
⟦ s = p' @ u'; length p < length p'; ρ' ∈ set rs ⟧ ⟹
¬ match_rule ρ' p'
⟧ ⟹
max_pref rs p s›
text ‹‹p› is the longest prefix of ‹s› that some rule matches
\<^cite>‹‹Fig.~3, MaxPref› in "egolf2021-verbatim-verified-lexer"›.›
inductive first_token where
first_tokenI:
‹⟦ max_pref rs p s; i < length rs; match_rule (rs ! i) p;
⋀j. j < i ⟹ ¬ match_rule (rs ! j) p
⟧ ⟹
first_token rs i p s›
text ‹Rule ‹i› wins on ‹s› with lexeme ‹p›: ‹p› is the longest match and ‹i› the first
rule matching it \<^cite>‹‹Sect.~7› in "paxson2026-flex-manual"›, as in lex
\<^cite>‹‹Sect.~5› in "lesk1975-lex"›.›
inductive step where
stepI:
‹⟦ first_token (sp m) i p s;
act (sp m ! i) p (m # st) = (k, st');
st' ≠ [];
s = p @ s'
⟧ ⟹
step sp (m # st) s (k, p, st', s')›
text ‹One step in the stack ‹m # st› reads the winning lexeme ‹p›, runs the winning action
and yields the kind ‹k›, the new stack and the rest of the input.›
inductive lexes ::
‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒
'ch list ⇒ ('k, 'ch) lexed ⇒ 'ch list ⇒ 'm list ⇒ bool›
for sp is_newline where
lexes_stop:
‹(⋀x. ¬ step sp st s x) ⟹ lexes sp is_newline st q s (Lexed [] []) s st›
| lexes_token:
‹⟦ step sp st s (Some k, p, st', s');
lexes sp is_newline st' (advance_list is_newline p q) s' (Lexed h ts) r st⇩f
⟧ ⟹
lexes sp is_newline st q s
(Lexed [] (⦇tok = k, span = span_at q p, trivia = h⦈ # ts)) r st⇩f›
| lexes_trivia:
‹⟦ step sp st s (None, p, st', s');
lexes sp is_newline st' (advance_list is_newline p q) s' (Lexed h ts) r st⇩f
⟧ ⟹
lexes sp is_newline st q s (Lexed (p @ h) ts) r st⇩f›
text ‹The driver lexes ‹s› from stack ‹st› and position ‹q› into a lexed source, the
residue ‹r› where no step applies and the stack ‹st⇩f› it stops in
\<^cite>‹‹Fig.~4, Tokens› in "egolf2021-verbatim-verified-lexer"›. The leading trivia
of the rest become the trailing trivia of a token, or the header in front of the
first token. Spans come from \<^const>‹advance_list›.
The final stack says where the input ended, so the end of the input needs no
sentinel character (flex's ‹<<EOF>>› \<^cite>‹‹Sect.~12› in "paxson2026-flex-manual"›).
An empty residue in a stack whose top is not a final mode (an unterminated comment)
is an error of the consumer's, not of the driver.›
subsection ‹Some facts›
lemma max_prefD: ‹max_pref rs p s ⟹ (∃u. s = p @ u) ∧ (∃ρ ∈ set rs. match_rule ρ p)›
by (blast elim: max_pref.cases)
lemma max_pref_longest:
assumes ‹max_pref rs p s› ‹s = p' @ u'› ‹length p < length p'› ‹ρ' ∈ set rs›
shows ‹¬ match_rule ρ' p'›
using ‹max_pref rs p s›
proof (cases rule: max_pref.cases)
case max_prefI
then have ‹⋀p' u' ρ'. ⟦ s = p' @ u'; length p < length p'; ρ' ∈ set rs ⟧ ⟹ ¬ match_rule ρ' p'›
by blast
with assms show ?thesis by blast
qed
lemma first_token_max_pref: ‹first_token rs i p s ⟹ max_pref rs p s›
by (auto elim: first_token.cases)
lemma first_token_match: ‹first_token rs i p s ⟹ match_rule (rs ! i) p›
by (auto elim: first_token.cases)
lemma first_token_first: ‹first_token rs i p s ⟹ j < i ⟹ ¬ match_rule (rs ! j) p›
by (auto elim: first_token.cases)
lemma first_token_prefix: ‹first_token rs i p s ⟹ ∃u. s = p @ u›
by (auto elim!: first_token.cases max_pref.cases)
lemma step_length_less: ‹step sp st s (k, p, st', s') ⟹ length s' < length s›
by (auto elim!: step.cases first_token.cases match_rule.cases)
text ‹Every step consumes input (no empty matches). This is the progress measure of the
driver.›
lemma lexes_source: ‹lexes sp is_newline st q s l r st⇩f ⟹ source l @ r = s›
by (induct rule: lexes.induct) (auto simp: source_def span_at_def elim!: step.cases)
section ‹Surface theorems›
text ‹The spec is unambiguous: the first token is unique, and so are a step and a whole
run. This is Verbatim's Uniqueness lemma
\<^cite>‹‹Sect.~V-B› in "egolf2021-verbatim-verified-lexer"›, proved the same way: both
lexemes are maximal prefixes of one string, so they are equal, and of two rules matching
it the later one cannot win. Verbatim has no modes; here the run also fixes the final
stack.›
theorem first_token_deterministic:
assumes ‹first_token rs i p s› ‹first_token rs i' p' s›
shows ‹i = i' ∧ p = p'›
proof -
from assms have mp: ‹max_pref rs p s› and mp': ‹max_pref rs p' s›
by (simp_all add: first_token_max_pref)
from mp obtain u ρ where ‹s = p @ u› ‹ρ ∈ set rs› ‹match_rule ρ p›
by (blast dest: max_prefD)
from mp' obtain u' ρ' where ‹s = p' @ u'› ‹ρ' ∈ set rs› ‹match_rule ρ' p'›
by (blast dest: max_prefD)
have ‹¬ length p < length p'›
using max_pref_longest[OF mp ‹s = p' @ u'› _ ‹ρ' ∈ set rs›] ‹match_rule ρ' p'› by blast
moreover have ‹¬ length p' < length p›
using max_pref_longest[OF mp' ‹s = p @ u› _ ‹ρ ∈ set rs›] ‹match_rule ρ p› by blast
ultimately have ‹p = p'›
using ‹s = p @ u› ‹s = p' @ u'› by simp
with assms show ?thesis
by (metis linorder_neqE_nat first_token_first first_token_match)
qed
theorem step_deterministic: ‹step sp st s x ⟹ step sp st s y ⟹ x = y›
by (elim step.cases) (auto dest: first_token_deterministic)
theorem lexes_deterministic:
assumes ‹lexes sp is_newline st q s l r st⇩f› ‹lexes sp is_newline st q s l' r' st⇩f'›
shows ‹l = l' ∧ r = r' ∧ st⇩f = st⇩f'›
using assms
proof (induction arbitrary: l' r' st⇩f' rule: lexes.induct)
case (lexes_stop st s q)
from lexes_stop.prems show ?case
by (cases rule: lexes.cases) (use lexes_stop.hyps in blast)+
next
case (lexes_token st s k p st' s' q h ts r st⇩f)
from lexes_token.prems ‹step sp st s (Some k, p, st', s')› show ?case
by (cases rule: lexes.cases)
(auto dest: step_deterministic[OF ‹step sp st s (Some k, p, st', s')›] lexes_token.IH)
next
case (lexes_trivia st s p st' s' q h ts r st⇩f)
from lexes_trivia.prems ‹step sp st s (None, p, st', s')› show ?case
by (cases rule: lexes.cases)
(auto dest: step_deterministic[OF ‹step sp st s (None, p, st', s')›] lexes_trivia.IH)
qed
text ‹The driver terminates on every input, whatever the actions do to the stack
(each step consumes a nonempty lexeme, @{thm [source] step_length_less}). This is the
termination argument of Verbatim's ‹lex0›, which recurses on proper suffixes of the input
\<^cite>‹‹Sect.~IV› in "egolf2021-verbatim-verified-lexer"›. Verbatim must thread an
accessibility proof through the function; here the run is an inductive relation and
totality is a theorem, by induction on the length of the input:›
theorem lexes_total: ‹∃l r st⇩f. lexes sp is_newline st q s l r st⇩f›
proof (induct s arbitrary: st q rule: length_induct[case_names len])
case (len s) show ?case
proof (cases ‹∃x. step sp st s x›)
case True
then obtain k p st' s' where step: ‹step sp st s (k, p, st', s')›
by (metis prod_cases4)
with len obtain l r st⇩f
where ‹lexes sp is_newline st' (advance_list is_newline p q) s' l r st⇩f›
by (meson step_length_less)
with step show ?thesis
by (cases l; cases k; blast intro: lexes_token lexes_trivia)
qed (blast intro: lexes_stop)
qed
end
end