Theory Regression_Tests

(* Author: Basil Fürer, Dmitriy Traytel *)

theory Regression_Tests
  imports TIGER_Grammar.LR_Parser Parser_Check
begin

section ‹Command-level regression tests›

definition tu :: ‹nat ⇒ 'tok ⇒ char list ⇒ ('tok, unit) token› where
  ‹tu i x u = ⦇tok = x, span = span.make 0 i 0 (length u) []⦈›

subsection ‹Aligned ‹do› blocks: unconditional completeness + layout›

datatype do_tok = DDo | DId

grammar (relation) do =
  tokens ‹do_tok›
  terminals "do" = ‹DDo›
  productions
      Expr :: ‹unit›
        = DId⇧>          ⇒ ‹λ_. ()›
        | "do"⇧> BStmts⇧> ⇒ ‹λ_. ()›
    and
      BStmts :: ‹unit›
        = BExpr⇧=         ⇒ ‹λ_. ()›
        | BStmts⇧= BExpr⇧= ⇒ ‹λ_ _. ()›
    and
      BExpr :: ‹unit›
        = DId⇧=          ⇒ ‹λ_. ()›
        | "do"⇧= BStmts⇧> ⇒ ‹λ_. ()›

parser do_parse2 for do

text ‹Accepted and rejected layouts of cite‹‹Sect.~5.7› in "adams2013"›.›

parser_check ‹do_parse2 [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x''] = Some ()›

parser_check ‹do_parse2
  [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 2 DId ''y''] = None›

parser_check ‹do_parse2
  [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 4 DId ''y''] = Some ()›

parser_check ‹do_parse2
  [tu 1 DDo ''do'', tu 4 DDo ''do'', tu 7 DId ''x'', tu 7 DId ''y''] = Some ()›

text ‹ The emitted theorems are hypothesis-free: no mentions of const‹mdet› or const‹fresh_name›.›

lemma ‹w ∈ ilang do ⟹ ∃x. do_parse2 w = Some x›
  by (fact do_parse2.complete_lang)

text ‹With ‹(relation)›, ‹.sound› / ‹.complete› are stated against the
  relation of the start symbol, also hypothesis-free: the accept/reduce
  check const‹acc_conflicts› is empty as well.›

lemma ‹do_parse2 w = Some x ⟹ do_Expr 0 w x›
  by (fact do_parse2.sound)

lemma ‹do_Expr 0 w x ⟹ do_parse2 w = Some x›
  by (fact do_parse2.complete)

subsection ‹The accept/reduce check: a cycle through the start symbol›

text ‹const‹mdet› alone does not make the relational ‹.complete› true: the
  conflict report ignores the start production, so a grammar with
  ‹S ⇒⁺ S› passes it, while the relation assigns two values to one word
  and the driver returns the first parse.  const‹acc_conflicts› must be
  non-empty here, and the command keeps it as an assumption (expected
  warning).›

grammar (relation) cyc =
  tokens ‹do_tok›
  productions
      S :: ‹nat› = A ⇒ ‹λa. a + 1› | DId ⇒ ‹λ_. 0›
    and
      A :: ‹nat› = S ⇒ ‹λs. s›

parser cyc_parse for cyc

text ‹The code equation runs on the action table over the states, and
  numbers the tokens by a case distinction.›

ML ‹val _ = const_name‹cyc_parse_ptabs››
parser_check ‹cyc_parse_tnum DId = pnum cyc_parse_ptabs DId›

parser_check ‹acc_conflicts cyc ''!'' ≠ []›

parser_check ‹map (λ(_, prs, _, _). prs) (explain_acc cyc ''!'' (acc_conflicts cyc ''!'')) = [[2]]›

lemma cyc_two_values:
  ‹cyc_S [tu 1 DId ''x''] 0› ‹cyc_S [tu 1 DId ''x''] 1›
proof -
  show 0: ‹cyc_S [tu 1 DId ''x''] 0› unfolding tu_def by (intro cyc.intros)
  have ‹cyc_S [tu 1 DId ''x''] (0 + 1)› by (intro cyc.intros 0)
  then show ‹cyc_S [tu 1 DId ''x''] 1› by simp
qed

parser_check ‹cyc_parse [tu 1 DId ''x''] = Some 0›

text ‹So ‹cyc_S w x ⟹ cyc_parse w = Some x› is false, and ‹.complete› still
  carries the check as a hypothesis:›

lemma ‹acc_conflicts cyc ''!'' = [] ⟹ cyc_S w x ⟹ cyc_parse w = Some x›
  by (fact cyc_parse.complete)

text ‹The simple driver on integer indices (‹parser_int_tables›): the same
  parser, whose code equation runs on the integer tables ‹cyc_parse_int_ztabs›.›

declare [[parser_int_tables]]
parser cyc_parse_int for cyc
declare [[parser_int_tables = false]]

ML ‹val _ = const_name‹cyc_parse_int_ztabs››

parser_check ‹cyc_parse_int [tu 1 DId ''x''] = Some 0› ‹cyc_parse_int [tu 1 DDo ''do''] = None›

text ‹The simple driver on evaluated tables (‹parser_literal_tables›): the start
  state and the action table its code equation names are literals, so that exported
  code computes no table when it loads. Without diagnostics both come with the checks.›

declare [[parser_literal_tables]]
parser cyc_parse_lit for cyc
parser (no_diagnostics) cyc_parse_lit_nd for cyc
declare [[parser_literal_tables = false]]

ML ‹
  assert (forall (fn th => not (exists_Const (fn (c, _) =>
      member (op =) [const_name‹ptabs_of›, const_name‹st_find›] c) (Thm.prop_of th)))
    @{thms cyc_parse_lit_ptabs_def cyc_parse_lit_i0_def
      cyc_parse_lit_nd_ptabs_def cyc_parse_lit_nd_i0_def})
›

parser_check ‹cyc_parse_lit [tu 1 DId ''x''] = Some 0› ‹cyc_parse_lit [tu 1 DDo ''do''] = None›
  ‹cyc_parse_lit_nd [tu 1 DId ''x''] = Some 0› ‹cyc_parse_lit_nd [tu 1 DDo ''do''] = None›

subsection ‹The rejection path: an ambiguous grammar keeps ‹mdet››

text ‹The ISWIM productions of cite‹‹Fig.~2› in "adams2013"›, with ‹WExpr›
  for the desugared ‹|expr|›. They apply Landin's offside rule
  cite‹‹Sect.~6, item~(4c)› in "landin1966-next-700"› to the right-hand side of
  ‹where› only.›

