172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
import scala.language.implicitConversions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
import scala.language.reflectiveCalls
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
/* Note, in the lectures I did not show the type consraint
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
* I <% Seq[_] , which means that the input type I can be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
6 |
* treated, or seen, as a sequence. */
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
|
461
|
8 |
abstract class Parser[I <% Seq[_], T] {
|
|
9 |
def parse(ts: I): Set[(T, I)]
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
|
461
|
11 |
def parse_all(ts: I) : Set[T] =
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
for ((head, tail) <- parse(ts);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
if (tail.isEmpty)) yield head
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
|
461
|
16 |
class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T],
|
|
17 |
q: => Parser[I, S]) extends Parser[I, (T, S)] {
|
|
18 |
def parse(sb: I) =
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
for ((head1, tail1) <- p.parse(sb);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
(head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
|
461
|
23 |
class AltParser[I <% Seq[_], T](p: => Parser[I, T],
|
|
24 |
q: => Parser[I, T]) extends Parser[I, T] {
|
|
25 |
def parse(sb: I) = p.parse(sb) ++ q.parse(sb)
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
|
461
|
28 |
class FunParser[I <% Seq[_], T, S](p: => Parser[I, T],
|
|
29 |
f: T => S) extends Parser[I, S] {
|
|
30 |
def parse(sb: I) =
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
|
183
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
// atomic parsers
|
461
|
35 |
case class CharParser(c: Char) extends Parser[String, Char] {
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
def parse(sb: String) =
|
462
|
37 |
if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
case class StringParser(s: String) extends Parser[String, String] {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
def parse(sb: String) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
val (prefix, suffix) = sb.splitAt(s.length)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
if (prefix == s) Set((prefix, suffix)) else Set()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
case object NumParser extends Parser[String, Int] {
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
val reg = "[0-9]+".r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
def parse(sb: String) = reg.findPrefixOf(sb) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
case None => Set()
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
case Some(s) => Set(sb.splitAt(s.length) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
case (x, y) => (x.toInt, y)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
})
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
// convenience
|
462
|
58 |
implicit def string2parser(s: String) = StringParser(s)
|
|
59 |
implicit def char2parser(c: Char) = CharParser(c)
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
implicit def StringOps(s: String) = new {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
def || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
69 |
def || (r: String) = new AltParser[String, String](s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
def ~[S] (q : => Parser[String, S]) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
72 |
new SeqParser[String, String, S](s, q)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
73 |
def ~ (r: String) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
new SeqParser[String, String, String](s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
// a parse palindromes
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
lazy val Pal : Parser[String, String] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
|
462
|
82 |
println("Palindrome: " + Pal.parse_all("ababbaba"))
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
// well-nested parenthesis parser
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
lazy val P : Parser[String, String] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
"(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
P.parse_all("(((()()))())")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
P.parse_all("(((()()))()))")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
P.parse_all(")(")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
P.parse_all("()")
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
92 |
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
// arithmetic expressions
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
lazy val E: Parser[String, Int] =
|
470
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
(T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
(T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } || T
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
lazy val T: Parser[String, Int] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
((F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } || F)
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
lazy val F: Parser[String, Int] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
101 |
|
470
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
println(E.parse("4*2+3"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
println(E.parse_all("4*2+3"))
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
println(E.parse("1 + 2 * 3"))
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
println(E.parse_all("(1+2)+3"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
println(E.parse_all("1+2+3")) // this is not parsed, because of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
// how the grammar is set up
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
108 |
|
462
|
109 |
// a repetition parser
|
|
110 |
|
|
111 |
def RepParser[I <% Seq[_], T](p: => Parser[I, T]): Parser[I, List[T]] = {
|
|
112 |
p ==> { case x => x :: Nil } ||
|
|
113 |
p ~ RepParser(p) ==> { case (x, y) => x :: y }
|
|
114 |
}
|
|
115 |
|
|
116 |
|
|
117 |
// a repetition parser
|
|
118 |
lazy val R : Parser[String, List[Char]] = RepParser('a')
|
|
119 |
println(R.parse_all("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))
|
|
120 |
|
|
121 |
|
|
122 |
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
// non-ambiguous vs ambiguous grammars
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
124 |
lazy val S : Parser[String, String] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
125 |
("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
126 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
127 |
S.parse_all("1" * 15)
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
lazy val U : Parser[String, String] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
("1" ~ U) ==> { case (x, y) => x + y } || ""
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
U.parse("11")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
U.parse("11111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
U.parse("11011")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
U.parse_all("1" * 100 + "0")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
lazy val UCount : Parser[String, Int] =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
("1" ~ UCount) ==> { case (x, y) => y + 1 } ||
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
"" ==> { (x) => 0 }
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
141 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
UCount.parse("11111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
143 |
UCount.parse_all("11111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
144 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
148 |
// Single Character parser
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
149 |
lazy val One : Parser[String, String] = "1"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
lazy val Two : Parser[String, String] = "2"
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
One.parse("1")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
One.parse("111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
155 |
(One ~ One).parse("111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
(One ~ One ~ One).parse("111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
(One ~ One ~ One ~ One).parse("1111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
(One || Two).parse("111")
|
467
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
161 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
162 |
for (x <- List(1, 2, 3, 4)) println(x)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
for (x <- List(1, 2, 3, 4); if (2 < x)) yield (x.toString + x.toString)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
for (x <- List("2", "1", "3", "4", "1")) yield (x + x + x)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
(1, "one", '1')._3
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
167 |
for ((x, y) <- List((1, "one"), (2, "two"), (3, "three"), (4,"many")); if (y == "many"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
yield (x.toString + y)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
170 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
def square(n: Int) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
n * n
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
square(4 + 3 + 5)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
def bar(): Int = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
bar()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
3
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
def foo(n: => Int) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
print("finished")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
foo(bar())
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
square(12) + square(10)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
def time_needed[T](i: Int, code: => T) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
val start = System.nanoTime()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
for (j <- 1 to i) code
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
val end = System.nanoTime()
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
(end - start)/(i * 1.0e9)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
197 |
}
|