diff -r 15973df32613 -r 2bf1516d730f progs/parser-combinators/comb1-2.sc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/parser-combinators/comb1-2.sc	Tue Apr 04 22:31:09 2023 +0100
@@ -0,0 +1,241 @@
+// Parser Combinators: Simple Version
+//====================================
+//
+// Call with Ammonite (Scala 2.13.10)
+//
+//  amm comb1-2.sc
+
+ 
+//  Note, in the lectures I did not show the implicit type bound
+//  I : IsSeq, 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(in: I): Set[(T, I)]  
+
+  def parse_all(in: I) : Set[T] =
+    for ((hd, tl) <- parse(in); 
+        if tl.isEmpty) yield hd
+}
+
+// parser combinators
+
+// alternative parser
+class AltParser[I : IsSeq, T](p: => Parser[I, T], 
+                              q: => Parser[I, T]) extends Parser[I, T] {
+  def parse(in: I) = p.parse(in) ++ q.parse(in)   
+}
+
+// sequence parser
+class SeqParser[I : IsSeq, T, S](p: => Parser[I, T], 
+                                 q: => Parser[I, S]) 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 : IsSeq, T, S](p: => Parser[I, T], 
+                                 f: T => S) 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('c').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("eelsethen")
+
+
+// NumParserInt transforms a "string integer" into a proper 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_>" 
+
+
+implicit def parser_interpolation(sc: StringContext) = new {
+  def p(args: Any*) = StrParser(sc.s(args:_*))
+}
+
+(p"else").parse("elsethen")           
+
+// more convenient syntax for parser combinators
+
+implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
+  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 map[S](f: => T => S) = new MapParser[I, T, S](p, f)
+}
+
+// example
+def toU(s: String) = s.map(_.toUpper)
+(p"ELSE").map(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").map{ case ((x, y), z) => s"$x$y$z" } || 
+   (p"b" ~ Pal ~ p"b").map{ 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).map{ 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 they 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)))))))"))
+