Theory TIGER_Lexer.TIGER_Driver
theory TIGER_Driver
imports TIGER_Lexer
begin
section ‹The driver›
text ‹The driver lexes a whole input. It steps the runner of the mode on top of the
stack, applies the action of the winning rule and stops when no step applies: the
stack is empty, no rule matches, or the action returns the empty stack. It returns
the lexed source, the residue and the stack it stops in
\<^cite>‹‹Sect.~10› in "paxson2026-flex-manual"›
\<^cite>‹‹Fig.~4, Tokens› in "egolf2021-verbatim-verified-lexer"›. Trivia go into the
header or the trailing trivia of the token before them, spans come from
\<^const>‹span_at› and \<^const>‹advance_list›.
The driver is generic in the runner ‹R›, which maps a mode and an input to the winning
rule, the lexeme and the rest. It takes the rest as \<^term>‹drop (length p) s›, which
makes the termination argument independent of ‹R›, and it stops on an empty lexeme,
which a correct runner never returns.›
fun drive ::
‹('m ⇒ 'ch list ⇒ (nat × 'ch list × 'ch list) option) ⇒ ('k, 'p, 'ch, 'm) lexer_spec ⇒
('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒ 'ch list ⇒ ('k, 'ch) lexed × 'ch list × 'm list›
where
‹drive R sp is_newline [] q s = (Lexed [] [], s, [])›
| ‹drive R sp is_newline (m # st) q [] = (Lexed [] [], [], m # st)›
| ‹drive R sp is_newline (m # st) q (c # v) =
(case R m (c # v) of
None ⇒ (Lexed [] [], c # v, m # st)
| Some (i, p, _) ⇒
(case act (sp m ! i) p (m # st) of
(k, st') ⇒
if p = [] ∨ st' = [] then (Lexed [] [], c # v, m # st)
else
(case drive R sp is_newline st' (advance_list is_newline p q)
(drop (length p) (c # v)) of
(Lexed h ts, r, st⇩f) ⇒
(case k of
None ⇒ (Lexed (p @ h) ts, r, st⇩f)
| Some k ⇒
(Lexed [] (⦇tok = k, span = span_at q p, trivia = h⦈ # ts), r, st⇩f)))))›
text ‹A spec whose modes are the numbers below the length of a list, with no rules in
the other modes. Tables for such a spec are an array indexed by the mode, so the
driver never compares modes:›
definition list_spec :: ‹'a list list ⇒ nat ⇒ 'a list› where
‹list_spec sps m = (if m < length sps then sps ! m else [])›
context symbolic
begin
subsection ‹The invariant›
text ‹‹R› runs the modes of ‹sp› if it returns exactly the winning rule and lexeme of
\<^const>‹first_token› in each mode:›
definition mode_runner ::
‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('m ⇒ 'ch list ⇒ (nat × 'ch list × 'ch list) option) ⇒
bool›
where
‹mode_runner sp R ⟷
(∀m s i p rest. R m s = Some (i, p, rest) ⟷ first_token (sp m) i p s ∧ s = p @ rest)›
lemma step_iff_mode_runner:
assumes ‹mode_runner sp R›
shows ‹step sp (m # st) s (k, p, st', s') ⟷
(∃i. R m s = Some (i, p, s') ∧ act (sp m ! i) p (m # st) = (k, st') ∧ st' ≠ [])›
using assms by (auto simp: mode_runner_def step.simps)
lemma lexes_drive:
assumes ‹mode_runner sp R›
shows ‹case drive R sp is_newline st q s of
(l, r, st⇩f) ⇒ lexes sp is_newline st q s l r st⇩f›
using assms
proof (induction R sp is_newline st q s rule: drive.induct)
case (1 R sp is_newline q s)
then show ?case
by (auto intro: lexes_stop elim: step.cases)
next
case (2 R sp is_newline m st q)
have ‹¬ step sp (m # st) [] x› for x
by (auto elim!: step.cases first_token.cases match_rule.cases)
then show ?case
by (auto intro: lexes_stop)
next
case (3 R sp is_newline m st q c v)
note runner = step_iff_mode_runner[OF ‹mode_runner sp R›]
show ?case
proof (cases ‹R m (c # v)›)
case None
then have ‹¬ step sp (m # st) (c # v) x› for x
using runner by (cases x) auto
with None show ?thesis
by (auto intro: lexes_stop)
next
case (Some x)
then obtain i p rest where R: ‹R m (c # v) = Some (i, p, rest)›
by (cases x) auto
with ‹mode_runner sp R› have ‹first_token (sp m) i p (c # v)› ‹c # v = p @ rest›
by (auto simp: mode_runner_def)
then have ‹p ≠ []› and rest: ‹drop (length p) (c # v) = rest›
by (auto dest!: first_token_match elim: match_rule.cases)
obtain k st' where act: ‹act (sp m ! i) p (m # st) = (k, st')›
by (cases ‹act (sp m ! i) p (m # st)›)
show ?thesis
proof (cases ‹st' = []›)
case True
then have ‹¬ step sp (m # st) (c # v) y› for y
using runner R act by (cases y) auto
with R act True show ?thesis
by (auto intro: lexes_stop)
next
case False
with R act have step: ‹step sp (m # st) (c # v) (k, p, st', rest)›
using runner by auto
let ?d = ‹drive R sp is_newline st' (advance_list is_newline p q) rest›
from "3.IH"[OF R refl refl act[symmetric]] False ‹p ≠ []› ‹mode_runner sp R› rest
have IH: ‹case ?d of (l, r, st⇩f) ⇒
lexes sp is_newline st' (advance_list is_newline p q) rest l r st⇩f›
by simp
obtain h ts r st⇩f where d: ‹?d = (Lexed h ts, r, st⇩f)›
by (metis lexed.exhaust prod.exhaust)
from IH d step R act False ‹p ≠ []› rest show ?thesis
by (cases k) (auto intro: lexes_token lexes_trivia)
qed
qed
qed
text ‹The driver returns a run of the spec (‹lexes_drive›), and by determinism of the spec
that run is the only one. This is how Verbatim gets Completeness from Soundness and
Uniqueness \<^cite>‹‹Sects.~V-A--V-C› in "egolf2021-verbatim-verified-lexer"›. Verbatim
assumes unambiguous rules (each label has one regex); this driver needs only a correct
runner.›
theorem drive_iff_lexes:
assumes ‹mode_runner sp R›
shows ‹drive R sp is_newline st q s = (l, r, st⇩f) ⟷ lexes sp is_newline st q s l r st⇩f›
proof
assume ‹drive R sp is_newline st q s = (l, r, st⇩f)›
with lexes_drive[OF assms, of is_newline st q s] show ‹lexes sp is_newline st q s l r st⇩f›
by simp
next
assume ‹lexes sp is_newline st q s l r st⇩f›
with lexes_drive[OF assms, of is_newline st q s]
show ‹drive R sp is_newline st q s = (l, r, st⇩f)›
by (auto split: prod.splits dest: lexes_deterministic)
qed
end
context eba
begin
text ‹The driver over the DFA runner of each mode, with a classifier for each mode:›
definition run_lexer ::
‹('k, 'p, 'ch, 'm) lexer_spec ⇒ ('m ⇒ 'ch ⇒ nat) ⇒ ('ch ⇒ bool) ⇒ 'm list ⇒ pos ⇒
'ch list ⇒ ('k, 'ch) lexed × 'ch list × 'm list›
where
‹run_lexer sp cls = drive (λm. run_dfa (sp m) (cls m)) sp›
lemma mode_runner_run_dfa:
assumes ‹⋀m. minterm_classifier (sp m) (cls m)›
shows ‹mode_runner sp (λm. run_dfa (sp m) (cls m))›
using run_dfa_Some_iff[OF assms] by (simp add: mode_runner_def)
section ‹Surface theorems›
text ‹With a classifier into the minterms of each mode, the driver returns exactly the
lexed source, the residue and the final stack of \<^const>‹lexes›:›
theorem run_lexer_iff_lexes:
assumes ‹⋀m. minterm_classifier (sp m) (cls m)›
shows ‹run_lexer sp cls is_newline st q s = (l, r, st⇩f) ⟷
lexes sp is_newline st q s l r st⇩f›
unfolding run_lexer_def by (rule drive_iff_lexes[OF mode_runner_run_dfa[OF assms]])
end
end