--- 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)))
--- 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)
--- 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)
--- 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)
--- 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)
--- 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)
--- 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)