(* sumProdRHSLens : gram -> int

   sum the lengths of the right-hand sides of a grammar's
   productions *)

fun sumProdRHSLens gram =
      let fun sum nil             = 0
            | sum ((_, bs) :: ps) = length bs + sum ps
      in sum(Set.toList(Gram.productions gram)) end

(* better : gram * gram -> bool

   metric for gram1 being "better" than gram2 *)

fun better(gram1, gram2) =
      let val nv1 = Gram.numVariables gram1
          val nv2 = Gram.numVariables gram2
      in nv1 < nv2 orelse
         (nv1 = nv2 andalso
          let val np1 = Gram.numProductions gram1
              val np2 = Gram.numProductions gram2
          in np1 < np2 orelse
             (np1 = np2 andalso
              let val n1 = sumProdRHSLens gram1
                  val n2 = sumProdRHSLens gram2
              in n1 < n2 end)
          end)
      end;
   
(* best : gram * gram option list -> gram

   best(gram, gramOpts) returns gram if none of the optional
   grammars in gramOpts are better than gram; otherwise it returns
   one of the optional grammars that is better than gram and
   such that no other optional grammar is even better *)

fun best(gram, nil)                    = gram
  | best(gram, NONE :: gramOpts)       = best(gram, gramOpts)
  | best(gram, SOME gram' :: gramOpts) =
      if better(gram', gram)
      then best(gram', gramOpts)
      else best(gram, gramOpts);

(* elims : gram -> gram

   recursively eliminate variables of a grammar *)

fun elims gram =
      let val qs       =
            SymSet.minus
            (Gram.variables gram, Set.sing(Gram.startVariable gram))
          val gramOpts =
            map (fn q =>
                   case Gram.eliminateVariableOpt(gram, q) of
                        NONE       => NONE
                      | SOME gram' => SOME(elims gram'))
                (Set.toList qs)
      in best(gram, gramOpts) end;

(* handSimp : gram -> gram

   hand-simplify a grammar *)

fun handSimp gram =
      let val gram = elims gram
      in case Gram.restartOpt gram of
              NONE       => gram
            | SOME gram' => gram'
      end;