--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/S_grammar.scala	Mon Nov 19 14:18:42 2012 +0000
@@ -0,0 +1,52 @@
+//: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")
+}