|
1 import scala.language.implicitConversions |
|
2 import scala.language.reflectiveCalls |
|
3 |
|
4 abstract class Parser[I <% Seq[_], T] { |
|
5 def parse(ts: I): Set[(T, I)] |
|
6 |
|
7 def parse_all(ts: I) : Set[T] = |
|
8 for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head |
|
9 } |
|
10 |
|
11 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { |
|
12 def parse(sb: I) = |
|
13 for ((head1, tail1) <- p.parse(sb); |
|
14 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
|
15 } |
|
16 |
|
17 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { |
|
18 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
|
19 } |
|
20 |
|
21 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { |
|
22 def parse(sb: I) = |
|
23 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
|
24 } |
|
25 |
|
26 // atomic parsers |
|
27 case class StringParser(s: String) extends Parser[String, String] { |
|
28 def parse(sb: String) = { |
|
29 val (prefix, suffix) = sb.splitAt(s.length) |
|
30 if (prefix == s) Set((prefix, suffix)) else Set() |
|
31 } |
|
32 } |
|
33 |
|
34 case object NumParser extends Parser[String, String] { |
|
35 val reg = "[0-9]+".r |
|
36 def parse(sb: String) = reg.findPrefixOf(sb) match { |
|
37 case None => Set() |
|
38 case Some(s) => Set(sb.splitAt(s.length)) |
|
39 } |
|
40 } |
|
41 |
|
42 |
|
43 implicit def string2parser(s : String) = StringParser(s) |
|
44 |
|
45 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
|
46 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
|
47 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
|
48 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
|
49 } |
|
50 |
|
51 implicit def StringOps(s: String) = new { |
|
52 def || (q : => Parser[String, String]) = new AltParser[String, String](s, q) |
|
53 def || (r: String) = new AltParser[String, String](s, r) |
|
54 def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f) |
|
55 def ~[S] (q : => Parser[String, S]) = |
|
56 new SeqParser[String, String, S](s, q) |
|
57 def ~ (r: String) = |
|
58 new SeqParser[String, String, String](s, r) |
|
59 } |
|
60 |
|
61 |
|
62 |
|
63 |
|
64 lazy val Pal : Parser[String, String] = |
|
65 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } || |
|
66 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "") |
|
67 |
|
68 Pal.parse_all("ababbaba") |
|
69 |
|
70 |
|
71 lazy val P : Parser[String, String] = |
|
72 "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || "" |
|
73 |
|
74 P.parse_all("(((()()))())") |
|
75 P.parse_all("(((()()))()))") |
|
76 P.parse_all(")(") |
|
77 |
|
78 lazy val E: Parser[String, String] = |
|
79 (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F |
|
80 lazy val F: Parser[String, String] = |
|
81 ((T ~ "+" ~ T) ==> { case ((x, y), z) => x + y + z } || |
|
82 (T ~ "-" ~ T) ==> { case ((x, y), z) => x + y + z } || T) |
|
83 lazy val T: Parser[String, String] = |
|
84 ("(" ~ E ~ ")") ==> { case ((x, y), z) => x + y + z } || NumParser |
|
85 |
|
86 |
|
87 println(E.parse_all("1+2+3")) |
|
88 |
|
89 |
|
90 |
|
91 // non-ambiguous vs ambiguous |
|
92 lazy val U : Parser[String, String] = |
|
93 ("1" ~ U) ==> { case (x, y) => x + y } || "" |
|
94 |
|
95 U.parse_all("1" * 100 + "0") |
|
96 |
|
97 lazy val S : Parser[String, String] = |
|
98 ("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || "" |
|
99 |
|
100 S.parse_all("1" * 15) |