Theory Prec_Surface_Tests

(* Author: Basil Fürer *)

theory Prec_Surface_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

section ‹Precedence declarations in ⬚‹grammar››

fun toks :: ‹nat ⇒ 'tok list ⇒ ('tok, unit) token list› where
  ‹toks i [] = []›
| ‹toks i (x # xs) = ⦇tok = x, span = span.make 0 i i 1 []⦈ # toks (Suc (Suc i)) xs›

datatype p_tok = PNum | PPlus | PMinus | PStar | PPow | PEq | PLP | PRP | PErr

datatype p_exp =
  N | Add p_exp p_exp | Sub p_exp p_exp | Mul p_exp p_exp | Pow p_exp p_exp
  | Neg p_exp | Equ p_exp p_exp | Bad

subsection ‹A total order, a name for a level, a nonassociative level›

grammar ep =
  tokens ‹p_tok›
  terminals
    "+" = ‹PPlus› and "-" = ‹PMinus› and "*" = ‹PStar› and "^" = ‹PPow› and
    "==" = ‹PEq› and "(" = ‹PLP› and ")" = ‹PRP›
  precedence right "^" > left UMINUS > left "*" > left "+" "-" > nonassoc "=="
  productions
    E :: ‹p_exp›
      = E "==" E ⇒ ‹λa b. Equ a b›
      | E "+" E ⇒ ‹λa b. Add a b›
      | E "-" E ⇒ ‹λa b. Sub a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | "-" E (prec UMINUS) ⇒ ‹λa. Neg a›
      | E "^" E ⇒ ‹λa b. Pow a b›
      | A
  and
    A :: ‹p_exp›
      = PNum ⇒ ‹λ_. N›
      | "(" E ")" ⇒ ‹λe. e›

parser ep_parse for ep

ML ‹val _ = @{thms ep_parse.sound ep_parse.complete ep_parse.sound_lang ep_parse.complete_lang}›

parser_check ‹ep_parse (toks 0 [PNum, PPlus, PNum, PStar, PNum]) = Some (Add N (Mul N N))›
parser_check ‹ep_parse (toks 0 [PNum, PStar, PNum, PPlus, PNum]) = Some (Add (Mul N N) N)›
parser_check ‹ep_parse (toks 0 [PNum, PMinus, PNum, PPlus, PNum]) = Some (Add (Sub N N) N)›
parser_check ‹ep_parse (toks 0 [PNum, PPow, PNum, PPow, PNum]) = Some (Pow N (Pow N N))›
parser_check ‹ep_parse (toks 0 [PMinus, PNum, PPow, PNum]) = Some (Neg (Pow N N))›
parser_check ‹ep_parse (toks 0 [PMinus, PNum, PStar, PNum]) = Some (Mul (Neg N) N)›
parser_check ‹ep_parse (toks 0 [PNum, PEq, PNum]) = Some (Equ N N)›
parser_check ‹ep_parse (toks 0 [PNum, PEq, PNum, PEq, PNum]) = None›
parser_check ‹ep_parse (toks 0 [PLP, PNum, PEq, PNum, PRP, PEq, PNum]) = Some (Equ (Equ N N) N)›

subsection ‹Several lines; an entry; a nonterminal below the prefix›

grammar eq =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar› and "(" = ‹PLP› and ")" = ‹PRP›
  precedence left "*" > left "+"
  productions
    S :: ‹p_exp› = E
  and
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | PNum ⇒ ‹λ_. N›
      | "(" E ")" ⇒ ‹λe. e›

parser eq_s for eq and eq_e for eq (E)

ML ‹val _ = @{thms eq_e.sound eq_e.complete}›

parser_check ‹eq_s (toks 0 [PNum, PPlus, PNum, PStar, PNum]) = Some (Add N (Mul N N))›
parser_check ‹eq_e (toks 0 [PNum, PStar, PNum, PPlus, PNum]) = Some (Add (Mul N N) N)›

subsection ‹Merged lines and transitivity›

text ‹
  Two ‹precedence› lines that share ‹*› merge into one order, and ‹^› binds
  tighter than ‹+› by transitivity. Afroozeh et al. close their ‹>› transitively
  in the same way cite‹‹Sect.~3.3› in "afroozeh2013-operator-precedence"›.
›

grammar em =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar› and "^" = ‹PPow›
  precedence left "*" > left "+"
  precedence right "^" > left "*"
  productions
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | E "^" E ⇒ ‹λa b. Pow a b›
      | PNum ⇒ ‹λ_. N›

parser em_parse for em

parser_check ‹em_parse (toks 0 [PNum, PPow, PNum, PPlus, PNum]) = Some (Add (Pow N N) N)›

subsection ‹Diagnostics and recovery›

grammar er =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar› and "(" = ‹PLP› and ")" = ‹PRP›
  precedence left "*" > left "+"
  productions
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | PNum ⇒ ‹λ_. N›
      | "(" E ")" ⇒ ‹λe. e›
      | PErr ⇒ ‹λ_. Bad›

parser (diagnostics) er_parse for er recover PErr

ML ‹val _ = @{thms er_parse_recover.clean er_parse_recover.no_error er_parse.sound}›

parser_check ‹er_parse_recover (toks 0 [PNum, PPlus, PNum, PStar, PNum]) =
    ([], Some (Add N (Mul N N)))›

parser_check ‹(case er_parse_recover (toks 0 [PNum, PPlus, PRP, PStar, PNum]) of
    ([e], Some x) ⇒ pe_index e = 2 ∧ x = Add N (Mul Bad N)
  | _ ⇒ False)›

value ‹er_parse_recover (toks 0 [PNum, PPlus, PRP, PStar, PNum])›
value ‹er_parse_diag (toks 0 [PNum, PPlus, PPlus])›

text ‹The raw error speaks of the grammar: const‹pe_stack› holds no symbol of ‹G'›.›

parser_check ‹(case er_parse_diag (toks 0 [PNum, PPlus, PPlus]) of
    Inl e ⇒ map fst (pe_stack e) = [Tm PPlus, Nt ''E''] | Inr _ ⇒ False)›

parser_check ‹(case er_parse_recover (toks 0 [PNum, PPlus, PRP, PStar, PNum]) of
    ([e], _) ⇒ map fst (pe_stack e) = [Tm PPlus, Nt ''E''] | _ ⇒ False)›

subsection ‹Without layout the chains are const‹Any›, and the simple driver runs›

parser_check ‹ii ep_parse_gram›

ML ‹
  val ths = Proof_Context.get_thms context "ep_parse_ptabs_def"
  val _ = assert (not (null ths))
›

text ‹The tables are those of the restricted grammar, the text is about the grammar.›

value ‹case er_parse_diag (toks 0 [PNum, PPlus, PPlus]) of
    Inl e ⇒ perr_render er_parse_info (λ_. '''') e | _ ⇒ ''''›

parser_check ‹case er_parse_diag (toks 0 [PNum, PPlus, PPlus]) of
    Inl e ⇒ sym_text er_parse_info (fst (pe_stack e ! 1)) = ''E''
  | _ ⇒ False›

subsection ‹Layout›

grammar el =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar›
  precedence left "*" > left "+"
  productions
    E :: ‹p_exp›
      = E⇧= "+"⇧> E⇧= ⇒ ‹λa b. Add a b›
      | E⇧= "*"⇧> E⇧= ⇒ ‹λa b. Mul a b›
      | PNum⇧≥ ⇒ ‹λ_. N›

parser el_parse for el

parser_check ‹el_parse (toks 0 [PNum, PPlus, PNum, PStar, PNum]) = Some (Add N (Mul N N))›

subsection ‹Unordered levels stay ambiguous, the report says so under the names of the grammar›

grammar eu =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar› and "^" = ‹PPow› and "-" = ‹PMinus›
  precedence left "*" > left "+"
  precedence right "^" > left "-"
  productions
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | E "^" E ⇒ ‹λa b. Pow a b›
      | E "-" E ⇒ ‹λa b. Sub a b›
      | PNum ⇒ ‹λ_. N›

parser eu_parse for eu

subsection ‹A relation family stays out of it›

grammar (relation) ev =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar›
  precedence left "*" > left "+"
  productions
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | PNum ⇒ ‹λ_. N›

parser ev_parse for ev

ML ‹val _ = @{thms ev_parse.sound ev_parse.complete}›

subsection ‹Errors of the declarations›

ML ‹
fun command_error src =
  let val thy = theory in
    (fold Toplevel.command_exception (Outer_Syntax.parse_text thy (K {skip_theory = false, theory = thy}) Position.none src)
       (Toplevel.make_state (SOME (Context.Theory thy))); NONE)
    handle Runtime.EXCURSION_FAIL (exn, _) => SOME (Runtime.exn_message exn)
  end;

fun decl_grammar decls alts =
  "grammar bad = tokens p_tok terminals \"+\" = PPlus and \"*\" = PStar " ^ decls ^
  " productions E :: p_exp = E \"+\" E ⇒ ‹λa b. Add a b›" ^
  " | E \"*\" E ⇒ ‹λa b. Mul a b› | PNum ⇒ ‹λ_. N›" ^ alts;

fun rejected frag decls alts =
  (case command_error (decl_grammar decls alts) of
    NONE => error ("accepted: " ^ decls ^ alts)
  | SOME msg =>
      if String.isSubstring frag msg then () else error ("unexpected: " ^ msg));
›

ML ‹
  val ok = decl_grammar "precedence left \"*\" > left \"+\"" "";
  val _ = assert (is_none (command_error ok));
  val _ = rejected "cyclic" "precedence left \"*\" > left \"+\" precedence left \"+\" > left \"*\"" "";
  val _ = rejected "is both" "precedence left \"+\" precedence right \"+\"" "";
  val _ = rejected "no production goes by" "precedence left \"%\"" "";
  val _ = rejected "not one of" "precedence sideways \"+\"" "";
  val _ = rejected "forbid: position 9" "precedence left \"+\" forbid \"+\" @ 9 right \"*\"" "";
  val _ = rejected "is not one of direct" "precedence left \"+\" forbid \"+\" @ 0 sideways \"*\"" "";
  val _ = rejected "cannot have declarations" "precedence left \"+\"" " | E ⇒ ‹λe. e›";
›

text ‹A ‹(prec NAME)› without any declaration is accepted and ignored (expected warning).›

ML ‹
  assert (is_none (command_error (decl_grammar "" " | \"*\" E (prec UMINUS) ⇒ ‹λa. Neg a›")))
›

subsection ‹What the command prints about ‹G'››

text ‹The messages of a command, run on a copy of the theory. The output hooks are
  wrapped, not replaced, so everything is still printed; kept are the messages that
  start with the given prefix.›

ML ‹
fun command_output thy prefix src =
  let
    val buf = Synchronized.var "command_output" ([]: string list);
    fun keep orig xs =
      let val s = XML.content_of (YXML.parse_body (implode xs)) in
        (if String.isPrefix prefix s then Synchronized.change buf (cons s) else (); orig xs)
      end;
    val (w0, l0) = (! Private_Output.warning_fn, ! Private_Output.writeln_fn);
    fun restore () = (Private_Output.warning_fn := w0; Private_Output.writeln_fn := l0);
    val _ = (Private_Output.warning_fn := keep w0; Private_Output.writeln_fn := keep l0);
    val res =
      Exn.capture (fn () =>
        fold Toplevel.command_exception (Outer_Syntax.parse_text thy (K {skip_theory = false, theory = thy}) Position.none src)
          (Toplevel.make_state (SOME (Context.Theory thy)))) ();
    val _ = restore ();
    val _ = Exn.release res;
  in rev (Synchronized.value buf) end;
›

text ‹Two lines that do not relate ‹"+"› and ‹"*"›, which stay ambiguous.›

grammar eh =
  tokens ‹p_tok›
  terminals "+" = ‹PPlus› and "*" = ‹PStar›
  precedence left "+"
  precedence left "*"
  productions
    E :: ‹p_exp›
      = E "+" E ⇒ ‹λa b. Add a b›
      | E "*" E ⇒ ‹λa b. Mul a b›
      | PNum ⇒ ‹λ_. N›

text ‹The report names the productions of the grammar. A state whose evidence is two
  copies of one production of ‹G'›, or a unit chain of ‹G'›, prints them as such:
  both copies map back to the production of ‹eh› they come from, so the two sides
  read alike, and the example below the line is what tells them apart. No chain carries
  its ‹=›, and each state has one line. Under ‹[[grammar_timing]]› the sizes are
  those of ‹G'›, the grammar the tables are built from: 6 productions, where ‹eh› has 3.
  The two commands run one after the other, as each wraps the output hooks.›

ML ‹
  val report = command_output theory "parser: ‹eh_t›" "parser eh_t for eh";
  val _ = assert (report = [cat_lines
    ["parser: ‹eh_t› (grammar ‹eh›, start ‹E›) has LR conflicts in 3 states (3 with a layout witness); ‹mdet› kept as an assumption on .complete",
     "state after ‹E \"+\" E \"*\" E›:",
     "  reduce/reduce on \"+\" \"*\":  reduce ‹E = E \"*\" E›  vs  reduce ‹E = E \"*\" E›",
     "  example ‹PNum \"+\" PNum \"*\" PNum ⋅ \"+\"›: two actions live (all tokens at column 0)",
     "state after ‹E \"+\" PNum›:",
     "  reduce/reduce on \"+\" \"*\":  reduce ‹E = PNum›  vs  reduce ‹E = PNum›",
     "  example ‹PNum \"+\" PNum ⋅ \"+\"›: two actions live (all tokens at column 0)",
     "state after ‹E \"*\" E›:",
     "  reduce/reduce on \"+\" \"*\":  reduce ‹E = E›  vs  reduce ‹E = E \"*\" E›",
     "  example ‹PNum \"*\" PNum ⋅ \"+\"›: two actions live (all tokens at column 0)"]]);
  val sizes = command_output theory "[parser] sizes" "declare [[grammar_timing]] parser eh_s for eh";
  val _ = assert (case sizes of
      [s] => String.isPrefix "[parser] sizes: productions = 6, nonterminals = 3, terminals = 3," s
    | _ => false);
›

end