91 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
91 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
92 case NUPTOM(r, i, j) => if (i == 0) true else nullable(r) |
92 case NUPTOM(r, i, j) => if (i == 0) true else nullable(r) |
93 case RANGE(_) => false |
93 case RANGE(_) => false |
94 case NOT(r) => !(nullable(r)) |
94 case NOT(r) => !(nullable(r)) |
95 case OPT(_) => true |
95 case OPT(_) => true |
|
96 } |
|
97 |
|
98 def zeroable (r: Rexp) : Boolean = r match { |
|
99 case NULL => true |
|
100 case EMPTY => false |
|
101 case CHAR(_) => false |
|
102 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
|
103 case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) |
|
104 case STAR(_) => false |
|
105 case PLUS(r) => zeroable(r) |
|
106 case NTIMES(r, i) => if (i == 0) false else zeroable(r) |
|
107 case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r) |
|
108 case RANGE(_) => false |
|
109 case NOT(r) => !(zeroable(r)) |
|
110 case OPT(_) => false |
96 } |
111 } |
97 |
112 |
98 // derivative of a regular expression w.r.t. a character |
113 // derivative of a regular expression w.r.t. a character |
99 def der (c: Char, r: Rexp) : Rexp = r match { |
114 def der (c: Char, r: Rexp) : Rexp = r match { |
100 case NULL => NULL |
115 case NULL => NULL |
210 println(ders_simp("aaa".toList, test)) |
225 println(ders_simp("aaa".toList, test)) |
211 println(ders_simp("aaaa".toList, test)) |
226 println(ders_simp("aaaa".toList, test)) |
212 println(ders_simp("aaaaa".toList, test)) |
227 println(ders_simp("aaaaa".toList, test)) |
213 println(ders_simp("aaaaaa".toList, test)) |
228 println(ders_simp("aaaaaa".toList, test)) |
214 println(ders_simp("aaaaaaa".toList, test)) |
229 println(ders_simp("aaaaaaa".toList, test)) |
|
230 |
|
231 def TEST(s: String, r: Rexp) = { |
|
232 println("Rexp |" + s + "|") |
|
233 println("Derivative:\n" + ders_simp(s.toList, r)) |
|
234 println("Is Nullable: " + nullable(ders_simp(s.toList, r))) |
|
235 println("Is Zeroable: " + zeroable(ders_simp(s.toList, r))) |
|
236 Console.readLine |
|
237 } |
|
238 |
|
239 |
|
240 val ALL2 = "a" | "f" |
|
241 val COMMENT2 = ("/*" ~ NOT(ALL2.% ~ "*/" ~ ALL2.%) ~ "*/") |
|
242 |
|
243 println("1) TEST TEST") |
|
244 TEST("", COMMENT2) |
|
245 TEST("/", COMMENT2) |
|
246 TEST("/*", COMMENT2) |
|
247 TEST("/*f", COMMENT2) |
|
248 TEST("/*f*", COMMENT2) |
|
249 TEST("/*f*/", COMMENT2) |
|
250 TEST("/*f*/ ", COMMENT2) |
|
251 |
|
252 val ALL3 = "a" | "f" |
|
253 val COMMENT3 = ("/" ~ NOT(ALL3.% ~ "&" ~ ALL3.%) ~ "&") |
|
254 |
|
255 println("2) TEST TEST") |
|
256 TEST("", COMMENT3) |
|
257 TEST("/", COMMENT3) |
|
258 TEST("/", COMMENT3) |
|
259 TEST("/f", COMMENT3) |
|
260 TEST("/f&", COMMENT3) |
|
261 TEST("/f& ", COMMENT3) |
|
262 |