datatype iswim_tok = IWhere | IPlus | IMinus | IEq | ILP | IRP | IId

grammar (relation) iswim =
  tokens ‹iswim_tok›
  terminals
    "where" = ‹IWhere› and "+" = ‹IPlus› and "-" = ‹IMinus› and
    "="     = ‹IEq›    and "(" = ‹ILP›   and ")" = ‹IRP›
  productions
      Expr :: ‹unit›
        = Expr⇧= "where"⇧≥ IId⇧≥ "="⇧≥ WExpr⇧≥  ⇒ ‹λ_ _ _. ()›
        | Expr⇧= "+"⇧≥ Expr⇧=                 ⇒ ‹λ_ _. ()›
        | "-"⇧≥ Expr⇧=                       ⇒ ‹λ_. ()›
        | "("⇧≥ Expr ")"⇧≥                  ⇒ ‹λ_. ()›
        | IId⇧≥                             ⇒ ‹λ_. ()›
    and
      WExpr :: ‹unit›
        = WExpr⇧= "where"⇧≥ IId⇧≥ "="⇧≥ WExpr⇧≥  ⇒ ‹λ_ _ _. ()›
        | WExpr⇧= "+"⇧≥ Expr⇧=                 ⇒ ‹λ_ _. ()›
        | "-"⇧= Expr⇧=                        ⇒ ‹λ_. ()›
        | "("⇧= Expr ")"⇧≥                   ⇒ ‹λ_. ()›
        | IId⇧=                              ⇒ ‹λ_. ()›

parser iswim_parse2 for iswim

text ‹‹iswim› is genuinely ambiguous, the check
  fires, and the command must NOT emit an unconditional ‹.complete›:
  const‹mdet› stays as an assumption.  Soundness is unconditional
  regardless.

  The driver still parses unambiguous ISWIM inputs (soundly):
  ‹- x› at columns 1 3.›

parser_check ‹iswim_parse2 [tu 1 IMinus ''-'', tu 3 IId ''x''] = Some ()›


subsection ‹Haskell ‹case› layout: unconditional›

text ‹The ‹case› productions of cite‹‹Fig.~5› in "adams2013"›. The
  Haskell report specifies layout by a function ‹L› that inserts braces and
  semicolons cite‹‹Sect.~10.3› in "marlow2010-haskell-report"›; the grammar
  states it directly, with no such pass.›

datatype hc_tok = HCase | HOf | HLC | HRC | HSemi | HId

grammar (relation) hask_case =
  tokens ‹hc_tok›
  terminals
    "case" = ‹HCase› and "of" = ‹HOf›   and
    "{"    = ‹HLC›   and "}"  = ‹HRC›   and ";" = ‹HSemi›
  productions
      Case = "case"⇧> Exp⇧= "of"⇧> AltBlock⇧= ⇒ ‹λ_ _. ()›
    and
      Exp = HId⇧≥ ⇒ ‹λ_. ()›
    and
      AltBlock :: ‹unit›
        = "{"⇧> Alts "}" ⇒ ‹λ_. ()›
        | AltLayout⇧>      ⇒ ‹λ_. ()›
    and
      AltLayout :: ‹unit›
        = Alts⇧=            ⇒ ‹λ_. ()›
        | AltLayout⇧= Alts⇧= ⇒ ‹λ_ _. ()›
    and
      Alts :: ‹unit›
        = HId⇧=            ⇒ ‹λ_. ()›
        | Alts⇧= ";"⇧≥ HId⇧= ⇒ ‹λ_ _. ()›

parser hask_case_parse2 for hask_case

parser_check ‹hask_case_parse2
  [tu 1 HCase ''case'', tu 6 HId ''x'', tu 8 HOf ''of'',
   tu 3 HId ''A'', tu 3 HId ''B''] = Some ()›

parser_check ‹hask_case_parse2
  [tu 1 HCase ''case'', tu 6 HId ''x'', tu 8 HOf ''of'',
   tu 3 HId ''A'', tu 4 HId ''B''] = None›

subsection ‹Python suites: unconditional›

text ‹Adapted from cite‹‹Sect.~3.3.2› in "adams2013"›.›

datatype py_tok = PWhile | PColon | PId

grammar (relation) py_suite =
  tokens ‹py_tok›
  terminals "while" = ‹PWhile› and ":" = ‹PColon›
  productions
      WhileStmt = "while"⇧> Test⇧= ":"⇧> Suite⇧= ⇒ ‹λ_ _. ()›
    and
      Test = PId⇧≥ ⇒ ‹λ_. ()›
    and
      Suite = Block⇧> ⇒ ‹λ_. ()›
    and
      Block :: ‹unit›
        = BStatement⇧=        ⇒ ‹λ_. ()›
        | Block⇧= BStatement⇧= ⇒ ‹λ_ _. ()›
    and
      BStatement = PId⇧= ⇒ ‹λ_. ()›

parser py_parse2 for py_suite

parser_check ‹py_parse2
  [tu 1 PWhile ''while'', tu 7 PId ''x'', tu 8 PColon '':'',
   tu 3 PId ''y'', tu 3 PId ''z''] = Some ()›

parser_check ‹py_parse2
  [tu 1 PWhile ''while'', tu 7 PId ''x'', tu 8 PColon '':'',
   tu 3 PId ''y'', tu 4 PId ''z''] = None›

text ‹Both are hypothesis-free (‹.complete› theorems are unconditional).›

lemma ‹w ∈ ilang hask_case ⟹ ∃x. hask_case_parse2 w = Some x›
  by (fact hask_case_parse2.complete_lang)

lemma ‹w ∈ ilang py_suite ⟹ ∃x. py_parse2 w = Some x›
  by (fact py_parse2.complete_lang)

lemma ‹py_suite_WhileStmt 0 w x ⟹ py_parse2 w = Some x›
  by (fact py_parse2.complete)

lemma ‹py_parse2 w = Some x ⟹ py_suite_WhileStmt 0 w x›
  by (fact py_parse2.sound)

subsection ‹Extensible tokens›

text ‹The token record fixes only const‹tok› and const‹span›. The
  ⬚‹tokens› clause names the (ground) token record type: the plain
  ‹('tok, 'ch) token›, or a client extension of it whose fields are then
  available to the semantic actions along with const‹tok› and
  const‹span›. A token class type ‹T›, as in the grammars above,
  abbreviates ‹(T, unit) token›.›

datatype trivia = Whitespace | Comment

