diff -r 83e38043ed78 -r e0d76f7f0688 progs/comb1a.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/comb1a.scala Sun Oct 27 11:57:57 2019 +0000 @@ -0,0 +1,203 @@ +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +// more convenience for the semantic actions later on +case 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 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 arithmetic expression parser -> gets +// slow with deep nestedness +println("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)))))))")