37 implicit def stringOps(s: String) = new { |
37 implicit def stringOps(s: String) = new { |
38 def | (r: Rexp) = ALT(s, r) |
38 def | (r: Rexp) = ALT(s, r) |
39 def | (r: String) = ALT(s, r) |
39 def | (r: String) = ALT(s, r) |
40 def % = STAR(s) |
40 def % = STAR(s) |
41 def ~ (r: Rexp) = SEQ(s, r) |
41 def ~ (r: Rexp) = SEQ(s, r) |
42 def ~ (r: String) = SEQ(s, r)n jjjjjjj=99999ij9999ijn0n |
42 def ~ (r: String) = SEQ(s, r) |
43 def $ (r: Rexp) = RECD(s, r) |
43 def $ (r: Rexp) = RECD(s, r) |
44 } |
44 } |
45 |
45 |
46 def pretty(r: Rexp) : String = r match { |
46 def pretty(r: Rexp) : String = r match { |
47 case NULL => "0" |
47 case NULL => "0" |
253 } |
253 } |
254 } |
254 } |
255 |
255 |
256 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
256 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
257 |
257 |
258 |
258 lexing_sim(("a" + "ab") | ("b" + ""), "ab") |
259 // brute force search infrastructure |
259 // brute force search infrastructure |
260 |
260 |
261 // enumerates regular expressions until a certain depth |
261 // enumerates regular expressions until a certain depth |
262 def enum(n: Int, s: String) : Set[Rexp] = n match { |
262 def enum(n: Int, s: String) : Set[Rexp] = n match { |
263 case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR) |
263 case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR) |
321 |
321 |
322 //tests for transitivity (simple transitivity fails) |
322 //tests for transitivity (simple transitivity fails) |
323 def transitivity_test(r: Rexp)(v1: Val)(v2: Val)(v3: Val) : Boolean = |
323 def transitivity_test(r: Rexp)(v1: Val)(v2: Val)(v3: Val) : Boolean = |
324 ord(v1, v2) && ord(v2, v3) && !ord(v1, v3) |
324 ord(v1, v2) && ord(v2, v3) && !ord(v1, v3) |
325 |
325 |
|
326 val test0 = enum(3, "a").flatMap(vfilter3(transitivity_test)) |
|
327 val test0_smallest = test0.toList.sortWith { (x,y) => size(x._1) < size(y._1) }.head |
|
328 |
|
329 pretty(test0_smallest._1) |
|
330 vpretty(test0_smallest._2) |
|
331 vpretty(test0_smallest._3) |
|
332 vpretty(test0_smallest._4) |
|
333 |
|
334 /* Counter example for simple transitivity: |
|
335 |
|
336 r = a | ((a | a)(a | e)) |
|
337 |
|
338 v1 = Left(a) |
|
339 v2 = Right(Left(a) ~ Right(())) |
|
340 v3 = Right(Right(a) ~ Left(a)) |
|
341 |
|
342 */ |
|
343 |
|
344 def is_seq(v: Val) : Boolean = v match { |
|
345 case Seq(_, _) => true |
|
346 case _ => false |
|
347 } |
|
348 |
326 def transitivity_test_extended(r: Rexp)(v1: Val)(v2: Val)(v3: Val) : Boolean = { |
349 def transitivity_test_extended(r: Rexp)(v1: Val)(v2: Val)(v3: Val) : Boolean = { |
327 flatten(v1) == flatten(v2) && flatten(v2) == flatten(v3) && |
350 //flatten(v1).size >= flatten(v2).size && |
|
351 //flatten(v2).size >= flatten(v3).size && |
|
352 is_seq(v1) && |
328 ord(v1, v2) && ord(v2, v3) && !ord(v1, v3) |
353 ord(v1, v2) && ord(v2, v3) && !ord(v1, v3) |
329 } |
354 } |
330 |
355 |
331 // smallest(?) example where simple transitivity fails |
356 // smallest(?) example where simple transitivity fails |
332 val test1 = enum(3, "a").flatMap(vfilter3(transitivity_test)) |
357 val test1 = enum(3, "a").flatMap(vfilter3(transitivity_test_extended)) |
333 val test1_smallest = test1.toList.sortWith { (x,y) => size(x._1) < size(y._1) }.head |
358 val test1_smallest = test1.toList.sortWith { (x,y) => size(x._1) < size(y._1) }.head |
334 |
359 |
335 pretty(test1_smallest._1) |
360 pretty(test1_smallest._1) |
336 vpretty(test1_smallest._2) |
361 vpretty(test1_smallest._2) |
337 vpretty(test1_smallest._3) |
362 vpretty(test1_smallest._3) |
339 |
364 |
340 ord(test1_smallest._2, test1_smallest._3) |
365 ord(test1_smallest._2, test1_smallest._3) |
341 ord(test1_smallest._3, test1_smallest._4) |
366 ord(test1_smallest._3, test1_smallest._4) |
342 ord(test1_smallest._2, test1_smallest._4) |
367 ord(test1_smallest._2, test1_smallest._4) |
343 ordr(test1_smallest._3, test1_smallest._1, test1_smallest._4) |
368 ordr(test1_smallest._3, test1_smallest._1, test1_smallest._4) |
|
369 |
|
370 /* Counter example for extended transitivity: |
|
371 |
|
372 r = ((e | e)(e | a)) | a |
|
373 |
|
374 v1 = Left(Right(()) ~ Right(a)) |
|
375 v2 = Right(a) |
|
376 v3 = Left(Left(()) ~ Left(())) |
|
377 |
|
378 */ |
|
379 |
344 |
380 |
345 // with flatten test |
381 // with flatten test |
346 enum(3, "a").flatMap(vfilter3(transitivity_test_extended)) |
382 enum(3, "a").flatMap(vfilter3(transitivity_test_extended)) |
347 |
383 |
348 //injection tests |
384 //injection tests |