Mercurial Mercurial > hg > lexing / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
thys2/blexer2.sc
changeset 628 7af4e2420a8c
parent 591 b2d0de6aee18
child 629 96e009a446d5
equal deleted inserted replaced
627:94db2636a296 628:7af4e2420a8c 
   659               )
 
   659               )
 
   660           }
 
   660           }
 
   661       }
 
   661       }
 
   662 
   662 
   663     //r = r' ~ tail' : If tail' matches tail => returns r'
 
   663     //r = r' ~ tail' : If tail' matches tail => returns r'
 
   664     def removeSeqTail(r: Rexp, tail: Rexp) : Rexp = r match {
 
   664     def removeSeqTail(r: Rexp, tail: Rexp) : Rexp = 
   665       case SEQ(r1, r2) => 
   665       if (r == tail)
 
   666         if(r2 == tail) 
   666         ONE
 
   667           r1
 
   667       else {
 
   668         else
 
   668         r match {
 
   669           ZERO
 
   669           case SEQ(r1, r2) => 
   670       case r => ZERO
 
   670             if(r2 == tail) 
   671     }
 
   671               r1
 
       
   672             else
 
       
   673               ZERO
 
       
   674           case r => ZERO
 
       
   675         }
 
       
   676       }
 
   672 
   677 
   673     def prune(r: ARexp, acc: Set[Rexp]) : ARexp = r match{
 
   678     def prune(r: ARexp, acc: Set[Rexp]) : ARexp = r match{
 
   674       case AALTS(bs, rs) => rs.map(r => prune(r, acc)).filter(_ != ZERO) match
 
   679       case AALTS(bs, rs) => rs.map(r => prune(r, acc)).filter(_ != AZERO) match
 
   675       {
 
   680       {
 
   676         //all components have been removed, meaning this is effectively a duplicate
 
   681         //all components have been removed, meaning this is effectively a duplicate
 
   677         //flats will take care of removing this AZERO 
   682         //flats will take care of removing this AZERO 
   678         case Nil => AZERO
 
   683         case Nil => AZERO
 
   679         case r::Nil => fuse(bs, r)
 
   684         case r::Nil => fuse(bs, r)
 
   909       case ZERO => false
 
   914       case ZERO => false
 
   910 
   915 
   911     }
 
   916     }
 
   912 
   917 
   913     def turnIntoTerms(r: Rexp): List[Rexp] = r match {
 
   918     def turnIntoTerms(r: Rexp): List[Rexp] = r match {
 
   914       case SEQ(r1, r2)  => if(isOne1(r1)) 
   919       case SEQ(r1, r2)  => 
   915       turnIntoTerms(r2) 
   920     //   if(isOne1(r1)) 
   916     else 
   921     //   turnIntoTerms(r2) 
   917       turnIntoTerms(r1).flatMap(r11 => furtherSEQ(r11, r2))
 
   922     // else 
   918       case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2)
 
   923         turnIntoTerms(r1).flatMap(r11 => furtherSEQ(r11, r2))
 
   919       case ZERO => Nil
 
   924           case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2)
 
   920       case _ => r :: Nil
 
   925           case ZERO => Nil
 
       
   926           case _ => r :: Nil
 
   921     }
 
   927     }
 
   922 
   928 
   923     def furtherSEQ(r11: Rexp, r2: Rexp) : List[Rexp] = {
 
   929     def furtherSEQ(r11: Rexp, r2: Rexp) : List[Rexp] = {
 
   924       if(r11 == ONE)
 
   930       if(r11 == ONE)
 
   925         turnIntoTerms(r2)
 
   931         turnIntoTerms(r2)
 
  1542     //new ce1 : STAR(SEQ(ALTS(ALTS(ONE,CHAR(a)),SEQ(ONE,CHAR(b))),ALTS(CHAR(a),ALTS(CHAR(b),CHAR(a)))))
 
  1548     //new ce1 : STAR(SEQ(ALTS(ALTS(ONE,CHAR(a)),SEQ(ONE,CHAR(b))),ALTS(CHAR(a),ALTS(CHAR(b),CHAR(a)))))
 
  1543     //new ce2 : ALTS(CHAR(b),SEQ(ALTS(ZERO,ALTS(CHAR(b),CHAR(b))),ALTS(ALTS(CHAR(a),CHAR(b)),SEQ(CHAR(c),ONE))))
 
  1549     //new ce2 : ALTS(CHAR(b),SEQ(ALTS(ZERO,ALTS(CHAR(b),CHAR(b))),ALTS(ALTS(CHAR(a),CHAR(b)),SEQ(CHAR(c),ONE))))
 
  1544     //new ce3 : SEQ(CHAR(b),ALTS(ALTS(ALTS(ONE,CHAR(a)),SEQ(CHAR(c),ONE)),SEQ(STAR(ZERO),SEQ(ONE,CHAR(b)))))
 
  1550     //new ce3 : SEQ(CHAR(b),ALTS(ALTS(ALTS(ONE,CHAR(a)),SEQ(CHAR(c),ONE)),SEQ(STAR(ZERO),SEQ(ONE,CHAR(b)))))
 
  1545     //circular double-nullable STAR(SEQ((STAR("b") | "a" | "b"), ("b" | ONE)))
 
  1551     //circular double-nullable STAR(SEQ((STAR("b") | "a" | "b"), ("b" | ONE)))
 
  1546     def counterexample_check() {
 
  1552     def counterexample_check() {
 
  1547       val r = STAR(SEQ(ALTS(STAR(CHAR('b')),ALTS(CHAR('b'),CHAR('a'))),
 
  1553       val r : Rexp = SEQ(ALTS(ONE, 
  1548         ALTS(ALTS(CHAR('b'),CHAR('c')),STAR(ZERO))))//SEQ(SEQ(STAR(ALTS(CHAR('a'),CHAR('b'))),
 
  1554         SEQ(ALTS(CHAR('f'), CHAR('b')), CHAR('g'))), SEQ(CHAR('a'), SEQ(CHAR('d'), CHAR('e'))))//(1+(f +b)·g)·(a·(d·e))//STAR(SEQ(ALTS(STAR(CHAR('b')),ALTS(CHAR('b'),CHAR('a'))),
 
       
  1555       val acc : Set[Rexp] = Set(SEQ(CHAR('a'), SEQ(CHAR('d'), CHAR('e'))), SEQ(SEQ(CHAR('f'), CHAR('g')), SEQ(CHAR('a'), SEQ(CHAR('d'), CHAR('e')))) )
 
       
  1556       val a = internalise(r)
 
       
  1557       aprint(prune(a, acc));
 
       
  1558         //ALTS(ALTS(CHAR('b'),CHAR('c')),STAR(ZERO))))//SEQ(SEQ(STAR(ALTS(CHAR('a'),CHAR('b'))),
 
  1549       //ALTS(ALTS(CHAR('c'),CHAR('b')),STAR(ONE))),STAR(CHAR('b')))
 
  1559       //ALTS(ALTS(CHAR('c'),CHAR('b')),STAR(ONE))),STAR(CHAR('b')))
 
  1550       val s = "ab"
 
  1560       // val s = "ab"
 
  1551       val bdStrong5 = bdersStrong6(s.toList, internalise(r))
 
  1561       // val bdStrong5 = bdersStrong6(s.toList, internalise(r))
 
  1552       val bdStrong5Set = breakIntoTerms(erase(bdStrong5))
 
  1562       // val bdStrong5Set = breakIntoTerms(erase(bdStrong5))
 
  1553       val pdersSet = pderUNIV(r)//.map(r => erase(bsimp(internalise(r))))//.flatMap(r => turnIntoTerms(r))//.map(oneSimp).flatMap(r => breakIntoTerms(r))
 
  1563       // val pdersSet = pderUNIV(r)//.map(r => erase(bsimp(internalise(r))))//.flatMap(r => turnIntoTerms(r))//.map(oneSimp).flatMap(r => breakIntoTerms(r))
 
  1554       val apdersSet = pdersSet.map(internalise)
 
  1564       // val apdersSet = pdersSet.map(internalise)
 
  1555       println("original regex ")
 
  1565       // println("original regex ")
 
  1556       rprint(r)
 
  1566       // rprint(r)
 
  1557       println("after strong bsimp")
 
  1567       // println("after strong bsimp")
 
  1558       aprint(bdStrong5)
 
  1568       // aprint(bdStrong5)
 
  1559       println("turned into a set %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   ")
 
  1569       // println("turned into a set %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   ")
 
  1560       rsprint(bdStrong5Set)
 
  1570       // rsprint(bdStrong5Set)
 
  1561       println("after pderUNIV")
 
  1571       // println("after pderUNIV")
 
  1562       rsprint(pdersSet.toList)
 
  1572       // rsprint(pdersSet.toList)
 
  1563       println("pderUNIV distinctBy6")
 
  1573       // println("pderUNIV distinctBy6")
 
  1564       //asprint(distinctBy6(apdersSet.toList))
 
  1574       // //asprint(distinctBy6(apdersSet.toList))
 
  1565       rsprint((pdersSet.toList).flatMap(turnIntoTerms))
 
  1575       // rsprint((pdersSet.toList).flatMap(turnIntoTerms))
 
  1566       // rsprint(turnIntoTerms(pdersSet.toList(3)))
 
  1576       // rsprint(turnIntoTerms(pdersSet.toList(3)))
 
  1567       // println("NO 3 not into terms")
 
  1577       // println("NO 3 not into terms")
 
  1568       // rprint((pdersSet.toList()))
 
  1578       // rprint((pdersSet.toList()))
 
  1569       // println("after pderUNIV broken")
 
  1579       // println("after pderUNIV broken")
 
  1570       // rsprint(pdersSet.flatMap(r => turnIntoTerms(r)).toList)
 
  1580       // rsprint(pdersSet.flatMap(r => turnIntoTerms(r)).toList)
 
  1584       val apdersSet = pdersSet.map(internalise)
 
  1594       val apdersSet = pdersSet.map(internalise)
 
  1585       lfprint(lf(r))
 
  1595       lfprint(lf(r))
 
  1586 
  1596 
  1587     }
 
  1597     }
 
  1588 
  1598 
  1589     lf_display()
 
  1599     // lf_display()
 
  1590 
  1600 
  1591     def breakable(r: Rexp) : Boolean = r match {
 
  1601     def breakable(r: Rexp) : Boolean = r match {
 
  1592       case SEQ(ALTS(_, _), _) => true
 
  1602       case SEQ(ALTS(_, _), _) => true
 
  1593       case SEQ(r1, r2) => breakable(r1)
 
  1603       case SEQ(r1, r2) => breakable(r1)
 
  1594       case _ => false
 
  1604       case _ => false
 
  1655         }
 
  1665         }
 
  1656         //  bders_bderssimp()
 
  1666         //  bders_bderssimp()
 
  1657 
  1667 
  1658 
  1668 
  1659 
  1669 
       
  1670 println("hi!!!!!")
 
       
  1671 counterexample_check()
lexing