913 def attachCtx(r: ARexp, ctx: List[Rexp]) : Set[Rexp] = { |
913 def attachCtx(r: ARexp, ctx: List[Rexp]) : Set[Rexp] = { |
914 val res = turnIntoTerms((L(erase(r), ctx))).map(oneSimp) |
914 val res = turnIntoTerms((L(erase(r), ctx))).map(oneSimp) |
915 res.toSet |
915 res.toSet |
916 } |
916 } |
917 |
917 |
|
918 def attachCtxcc(r: Rexp, ctx: List[Rexp]) : Set[Rexp] = { |
|
919 val res = turnIntoTerms((L(r, ctx))).map(oneSimp) |
|
920 res.toSet |
|
921 } |
|
922 |
918 def ABIncludedByC[A, B, C](a: A, b: B, c: C, f: (A, B) => C, subseteqPred: (C, C) => Boolean) : Boolean = { |
923 def ABIncludedByC[A, B, C](a: A, b: B, c: C, f: (A, B) => C, subseteqPred: (C, C) => Boolean) : Boolean = { |
919 subseteqPred(f(a, b), c) |
924 subseteqPred(f(a, b), c) |
920 } |
925 } |
921 def rs1_subseteq_rs2(rs1: Set[Rexp], rs2: Set[Rexp]) : Boolean = { |
926 def rs1_subseteq_rs2(rs1: Set[Rexp], rs2: Set[Rexp]) : Boolean = { |
922 val res = rs1.forall(rs2.contains) |
927 val res = rs1.forall(rs2.contains) |
923 res |
928 res |
924 } |
929 } |
925 def prune6(acc: Set[Rexp], r: ARexp, ctx: List[Rexp]) : ARexp = { |
930 def prune6(acc: Set[Rexp], r: ARexp, ctx: List[Rexp]) : ARexp = { |
926 if (ABIncludedByC(r, ctx, acc, attachCtx, rs1_subseteq_rs2)) {//acc.flatMap(breakIntoTerms |
931 if (ABIncludedByC(a = r, b = ctx, c = acc, |
|
932 f = attachCtx, subseteqPred = rs1_subseteq_rs2)) |
|
933 {//acc.flatMap(breakIntoTerms |
927 AZERO |
934 AZERO |
928 } |
935 } |
929 else{ |
936 else{ |
930 r match { |
937 r match { |
931 case ASEQ(bs, r1, r2) => |
938 case ASEQ(bs, r1, r2) => |
1378 // print(duration) |
1435 // print(duration) |
1379 // println() |
1436 // println() |
1380 // } |
1437 // } |
1381 |
1438 |
1382 } |
1439 } |
1383 naive_matcher() |
1440 // naive_matcher() |
1384 def generator_test() { |
1441 def generator_test() { |
1385 |
1442 |
1386 test(rexp(4), 1000000) { (r: Rexp) => |
1443 test(single(SEQ(SEQ(STAR(CHAR('b')),STAR(STAR(SEQ(CHAR('a'),CHAR('b'))))), |
|
1444 SEQ(SEQ(CHAR('b'),STAR(ALTS(CHAR('a'),ONE))),ONE))), 1) { (r: Rexp) => |
1387 // ALTS(SEQ(SEQ(ONE,CHAR('a')),STAR(CHAR('a'))),SEQ(ALTS(CHAR('c'),ONE),STAR(ZERO))))))), 1) { (r: Rexp) => |
1445 // ALTS(SEQ(SEQ(ONE,CHAR('a')),STAR(CHAR('a'))),SEQ(ALTS(CHAR('c'),ONE),STAR(ZERO))))))), 1) { (r: Rexp) => |
1388 val ss = Set("b")//stringsFromRexp(r) |
1446 val ss = stringsFromRexp(r) |
1389 val boolList = ss.filter(s => s != "").map(s => { |
1447 val boolList = ss.map(s => { |
1390 //val bdStrong = bdersStrong(s.toList, internalise(r)) |
1448 //val bdStrong = bdersStrong(s.toList, internalise(r)) |
1391 val bdStrong6 = bdersStrong7(s.toList, internalise(r)) |
1449 val bdStrong6 = bdersStrong6(s.toList, internalise(r)) |
1392 val bdStrong6Set = turnIntoTerms(erase(bdStrong6)) |
1450 val bdStrong6Set = turnIntoTerms(erase(bdStrong6)) |
1393 val pdersSet = pderUNIV(r)//.flatMap(r => turnIntoTerms(r)) |
1451 val pdersSet = pderUNIV(r)//.flatMap(r => turnIntoTerms(r)) |
1394 val pdersSetBroken = pdersSet.flatMap(r => turnIntoTerms(r)) |
1452 val pdersSetBroken = pdersSet.flatMap(r => turnIntoTerms(r)) |
1395 bdStrong6Set.size <= pdersSet.size || bdStrong6Set.size <= pdersSetBroken.size |
1453 rs1_subseteq_rs2(bdStrong6Set.toSet, distinctByacc(pdersSet.toList)) |
|
1454 //bdStrong6Set.size <= pdersSet.size || bdStrong6Set.size <= pdersSetBroken.size || |
|
1455 //rs1_subseteq_rs2(bdStrong6Set.toSet, pdersSet union pdersSetBroken)//|| bdStrong6Set.size <= pdersSetBroken.size |
1396 }) |
1456 }) |
1397 //println(boolList) |
|
1398 //!boolList.exists(b => b == false) |
1457 //!boolList.exists(b => b == false) |
1399 !boolList.exists(b => b == false) |
1458 !boolList.exists(b => b == false) |
1400 } |
1459 } |
1401 } |
1460 } |
1402 // small() |
1461 // small() |
1406 //STAR(STAR(STAR(SEQ(SEQ(ALTS(STAR(ALTS(ONE,CHAR('c'))), |
1465 //STAR(STAR(STAR(SEQ(SEQ(ALTS(STAR(ALTS(ONE,CHAR('c'))), |
1407 // CHAR('c')),ALTS(CHAR('a'),ALTS(STAR(CHAR('b')),ALTS(CHAR('a'),ZERO)))), |
1466 // CHAR('c')),ALTS(CHAR('a'),ALTS(STAR(CHAR('b')),ALTS(CHAR('a'),ZERO)))), |
1408 // CHAR('c')))))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE)))//STAR(SEQ(ALTS(STAR(CHAR('c')),CHAR('c')),SEQ(ALTS(CHAR('c'),ONE),ONE))) |
1467 // CHAR('c')))))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE)))//STAR(SEQ(ALTS(STAR(CHAR('c')),CHAR('c')),SEQ(ALTS(CHAR('c'),ONE),ONE))) |
1409 //counterexample1: STAR(SEQ(ALTS(STAR(ZERO),ALTS(CHAR(a),CHAR(b))),SEQ(ONE,ALTS(CHAR(a),CHAR(b))))) |
1468 //counterexample1: STAR(SEQ(ALTS(STAR(ZERO),ALTS(CHAR(a),CHAR(b))),SEQ(ONE,ALTS(CHAR(a),CHAR(b))))) |
1410 //counterexample2: SEQ(ALTS(SEQ(CHAR(a),STAR(ONE)),STAR(ONE)),ALTS(CHAR(a),SEQ(ALTS(CHAR(c),CHAR(a)),CHAR(b)))) |
1469 //counterexample2: SEQ(ALTS(SEQ(CHAR(a),STAR(ONE)),STAR(ONE)),ALTS(CHAR(a),SEQ(ALTS(CHAR(c),CHAR(a)),CHAR(b)))) |
|
1470 |
|
1471 //new ce1 : STAR(SEQ(ALTS(ALTS(ONE,CHAR(a)),SEQ(ONE,CHAR(b))),ALTS(CHAR(a),ALTS(CHAR(b),CHAR(a))))) |
|
1472 //new ce2 : ALTS(CHAR(b),SEQ(ALTS(ZERO,ALTS(CHAR(b),CHAR(b))),ALTS(ALTS(CHAR(a),CHAR(b)),SEQ(CHAR(c),ONE)))) |
|
1473 //new ce3 : SEQ(CHAR(b),ALTS(ALTS(ALTS(ONE,CHAR(a)),SEQ(CHAR(c),ONE)),SEQ(STAR(ZERO),SEQ(ONE,CHAR(b))))) |
1411 def counterexample_check() { |
1474 def counterexample_check() { |
1412 val r = SEQ(SEQ(STAR(ALTS(CHAR('a'),CHAR('b'))), |
1475 val r = SEQ(SEQ(STAR(CHAR('b')),STAR(STAR(SEQ(CHAR('a'),CHAR('b'))))), |
1413 ALTS(ALTS(CHAR('c'),CHAR('b')),STAR(ONE))),STAR(CHAR('b'))) |
1476 SEQ(SEQ(CHAR('b'),STAR(ALTS(CHAR('a'),ONE))),ONE))//SEQ(SEQ(STAR(ALTS(CHAR('a'),CHAR('b'))), |
|
1477 //ALTS(ALTS(CHAR('c'),CHAR('b')),STAR(ONE))),STAR(CHAR('b'))) |
1414 val s = "b" |
1478 val s = "b" |
1415 val bdStrong5 = bdersStrong7(s.toList, internalise(r)) |
1479 val bdStrong5 = bdersStrong7(s.toList, internalise(r)) |
1416 val bdStrong5Set = breakIntoTerms(erase(bdStrong5)) |
1480 val bdStrong5Set = turnIntoTerms(erase(bdStrong5)) |
1417 val pdersSet = pderUNIV(r)//.map(r => erase(bsimp(internalise(r))))//.flatMap(r => turnIntoTerms(r))//.map(oneSimp).flatMap(r => breakIntoTerms(r)) |
1481 val pdersSet = pderUNIV(r)//.map(r => erase(bsimp(internalise(r))))//.flatMap(r => turnIntoTerms(r))//.map(oneSimp).flatMap(r => breakIntoTerms(r)) |
|
1482 val apdersSet = pdersSet.map(internalise) |
1418 println("original regex ") |
1483 println("original regex ") |
1419 rprint(r) |
1484 rprint(r) |
1420 println("after strong bsimp") |
1485 println("after strong bsimp") |
1421 aprint(bdStrong5) |
1486 aprint(bdStrong5) |
1422 println("turned into a set %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ") |
1487 println("turned into a set %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ") |
1423 rsprint(bdStrong5Set) |
1488 rsprint(bdStrong5Set) |
1424 println("after pderUNIV") |
1489 println("after pderUNIV") |
1425 rsprint(pdersSet.toList) |
1490 rsprint(pdersSet.toList) |
1426 |
1491 println("pderUNIV distinctBy6") |
1427 } |
1492 //asprint(distinctBy6(apdersSet.toList)) |
1428 // counterexample_check() |
1493 rsprint(distinctByacc(pdersSet.toList)) |
|
1494 // rsprint(turnIntoTerms(pdersSet.toList(3))) |
|
1495 // println("NO 3 not into terms") |
|
1496 // rprint((pdersSet.toList())) |
|
1497 // println("after pderUNIV broken") |
|
1498 // rsprint(pdersSet.flatMap(r => turnIntoTerms(r)).toList) |
|
1499 |
|
1500 } |
|
1501 counterexample_check() |
|
1502 |
|
1503 def breakable(r: Rexp) : Boolean = r match { |
|
1504 case SEQ(ALTS(_, _), _) => true |
|
1505 case SEQ(r1, r2) => breakable(r1) |
|
1506 case _ => false |
|
1507 } |
1429 |
1508 |
1430 def linform_test() { |
1509 def linform_test() { |
1431 val r = STAR(SEQ(STAR(CHAR('c')),ONE))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE))) // |
1510 val r = STAR(SEQ(STAR(CHAR('c')),ONE))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE))) // |
1432 val r_linforms = lf(r) |
1511 val r_linforms = lf(r) |
1433 println(r_linforms.size) |
1512 println(r_linforms.size) |