# HG changeset patch # User Christian Urban # Date 1465599226 -3600 # Node ID c2d36c3cf8ad2f8374aff3c6071615d4dfe24467 # Parent 761793cce563c1a5006c85e7021345d68fa08f89 run all posix tests diff -r 761793cce563 -r c2d36c3cf8ad progs/scala/tests.scala --- a/progs/scala/tests.scala Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/scala/tests.scala Fri Jun 10 23:53:46 2016 +0100 @@ -10,6 +10,9 @@ case class CHAR(c: Char) extends Rexp { override def toString = c.toString } +case object ANYCHAR extends Rexp { + override def toString = "." +} case class ALT(r1: Rexp, r2: Rexp) extends Rexp { override def toString = "(" + r1.toString + "|" + r2.toString + ")" } @@ -17,7 +20,132 @@ override def toString = "(" + r1.toString + r2.toString +")" } case class STAR(r: Rexp) extends Rexp -case class RECD(x: String, r: Rexp) extends Rexp +case class RECD(x: String, r: Rexp) extends Rexp { + override def toString = "[" + r.toString +"]" +} + + +abstract class Val +case object Empty extends Val +case class Chr(c: Char) extends Val +case class Sequ(v1: Val, v2: Val) extends Val +case class Left(v: Val) extends Val +case class Right(v: Val) extends Val +case class Stars(vs: List[Val]) extends Val + +// nullable function: tests whether the regular +// expression can recognise the empty string +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ANYCHAR => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case RECD(_, r1) => nullable(r1) +} + +// derivative of a regular expression w.r.t. a character +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ANYCHAR => ONE + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r) => SEQ(der(c, r), STAR(r)) + case RECD(_, r1) => der(c, r1) +} + +// derivative w.r.t. a string (iterates der) +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, der(c, r)) +} + +// extracts a string from value +def flatten(v: Val) : String = v match { + case Empty => "" + case Chr(c) => c.toString + case Left(v) => flatten(v) + case Right(v) => flatten(v) + case Sequ(v1, v2) => flatten(v1) + flatten(v2) + case Stars(vs) => vs.map(flatten).mkString +} + +// extracts an environment from a value +def env(v: Val, r: Rexp) : List[(String, String)] = (v, r) match { + case (Empty, ONE) => Nil + case (Chr(c), CHAR(_)) => Nil + case (Chr(c), ANYCHAR) => Nil + case (Left(v), ALT(r1, r2)) => env(v, r1) + case (Right(v), ALT(r1, r2)) => env(v, r2) + case (Sequ(v1, v2), SEQ(r1, r2)) => env(v1, r1) ::: env(v2, r2) + case (Stars(vs), STAR(r)) => vs.flatMap(env(_, r)) + case (v, RECD(x, r)) => (x, flatten(v))::env(v, r) +} + +// extracts indices for the underlying strings +def env2(v: Val, r: Rexp, n: Int) : (List[(Int, Int)], Int) = (v, r) match { + case (Empty, ONE) => (Nil, n) + case (Chr(c), CHAR(_)) => (Nil, n + 1) + case (Chr(c), ANYCHAR) => (Nil, n + 1) + case (Left(v), ALT(r1, r2)) => env2(v, r1, n) + case (Right(v), ALT(r1, r2)) => env2(v, r2, n) + case (Sequ(v1, v2), SEQ(r1, r2)) => { + val (e1, n1) = env2(v1, r1, n) + val (e2, n2) = env2(v2, r2, n1) + (e1 ::: e2, n2) + } + case (Stars(Nil), STAR(r)) => (Nil, n) + case (Stars(v :: vs), STAR(r)) => { + val (e1, n1) = env2(v, r, n) + val (e2, n2) = env2(Stars(vs), STAR(r), n1) + (e1 ::: e2, n2) + } + case (v, RECD(x, r)) => { + val (e1, n1) = env2(v, r, n) + ((n, n + flatten(v).length) :: e1, n1) + } +} + +// injection part +def mkeps(r: Rexp) : Val = r match { + case ONE => Empty + case ALT(r1, r2) => + if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) + case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) + case STAR(r) => Stars(Nil) + case RECD(x, r) => mkeps(r) +} + +def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { + case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) + case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) + case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) + case (CHAR(d), Empty) => Chr(c) + case (ANYCHAR, Empty) => Chr(c) + case (RECD(x, r1), _) => inj(r1, c, v) +} + + +// main lexing function (produces a value) +def lex(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") + case c::cs => inj(r, c, lex(der(c, r), cs)) +} + +def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) + + + +// Regular expression parser case class Parser(s: String) { var i = 0 @@ -39,11 +167,10 @@ def Term() : Rexp = { var f : Rexp = - if (more() && peek() != ')' && peek() != '|') Factor() else ZERO; + if (more() && peek() != ')' && peek() != '|') Factor() else ONE; while (more() && peek() != ')' && peek() != '|') { f = SEQ(f, Factor()) ; } - f } @@ -53,13 +180,21 @@ eat('*') ; b = STAR(b) ; } - + while (more() && peek() == '?') { + eat('?') ; + b = ALT(b, ONE) ; + } + while (more() && peek() == '+') { + eat('+') ; + b = SEQ(b, STAR(b)) ; + } b } def Base() : Rexp = { peek() match { - case '(' => { eat('(') ; val r = Regex(); eat(')') ; r } + case '(' => { eat('(') ; val r = Regex(); eat(')') ; RECD("",r) } + case '.' => { eat('.'); ANYCHAR } case _ => CHAR(next()) } } @@ -69,14 +204,40 @@ def process(line: String) : String = { - val s = line.split("\\t+")(1) - s + ": " + Parser(s).Regex().toString + if (line.head == '#') "#" else + { + val line_split = line.split("\\t+") + val reg_str = line_split(1) + val reg = RECD("", Parser(reg_str).Regex()) + val in_str = if (line_split(2) == "-") "" else line_split(2) + val res_str = line_split(3) + val our_val = lexing(reg, in_str) + val our_result = env2(our_val, reg, 0)._1.mkString("") + if (our_result != res_str) + { + reg_str + ": " + + reg.toString + ": " + + in_str + " \n " + + our_result + + " => \n" + res_str + " ! " + + our_val + ":" + reg + "\n" + } + else "*" + } } -val filename = "../tests/forced-assoc.txt" +//val filename = "../tests/forced-assoc.txt" +//val filename = "../tests/left-assoc.txt" +//val filename = "../tests/right-assoc.txt" +//val filename = "../tests/class.txt" +//val filename = "../tests/basic3.txt" +//val filename = "../tests/totest.txt" +//val filename = "../tests/repetition2.txt" +//val filename = "../tests/osx-bsd-critical.txt" +val filename = "../tests/nullsub3.txt" val filelines : List[String] = Source.fromFile(filename).getLines.toList -filelines.foreach((s: String) => println(process(s))) +filelines.foreach((s: String) => print(process(s))) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/basic3.txt --- a/progs/tests/basic3.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/basic3.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,142 +1,142 @@ - 1 \) () (1,2) - 2 \} } (0,1) +# 1 \) () (1,2) +# 2 \} } (0,1) 3 ] ] (0,1) - 4 $^ NULL (0,0) - 5 a($) aa (1,2)(2,2) - 6 a*(^a) aa (0,1)(0,1) - 7 (..)*(...)* a (0,0)(?,?)(?,?) - 8 (..)*(...)* abcd (0,4)(2,4)(?,?) +# 4 $^ NULL (0,0) +# 5 a($) aa (1,2)(2,2) +# 6 a*(^a) aa (0,1)(0,1) +# 7 (..)*(...)* a (0,0)(?,?)(?,?) + 8 (..)*(...)* abcd (0,4)(0,2)(2,4) 9 (ab|a)(bc|c) abc (0,3)(0,2)(2,3) 10 (ab)c|abc abc (0,3)(0,2) - 11 a{0}b ab (1,2) - 12 (a*)(b?)(b+)b{3} aaabbbbbbb (0,10)(0,3)(3,4)(4,7) - 13 (a*)(b{0,1})(b{1,})b{3} aaabbbbbbb (0,10)(0,3)(3,4)(4,7) +# 11 a{0}b ab (1,2) +# 12 (a*)(b?)(b+)b{3} aaabbbbbbb (0,10)(0,3)(3,4)(4,7) +# 13 (a*)(b{0,1})(b{1,})b{3} aaabbbbbbb (0,10)(0,3)(3,4)(4,7) 15 ((a|a)|a) a (0,1)(0,1)(0,1) 16 (a*)(a|aa) aaaa (0,4)(0,3)(3,4) 17 a*(a.|aa) aaaa (0,4)(2,4) - 18 a(b)|c(d)|a(e)f aef (0,3)(?,?)(?,?)(1,2) + 18 a(b)|c(d)|a(e)f aef (0,3)(1,2) 19 (a|b)?.* b (0,1)(0,1) - 20 (a|b)c|a(b|c) ac (0,2)(0,1)(?,?) - 21 (a|b)c|a(b|c) ab (0,2)(?,?)(1,2) - 22 (a|b)*c|(a|ab)*c abc (0,3)(1,2)(?,?) - 23 (a|b)*c|(a|ab)*c xc (1,2)(?,?)(?,?) - 24 (.a|.b).*|.*(.a|.b) xa (0,2)(0,2)(?,?) + 20 (a|b)c|a(b|c) ac (0,2)(0,1) + 21 (a|b)c|a(b|c) ab (0,2)(1,2) + 22 (a|b)*c|(a|ab)*c abc (0,3)(0,1)(1,2) +# 23 (a|b)*c|(a|ab)*c xc (1,2)(?,?)(?,?) +# 24 (.a|.b).*|.*(.a|.b) xa (0,2)(0,2)(?,?) 25 a?(ab|ba)ab abab (0,4)(0,2) - 26 a?(ac{0}b|ba)ab abab (0,4)(0,2) - 27 ab|abab abbabab (0,2) - 28 aba|bab|bba baaabbbaba (5,8) - 29 aba|bab baaabbbaba (6,9) - 30 (aa|aaa)*|(a|aaaaa) aa (0,2)(0,2)(?,?) - 31 (a.|.a.)*|(a|.a...) aa (0,2)(0,2)(?,?) - 32 ab|a xabc (1,3) - 33 ab|a xxabc (2,4) - 34 (Ab|cD)* aBcD (0,4)(2,4) - 35 :::1:::0:|:::1:1:0: :::0:::1:::1:::0: (8,17) - 36 :::1:::0:|:::1:1:1: :::0:::1:::1:::0: (8,17) - 37 [[:lower:]]+ `az{ (1,3) - 38 [[:upper:]]+ @AZ[ (1,3) +# 26 a?(ac{0}b|ba)ab abab (0,4)(0,2) +# 27 ab|abab abbabab (0,2) +# 28 aba|bab|bba baaabbbaba (5,8) +# 29 aba|bab baaabbbaba (6,9) + 30 (aa|aaa)*|(a|aaaaa) aa (0,2)(0,2) + 31 (a.|.a.)*|(a|.a...) aa (0,2)(0,2) +# 32 ab|a xabc (1,3) +# 33 ab|a xxabc (2,4) + 34 (aB|cD)* aBcD (0,4)(0,2)(2,4) +# 35 :::1:::0:|:::1:1:0: :::0:::1:::1:::0: (8,17) +# 36 :::1:::0:|:::1:1:1: :::0:::1:::1:::0: (8,17) +# 37 [[:lower:]]+ `az{ (1,3) +# 38 [[:upper:]]+ @AZ[ (1,3) 39 (a)(b)(c) abc (0,3)(0,1)(1,2)(2,3) 43 ((((((((((((((((((((((((((((((x)))))))))))))))))))))))))))))) x (0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1) - 44 ((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))* xx (0,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2) - 45 a?(ab|ba)* ababababababababababababababababababababababababababababababababababababababababa (0,81)(79,81) - 46 abaa|abbaa|abbbaa|abbbbaa ababbabbbabbbabbbbabbbbaa (18,25) - 47 abaa|abbaa|abbbaa|abbbbaa ababbabbbabbbabbbbabaa (18,22) - 48 aaac|aabc|abac|abbc|baac|babc|bbac|bbbc baaabbbabac (7,11) - 49 aaaa|bbbb|cccc|ddddd|eeeeee|fffffff|gggg|hhhh|iiiii|jjjjj|kkkkk|llll XaaaXbbbXcccXdddXeeeXfffXgggXhhhXiiiXjjjXkkkXlllXcbaXaaaa (53,57) + 44 ((((((((((((((((((((((((((((((x))))))))))))))))))))))))))))))* xx (0,2)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2)(1,2) + 45 a?(ab|ba)* ababababababababababababababababababababababababababababababababababababababababa (0,81)(1,3)(3,5)(5,7)(7,9)(9,11)(11,13)(13,15)(15,17)(17,19)(19,21)(21,23)(23,25)(25,27)(27,29)(29,31)(31,33)(33,35)(35,37)(37,39)(39,41)(41,43)(43,45)(45,47)(47,49)(49,51)(51,53)(53,55)(55,57)(57,59)(59,61)(61,63)(63,65)(65,67)(67,69)(69,71)(71,73)(73,75)(75,77)(77,79)(79,81) +# 46 abaa|abbaa|abbbaa|abbbbaa ababbabbbabbbabbbbabbbbaa (18,25) +# 47 abaa|abbaa|abbbaa|abbbbaa ababbabbbabbbabbbbabaa (18,22) +# 48 aaac|aabc|abac|abbc|baac|babc|bbac|bbbc baaabbbabac (7,11) +# 49 aaaa|bbbb|cccc|ddddd|eeeeee|fffffff|gggg|hhhh|iiiii|jjjjj|kkkkk|llll XaaaXbbbXcccXdddXeeeXfffXgggXhhhXiiiXjjjXkkkXlllXcbaXaaaa (53,57) 50 a*a*a*a*a*b aaaaaaaaab (0,10) 51 ab+bc abbc (0,4) 52 ab+bc abbbbc (0,6) 53 ab?bc abbc (0,4) 54 ab?bc abc (0,3) 55 ab?c abc (0,3) - 56 ab|cd abc (0,2) - 57 ab|cd abcd (0,2) - 58 a\(b a(b (0,3) - 59 a\(*b ab (0,2) - 60 a\(*b a((b (0,4) - 61 ((a)) abc (0,1)(0,1)(0,1) +# 56 ab|cd abc (0,2) +# 57 ab|cd abcd (0,2) +# 58 a\(b a(b (0,3) +# 59 a\(*b ab (0,2) +# 60 a\(*b a((b (0,4) +# 61 ((a)) abc (0,1)(0,1)(0,1) 62 (a)b(c) abc (0,3)(0,1)(2,3) - 63 a+b+c aabbabc (4,7) +# 63 a+b+c aabbabc (4,7) 64 a* aaa (0,3) - 65 (a*)* - (0,0)(0,0) + 65 (a*)* - (0,0) 66 (a*)+ - (0,0)(0,0) - 67 (a*|b)* - (0,0)(0,0) - 68 (a+|b)* ab (0,2)(1,2) - 69 (a+|b)+ ab (0,2)(1,2) - 70 (a+|b)? ab (0,1)(0,1) - 71 (^)* - (0,0)(0,0) - 72 ([abc])*d abbbcd (0,6)(4,5) - 73 ([abc])*bcd abcd (0,4)(0,1) + 67 (a*|b)* - (0,0) + 68 (a+|b)* ab (0,2)(0,1)(1,2) + 69 (a+|b)+ ab (0,2)(0,1)(1,2) +# 70 (a+|b)? ab (0,1)(0,1) +# 71 (^)* - (0,0)(0,0) +# 72 ([abc])*d abbbcd (0,6)(4,5) +# 73 ([abc])*bcd abcd (0,4)(0,1) 74 a|b|c|d|e e (0,1) 75 (a|b|c|d|e)f ef (0,2)(0,1) - 76 ((a*|b))* - (0,0)(0,0)(0,0) - 77 (ab|cd)e abcde (2,5)(2,4) - 78 (a|b)c*d abcd (1,4)(1,2) +# 76 ((a*|b))* - (0,0)(0,0)(0,0) +# 77 (ab|cd)e abcde (2,5)(2,4) +# 78 (a|b)c*d abcd (1,4)(1,2) 79 (ab|ab*)bc abc (0,3)(0,1) - 80 a([bc]*)c* abc (0,3)(1,3) - 81 a([bc]*)(c*d) abcd (0,4)(1,3)(3,4) - 82 a([bc]+)(c*d) abcd (0,4)(1,3)(3,4) - 83 a([bc]*)(c+d) abcd (0,4)(1,2)(2,4) - 84 a[bcd]*dcdcde adcdcde (0,7) +# 80 a([bc]*)c* abc (0,3)(1,3) +# 81 a([bc]*)(c*d) abcd (0,4)(1,3)(3,4) +# 82 a([bc]+)(c*d) abcd (0,4)(1,3)(3,4) +# 83 a([bc]*)(c+d) abcd (0,4)(1,2)(2,4) +# 84 a[bcd]*dcdcde adcdcde (0,7) 85 (ab|a)b*c abc (0,3)(0,2) 86 ((a)(b)c)(d) abcd (0,4)(0,3)(0,1)(1,2)(3,4) - 87 ^a(bc+|b[eh])g|.h$ abh (1,3)(?,?) - 88 (bc+d$|ef*g.|h?i(j|k)) effgz (0,5)(0,5)(?,?) - 89 (bc+d$|ef*g.|h?i(j|k)) ij (0,2)(0,2)(1,2) - 90 (bc+d$|ef*g.|h?i(j|k)) reffgz (1,6)(1,6)(?,?) +# 87 ^a(bc+|b[eh])g|.h$ abh (1,3)(?,?) +# 88 (bc+d$|ef*g.|h?i(j|k)) effgz (0,5)(0,5)(?,?) +# 89 (bc+d$|ef*g.|h?i(j|k)) ij (0,2)(0,2)(1,2) +# 90 (bc+d$|ef*g.|h?i(j|k)) reffgz (1,6)(1,6)(?,?) 91 (((((((((a))))))))) a (0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1)(0,1) 92 (.*)c(.*) abcde (0,5)(0,2)(3,5) 93 a(bc)d abcd (0,4)(1,3) - 94 a[-]?c ac (0,3) - 95 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Qaddafi (0,15)(?,?)(10,12) - 96 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mo'ammar_Gadhafi (0,16)(?,?)(11,13) - 97 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Kaddafi (0,15)(?,?)(10,12) - 98 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Qadhafi (0,15)(?,?)(10,12) - 99 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Gadafi (0,14)(?,?)(10,11) - 100 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mu'ammar_Qadafi (0,15)(?,?)(11,12) - 101 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moamar_Gaddafi (0,14)(?,?)(9,11) - 102 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mu'ammar_Qadhdhafi (0,18)(?,?)(13,15) - 103 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Khaddafi (0,16)(?,?)(11,13) - 104 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghaddafy (0,16)(?,?)(11,13) - 105 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghadafi (0,15)(?,?)(11,12) - 106 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghaddafi (0,16)(?,?)(11,13) - 107 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muamar_Kaddafi (0,14)(?,?)(9,11) - 108 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Quathafi (0,16)(?,?)(11,13) - 109 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Gheddafi (0,16)(?,?)(11,13) - 110 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moammar_Khadafy (0,15)(?,?)(11,12) - 111 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moammar_Qudhafi (0,15)(?,?)(10,12) - 112 a+(b|c)*d+ aabcdd (0,6)(3,4) - 113 ^.+$ vivi (0,4) - 114 ^(.+)$ vivi (0,4)(0,4) - 115 ^([^!.]+).att.com!(.+)$ gryphon.att.com!eby (0,19)(0,7)(16,19) - 116 ^([^!]+!)?([^!]+)$ bas (0,3)(?,?)(0,3) - 117 ^([^!]+!)?([^!]+)$ bar!bas (0,7)(0,4)(4,7) - 118 ^([^!]+!)?([^!]+)$ foo!bas (0,7)(0,4)(4,7) - 119 ^.+!([^!]+!)([^!]+)$ foo!bar!bas (0,11)(4,8)(8,11) - 120 ((foo)|(bar))!bas bar!bas (0,7)(0,3)(?,?)(0,3) - 121 ((foo)|(bar))!bas foo!bar!bas (4,11)(4,7)(?,?)(4,7) - 122 ((foo)|(bar))!bas foo!bas (0,7)(0,3)(0,3)(?,?) - 123 ((foo)|bar)!bas bar!bas (0,7)(0,3)(?,?) - 124 ((foo)|bar)!bas foo!bar!bas (4,11)(4,7)(?,?) +# 94 a[-]?c ac (0,3) +# 95 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Qaddafi (0,15)(?,?)(10,12) +# 96 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mo'ammar_Gadhafi (0,16)(?,?)(11,13) +# 97 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Kaddafi (0,15)(?,?)(10,12) +# 98 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Qadhafi (0,15)(?,?)(10,12) +# 99 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Gadafi (0,14)(?,?)(10,11) +# 100 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mu'ammar_Qadafi (0,15)(?,?)(11,12) +# 101 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moamar_Gaddafi (0,14)(?,?)(9,11) +# 102 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Mu'ammar_Qadhdhafi (0,18)(?,?)(13,15) +# 103 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Khaddafi (0,16)(?,?)(11,13) +# 104 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghaddafy (0,16)(?,?)(11,13) +# 105 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghadafi (0,15)(?,?)(11,12) +# 106 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Ghaddafi (0,16)(?,?)(11,13) +# 107 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muamar_Kaddafi (0,14)(?,?)(9,11) +# 108 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Quathafi (0,16)(?,?)(11,13) +# 109 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Muammar_Gheddafi (0,16)(?,?)(11,13) +# 110 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moammar_Khadafy (0,15)(?,?)(11,12) +# 111 M[ou]'?am+[ae]r_.*([AEae]l[-_])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy] Moammar_Qudhafi (0,15)(?,?)(10,12) + 112 a+(b|c)*d+ aabcdd (0,6)(2,3)(3,4) +# 113 ^.+$ vivi (0,4) +# 114 ^(.+)$ vivi (0,4)(0,4) +# 115 ^([^!.]+).att.com!(.+)$ gryphon.att.com!eby (0,19)(0,7)(16,19) +# 116 ^([^!]+!)?([^!]+)$ bas (0,3)(?,?)(0,3) +# 117 ^([^!]+!)?([^!]+)$ bar!bas (0,7)(0,4)(4,7) +# 118 ^([^!]+!)?([^!]+)$ foo!bas (0,7)(0,4)(4,7) +# 119 ^.+!([^!]+!)([^!]+)$ foo!bar!bas (0,11)(4,8)(8,11) + 120 ((foo)|(bar))!bas bar!bas (0,7)(0,3)(0,3) +# 121 ((foo)|(bar))!bas foo!bar!bas (4,11)(4,7)(?,?)(4,7) + 122 ((foo)|(bar))!bas foo!bas (0,7)(0,3)(0,3) + 123 ((foo)|bar)!bas bar!bas (0,7)(0,3) +# 124 ((foo)|bar)!bas foo!bar!bas (4,11)(4,7)(?,?) 125 ((foo)|bar)!bas foo!bas (0,7)(0,3)(0,3) 126 (foo|(bar))!bas bar!bas (0,7)(0,3)(0,3) - 127 (foo|(bar))!bas foo!bar!bas (4,11)(4,7)(4,7) - 128 (foo|(bar))!bas foo!bas (0,7)(0,3)(?,?) +# 127 (foo|(bar))!bas foo!bar!bas (4,11)(4,7)(4,7) + 128 (foo|(bar))!bas foo!bas (0,7)(0,3) 129 (foo|bar)!bas bar!bas (0,7)(0,3) - 130 (foo|bar)!bas foo!bar!bas (4,11)(4,7) +# 130 (foo|bar)!bas foo!bar!bas (4,11)(4,7) 131 (foo|bar)!bas foo!bas (0,7)(0,3) - 132 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bar!bas (0,11)(0,11)(?,?)(?,?)(4,8)(8,11) - 133 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ bas (0,3)(?,?)(0,3)(?,?)(?,?) - 134 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ bar!bas (0,7)(0,4)(4,7)(?,?)(?,?) - 135 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ foo!bar!bas (0,11)(?,?)(?,?)(4,8)(8,11) - 136 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ foo!bas (0,7)(0,4)(4,7)(?,?)(?,?) - 137 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ bas (0,3)(0,3)(?,?)(0,3)(?,?)(?,?) - 138 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ bar!bas (0,7)(0,7)(0,4)(4,7)(?,?)(?,?) - 139 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bar!bas (0,11)(0,11)(?,?)(?,?)(4,8)(8,11) - 140 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bas (0,7)(0,7)(0,4)(4,7)(?,?)(?,?) +# 132 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bar!bas (0,11)(0,11)(?,?)(?,?)(4,8)(8,11) +# 133 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ bas (0,3)(?,?)(0,3)(?,?)(?,?) +# 134 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ bar!bas (0,7)(0,4)(4,7)(?,?)(?,?) +# 135 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ foo!bar!bas (0,11)(?,?)(?,?)(4,8)(8,11) +# 136 ^([^!]+!)?([^!]+)$|^.+!([^!]+!)([^!]+)$ foo!bas (0,7)(0,4)(4,7)(?,?)(?,?) +# 137 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ bas (0,3)(0,3)(?,?)(0,3)(?,?)(?,?) +# 138 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ bar!bas (0,7)(0,7)(0,4)(4,7)(?,?)(?,?) +# 139 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bar!bas (0,11)(0,11)(?,?)(?,?)(4,8)(8,11) +# 140 ^(([^!]+!)?([^!]+)|.+!([^!]+!)([^!]+))$ foo!bas (0,7)(0,7)(0,4)(4,7)(?,?)(?,?) 141 .*(/XXX).* /XXX (0,4)(0,4) - 142 .*(\\XXX).* \XXX (0,4)(0,4) - 143 \\XXX \XXX (0,4) +# 142 .*(\\XXX).* \XXX (0,4)(0,4) +# 143 \\XXX \XXX (0,4) 144 .*(/000).* /000 (0,4)(0,4) - 145 .*(\\000).* \000 (0,4)(0,4) - 146 \\000 \000 (0,4) +# 145 .*(\\000).* \000 (0,4)(0,4) +# 146 \\000 \000 (0,4) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/class.txt --- a/progs/tests/class.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/class.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,14 +1,14 @@ -1 aa* xaxaax (1,2) -2 (a*)(ab)*(b*) abc (0,2)(0,1)(?,?)(1,2) --2 (a*)(ab)*(b*) abc (0,2)(0,0)(0,2)(2,2) +#1 aa* xaxaax (1,2) +#2 (a*)(ab)*(b*) abc (0,2)(0,1)(?,?)(1,2) +#-2 (a*)(ab)*(b*) abc (0,2)(0,0)(0,2)(2,2) 3 ((a*)(ab)*)((b*)(a*)) aba (0,3)(0,2)(0,0)(0,2)(2,3)(2,2)(2,3) -4 (...?.?)* xxxxxx (0,6)(4,6) -5 (a|ab)(bc|c) abcabc (0,3)(0,2)(2,3) +#4 (...?.?)* xxxxxx (0,6)(4,6) +#5 (a|ab)(bc|c) abcabc (0,3)(0,2)(2,3) 6 (aba|a*b)(aba|a*b) ababa (0,5)(0,2)(2,5) -7 (a*){2} xxxxx (0,0)(0,0) +#7 (a*){2} xxxxx (0,0)(0,0) 8 (a*)* a (0,1)(0,1) -9 (aba|a*b)* ababa (0,5)(2,5) -10 (a(b)?)+ aba (0,3)(2,3)(?,?) +9 (aba|a*b)* ababa (0,5)(0,2)(2,5) +10 (a(b)?)+ aba (0,3)(0,2)(1,2)(2,3) 11 .*(.*) ab (0,2)(2,2) -12 (a?)((ab)?)(b?)a?(ab)?b? abab (0,4)(0,1)(1,1)(?,?)(1,2)(?,?) --12 (a?)((ab)?)(b?)a?(ab)?b? abab (0,4)(0,1)(1,1)(?,?)(1,2)(2,4) +#12 (a?)((ab)?)(b?)a?(ab)?b? abab (0,4)(0,1)(1,1)(?,?)(1,2)(?,?) +-12 (a?)((ab)?)(b?)a?(ab)?b? abab (0,4)(0,0)(0,2)(0,2)(2,2)(2,4) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/nullsub3.txt --- a/progs/tests/nullsub3.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/nullsub3.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,51 +1,51 @@ 1 (a*)* a (0,1)(0,1) - 2 SAME x (0,0)(0,0) - 3 SAME aaaaaa (0,6)(0,6) - 4 SAME aaaaaax (0,6)(0,6) +# 2 SAME x (0,0)(0,0) +# 3 SAME aaaaaa (0,6)(0,6) +# 4 SAME aaaaaax (0,6)(0,6) 5 (a*)+ a (0,1)(0,1) - 6 SAME x (0,0)(0,0) - 7 SAME aaaaaa (0,6)(0,6) - 8 SAME aaaaaax (0,6)(0,6) +# 6 SAME x (0,0)(0,0) +# 7 SAME aaaaaa (0,6)(0,6) +# 8 SAME aaaaaax (0,6)(0,6) 9 (a+)* a (0,1)(0,1) - 10 SAME x (0,0)(?,?) - 11 SAME aaaaaa (0,6)(0,6) - 12 SAME aaaaaax (0,6)(0,6) +# 10 SAME x (0,0)(?,?) +# 11 SAME aaaaaa (0,6)(0,6) +# 12 SAME aaaaaax (0,6)(0,6) 13 (a+)+ a (0,1)(0,1) - 14 SAME x NOMATCH - 15 SAME aaaaaa (0,6)(0,6) - 16 SAME aaaaaax (0,6)(0,6) - 17 ([a]*)* a (0,1)(0,1) - 18 SAME x (0,0)(0,0) - 19 SAME aaaaaa (0,6)(0,6) - 20 SAME aaaaaax (0,6)(0,6) - 21 ([a]*)+ a (0,1)(0,1) - 22 SAME x (0,0)(0,0) - 23 SAME aaaaaa (0,6)(0,6) - 24 SAME aaaaaax (0,6)(0,6) - 25 ([^b]*)* a (0,1)(0,1) - 26 SAME b (0,0)(0,0) - 27 SAME aaaaaa (0,6)(0,6) - 28 SAME aaaaaab (0,6)(0,6) - 29 ([ab]*)* a (0,1)(0,1) - 30 SAME aaaaaa (0,6)(0,6) - 31 SAME ababab (0,6)(0,6) - 32 SAME bababa (0,6)(0,6) - 33 SAME b (0,1)(0,1) - 34 SAME bbbbbb (0,6)(0,6) - 35 SAME aaaabcde (0,5)(0,5) - 36 ([^a]*)* b (0,1)(0,1) - 37 SAME bbbbbb (0,6)(0,6) - 38 SAME aaaaaa (0,0)(0,0) - 39 ([^ab]*)* ccccxx (0,6)(0,6) - 40 SAME ababab (0,0)(0,0) - 41 ((z)+|a)* zabcde (0,2)(1,2)(?,?) - 42 (a) aaa (0,1)(0,1) - 46 (a*)*(x) x (0,1)(0,0)(0,1) +# 14 SAME x NOMATCH +# 15 SAME aaaaaa (0,6)(0,6) +# 16 SAME aaaaaax (0,6)(0,6) + 17 (a*)* a (0,1)(0,1) +# 18 SAME x (0,0)(0,0) +# 19 SAME aaaaaa (0,6)(0,6) +# 20 SAME aaaaaax (0,6)(0,6) + 21 (a*)+ a (0,1)(0,1) +# 22 SAME x (0,0)(0,0) +# 23 SAME aaaaaa (0,6)(0,6) +# 24 SAME aaaaaax (0,6)(0,6) +# 25 ([^b]*)* a (0,1)(0,1) +# 26 SAME b (0,0)(0,0) +# 27 SAME aaaaaa (0,6)(0,6) +# 28 SAME aaaaaab (0,6)(0,6) +# 29 ([ab]*)* a (0,1)(0,1) +# 30 SAME aaaaaa (0,6)(0,6) +# 31 SAME ababab (0,6)(0,6) +# 32 SAME bababa (0,6)(0,6) +# 33 SAME b (0,1)(0,1) +# 34 SAME bbbbbb (0,6)(0,6) +# 35 SAME aaaabcde (0,5)(0,5) +# 36 ([^a]*)* b (0,1)(0,1) +# 37 SAME bbbbbb (0,6)(0,6) +# 38 SAME aaaaaa (0,0)(0,0) +# 39 ([^ab]*)* ccccxx (0,6)(0,6) +# 40 SAME ababab (0,0)(0,0) +# 41 ((z)+|a)* zabcde (0,2)(1,2)(?,?) +# 42 (a) aaa (0,1)(0,1) + 46 (a*)*(x) x (0,1)(0,1) 47 (a*)*(x) ax (0,2)(0,1)(1,2) - 48 (a*)*(x) axa (0,2)(0,1)(1,2) +# 48 (a*)*(x) axa (0,2)(0,1)(1,2) 49 (a*)+(x) x (0,1)(0,0)(0,1) 50 (a*)+(x) ax (0,2)(0,1)(1,2) - 51 (a*)+(x) axa (0,2)(0,1)(1,2) - 52 (a*){2}(x) x (0,1)(0,0)(0,1) - 53 (a*){2}(x) ax (0,2)(1,1)(1,2) - 54 (a*){2}(x) axa (0,2)(1,1)(1,2) +# 51 (a*)+(x) axa (0,2)(0,1)(1,2) +# 52 (a*){2}(x) x (0,1)(0,0)(0,1) +# 53 (a*){2}(x) ax (0,2)(1,1)(1,2) +# 54 (a*){2}(x) axa (0,2)(1,1)(1,2) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/osx-bsd-critical.txt --- a/progs/tests/osx-bsd-critical.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/osx-bsd-critical.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,11 +1,11 @@ -1 (()|.)(b) ab (0,2)(0,1)(?,?)(1,2) --1 (()|.)(b) ab (1,2)(1,1)(1,1)(1,2) -2 (()|[ab])(b) ab (0,2)(0,1)(?,?)(1,2) --2 (()|[ab])(b) ab (1,2)(1,1)(1,1)(1,2) -3 (()|[ab])+b aaab (0,4)(2,3)(?,?) --3 (()|[ab])+b aaab (3,4)(3,3)(3,3) -11 (.|())(b) ab (0,2)(0,1)(?,?)(1,2) -12 ([ab]|())(b) ab (0,2)(0,1)(?,?)(1,2) -14 ([ab]|())+b aaab (0,4)(2,3)(?,?) --14 ([ab]|())+b aaab (0,4)(3,3)(3,3) +1 (()|.)(b) ab (0,2)(0,1)(1,2) +-1 (()|.)(b) ab (0,2)(0,1)(1,2) +#2 (()|[ab])(b) ab (0,2)(0,1)(?,?)(1,2) +#-2 (()|[ab])(b) ab (1,2)(1,1)(1,1)(1,2) +#3 (()|[ab])+b aaab (0,4)(2,3)(?,?) +#-3 (()|[ab])+b aaab (3,4)(3,3)(3,3) +11 (.|())(b) ab (0,2)(0,1)(1,2) +#12 ([ab]|())(b) ab (0,2)(0,1)(?,?)(1,2) +#14 ([ab]|())+b aaab (0,4)(2,3)(?,?) +#-14 ([ab]|())+b aaab (0,4)(3,3)(3,3) 20 (.?)(b) ab (0,2)(0,1)(1,2) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/repetition2.txt --- a/progs/tests/repetition2.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/repetition2.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,79 +1,79 @@ -1 ((..)|(.)) NULL NOMATCH -2 ((..)|(.))((..)|(.)) NULL NOMATCH -3 ((..)|(.))((..)|(.))((..)|(.)) NULL NOMATCH -4 ((..)|(.)){1} NULL NOMATCH -5 ((..)|(.)){2} NULL NOMATCH -6 ((..)|(.)){3} NULL NOMATCH -7 ((..)|(.))* NULL (0,0)(?,?)(?,?)(?,?) -8 ((..)|(.)) a (0,1)(0,1)(?,?)(0,1) -9 ((..)|(.))((..)|(.)) a NOMATCH -10 ((..)|(.))((..)|(.))((..)|(.)) a NOMATCH -11 ((..)|(.)){1} a (0,1)(0,1)(?,?)(0,1) -12 ((..)|(.)){2} a NOMATCH -13 ((..)|(.)){3} a NOMATCH -14 ((..)|(.))* a (0,1)(0,1)(?,?)(0,1) -15 ((..)|(.)) aa (0,2)(0,2)(0,2)(?,?) -16 ((..)|(.))((..)|(.)) aa (0,2)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2) -17 ((..)|(.))((..)|(.))((..)|(.)) aa NOMATCH -18 ((..)|(.)){1} aa (0,2)(0,2)(0,2)(?,?) -19 ((..)|(.)){2} aa (0,2)(1,2)(?,?)(1,2) -20 ((..)|(.)){3} aa NOMATCH -21 ((..)|(.))* aa (0,2)(0,2)(0,2)(?,?) -22 ((..)|(.)) aaa (0,2)(0,2)(0,2)(?,?) -23 ((..)|(.))((..)|(.)) aaa (0,3)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3) -24 ((..)|(.))((..)|(.))((..)|(.)) aaa (0,3)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2)(2,3)(?,?)(2,3) -25 ((..)|(.)){1} aaa (0,2)(0,2)(0,2)(?,?) -26 ((..)|(.)){2} aaa (0,3)(2,3)(?,?)(2,3) -27 ((..)|(.)){3} aaa (0,3)(2,3)(?,?)(2,3) -28 ((..)|(.))* aaa (0,3)(2,3)(?,?)(2,3) -29 ((..)|(.)) aaaa (0,2)(0,2)(0,2)(?,?) -30 ((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) -31 ((..)|(.))((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3)(3,4)(?,?)(3,4) -32 ((..)|(.)){1} aaaa (0,2)(0,2)(0,2)(?,?) -33 ((..)|(.)){2} aaaa (0,4)(2,4)(2,4)(?,?) -34 ((..)|(.)){3} aaaa (0,4)(3,4)(?,?)(3,4) -35 ((..)|(.))* aaaa (0,4)(2,4)(2,4)(?,?) -36 ((..)|(.)) aaaaa (0,2)(0,2)(0,2)(?,?) -37 ((..)|(.))((..)|(.)) aaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) -38 ((..)|(.))((..)|(.))((..)|(.)) aaaaa (0,5)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,5)(?,?)(4,5) -39 ((..)|(.)){1} aaaaa (0,2)(0,2)(0,2)(?,?) -40 ((..)|(.)){2} aaaaa (0,4)(2,4)(2,4)(?,?) -41 ((..)|(.)){3} aaaaa (0,5)(4,5)(?,?)(4,5) -42 ((..)|(.))* aaaaa (0,5)(4,5)(?,?)(4,5) -43 ((..)|(.)) aaaaaa (0,2)(0,2)(0,2)(?,?) -44 ((..)|(.))((..)|(.)) aaaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) -45 ((..)|(.))((..)|(.))((..)|(.)) aaaaaa (0,6)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,6)(4,6)(?,?) -46 ((..)|(.)){1} aaaaaa (0,2)(0,2)(0,2)(?,?) -47 ((..)|(.)){2} aaaaaa (0,4)(2,4)(2,4)(?,?) -48 ((..)|(.)){3} aaaaaa (0,6)(4,6)(4,6)(?,?) -49 ((..)|(.))* aaaaaa (0,6)(4,6)(4,6)(?,?) -100 X(.?){0,}Y X1234567Y (0,9)(7,8) -101 X(.?){1,}Y X1234567Y (0,9)(7,8) -102 X(.?){2,}Y X1234567Y (0,9)(7,8) -103 X(.?){3,}Y X1234567Y (0,9)(7,8) -104 X(.?){4,}Y X1234567Y (0,9)(7,8) -105 X(.?){5,}Y X1234567Y (0,9)(7,8) -106 X(.?){6,}Y X1234567Y (0,9)(7,8) -107 X(.?){7,}Y X1234567Y (0,9)(7,8) -108 X(.?){8,}Y X1234567Y (0,9)(8,8) -110 X(.?){0,8}Y X1234567Y (0,9)(7,8) -111 X(.?){1,8}Y X1234567Y (0,9)(7,8) -112 X(.?){2,8}Y X1234567Y (0,9)(7,8) -113 X(.?){3,8}Y X1234567Y (0,9)(7,8) -114 X(.?){4,8}Y X1234567Y (0,9)(7,8) -115 X(.?){5,8}Y X1234567Y (0,9)(7,8) -116 X(.?){6,8}Y X1234567Y (0,9)(7,8) -117 X(.?){7,8}Y X1234567Y (0,9)(7,8) -118 X(.?){8,8}Y X1234567Y (0,9)(8,8) -260 (a|ab|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) -261 (a|ab|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) -262 (a|ab|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) -263 (a|ab|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) -264 (a|ab|c|bcd){4,}(d*) ababcd NOMATCH -265 (a|ab|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) -266 (a|ab|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) -267 (a|ab|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) -268 (a|ab|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) -269 (a|ab|c|bcd){4,10}(d*) ababcd NOMATCH -270 (a|ab|c|bcd)*(d*) ababcd (0,6)(3,6)(6,6) -271 (a|ab|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) +#1 ((..)|(.)) NULL NOMATCH +#2 ((..)|(.))((..)|(.)) NULL NOMATCH +#3 ((..)|(.))((..)|(.))((..)|(.)) NULL NOMATCH +#4 ((..)|(.)){1} NULL NOMATCH +#5 ((..)|(.)){2} NULL NOMATCH +#6 ((..)|(.)){3} NULL NOMATCH +7 ((..)|(.))* - (0,0) +8 ((..)|(.)) a (0,1)(0,1)(0,1) +#9 ((..)|(.))((..)|(.)) a NOMATCH +#10 ((..)|(.))((..)|(.))((..)|(.)) a NOMATCH +#11 ((..)|(.)){1} a (0,1)(0,1)(?,?)(0,1) +#12 ((..)|(.)){2} a NOMATCH +#13 ((..)|(.)){3} a NOMATCH +14 ((..)|(.))* a (0,1)(0,1)(0,1) +15 ((..)|(.)) aa (0,2)(0,2)(0,2) +16 ((..)|(.))((..)|(.)) aa (0,2)(0,1)(0,1)(1,2)(1,2) +#17 ((..)|(.))((..)|(.))((..)|(.)) aa NOMATCH +#18 ((..)|(.)){1} aa (0,2)(0,2)(0,2)(?,?) +#19 ((..)|(.)){2} aa (0,2)(1,2)(?,?)(1,2) +#20 ((..)|(.)){3} aa NOMATCH +21 ((..)|(.))* aa (0,2)(0,2)(0,2) +#22 ((..)|(.)) aaa (0,2)(0,2)(0,2)(?,?) +23 ((..)|(.))((..)|(.)) aaa (0,3)(0,2)(0,2)(2,3)(2,3) +24 ((..)|(.))((..)|(.))((..)|(.)) aaa (0,3)(0,1)(0,1)(1,2)(1,2)(2,3)(2,3) +#25 ((..)|(.)){1} aaa (0,2)(0,2)(0,2)(?,?) +#26 ((..)|(.)){2} aaa (0,3)(2,3)(?,?)(2,3) +#27 ((..)|(.)){3} aaa (0,3)(2,3)(?,?)(2,3) +28 ((..)|(.))* aaa (0,3)(0,2)(0,2)(2,3)(2,3) +#29 ((..)|(.)) aaaa (0,2)(0,2)(0,2)(?,?) +30 ((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(2,4)(2,4) +31 ((..)|(.))((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(2,3)(2,3)(3,4)(3,4) +#32 ((..)|(.)){1} aaaa (0,2)(0,2)(0,2)(?,?) +#33 ((..)|(.)){2} aaaa (0,4)(2,4)(2,4)(?,?) +#34 ((..)|(.)){3} aaaa (0,4)(3,4)(?,?)(3,4) +35 ((..)|(.))* aaaa (0,4)(0,2)(0,2)(2,4)(2,4) +#36 ((..)|(.)) aaaaa (0,2)(0,2)(0,2)(?,?) +#37 ((..)|(.))((..)|(.)) aaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) +38 ((..)|(.))((..)|(.))((..)|(.)) aaaaa (0,5)(0,2)(0,2)(2,4)(2,4)(4,5)(4,5) +#39 ((..)|(.)){1} aaaaa (0,2)(0,2)(0,2)(?,?) +#40 ((..)|(.)){2} aaaaa (0,4)(2,4)(2,4)(?,?) +#41 ((..)|(.)){3} aaaaa (0,5)(4,5)(?,?)(4,5) +42 ((..)|(.))* aaaaa (0,5)(0,2)(0,2)(2,4)(2,4)(4,5)(4,5) +#43 ((..)|(.)) aaaaaa (0,2)(0,2)(0,2)(?,?) +#44 ((..)|(.))((..)|(.)) aaaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) +45 ((..)|(.))((..)|(.))((..)|(.)) aaaaaa (0,6)(0,2)(0,2)(2,4)(2,4)(4,6)(4,6) +#46 ((..)|(.)){1} aaaaaa (0,2)(0,2)(0,2)(?,?) +#47 ((..)|(.)){2} aaaaaa (0,4)(2,4)(2,4)(?,?) +#48 ((..)|(.)){3} aaaaaa (0,6)(4,6)(4,6)(?,?) +49 ((..)|(.))* aaaaaa (0,6)(0,2)(0,2)(2,4)(2,4)(4,6)(4,6) +#100 X(.?){0,}Y X1234567Y (0,9)(7,8) +#101 X(.?){1,}Y X1234567Y (0,9)(7,8) +#102 X(.?){2,}Y X1234567Y (0,9)(7,8) +#103 X(.?){3,}Y X1234567Y (0,9)(7,8) +#104 X(.?){4,}Y X1234567Y (0,9)(7,8) +#105 X(.?){5,}Y X1234567Y (0,9)(7,8) +#106 X(.?){6,}Y X1234567Y (0,9)(7,8) +#107 X(.?){7,}Y X1234567Y (0,9)(7,8) +#108 X(.?){8,}Y X1234567Y (0,9)(8,8) +#110 X(.?){0,8}Y X1234567Y (0,9)(7,8) +#111 X(.?){1,8}Y X1234567Y (0,9)(7,8) +#112 X(.?){2,8}Y X1234567Y (0,9)(7,8) +#113 X(.?){3,8}Y X1234567Y (0,9)(7,8) +#114 X(.?){4,8}Y X1234567Y (0,9)(7,8) +#115 X(.?){5,8}Y X1234567Y (0,9)(7,8) +#116 X(.?){6,8}Y X1234567Y (0,9)(7,8) +#117 X(.?){7,8}Y X1234567Y (0,9)(7,8) +#118 X(.?){8,8}Y X1234567Y (0,9)(8,8) +#260 (a|ab|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) +#261 (a|ab|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) +#262 (a|ab|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) +#263 (a|ab|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) +#264 (a|ab|c|bcd){4,}(d*) ababcd NOMATCH +#265 (a|ab|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) +#266 (a|ab|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) +#267 (a|ab|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) +#268 (a|ab|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) +#269 (a|ab|c|bcd){4,10}(d*) ababcd NOMATCH +270 (a|ab|c|bcd)*(d*) ababcd (0,6)(0,2)(2,3)(3,6)(6,6) +271 (a|ab|c|bcd)+(d*) ababcd (0,6)(0,2)(2,3)(3,6)(6,6) diff -r 761793cce563 -r c2d36c3cf8ad progs/tests/totest.txt --- a/progs/tests/totest.txt Thu Jun 09 12:31:02 2016 +0100 +++ b/progs/tests/totest.txt Fri Jun 10 23:53:46 2016 +0100 @@ -1,79 +1,80 @@ -01 a+ xaax (1,3) +#01 a+ xaax (1,3) 03 (a?)((ab)?) ab (0,2)(0,0)(0,2)(0,2) -04 (a?)((ab)?)(b?) ab (0,2)(0,1)(1,1)(?,?)(1,2) +04 (a?)((ab)?)(b?) ab (0,2)(0,0)(0,2)(0,2)(2,2) 05 ((a?)((ab)?))(b?) ab (0,2)(0,2)(0,0)(0,2)(0,2)(2,2) -06 (a?)(((ab)?)(b?)) ab (0,2)(0,1)(1,2)(1,1)(?,?)(1,2) +06 (a?)(((ab)?)(b?)) ab (0,2)(0,1)(1,2)(1,1)(1,2) 07 (.?) x (0,1)(0,1) -08 (.?){1} x (0,1)(0,1) +#08 (.?){1} x (0,1)(0,1) 09 (.?)(.?) x (0,1)(0,1)(1,1) -10 (.?){2} x (0,1)(1,1) +#10 (.?){2} x (0,1)(1,1) 11 (.?)* x (0,1)(0,1) -12 (.?.?) xxx (0,2)(0,2) -13 (.?.?){1} xxx (0,2)(0,2) +#12 (.?.?) xxx (0,2)(0,2) +12 (.?.?.?) xxx (0,3)(0,3) +#13 (.?.?){1} xxx (0,2)(0,2) 14 (.?.?)(.?.?) xxx (0,3)(0,2)(2,3) -15 (.?.?){2} xxx (0,3)(2,3) +#15 (.?.?){2} xxx (0,3)(2,3) 16 (.?.?)(.?.?)(.?.?) xxx (0,3)(0,2)(2,3)(3,3) -17 (.?.?){3} xxx (0,3)(3,3) -18 (.?.?)* xxx (0,3)(2,3) -19 a?((ab)?)(b?) ab (0,2)(1,1)(?,?)(1,2) -20 (a?)((ab)?)b? ab (0,2)(0,1)(1,1)(?,?) -21 a?((ab)?)b? ab (0,2)(1,1)(?,?) -22 (a*){2} xxxxx (0,0)(0,0) +#17 (.?.?){3} xxx (0,3)(3,3) +18 (.?.?)* xxx (0,3)(0,2)(2,3) +19 a?((ab)?)(b?) ab (0,2)(0,2)(0,2)(2,2) +20 (a?)((ab)?)b? ab (0,2)(0,0)(0,2)(0,2) +21 a?((ab)?)b? ab (0,2)(0,2)(0,2) +#22 (a*){2} xxxxx (0,0)(0,0) 23 (ab?)(b?a) aba (0,3)(0,2)(2,3) 24 (a|ab)(ba|a) aba (0,3)(0,2)(2,3) -25 (a|ab|ba) aba (0,2)(0,2) +#25 (a|ab|ba) aba (0,2)(0,2) 26 (a|ab|ba)(a|ab|ba) aba (0,3)(0,2)(2,3) -27 (a|ab|ba)* aba (0,3)(2,3) -28 (aba|a*b) ababa (0,3)(0,3) +27 (a|ab|ba)* aba (0,3)(0,2)(2,3) +#28 (aba|a*b) ababa (0,3)(0,3) 29 (aba|a*b)(aba|a*b) ababa (0,5)(0,2)(2,5) -1029 (aba|a*b)(aba|a*b)(aba|a*b) ababa NOMATCH -30 (aba|a*b)* ababa (0,5)(2,5) -31 (aba|ab|a) ababa (0,3)(0,3) +#1029 (aba|a*b)(aba|a*b)(aba|a*b) ababa NOMATCH +30 (aba|a*b)* ababa (0,5)(0,2)(2,5) +#31 (aba|ab|a) ababa (0,3)(0,3) 32 (aba|ab|a)(aba|ab|a) ababa (0,5)(0,2)(2,5) 1032 (aba|ab|a)(aba|ab|a)(aba|ab|a) ababa (0,5)(0,2)(2,4)(4,5) -33 (aba|ab|a)* ababa (0,5)(2,5) -34 (a(b)?) aba (0,2)(0,2)(1,2) -35 (a(b)?)(a(b)?) aba (0,3)(0,2)(1,2)(2,3)(?,?) -36 (a(b)?)+ aba (0,3)(2,3)(?,?) +33 (aba|ab|a)* ababa (0,5)(0,2)(2,5) +#34 (a(b)?) aba (0,2)(0,2)(1,2) +35 (a(b)?)(a(b)?) aba (0,3)(0,2)(1,2)(2,3) +36 (a(b)?)+ aba (0,3)(0,2)(1,2)(2,3) 37 (.*)(.*) xx (0,2)(0,2)(2,2) 38 .*(.*) xx (0,2)(2,2) -39 (a.*z|b.*y) azbazby (0,5)(0,5) +#39 (a.*z|b.*y) azbazby (0,5)(0,5) 40 (a.*z|b.*y)(a.*z|b.*y) azbazby (0,7)(0,5)(5,7) -41 (a.*z|b.*y)* azbazby (0,7)(5,7) +41 (a.*z|b.*y)* azbazby (0,7)(0,5)(5,7) 42 (.|..)(.*) ab (0,2)(0,2)(2,2) -43 ((..)*(...)*) xxx (0,3)(0,3)(?,?)(0,3) -44 ((..)*(...)*)((..)*(...)*) xxx (0,3)(0,3)(?,?)(0,3)(3,3)(?,?)(?,?) -45 ((..)*(...)*)* xxx (0,3)(0,3)(?,?)(0,3) -83 (aa(b(b))?)+ aabbaa (0,6)(4,6)(?,?)(?,?) -84 (a(b)?)+ aba (0,3)(2,3)(?,?) -85 ([ab]+)([bc]+)([cd]*) abcd (0,4)(0,2)(2,3)(3,4) -90 ^(A([^B]*))?(B(.*))? Aa (0,2)(0,2)(1,2)(?,?)(?,?) -91 ^(A([^B]*))?(B(.*))? Bb (0,2)(?,?)(?,?)(0,2)(1,2) -110 (^){0,3} a (0,0)(0,0) -111 ($){0,3} a (0,0)(?,?) -112 (^){1,3} a (0,0)(0,0) -113 ($){1,3} a (1,1)(1,1) -200 ((s^)|(s)|(^)|($)|(^.))* searchme (0,1)(0,1)(?,?)(0,1)(?,?)(?,?)(?,?) -201 s(()|^)e searchme (0,2)(1,1)(1,1) -202 s(^|())e searchme (0,2)(1,1)(1,1) -203 s(^|())e searchme (0,2)(1,1)(1,1) -204 s()?e searchme (0,2)(1,1) -205 s(^)?e searchme (0,2)(?,?) -206 ((s)|(e)|(a))* searchme (0,3)(2,3)(?,?)(?,?)(2,3) -207 ((s)|(e)|())* searchme (0,2)(1,2)(?,?)(1,2)(?,?) -208 ((b*)|c(c*))* cbb (0,3)(1,3)(1,3)(?,?) -209 (yyy|(x?)){2,4} yyyyyy (0,6)(3,6)(?,?) -210 ($)|() xxx (0,0)(?,?)(0,0) -211 $()|^() ac\n (0,0)(?,?)(0,0) -212 ^()|$() ac\n (0,0)(0,0)(?,?) -213 ($)?(.) __ (0,1)(?,?)(0,1) -214 (.|()|())* c (0,1)(0,1)(?,?)(?,?) -215 ((a)|(b)){2,} ab (0,2)(1,2)(?,?)(1,2) -216 .()|((.)?) NULL (0,0)(?,?)(0,0)(?,?) -217 (.|$){2,} xx (0,2)(1,2) -218 (.|$){2,2} xx (0,2)(1,2) -219 (.){2,} xx (0,2)(1,2) -220 (a|())(b|())(c|()) abc (0,3)(0,1)(?,?)(1,2)(?,?)(2,3)(?,?) -220 ab()c|ab()c() abc (0,3)(2,2)(-1,-1)(-1,-1) -250 (b(c)|d(e))* bcde (0,4)(2,4)(-1,-1)(3,4) -251 (a(b)*)* aba (0,3)(2,3)(-1,-1) +43 ((..)*(...)*) xxx (0,3)(0,3)(0,3) +44 ((..)*(...)*)((..)*(...)*) xxx (0,3)(0,3)(0,3)(3,3) +45 ((..)*(...)*)* xxx (0,3)(0,3)(0,3) +83 (aa(b(b))?)+ aabbaa (0,6)(0,4)(2,4)(3,4)(4,6) +84 (a(b)?)+ aba (0,3)(0,2)(1,2)(2,3) +#85 ([ab]+)([bc]+)([cd]*) abcd (0,4)(0,2)(2,3)(3,4) +#90 ^(A([^B]*))?(B(.*))? Aa (0,2)(0,2)(1,2)(?,?)(?,?) +#91 ^(A([^B]*))?(B(.*))? Bb (0,2)(?,?)(?,?)(0,2)(1,2) +#110 (^){0,3} a (0,0)(0,0) +#111 ($){0,3} a (0,0)(?,?) +#112 (^){1,3} a (0,0)(0,0) +#113 ($){1,3} a (1,1)(1,1) +#200 ((s^)|(s)|(^)|($)|(^.))* searchme (0,1)(0,1)(?,?)(0,1)(?,?)(?,?)(?,?) +#201 s(()|^)e searchme (0,2)(1,1)(1,1) +#202 s(^|())e searchme (0,2)(1,1)(1,1) +#203 s(^|())e searchme (0,2)(1,1)(1,1) +#204 s()?e searchme (0,2)(1,1) +#205 s(^)?e searchme (0,2)(?,?) +#206 ((s)|(e)|(a))* searchme (0,3)(2,3)(?,?)(?,?)(2,3) +#207 ((s)|(e)|())* searchme (0,2)(1,2)(?,?)(1,2)(?,?) +208 ((b*)|c(c*))* cbb (0,3)(0,1)(1,1)(1,3)(1,3) +#209 (yyy|(x?)){2,4} yyyyyy (0,6)(3,6)(?,?) +#210 ($)|() xxx (0,0)(?,?)(0,0) +#211 $()|^() ac\n (0,0)(?,?)(0,0) +#212 ^()|$() ac\n (0,0)(0,0)(?,?) +#213 ($)?(.) __ (0,1)(?,?)(0,1) +214 (.|()|())* c (0,1)(0,1) +#215 ((a)|(b)){2,} ab (0,2)(1,2)(?,?)(1,2) +#216 .()|((.)?) NULL (0,0)(?,?)(0,0)(?,?) +#217 (.|$){2,} xx (0,2)(1,2) +#218 (.|$){2,2} xx (0,2)(1,2) +#219 (.){2,} xx (0,2)(1,2) +220 (a|())(b|())(c|()) abc (0,3)(0,1)(1,2)(2,3) +##220 ab()c|ab()c() abc (0,3)(2,2)(-1,-1)(-1,-1) +250 (b(c)|d(e))* bcde (0,4)(0,2)(1,2)(2,4)(3,4) +251 (a(b)*)* aba (0,3)(0,2)(1,2)(2,3)