Theory Prec_Tests

(* Author: Basil Fürer *)

theory Prec_Tests
  imports TIGER_Grammar.LR_Prec_Parse Parser_Check
begin

text ‹The theorems of theory‹TIGER_Grammar.LR_Prec_Parse› relate const‹restrict› to
  const‹prec_ok›. What they cannot say is that const‹prec_ok› of a level table means what
  a reader expects, and that const‹restrict› computes. Both are checked here on small
  grammars by enumerating every tree of every short word.›

section ‹Enumeration›

datatype tk = TA | TP | TM | TI | TB

type_synonym tree = ‹(unit, unit, string, tk) ptree›
type_synonym word = ‹(unit, unit, tk) tword›

definition tk_at :: ‹nat ⇒ tk ⇒ (tk, unit) token› where
  ‹tk_at c x = ⦇tok = x, span = span.make 0 c 0 1 []⦈›

fun cart :: ‹'a list list ⇒ 'a list list› where
  ‹cart [] = [[]]›
| ‹cart (xs # xss) = concat (map (λx. map (Cons x) (cart xss)) xs)›

fun splits :: ‹nat ⇒ 'a list ⇒ 'a list list list› where
  ‹splits 0 w = (if w = [] then [[]] else [])›
| ‹splits (Suc n) w = concat (map (λi. map (Cons (take i w)) (splits n (drop i w))) [0..<Suc (length w)])›

definition kids_ok :: ‹(string, tk) rhs ⇒ nat ⇒ tree list ⇒ bool› where
  ‹kids_ok r i ts ⟷ list_all2 (λa t. fst (proot t) = fst a ∧ irel_sat (snd a) (snd (proot t)) i) r ts›

definition fits :: ‹string list ⇒ (string, tk) rhs ⇒ word list ⇒ bool› where
  ‹fits ns r ws ⟷ list_all2 (λa u. u ≠ [] ∨ sym_null ns (fst a)) r ws›

text ‹All trees of a word, with node indentations from ‹ixs›; ‹f› bounds the depth, ‹ns› are
  the nullable names, which keeps empty parts from branching.›

fun gen :: ‹(string, tk) is_cfg ⇒ string list ⇒ nat list ⇒ nat ⇒ (string, tk) sym ⇒ word ⇒ tree list› where
  ‹gen G ns ixs 0 X w = []›
| ‹gen G ns ixs (Suc f) (Tm t) w = (case w of [x] ⇒ if tok x = t then [PLeaf x] else [] | _ ⇒ [])›
| ‹gen G ns ixs (Suc f) (Nt n) w = concat (map (λr. concat (map (λws.
       let kids = cart (map2 (λa u. gen G ns ixs f (fst a) u) r ws) in
       concat (map (λi. map (PNode n i) (filter (kids_ok r i) kids)) ixs))
       (filter (fits ns r) (splits (length r) w)))) (map snd (filter (λp. fst p = n) (iprods G))))›

text ‹const‹pk›, run on a tree.›

fun chk :: ‹nat ⇒ (string, tk) is_cfg ⇒ string list ⇒ (string, tk) forbid list ⇒
    (string, tk) alt list ⇒ (string, tk) alt list ⇒ (string, tk) alt list ⇒ tree ⇒ bool› where
  ‹chk f G ns F Ds Rs Ls (PLeaf t) = True›
| ‹chk 0 G ns F Ds Rs Ls (PNode n i ts) = False›
| ‹chk (Suc f) G ns F Ds Rs Ls (PNode n i ts) = list_ex (λp. fst p = n ∧ p ∉ set Ds ∧ p ∉ set Rs ∧
     p ∉ set Ls ∧ kids_ok (snd p) i ts ∧ list_all (λk. chk f G ns F (fb F FDirect p k)
       (fb F FRight p k @ (if rpos ns (snd p) k then Rs else []))
       (fb F FLeft p k @ (if lpos ns (snd p) k then Ls else [])) (ts ! k)) [0..<length ts]) (iprods G)›

definition words :: ‹tk list ⇒ nat ⇒ word list› where
  ‹words ts n = concat (map (λm. map (map (tk_at 0)) (cart (replicate m ts))) [0..<Suc n])›

text ‹The trees of ‹G› accepted by const‹prec_ok› and those read back from ‹G'› agree
  on each word.›

definition same_on :: ‹(string, tk) is_cfg ⇒ (string, tk) prec_decl ⇒ nat list ⇒ nat ⇒ word list ⇒ bool› where
  ‹same_on G d ixs f ws = (let G' = restrict G d; ns = nulls G; ns' = nulls G'; F = forbids G d in
     list_all (λw.
       set (filter (chk 12 G ns F [] [] []) (gen G ns ixs f (Nt (istart G)) w)) =
       set (map (plain orig_name) (gen G' ns' ixs (3 * f) (Nt (istart G')) w))) ws)›

definition unique_on :: ‹(string, tk) is_cfg ⇒ (string, tk) prec_decl ⇒ nat list ⇒ nat ⇒ word list ⇒ bool› where
  ‹unique_on G d ixs f ws = (let ns = nulls G; F = forbids G d in list_all (λw.
     let ts = gen G ns ixs f (Nt (istart G)) w
     in ts = [] ∨ length (filter (chk 12 G ns F [] [] []) ts) = 1) ws)›

section ‹Infix, and ‹if› in an operand›

text ‹
  The grammar ‹E ::= E + E | if E | Num› of Afroozeh et al.
  cite‹‹Sect.~2.2, Fig.~1› in "afroozeh2013-operator-precedence"›, with ‹*›
  added. There ‹if› is below ‹+›, and ‹1 + if 2 + 3› has the one tree
  ‹1 + (if (2 + 3))›, which no one-level filter selects. Here it is the word
  ‹a + if a + a› below.
›

definition p_add where ‹p_add = (''E'', [(Nt ''E'', Any), (Tm TP, Any), (Nt ''E'', Any)])›
definition p_mul where ‹p_mul = (''E'', [(Nt ''E'', Any), (Tm TM, Any), (Nt ''E'', Any)])›
definition p_if  where ‹p_if  = (''E'', [(Tm TI, Any), (Nt ''E'', Any)])›
definition p_a   where ‹p_a   = (''E'', [(Tm TA, Any)])›

definition ge :: ‹(string, tk) is_cfg› where
  ‹ge = ⦇iprods = [p_add, p_mul, p_if, p_a], istart = ''E'', istart_ind = 0⦈›

definition de :: ‹(string, tk) prec_decl› where
  ‹de = ⦇dlevels = [[(AOpen, [(p_if, False)]), (ALeft, [(p_add, False)]), (ALeft, [(p_mul, False)])]],
         dforbids = []⦈›

definition col0 :: ‹tk list ⇒ word› where ‹col0 = map (tk_at 0)›

text ‹Every word has one tree, and none lost its language.›

parser_check ‹unique_on ge de [0] 7 (words [TA, TP, TM, TI] 4)›
parser_check ‹same_on ge de [0] 7 (words [TA, TP, TM, TI] 4)›

text ‹Without a declaration nothing changes, and the grammar stays ambiguous.›

parser_check ‹same_on ge ⦇dlevels = [], dforbids = []⦈ [0] 7 (words [TA, TP, TI] 4)›

parser_check ‹¬ unique_on ge ⦇dlevels = [], dforbids = []⦈ [0] 7 (words [TA, TP] 5)›

definition tr where ‹tr G f ws = (let ns = nulls G in map erase
  (filter (chk 12 G ns (forbids G de) [] [] []) (gen G ns [0] f (Nt ''E'') (col0 ws))))›

abbreviation ‹la ≡ Node ''E'' [Leaf (tk_at 0 TA)] :: (unit, unit, string, tk) ast›
abbreviation ‹bin x a b ≡ Node ''E'' [a, Leaf (tk_at 0 x), b] :: (unit, unit, string, tk) ast›
abbreviation ‹ifn a ≡ Node ''E'' [Leaf (tk_at 0 TI), a] :: (unit, unit, string, tk) ast›

parser_check ‹tr ge 7 [TA, TP, TA, TM, TA] = [bin TP la (bin TM la la)]›
parser_check ‹tr ge 7 [TA, TP, TA, TP, TA] = [bin TP (bin TP la la) la]›
parser_check ‹tr ge 7 [TA, TP, TI, TA, TP, TA] = [bin TP la (ifn (bin TP la la))]›
parser_check ‹tr ge 7 [TA, TM, TI, TA, TP, TA] = [bin TM la (ifn (bin TP la la))]›
parser_check ‹tr ge 7 [TI, TA, TP, TA] = [ifn (bin TP la la)]›

text ‹The driver on the restricted grammar, unit nodes dropped by const‹plain_ast›.›

definition Sh where ‹Sh = ''S''›

parser_check ‹rlalr_conflicts (restrict ge de) Sh = []›

definition pa where ‹pa ws = map_option (plain_ast orig_name) (dparse (restrict ge de) Sh (col0 ws))›

parser_check ‹pa [TA, TP, TI, TA, TP, TA] = Some (bin TP la (ifn (bin TP la la)))›
parser_check ‹pa [TA, TM, TA, TP, TA] = Some (bin TP (bin TM la la) la)›
parser_check ‹pa [TA, TP] = None›

section ‹A layout grammar›

text ‹A block keyword whose body is indented; the left operand keeps its own column.›

definition q_add where ‹q_add = (''E'', [(Nt ''E'', Eq), (Tm TP, Any), (Nt ''E'', Ge)])›
definition q_blk where ‹q_blk = (''E'', [(Tm TB, Eq), (Nt ''E'', Gt)])›
definition q_a   where ‹q_a   = (''E'', [(Tm TA, Eq)])›

definition gl :: ‹(string, tk) is_cfg› where
  ‹gl = ⦇iprods = [q_add, q_blk, q_a], istart = ''E'', istart_ind = 0⦈›

definition dl :: ‹(string, tk) prec_decl› where
  ‹dl = ⦇dlevels = [[(AOpen, [(q_blk, False)]), (ALeft, [(q_add, False)])]], dforbids = []⦈›

definition lwords :: ‹word list› where
  ‹lwords = concat (map (λn. concat (map (λts. map (λcs. map2 tk_at cs ts)
       (cart (replicate n [0, 1, 2]))) (cart (replicate n [TA, TP, TB])))) [0..<4])›

parser_check ‹same_on gl dl [0, 1, 2] 6 lwords›
parser_check ‹unique_on gl dl [0, 1, 2] 6 lwords›

text ‹A unit step of the chains relates the child to its parent by ‹=›, so it adds no
  indentation constraint.›

definition unit_eq :: ‹(string, tk) is_cfg ⇒ bool› where
  ‹unit_eq H ⟷ list_all (λ(m, r). case r of
     [(Nt c, i)] ⇒ orig_name c ≠ orig_name m ∨ i = Eq | _ ⇒ True) (iprods H)›

parser_check ‹unit_eq (restrict gl dl)›
parser_check ‹unit_eq (restrict ge de)›

section ‹Spines through nullable tails›

text ‹The right spine runs through ‹n_app›, whose last symbol ‹O› can derive nothing.›

definition n_app where ‹n_app = (''E'', [(Tm TI, Any), (Nt ''E'', Any), (Nt ''O'', Any)])›
definition n_add where ‹n_add = (''E'', [(Nt ''E'', Any), (Tm TP, Any), (Nt ''E'', Any)])›
definition n_a   where ‹n_a   = (''E'', [(Tm TA, Any)])›
definition n_e   where ‹n_e   = (''O'', [])›
definition n_b   where ‹n_b   = (''O'', [(Tm TB, Any)])›

definition gn :: ‹(string, tk) is_cfg› where
  ‹gn = ⦇iprods = [n_app, n_add, n_a, n_e, n_b], istart = ''E'', istart_ind = 0⦈›

definition dn :: ‹(string, tk) prec_decl› where
  ‹dn = ⦇dlevels = [], dforbids = [(n_add, 0, FRight, n_add)]⦈›

parser_check ‹nulls gn = [''O'']›
parser_check ‹same_on gn dn [0] 7 (words [TA, TP, TI, TB] 4)›

end