import scala.language.implicitConversionsimport scala.language.reflectiveCalls// more convenience for the semantic actions later oncase class ~[+A, +B](_1: A, _2: B)/* 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}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 stringscase 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.Regexcase 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 classval NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)// convenienceimplicit 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 asval 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 } || Flazy val F: Parser[String, Int] = ("(" ~ E ~ ")") ==> { case x ~ y ~ z => y } || NumParserInt/* same parser but producing a stringlazy 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 + ")"} || Flazy 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 looplazy 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// ambiguouslazy val S : Parser[String, String] = ("1" ~ S ~ S) ==> { case x ~ y ~ z => x + y + z } || ""S.parse("1" * 10)// non-ambiguouslazy 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 parserlazy 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 arithmetic expression parser -> gets // slow with deep nestednessprintln("Runtime problem")E.parse("1")E.parse("(1)")E.parse("((1))")E.parse("(((1)))")E.parse("((((1))))")E.parse("((((((1))))))")E.parse("(((((((1)))))))")E.parse("((((((((1)))))))")