afl-material: comparison progs/parser-combinators/comb1.sc

equal deleted inserted replaced

-:409e5014edde
+:c18b991eaad2
 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)
 }
-// 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)
-}
 // 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()
 }
 // an atomic parser for parsing strings according to a regex
 import scala.util.matching.Regex
 case class RegexParser(reg: Regex) extends Parser[String, String] {
 // atomic parsers for numbers and "verbatim" strings
 val NumParser = RegexParser("[0-9]+".r)
 def StrParser(s: String) = RegexParser(Regex.quote(s).r)
 // NumParserInt transforms a "string integer" into a propper Int
 // (needs "new" because MapParser is not a case class)
 val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt)
 // p"<_some_string_>"
 implicit def parser_interpolation(sc: StringContext) = new {
 def p(args: Any*) = StrParser(sc.s(args:_*))
 }
 // 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)
 // with this NumParserInt can now be written more conveniently
 // as:
-val NumParserInt2 = NumParser.map(s => s.toInt)
+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" } ||
 Pal.parse_all("abaaaba")
 Pal.parse("abaaaba")
 println("Palindrome: " + Pal.parse_all("abaaaba"))
-// A parser for wellnested parentheses (transforms '(' -> '{' , ')' -> '}' )
+// A parser for wellnested parentheses
-lazy val P : Parser[String, String] =
+//
-(p"(" ~ P ~ p")" ~ P).map{ case (((_, x), _), y) => "{" + x + "}" + y } || p""
+//   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] =
+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
+(T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T }
-lazy val T: Parser[String, Int] =
+lazy val T: Parser[String, Int] = {
-(F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F
+(F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F }
-lazy val F: Parser[String, Int] =
+lazy val F: Parser[String, Int] = {
-(p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt
+(p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt }
-/* same parser but producing a string
-lazy val E: Parser[String, String] =
-(T ~ "+" ~ E).map{ case x ~ y ~ z => "(" + x + ")+(" + z + ")"} || T
-lazy val T: Parser[String, String] =
-(F ~ "*" ~ T).map{ case x ~ y ~ z => "(" + x + ")*("+ z + ")"} || F
-lazy val F: Parser[String, String] =
-("(" ~ E ~ ")").map{ 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"))
 // with parser combinators (and other parsing algorithms)
 // no left-recursion is allowed, otherwise the will loop
 //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[Int]{ case (_, y) => y + 1 } || p"".map[Int]{ _ => 0 }
+(p"1" ~ UCount).map{ case (_, y) => y + 1 } || p"".map{ _ => 0 }
 println(UCount.parse("11111"))
 println(UCount.parse_all("11111"))
 // Two single character parsers

changeset 799	c18b991eaad2
parent 742	155426396b5f
child 801	b17a43f80ed0