// Parser Combinators: Simple Version+
−
//====================================+
−
//+
−
// Call with+
−
//+
−
//  amm comb1.sc+
−
+
−
 +
−
//  Note, in the lectures I did not show the type bound+
−
//  using is: I => Seq[_], which means that the input +
−
//  type 'I' needs to be a sequence. +
−
+
−
abstract class Parser[I, T](using is: I => Seq[_])  {+
−
  def parse(in: I): Set[(T, I)]  +
−
+
−
  def parse_all(in: I) : Set[T] =+
−
    for ((hd, tl) <- parse(in); +
−
        if is(tl).isEmpty) yield hd+
−
}+
−
+
−
// parser combinators+
−
+
−
// alternative parser+
−
class AltParser[I, T](p: => Parser[I, T], +
−
                      q: => Parser[I, T])(using I => Seq[_]) extends Parser[I, T] {+
−
  def parse(in: I) = p.parse(in) ++ q.parse(in)   +
−
}+
−
+
−
// sequence parser+
−
class SeqParser[I, T, S](p: => Parser[I, T], +
−
                         q: => Parser[I, S])(using I => Seq[_]) extends Parser[I, (T, S)] {+
−
  def parse(in: I) = +
−
    for ((hd1, tl1) <- p.parse(in); +
−
         (hd2, tl2) <- q.parse(tl1)) yield ((hd1, hd2), tl2)+
−
}+
−
+
−
// map parser+
−
class MapParser[I, T, S](p: => Parser[I, T], +
−
                         f: T => S)(using I => Seq[_]) extends Parser[I, S] {+
−
  def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)+
−
}+
−
+
−
+
−
+
−
// an example of an atomic parser for characters+
−
case class CharParser(c: Char) extends Parser[String, Char] {+
−
  def parse(in: String) = +
−
    if (in != "" && in.head == c) Set((c, in.tail)) else Set()+
−
}+
−
+
−
CharParser('a').parse("abc")+
−
+
−
// an atomic parser for parsing strings according to a regex+
−
import scala.util.matching.Regex+
−
+
−
case class RegexParser(reg: Regex) extends Parser[String, String] {+
−
  def parse(in: String) = reg.findPrefixMatchOf(in) match {+
−
    case None => Set()+
−
    case Some(m) => Set((m.matched, m.after.toString))  +
−
  }+
−
}+
−
+
−
// atomic parsers for numbers and "verbatim" strings +
−
val NumParser = RegexParser("[0-9]+".r)+
−
def StrParser(s: String) = RegexParser(Regex.quote(s).r)+
−
+
−
NumParser.parse("a123a123bc") +
−
StrParser("else").parse("elsethen")+
−
+
−
+
−
// NumParserInt transforms a "string integer" into a propper Int+
−
// (needs "new" because MapParser is not a case class)+
−
+
−
val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt)+
−
NumParserInt.parse("123abc")+
−
+
−
// the following string interpolation allows us to write +
−
// StrParser(_some_string_) more conveniently as +
−
//+
−
// p"<_some_string_>" +
−
+
−
extension (sc: StringContext) +
−
  def p(args: Any*) = StrParser(sc.s(args:_*))+
−
+
−
+
−
(p"else").parse("elsethen")           +
−
+
−
// more convenient syntax for parser combinators+
−
extension [I, T](p: Parser[I, T])(using I => Seq[_]) {+
−
  def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)+
−
  def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)+
−
  def mapp[S](f: => T => S) = new MapParser[I, T, S](p, f)+
