import scala.language.implicitConversions+
−
import scala.language.reflectiveCalls+
−
+
−
/* Note, in the lectures I did not show the implicit type consraint+
−
 * I => Seq[_], which means that the input type 'I' needs to be+
−
 * a sequence. */+
−
+
−
type IsSeq[A] = A => Seq[_]+
−
+
−
abstract class Parser[I : IsSeq, 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+
−
}+
−
+
−
// convenience for matching later on+
−
case class ~[+A, +B](_1: A, _2: B)+
−
+
−
class SeqParser[I : IsSeq, 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 (new ~(head1, head2), tail2)+
−
}+
−
+
−
class AltParser[I : IsSeq, 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 : IsSeq, 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 for characters, numbers and strings+
−
case class CharParser(c: Char) extends Parser[String, Char] {+
−
  def parse(sb: String) = +
−
    if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()+
−
}+
−
+
−
import scala.util.matching.Regex+
−
case class RegexParser(reg: Regex) extends Parser[String, String] {+
−
  def parse(sb: String) = reg.findPrefixMatchOf(sb) match {+
−
    case None => Set()+
−
    case Some(m) => Set((m.matched, m.after.toString))  +
−
  }+
−
}+
−
+
−
val NumParser = RegexParser("[0-9]+".r)+
−
def StringParser(s: String) = RegexParser(Regex.quote(s).r)+
−
+
−
// NumParserInt2 transforms a "string integer" into an Int;+
−
// needs new, because FunParser is not a case class+
−
+
−
val NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)+
−
+
−
+
−
// convenience+
−
implicit def string2parser(s: String) = StringParser(s)+
−
implicit def char2parser(c: Char) = CharParser(c)+
−
+
−
implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = 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)+
−
}+
−
+
−
// NumParserInt can now be written as+
−
val NumParserInt = NumParser ==> (s => s.toInt)+
−
+
−
+
−
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 } || "a" || "b" || "")+
−
+
−
Pal.parse_all("abaaaba")+
−
Pal.parse("abaaaba")+
−
+
−
println("Palindrome: " + Pal.parse_all("abaaaba"))+
−
+
−
// well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' )+
−
lazy val P : Parser[String, String] = +
−
  "(" ~ P ~ ")" ~ P ==> { case _ ~ x ~ _ ~ y => "{" + x + "}" + y } || ""+
−
+
−
P.parse_all("(((()()))())")+
−
P.parse_all("(((()()))()))")+
−
P.parse_all(")(")+
−
P.parse_all("()")+
−
+
−
// Arithmetic Expressions (Terms and Factors)+
−
+
−
lazy val E: Parser[String, Int] = +
−
  (T ~ "+" ~ E) ==> { case x ~ y ~ z => x + z } ||+
−
  (T ~ "-" ~ E) ==> { case x ~ y ~ z => x - z } || T +
−
lazy val T: Parser[String, Int] = +
−
  (F ~ "*" ~ T) ==> { case x ~ y ~ z => x * z } || F+
−
lazy val F: Parser[String, Int] = +
−
  ("(" ~ E ~ ")") ==> { case x ~ y ~ z => y } || NumParserInt+
−
+
−
/* same parser but producing a string+
−
lazy val E: Parser[String, String] = +
−
  (T ~ "+" ~ E) ==> { case ((x, y), z) => "(" + x + ")+(" + z + ")"} || T +
−
lazy val T: Parser[String, String] = +
−
  (F ~ "*" ~ T) ==> { case ((x, y), z) => "(" + x + ")*("+ z + ")"} || F+
−
lazy val F: Parser[String, String] = +
−
  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser+
−
*/+
−
+
−
println(E.parse_all("1+3+4"))+
−
println(E.parse("1+3+4"))+
−
println(E.parse_all("4*2+3"))+
−
println(E.parse_all("4*(2+3)"))+
−
println(E.parse_all("(4)*((2+3))"))+
−
println(E.parse_all("4/2+3"))+
−
println(E.parse("1 + 2 * 3"))+
−
println(E.parse_all("(1+2)+3"))+
−
println(E.parse_all("1+2+3"))  +
−
+
−
+
−
+
−
// no left-recursion allowed, otherwise will loop+
−
lazy val EL: Parser[String, Int] = +
−
  (EL ~ "+" ~ EL ==> { case x ~ y ~ z => x + z} || +
−
   EL ~ "*" ~ EL ==> { case x ~ y ~ z => x * z} ||+
−
   "(" ~ EL ~ ")" ==> { case x ~ y ~ z => y} ||+
−
   NumParserInt)+
−
+
−
//println(EL.parse_all("1+2+3"))+
−
+
−
+
−
+
−
+
−
// non-ambiguous vs ambiguous grammars+
−
+
−
// ambiguous+
−
lazy val S : Parser[String, String] =+
−
  ("1" ~ S ~ S) ==> { case x ~ y ~ z => x + y + z } || ""+
−
+
−
S.parse("1" * 10)+
−
+
−
// non-ambiguous+
−
lazy val U : Parser[String, String] =+
−
  ("1" ~ U) ==> { case x ~ y => x + y  } || ""+
−
+
−
U.parse("1" * 25)+
−
+
−
U.parse("11")+
−
U.parse("11111")+
−
U.parse("11011")+
−
+
−
U.parse_all("1" * 100)+
−
U.parse_all("1" * 100 + "0")+
−
+
−
lazy val UCount : Parser[String, Int] =+
−
  ("1" ~ UCount) ==> { case x ~ y => y + 1 } || "" ==> { x => 0 }+
−
+
−
UCount.parse("11111")+
−
UCount.parse_all("11111")+
−
+
−
+
−
+
−
// Single Character parser+
−
lazy val One : Parser[String, String] = "1"+
−
lazy val Two : Parser[String, String] = "2"+
−
+
−
One.parse("1")+
−
One.parse("111")+
−
+
−
(One ~ One).parse("111")+
−
(One ~ One ~ One).parse("111")+
−
(One ~ One ~ One ~ One).parse("1111")+
−
+
−
(One || Two).parse("111")+
−
+
−
+
−
+
−
+
−
+
−
// a problem with the parser -> gets slow with nestedness+
−
E.parse("1")+
−
E.parse("(1)")+
−
E.parse("((1))")+
−
E.parse("(((1)))")+
−
E.parse("((((1))))")+
−
E.parse("((((((1))))))")+
−
E.parse("(((((((1)))))))")+
−