(* This code extends 'std_prelude'. *)

let push = 
  (fun v2 -> 
    (fun v1 -> (Cons (v1, v2)))) ;;

let rec pop v3 = 
  (fun v4 -> 
    (match v3 with 
        Nil -> Nil 
      | (Cons (v2, v1)) -> 
          (if (v4 <= 0) 
          then (Cons (v2, v1)) 
          else ((pop v1) (v4 - 1))))) ;;

let rec take1 x = 
  (fun x1 -> 
    (if (x <= 0) 
    then 
      (match x1 with 
          Nil -> Nil 
        | (Cons (v2, v1)) -> Nil) 
    else 
      (match x1 with 
          Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
        | (Cons (v4, v3)) -> 
            (if (x <= 0) 
            then Nil 
            else (Cons (v4, ((take1 (x - 1)) v3))))))) ;;

let take = 
  (fun v2 -> 
    (fun v1 -> 
      (if ((LENGTH v1) > v2) 
      then (Some (((take1 v2) v1))) 
      else None))) ;;

type symbol = 
    Nts of (int) list 
  | Ts of (int) list ;;

let isNonTmnlSym = 
  (fun v3 -> 
    (match v3 with 
        (Ts (v1)) -> false 
      | (Nts (v2)) -> true)) ;;

let sym2Str = 
  (fun v3 -> 
    (match v3 with 
        (Ts (v1)) -> v1 
      | (Nts (v2)) -> v2)) ;;

type rule = 
    Rule of (int) list * (symbol) list ;;

let ruleRhs = 
  (fun v3 -> 
    (match v3 with 
        (Rule (v2, v1)) -> v1)) ;;

let ruleLhs = 
  (fun v3 -> 
    (match v3 with 
        (Rule (v2, v1)) -> v2)) ;;

type ptree = 
    Node of (int) list * (ptree) list 
  | Leaf of (int) list ;;

let ptree2Sym = 
  (fun v4 -> 
    (match v4 with 
        (Leaf (v1)) -> (Ts (v1)) 
      | (Node (v3, v2)) -> (Nts (v3)))) ;;

let buildTree = 
  (fun v2 -> 
    (fun v3 -> 
      (let v1 = ((take (LENGTH v3)) ((MAP ((o ptree2Sym) SND)) v2)) 
      in 
        (if (v1 = None) 
        then None 
        else 
          (if (v3 = (THE v1)) 
          then ((take (LENGTH (THE v1))) ((MAP SND) v2)) 
          else None))))) ;;

let addRule = 
  (fun v4 -> 
    (fun v5 -> 
      (match v5 with 
          (Rule (v3, v2)) -> 
            (let v1 = ((buildTree v4) (REVERSE v2)) 
            in 
              (if (v1 = None) 
              then None 
              else (Some ((Node (v3, (REVERSE (THE v1))))))))))) ;;

let stackSyms = 
  (fun v1 -> (REVERSE ((MAP FST) ((MAP FST) v1)))) ;;

type item = 
    Item of (int) list * ((symbol) list, (symbol) list) prod ;;

let findItemInRules = 
  (fun v11 -> 
    (fun v12 -> 
      (match v11 with 
          (Item (v10, v9)) -> 
            (match v9 with 
                (Pair (v8, v7)) -> 
                  (match v7 with 
                      Nil -> 
                        (match v12 with 
                            Nil -> false 
                          | (Cons (v4, v3)) -> 
                              (match v4 with 
                              (Rule (v2, v1)) -> true)) 
                    | (Cons (v6, v5)) -> false))))) ;;

let rec itemEqRuleList v7 = 
  (fun v8 -> 
    (match v7 with 
        Nil -> 
          (match v8 with 
              Nil -> true 
            | (Cons (v2, v1)) -> true) 
      | (Cons (v6, v5)) -> 
          (match v8 with 
              Nil -> false 
            | (Cons (v4, v3)) -> 
                (if (((LENGTH (Cons (v6, v5))) = (LENGTH (Cons (v4, v3)))) = false) 
                then false 
                else 
                  (if ((findItemInRules (HD (Cons (v6, v5)))) (Cons (v4, v3))) 
                  then ((itemEqRuleList (TL (Cons (v6, v5)))) (Cons (v4, v3))) 
                  else false))))) ;;

type action = 
    Na 
  | Goto of (item) list 
  | Reduce of rule ;;

let getState = 
  (fun v11 -> 
    (fun v12 -> 
      (fun v13 -> 
        (match v11 with 
            (Pair (v10, v9)) -> 
              (let v8 = ((v10 v12) v13) 
              in 
                (let v7 = ((v9 v12) (sym2Str v13)) 
                in 
                  (match v8 with 
                      Nil -> 
                        (match v7 with 
                            Nil -> Na 
                          | (Cons (v2, v1)) -> 
                              (if ((LENGTH v7) = 1) 
                              then (Reduce ((HD v7))) 
                              else Na)) 
                    | (Cons (v6, v5)) -> 
                        (match v7 with 
                            Nil -> (Goto (v8)) 
                          | (Cons (v4, v3)) -> 
                              (if ((itemEqRuleList (Cons (v6, v5))) (Cons (v4, v3))) 
                              then (Reduce ((HD v7))) 
                              else Na))))))))) ;;

let stackSyms_1 = 
  (fun v1 -> (REVERSE ((MAP FST) ((MAP FST) v1)))) ;;

