3 |
3 |
4 abstract class Parser[I <% Seq[_], T] { |
4 abstract class Parser[I <% Seq[_], T] { |
5 def parse(ts: I): Set[(T, I)] |
5 def parse(ts: I): Set[(T, I)] |
6 |
6 |
7 def parse_all(ts: I) : Set[T] = |
7 def parse_all(ts: I) : Set[T] = |
8 for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head |
8 for ((head, tail) <- parse(ts); |
|
9 if (tail.isEmpty)) yield head |
9 } |
10 } |
10 |
11 |
11 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { |
12 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], |
|
13 q: => Parser[I, S]) extends Parser[I, (T, S)] { |
12 def parse(sb: I) = |
14 def parse(sb: I) = |
13 for ((head1, tail1) <- p.parse(sb); |
15 for ((head1, tail1) <- p.parse(sb); |
14 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
16 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
15 } |
17 } |
16 |
18 |
17 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { |
19 class AltParser[I <% Seq[_], T](p: => Parser[I, T], |
|
20 q: => Parser[I, T]) extends Parser[I, T] { |
18 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
21 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
19 } |
22 } |
20 |
23 |
21 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { |
24 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], |
|
25 f: T => S) extends Parser[I, S] { |
22 def parse(sb: I) = |
26 def parse(sb: I) = |
23 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
27 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
24 } |
28 } |
25 |
29 |
26 // atomic parsers |
30 // atomic parsers |
42 case None => Set() |
46 case None => Set() |
43 case Some(s) => Set(sb.splitAt(s.length)) |
47 case Some(s) => Set(sb.splitAt(s.length)) |
44 } |
48 } |
45 } |
49 } |
46 |
50 |
47 |
51 // convenience |
48 implicit def string2parser(s : String) = StringParser(s) |
52 implicit def string2parser(s : String) = StringParser(s) |
49 |
53 |
50 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
54 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
51 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
55 def || (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
52 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
56 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
61 new SeqParser[String, String, S](s, q) |
65 new SeqParser[String, String, S](s, q) |
62 def ~ (r: String) = |
66 def ~ (r: String) = |
63 new SeqParser[String, String, String](s, r) |
67 new SeqParser[String, String, String](s, r) |
64 } |
68 } |
65 |
69 |
66 |
70 // palindromes |
67 |
|
68 |
|
69 lazy val Pal : Parser[String, String] = |
71 lazy val Pal : Parser[String, String] = |
70 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } || |
72 (("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } || |
71 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "") |
73 ("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "") |
72 |
74 |
73 println("Palindrom" + Pal.parse_all("ababbaba")) |
75 println("Palindrom: " + Pal.parse_all("ababbaba")) |
74 |
76 |
75 |
77 // well-nested parenthesis |
76 lazy val P : Parser[String, String] = |
78 lazy val P : Parser[String, String] = |
77 "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || "" |
79 "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || "" |
78 |
80 |
79 P.parse_all("(((()()))())") |
81 P.parse_all("(((()()))())") |
80 P.parse_all("(((()()))()))") |
82 P.parse_all("(((()()))()))") |
81 P.parse_all(")(") |
83 P.parse_all(")(") |
82 |
84 |
|
85 // arithmetic expressions |
83 lazy val E: Parser[String, String] = |
86 lazy val E: Parser[String, String] = |
84 (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F |
87 (F ~ "*" ~ F) ==> { case ((x, y), z) => x + y + z } || F |
85 lazy val F: Parser[String, String] = |
88 lazy val F: Parser[String, String] = |
86 ((T ~ "+" ~ T) ==> { case ((x, y), z) => x + y + z } || |
89 ((T ~ "+" ~ T) ==> { case ((x, y), z) => x + y + z } || |
87 (T ~ "-" ~ T) ==> { case ((x, y), z) => x + y + z } || T) |
90 (T ~ "-" ~ T) ==> { case ((x, y), z) => x + y + z } || T) |