|
1 |
|
2 import scala.language.implicitConversions |
|
3 import scala.language.reflectiveCalls |
|
4 import scala.annotation.tailrec |
|
5 import scala.util.Try |
|
6 |
|
7 def escape(raw: String) : String = { |
|
8 import scala.reflect.runtime.universe._ |
|
9 Literal(Constant(raw)).toString |
|
10 } |
|
11 |
|
12 def esc2(r: (String, String)) = (escape(r._1), escape(r._2)) |
|
13 |
|
14 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match { |
|
15 case Nil => Nil |
|
16 case (x::xs) => { |
|
17 val res = f(x) |
|
18 if (acc.contains(res)) distinctBy(xs, f, acc) |
|
19 else x::distinctBy(xs, f, res::acc) |
|
20 } |
|
21 } |
|
22 |
|
23 abstract class Bit |
|
24 case object Z extends Bit |
|
25 case object S extends Bit |
|
26 case class C(c: Char) extends Bit |
|
27 |
|
28 type Bits = List[Bit] |
|
29 |
|
30 // usual regular expressions |
|
31 abstract class Rexp |
|
32 case object ZERO extends Rexp |
|
33 case object ONE extends Rexp |
|
34 case class PRED(f: Char => Boolean) extends Rexp |
|
35 case class ALTS(rs: List[Rexp]) extends Rexp |
|
36 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
37 case class STAR(r: Rexp) extends Rexp |
|
38 case class RECD(x: String, r: Rexp) extends Rexp |
|
39 |
|
40 |
|
41 // abbreviations |
|
42 def CHAR(c: Char) = PRED(_ == c) |
|
43 def ALT(r1: Rexp, r2: Rexp) = ALTS(List(r1, r2)) |
|
44 def PLUS(r: Rexp) = SEQ(r, STAR(r)) |
|
45 |
|
46 // annotated regular expressions |
|
47 abstract class ARexp |
|
48 case object AZERO extends ARexp |
|
49 case class AONE(bs: Bits) extends ARexp |
|
50 case class APRED(bs: Bits, f: Char => Boolean) extends ARexp |
|
51 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
|
52 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
|
53 case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
|
54 |
|
55 // abbreviations |
|
56 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2)) |
|
57 |
|
58 // values |
|
59 abstract class Val |
|
60 case object Empty extends Val |
|
61 case class Chr(c: Char) extends Val |
|
62 case class Sequ(v1: Val, v2: Val) extends Val |
|
63 case class Left(v: Val) extends Val |
|
64 case class Right(v: Val) extends Val |
|
65 case class Stars(vs: List[Val]) extends Val |
|
66 case class Rec(x: String, v: Val) extends Val |
|
67 |
|
68 |
|
69 |
|
70 // some convenience for typing in regular expressions |
|
71 def charlist2rexp(s : List[Char]): Rexp = s match { |
|
72 case Nil => ONE |
|
73 case c::Nil => CHAR(c) |
|
74 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
75 } |
|
76 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
77 |
|
78 implicit def RexpOps(r: Rexp) = new { |
|
79 def | (s: Rexp) = ALT(r, s) |
|
80 def % = STAR(r) |
|
81 def ~ (s: Rexp) = SEQ(r, s) |
|
82 } |
|
83 |
|
84 implicit def stringOps(s: String) = new { |
|
85 def | (r: Rexp) = ALT(s, r) |
|
86 def | (r: String) = ALT(s, r) |
|
87 def % = STAR(s) |
|
88 def ~ (r: Rexp) = SEQ(s, r) |
|
89 def ~ (r: String) = SEQ(s, r) |
|
90 def $ (r: Rexp) = RECD(s, r) |
|
91 } |
|
92 |
|
93 |
|
94 //-------------------------------------------------------------------------------------------------------- |
|
95 // START OF NON-BITCODE PART |
|
96 // |
|
97 |
|
98 // nullable function: tests whether the regular |
|
99 // expression can recognise the empty string |
|
100 def nullable (r: Rexp) : Boolean = r match { |
|
101 case ZERO => false |
|
102 case ONE => true |
|
103 case PRED(_) => false |
|
104 case ALTS(rs) => rs.exists(nullable) |
|
105 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
106 case STAR(_) => true |
|
107 case RECD(_, r) => nullable(r) |
|
108 } |
|
109 |
|
110 // derivative of a regular expression w.r.t. a character |
|
111 def der (c: Char, r: Rexp) : Rexp = r match { |
|
112 case ZERO => ZERO |
|
113 case ONE => ZERO |
|
114 case PRED(f) => if (f(c)) ONE else ZERO |
|
115 case ALTS(List(r1, r2)) => ALTS(List(der(c, r1), der(c, r2))) |
|
116 case SEQ(r1, r2) => |
|
117 if (nullable(r1)) ALTS(List(SEQ(der(c, r1), r2), der(c, r2))) |
|
118 else SEQ(der(c, r1), r2) |
|
119 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
120 case RECD(_, r1) => der(c, r1) |
|
121 } |
|
122 |
|
123 |
|
124 def flatten(v: Val) : String = v match { |
|
125 case Empty => "" |
|
126 case Chr(c) => c.toString |
|
127 case Left(v) => flatten(v) |
|
128 case Right(v) => flatten(v) |
|
129 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
|
130 case Stars(vs) => vs.map(flatten).mkString |
|
131 case Rec(_, v) => flatten(v) |
|
132 } |
|
133 |
|
134 // extracts an environment from a value |
|
135 def env(v: Val) : List[(String, String)] = v match { |
|
136 case Empty => Nil |
|
137 case Chr(c) => Nil |
|
138 case Left(v) => env(v) |
|
139 case Right(v) => env(v) |
|
140 case Sequ(v1, v2) => env(v1) ::: env(v2) |
|
141 case Stars(vs) => vs.flatMap(env) |
|
142 case Rec(x, v) => (x, flatten(v))::env(v) |
|
143 } |
|
144 |
|
145 |
|
146 // injection part |
|
147 def mkeps(r: Rexp) : Val = r match { |
|
148 case ONE => Empty |
|
149 case ALTS(List(r1, r2)) => |
|
150 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
|
151 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
|
152 case STAR(r) => Stars(Nil) |
|
153 case RECD(x, r) => Rec(x, mkeps(r)) |
|
154 } |
|
155 |
|
156 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
|
157 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
158 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
|
159 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
|
160 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
|
161 case (ALTS(List(r1, r2)), Left(v1)) => Left(inj(r1, c, v1)) |
|
162 case (ALTS(List(r1, r2)), Right(v2)) => Right(inj(r2, c, v2)) |
|
163 case (PRED(_), Empty) => Chr(c) |
|
164 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
|
165 } |
|
166 |
|
167 // lexing without simplification |
|
168 def lex(r: Rexp, s: List[Char]) : Val = s match { |
|
169 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
|
170 case c::cs => inj(r, c, lex(der(c, r), cs)) |
|
171 } |
|
172 |
|
173 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
|
174 |
|
175 //println(lexing(("ab" | "ab") ~ ("b" | ONE), "ab")) |
|
176 |
|
177 // some "rectification" functions for simplification |
|
178 def F_ID(v: Val): Val = v |
|
179 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
|
180 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
|
181 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
|
182 case Right(v) => Right(f2(v)) |
|
183 case Left(v) => Left(f1(v)) |
|
184 } |
|
185 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
|
186 case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
|
187 } |
|
188 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
|
189 (v:Val) => Sequ(f1(Empty), f2(v)) |
|
190 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
|
191 (v:Val) => Sequ(f1(v), f2(Empty)) |
|
192 def F_RECD(f: Val => Val) = (v:Val) => v match { |
|
193 case Rec(x, v) => Rec(x, f(v)) |
|
194 } |
|
195 def F_ERROR(v: Val): Val = throw new Exception("error") |
|
196 |
|
197 // simplification of regular expressions returning also an |
|
198 // rectification function; no simplification under STAR |
|
199 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
|
200 case ALTS(List(r1, r2)) => { |
|
201 val (r1s, f1s) = simp(r1) |
|
202 val (r2s, f2s) = simp(r2) |
|
203 (r1s, r2s) match { |
|
204 case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
|
205 case (_, ZERO) => (r1s, F_LEFT(f1s)) |
|
206 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
|
207 else (ALTS(List(r1s, r2s)), F_ALT(f1s, f2s)) |
|
208 } |
|
209 } |
|
210 case SEQ(r1, r2) => { |
|
211 val (r1s, f1s) = simp(r1) |
|
212 val (r2s, f2s) = simp(r2) |
|
213 (r1s, r2s) match { |
|
214 case (ZERO, _) => (ZERO, F_ERROR) |
|
215 case (_, ZERO) => (ZERO, F_ERROR) |
|
216 case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
|
217 case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
|
218 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
|
219 } |
|
220 } |
|
221 case RECD(x, r1) => { |
|
222 val (r1s, f1s) = simp(r1) |
|
223 (RECD(x, r1s), F_RECD(f1s)) |
|
224 } |
|
225 case r => (r, F_ID) |
|
226 } |
|
227 |
|
228 def lex_simp(r: Rexp, s: List[Char]) : Val = s match { |
|
229 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
|
230 case c::cs => { |
|
231 val (r_simp, f_simp) = simp(der(c, r)) |
|
232 inj(r, c, f_simp(lex_simp(r_simp, cs))) |
|
233 } |
|
234 } |
|
235 |
|
236 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
|
237 |
|
238 println(lexing_simp(("a" | "ab") ~ ("b" | ""), "ab")) |
|
239 |
|
240 |
|
241 def tokenise_simp(r: Rexp, s: String) = env(lexing_simp(r, s)).map(esc2) |
|
242 |
|
243 //-------------------------------------------------------------------------------------------------------- |
|
244 // BITCODED PART |
|
245 |
|
246 |
|
247 def fuse(bs: Bits, r: ARexp) : ARexp = r match { |
|
248 case AZERO => AZERO |
|
249 case AONE(cs) => AONE(bs ++ cs) |
|
250 case APRED(cs, f) => APRED(bs ++ cs, f) |
|
251 case AALTS(cs, rs) => AALTS(bs ++ cs, rs) |
|
252 case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2) |
|
253 case ASTAR(cs, r) => ASTAR(bs ++ cs, r) |
|
254 } |
|
255 |
|
256 // translation into ARexps |
|
257 def internalise(r: Rexp) : ARexp = r match { |
|
258 case ZERO => AZERO |
|
259 case ONE => AONE(Nil) |
|
260 case PRED(f) => APRED(Nil, f) |
|
261 case ALTS(List(r1, r2)) => |
|
262 AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2)))) |
|
263 case ALTS(r1::rs) => { |
|
264 val AALTS(Nil, rs2) = internalise(ALTS(rs)) |
|
265 AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _))) |
|
266 } |
|
267 case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2)) |
|
268 case STAR(r) => ASTAR(Nil, internalise(r)) |
|
269 case RECD(x, r) => internalise(r) |
|
270 } |
|
271 |
|
272 internalise(("a" | "ab") ~ ("b" | "")) |
|
273 |
|
274 // decoding of values from bit sequences |
|
275 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
|
276 case (ONE, bs) => (Empty, bs) |
|
277 case (PRED(f), C(c)::bs) => (Chr(c), bs) |
|
278 case (ALTS(r::Nil), bs) => decode_aux(r, bs) |
|
279 case (ALTS(rs), bs) => bs match { |
|
280 case Z::bs1 => { |
|
281 val (v, bs2) = decode_aux(rs.head, bs1) |
|
282 (Left(v), bs2) |
|
283 } |
|
284 case S::bs1 => { |
|
285 val (v, bs2) = decode_aux(ALTS(rs.tail), bs1) |
|
286 (Right(v), bs2) |
|
287 } |
|
288 } |
|
289 case (SEQ(r1, r2), bs) => { |
|
290 val (v1, bs1) = decode_aux(r1, bs) |
|
291 val (v2, bs2) = decode_aux(r2, bs1) |
|
292 (Sequ(v1, v2), bs2) |
|
293 } |
|
294 case (STAR(r1), S::bs) => { |
|
295 val (v, bs1) = decode_aux(r1, bs) |
|
296 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
|
297 (Stars(v::vs), bs2) |
|
298 } |
|
299 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
|
300 case (RECD(x, r1), bs) => { |
|
301 val (v, bs1) = decode_aux(r1, bs) |
|
302 (Rec(x, v), bs1) |
|
303 } |
|
304 } |
|
305 |
|
306 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match { |
|
307 case (v, Nil) => v |
|
308 case _ => throw new Exception("Not decodable") |
|
309 } |
|
310 |
|
311 |
|
312 //erase function: extracts a Rexp from Arexp |
|
313 def erase(r: ARexp) : Rexp = r match{ |
|
314 case AZERO => ZERO |
|
315 case AONE(_) => ONE |
|
316 case APRED(bs, f) => PRED(f) |
|
317 case AALTS(bs, rs) => ALTS(rs.map(erase(_))) |
|
318 case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2)) |
|
319 case ASTAR(cs, r)=> STAR(erase(r)) |
|
320 } |
|
321 |
|
322 |
|
323 // bnullable function: tests whether the aregular |
|
324 // expression can recognise the empty string |
|
325 def bnullable (r: ARexp) : Boolean = r match { |
|
326 case AZERO => false |
|
327 case AONE(_) => true |
|
328 case APRED(_,_) => false |
|
329 case AALTS(_, rs) => rs.exists(bnullable) |
|
330 case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2) |
|
331 case ASTAR(_, _) => true |
|
332 } |
|
333 |
|
334 def bmkeps(r: ARexp) : Bits = r match { |
|
335 case AONE(bs) => bs |
|
336 case AALTS(bs, rs) => { |
|
337 val n = rs.indexWhere(bnullable) |
|
338 bs ++ bmkeps(rs(n)) |
|
339 } |
|
340 case ASEQ(bs, r1, r2) => bs ++ bmkeps(r1) ++ bmkeps(r2) |
|
341 case ASTAR(bs, r) => bs ++ List(Z) |
|
342 } |
|
343 |
|
344 // derivative of a regular expression w.r.t. a character |
|
345 def bder(c: Char, r: ARexp) : ARexp = r match { |
|
346 case AZERO => AZERO |
|
347 case AONE(_) => AZERO |
|
348 case APRED(bs, f) => if (f(c)) AONE(bs:::List(C(c))) else AZERO |
|
349 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
|
350 case ASEQ(bs, r1, r2) => |
|
351 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(bmkeps(r1), bder(c, r2))) |
|
352 else ASEQ(bs, bder(c, r1), r2) |
|
353 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
|
354 } |
|
355 |
|
356 |
|
357 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
|
358 case Nil => r |
|
359 case c::s => ders(s, der(c, r)) |
|
360 } |
|
361 |
|
362 |
|
363 // derivative w.r.t. a string (iterates bder) |
|
364 @tailrec |
|
365 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
|
366 case Nil => r |
|
367 case c::s => bders(s, bder(c, r)) |
|
368 } |
|
369 |
|
370 |
|
371 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
|
372 case Nil => Nil |
|
373 case AZERO :: rs1 => flats(rs1) |
|
374 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
375 case r1 :: rs2 => r1 :: flats(rs2) |
|
376 } |
|
377 |
|
378 def bsimp(r: ARexp): ARexp = r match { |
|
379 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { |
|
380 case (AZERO, _) => AZERO |
|
381 case (_, AZERO) => AZERO |
|
382 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
383 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
384 } |
|
385 case AALTS(bs1, rs) => distinctBy(flats(rs.map(bsimp)), erase) match { |
|
386 case Nil => AZERO |
|
387 case s :: Nil => fuse(bs1, s) |
|
388 case rs => AALTS(bs1, rs) |
|
389 } |
|
390 case r => r |
|
391 } |
|
392 |
|
393 def bders_simp (s: List[Char], r: ARexp) : ARexp = s match { |
|
394 case Nil => r |
|
395 case c::s => bders_simp(s, bsimp(bder(c, r))) |
|
396 } |
|
397 |
|
398 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
|
399 case Nil => if (bnullable(r)) bmkeps(r) |
|
400 else throw new Exception("Not matched") |
|
401 case c::cs => blex_simp(bsimp(bder(c, r)), cs) |
|
402 } |
|
403 |
|
404 |
|
405 def blexing_simp(r: Rexp, s: String) : Val = |
|
406 decode(r, blex_simp(internalise(r), s.toList)) |
|
407 |
|
408 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2) |
|
409 |
|
410 //---------------------------------------------------------------------------- |
|
411 // This bsimp is the original slow one |
|
412 /* |
|
413 def bsimp(r: ARexp): ARexp = r match { |
|
414 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { |
|
415 case (AZERO, _) => AZERO |
|
416 case (_, AZERO) => AZERO |
|
417 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
418 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
419 } |
|
420 case AALTS(bs1, rs) => { |
|
421 distinctBy(flats(rs.map(bsimp)), erase) match { |
|
422 case Nil => AZERO |
|
423 case s :: Nil => fuse(bs1, s) |
|
424 case rs => AALTS(bs1, rs) |
|
425 } |
|
426 } |
|
427 case r => r |
|
428 } |
|
429 */ |
|
430 |
|
431 |
|
432 //---------------------------------------------------------------------------- |
|
433 // Testing |
|
434 //============ |
|
435 |
|
436 def time[T](code: => T) = { |
|
437 val start = System.nanoTime() |
|
438 val result = code |
|
439 val end = System.nanoTime() |
|
440 ((end - start)/1.0e9).toString |
|
441 //result |
|
442 } |
|
443 |
|
444 //size: of a Aregx for testing purposes |
|
445 def size(r: Rexp) : Int = r match { |
|
446 case ZERO => 1 |
|
447 case ONE => 1 |
|
448 case PRED(_) => 1 |
|
449 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
450 case ALTS(rs) => 1 + rs.map(size).sum |
|
451 case STAR(r) => 1 + size(r) |
|
452 } |
|
453 |
|
454 def asize(a: ARexp) = size(erase(a)) |
|
455 |
|
456 |
|
457 // Lexing Rules for a Small While Language |
|
458 |
|
459 //symbols |
|
460 val SYM = PRED("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".contains(_)) |
|
461 //digits |
|
462 val DIGIT = PRED("0123456789".contains(_)) |
|
463 //identifiers |
|
464 val ID = SYM ~ (SYM | DIGIT).% |
|
465 //numbers |
|
466 val NUM = STAR(DIGIT) |
|
467 //keywords |
|
468 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
|
469 //semicolons |
|
470 val SEMI: Rexp = ";" |
|
471 //operators |
|
472 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" |
|
473 //whitespaces |
|
474 val WHITESPACE = PLUS(" " | "\n" | "\t") |
|
475 //parentheses |
|
476 val RPAREN: Rexp = ")" |
|
477 val LPAREN: Rexp = "(" |
|
478 val BEGIN: Rexp = "{" |
|
479 val END: Rexp = "}" |
|
480 //strings...but probably needs not |
|
481 val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
|
482 |
|
483 |
|
484 |
|
485 val WHILE_REGS = (("k" $ KEYWORD) | |
|
486 ("i" $ ID) | |
|
487 ("o" $ OP) | |
|
488 ("n" $ NUM) | |
|
489 ("s" $ SEMI) | |
|
490 ("str" $ STRING) | |
|
491 ("p" $ (LPAREN | RPAREN)) | |
|
492 ("b" $ (BEGIN | END)) | |
|
493 ("w" $ WHITESPACE)).% |
|
494 |
|
495 |
|
496 // Some Small Tests |
|
497 //================== |
|
498 |
|
499 /* |
|
500 println("simple tests:") |
|
501 println(blexing_simp((SYM.%), "abcd")) |
|
502 println(blexing_simp(((SYM.%) | ((SYM.% | NUM).%)), "12345")) |
|
503 println(blexing_simp((WHILE_REGS), "abcd")) |
|
504 println(blexing_simp((WHILE_REGS), "12345")) |
|
505 println(blexing_simp((WHILE_REGS), """write "Fib";""")) |
|
506 */ |
|
507 |
|
508 |
|
509 // Bigger Tests |
|
510 //============== |
|
511 |
|
512 |
|
513 val fib_prog = """ |
|
514 write "Fib"; |
|
515 read n; |
|
516 minus1 := 0; |
|
517 minus2 := 1; |
|
518 while n > 0 do { |
|
519 temp := minus2; |
|
520 minus2 := minus1 + minus2; |
|
521 minus1 := temp; |
|
522 n := n - 1 |
|
523 }; |
|
524 write "Result"; |
|
525 write minus2 |
|
526 """ |
|
527 |
|
528 |
|
529 println("fib prog tests :") |
|
530 println(tokenise_simp(WHILE_REGS, fib_prog)) |
|
531 println(btokenise_simp(WHILE_REGS, fib_prog)) |
|
532 println(time(tokenise_simp(WHILE_REGS, fib_prog * 7))) |
|
533 println(time(btokenise_simp(WHILE_REGS, fib_prog * 7))) |
|
534 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog))) |
|
535 |
|
536 |
|
537 |
|
538 |
|
539 |
|
540 //testing the two lexings produce the same value |
|
541 //enumerates strings of length n over alphabet cs |
|
542 def strs(n: Int, cs: String) : Set[String] = { |
|
543 if (n == 0) Set("") |
|
544 else { |
|
545 val ss = strs(n - 1, cs) |
|
546 ss ++ |
|
547 (for (s <- ss; c <- cs.toList) yield c + s) |
|
548 } |
|
549 } |
|
550 def enum(n: Int, s: String) : Stream[Rexp] = n match { |
|
551 case 0 => ZERO #:: ONE #:: s.toStream.map(CHAR) |
|
552 case n => { |
|
553 val rs = enum(n - 1, s) |
|
554 rs #::: |
|
555 (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: |
|
556 (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: |
|
557 (for (r1 <- rs) yield STAR(r1)) |
|
558 } |
|
559 } |
|
560 |
|
561 //tests blexing and lexing |
|
562 def tests(ss: Set[String])(r: Rexp) = { |
|
563 //println(s"Testing ${r}") |
|
564 for (s <- ss.par) yield { |
|
565 val res1 = Try(Some(lexing_simp(r, s))).getOrElse(None) |
|
566 val res2 = Try(Some(blexing_simp(r, s))).getOrElse(None) |
|
567 if (res1 != res2) |
|
568 { println(s"Disagree on ${r} and ${s}") |
|
569 println(s" ${res1} != ${res2}") |
|
570 Some((r, s)) } else None |
|
571 } |
|
572 } |
|
573 |
|
574 |
|
575 println("Partial searching: ") |
|
576 enum(2, "abc").map(tests(strs(3, "abc"))).toSet |