record py_token = ‹(py_tok, nat) token› +
  trailing :: ‹(trivia × nat span) list›

datatype out = Foo ‹(trivia × nat span) list› | Bar

grammar (relation) t_ext =
  tokens ‹py_token›
  terminals "while" = PWhile and ":" = ‹PColon›
  productions
    X = Y | "while" ⇒ ‹Bar›
  and
    Y = ":" PId ⇒ ‹Foo ∘ trailing›

lemma ‹(∃x. t_ext_X w x) = (w ∈ ilang t_ext)›
  by (fact t_ext.lang)

parser t_ext_parse for t_ext

parser_check ‹t_ext_parse [⦇tok = PColon, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = []⦈, trailing = []⦈,
                    ⦇tok = PId, span = ⦇s_line = 0, s_col = 2, s_off = 2, s_len = 1, s_txt = []⦈,
                     trailing = [(Comment, ⦇s_line = 0, s_col = 4, s_off = 4, s_len = 3, s_txt = []⦈)]⦈]
       = Some (Foo [(Comment, ⦇s_line = 0, s_col = 4, s_off = 4, s_len = 3, s_txt = []⦈)])›

text ‹The plain record with a span payload, spelled out.›

grammar (relation) t_span =
  tokens ‹(py_tok, nat) token›
  terminals "while" = PWhile and ":" = ‹PColon›
  productions
    X = Y | "while" ⇒ ‹0›
  and
    Y :: ‹nat› = ":" PId ⇒ ‹λt. s_col (span t) + length (s_txt (span t))›

parser t_span_parse for t_span

parser_check ‹t_span_parse [⦇tok = PColon, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = [0]⦈⦈,
                     ⦇tok = PId, span = ⦇s_line = 0, s_col = 2, s_off = 2, s_len = 1, s_txt = [7, 7]⦈⦈]
       = Some 4›


subsection ‹Decoders without ‹(relation)››

text ‹⬚‹parser› needs only the grammar constant and the decoders,
  both of which every ⬚‹grammar› defines; the ‹(relation)›
  option is not required for it, and ‹.complete› is still hypothesis-free.›

grammar not =
  tokens bool
  productions X = ‹False› ⇒ ‹True› | ‹True› ⇒ ‹False›

parser parse_not for not

parser_check ‹parse_not [⦇tok = False, span = ⦇s_line = 0, s_col = 0, s_off = 0, s_len = 1, s_txt = []⦈⦈] = Some True›
  and ‹parse_not [] = None›

lemma ‹w ∈ ilang not ⟹ ∃x. parse_not w = Some x›
  by (fact parse_not.complete)



subsection ‹A terminal alternative listed before a nonterminal one›

datatype abc_tok = PA | PB | PC

grammar (relation) term_first =
  tokens ‹abc_tok›
  productions S :: ‹nat› = PA ⇒ ‹λ_. 0› | B ⇒ ‹λb. b›
    and B :: ‹nat› = PB ⇒ ‹λ_. 1›

parser term_first_parse for term_first

text ‹The relational forms unconditional:›

lemma ‹term_first_S w x ⟹ term_first_parse w = Some x›
  by (fact term_first_parse.complete)

lemma ‹term_first_parse w = Some x ⟹ term_first_S w x›
  by (fact term_first_parse.sound)


subsection ‹Unit self-loop›

grammar (relation) self_loop =
  tokens ‹abc_tok›
  productions S :: ‹nat› = S ⇒ ‹λs. s + 1› | PA ⇒ ‹λ_. 0›

lemma ‹(∃x. self_loop_S w x) = (w ∈ ilang self_loop)›
  by (fact self_loop.lang)


subsection ‹‹grammar› inside a locale›

locale loc begin

grammar (relation) g =
  tokens ‹abc_tok›
  productions S :: ‹nat› = PA ⇒ ‹λ_. 0› | B PB ⇒ ‹λb _. b + 1›
    and B :: ‹nat› = PB ⇒ ‹λ_. 1›

lemma ‹(∃x. g_S w x) = (w ∈ ilang g)›
  by (fact g.lang)

end


subsection ‹A duplicate production is rejected›

ML ‹
local
  fun alt v : Grammar_Common.alternative =
    ([(Grammar_Common.Ref ("PC", Position.none), NONE)],
     SOME (Input.string ("λ_. " ^ string_of_int v)));
  val dup : Grammar_Common.spec =
    {name = Binding.name "dup", tok_typ = SOME (Input.string "abc_tok"), terminals = [], prec = NONE,
     productions = [((Binding.name "S", SOME (Input.string "nat")), [alt 0, alt 1])]};
in
val _ =
  (Named_Target.theory_map (Grammar_Command.grammar_cmd [] dup) theory;
   error "duplicate production accepted")
  handle ERROR msg =>
    if String.isPrefix "Duplicate production" msg then ()
    else error ("unexpected: " ^ msg)
end
›

grammar (relation) one_alt =
  tokens ‹abc_tok›
  productions S :: ‹nat› = PC ⇒ ‹λ_. 7›

parser one_alt_parse for one_alt

lemma ‹one_alt_S w x ⟹ one_alt_parse w = Some x›
  by (fact one_alt_parse.complete)


subsection ‹Backend default, idempotence, input validation›

parser term_first_parse2 for term_first   ― ‹a second parser for the same grammar›

