42 } |
42 } |
43 |
43 |
44 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
44 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
45 |
45 |
46 |
46 |
47 //optional regular expression: one or zero times |
47 // the optional regular expression: one or zero times |
48 //this regular expression is still defined in terms of ALT |
48 // this regular expression is still defined in terms of ALT |
49 def OPT(r: Rexp) = ALT(r, ONE) |
49 def OPT(r: Rexp) = ALT(r, ONE) |
50 |
50 |
51 |
51 |
52 // Test Cases |
52 // Test Cases |
53 |
53 |
54 //evil regular expressions |
54 // evil regular expressions |
55 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
55 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
56 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
56 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
57 |
57 |
58 def time_needed[T](i: Int, code: => T) = { |
58 def time_needed[T](i: Int, code: => T) = { |
59 val start = System.nanoTime() |
59 val start = System.nanoTime() |
60 for (j <- 1 to i) code |
60 for (j <- 1 to i) code |
61 val end = System.nanoTime() |
61 val end = System.nanoTime() |
62 (end - start)/(i * 1.0e9) |
62 "%.5f".format((end - start) / (i * 1.0e9)) |
63 } |
|
64 |
|
65 |
|
66 //test: (a?{n}) (a{n}) |
|
67 for (i <- 1 to 1201 by 100) { |
|
68 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
|
69 } |
|
70 |
|
71 for (i <- 1 to 1201 by 100) { |
|
72 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
|
73 } |
|
74 |
|
75 |
|
76 //test: (a*)* b |
|
77 for (i <- 1 to 21) { |
|
78 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
|
79 } |
|
80 |
|
81 for (i <- 1 to 21) { |
|
82 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
|
83 } |
63 } |
84 |
64 |
85 |
65 |
86 |
66 |
87 // size of a regular expressions - for testing purposes |
67 // test: (a?{n}) (a{n}) |
|
68 for (i <- 0 to 1000 by 100) { |
|
69 println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") |
|
70 } |
|
71 |
|
72 // test: (a*)* b |
|
73 for (i <- 1 to 21) { |
|
74 println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") |
|
75 } |
|
76 |
|
77 |
|
78 // the size of a regular expressions - for testing purposes |
88 def size(r: Rexp) : Int = r match { |
79 def size(r: Rexp) : Int = r match { |
89 case ZERO => 1 |
80 case ZERO => 1 |
90 case ONE => 1 |
81 case ONE => 1 |
91 case CHAR(_) => 1 |
82 case CHAR(_) => 1 |
92 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
83 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
101 |
92 |
102 size(EVIL1(1)) // 7 |
93 size(EVIL1(1)) // 7 |
103 size(EVIL1(3)) // 7 |
94 size(EVIL1(3)) // 7 |
104 size(EVIL1(5)) // 7 |
95 size(EVIL1(5)) // 7 |
105 size(EVIL1(7)) // 7 |
96 size(EVIL1(7)) // 7 |
|
97 size(EVIL1(20)) // 7 |
106 |
98 |
107 size(ders("".toList, EVIL1(5))) // 7 |
99 size(ders("".toList, EVIL1(5))) // 7 |
108 size(ders("a".toList, EVIL1(5))) // 16 |
100 size(ders("a".toList, EVIL1(5))) // 16 |
109 size(ders("aa".toList, EVIL1(5))) // 35 |
101 size(ders("aa".toList, EVIL1(5))) // 35 |
110 size(ders("aaa".toList, EVIL1(5))) // 59 |
102 size(ders("aaa".toList, EVIL1(5))) // 59 |