--- a/progs/comb1.scala	Sun Jul 28 21:10:39 2019 +0100
+++ b/progs/comb1.scala	Tue Jul 30 20:19:40 2019 +0100
@@ -2,8 +2,8 @@
 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, subtype of Seq. */
+ * I => Seq[_], which means that the input type 'I' needs to be
+ * a sequence. */
 
 abstract class Parser[I, T](implicit ev: I => Seq[_]) {
   def parse(ts: I): Set[(T, I)]
@@ -31,7 +31,7 @@
     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
 }
 
-// atomic parsers  
+// 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()
@@ -48,9 +48,9 @@
 val NumParser = RegexParser("[0-9]+".r)
 def StringParser(s: String) = RegexParser(Regex.quote(s).r)
 
-// NumParserInt transforms a "string integer" into an Int;
+// NumParserInt2 transforms a "string integer" into an Int;
 // needs new, because FunParser is not a case class
-val NumParserInt = new FunParser(NumParser, (s: String) => s.toInt)
+val NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)
 
 
 // convenience
@@ -58,14 +58,14 @@
 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 || (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 || (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)
@@ -78,8 +78,8 @@
 
 
 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" | "")
+  (("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")
@@ -88,29 +88,31 @@
 
 // well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' )
 lazy val P : Parser[String, String] = 
-  "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } | ""
+  "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } || ""
 
 P.parse_all("(((()()))())")
 P.parse_all("(((()()))()))")
 P.parse_all(")(")
 P.parse_all("()")
 
-// Arithmetic Expressions
+// 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 
+  (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
+  (F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } || F
 lazy val F: Parser[String, Int] = 
-  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } | NumParserInt
+  ("(" ~ 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 
+  (T ~ "+" ~ E) ==> { case ((x, y), z) => "(" + x + ")+(" + z + ")"} || T 
 lazy val T: Parser[String, String] = 
-  (F ~ "*" ~ T) ==> { case ((x, y), z) => "(" + x + ")*("+ z + ")"} | F
+  (F ~ "*" ~ T) ==> { case ((x, y), z) => "(" + x + ")*("+ z + ")"} || F
 lazy val F: Parser[String, String] = 
-  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } | NumParser
+  ("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser
+*/
 
 println(E.parse_all("1+3+4"))
 println(E.parse("1+3+4"))
@@ -126,9 +128,9 @@
 
 // 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} |
+  (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"))
@@ -137,13 +139,16 @@
 
 
 // non-ambiguous vs ambiguous grammars
+
+// ambiguous
 lazy val S : Parser[String, String] =
-  ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } | ""
+  ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
 
-S.parse("1" * 17)
+S.parse("1" * 10)
 
+// non-ambiguous
 lazy val U : Parser[String, String] =
-  ("1" ~ U) ==> { case (x, y) => x + y  } | ""
+  ("1" ~ U) ==> { case (x, y) => x + y  } || ""
 
 U.parse("1" * 25)
 
@@ -155,7 +160,7 @@
 U.parse_all("1" * 100 + "0")
 
 lazy val UCount : Parser[String, Int] =
-  ("1" ~ UCount) ==> { case (x, y) => y + 1 } | "" ==> { x => 0 }
+  ("1" ~ UCount) ==> { case (x, y) => y + 1 } || "" ==> { x => 0 }
 
 UCount.parse("11111")
 UCount.parse_all("11111")
@@ -173,7 +178,17 @@
 (One ~ One ~ One).parse("111")
 (One ~ One ~ One ~ One).parse("1111")
 
-(One | Two).parse("111")
+(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