ML ‹
  val ctxt = context;
  val thy = Proof_Context.theory_of ctxt;
  (* registering a backend does not change the default *)
  val _ =
    Parser_Generators.default (Parser_Generators.register "pr_dummy" LR_Backend.lr_gen thy)
      = SOME "LR"
    orelse error "register changed the default backend";
  (* define_relation_of returns the existing family *)
  val (sem1, _) = Grammar_Defs.define_relation_of ("term_first", Position.none) ctxt;
  val (sem2, _) = Grammar_Defs.define_relation_of ("term_first", Position.none) ctxt;
  val _ =
    map fst (#preds sem1) = map fst (#preds sem2)
    orelse error "define_relation_of is not idempotent";
  (* inputs are validated against the grammar record *)
  val g1 = snd (Grammar_Common.check_grammar ctxt ("term_first", Position.none));
  val g2 = snd (Grammar_Common.check_grammar ctxt ("self_loop", Position.none));
  val _ =
    (Parser_Rel_Bridge.prove ctxt g2 (the (Grammar_Defs.lookup_rel ctxt g1));
     error "foreign predicate family accepted")
    handle ERROR msg =>
      String.isPrefix unchecked_name‹Parser_Rel_Bridge.prove› msg orelse error msg;
  val _ =
    (Grammar_Defs.decoder_of ctxt g1 "Nope"; error "unknown nonterminal accepted")
    handle ERROR msg =>
      String.isPrefix "decoder_of" msg orelse error msg;
›


subsection ‹Nonterminal names that used to collide with generated names›

grammar (relation) dec_clash =
  tokens ‹abc_tok›
  productions A :: ‹nat› = PA ⇒ ‹λ_. 0› | dec_A ⇒ ‹λx. x›
    and dec_A :: ‹nat› = PB ⇒ ‹λ_. 1›

parser dec_clash_parse for dec_clash

lemma ‹dec_clash_A w x ⟹ dec_clash_parse w = Some x›
  by (fact dec_clash_parse.complete)

text ‹The flat relation names can still collide across grammars (‹flat› with
  ‹A_B› and ‹flat_A› with ‹B› both give ‹flat_A_B›); that is reported up
  front.›

grammar (relation) flat =
  tokens ‹abc_tok›
  productions A_B :: ‹nat› = PA ⇒ ‹λ_. 0›

ML ‹
local
  val clash : Grammar_Common.spec =
    {name = Binding.name "flat_A", tok_typ = SOME (Input.string "abc_tok"), terminals = [], prec = NONE,
     productions =
      [((Binding.name "B", SOME (Input.string "nat")),
        [([(Grammar_Common.Ref ("PA", Position.none), NONE)], SOME (Input.string "λ_. 0"))])]};
in
val _ =
  (Named_Target.theory_map
     (Grammar_Command.grammar_cmd [Grammar_Command.Opt_Relation] clash) theory;
   error "relation name clash not detected")
  handle ERROR msg =>
    if String.isSubstring "already exists" msg then ()
    else error ("unexpected: " ^ msg)
end
›

subsection ‹‹parser› inside a locale with assumptions›

locale box = fixes alive :: bool assumes ‹alive ⟶ exp 1 + pi ∈ range real_of_rat›

grammar (in box) (relation) idk =
  tokens do_tok productions X = DId ⇒ ‹λ_. alive›

parser (in box) parse_sealed for idk

global_interpretation box False by unfold_locales simp

parser_check ‹parse_sealed [tu 0 DId ''F''] = Some False›

text ‹The decoders of a locale with parameters are applied constants, not bare
  ones; the totality premise must still be discharged.›

lemma ‹idk_X w x ⟹ parse_sealed w = Some x›
  by (fact parse_sealed.complete)


subsection ‹Long right-hand sides›

text ‹Decoder totality and both bridges were super-linear in the length of rhs:›

grammar (relation) long_rhs =
  tokens ‹abc_tok›
  productions S :: ‹nat› = PA PB PC PA PB PC PA PB PC PA PB PC ⇒ ‹λ_ _ _ _ _ _ _ _ _ _ _ _. 12›

parser long_rhs_parse for long_rhs

lemma ‹long_rhs_S w x ⟹ long_rhs_parse w = Some x›
  by (fact long_rhs_parse.complete)


subsection ‹Unit self-loops with identity actions›

text ‹The intro of ‹S = S ⇒ ‹λn. n›› is ‹id_loop_S w x ⟹ id_loop_S w x›; with it in the
  classical rule set, the depth-first search closing ‹dec_sound› never
  returned (the ‹parser› command hung after its ‹mdet› warning).  Such
  intros are dropped from the rule set: the node they describe is closed by
  the induction hypothesis.  The grammar is ambiguous (every derivation can
  be extended through the loops), so both checks fire: expected warnings,
  a reduce/reduce conflict at end of input after ‹A› and an accept/reduce
  conflict after ‹S›.›

grammar (relation) id_loop =
  tokens ‹abc_tok›
  productions S :: ‹nat› = S ⇒ ‹λn. n› | A ⇒ ‹λ_. 0›
    and A :: ‹unit› = A ⇒ ‹λu. u› | ⇒ ‹()›

parser id_loop_parse for id_loop

lemma ‹id_loop_parse w = Some x ⟹ id_loop_S w x›
  by (fact id_loop_parse.sound)


subsection ‹A unit self-loop under a relation keeps the relational forms›

text ‹Under ‹^>› the loop's intro is ‹gt_loop_A j w x ⟹ i < j ⟹ gt_loop_A i w x›:
  not circular, and the only rule closing that node of ‹dec_sound›.  The
  bridge keeps it out of the classical rule set and applies it once when the
  search fails; dropping it, as for ‹id_loop›, lost the relational forms.
  Expected warning: an accept/reduce conflict (a cycle through the start
  symbol).›

grammar (relation) gt_loop =
  tokens ‹abc_tok›
  productions A :: ‹nat› = A^> ⇒ ‹λn. n› | PA ⇒ ‹λ_. 0›

parser gt_loop_parse for gt_loop

lemma ‹gt_loop_parse w = Some x ⟹ gt_loop_A 0 w x›
  by (fact gt_loop_parse.sound)

lemma ‹acc_conflicts gt_loop ''!'' = [] ⟹ gt_loop_A 0 w x ⟹ gt_loop_parse w = Some x›
  by (fact gt_loop_parse.complete)


subsection ‹A unit self-loop reduce at end of input terminates›

text ‹After ‹B = PB› the frame offers ‹B = B› before ‹C = B›; that reduce
  rebuilds the frame it popped, and the fixed-point driver used to run forever
  on ‹PB›.  Its code equation (‹drun_hist›) stops at the repeated
  configuration and returns const‹None›.  Expected warning: a
  reduce/reduce conflict at end of input, so ‹mdet› stays on ‹.complete›.›

grammar (relation) uloop =
  tokens ‹abc_tok›
  productions S :: ‹nat› = C ⇒ ‹λc. c›
    and B :: ‹nat› = B ⇒ ‹λn. n› | PB ⇒ ‹λ_. 0›
    and C :: ‹nat› = B ⇒ ‹λb. b›

parser uloop_parse for uloop

parser_check ‹uloop_parse [tu 1 PB ''x''] = None›

lemma ‹mdet uloop ''!'' ⟹ uloop_S w x ⟹ uloop_parse w = Some x›
  by (fact uloop_parse.complete)


subsection ‹A free variable in an action is rejected up front›

text ‹‹S = PA ⇒ ‹λ_. n›› with ‹n› not fixed used to reach the function package
  (“Variable "n" occurs on right hand side only” about the decoder equation).
  The fixes of a locale (‹box› above) and of an unnamed context stay legal.›

ML ‹
local
  val spec : Grammar_Common.spec =
    {name = Binding.name "free_var", tok_typ = SOME (Input.string "abc_tok"), terminals = [], prec = NONE,
     productions =
      [((Binding.name "S", SOME (Input.string "nat")),
        [([(Grammar_Common.Ref ("PA", Position.none), NONE)],
          SOME (Input.string "λ_. n"))])]};
in
val _ =
  (Named_Target.theory_map (Grammar_Command.grammar_cmd [] spec) theory;
   error "free variable in an action accepted")
  handle ERROR msg =>
    if String.isPrefix "Free variable \"n\" in the action of production" msg then ()
    else error ("unexpected: " ^ msg)
end
›

context fixes k :: nat begin

grammar (relation) fixed_k =
  tokens ‹abc_tok›
  productions S :: ‹nat› = PA ⇒ ‹λ_. k›

lemma ‹(∃x. fixed_k_S w x) = (w ∈ ilang fixed_k)›
  by (fact fixed_k.lang)

end


subsection ‹A non-ground carrier ascription names the ascription›

text ‹‹S :: ‹'a list› = …› used to say “ascribe the type” although the type was
  ascribed; it now says that the ascription has type variables.›

ML ‹
local
  val spec : Grammar_Common.spec =
    {name = Binding.name "nonground", tok_typ = SOME (Input.string "abc_tok"), terminals = [], prec = NONE,
     productions =
      [((Binding.name "S", SOME (Input.string "'a list")),
        [([(Grammar_Common.Ref ("PA", Position.none), NONE)], SOME (Input.string "λ_. []"))])]};
in
val _ =
  (Named_Target.theory_map (Grammar_Command.grammar_cmd [] spec) theory;
   error "non-ground carrier ascription accepted")
  handle ERROR msg =>
    if String.isPrefix "Carrier of nonterminal \"S\" is not ground: the ascribed type" msg
    then () else error ("unexpected: " ^ msg)
end
›


subsection ‹Two spellings of one token value are one terminal›

text ‹Terminals are identified by their evaluated token value, not by their
  spelling: ‹‹1›› and ‹‹Suc 0›› are one terminal (with a warning), so two
  alternatives that differ only in that spelling are a duplicate production,
  and a grammar that keeps them apart gets its relation bridged.  Before, the
  relation had two intros for the word ‹[1]› and the ‹parser› command fell back
  to the language forms.›

ML ‹
local
  fun alt toks act =
    (map (fn s => (Grammar_Common.Tok (Input.string s), NONE)) toks,
     SOME (Input.string act));
  val spec : Grammar_Common.spec =
    {name = Binding.name "spelling_dup", tok_typ = SOME (Input.string "nat"), terminals = [], prec = NONE,
     productions =
      [((Binding.name "S", SOME (Input.string "nat")),
        [alt ["1"] "0", alt ["Suc 0"] "1"])]};
in
val _ =
  (Named_Target.theory_map (Grammar_Command.grammar_cmd [] spec) theory;
   error "two spellings of one token accepted as distinct alternatives")
  handle ERROR msg =>
    if String.isPrefix "Duplicate production" msg then ()
    else error ("unexpected: " ^ msg)
end
›

grammar (relation) spelling =
  tokens ‹nat›
  productions S :: ‹nat› = ‹1› ⇒ ‹0› | ‹Suc 0› ‹2› ⇒ ‹1›

parser spelling_parse for spelling

lemma ‹spelling_S w x ⟹ spelling_parse w = Some x›
  by (fact spelling_parse.complete)

parser_check ‹spelling_parse [tu 0 (Suc 0) ''F'', tu 1 2 ''F''] = Some 1›


subsection ‹Many nonterminals›

text ‹The three tree inductions (completeness, decoder totality, dec_sound)
  were quadratic in the number of nonterminals: an n-way conjunction as
  the invariant.  They are stated through a root-indexed selector now
  (ML_structure‹Grammar_Ptree_Induct›), one body per production case.›

grammar (relation) nt_chain =
  tokens ‹abc_tok›
  productions
      N1 :: ‹nat› = PA N2 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N2 :: ‹nat› = PA N3 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N3 :: ‹nat› = PA N4 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N4 :: ‹nat› = PA N5 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N5 :: ‹nat› = PA N6 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N6 :: ‹nat› = PA N7 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N7 :: ‹nat› = PA N8 ⇒ ‹λ_ x. Suc x› | PB ⇒ ‹λ_. 0›
  and N8 :: ‹nat› = PA ⇒ ‹λ_. 1› | PB ⇒ ‹λ_. 0›

parser nt_chain_parse for nt_chain

lemma ‹nt_chain_N1 w x ⟹ nt_chain_parse w = Some x›
  by (fact nt_chain_parse.complete)

parser_check ‹nt_chain_parse [tu 0 PA ''F'', tu 1 PA ''F'', tu 2 PB ''F''] = Some 2›

subsection ‹Several start symbols for one grammar›

text ‹Terms and types contain each other (‹lam x : Ty . Tm›, ‹{ Tm }›);
  ‹TyFile›, an aligned block of declarations, is unreachable from the start
  ‹Tm› (the expected warning of ‹grammar›).  One ‹parser› command emits a
  parser per start.›

datatype toy_tok = TLam | TColon | TDot | TArr | TLP | TRP | TLB | TRB | TId

datatype tm = Var nat | App tm tm | Lam nat ty tm
     and ty = TV nat | Arr ty ty | Sing tm

grammar (relation) toy =
  tokens ‹toy_tok›
  terminals
    "lam" = ‹TLam› and ":" = ‹TColon› and "." = ‹TDot› and "->" = ‹TArr› and
    "(" = ‹TLP›  and ")" = ‹TRP›    and "{" = ‹TLB›  and "}" = ‹TRB›
  productions
      Tm :: ‹tm›
        = Apps
        | "lam" TId ":" Ty "." Tm ⇒ ‹λx t b. Lam (s_col (span x)) t b›
    and
      Apps :: ‹tm› = Atom | Apps Atom ⇒ ‹App›
    and
      Atom :: ‹tm› = TId ⇒ ‹λx. Var (s_col (span x))› | "(" Tm ")" ⇒ ‹λt. t›
    and
      Ty :: ‹ty› = TAtom | TAtom "->" Ty ⇒ ‹Arr›
    and
      TAtom :: ‹ty›
        = TId ⇒ ‹λx. TV (s_col (span x))›
        | "{" Tm "}" ⇒ ‹Sing›
        | "(" Ty ")" ⇒ ‹λt. t›
    and
      TyFile :: ‹(nat × ty) list› = Decls
    and
      Decls :: ‹(nat × ty) list›
        = Decl⇧=         ⇒ ‹λd. [d]›
        | Decls⇧= Decl⇧= ⇒ ‹λds d. ds @ [d]›
    and
      Decl :: ‹nat × ty› = TId⇧= ":"⇧> Ty⇧> ⇒ ‹λx t. (s_col (span x), t)›

parser (no_diagnostics) toy_parse for toy
  and toy_parse_ty for toy (Ty)
  and toy_parse_file for toy (TyFile)

text ‹Each entry parses from its own start: ‹x y› is a term, not a type, ‹a -> b›
  a type, not a term, and the two nest through ‹{ … }› and ‹lam›.›

parser_check ‹toy_parse [tu 1 TId ''x'', tu 3 TId ''y''] = Some (App (Var 1) (Var 3))›

parser_check ‹toy_parse_ty [tu 1 TId ''x'', tu 3 TId ''y''] = None›

parser_check ‹toy_parse_ty [tu 1 TId ''a'', tu 3 TArr ''->'', tu 6 TId ''b''] =
    Some (Arr (TV 1) (TV 6))›

parser_check ‹toy_parse [tu 1 TId ''a'', tu 3 TArr ''->'', tu 6 TId ''b''] = None›

parser_check ‹toy_parse_ty [tu 1 TLB ''{'', tu 2 TId ''f'', tu 4 TId ''x'', tu 5 TRB ''}'',
    tu 7 TArr ''->'', tu 10 TId ''a''] = Some (Arr (Sing (App (Var 2) (Var 4))) (TV 10))›

parser_check ‹toy_parse [tu 1 TLam ''lam'', tu 5 TId ''x'', tu 7 TColon '':'', tu 9 TLB ''{'',
    tu 10 TId ''y'', tu 11 TRB ''}'', tu 13 TDot ''.'', tu 15 TId ''x''] =
    Some (Lam 5 (Sing (Var 10)) (Var 15))›

text ‹A ‹TyFile› is a block of aligned declarations; a misaligned line is rejected.›

parser_check ‹toy_parse_file [tu 1 TId ''x'', tu 3 TColon '':'', tu 5 TId ''a'',
    tu 1 TId ''y'', tu 3 TColon '':'', tu 5 TId ''b'', tu 7 TArr ''->'', tu 10 TId ''c''] =
    Some [(1, TV 5), (1, Arr (TV 5) (TV 10))]›

parser_check ‹toy_parse_file [tu 1 TId ''x'', tu 3 TColon '':'', tu 5 TId ''a'',
    tu 2 TId ''y'', tu 4 TColon '':'', tu 6 TId ''b'', tu 8 TArr ''->'', tu 11 TId ''c''] =
    None›

parser_check ‹toy_parse_file [tu 1 TId ''x'', tu 3 TId ''y''] = None›

text ‹The relational forms are stated against the relation of each start,
  without hypotheses.›

lemma ‹toy_parse_ty w = Some x ⟹ toy_Ty 0 w x›
  by (fact toy_parse_ty.sound)

lemma ‹toy_Ty 0 w x ⟹ toy_parse_ty w = Some x›
  by (fact toy_parse_ty.complete)

lemma ‹toy_parse_file w = Some x ⟹ toy_TyFile 0 w x›
  by (fact toy_parse_file.sound)

lemma ‹toy_TyFile 0 w x ⟹ toy_parse_file w = Some x›
  by (fact toy_parse_file.complete)

lemma ‹w ∈ ilang (toy⦇istart := ''Ty''⦈) ⟹ ∃x. toy_parse_ty w = Some x›
  by (fact toy_parse_ty.complete_lang)

text ‹The entries share the grammar, its decoders and its relation family: an entry
  runs ‹dparse› on the grammar with another start and decodes with the grammar's
  decoder of that start, and defines nothing but its parse constant and its tables.›

lemma ‹toy_parse_ty ≡ λw. Option.bind (dparse (toy⦇istart := ''Ty''⦈) ''!'' w) toy__dec_Ty›
  by (fact toy_parse_ty_def)

lemma ‹toy_parse_file ≡
    λw. Option.bind (dparse (toy⦇istart := ''TyFile''⦈) ''!'' w) toy__dec_TyFile›
  by (fact toy_parse_file_def)

ML ‹
  val consts = map #1 (#constants (Consts.dest (Sign.consts_of theory)));
  fun own p = filter (fn c => Long_Name.base_name c = p orelse
    String.isPrefix (p ^ "_") (Long_Name.base_name c)) consts |> map Long_Name.base_name;
  val tables = ["states", "gtab", "redtab", "i0", "stab", "vtab", "vktab", "sinit", "sclos", "tnum"];
  val _ =
    forall (fn p => eq_set (op =) (own p, p :: map (fn t => p ^ "_" ^ t) tables))
      ["toy_parse_ty", "toy_parse_file"]
    orelse error "an entry defines more than its parse constant and its tables";
›

text ‹Without the option a parser has its diagnostics, which is the default.›

ML ‹val _ = const_name‹do_parse2_diag››

text ‹A start that is not a nonterminal, a name declared twice, and a second
  grammar in one command are rejected before anything is defined.›
ML ‹
local
  fun run entries =
    Named_Target.theory_map (Parser_Generators.define_cmd NONE entries) theory;
  val toy = ("toy", Position.none);
in
val _ =
  (run [(binding‹toy_nope›, toy, SOME ("Nope", Position.none))];
   error "unknown start accepted")
  handle ERROR msg =>
    if String.isPrefix "parser \"toy_nope\": \"Nope\" is not a nonterminal of grammar \"toy\"" msg
    then () else error ("unexpected: " ^ msg)
val _ =
  (run [(binding‹toy_twice›, toy, NONE),
        (binding‹toy_twice›, toy, SOME ("Ty", Position.none))];
   error "a name declared twice accepted")
  handle ERROR msg =>
    if String.isPrefix "parser \"toy_twice\": declared twice in one command" msg
    then () else error ("unexpected: " ^ msg)
val _ =
  (run [(binding‹toy_one›, toy, NONE), (binding‹do_two›, ("do", Position.none), NONE)];
   error "two grammars in one command accepted")
  handle ERROR msg =>
    if String.isPrefix "parser \"do_two\": grammar \"do\" is not the grammar \"toy\"" msg
    then () else error ("unexpected: " ^ msg)
end
›

text ‹Naming the grammar's own start is the default entry: the same definition,
  theorems and tables as ‹toy_parse›.›

parser toy_parse_tm for toy (Tm)

lemma ‹toy_parse_tm ≡ λw. Option.bind (dparse toy ''!'' w) toy__dec_Tm›
  by (fact toy_parse_tm_def)

lemma ‹toy_parse w = Some x ⟹ toy_Tm 0 w x›
  by (fact toy_parse.sound)

lemma ‹toy_parse_tm w = Some x ⟹ toy_Tm 0 w x›
  by (fact toy_parse_tm.sound)

lemma ‹toy_Tm 0 w x ⟹ toy_parse w = Some x›
  by (fact toy_parse.complete)

lemma ‹toy_Tm 0 w x ⟹ toy_parse_tm w = Some x›
  by (fact toy_parse_tm.complete)

lemma ‹toy_parse_tm w = Some x ⟹ w ∈ ilang toy›
  by (fact toy_parse_tm.sound_lang)

lemma ‹w ∈ ilang toy ⟹ ∃x. toy_parse_tm w = Some x›
  by (fact toy_parse_tm.complete_lang)

parser_check ‹toy_parse_tm_states = toy_parse_states›

text ‹The generator option applies to all entries.›

parser (LR) toy_parse_ty2 for toy (Ty) and toy_parse_tm2 for toy

lemma ‹toy_Ty 0 w x ⟹ toy_parse_ty2 w = Some x›
  by (fact toy_parse_ty2.complete)

lemma ‹toy_Tm 0 w x ⟹ toy_parse_tm2 w = Some x›
  by (fact toy_parse_tm2.complete)

text ‹An entry inside a locale with parameters (‹box› above).›

grammar (in box) (relation) idk2 =
  tokens do_tok productions X = Y DDo ⇒ ‹λy _. y› and Y = DId ⇒ ‹λ_. alive›

parser (in box) idk2_parse for idk2 and idk2_parse_y for idk2 (Y)

parser_check ‹idk2_parse_y [tu 0 DId ''F''] = Some False›

lemma ‹idk2_Y w x ⟹ idk2_parse_y w = Some x›
  by (fact idk2_parse_y.complete)


section ‹Check-level grammars›

text ‹Grammar records written out by hand, to pin the static check itself:
  it must fire on the ambiguous grammars and stay empty on the deterministic
  ones.›

subsection ‹Right-recursive with an ‹ε›-production, and LR(0)-clean›

definition tg1 :: ‹(string, string) is_cfg› where
  ‹tg1 = ⦇ iprods = [(''S'', [(Tm ''a'', Any), (Nt ''S'', Ge)]),
                     (''S'', [])],
           istart = ''S'', istart_ind = 0 ⦈›

definition tg2 :: ‹(string, string) is_cfg› where
  ‹tg2 = ⦇ iprods = [(''S'', [(Tm ''a'', Any), (Nt ''S'', Eq), (Tm ''b'', Any)]),
                     (''S'', [(Tm ''c'', Any)])],
           istart = ''S'', istart_ind = 0 ⦈›

parser_check ‹length (pr0_states tg1 ''!'') = 5›

parser_check ‹nullables tg1 = [''S'']› and ‹nullables tg2 = []›

parser_check ‹rlalr_conflicts tg1 ''!'' = []› and ‹rlalr_conflicts tg2 ''!'' = []›

subsection ‹Ambiguous: ‹E → E + E | x››

definition tg3 :: ‹(string, string) is_cfg› where
  ‹tg3 = ⦇ iprods = [(''E'', [(Nt ''E'', Any), (Tm ''+'', Any), (Nt ''E'', Any)]),
                     (''E'', [(Tm ''x'', Any)])],
           istart = ''E'', istart_ind = 0 ⦈›

parser_check ‹rlalr_conflicts tg3 ''!'' ≠ []›

subsection ‹The NQLALR pitfall›

text ‹After cite‹‹Sect.~5.1› in "deremer1982-lalr-lookahead"›: ‹S → aAc | bAd | agd | bgc, A → B, B → g› is LALR(1):
  ‹LA(g0, B → g) = {c}› and ‹LA(g1, B → g) = {d}›.  A state-merged
  NQLALR computation assigns ‹{c, d}› to both ‹g›-states and wrongly reports
  conflicts; the per-item cells keep the two halves apart.›

definition nqg :: ‹(string, string) is_cfg› where
  ‹nqg = ⦇ iprods =
     [(''S'', [(Tm ''a'', Any), (Nt ''A'', Any), (Tm ''c'', Any)]),
      (''S'', [(Tm ''b'', Any), (Nt ''A'', Any), (Tm ''d'', Any)]),
      (''S'', [(Tm ''a'', Any), (Tm ''g'', Any), (Tm ''d'', Any)]),
      (''S'', [(Tm ''b'', Any), (Tm ''g'', Any), (Tm ''c'', Any)]),
      (''A'', [(Nt ''B'', Any)]),
      (''B'', [(Tm ''g'', Any)])],
    istart = ''S'', istart_ind = 0 ⦈›

parser_check ‹lalr_conflicts nqg ''!'' = []› and ‹rlalr_conflicts nqg ''!'' = []›

subsection ‹Cross-anchor ambiguity›

text ‹‹S → T⋆;  T → A= b= | U= b>;  U → A=;  A → a>›.  The word
  ‹a@2 b@1› has two layout parses: ‹T› anchored at 1 (‹T → A b›) and at 0
  (‹T → U b›).  After reducing ‹A› the pooled frame carries the anchor set
  ‹{0, 1}›; the shift is live via anchor 1 and the reduce of ‹U → A› via
  anchor 0.  A comparison of the two sides at one shared anchor is blind to
  this; the item-relative check is not, and its explanation finds the witness.›

definition xag :: ‹(string, string) is_cfg› where
  ‹xag = ⦇ iprods =
     [(''S'', [(Nt ''T'', Any)]),
      (''T'', [(Nt ''A'', Eq), (Tm ''b'', Eq)]),
      (''T'', [(Nt ''U'', Eq), (Tm ''b'', Gt)]),
      (''U'', [(Nt ''A'', Eq)]),
      (''A'', [(Tm ''a'', Gt)])],
    istart = ''S'', istart_ind = 0 ⦈›

parser_check ‹rlalr_conflicts xag ''!'' ≠ []›

parser_check ‹list_ex (λ(_, _, _, _, _, w). w ≠ None)
         (explain_rp xag ''!'' (rlalr_conflicts xag ''!''))›

parser_check ‹explain_rp tg2 ''!'' (rlalr_conflicts tg2 ''!'') = []›

text ‹The cheaper levels of the explanation reach the same states: every
  reported pair of ‹xag› has a symbol path and its action pairs.›

parser_check ‹list_all (λ(_, _, path, prs). path ≠ None ∧ prs ≠ [])
         (explain_rp_brief xag ''!'' (rlalr_conflicts xag ''!''))›

subsection ‹LALR merging›

text ‹‹S → aEa | bEb | aFb | bFa; E → e; F → e› is LR(1) but not
  LALR(1): the merged state ‹{E → e·, F → e·}› pools the lookaheads of
  the ‹a›- and ‹b›-contexts, so the driver, which licenses by the merged
  cells, offers both reduces on the same lookahead: ‹mdet› fails, and the
  check, which inspects the very cells the driver licenses by, fires. In the
  terms of cite‹‹Sect.~7› in "deremer1982-lalr-lookahead"› this is an
  LALR-only reduce-reduce conflict: merging joins two distinct left contexts.›

definition pol :: ‹(string, string) is_cfg› where
  ‹pol = ⦇ iprods =
     [(''S'', [(Tm ''a'', Any), (Nt ''E'', Any), (Tm ''a'', Any)]),
      (''S'', [(Tm ''b'', Any), (Nt ''E'', Any), (Tm ''b'', Any)]),
      (''S'', [(Tm ''a'', Any), (Nt ''F'', Any), (Tm ''b'', Any)]),
      (''S'', [(Tm ''b'', Any), (Nt ''F'', Any), (Tm ''a'', Any)]),
      (''E'', [(Tm ''e'', Any)]),
      (''F'', [(Tm ''e'', Any)])],
    istart = ''S'', istart_ind = 0 ⦈›

parser_check ‹rlalr_conflicts pol ''!'' ≠ []›


subsection ‹The same checks without the oracle›

text ‹Every check above is compiled to ML, run, and its verdict trusted:
  ⬚‹parser_check› proves nothing, and ⬚‹by eval›
  closes its goal by ‹holds_by_evaluation›.
  ⬚‹code_simp› rewrites with the very same code equations inside
  the kernel instead, so it produces an ordinary theorem and trusts nothing
  beyond the simplifier.  Proving the checks both ways on one small grammar is
  an oracle-free confirmation, for this development's own code, that the
  generated ML computes what the code equations say --- in particular for
  const‹la_fix› and const‹acc_conflicts›, whose equations bind the
  automaton once for speed and are therefore not the ones a reader would write.

  It buys that only here.  const‹rlalr_conflicts› did not finish in 200 s on
  these same two productions, and it swallows interrupts, so a runaway cannot
  even be stopped by a timeout.  The four checks below, by contrast, cost 13 s
  by ⬚‹eval› --- most of it the fixed ML-compilation floor --- and
  25 s by ⬚‹code_simp›.  Keep this audit on ‹tg1›, keep
  const‹rlalr_conflicts› out of it, and keep the whole thing under a
  minute.›

lemma checks_by_eval:
  ‹nullables tg1 = [''S'']›
  ‹length (pr0_states tg1 ''!'') = 5›
  ‹length (la_fix tg1 ''!'') = 8›
  ‹acc_conflicts tg1 ''!'' = []›
  by eval+

lemma checks_by_code_simp:
  ‹nullables tg1 = [''S'']›
  ‹length (pr0_states tg1 ''!'') = 5›
  ‹length (la_fix tg1 ''!'') = 8›
  ‹acc_conflicts tg1 ''!'' = []›
  by code_simp+


section ‹Backend plumbing›

subsection ‹Fixed terminals sharing a constructor keep their spellings›

datatype kw_tok = Kw string | KNum

grammar (relation) kwg =
  tokens ‹kw_tok›
  terminals "if" = ‹Kw ''if''› and "then" = ‹Kw ''then''›
  productions
    S :: ‹nat› = "if" KNum "then" KNum ⇒ ‹λ_ _. 0›

ML ‹
  val ctxt = context;
  val g = snd (Grammar_Common.check_grammar ctxt ("kwg", Position.none));
  val _ =
    LR_Backend.string_of_tm ctxt g term‹Kw ''then''› = quote "then"
    andalso LR_Backend.string_of_tm ctxt g term‹Kw ''if''› = quote "if"
    orelse error "fixed terminals sharing a constructor are confused in reports";
›

subsection ‹Fixed variables named like the backend's constants›

context
  fixes xinit :: nat and st_find :: nat and rlalr_conflicts :: nat
begin

parser shadow_parse for term_first

lemma ‹term_first_S w x ⟹ shadow_parse w = Some x›
  by (fact shadow_parse.complete)

end

subsection ‹Several components›

text ‹The relation is defined by one inductive definition per strongly connected
  component of the nonterminals, lower components first: here ‹N›
  (not recursive), ‹E› and ‹T›, and ‹S›.  The soundness and the bridge
  proofs go through the components in the same order.›

datatype lay_tok = LX | LNum | LPlus | LSemi | LLP | LRP

grammar (relation) lay =
  tokens ‹lay_tok›
  productions
    S :: ‹nat list› = E LSemi S ⇒ ‹λe _ s. e # s› | E ⇒ ‹λe. [e]›
  and
    E :: ‹nat› = E LPlus T ⇒ ‹λa _ b. a + b› | T
  and
    T :: ‹nat› = N | LLP E LRP ⇒ ‹λ_ e _. e›
  and
    N :: ‹nat› = LX ⇒ ‹λ_. 1› | LNum ⇒ ‹λ_. 2›

ML ‹
  val g = snd (Grammar_Common.check_grammar context ("lay", Position.none));
  val _ =
    Grammar_Defs.components g = [["N"], ["E", "T"], ["S"]]
    orelse error "components of lay";
›

parser lay_parse for lay

parser_check ‹lay_parse [tu 1 LX ''x'', tu 2 LPlus ''+'', tu 3 LLP ''('', tu 4 LNum ''2'',
    tu 5 LRP '')'', tu 6 LSemi '';'', tu 7 LX ''x''] = Some [3, 1]›

lemma ‹lay_S w x ⟷ lay_parse w = Some x›
  using lay_parse.sound lay_parse.complete by blast

end