1 def nullable (r: Rexp) : Boolean = r match { |
1 def nullable(r: Rexp) : Boolean = r match { |
2 case ZERO => false |
2 case ZERO => false |
3 case ONE => 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 ZERO => ZERO |
11 case ZERO => ZERO |
12 case ONE => ZERO |
12 case ONE => ZERO |
13 case CHAR(d) => if (c == d) ONE else ZERO |
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)) |
19 } |
19 } |
20 |
20 |
21 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
21 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
22 case Nil => r |
22 case Nil => r |
23 case c::s => ders(s, der(c, r)) |
23 case c::s => ders(s, der(c, r)) |
24 } |
24 } |
25 |
25 |
26 def matches(r: Rexp, s: String) : Boolean = |
26 def matches(r: Rexp, s: String) : Boolean = |