//: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")

}