1 def nullable (r: Rexp) : Boolean = r match { |
1 def nullable (r: Rexp) : Boolean = r match { |
2 case NULL => false |
2 case ZERO => false |
3 case EMPTY => true |
3 case ONE => true |
4 case CHAR(_) => false |
4 case CHAR(_) => false |
5 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
5 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
6 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
6 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
7 case STAR(_) => true |
7 case STAR(_) => true |
8 } |
8 } |
9 |
9 |
10 def der (c: Char, r: Rexp) : Rexp = r match { |
10 def der (c: Char, r: Rexp) : Rexp = r match { |
11 case NULL => NULL |
11 case ZERO => ZERO |
12 case EMPTY => NULL |
12 case ONE => ZERO |
13 case CHAR(d) => if (c == d) EMPTY else NULL |
13 case CHAR(d) => if (c == d) ONE else ZERO |
14 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
14 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
15 case SEQ(r1, r2) => |
15 case SEQ(r1, r2) => |
16 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
16 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
17 else SEQ(der(c, r1), r2) |
17 else SEQ(der(c, r1), r2) |
18 case STAR(r) => SEQ(der(c, r), STAR(r)) |
18 case STAR(r) => SEQ(der(c, r), STAR(r)) |