(* This code extends 'std_prelude'. *)

val push = 
  (fn v2 => 
    (fn v1 => (Cons (v1, v2)))) ;

fun pop v3 = 
  (fn v4 => 
    (case v3 of 
        Nil => Nil 
      | (Cons (v2, v1)) => 
          (if (v4 <= 0) 
          then (Cons (v2, v1)) 
          else ((pop v1) (v4 - 1))))) ;

fun take1 x = 
  (fn x1 => 
    (if (x <= 0) 
    then 
      (case x1 of 
          Nil => Nil 
        | (Cons (v2, v1)) => Nil) 
    else 
      (case x1 of 
          Nil => (raise Bind) 
        | (Cons (v4, v3)) => 
            (if (x <= 0) 
            then Nil 
            else (Cons (v4, ((take1 (x - 1)) v3))))))) ;

val take = 
  (fn v2 => 
    (fn v1 => 
      (if ((LENGTH v1) > v2) 
      then (Some (((take1 v2) v1))) 
      else None))) ;

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

val isNonTmnlSym = 
  (fn v3 => 
    (case v3 of 
        (Ts (v1)) => false 
      | (Nts (v2)) => true)) ;

val sym2Str = 
  (fn v3 => 
    (case v3 of 
        (Ts (v1)) => v1 
      | (Nts (v2)) => v2)) ;

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

val ruleRhs = 
  (fn v3 => 
    (case v3 of 
        (Rule (v2, v1)) => v1)) ;

val ruleLhs = 
  (fn v3 => 
    (case v3 of 
        (Rule (v2, v1)) => v2)) ;

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

val ptree2Sym = 
  (fn v4 => 
    (case v4 of 
        (Leaf (v1)) => (Ts (v1)) 
      | (Node (v3, v2)) => (Nts (v3)))) ;

val buildTree = 
  (fn v2 => 
    (fn v3 => 
      let val v1 = ((take (LENGTH v3)) ((MAP ((op 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)) 
      end )) ;

val addRule = 
  (fn v4 => 
    (fn v5 => 
      (case v5 of 
          (Rule (v3, v2)) => 
            let val v1 = ((buildTree v4) (REVERSE v2)) 
            in 
              (if (v1 = None) 
              then None 
              else (Some ((Node (v3, (REVERSE (THE v1))))))) 
            end ))) ;

val stackSyms = 
  (fn v1 => (REVERSE ((MAP FST) ((MAP FST) v1)))) ;

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

val findItemInRules = 
  (fn v11 => 
    (fn v12 => 
      (case v11 of 
          (Item (v10, v9)) => 
            (case v9 of 
                (Pair (v8, v7)) => 
                  (case v7 of 
                      Nil => 
                        (case v12 of 
                            Nil => false 
                          | (Cons (v4, v3)) => 
                              (case v4 of 
                              (Rule (v2, v1)) => true)) 
                    | (Cons (v6, v5)) => false))))) ;

fun itemEqRuleList v7 = 
  (fn v8 => 
    (case v7 of 
        Nil => 
          (case v8 of 
              Nil => true 
            | (Cons (v2, v1)) => true) 
      | (Cons (v6, v5)) => 
          (case v8 of 
              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))))) ;

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

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

val stackSyms_1 = 
  (fn v1 => (REVERSE ((MAP FST) ((MAP FST) v1)))) ;

val exitCond = 
  (fn v7 => 
    (fn v8 => 
      (case v7 of 
          (Pair (v6, v5)) => 
            (case v8 of 
                (Pair (v4, v3)) => 
                  (case v3 of 
                      (Pair (v2, v1)) => ((((v2 = Nil) = false) andalso ((stackSyms_1 v2) = (Cons (v5, Nil)))) andalso (v4 = (Cons ((Ts (v6)), Nil))))))))) ;

val init = 
  (fn v1 => 
    (fn v2 => (Pair (v2, (Pair (Nil, (Cons (v1, Nil)))))))) ;

val doReduce = 
  (fn x => 
    (fn x1 => 
      (fn x2 => 
        (case x1 of 
            (Pair (v19, v18)) => 
              (case v19 of 
                  Nil => (raise Bind) 
                | (Cons (v17, v16)) => 
                    (case v18 of 
                        (Pair (v15, v14)) => 
                          (case v14 of 
                              Nil => (raise Bind) 
                            | (Cons (v13, v12)) => 
                              (case v13 of 
                              (Pair (v11, v10)) => 
                              (if (isNonTmnlSym v17) 
                              then None 
                              else 
                              let val v9 = (ruleLhs x2) 
                              in 
                              let val v8 = (ruleRhs x2) 
                              in 
                              let val v7 = ((addRule v15) x2) 
                              in 
                              (case v7 of 
                              None => None 
                              | (Some (v6)) => 
                              let val v5 = ((pop v15) (LENGTH v8)) 
                              in 
                              let val v4 = ((pop (Cons ((Pair (v11, v10)), v12))) (LENGTH v8)) 
                              in 
                              (if (v4 = Nil) 
                              then None 
                              else 
                              let val v3 = (SND (HD v4)) 
                              in 
                              let val v2 = (((FST x) v3) (Nts (v9))) 
                              in 
                              (if (v2 = Nil) 
                              then None 
                              else 
                              let val v1 = (Pair ((Nts (v9)), v2)) 
                              in (Some ((Pair ((Cons (v17, v16)), (Pair (((APPEND (Cons ((Pair (v1, v6)), Nil))) v5), ((push v4) v1))))))) 
                              end ) 
                              end 
                              end ) 
                              end 
                              end ) 
                              end 
                              end 
                              end ))))))))) ;

val parse = 
  (fn x => 
    (fn x1 => 
      (case x1 of 
          (Pair (v19, v18)) => 
            (case v18 of 
                (Pair (v17, v16)) => 
                  (case v16 of 
                      Nil => (raise Bind) 
                    | (Cons (v15, v14)) => 
                        (case v15 of 
                            (Pair (v13, v12)) => 
                              (case x of 
                              None => None 
                              | (Some (v11)) => 
                              (case v19 of 
                              Nil => None 
                              | (Cons (v10, v9)) => 
                              (case v9 of 
                              Nil => 
                              let val v3 = (((getState v11) v12) v10) 
                              in 
                              (case v3 of 
                              (Reduce (v1)) => (((doReduce v11) (Pair ((Cons (v10, Nil)), (Pair (v17, (Cons ((Pair (v13, v12)), v14))))))) v1) 
                              | (Goto (v2)) => None 
                              | Na => None) 
                              end 
                              | (Cons (v8, v7)) => 
                              let val v6 = (((getState v11) v12) v10) 
                              in 
                              (case v6 of 
                              (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) 
                              end ))))))))) ;

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