progs/parser-combinators/comb1.sc
changeset 954 eda0ccf56c72
parent 948 6bb67c2dcfd3
child 956 ae9782e62bdd
equal deleted inserted replaced
953:5e070fb0332a 954:eda0ccf56c72
    17 
    17 
    18   def parse_all(in: I) : Set[T] =
    18   def parse_all(in: I) : Set[T] =
    19     for ((hd, tl) <- parse(in); 
    19     for ((hd, tl) <- parse(in); 
    20         if is(tl).isEmpty) yield hd
    20         if is(tl).isEmpty) yield hd
    21 }
    21 }
       
    22 
    22 
    23 
    23 // parser combinators
    24 // parser combinators
    24 
    25 
    25 
    26 
    26 // alternative parser
    27 // alternative parser
    37          (hd2, tl2) <- q.parse(tl1)) yield ((hd1, hd2), tl2)
    38          (hd2, tl2) <- q.parse(tl1)) yield ((hd1, hd2), tl2)
    38 }
    39 }
    39 
    40 
    40 // map parser
    41 // map parser
    41 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], 
    42 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], 
    42                          f: T => S) extends Parser[I, S] {
    43                                  f: T => S) extends Parser[I, S] {
    43   def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)
    44   def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)
    44 }
    45 }
    45 
    46 
    46 
    47 
    47 
    48 
    49 case class CharParser(c: Char) extends Parser[String, Char] {
    50 case class CharParser(c: Char) extends Parser[String, Char] {
    50   def parse(in: String) = 
    51   def parse(in: String) = 
    51     if (in != "" && in.head == c) Set((c, in.tail)) else Set()
    52     if (in != "" && in.head == c) Set((c, in.tail)) else Set()
    52 }
    53 }
    53 
    54 
    54 CharParser('a').parse("abc")
    55 val ap = CharParser('a')
       
    56 val bp = CharParser('b')
       
    57 
       
    58 val abp = SeqParser(ap, bp)
       
    59 MapParser(abp, ab => s"$ab").parse("abc")
    55 
    60 
    56 // an atomic parser for parsing strings according to a regex
    61 // an atomic parser for parsing strings according to a regex
    57 import scala.util.matching.Regex
    62 import scala.util.matching.Regex
    58 
    63 
    59 case class RegexParser(reg: Regex) extends Parser[String, String] {
    64 case class RegexParser(reg: Regex) extends Parser[String, String] {
    65 
    70 
    66 // atomic parsers for numbers and "verbatim" strings 
    71 // atomic parsers for numbers and "verbatim" strings 
    67 val NumParser = RegexParser("[0-9]+".r)
    72 val NumParser = RegexParser("[0-9]+".r)
    68 def StrParser(s: String) = RegexParser(Regex.quote(s).r)
    73 def StrParser(s: String) = RegexParser(Regex.quote(s).r)
    69 
    74 
    70 NumParser.parse("a123a123bc") 
    75 NumParser.parse("123a123bc") 
    71 StrParser("else").parse("elsethen")
    76 StrParser("else").parse("elsethen")
    72 
    77 
    73 
    78 
    74 // NumParserInt transforms a "string integer" into a propper Int
    79 // NumParserInt transforms a "string integer" into a propper Int
    75 // (needs "new" because MapParser is not a case class)
    80 // (needs "new" because MapParser is not a case class)
    76 
    81 
    77 val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt)
    82 val NumParserInt = MapParser(NumParser, (s: String) => s.toInt)
    78 NumParserInt.parse("123abc")
    83 NumParserInt.parse("123abc")
    79 
    84 
    80 // the following string interpolation allows us to write 
    85 // the following string interpolation allows us to write 
    81 // StrParser(_some_string_) more conveniently as 
    86 // StrParser(_some_string_) more conveniently as 
    82 //
    87 //
   109 // with this NumParserInt can now be written more conveniently
   114 // with this NumParserInt can now be written more conveniently
   110 // as:
   115 // as:
   111 
   116 
   112 val NumParserInt2 = NumParser.map(_.toInt)
   117 val NumParserInt2 = NumParser.map(_.toInt)
   113 
   118 
       
   119 val x = 1 + 3
   114 
   120 
   115 // A parser for palindromes (just returns them as string)
   121 // A parser for palindromes (just returns them as string)
   116 //  since the parser is recursive it needs to be lazy
   122 //  since the parser is recursive it needs to be lazy
   117 lazy val Pal : Parser[String, String] = {
   123 lazy val Pal : Parser[String, String] = {
   118    (p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } || 
   124    (p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } || 
   119    (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } || 
   125    (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } || 
   120     p"a" || p"b" || p""
   126     p"a" || p"b" || p""
   121 }  
   127 }  
   122 
   128 
   123 // examples
   129 // examples
   124 Pal.parse_all("abaaaba")
   130 Pal.parse_all("abacaba")
   125 Pal.parse("abaaaba")
   131 Pal.parse("abacaaba")
   126 
   132 
   127 println("Palindrome: " + Pal.parse_all("abaaaba"))
   133 println("Palindrome: " + Pal.parse_all("abaaaba"))
   128 
   134 
   129 // A parser for wellnested parentheses 
   135 // A parser for wellnested parentheses 
   130 //
   136 //
   141 println(P.parse_all(")("))
   147 println(P.parse_all(")("))
   142 println(P.parse_all("()"))
   148 println(P.parse_all("()"))
   143 
   149 
   144 // A parser for arithmetic expressions (Terms and Factors)
   150 // A parser for arithmetic expressions (Terms and Factors)
   145 
   151 
       
   152 "1 + 2 * 3"
       
   153 "(1 + 2) * 3"
       
   154 {
   146 lazy val E: Parser[String, Int] = {
   155 lazy val E: Parser[String, Int] = {
   147   (T ~ p"+" ~ E).map{ case ((x, _), z) => x + z } ||
   156   (T ~ p"+" ~ E).map{ case ((x, _), z) => x + z } ||
   148   (T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T }
   157   (T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T }
   149 lazy val T: Parser[String, Int] = {
   158 lazy val T: Parser[String, Int] = {
   150   (F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F }
   159   (F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F }
   151 lazy val F: Parser[String, Int] = {
   160 lazy val F: Parser[String, Int] = {
   152   (p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt }
   161   (p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt }
   153 
   162 }
   154 println(E.parse_all("1+3+4"))
   163 println(E.parse_all("1+3+4"))
   155 println(E.parse("1+3+4"))
   164 println(E.parse("1+3+4"))
   156 println(E.parse_all("4*2+3"))
   165 println(E.parse_all("4*2+3"))
   157 println(E.parse_all("4*(2+3)"))
   166 println(E.parse_all("4*(2+3)"))
   158 println(E.parse_all("(4)*((2+3))"))
   167 println(E.parse_all("(4)*(((2+3)))"))
   159 println(E.parse_all("4/2+3"))
   168 println(E.parse_all("4/2+3"))
   160 println(E.parse("1 + 2 * 3"))
   169 println(E.parse("1 + 2 * 3"))
   161 println(E.parse_all("(1+2)+3"))
   170 println(E.parse_all("(1+2)+3"))
   162 println(E.parse_all("1+2+3"))
   171 println(E.parse_all("1+2+3"))
   163 
   172