7 case class STAR(r: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
8 case class NTIMES(r: Rexp, n: Int) extends Rexp |
8 case class NTIMES(r: Rexp, n: Int) extends Rexp |
9 |
9 |
10 def simp(r: Rexp): Rexp = r match { |
10 def simp(r: Rexp): Rexp = r match { |
11 case ALT(r1, r2) => { |
11 case ALT(r1, r2) => { |
12 val r1s = simp(r1) |
12 (simp(r1), simp(r2)) match { |
13 val r2s = simp(r2) |
13 case (NULL, r2s) => r2s |
14 (r1s, r2s) match { |
14 case (r1s, NULL) => r1s |
15 case (NULL, _) => r2s |
15 case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s) |
16 case (_, NULL) => r1s |
|
17 case _ => if (r1s == r2s) r1s else ALT(r1s, r2s) |
|
18 } |
16 } |
19 } |
17 } |
20 case SEQ(r1, r2) => { |
18 case SEQ(r1, r2) => { |
21 val r1s = simp(r1) |
19 (simp(r1), simp(r2)) match { |
22 val r2s = simp(r2) |
|
23 (r1s, r2s) match { |
|
24 case (NULL, _) => NULL |
20 case (NULL, _) => NULL |
25 case (_, NULL) => NULL |
21 case (_, NULL) => NULL |
26 case (EMPTY, _) => r2s |
22 case (EMPTY, r2s) => r2s |
27 case (_, EMPTY) => r1s |
23 case (r1s, EMPTY) => r1s |
28 case _ => SEQ(r1s, r2s) |
24 case (r1s, r2s) => SEQ(r1s, r2s) |
29 } |
25 } |
30 } |
26 } |
31 case NTIMES(r, n) => NTIMES(simp(r), n) |
27 case NTIMES(r, n) => NTIMES(simp(r), n) |
32 case r => r |
28 case r => r |
33 } |
29 } |