1 //:load parser3.scala

     2 

     3 case class StringParser(s: String) extends Parser[String, String] {

     4   def parse(ts: String) = {

     5     if (s.length <= ts.length && ts.startsWith(s)) Set((s, ts.drop(s.length)))

     6     else Set()

     7   }

     8 }

     9 

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

    11 

    12 def time_needed[T](i: Int, code: => T) = {

    13   val start = System.nanoTime()

    14   for (j <- 1 to i) code

    15   val end = System.nanoTime()

    16   (end - start)/(i * 1.0e9)

    17 }

    18 

    19 // unambiguous grammar

    20 

    21 lazy val U: Parser[String, String] = 

    22   ("1" ~ U) ==> { case (x, y) => "1" + y} || ""  

    23 

    24 def test1(i: Int) = {

    25   val result = U.parse_all("1" * i)

    26   //print(result.size + " ")

    27 }

    28 

    29 for (i <- 1 to 1000 by 50) {

    30   print(i + " ")

    31   print("%.5f".format(time_needed(1, test1(i))))

    32   print("\n")

    33 }

    34 

    35 

    36 

    37 // ambiguous grammar

    38 // n = 16 -> over 35 million parse trees

    39 

    40 lazy val S: Parser[String, String] = 

    41   ("1" ~ S ~ S) ==> { case ((x, y), z) => "1" + y + z} || ""

    42 

    43 def test2(i: Int) = {

    44   val result = S.parse_all("1" * i)

    45   print(result.size + " ")

    46 }

    47 

    48 for (i <- 1 to 30) {

    49   print(i + " ")

    50   print("%.5f".format(time_needed(1, test2(i))))

    51   print("\n")

    52 }