afl-material: comparison progs/comb1.scala

equal deleted inserted replaced

-:f5214da1976e
+:8067d0a8ba04
 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
+* I => Seq[_], which means that the input type 'I' needs to be
-* a sequence, subtype of Seq. */
+* a sequence. */
 abstract class Parser[I, T](implicit ev: I => Seq[_]) {
 def parse(ts: I): Set[(T, I)]
 def parse_all(ts: I) : Set[T] =
 f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] {
 def parse(sb: I) =
 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()
 }
 }
 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
 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 || (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 || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
-def | (r: String) = new AltParser[String, String](s, r)
+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 } |
+(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
-("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } | "a" | "b" | "")
+("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 ~ ")" ~ 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 ~ "-" ~ E) ==> { case ((x, y), z) => x - z } | T
+(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"))
 println(E.parse_all("4*2+3"))
 println(E.parse_all("4*(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 ~ "*" ~ EL ==> { case ((x, y), z) => x * z} |
+EL ~ "*" ~ EL ==> { case ((x, y), z) => x * z} ||
-"(" ~ EL ~ ")" ==> { case ((x, y), z) => y} |
+"(" ~ 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 } | ""
+("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)
 U.parse("11")
 U.parse("11111")
 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 }
+("1" ~ UCount) ==> { case (x, y) => y + 1 } || "" ==> { x => 0 }
 UCount.parse("11111")
 UCount.parse_all("11111")
 (One ~ One).parse("111")
 (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)))))))")

changeset 628	8067d0a8ba04
parent 624	8d0af38389bc
child 629	1b718d6065c2