87 |
87 |
88 // more convenient syntax for parser combinators |
88 // more convenient syntax for parser combinators |
89 extension [I, T](p: Parser[I, T])(using I => Seq[_]) { |
89 extension [I, T](p: Parser[I, T])(using I => Seq[_]) { |
90 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
90 def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q) |
91 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
91 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
92 def mapp[S](f: => T => S) = new MapParser[I, T, S](p, f) |
92 def map[S](f: => T => S) = new MapParser[I, T, S](p, f) |
93 } |
93 } |
94 |
94 |
95 def toU(s: String) = s.map(_.toUpper) |
95 def toU(s: String) = s.map(_.toUpper) |
96 |
96 |
97 (p"ELSE").mapp(toU(_)).parse("ELSEifthen") |
97 (p"ELSE").map(toU(_)).parse("ELSEifthen") |
98 |
98 |
99 // these implicits allow us to use an infix notation for |
99 // these implicits allow us to use an infix notation for |
100 // sequences and alternatives; we also can write the usual |
100 // sequences and alternatives; we also can write the usual |
101 // map for a MapParser |
101 // map for a MapParser |
102 |
102 |
107 val NumParserInt2 = NumParser.map(_.toInt) |
107 val NumParserInt2 = NumParser.map(_.toInt) |
108 |
108 |
109 |
109 |
110 // A parser for palindromes (just returns them as string) |
110 // A parser for palindromes (just returns them as string) |
111 lazy val Pal : Parser[String, String] = { |
111 lazy val Pal : Parser[String, String] = { |
112 (p"a" ~ Pal ~ p"a").mapp{ case ((x, y), z) => s"$x$y$z" } || |
112 (p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } || |
113 (p"b" ~ Pal ~ p"b").mapp{ case ((x, y), z) => s"$x$y$z" } || |
113 (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } || |
114 p"a" || p"b" || p"" |
114 p"a" || p"b" || p"" |
115 } |
115 } |
116 |
116 |
117 // examples |
117 // examples |
118 Pal.parse_all("abaaaba") |
118 Pal.parse_all("abaaaba") |
124 // |
124 // |
125 // P ::= ( P ) P | epsilon |
125 // P ::= ( P ) P | epsilon |
126 // |
126 // |
127 // (transforms '(' -> '{' , ')' -> '}' ) |
127 // (transforms '(' -> '{' , ')' -> '}' ) |
128 lazy val P : Parser[String, String] = { |
128 lazy val P : Parser[String, String] = { |
129 (p"(" ~ P ~ p")" ~ P).mapp{ case (((_, x), _), y) => "{" + x + "}" + y } || |
129 (p"(" ~ P ~ p")" ~ P).map{ case (((_, x), _), y) => "{" + x + "}" + y } || |
130 p"" |
130 p"" |
131 } |
131 } |
132 |
132 |
133 println(P.parse_all("(((()()))())")) |
133 println(P.parse_all("(((()()))())")) |
134 println(P.parse_all("(((()()))()))")) |
134 println(P.parse_all("(((()()))()))")) |
222 |
222 |
223 |
223 |
224 // a problem with the arithmetic expression parser: it |
224 // a problem with the arithmetic expression parser: it |
225 // gets very slow with deeply nested parentheses |
225 // gets very slow with deeply nested parentheses |
226 |
226 |
227 println("Runtime problem") |
227 println("A runtime problem") |
228 println(E.parse("1")) |
228 println(E.parse("1")) |
229 println(E.parse("(1)")) |
229 println(E.parse("(1)")) |
230 println(E.parse("((1))")) |
230 println(E.parse("((1))")) |
231 println(E.parse("(((1)))")) |
231 println(E.parse("(((1)))")) |
232 println(E.parse("((((1))))")) |
232 println(E.parse("((((1))))")) |
233 //println(E.parse("((((((1))))))")) |
233 println(E.parse("((((((1))))))")) |
234 //println(E.parse("(((((((1)))))))")) |
234 println(E.parse("(((((((1)))))))")) |
235 //println(E.parse("((((((((1))))))))")) |
235 //println(E.parse("((((((((1))))))))")) |
236 |
236 |
237 |
237 |
238 // faster because of merge |
238 // faster because of merge in the +/- case |
239 lazy val E2: Parser[String, Int] = { |
239 lazy val E2: Parser[String, Int] = { |
240 (T2 ~ (p"+" || p"-") ~ E2).mapp[Int]{ case ((x, y), z) => if (y == "+") x + z else x - z} || T2 } |
240 (T2 ~ (p"+" || p"-") ~ E2).map[Int]{ case ((x, y), z) => if (y == "+") x + z else x - z} || T2 } |
241 lazy val T2: Parser[String, Int] = { |
241 lazy val T2: Parser[String, Int] = { |
242 (F2 ~ p"*" ~ T2).mapp[Int]{ case ((x, _), z) => x * z } || F2 } |
242 (F2 ~ p"*" ~ T2).map[Int]{ case ((x, _), z) => x * z } || F2 } |
243 lazy val F2: Parser[String, Int] = { |
243 lazy val F2: Parser[String, Int] = { |
244 (p"(" ~ E2 ~ p")").mapp[Int]{ case ((_, y), _) => y } || NumParserInt } |
244 (p"(" ~ E2 ~ p")").map[Int]{ case ((_, y), _) => y } || NumParserInt } |
245 |
245 |
246 |
246 |
247 println("Runtime problem") |
247 println("mitigated by merging clauses") |
248 println(E2.parse("1")) |
248 println(E2.parse("1")) |
249 println(E2.parse("(1)")) |
249 println(E2.parse("(1)")) |
250 println(E2.parse("((1))")) |
250 println(E2.parse("((1))")) |
251 println(E2.parse("(((1)))")) |
251 println(E2.parse("(((1)))")) |
252 println(E2.parse("((((1))))")) |
252 println(E2.parse("((((1))))")) |
253 //println(E2.parse("((((((1))))))")) |
253 println(E2.parse("((((((1))))))")) |
254 //println(E2.parse("(((((((1)))))))")) |
254 println(E2.parse("(((((((1)))))))")) |
255 //println(E2.parse("((((((((1))))))))")) |
255 println(E2.parse("((((((((1))))))))")) |