let exitCond = 
  (fun v7 -> 
    (fun v8 -> 
      (match v7 with 
          (Pair (v6, v5)) -> 
            (match v8 with 
                (Pair (v4, v3)) -> 
                  (match v3 with 
                      (Pair (v2, v1)) -> ((((v2 = Nil) = false) && ((stackSyms_1 v2) = (Cons (v5, Nil)))) && (v4 = (Cons ((Ts (v6)), Nil))))))))) ;;

let init = 
  (fun v1 -> 
    (fun v2 -> (Pair (v2, (Pair (Nil, (Cons (v1, Nil)))))))) ;;

let doReduce = 
  (fun x -> 
    (fun x1 -> 
      (fun x2 -> 
        (match x1 with 
            (Pair (v19, v18)) -> 
              (match v19 with 
                  Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
                | (Cons (v17, v16)) -> 
                    (match v18 with 
                        (Pair (v15, v14)) -> 
                          (match v14 with 
                              Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
                            | (Cons (v13, v12)) -> 
                              (match v13 with 
                              (Pair (v11, v10)) -> 
                              (if (isNonTmnlSym v17) 
                              then None 
                              else 
                              (let v9 = (ruleLhs x2) 
                              in 
                              (let v8 = (ruleRhs x2) 
                              in 
                              (let v7 = ((addRule v15) x2) 
                              in 
                              (match v7 with 
                              None -> None 
                              | (Some (v6)) -> 
                              (let v5 = ((pop v15) (LENGTH v8)) 
                              in 
                              (let v4 = ((pop (Cons ((Pair (v11, v10)), v12))) (LENGTH v8)) 
                              in 
                              (if (v4 = Nil) 
                              then None 
                              else 
                              (let v3 = (SND (HD v4)) 
                              in 
                              (let v2 = (((FST x) v3) (Nts (v9))) 
                              in 
                              (if (v2 = Nil) 
                              then None 
                              else 
                              (let v1 = (Pair ((Nts (v9)), v2)) 
                              in (Some ((Pair ((Cons (v17, v16)), (Pair (((APPEND (Cons ((Pair (v1, v6)), Nil))) v5), ((push v4) v1))))))))))))))))))))))))))) ;;

let parse = 
  (fun x -> 
    (fun x1 -> 
      (match x1 with 
          (Pair (v19, v18)) -> 
            (match v18 with 
                (Pair (v17, v16)) -> 
                  (match v16 with 
                      Nil -> (raise (Match_failure (string_of_bool true, 0, 0))) 
                    | (Cons (v15, v14)) -> 
                        (match v15 with 
                            (Pair (v13, v12)) -> 
                              (match x with 
                              None -> None 
                              | (Some (v11)) -> 
                              (match v19 with 
                              Nil -> None 
                              | (Cons (v10, v9)) -> 
                              (match v9 with 
                              Nil -> 
                              (let v3 = (((getState v11) v12) v10) 
                              in 
                              (match v3 with 
                              (Reduce (v1)) -> (((doReduce v11) (Pair ((Cons (v10, Nil)), (Pair (v17, (Cons ((Pair (v13, v12)), v14))))))) v1) 
                              | (Goto (v2)) -> None 
                              | Na -> None)) 
                              | (Cons (v8, v7)) -> 
                              (let v6 = (((getState v11) v12) v10) 
                              in 
                              (match v6 with 
                              (Reduce (v4)) -> (((doReduce v11) (Pair ((Cons (v10, (Cons (v8, v7)))), (Pair (v17, (Cons ((Pair (v13, v12)), v14))))))) v4) 
                              | (Goto (v5)) -> 
                              (if (isNonTmnlSym v10) 
                              then None 
                              else (Some ((Pair ((Cons (v8, v7)), (Pair ((Cons ((Pair ((Pair (v10, v5)), (Leaf ((sym2Str v10))))), v17)), ((push (Cons ((Pair (v13, v12)), v14))) (Pair (v10, v5)))))))))) 
                              | Na -> None))))))))))) ;;

let parser = 
  (fun v26 -> 
    (fun v27 -> 
      (fun v28 -> 
        (match v26 with 
            (Pair (v25, v24)) -> 
              (match v24 with 
                  (Pair (v23, v22)) -> 
                    (let v13 = (((
                    (rec owhile g = 
                      (fun f -> 
                        (fun x -> 
                          (if (g x) 
                          then (((owhile g) f) (f x)) 
                          else (Some (x))))) 
                    in owhile) 
                    (fun v15 -> 
                      (match v15 with 
                          None -> false 
                        | (Some (v14)) -> (((exitCond (Pair (v23, (Nts (v22))))) v14) = false)))) 
                    (fun v21 -> 
                      (match v21 with 
                          None -> None 
                        | (Some (v20)) -> 
                            (match v20 with 
                              (Pair (v19, v18)) -> 
                              (match v18 with 
                              (Pair (v17, v16)) -> ((parse v27) (Pair (v19, (Pair (v17, v16)))))))))) (Some (((init v25) v28)))) 
                    in 
                      (match v13 with 
                          None -> None 
                        | (Some (v12)) -> 
                            (match v12 with 
                              None -> (Some (None)) 
                              | (Some (v11)) -> 
                              (match v11 with 
                              (Pair (v10, v9)) -> 
                              (match v9 with 
                              (Pair (v8, v7)) -> 
                              (match v8 with 
                              Nil -> (Some (None)) 
                              | (Cons (v6, v5)) -> 
                              (match v6 with 
                              (Pair (v4, v3)) -> 
                              (match v5 with 
                              Nil -> (Some ((Some (v3)))) 
                              | (Cons (v2, v1)) -> (Some (None))))))))))))))) ;;