1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
3 |
3 |
4 /* Note, in the lectures I did not show the type consraint |
4 /* Note, in the lectures I did not show the implicit type consraint |
5 * I <% Seq[_] , which means that the input type I can be |
5 * I => Seq[_] , which means that the input type I needs to be |
6 * treated, or seen, as a sequence. */ |
6 * a sequence, subtype of Seq. */ |
7 |
7 |
8 abstract class Parser[I <% Seq[_], T] { |
8 abstract class Parser[I, T](implicit ev: I => Seq[_]) { |
9 def parse(ts: I): Set[(T, I)] |
9 def parse(ts: I): Set[(T, I)] |
10 |
10 |
11 def parse_all(ts: I) : Set[T] = |
11 def parse_all(ts: I) : Set[T] = |
12 for ((head, tail) <- parse(ts); |
12 for ((head, tail) <- parse(ts); |
13 if (tail.isEmpty)) yield head |
13 if (tail.isEmpty)) yield head |
14 } |
14 } |
15 |
15 |
16 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], |
16 class SeqParser[I, T, S](p: => Parser[I, T], |
17 q: => Parser[I, S]) extends Parser[I, (T, S)] { |
17 q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] { |
18 def parse(sb: I) = |
18 def parse(sb: I) = |
19 for ((head1, tail1) <- p.parse(sb); |
19 for ((head1, tail1) <- p.parse(sb); |
20 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
20 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
21 } |
21 } |
22 |
22 |
23 class AltParser[I <% Seq[_], T](p: => Parser[I, T], |
23 class AltParser[I, T](p: => Parser[I, T], |
24 q: => Parser[I, T]) extends Parser[I, T] { |
24 q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] { |
25 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
25 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
26 } |
26 } |
27 |
27 |
28 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], |
28 class FunParser[I, T, S](p: => Parser[I, T], |
29 f: T => S) extends Parser[I, S] { |
29 f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] { |
30 def parse(sb: I) = |
30 def parse(sb: I) = |
31 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
31 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
32 } |
32 } |
33 |
33 |
34 // atomic parsers |
34 // atomic parsers |
46 } |
46 } |
47 |
47 |
48 val NumParser = RegexParser("[0-9]+".r) |
48 val NumParser = RegexParser("[0-9]+".r) |
49 def StringParser(s: String) = RegexParser(Regex.quote(s).r) |
49 def StringParser(s: String) = RegexParser(Regex.quote(s).r) |
50 |
50 |
51 val NumParserInt = NumParser ==> (s => s.toInt) |
51 // NumParserInt transforms a "string integer" into an Int; |
|
52 // needs new, because FunParser is not a case class |
|
53 val NumParserInt = new FunParser(NumParser, (s: String) => s.toInt) |
|
54 |
52 |
55 |
53 // convenience |
56 // convenience |
54 implicit def string2parser(s: String) = StringParser(s) |
57 implicit def string2parser(s: String) = StringParser(s) |
55 implicit def char2parser(c: Char) = CharParser(c) |
58 implicit def char2parser(c: Char) = CharParser(c) |
56 |
59 |
57 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
60 implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new { |
58 def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
61 def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
59 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
62 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
60 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
63 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
61 } |
64 } |
62 |
65 |
68 new SeqParser[String, String, S](s, q) |
71 new SeqParser[String, String, S](s, q) |
69 def ~ (r: String) = |
72 def ~ (r: String) = |
70 new SeqParser[String, String, String](s, r) |
73 new SeqParser[String, String, String](s, r) |
71 } |
74 } |
72 |
75 |
|
76 // NumParserInt can now be written as |
|
77 val NumParserInt = NumParser ==> (s => s.toInt) |
|
78 |
73 |
79 |
74 lazy val Pal : Parser[String, String] = |
80 lazy val Pal : Parser[String, String] = |
75 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } | |
81 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } | |
76 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } | "a" | "b" | "") |
82 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } | "a" | "b" | "") |
77 |
83 |
78 Pal.parse_all("abaaaba") |
84 Pal.parse_all("abaaaba") |
79 Pal.parse("abaaaba") |
85 Pal.parse("abaaaba") |
80 |
86 |
81 println("Palindrome: " + Pal.parse_all("abaaaba")) |
87 println("Palindrome: " + Pal.parse_all("abaaaba")) |
82 |
88 |
83 // well-nested parenthesis parser |
89 // well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' ) |
84 lazy val P : Parser[String, String] = |
90 lazy val P : Parser[String, String] = |
85 "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } | "" |
91 "(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } | "" |
86 |
92 |
87 P.parse_all("(((()()))())") |
93 P.parse_all("(((()()))())") |
88 P.parse_all("(((()()))()))") |
94 P.parse_all("(((()()))()))") |
89 P.parse_all(")(") |
95 P.parse_all(")(") |
90 P.parse_all("()") |
96 P.parse_all("()") |
91 |
97 |
92 // arithmetic expressions |
98 // Arithmetic Expressions |
93 |
99 |
94 lazy val E: Parser[String, Int] = |
100 lazy val E: Parser[String, Int] = |
95 (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } | |
101 (T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } | |
96 (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } | T |
102 (T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } | T |
97 lazy val T: Parser[String, Int] = |
103 lazy val T: Parser[String, Int] = |
147 |
153 |
148 U.parse_all("1" * 100) |
154 U.parse_all("1" * 100) |
149 U.parse_all("1" * 100 + "0") |
155 U.parse_all("1" * 100 + "0") |
150 |
156 |
151 lazy val UCount : Parser[String, Int] = |
157 lazy val UCount : Parser[String, Int] = |
152 ("1" ~ UCount) ==> { case (x, y) => y + 1 } | |
158 ("1" ~ UCount) ==> { case (x, y) => y + 1 } | "" ==> { x => 0 } |
153 "" ==> { x => 0 } |
|
154 |
159 |
155 UCount.parse("11111") |
160 UCount.parse("11111") |
156 UCount.parse_all("11111") |
161 UCount.parse_all("11111") |
157 |
|
158 |
162 |
159 |
163 |
160 |
164 |
161 // Single Character parser |
165 // Single Character parser |
162 lazy val One : Parser[String, String] = "1" |
166 lazy val One : Parser[String, String] = "1" |