135 |
135 |
136 def char_list(len: Int): Generator[List[Char]] = { |
136 def char_list(len: Int): Generator[List[Char]] = { |
137 if(len <= 0) single(Nil) |
137 if(len <= 0) single(Nil) |
138 else{ |
138 else{ |
139 for { |
139 for { |
140 c <- chars |
140 c <- chars_range('a', 'd') |
141 tail <- char_list(len - 1) |
141 tail <- char_list(len - 1) |
142 } yield c :: tail |
142 } yield c :: tail |
143 } |
143 } |
144 } |
144 } |
145 |
145 |
146 def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString |
146 def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString |
|
147 |
|
148 def sampleString(r: Rexp) : List[String] = r match { |
|
149 case STAR(r) => stringsFromRexp(r).flatMap(s => List("", s, s ++ s))//only generate 0, 1, 2 reptitions |
|
150 case SEQ(r1, r2) => stringsFromRexp(r1).flatMap(s1 => stringsFromRexp(r2).map(s2 => s1 ++ s2) ) |
|
151 case ALTS(r1, r2) => throw new Error(s" Rexp ${r} not expected: all alternatives are supposed to have been opened up") |
|
152 case ONE => "" :: Nil |
|
153 case ZERO => Nil |
|
154 case CHAR(c) => c.toString :: Nil |
|
155 |
|
156 } |
|
157 |
|
158 def stringsFromRexp(r: Rexp) : List[String] = |
|
159 breakIntoTerms(r).flatMap(r => sampleString(r)) |
147 |
160 |
148 |
161 |
149 // (simple) binary trees |
162 // (simple) binary trees |
150 trait Tree[T] |
163 trait Tree[T] |
151 case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T] |
164 case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T] |
921 // test(rexp(10), 1000) { _ => true } |
933 // test(rexp(10), 1000) { _ => true } |
922 // println("XXX generates regexes and tests a valid predicate") |
934 // println("XXX generates regexes and tests a valid predicate") |
923 // test(rexp(10), 1000) { r => height(r) <= size(r) } |
935 // test(rexp(10), 1000) { r => height(r) <= size(r) } |
924 // println("XXX faulty test") |
936 // println("XXX faulty test") |
925 // test(rexp(10), 100) { r => height(r) <= size_faulty(r) } |
937 // test(rexp(10), 100) { r => height(r) <= size_faulty(r) } |
926 println("testing strongbsimp against bsimp") |
938 |
927 test2(rexp(10), strings(2), 100) { (r : Rexp, s: String) => |
939 |
928 (simpBlexer(r, s) == strongBlexer(r, s)) |
940 /* For inspection of counterexamples should they arise*/ |
929 } |
941 // println("testing strongbsimp against bsimp") |
930 |
942 // val r = SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))), |
|
943 // SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))), |
|
944 // STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))), |
|
945 // SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE)) |
|
946 |
|
947 // val ss = stringsFromRexp(r) |
|
948 // val boolList = ss.map(s => { |
|
949 // val simpVal = simpBlexer(r, s) |
|
950 // val strongVal = strongBlexer(r, s) |
|
951 // println(simpVal) |
|
952 // println(strongVal) |
|
953 // (simpVal == strongVal) && (simpVal != None) |
|
954 // }) |
|
955 // println(boolList) |
|
956 // println(boolList.exists(b => b == false)) |
|
957 |
|
958 |
|
959 test(rexp(9), 100000) { (r: Rexp) => |
|
960 val ss = stringsFromRexp(r) |
|
961 val boolList = ss.map(s => { |
|
962 val simpVal = simpBlexer(r, s) |
|
963 val strongVal = strongBlexer(r, s) |
|
964 // println(simpVal) |
|
965 // println(strongVal) |
|
966 (simpVal == strongVal) && (simpVal != None) |
|
967 }) |
|
968 !boolList.exists(b => b == false) |
|
969 } |
|
970 |
|
971 |
931 } |
972 } |
932 // small() |
973 // small() |
933 generator_test() |
974 generator_test() |
|
975 |
|
976 1 |
|
977 |
|
978 SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))), |
|
979 SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))), |
|
980 STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))), |
|
981 SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE)) |
|
982 |
|
983 |
|
984 // Sequ(Sequ(Sequ(Empty,Chr(b)),Stars(List(Chr(b), Chr(b)))),Sequ(Right(Stars(List(Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty)), Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty))))),Empty)) |
|
985 // Sequ(Sequ(Sequ(Empty,Chr(b)),Stars(List(Chr(b), Chr(b)))),Sequ(Right(Stars(List(Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty)), Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty))))),Empty)) |