230 } |
230 } |
231 } |
231 } |
232 |
232 |
233 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
233 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
234 |
234 |
|
235 |
|
236 // brute force infrastructure |
|
237 |
|
238 def enum(n: Int, s: String) : Set[Rexp] = n match { |
|
239 case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR) |
|
240 case n => { |
|
241 val rs = enum(n - 1, s) |
|
242 rs ++ |
|
243 (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++ |
|
244 (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) |
|
245 } |
|
246 } |
|
247 |
|
248 def ord(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match { |
|
249 case (Void, EMPTY, Void) => true |
|
250 case (Chr(c1), CHAR(c2), Chr(c3)) if (c1==c2 && c1==c3) => true |
|
251 case (Left(v1), ALT(r1,r2), Left(v2)) => ord(v1,r1,v2) |
|
252 case (Right(v1), ALT(r1,r2), Right(v2)) => ord(v1,r2,v2) |
|
253 case (Left(v1), ALT(r1,r2), Right(v2)) => flatten(v2).length <= flatten(v1).length |
|
254 case (Right(v1), ALT(r1,r2), Left(v2)) => flatten(v2).length < flatten(v1).length |
|
255 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1==v3) => ord(v2, r2, v4) |
|
256 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1!=v3) => ord(v1, r1, v3) |
|
257 case _ => false |
|
258 } |
|
259 |
|
260 def tst(r: Rexp, c: Char) : Set[(Rexp, Val, Val, Val, Val)] = { |
|
261 val r_der = der(c, r) |
|
262 val vs = values(r_der) |
|
263 for (v1 <- vs; v2 <- vs; |
|
264 if (v1 != v2 && ord(v1, r_der, v2) && ord(inj(r, c, v2), r, inj(r, c, v1)))) |
|
265 yield (r, v1, v2, inj(r, c, v1), inj(r, c, v2)) |
|
266 } |
|
267 |
|
268 def comp(r1: (Rexp, Val, Val, Val, Val), r2: (Rexp, Val, Val, Val, Val)) = size(r1._1) < size(r2._1) |
|
269 |
|
270 |
|
271 val smallest = enum(3, "a").flatMap(tst(_, 'a')).toList.sortWith { comp }.head |
|
272 |
|
273 smallest match { |
|
274 case (r, v1, v2, v3, v4) => List(pretty(r), |
|
275 pretty(der('a', r)), |
|
276 vpretty(v1), |
|
277 vpretty(v2), |
|
278 vpretty(v3), |
|
279 vpretty(v4)).mkString("\n") } |
235 |
280 |
236 // Lexing Rules for a Small While Language |
281 // Lexing Rules for a Small While Language |
237 |
282 |
238 def PLUS(r: Rexp) = r ~ r.% |
283 def PLUS(r: Rexp) = r ~ r.% |
239 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |
284 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |
369 for (i <- 1 to 80) { |
414 for (i <- 1 to 80) { |
370 print(i.toString + ": ") |
415 print(i.toString + ": ") |
371 time(lexing_simp(WHILE_REGS, prog2 * i)) |
416 time(lexing_simp(WHILE_REGS, prog2 * i)) |
372 } |
417 } |
373 |
418 |
374 val a0 = (EMPTY | "a") ~ ("b" | "abc") |
419 |
|
420 val a0 = (EMPTY | "a") ~ (EMPTY | "ab") |
|
421 val a1 = der('a', a0) |
|
422 pretty(a1) |
|
423 val m = mkeps(a1) |
|
424 vpretty(m) |
|
425 val v = inj(a0, 'a', m) |
|
426 vpretty(v) |
|
427 |
|
428 val a0 = (EMPTY | "a") ~ (EMPTY | "ab") |
375 val a1 = der('a', a0) |
429 val a1 = der('a', a0) |
376 pretty(a1) |
430 pretty(a1) |
377 values(a1).toList |
431 values(a1).toList |
378 val List(u2,_,u1) = values(a1).toList |
432 val List(u2,_,u1) = values(a1).toList |
379 vpretty(u1) |
433 vpretty(u1) |
380 vpretty(u2) |
434 vpretty(u2) |
381 vpretty(inj(a0,'a',u1)) |
435 vpretty(inj(a0,'a',u1)) |
382 vpretty(inj(a0,'a',u2)) |
436 vpretty(inj(a0,'a',u2)) |
383 |
437 |
|
438 lexing(a0, "ab") |
|
439 val aa = der('a', a0) |
|
440 pretty(aa) |
|
441 val ab = der('b', aa) |
|
442 pretty(ab) |
|
443 nullable(ab) |
|
444 val m = mkeps(ab) |
|
445 vpretty(m) |
|
446 val vb = inj(aa, 'b', m) |
|
447 vpretty(vb) |
|
448 val va = inj(a0, 'a', vb) |
|
449 vpretty(va) |