# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1572177477 0
# Node ID e0d76f7f06885be59e72add05295e191878475f1
# Parent  83e38043ed7804594a298396fe0b193d39dbf4d5
updated

diff -r 83e38043ed78 -r e0d76f7f0688 progs/comb1-test.scala
--- a/progs/comb1-test.scala	Sun Oct 27 11:46:06 2019 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,200 +0,0 @@
-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)))))))")
\ No newline at end of file
diff -r 83e38043ed78 -r e0d76f7f0688 progs/comb1.scala
--- a/progs/comb1.scala	Sun Oct 27 11:46:06 2019 +0000
+++ b/progs/comb1.scala	Sun Oct 27 11:57:57 2019 +0000
@@ -50,7 +50,7 @@
 val NumParser = RegexParser("[0-9]+".r)
 def StringParser(s: String) = RegexParser(Regex.quote(s).r)
 
-// NumParserInt2 transforms a "string integer" into an Int;
+// NumParserInt2 transforms a "string integer" into an actual Int;
 // needs new, because FunParser is not a case class
 val NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)
 
@@ -75,10 +75,13 @@
     new SeqParser[String, String, String](s, r)
 }
 
-// NumParserInt can now be written as
+// NumParserInt can now be written as _ ===> _
+// the first part is the parser, and the second the 
+// semantic action
 val NumParserInt = NumParser ==> (s => s.toInt)
 
 
+// palindromes
 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" || "")
@@ -89,7 +92,7 @@
 
 println("Palindrome: " + Pal.parse_all("abaaaba"))
 
-// well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' )
+// parser for well-nested parentheses (transforms '(' -> '{' , ')' -> '}' )
 lazy val P : Parser[String, String] = 
   "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } || ""
 
@@ -98,6 +101,7 @@
 P.parse_all(")(")
 P.parse_all("()")
 
+// just counts parentheses
 lazy val PC : Parser[String, Int] = 
   ("(" ~ PC ~ ")" ~ PC ==> { case (((_, x), _), y) => x + y + 2 } || 
    "" ==> { (s) => 0 })
@@ -106,6 +110,8 @@
 P.parse_all("(((()()))()))")
 
 // Arithmetic Expressions (Terms and Factors)
+// (because it is mutually recursive, you need :paste 
+//  for munching this definition in the REPL)
 
 lazy val E: Parser[String, Int] = 
   (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
@@ -193,12 +199,12 @@
 
 
 
-
-// a problem with the parser -> gets slow with nestedness
+// a problem with the arithmetic expression parser -> gets 
+// slow with deep nestedness
 E.parse("1")
 E.parse("(1)")
 E.parse("((1))")
 E.parse("(((1)))")
 E.parse("((((1))))")
 E.parse("((((((1))))))")
-E.parse("(((((((1)))))))")
\ No newline at end of file
+E.parse("(((((((1)))))))")
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)))))))")