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 |