−
}+
−
+
−
def toU(s: String) = s.map(_.toUpper)+
−
+
−
(p"ELSE").mapp(toU(_)).parse("ELSEifthen")  +
−
+
−
// these implicits allow us to use an infix notation for+
−
// sequences and alternatives; we also can write the usual+
−
// map for a MapParser+
−
+
−
+
−
// with this NumParserInt can now be written more conveniently+
−
// as:+
−
+
−
val NumParserInt2 = NumParser.map(_.toInt)+
−
+
−
+
−
// A parser for palindromes (just returns them as string)+
−
lazy val Pal : Parser[String, String] = {+
−
   (p"a" ~ Pal ~ p"a").mapp{ case ((x, y), z) => s"$x$y$z" } || +
−
   (p"b" ~ Pal ~ p"b").mapp{ case ((x, y), z) => s"$x$y$z" } || +
−
    p"a" || p"b" || p""+
−
}  +
−
+
−
// examples+
−
Pal.parse_all("abaaaba")+
−
Pal.parse("abaaaba")+
−
+
−
println("Palindrome: " + Pal.parse_all("abaaaba"))+
−
+
−
// A parser for wellnested parentheses +
−
//+
−
//   P ::= ( P ) P | epsilon+
−
//+
−
//   (transforms '(' -> '{' , ')' -> '}' )+
−
lazy val P : Parser[String, String] = {+
−
  (p"(" ~ P ~ p")" ~ P).mapp{ case (((_, x), _), y) => "{" + x + "}" + y } ||+
−
  p""+
−
}  +
−
+
−
println(P.parse_all("(((()()))())"))+
−
println(P.parse_all("(((()()))()))"))+
−
println(P.parse_all(")("))+
−
println(P.parse_all("()"))+
−
+
−
// A parser for arithmetic expressions (Terms and Factors)+
−
+
−
lazy val E: Parser[String, Int] = {+
−
  (T ~ p"+" ~ E).map{ case ((x, _), z) => x + z } ||+
−
  (T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T }+
−
lazy val T: Parser[String, Int] = {+
−
  (F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F }+
−
lazy val F: Parser[String, Int] = {+
−
  (p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt }+
−
+
−
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"))+
−
+
−
+
−
// with parser combinators (and other parsing algorithms)+
−
// no left-recursion is allowed, otherwise the will loop+
−
+
−
lazy val EL: Parser[String, Int] = +
−
  ((EL ~ p"+" ~ EL).map{ case ((x, y), z) => x + z} || +
−
   (EL ~ p"*" ~ EL).map{ case ((x, y), z) => x * z} ||+
−
   (p"(" ~ EL ~ p")").map{ case ((x, y), z) => y} ||+
−
   NumParserInt)+
−
+
−
// this will run forever:+
−
//println(EL.parse_all("1+2+3"))+
−
+
−
+
−
// non-ambiguous vs ambiguous grammars+
−
+
−
// ambiguous+
−
lazy val S : Parser[String, String] =+
−
  (p"1" ~ S ~ S).map{ case ((x, y), z) => x + y + z } || p""+
−
+
−
//println(time(S.parse("1" * 10)))+
−
//println(time(S.parse_all("1" * 10)))+
−
+
−
// non-ambiguous+
−
lazy val U : Parser[String, String] =+
−
  (p"1" ~ U).map{ case (x, y) => x + y } || p""+
−
+
−
//println(time(U.parse("1" * 10)))+
−
//println(time(U.parse_all("1" * 10)))+
−
println(U.parse("1" * 25))+
−
+
−
U.parse("11")+
−
U.parse("11111")+
−
U.parse("11011")+
−
+
−
U.parse_all("1" * 100)+
−
U.parse_all("1" * 100 + "0")+
−
+
−
// you can see the difference in second example+
−
//S.parse_all("1" * 100)         // succeeds+
−
//S.parse_all("1" * 100 + "0")   // fails+
−
+
−
+
−
// A variant which counts how many 1s are parsed+
−
lazy val UCount : Parser[String, Int] =+
−
  (p"1" ~ UCount).map{ case (_, y) => y + 1 } || p"".map{ _ => 0 }+
−
+
−
println(UCount.parse("11111"))+
−
println(UCount.parse_all("11111"))+
−
+
−
// Two single character parsers+
−
lazy val One : Parser[String, String] = p"a"+
−
lazy val Two : Parser[String, String] = p"b"+
−
+
−
One.parse("a")+
−
One.parse("aaa")+
−
+
−
// note how the pairs nest to the left with sequence parsers+
−
(One ~ One).parse("aaa")+
−
(One ~ One ~ One).parse("aaa")+
−
(One ~ One ~ One ~ One).parse("aaaa")+
−
+
−
(One || Two).parse("aaa")+
−
+
−
+
−
+
−
// a problem with the arithmetic expression parser: it +
−
// gets very slow with deeply nested parentheses+
−
+
−
println("Runtime problem")+
−
println(E.parse("1"))+
−
println(E.parse("(1)"))+
−
println(E.parse("((1))"))+
−
println(E.parse("(((1)))"))+
−
println(E.parse("((((1))))"))+
−
//println(E.parse("((((((1))))))"))+
−
//println(E.parse("(((((((1)))))))"))+
−
//println(E.parse("((((((((1))))))))"))+
−
+
−
+
−
// faster because of merge+
−
lazy val E2: Parser[String, Int] = {+
−
  (T2 ~ (p"+" || p"-") ~ E2).mapp[Int]{ case ((x, y), z) => if (y == "+") x + z else x - z} || T2 }+
−
lazy val T2: Parser[String, Int] = {+
−
  (F2 ~ p"*" ~ T2).mapp[Int]{ case ((x, _), z) => x * z } || F2 }+
−
lazy val F2: Parser[String, Int] = {+
−
  (p"(" ~ E2 ~ p")").mapp[Int]{ case ((_, y), _) => y } || NumParserInt }+
−
+
−
+
−
println("Runtime problem")+
−
println(E2.parse("1"))+
−
println(E2.parse("(1)"))+
−
println(E2.parse("((1))"))+
−
println(E2.parse("(((1)))"))+
−
println(E2.parse("((((1))))"))+
−
//println(E2.parse("((((((1))))))"))+
−
//println(E2.parse("(((((((1)))))))"))+
−
//println(E2.parse("((((((((1))))))))"))+
−