//:load parser3.scala

case class StringParser(s: String) extends Parser[String, String] {
  def parse(ts: String) = {
    if (s.length <= ts.length && ts.startsWith(s)) Set((s, ts.drop(s.length)))
    else Set()
  }
}

implicit def string2parser(s: String) = StringParser(s)

def time_needed[T](i: Int, code: => T) = {
  val start = System.nanoTime()
  for (j <- 1 to i) code
  val end = System.nanoTime()
  (end - start)/(i * 1.0e9)
}

// unambiguous grammar

lazy val U: Parser[String, String] = 
  ("1" ~ U) ==> { case (x, y) => "1" + y} || ""  

def test1(i: Int) = {
  val result = U.parse_all("1" * i)
  //print(result.size + " ")
}

for (i <- 1 to 1000 by 50) {
  print(i + " ")
  print("%.5f".format(time_needed(1, test1(i))))
  print("\n")
}



// ambiguous grammar
// n = 16 -> over 35 million parse trees

lazy val S: Parser[String, String] = 
  ("1" ~ S ~ S) ==> { case ((x, y), z) => "1" + y + z} || ""

def test2(i: Int) = {
  val result = S.parse_all("1" * i)
  print(result.size + " ")
}

for (i <- 1 to 30) {
  print(i + " ")
  print("%.5f".format(time_needed(1, test2(i))))
  print("\n")
}