diff -r 8db273a410cc -r 47b5c91eff47 progs/comb1.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/comb1.scala	Wed Oct 30 15:14:14 2013 +0000
@@ -0,0 +1,100 @@
+import scala.language.implicitConversions
+import scala.language.reflectiveCalls
+
+abstract class Parser[I <% Seq[_], T] {
+  def parse(ts: I): Set[(T, I)]
+
+  def parse_all(ts: I) : Set[T] =
+    for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
+}
+
+class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {
+  def parse(sb: I) = 
+    for ((head1, tail1) <- p.parse(sb); 
+         (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
+}
+
+class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   
+}
+
+class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+  def parse(sb: I) = 
+    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
+}
+
+// atomic parsers
+case class StringParser(s: String) extends Parser[String, String] {
+  def parse(sb: String) = {
+    val (prefix, suffix) = sb.splitAt(s.length)
+    if (prefix == s) Set((prefix, suffix)) else Set()
+  }
+}
+
+case object NumParser extends Parser[String, String] {
+  val reg = "[0-9]+".r
+  def parse(sb: String) = reg.findPrefixOf(sb) match {
+    case None => Set()
+    case Some(s) => Set(sb.splitAt(s.length)) 
+  }
+}
+
+
+implicit def string2parser(s : String) = StringParser(s)
+
+implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
+  def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
+  def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
+  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
+}
+
+implicit def StringOps(s: String) = new {
+  def || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
+  def || (r: String) = new AltParser[String, String](s, r)
+  def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)
+  def ~[S] (q : => Parser[String, S]) = 
+    new SeqParser[String, String, S](s, q)
+  def ~ (r: String) = 
+    new SeqParser[String, String, String](s, r)
+}
+
+
+
+
+lazy val Pal : Parser[String, String] = 
+  (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
+   ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "")
+
+Pal.parse_all("ababbaba")
+
+
+lazy val P : Parser[String, String] = 
+  "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""
+
+P.parse_all("(((()()))())")
+P.parse_all("(((()()))()))")
+P.parse_all(")(")
+
+lazy val E: Parser[String, String] = 
+  (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F  
+lazy val F: Parser[String, String] = 
+  ((T ~ "+" ~ T) ==> { case ((x, y), z) => x + y + z } ||
+   (T ~ "-" ~ T) ==> { case ((x, y), z) => x + y + z } || T)
+lazy val T: Parser[String, String] = 
+  ("(" ~ E ~ ")") ==> { case ((x, y), z) => x + y + z } || NumParser
+
+
+println(E.parse_all("1+2+3"))
+
+
+
+// non-ambiguous vs ambiguous
+lazy val U : Parser[String, String] =
+  ("1" ~ U) ==> { case (x, y) => x + y } || ""
+
+U.parse_all("1" * 100 + "0")
+
+lazy val S : Parser[String, String] =
+  ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
+
+S.parse_all("1" * 15)