--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/parser4.scala	Sat Jun 15 09:23:18 2013 -0400
@@ -0,0 +1,82 @@
+
+// parser combinators with input type I and return type T
+
+case class SubString(s: String, l: Int, h: Int) {
+  def low = l
+  def high = h
+  def length = h - l
+  def substring(l: Int = l, h: Int = h) = s.slice(l, h)
+  def set(low: Int = l, high: Int = h) = SubString(s, low, high)
+  
+}
+
+type Ctxt = List[(String, SubString)]
+
+abstract class Parser[T] {
+
+  def parse(ts: SubString, ctxt: Ctxt): Set[(T, SubString)]
+
+  def parse_all(s: String) : Set[T] =
+    for ((head, tail) <- parse(SubString(s, 0, s.length), Nil); if (tail.substring() == "")) yield head
+
+  def || (right : => Parser[T]) : Parser[T] = new AltParser(this, right)
+  def ==>[S] (f: => T => S) : Parser [S] = new FunParser(this, f)
+  def ~[S] (right : => Parser[S]) : Parser[(T, S)] = new SeqParser(this, right)
+}
+
+class SeqParser[T, S](p: => Parser[T], q: => Parser[S]) extends Parser[(T, S)] {
+  def parse(sb: SubString, ctxt: Ctxt) = 
+    for ((head1, tail1) <- p.parse(sb, ctxt); 
+         (head2, tail2) <- q.parse(tail1, ctxt)) yield ((head1, head2), tail2)
+}
+
+class AltParser[T](p: => Parser[T], q: => Parser[T]) extends Parser[T] {
+  def parse(sb: SubString, ctxt: Ctxt) = p.parse(sb, ctxt) ++ q.parse(sb, ctxt)   
+}
+
+class FunParser[T, S](p: => Parser[T], f: T => S) extends Parser[S] {
+  def parse(sb: SubString, ctxt: Ctxt) = 
+    for ((head, tail) <- p.parse(sb, ctxt)) yield (f(head), tail)
+}
+
+case class SubStringParser(s: String) extends Parser[SubString] {
+  val n = s.length
+  def parse(sb: SubString, ctxt: Ctxt) = {
+    if (n <= sb.length && sb.substring(sb.low, sb.low + n) == s) 
+      Set((sb.set(high = sb.low + n), sb.set(low = sb.low + n))) 
+    else Set()
+  }
+}
+
+implicit def string2parser(s: String) = SubStringParser(s) ==> (_.substring())
+
+class IgnLst[T](p: => Parser[T]) extends Parser[T] {
+  def parse(sb: SubString, ctxt: Ctxt) = {
+    if (sb.length == 0) Set()
+    else for ((head, tail) <- p.parse(sb.set(high = sb.high - 1), ctxt)) 
+         yield (head, tail.set(high = tail.high + 1))
+  }
+}
+
+class CHECK[T](nt: String, p: => Parser[T]) extends Parser[T] {
+  def parse(sb: SubString, ctxt: Ctxt) = {
+    val should_trim = ctxt.contains (nt, sb)
+    if (should_trim && sb.length == 0) Set()
+    else if (should_trim) new IgnLst(p).parse(sb, (nt, sb)::ctxt)
+    else p.parse(sb, (nt, sb)::ctxt)
+  }
+}
+
+// ambigous grammar
+lazy val E: Parser[Int] = 
+  new CHECK("E", (E ~ "+" ~ E) ==> { case ((x, y), z) => x + z} || 
+                 (E ~ "*" ~ E) ==> { case ((x, y), z) => x * z} ||
+                 ("(" ~ E ~ ")") ==> { case ((x, y), z) => y} ||
+                 "0" ==> { (s) => 0 } ||
+                 "1" ==> { (s) => 1 } ||
+                 "2" ==> { (s) => 2 } ||
+                 "3" ==> { (s) => 3 })
+
+println(E.parse_all("1+2*3+3"))
+
+