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 val r1s = simp(r1) |
3 (simp(r1), simp(r2)) match { |
4 val r2s = simp(r2) |
4 case (NULL, r2s) => r2s |
5 (r1s, r2s) match { |
5 case (r1s, NULL) => r1s |
6 case (NULL, _) => r2s |
6 case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s) |
7 case (_, NULL) => r1s |
|
8 case _ => if (r1s == r2s) r1s else ALT(r1s, r2s) |
|
9 } |
7 } |
10 } |
8 } |
11 case SEQ(r1, r2) => { |
9 case SEQ(r1, r2) => { |
12 val r1s = simp(r1) |
10 (simp(r1), simp(r2)) match { |
13 val r2s = simp(r2) |
|
14 (r1s, r2s) match { |
|
15 case (NULL, _) => NULL |
11 case (NULL, _) => NULL |
16 case (_, NULL) => NULL |
12 case (_, NULL) => NULL |
17 case (EMPTY, _) => r2s |
13 case (EMPTY, r2s) => r2s |
18 case (_, EMPTY) => r1s |
14 case (r1s, EMPTY) => r1s |
19 case _ => SEQ(r1s, r2s) |
15 case (r1s, r2s) => SEQ(r1s, r2s) |
20 } |
16 } |
21 } |
17 } |
22 case NTIMES(r, n) => NTIMES(simp(r), n) |
18 case NTIMES(r, n) => NTIMES(simp(r), n) |
23 case r => r |
19 case r => r |
24 } |
20 } |