1 def simp(r: Rexp): Rexp = r match { |
1 def simp(r: Rexp): Rexp = r match { |
2 case ALT(r1, r2) => { |
2 case ALT(r1, r2) => { |
3 (simp(r1), simp(r2)) match { |
3 (simp(r1), simp(r2)) match { |
4 case (NULL, r2s) => r2s |
4 case (ZERO, r2s) => r2s |
5 case (r1s, NULL) => r1s |
5 case (r1s, ZERO) => r1s |
6 case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s) |
6 case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s) |
7 } |
7 } |
8 } |
8 } |
9 case SEQ(r1, r2) => { |
9 case SEQ(r1, r2) => { |
10 (simp(r1), simp(r2)) match { |
10 (simp(r1), simp(r2)) match { |
11 case (NULL, _) => NULL |
11 case (ZERO, _) => ZERO |
12 case (_, NULL) => NULL |
12 case (_, ZERO) => ZERO |
13 case (EMPTY, r2s) => r2s |
13 case (ONE, r2s) => r2s |
14 case (r1s, EMPTY) => r1s |
14 case (r1s, ONE) => r1s |
15 case (r1s, r2s) => SEQ(r1s, r2s) |
15 case (r1s, r2s) => SEQ(r1s, r2s) |
16 } |
16 } |
17 } |
17 } |
18 case NTIMES(r, n) => NTIMES(simp(r), n) |
18 case NTIMES(r, n) => NTIMES(simp(r), n) |
19 case r => r |
19 case r => r |
20 } |
20 } |
21 |
21 |
22 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
22 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
23 case Nil => r |
23 case Nil => r |
24 case c::s => ders(s, simp(der(c, r))) |
24 case c::s => ders(s, simp(der(c, r))) (*@\label{simpline}@*) |
25 } |
25 } |
26 |
26 |