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 |
|
629
|
4 |
/* Note, in the lectures I did not show the implicit type
|
|
5 |
* constraint IsSeq, which means that the input type 'I' needs
|
|
6 |
* to be a sequence. */
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
|
667
|
8 |
type IsSeq[A] = A => Seq[_]
|
629
|
9 |
|
|
10 |
abstract class Parser[I : IsSeq, T] {
|
461
|
11 |
def parse(ts: I): Set[(T, I)]
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
|
461
|
13 |
def parse_all(ts: I) : Set[T] =
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
for ((head, tail) <- parse(ts);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
if (tail.isEmpty)) yield head
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
|
629
|
18 |
class SeqParser[I : IsSeq, T, S](p: => Parser[I, T],
|
|
19 |
q: => Parser[I, S]) extends Parser[I, (T, S)] {
|
461
|
20 |
def parse(sb: I) =
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
for ((head1, tail1) <- p.parse(sb);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
(head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
23 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
|
629
|
25 |
class AltParser[I : IsSeq, T](p: => Parser[I, T],
|
|
26 |
q: => Parser[I, T]) extends Parser[I, T] {
|
461
|
27 |
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
|
28 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
|
629
|
30 |
class FunParser[I : IsSeq, T, S](p: => Parser[I, T],
|
|
31 |
f: T => S) extends Parser[I, S] {
|
461
|
32 |
def parse(sb: I) =
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
|
628
|
36 |
// atomic parsers for characters, numbers and strings
|
461
|
37 |
case class CharParser(c: Char) extends Parser[String, Char] {
|
177
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
def parse(sb: String) =
|
462
|
39 |
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
|
40 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
|
588
|
42 |
import scala.util.matching.Regex
|
|
43 |
case class RegexParser(reg: Regex) extends Parser[String, String] {
|
|
44 |
def parse(sb: String) = reg.findPrefixMatchOf(sb) match {
|
|
45 |
case None => Set()
|
|
46 |
case Some(m) => Set((m.matched, m.after.toString))
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
|
588
|
50 |
val NumParser = RegexParser("[0-9]+".r)
|
593
|
51 |
def StringParser(s: String) = RegexParser(Regex.quote(s).r)
|
588
|
52 |
|
672
|
53 |
// NumParserInt2 transforms a "string integer" into an actual Int;
|
624
|
54 |
// needs new, because FunParser is not a case class
|
628
|
55 |
val NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)
|
624
|
56 |
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
|
360
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
// convenience
|
462
|
59 |
implicit def string2parser(s: String) = StringParser(s)
|
593
|
60 |
implicit def char2parser(c: Char) = CharParser(c)
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
|
624
|
62 |
implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new {
|
628
|
63 |
def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
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
|
65 |
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
|
66 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
implicit def StringOps(s: String) = new {
|
628
|
69 |
def || (q : => Parser[String, String]) = new AltParser[String, String](s, q)
|
|
70 |
def || (r: String) = new AltParser[String, String](s, r)
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
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
|
72 |
def ~[S] (q : => Parser[String, S]) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
73 |
new SeqParser[String, String, S](s, q)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
def ~ (r: String) =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
new SeqParser[String, String, String](s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
|
672
|
78 |
// NumParserInt can now be written as _ ===> _
|
|
79 |
// the first part is the parser, and the second the
|
|
80 |
// semantic action
|
624
|
81 |
val NumParserInt = NumParser ==> (s => s.toInt)
|
|
82 |
|
588
|
83 |
|
672
|
84 |
// palindromes
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
lazy val Pal : Parser[String, String] =
|
628
|
86 |
(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } ||
|
|
87 |
("b" ~ Pal ~ "b") ==> { case ((x, y), z) => x + y + z } || "a" || "b" || "")
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
|
586
|
89 |
Pal.parse_all("abaaaba")
|
667
|
90 |
Pal.parse_all("abacba")
|
593
|
91 |
Pal.parse("abaaaba")
|
586
|
92 |
|
531
|
93 |
println("Palindrome: " + Pal.parse_all("abaaaba"))
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
94 |
|
672
|
95 |
// parser for well-nested parentheses (transforms '(' -> '{' , ')' -> '}' )
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
96 |
lazy val P : Parser[String, String] =
|
628
|
97 |
"(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } || ""
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
98 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
99 |
P.parse_all("(((()()))())")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
100 |
P.parse_all("(((()()))()))")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
101 |
P.parse_all(")(")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
P.parse_all("()")
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
103 |
|
672
|
104 |
// just counts parentheses
|
667
|
105 |
lazy val PC : Parser[String, Int] =
|
|
106 |
("(" ~ PC ~ ")" ~ PC ==> { case (((_, x), _), y) => x + y + 2 } ||
|
|
107 |
"" ==> { (s) => 0 })
|
|
108 |
|
|
109 |
PC.parse_all("(((()()))())")
|
|
110 |
P.parse_all("(((()()))()))")
|
|
111 |
|
628
|
112 |
// Arithmetic Expressions (Terms and Factors)
|
672
|
113 |
// (because it is mutually recursive, you need :paste
|
|
114 |
// for munching this definition in the REPL)
|
586
|
115 |
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
lazy val E: Parser[String, Int] =
|
628
|
117 |
(T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } ||
|
|
118 |
(T ~ "-" ~ E) ==> { case ((x, y), z) => x - z } || T
|
470
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
lazy val T: Parser[String, Int] =
|
628
|
120 |
(F ~ "*" ~ T) ==> { case ((x, y), z) => x * z } || F
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
lazy val F: Parser[String, Int] =
|
628
|
122 |
("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParserInt
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
123 |
|
628
|
124 |
/* same parser but producing a string
|
599
|
125 |
lazy val E: Parser[String, String] =
|
628
|
126 |
(T ~ "+" ~ E) ==> { case ((x, y), z) => "(" + x + ")+(" + z + ")"} || T
|
599
|
127 |
lazy val T: Parser[String, String] =
|
628
|
128 |
(F ~ "*" ~ T) ==> { case ((x, y), z) => "(" + x + ")*("+ z + ")"} || F
|
599
|
129 |
lazy val F: Parser[String, String] =
|
628
|
130 |
("(" ~ E ~ ")") ==> { case ((x, y), z) => y } || NumParser
|
|
131 |
*/
|
586
|
132 |
|
599
|
133 |
println(E.parse_all("1+3+4"))
|
|
134 |
println(E.parse("1+3+4"))
|
593
|
135 |
println(E.parse_all("4*2+3"))
|
|
136 |
println(E.parse_all("4*(2+3)"))
|
594
|
137 |
println(E.parse_all("(4)*((2+3))"))
|
586
|
138 |
println(E.parse_all("4/2+3"))
|
367
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
println(E.parse("1 + 2 * 3"))
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
println(E.parse_all("(1+2)+3"))
|
531
|
141 |
println(E.parse_all("1+2+3"))
|
|
142 |
|
586
|
143 |
|
|
144 |
|
531
|
145 |
// no left-recursion allowed, otherwise will loop
|
|
146 |
lazy val EL: Parser[String, Int] =
|
628
|
147 |
(EL ~ "+" ~ EL ==> { case ((x, y), z) => x + z} ||
|
|
148 |
EL ~ "*" ~ EL ==> { case ((x, y), z) => x * z} ||
|
|
149 |
"(" ~ EL ~ ")" ==> { case ((x, y), z) => y} ||
|
593
|
150 |
NumParserInt)
|
531
|
151 |
|
593
|
152 |
//println(EL.parse_all("1+2+3"))
|
531
|
153 |
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
154 |
|
462
|
155 |
|
|
156 |
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
// non-ambiguous vs ambiguous grammars
|
628
|
158 |
|
|
159 |
// ambiguous
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
160 |
lazy val S : Parser[String, String] =
|
628
|
161 |
("1" ~ S ~ S) ==> { case ((x, y), z) => x + y + z } || ""
|
172
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
162 |
|
628
|
163 |
S.parse("1" * 10)
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
|
628
|
165 |
// non-ambiguous
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
lazy val U : Parser[String, String] =
|
628
|
167 |
("1" ~ U) ==> { case (x, y) => x + y } || ""
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
168 |
|
599
|
169 |
U.parse("1" * 25)
|
531
|
170 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
U.parse("11")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
U.parse("11111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
U.parse("11011")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
|
531
|
175 |
U.parse_all("1" * 100)
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
U.parse_all("1" * 100 + "0")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
lazy val UCount : Parser[String, Int] =
|
628
|
179 |
("1" ~ UCount) ==> { case (x, y) => y + 1 } || "" ==> { x => 0 }
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
181 |
UCount.parse("11111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
182 |
UCount.parse_all("11111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
184 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
// Single Character parser
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
187 |
lazy val One : Parser[String, String] = "1"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
lazy val Two : Parser[String, String] = "2"
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
190 |
One.parse("1")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
One.parse("111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
192 |
|
366
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
193 |
(One ~ One).parse("111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
194 |
(One ~ One ~ One).parse("111")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
195 |
(One ~ One ~ One ~ One).parse("1111")
|
362
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
196 |
|
628
|
197 |
(One || Two).parse("111")
|
|
198 |
|
|
199 |
|
467
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
200 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
201 |
|
672
|
202 |
// a problem with the arithmetic expression parser -> gets
|
|
203 |
// slow with deep nestedness
|
628
|
204 |
E.parse("1")
|
|
205 |
E.parse("(1)")
|
|
206 |
E.parse("((1))")
|
|
207 |
E.parse("(((1)))")
|
|
208 |
E.parse("((((1))))")
|
|
209 |
E.parse("((((((1))))))")
|
672
|
210 |
E.parse("(((((((1)))))))")
|