Theory Tables_Tests

(* Author: Basil Fürer *)

theory Tables_Tests
  imports TIGER_Lexer.TIGER_Tables
begin

section ‹Tests of the tables›

text ‹Two specs on bytes, with their tables by ‹eval_table› and the runner on
  them: identifiers, numerals and a keyword in one mode, and Reps' pair ‹abc›,
  ‹(abc)*d›, which makes the runner back up
  cite‹‹Sect.~1› in "reps1998-maximal-munch-linear"›. The theorems about the
  runners are instances of @{thm [source] run_char_tables}.›

subsection ‹Identifiers, numerals and a keyword›

datatype tok = KW_IF | IDENT | NUM

definition ‹letter = [(CHR ''a'', CHR ''z'')]›
definition ‹digit = [(CHR ''0'', CHR ''9'')]›
definition ‹space = [(CHR '' '', CHR '' ''), (CHR 0x0A, CHR 0x0A)]›

text ‹The keyword ‹if› comes first, so it wins against identifiers on ‹if› by
  priority and loses on ‹iff› by length. Whitespace is trivia. There is one mode:›

definition test_rules :: ‹(tok, char cls, char, unit) rule list› where
  ‹test_rules = [
    ⦇match = Times (Pred [(CHR ''i'', CHR ''i'')]) (Pred [(CHR ''f'', CHR ''f'')]),
     act = λ_ st. (Some KW_IF, st)⦈,
    ⦇match = Times (Pred letter) (Star (Plus (Pred letter) (Pred digit))),
     act = λ_ st. (Some IDENT, st)⦈,
    ⦇match = Times (Pred digit) (Star (Pred digit)), act = λ_ st. (Some NUM, st)⦈,
    ⦇match = Times (Pred space) (Star (Pred space)), act = λ_ st. (None, st)⦈]›

definition ‹test_tables = char_tables test_rules›

local_setup ‹eval_table (binding‹test_tables_code›, term‹test_tables›)›

declare test_tables_code[code]

value ‹test_tables›

definition ‹test_run = run_char test_tables›

text ‹The runner on the tables is the step of the spec:›

theorem test_run_Some_iff:
  ‹test_run s = Some (i, p, rest) ⟷ char_cls.first_token test_rules i p s ∧ s = p @ rest›
  by (simp add: test_run_def test_tables_def run_char_tables char_cls.run_dfa_Some_iff
      char_cls.minterm_classifier_class_of)

theorem test_run_None_iff:
  ‹test_run s = None ⟷ (∄i p. char_cls.first_token test_rules i p s)›
  by (simp add: test_run_def test_tables_def run_char_tables char_cls.run_dfa_None_iff
      char_cls.minterm_classifier_class_of)

text ‹Priority on ‹if›, length on ‹iff›, trivia, and inputs no rule matches:›

value ‹test_run ''if x''›
value ‹test_run ''iff x''›
value ‹test_run ''x1 = 42''›
value ‹test_run ''42ab''›
value ‹test_run ''  ⏎ if''›
value ‹test_run ''= x''›
value ‹test_run []›

lemma ‹test_run ''if x'' = Some (0, ''if'', '' x'')› by eval
lemma ‹test_run ''iff x'' = Some (1, ''iff'', '' x'')› by eval
lemma ‹test_run ''42ab'' = Some (2, ''42'', ''ab'')› by eval
lemma ‹test_run ''= x'' = None› by eval

subsection ‹Backing up›

text ‹On ‹abcabd›, the runner reads ‹abcab›, finds that no rule can match a longer
  prefix and backs up to ‹abc› cite‹‹Sect.~1› in "reps1998-maximal-munch-linear"›:›

definition ‹chr c = Pred [(c, c)]›

definition reps_rules :: ‹(nat, char cls, char, unit) rule list› where
  ‹reps_rules = [
    ⦇match = Times (chr CHR ''a'') (Times (chr CHR ''b'') (chr CHR ''c'')),
     act = λ_ st. (Some 0, st)⦈,
    ⦇match = Times (Star (Times (chr CHR ''a'') (Times (chr CHR ''b'') (chr CHR ''c''))))
       (chr CHR ''d''),
     act = λ_ st. (Some 1, st)⦈]›

definition ‹reps_tables = char_tables reps_rules›

local_setup ‹eval_table (binding‹reps_tables_code›, term‹reps_tables›)›

declare reps_tables_code[code]

definition ‹reps_run = run_char reps_tables›

theorem reps_run_Some_iff:
  ‹reps_run s = Some (i, p, rest) ⟷ char_cls.first_token reps_rules i p s ∧ s = p @ rest›
  by (simp add: reps_run_def reps_tables_def run_char_tables char_cls.run_dfa_Some_iff
      char_cls.minterm_classifier_class_of)

value ‹reps_tables›
value ‹reps_run ''abcabd''›
value ‹reps_run ''abd''›
value ‹reps_run ''abcabcd''›

lemma ‹reps_run ''abcabd'' = Some (0, ''abc'', ''abd'')› by eval
lemma ‹reps_run ''abd'' = None› by eval
lemma ‹reps_run ''abcabcd'' = Some (1, ''abcabcd'', [])› by eval

end