1 // Parser Combinators: Simple Version |
1 // Parser Combinators: Simple Version |
2 //==================================== |
2 //==================================== |
3 |
3 // |
4 /* |
4 // Call with |
5 Note, in the lectures I did not show the implicit type constraint |
5 // |
6 I : IsSeq, which means that the input type 'I' needs to be |
6 // amm comb1.sc |
7 a sequence. |
7 |
8 */ |
8 |
|
9 // Note, in the lectures I did not show the implicit type constraint |
|
10 // I : IsSeq, which means that the input type 'I' needs to be |
|
11 // a sequence. |
9 |
12 |
10 type IsSeq[A] = A => Seq[_] |
13 type IsSeq[A] = A => Seq[_] |
11 |
14 |
12 abstract class Parser[I : IsSeq, T]{ |
15 abstract class Parser[I : IsSeq, T]{ |
13 def parse(in: I): Set[(T, I)] |
16 def parse(in: I): Set[(T, I)] |
31 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
34 class AltParser[I : IsSeq, T](p: => Parser[I, T], |
32 q: => Parser[I, T]) extends Parser[I, T] { |
35 q: => Parser[I, T]) extends Parser[I, T] { |
33 def parse(in: I) = p.parse(in) ++ q.parse(in) |
36 def parse(in: I) = p.parse(in) ++ q.parse(in) |
34 } |
37 } |
35 |
38 |
36 // parser map |
39 // map parser |
37 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], |
40 class MapParser[I : IsSeq, T, S](p: => Parser[I, T], |
38 f: T => S) extends Parser[I, S] { |
41 f: T => S) extends Parser[I, S] { |
39 def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
42 def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl) |
40 } |
43 } |
|
44 |
|
45 |
41 |
46 |
42 // an example of an atomic parser for characters |
47 // an example of an atomic parser for characters |
43 case class CharParser(c: Char) extends Parser[String, Char] { |
48 case class CharParser(c: Char) extends Parser[String, Char] { |
44 def parse(in: String) = |
49 def parse(in: String) = |
45 if (in != "" && in.head == c) Set((c, in.tail)) else Set() |
50 if (in != "" && in.head == c) Set((c, in.tail)) else Set() |
56 } |
61 } |
57 |
62 |
58 // atomic parsers for numbers and "verbatim" strings |
63 // atomic parsers for numbers and "verbatim" strings |
59 val NumParser = RegexParser("[0-9]+".r) |
64 val NumParser = RegexParser("[0-9]+".r) |
60 def StrParser(s: String) = RegexParser(Regex.quote(s).r) |
65 def StrParser(s: String) = RegexParser(Regex.quote(s).r) |
|
66 |
61 |
67 |
62 // NumParserInt transforms a "string integer" into a propper Int |
68 // NumParserInt transforms a "string integer" into a propper Int |
63 // (needs "new" because MapParser is not a case class) |
69 // (needs "new" because MapParser is not a case class) |
64 |
70 |
65 val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt) |
71 val NumParserInt = new MapParser(NumParser, (s: String) => s.toInt) |
208 (One || Two).parse("aaa") |
214 (One || Two).parse("aaa") |
209 |
215 |
210 |
216 |
211 |
217 |
212 // a problem with the arithmetic expression parser: it |
218 // a problem with the arithmetic expression parser: it |
213 // gets vert slow with deeply nested parentheses |
219 // gets very slow with deeply nested parentheses |
214 |
220 |
215 println("Runtime problem") |
221 println("Runtime problem") |
216 println(E.parse("1")) |
222 println(E.parse("1")) |
217 println(E.parse("(1)")) |
223 println(E.parse("(1)")) |
218 println(E.parse("((1))")) |
224 println(E.parse("((1))")) |