thys2/blexer2.sc
changeset 541 5bf9f94c02e1
parent 539 7cf9f17aa179
child 543 b2bea5968b89
equal deleted inserted replaced
540:3a1fd5ea2484 541:5bf9f94c02e1
   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) => 
   949       case r => r
   956       case r => r
   950     }
   957     }
   951   }
   958   }
   952 }
   959 }
   953 
   960 
       
   961 def prune6cc(acc: Set[Rexp], r: Rexp, ctx: List[Rexp]) : Rexp = {
       
   962   if (ABIncludedByC(a = r, b = ctx, c = acc, 
       
   963                     f = attachCtxcc, subseteqPred = rs1_subseteq_rs2)) 
       
   964   {//acc.flatMap(breakIntoTerms
       
   965     ZERO
       
   966   }
       
   967   else{
       
   968     r match {
       
   969       case SEQ(r1, r2) => 
       
   970       (prune6cc(acc, r1, r2 :: ctx)) match{
       
   971         case ZERO => 
       
   972           ZERO
       
   973         case ONE => 
       
   974           r2
       
   975         case r1p => 
       
   976           SEQ(r1p, r2)
       
   977       }
       
   978       case ALTS(r1, r2) => 
       
   979         List(r1, r2).map(r => prune6cc(acc, r, ctx)).filter(_ != AZERO) match {
       
   980           case Nil => 
       
   981             ZERO
       
   982           case r :: Nil => 
       
   983             r 
       
   984           case ra :: rb :: Nil => 
       
   985             ALTS(ra, rb)
       
   986         }
       
   987       case r => r
       
   988     }
       
   989   }
       
   990 }
   954 
   991 
   955 def distinctBy6(xs: List[ARexp], acc: Set[Rexp] = Set()) : List[ARexp] = xs match {
   992 def distinctBy6(xs: List[ARexp], acc: Set[Rexp] = Set()) : List[ARexp] = xs match {
   956   case Nil => 
   993   case Nil => 
   957     Nil
   994     Nil
   958   case x :: xs => {
   995   case x :: xs => {
   966       pruned match {
  1003       pruned match {
   967         case AZERO => 
  1004         case AZERO => 
   968           distinctBy6(xs, acc)
  1005           distinctBy6(xs, acc)
   969         case xPrime => 
  1006         case xPrime => 
   970           xPrime :: distinctBy6(xs, newTerms.map(oneSimp) ++: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc)
  1007           xPrime :: distinctBy6(xs, newTerms.map(oneSimp) ++: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc)
       
  1008       }
       
  1009     }
       
  1010   }
       
  1011 }
       
  1012 
       
  1013 def distinctByacc(xs: List[Rexp], acc: Set[Rexp] = Set()) : Set[Rexp] = xs match {
       
  1014   case Nil => 
       
  1015     acc
       
  1016   case x :: xs => {
       
  1017     if(acc.contains(x)){
       
  1018       distinctByacc(xs, acc)
       
  1019     }
       
  1020     else{
       
  1021       val pruned = prune6cc(acc, x, Nil)
       
  1022       val newTerms = turnIntoTerms(pruned)
       
  1023       pruned match {
       
  1024         case ZERO => 
       
  1025           distinctByacc(xs, acc)
       
  1026         case xPrime => 
       
  1027           distinctByacc(xs, newTerms.map(oneSimp) ++: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc)
   971       }
  1028       }
   972     }
  1029     }
   973   }
  1030   }
   974 }
  1031 }
   975 
  1032 
  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)