|
0
|
1 |
import Element.elem
|
|
|
2 |
import RexpRelated._
|
|
|
3 |
import RexpRelated.Rexp._
|
|
|
4 |
import Partial._
|
|
|
5 |
import BRexp._
|
|
|
6 |
import scala.collection.mutable.ListBuffer
|
|
|
7 |
object Spiral{
|
|
|
8 |
|
|
|
9 |
val space = elem(" ")
|
|
|
10 |
val corner = elem("+")
|
|
|
11 |
|
|
|
12 |
def spiral(nEdges: Int, direction: Int): Element = {
|
|
|
13 |
if(nEdges == 1)
|
|
|
14 |
elem("+")
|
|
|
15 |
else {
|
|
|
16 |
val sp = spiral(nEdges - 1, (direction + 3) % 4)
|
|
|
17 |
def verticalBar = elem('|', 1, sp.height)
|
|
|
18 |
def horizontalBar = elem('-', sp.width, 1)
|
|
|
19 |
if(direction == 0)
|
|
|
20 |
(corner beside horizontalBar) above sp//(sp beside space)
|
|
|
21 |
else if (direction == 1)
|
|
|
22 |
sp beside (corner above verticalBar)
|
|
|
23 |
else if (direction == 2)
|
|
|
24 |
(space beside sp) above (horizontalBar beside corner)
|
|
|
25 |
else
|
|
|
26 |
(verticalBar above corner) beside (space above sp)
|
|
|
27 |
}
|
|
|
28 |
}
|
|
|
29 |
val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c')
|
|
|
30 |
def bregx_tree(r: BRexp): Element = regx_tree(berase(r))
|
|
|
31 |
def regx_tree(r: Rexp): Element = aregx_tree(internalise(r))
|
|
5
|
32 |
def annotated_tree(r: ARexp): Element = {
|
|
|
33 |
r match {
|
|
|
34 |
case ACHAR(bs, d) => {
|
|
|
35 |
//val Some(d) = alphabet.find(f)
|
|
|
36 |
d match {
|
|
|
37 |
case '\n' => elem("\\n")
|
|
|
38 |
case '\t' => elem("\\t")
|
|
|
39 |
case ' ' => elem("space")
|
|
7
|
40 |
case d => if(bs.isEmpty) elem(d.toString) else elem(d.toString++" ") beside elem(bs.toString)
|
|
5
|
41 |
}
|
|
|
42 |
}
|
|
|
43 |
case AONE(bs) => {
|
|
7
|
44 |
if(bs.isEmpty) elem("ONE") else elem("ONE ") beside elem(bs.toString)
|
|
5
|
45 |
}
|
|
|
46 |
case AZERO => {
|
|
7
|
47 |
elem("ZERO")
|
|
5
|
48 |
}
|
|
|
49 |
case ASEQ(bs, r1, r2) => {
|
|
7
|
50 |
annotated_binary_print("SEQ", r1, r2, bs)
|
|
5
|
51 |
}
|
|
|
52 |
case AALTS(bs, rs) => {
|
|
|
53 |
//elem("Awaiting completion")
|
|
7
|
54 |
annotated_list_print("ALT", rs, bs)
|
|
5
|
55 |
}
|
|
|
56 |
case ASTAR(bs, r) => {
|
|
7
|
57 |
annotated_list_print("STA", List(r), bs)
|
|
5
|
58 |
}
|
|
|
59 |
}
|
|
|
60 |
}
|
|
0
|
61 |
def aregx_tree(r: ARexp): Element = {
|
|
|
62 |
r match {
|
|
|
63 |
case ACHAR(bs, d) => {
|
|
|
64 |
//val Some(d) = alphabet.find(f)
|
|
|
65 |
d match {
|
|
|
66 |
case '\n' => elem("\\n")
|
|
|
67 |
case '\t' => elem("\\t")
|
|
|
68 |
case ' ' => elem("space")
|
|
|
69 |
case d => elem(d.toString)
|
|
|
70 |
}
|
|
|
71 |
}
|
|
|
72 |
case AONE(bs) => {
|
|
|
73 |
elem("ONE")
|
|
|
74 |
}
|
|
|
75 |
case AZERO => {
|
|
|
76 |
elem("ZERO")
|
|
|
77 |
}
|
|
|
78 |
case ASEQ(bs, r1, r2) => {
|
|
|
79 |
binary_print("SEQ", r1, r2)
|
|
|
80 |
}
|
|
|
81 |
case AALTS(bs, rs) => {
|
|
|
82 |
//elem("Awaiting completion")
|
|
|
83 |
list_print("ALT", rs)
|
|
|
84 |
}
|
|
|
85 |
case ASTAR(bs, r) => {
|
|
|
86 |
list_print("STA", List(r))
|
|
|
87 |
}
|
|
|
88 |
}
|
|
|
89 |
}
|
|
|
90 |
val port = elem(" └-")
|
|
|
91 |
def list_print(name: String, rs: List[ARexp]): Element = {
|
|
|
92 |
rs match {
|
|
|
93 |
case r::Nil => {
|
|
|
94 |
val pref = aregx_tree(r)
|
|
|
95 |
val head = elem(name)
|
|
|
96 |
(head left_align (port up_align pref) )
|
|
|
97 |
}
|
|
|
98 |
case r2::r1::Nil => {
|
|
|
99 |
binary_print(name, r2, r1)
|
|
|
100 |
}
|
|
|
101 |
case r::rs1 => {
|
|
|
102 |
val pref = aregx_tree(r)
|
|
|
103 |
val head = elem(name)
|
|
|
104 |
if (pref.height > 1){
|
|
|
105 |
val link = elem('|', 1, pref.height - 1)
|
|
|
106 |
(head left_align ((port above link) beside pref)) left_align tail_print(rs1)
|
|
|
107 |
}
|
|
|
108 |
else{
|
|
|
109 |
(head left_align (port beside pref) ) left_align tail_print(rs1)
|
|
|
110 |
}
|
|
|
111 |
}
|
|
|
112 |
}
|
|
|
113 |
}
|
|
7
|
114 |
def annotated_list_print(name: String, rs: List[ARexp], bs: List[Bit]): Element = {
|
|
|
115 |
rs match {
|
|
|
116 |
case r::Nil => {
|
|
|
117 |
val pref = annotated_tree(r)
|
|
|
118 |
val head = if(bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
|
|
|
119 |
(head left_align (port up_align pref) )
|
|
|
120 |
}
|
|
|
121 |
case r2::r1::Nil => {
|
|
|
122 |
annotated_binary_print(name, r2, r1, bs)
|
|
|
123 |
}
|
|
|
124 |
case r::rs1 => {
|
|
|
125 |
val pref = annotated_tree(r)
|
|
|
126 |
val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
|
|
|
127 |
if (pref.height > 1){
|
|
|
128 |
val link = elem('|', 1, pref.height - 1)
|
|
|
129 |
(head left_align ((port above link) beside pref)) left_align annotated_tail_print(rs1)
|
|
|
130 |
}
|
|
|
131 |
else{
|
|
|
132 |
(head left_align (port beside pref) ) left_align annotated_tail_print(rs1)
|
|
|
133 |
}
|
|
|
134 |
}
|
|
|
135 |
}
|
|
|
136 |
}
|
|
|
137 |
|
|
|
138 |
def annotated_tail_print(rs: List[ARexp]): Element = {
|
|
|
139 |
rs match {
|
|
|
140 |
case r2::r1::Nil => {
|
|
|
141 |
val pref = annotated_tree(r2)
|
|
|
142 |
val suff = annotated_tree(r1)
|
|
|
143 |
if (pref.height > 1){
|
|
|
144 |
val link = elem('|', 1, pref.height - 1)
|
|
|
145 |
((port above link) beside pref) left_align (port up_align suff)
|
|
|
146 |
}
|
|
|
147 |
else{
|
|
|
148 |
(port beside pref) left_align (port up_align suff)
|
|
|
149 |
}
|
|
|
150 |
}
|
|
|
151 |
case r2::rs1 => {
|
|
|
152 |
val pref = annotated_tree(r2)
|
|
|
153 |
|
|
|
154 |
if (pref.height > 1){
|
|
|
155 |
val link = elem('|', 1, pref.height - 1)
|
|
|
156 |
((port above link) beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1) )
|
|
|
157 |
}
|
|
|
158 |
else{
|
|
|
159 |
(port beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1))
|
|
|
160 |
}
|
|
|
161 |
//pref left_align tail_print(rs1)
|
|
|
162 |
}
|
|
|
163 |
}
|
|
|
164 |
}
|
|
|
165 |
|
|
0
|
166 |
def tail_print(rs: List[ARexp]): Element = {
|
|
|
167 |
rs match {
|
|
|
168 |
case r2::r1::Nil => {
|
|
|
169 |
val pref = aregx_tree(r2)
|
|
|
170 |
val suff = aregx_tree(r1)
|
|
|
171 |
if (pref.height > 1){
|
|
|
172 |
val link = elem('|', 1, pref.height - 1)
|
|
|
173 |
((port above link) beside pref) left_align (port up_align suff)
|
|
|
174 |
}
|
|
|
175 |
else{
|
|
|
176 |
(port beside pref) left_align (port up_align suff)
|
|
|
177 |
}
|
|
|
178 |
}
|
|
|
179 |
case r2::rs1 => {
|
|
|
180 |
val pref = aregx_tree(r2)
|
|
|
181 |
|
|
|
182 |
if (pref.height > 1){
|
|
|
183 |
val link = elem('|', 1, pref.height - 1)
|
|
|
184 |
((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) )
|
|
|
185 |
}
|
|
|
186 |
else{
|
|
|
187 |
(port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1))
|
|
|
188 |
}
|
|
|
189 |
//pref left_align tail_print(rs1)
|
|
|
190 |
}
|
|
|
191 |
}
|
|
|
192 |
}
|
|
|
193 |
|
|
|
194 |
def binary_print(name: String, r1: ARexp, r2: ARexp): Element = {
|
|
|
195 |
val pref = aregx_tree(r1)
|
|
|
196 |
val suff = aregx_tree(r2)
|
|
7
|
197 |
val head = elem(name)
|
|
0
|
198 |
if (pref.height > 1){
|
|
|
199 |
val link = elem('|', 1, pref.height - 1)
|
|
|
200 |
(head left_align ((port above link) beside pref) ) left_align (port up_align suff)
|
|
|
201 |
}
|
|
|
202 |
else{
|
|
|
203 |
(head left_align (port beside pref) ) left_align (port up_align suff)
|
|
|
204 |
}
|
|
|
205 |
}
|
|
7
|
206 |
def annotated_binary_print(name: String, r1: ARexp, r2: ARexp, bs: List[Bit]): Element = {
|
|
|
207 |
val pref = annotated_tree(r1)
|
|
|
208 |
val suff = annotated_tree(r2)
|
|
|
209 |
val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
|
|
|
210 |
if (pref.height > 1){
|
|
|
211 |
val link = elem('|', 1, pref.height - 1)
|
|
|
212 |
(head left_align ((port above link) beside pref) ) left_align (port up_align suff)
|
|
|
213 |
}
|
|
|
214 |
else{
|
|
|
215 |
(head left_align (port beside pref) ) left_align (port up_align suff)
|
|
|
216 |
}
|
|
|
217 |
}
|
|
|
218 |
|
|
0
|
219 |
val arr_of_size = ListBuffer.empty[Int]
|
|
2
|
220 |
|
|
0
|
221 |
def pC(r: Rexp): Set[Rexp] = {//PD's companion
|
|
|
222 |
r match {
|
|
|
223 |
case SEQ(r1, r2) => pC(r2)
|
|
|
224 |
case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet
|
|
|
225 |
case CHAR(c) => Set(r)
|
|
|
226 |
case r => Set()
|
|
|
227 |
}
|
|
|
228 |
}
|
|
|
229 |
def illustration(r: Rexp, s: String){
|
|
|
230 |
var i_like_imperative_style = internalise(r)
|
|
|
231 |
val all_chars = s.toList
|
|
|
232 |
for (i <- 0 to s.length - 1){
|
|
|
233 |
val der_res = bder(all_chars(i), i_like_imperative_style)
|
|
|
234 |
val simp_res = bsimp(der_res)
|
|
|
235 |
println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.")
|
|
|
236 |
println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res))
|
|
|
237 |
//println(asize(i_like_imperative_style), asize(der_res), asize(simp_res))
|
|
|
238 |
arr_of_size += asize(i_like_imperative_style)
|
|
|
239 |
//println(asize(simp_res), asize(simp_res) / arr_of_size(0) )
|
|
|
240 |
i_like_imperative_style = simp_res
|
|
|
241 |
}
|
|
|
242 |
arr_of_size += asize(i_like_imperative_style)
|
|
|
243 |
}
|
|
|
244 |
val ran = scala.util.Random
|
|
|
245 |
var alphabet_size = 3
|
|
|
246 |
def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = {
|
|
|
247 |
if(depth == 1){
|
|
|
248 |
((ran.nextInt(4) + 97).toChar).toString
|
|
|
249 |
}
|
|
|
250 |
else if(star){
|
|
|
251 |
STAR(balanced_seq_star_gen(depth - 1, false))
|
|
|
252 |
}
|
|
|
253 |
else{
|
|
|
254 |
SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true))
|
|
|
255 |
}
|
|
|
256 |
}
|
|
|
257 |
def max(i: Int, j: Int): Int = {
|
|
|
258 |
if(i > j)
|
|
|
259 |
i
|
|
|
260 |
else
|
|
|
261 |
j
|
|
|
262 |
}
|
|
|
263 |
def random_struct_gen(depth:Int): Rexp = {
|
|
|
264 |
val dice = ran.nextInt(3)
|
|
|
265 |
val dice2 = ran.nextInt(3)
|
|
|
266 |
(dice, depth) match {
|
|
|
267 |
case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
|
|
|
268 |
case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2)))
|
|
|
269 |
case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2)))
|
|
|
270 |
case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) )
|
|
|
271 |
}
|
|
|
272 |
}
|
|
|
273 |
def balanced_struct_gen(depth: Int): Rexp = {
|
|
|
274 |
val dice = ran.nextInt(3)
|
|
|
275 |
(dice, depth) match {
|
|
|
276 |
case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
|
|
|
277 |
case (0, i) => STAR(random_struct_gen(depth - 1))
|
|
|
278 |
case (1, i) => SEQ(random_struct_gen(depth - 1), random_struct_gen(depth - 1))
|
|
|
279 |
case (2, i) => ALTS( List(random_struct_gen(depth - 1), random_struct_gen(depth - 1) ) )
|
|
|
280 |
}
|
|
|
281 |
}
|
|
6
|
282 |
def random_pool(n: Int, d: Int) : Stream[Rexp] = n match {
|
|
|
283 |
case 0 => (for (i <- 1 to 10) yield balanced_struct_gen(d)).toStream
|
|
|
284 |
case n => {
|
|
|
285 |
val rs = random_pool(n - 1, d)
|
|
|
286 |
rs #:::
|
|
|
287 |
(for (i <- (1 to 10).toStream) yield balanced_struct_gen(d)) #:::
|
|
|
288 |
(for (i <- (1 to 10).toStream) yield random_struct_gen(d))
|
|
|
289 |
}
|
|
|
290 |
}
|
|
|
291 |
|
|
0
|
292 |
def rd_string_gen(alp_size: Int, len: Int): String = {
|
|
|
293 |
if( len > 0)
|
|
|
294 |
((ran.nextInt(alp_size) + 97).toChar).toString + rd_string_gen(alp_size, len - 1)
|
|
|
295 |
else
|
|
|
296 |
((ran.nextInt(alp_size) + 97).toChar).toString
|
|
|
297 |
}
|
|
|
298 |
def plot(b: List[Int]){
|
|
|
299 |
println(b(0),b.max)
|
|
|
300 |
|
|
|
301 |
}
|
|
|
302 |
def dep_exp(depth: List[Int]){
|
|
|
303 |
for(i <- depth){
|
|
|
304 |
arr_of_size.clear()
|
|
|
305 |
val s = rd_string_gen(alphabet_size, (i-8)*(i-8)+10)
|
|
|
306 |
val r = random_struct_gen(i)
|
|
|
307 |
println("depth: "+i)
|
|
|
308 |
illustration(r, s) //"abcabadaaadcabdbabcdaadbabbcbbdabdabbcbdbabdbcdb")
|
|
|
309 |
//println("depth: " + i + " general stats:"+ arr_of_size(0), arr_of_size.max, arr_of_size.max/arr_of_size(0))
|
|
|
310 |
//println("x y label alignment")
|
|
|
311 |
/*for(i <- 0 to s.length - 1){
|
|
|
312 |
if(s(i) == '\n')
|
|
|
313 |
println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
|
|
|
314 |
else if(s(i) == ' ')
|
|
|
315 |
println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
|
|
|
316 |
else
|
|
|
317 |
println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
|
|
|
318 |
}*/
|
|
|
319 |
//println(s.length + " " + arr_of_size(s.length) + " ]" + " -140")
|
|
|
320 |
}
|
|
|
321 |
}
|
|
|
322 |
def case_study(ss: List[String], r: Rexp){
|
|
|
323 |
for(s <- ss){
|
|
|
324 |
arr_of_size.clear()
|
|
|
325 |
illustration(r, s)
|
|
|
326 |
println("x y label alignment")
|
|
|
327 |
for(i <- 0 to s.length - 1){
|
|
|
328 |
if(s(i) == '\n')
|
|
|
329 |
println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
|
|
|
330 |
else if(s(i) == ' ')
|
|
|
331 |
println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
|
|
|
332 |
else
|
|
|
333 |
println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
|
|
|
334 |
}
|
|
|
335 |
}
|
|
|
336 |
}
|
|
|
337 |
def star_gen(dp: Int): Rexp = {
|
|
|
338 |
if(dp > 0)
|
|
|
339 |
STAR(star_gen(dp - 1))
|
|
|
340 |
else
|
|
|
341 |
"a"
|
|
|
342 |
}
|
|
|
343 |
def strs_gen(len: Int, num: Int): List[String] = {
|
|
|
344 |
if(num > 0){
|
|
|
345 |
rd_string_gen(3, len)::strs_gen(len, num - 1)
|
|
|
346 |
}
|
|
|
347 |
else{
|
|
|
348 |
Nil
|
|
|
349 |
}
|
|
|
350 |
}
|
|
|
351 |
def regx_print(r: Rexp): String = {
|
|
|
352 |
r match {
|
|
|
353 |
case ZERO =>
|
|
|
354 |
"ZERO"
|
|
|
355 |
case CHAR(c) => {
|
|
|
356 |
//val Some(c) = alphabet.find(f)
|
|
|
357 |
"\"" + c.toString + "\""
|
|
|
358 |
}
|
|
|
359 |
case ONE => {
|
|
|
360 |
"ONE"
|
|
|
361 |
}
|
|
|
362 |
case ALTS(rs) => {
|
|
|
363 |
"ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))"
|
|
|
364 |
}
|
|
|
365 |
case SEQ(r1, r2) => {
|
|
|
366 |
"SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")"
|
|
|
367 |
}
|
|
|
368 |
case STAR(r) => {
|
|
|
369 |
"STAR(" + regx_print(r) + ")"
|
|
|
370 |
}
|
|
|
371 |
}
|
|
|
372 |
}
|
|
|
373 |
val mkst = "abcdefghijklmnopqrstuvwxyz"
|
|
|
374 |
def weak_sub_check(r: Rexp, s: String, i: Int, f: (List[Rexp], Set[Rexp]) => Boolean){
|
|
|
375 |
//we first compute pders over the set of all strings on the alphabet
|
|
|
376 |
val pd = pderas(Set(r), i + 4)
|
|
|
377 |
//then "b-internalise" the regular expression into a brexp(this is essentially
|
|
|
378 |
//attaching a bit Z to every alts to signify that they come from the original regular expression)
|
|
|
379 |
var old = brternalise(r)
|
|
|
380 |
//this is for comparison between normal simp and the weakened version of simp
|
|
|
381 |
//normal simp will be performed on syncold
|
|
|
382 |
//weakend simp will be performed on old
|
|
5
|
383 |
var syncold = internalise(r)
|
|
0
|
384 |
val all_chars = s.toList
|
|
|
385 |
for (i <- 0 to s.length - 1){
|
|
5
|
386 |
val syncder_res = bder(all_chars(i), syncold)
|
|
|
387 |
val syncsimp_res = super_bsimp(syncder_res)
|
|
0
|
388 |
//see brder for detailed explanation
|
|
|
389 |
//just changes bit Z to S when deriving an ALTS,
|
|
|
390 |
//signifying that the structure has been "touched" and
|
|
|
391 |
//therefore able to be spilled in the bspill function
|
|
|
392 |
val der_res = brder(all_chars(i), old)
|
|
|
393 |
val simp_res = br_simp(der_res)
|
|
|
394 |
val anatomy = bspill(simp_res)
|
|
|
395 |
//track if the number of regular expressions exceeds those in the PD set(remember PD means the pders over A*)
|
|
5
|
396 |
if(f(List(berase(simp_res)), pd) == false ){
|
|
|
397 |
println(size(erase(syncsimp_res)))
|
|
0
|
398 |
println(size(berase(simp_res)))
|
|
3
|
399 |
println(bregx_tree(simp_res))
|
|
5
|
400 |
println(s)
|
|
|
401 |
println(i)
|
|
|
402 |
println(r)
|
|
0
|
403 |
println(anatomy.map(size).sum)
|
|
|
404 |
println(pd.map(size).sum)
|
|
|
405 |
}
|
|
|
406 |
old = simp_res
|
|
|
407 |
syncold = syncsimp_res
|
|
|
408 |
}
|
|
|
409 |
}
|
|
|
410 |
def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = {
|
|
|
411 |
val aset = anatomy.toSet
|
|
|
412 |
if(aset subsetOf pd){
|
|
|
413 |
true
|
|
|
414 |
}
|
|
|
415 |
else{
|
|
|
416 |
println("inclusion not true")
|
|
|
417 |
false
|
|
|
418 |
}
|
|
|
419 |
}
|
|
|
420 |
def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true}
|
|
5
|
421 |
def size_expansion_rate(r: List[Rexp], pd: Set[Rexp]): Boolean = if(size(r(0)) > (pd.map(size).sum) * 3 ) { false }else {true}
|
|
4
|
422 |
def ders_simp(r: ARexp, s: List[Char]): ARexp = {
|
|
|
423 |
s match {
|
|
|
424 |
case Nil => r
|
|
|
425 |
case c::cs => ders_simp(bsimp(bder(c, r)), cs)
|
|
|
426 |
}
|
|
|
427 |
}
|
|
5
|
428 |
val big_panda = STAR(STAR(STAR(ALTS(List(ALTS(List(CHAR('c'), CHAR('b'))), SEQ(CHAR('c'),CHAR('c')))))))
|
|
|
429 |
val str_panda = "ccccb"
|
|
0
|
430 |
def check_all(){
|
|
5
|
431 |
|
|
|
432 |
weak_sub_check(big_panda, str_panda, 6, size_expansion_rate)
|
|
|
433 |
|
|
0
|
434 |
}
|
|
5
|
435 |
//simplified regex size 291, so called pd_simp size 70 (did not do simplification to terms in the PD set)
|
|
10
|
436 |
def pushbits(r: ARexp): ARexp = r match {
|
|
|
437 |
case AALTS(bs, rs) => AALTS(Nil, rs.map(fuse(bs, _)))
|
|
|
438 |
case r => r
|
|
|
439 |
}
|
|
4
|
440 |
def correctness_proof_convenient_path(){
|
|
|
441 |
for(i <- 1 to 1)
|
|
|
442 |
{
|
|
10
|
443 |
val s = "baa"//rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
|
|
|
444 |
val r = ASTAR(List(),ASEQ(List(),AALTS(List(),List(ACHAR(List(Z),'c'), ACHAR(List(S),'b'))),ASEQ(List(),ASTAR(List(),ACHAR(List(),'a')),AALTS(List(),List(ACHAR(List(Z),'a'), ACHAR(List(S),'a'))))))//internalise(random_struct_gen(4))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)
|
|
4
|
445 |
for(j <- 0 to s.length - 1){
|
|
|
446 |
val ss = s.slice(0, j+ 1)
|
|
|
447 |
val nangao = ders_simp(r, ss.toList)
|
|
|
448 |
val easy = bsimp(bders(ss.toList, r))
|
|
10
|
449 |
if(!(nangao == easy || pushbits(nangao) == (easy))){
|
|
4
|
450 |
println(j)
|
|
10
|
451 |
println("not equal")
|
|
5
|
452 |
println("string")
|
|
4
|
453 |
println(ss)
|
|
5
|
454 |
println("original regex")
|
|
10
|
455 |
println(annotated_tree(r))
|
|
5
|
456 |
println("regex after ders simp")
|
|
10
|
457 |
println(annotated_tree(nangao))
|
|
5
|
458 |
println("regex after ders")
|
|
8
|
459 |
println(annotated_tree(bders(ss.toList, r)))//flats' fuse when opening up AALTS causes the difference
|
|
5
|
460 |
println("regex after ders and then a single simp")
|
|
7
|
461 |
println(annotated_tree(easy))
|
|
4
|
462 |
}
|
|
|
463 |
}
|
|
|
464 |
}
|
|
|
465 |
}
|
|
7
|
466 |
def radical_correctness(){
|
|
|
467 |
enum(3, "abc").map(tests_blexer_simp(strs(3, "abc"))).toSet
|
|
|
468 |
random_pool(1, 5).map(tests_blexer_simp(strs(5, "abc"))).toSet
|
|
|
469 |
}
|
|
0
|
470 |
def main(args: Array[String]) {
|
|
4
|
471 |
//check_all()
|
|
7
|
472 |
//radical_correctness()
|
|
|
473 |
correctness_proof_convenient_path()
|
|
0
|
474 |
}
|
|
|
475 |
}
|
|
|
476 |
|