19 case object ZERO extends Rexp |
19 case object ZERO extends Rexp |
20 case object ONE extends Rexp |
20 case object ONE extends Rexp |
21 case object ANYCHAR extends Rexp |
21 case object ANYCHAR extends Rexp |
22 case class CHAR(c: Char) extends Rexp |
22 case class CHAR(c: Char) extends Rexp |
23 case class ALTS(r1: Rexp, r2: Rexp) extends Rexp |
23 case class ALTS(r1: Rexp, r2: Rexp) extends Rexp |
|
24 case class ALTSS(rs: List[Rexp]) extends Rexp |
24 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
25 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
25 case class STAR(r: Rexp) extends Rexp |
26 case class STAR(r: Rexp) extends Rexp |
26 case class RECD(x: String, r: Rexp) extends Rexp |
27 case class RECD(x: String, r: Rexp) extends Rexp |
27 case class NTIMES(n: Int, r: Rexp) extends Rexp |
28 case class NTIMES(n: Int, r: Rexp) extends Rexp |
28 case class OPTIONAL(r: Rexp) extends Rexp |
29 case class OPTIONAL(r: Rexp) extends Rexp |
268 case ZERO => false |
269 case ZERO => false |
269 case ONE => true |
270 case ONE => true |
270 case CHAR(_) => false |
271 case CHAR(_) => false |
271 case ANYCHAR => false |
272 case ANYCHAR => false |
272 case ALTS(r1, r2) => nullable(r1) || nullable(r2) |
273 case ALTS(r1, r2) => nullable(r1) || nullable(r2) |
|
274 case ALTSS(rs) => rs.exists(nullable) |
273 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
275 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
274 case STAR(_) => true |
276 case STAR(_) => true |
275 case RECD(_, r1) => nullable(r1) |
277 case RECD(_, r1) => nullable(r1) |
276 case NTIMES(n, r) => if (n == 0) true else nullable(r) |
278 case NTIMES(n, r) => if (n == 0) true else nullable(r) |
277 case OPTIONAL(r) => true |
279 case OPTIONAL(r) => true |
282 case ZERO => ZERO |
284 case ZERO => ZERO |
283 case ONE => ZERO |
285 case ONE => ZERO |
284 case CHAR(d) => if (c == d) ONE else ZERO |
286 case CHAR(d) => if (c == d) ONE else ZERO |
285 case ANYCHAR => ONE |
287 case ANYCHAR => ONE |
286 case ALTS(r1, r2) => ALTS(der(c, r1), der(c, r2)) |
288 case ALTS(r1, r2) => ALTS(der(c, r1), der(c, r2)) |
|
289 case ALTSS(rs) => ALTSS(rs.map(der(c, _))) |
287 case SEQ(r1, r2) => |
290 case SEQ(r1, r2) => |
288 if (nullable(r1)) ALTS(SEQ(der(c, r1), r2), der(c, r2)) |
291 if (nullable(r1)) ALTS(SEQ(der(c, r1), r2), der(c, r2)) |
289 else SEQ(der(c, r1), r2) |
292 else SEQ(der(c, r1), r2) |
290 case STAR(r) => SEQ(der(c, r), STAR(r)) |
293 case STAR(r) => SEQ(der(c, r), STAR(r)) |
291 case RECD(_, r1) => der(c, r1) |
294 case RECD(_, r1) => der(c, r1) |
292 case NTIMES(n, r) => if(n > 0) SEQ(der(c, r), NTIMES(n - 1, r)) else ZERO |
295 case NTIMES(n, r) => if(n > 0) SEQ(der(c, r), NTIMES(n - 1, r)) else ZERO |
293 case OPTIONAL(r) => der(c, r) |
296 case OPTIONAL(r) => der(c, r) |
294 case NOT(r) => NOT(der(c, r)) |
297 case NOT(r) => NOT(der(c, r)) |
295 } |
298 } |
|
299 |
|
300 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
|
301 case Nil => r |
|
302 case c :: cs => ders(cs, der(c, r)) |
|
303 } |
|
304 |
|
305 def ders_simp(s: List[Char], r: Rexp) : Rexp = s match { |
|
306 case Nil => simp(r) |
|
307 case c :: cs => ders_simp(cs, simp(der(c, r))) |
|
308 } |
|
309 |
|
310 |
|
311 def simp2(r: Rexp) : Rexp = r match { |
|
312 case SEQ(r1, r2) => |
|
313 (simp2(r1), simp2(r2)) match { |
|
314 case (ZERO, _) => ZERO |
|
315 case (_, ZERO) => ZERO |
|
316 case (ONE, r2s) => r2s |
|
317 case (r1s, ONE) => r1s |
|
318 case (r1s, r2s) => |
|
319 SEQ(r1s, r2s) |
|
320 } |
|
321 case ALTS(r1, r2) => |
|
322 val r1r2s = fltsplain(simp2(r1) :: simp2(r2) :: Nil).distinct |
|
323 r1r2s match { |
|
324 case Nil => ZERO |
|
325 case r :: Nil => r |
|
326 case r1 :: r2 :: rs => |
|
327 ALTSS(r1 :: r2 :: rs) |
|
328 } |
|
329 case ALTSS(rs) => |
|
330 // println(rs) |
|
331 (fltsplain(rs.map(simp2))).distinct match { |
|
332 case Nil => ZERO |
|
333 case r :: Nil => r |
|
334 case r1 :: r2 :: rs => |
|
335 ALTSS(r1 :: r2 :: rs) |
|
336 } |
|
337 case r => r |
|
338 } |
|
339 |
|
340 |
|
341 def simp(r: Rexp) : Rexp = r match { |
|
342 case SEQ(r1, r2) => |
|
343 (simp(r1), simp(r2)) match { |
|
344 case (ZERO, _) => ZERO |
|
345 case (_, ZERO) => ZERO |
|
346 case (ONE, r2s) => r2s |
|
347 case (r1s, ONE) => r1s |
|
348 case (r1s, r2s) => SEQ(r1s, r2s) |
|
349 } |
|
350 case ALTS(r1, r2) => { |
|
351 (simp(r1), simp(r2)) match { |
|
352 case (ZERO, r2s) => r2s |
|
353 case (r1s, ZERO) => r1s |
|
354 case (r1s, r2s) => |
|
355 if(r1s == r2s) r1s else ALTS(r1s, r2s) |
|
356 } |
|
357 } |
|
358 case r => r |
|
359 } |
|
360 |
|
361 def fltsplain(rs: List[Rexp]) : List[Rexp] = rs match { |
|
362 case Nil => Nil |
|
363 case ZERO :: rs => fltsplain(rs) |
|
364 case ALTS(r1, r2) :: rs => r1 :: r2 :: fltsplain(rs) |
|
365 case ALTSS(rs) :: rs1 => rs ::: fltsplain(rs1) |
|
366 case r :: rs => r :: fltsplain(rs) |
|
367 } |
|
368 |
|
369 |
|
370 |
|
371 |
|
372 def matcher(s: String, r: Rexp) : Boolean = |
|
373 nullable(ders(s.toList, r)) |
|
374 |
|
375 def simp_matcher(s: String, r: Rexp) : Boolean = |
|
376 nullable(ders_simp(s.toList, r)) |
296 |
377 |
297 |
378 |
298 // extracts a string from a value |
379 // extracts a string from a value |
299 def flatten(v: Val) : String = v match { |
380 def flatten(v: Val) : String = v match { |
300 case Empty => "" |
381 case Empty => "" |
1267 for(i <- 0 to 100) { |
1349 for(i <- 0 to 100) { |
1268 val prog = "a" * i |
1350 val prog = "a" * i |
1269 println(asize(bders_simp(prog.toList, internalise(r)))) |
1351 println(asize(bders_simp(prog.toList, internalise(r)))) |
1270 } |
1352 } |
1271 } |
1353 } |
1272 aaa_star() |
1354 // aaa_star() |
1273 |
1355 def naive_matcher() { |
|
1356 val r = STAR(STAR("a") ~ STAR("a")) |
|
1357 |
|
1358 for(i <- 0 to 20) { |
|
1359 val s = "a" * i |
|
1360 val t1 = System.nanoTime |
|
1361 matcher(s, r) |
|
1362 val duration = (System.nanoTime - t1) / 1e9d |
|
1363 print(i) |
|
1364 print(" ") |
|
1365 // print(duration) |
|
1366 // print(" ") |
|
1367 print(asize(bders_simp(s.toList, internalise(r)))) |
|
1368 //print(size(ders_simp(s.toList, r))) |
|
1369 println() |
|
1370 } |
|
1371 // for(i <- 1 to 40000000 by 500000) { |
|
1372 // val s = "a" * i |
|
1373 // val t1 = System.nanoTime |
|
1374 // val derssimp_result = ders_simp(s.toList, r) |
|
1375 // val duration = (System.nanoTime - t1) / 1e9d |
|
1376 // print(i) |
|
1377 // print(" ") |
|
1378 // print(duration) |
|
1379 // println() |
|
1380 // } |
|
1381 |
|
1382 } |
|
1383 naive_matcher() |
1274 def generator_test() { |
1384 def generator_test() { |
1275 |
1385 |
1276 test(rexp(4), 1000000) { (r: Rexp) => |
1386 test(rexp(4), 1000000) { (r: Rexp) => |
1277 // ALTS(SEQ(SEQ(ONE,CHAR('a')),STAR(CHAR('a'))),SEQ(ALTS(CHAR('c'),ONE),STAR(ZERO))))))), 1) { (r: Rexp) => |
1387 // ALTS(SEQ(SEQ(ONE,CHAR('a')),STAR(CHAR('a'))),SEQ(ALTS(CHAR('c'),ONE),STAR(ZERO))))))), 1) { (r: Rexp) => |
1278 val ss = Set("b")//stringsFromRexp(r) |
1388 val ss = Set("b")//stringsFromRexp(r) |