1 def der (r: Rexp, c: Char) : Rexp = r match { |
1 def simp(r: Rexp): Rexp = r match { |
2 case NULL => NULL |
2 case ALT(r1, r2) => { |
3 case EMPTY => NULL |
3 val r1s = simp(r1) |
4 case CHAR(d) => if (c == d) EMPTY else NULL |
4 val r2s = simp(r2) |
5 case ALT(r1, r2) => ALT(der(r1, c), der(r2, c)) |
5 (r1s, r2s) match { |
6 case SEQ(r1, r2) => |
6 case (NULL, _) => r2s |
7 if (nullable(r1)) ALT(SEQ(der(r1, c), r2), der(r2, c)) |
7 case (_, NULL) => r1s |
8 else SEQ(der(r1, c), r2) |
8 case _ => if (r1s == r2s) r1s else ALT(r1s, r2s) |
9 case STAR(r) => SEQ(der(r, c), STAR(r)) |
9 } |
|
10 } |
|
11 case SEQ(r1, r2) => { |
|
12 val r1s = simp(r1) |
|
13 val r2s = simp(r2) |
|
14 (r1s, r2s) match { |
|
15 case (NULL, _) => NULL |
|
16 case (_, NULL) => NULL |
|
17 case (EMPTY, _) => r2s |
|
18 case (_, EMPTY) => r1s |
|
19 case _ => SEQ(r1s, r2s) |
|
20 } |
|
21 } |
|
22 case NTIMES(r, n) => NTIMES(simp(r), n) |
|
23 case r => r |
10 } |
24 } |
11 |
25 |
12 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
26 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
13 case Nil => r |
27 case Nil => r |
14 case c::s => ders(s, der(c, r)) |
28 case c::s => ders(s, simp(der(c, r))) |
15 } |
29 } |
16 |
30 |