equal
deleted
inserted
replaced
28 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
28 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
29 case STAR(_) => true |
29 case STAR(_) => true |
30 } |
30 } |
31 |
31 |
32 // the derivative of a regular expression w.r.t. a character |
32 // the derivative of a regular expression w.r.t. a character |
33 def der (c: Char, r: Rexp) : Rexp = r match { |
33 def der(c: Char, r: Rexp) : Rexp = r match { |
34 case ZERO => ZERO |
34 case ZERO => ZERO |
35 case ONE => ZERO |
35 case ONE => ZERO |
36 case CHAR(d) => if (c == d) ONE else ZERO |
36 case CHAR(d) => if (c == d) ONE else ZERO |
37 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
37 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
38 case SEQ(r1, r2) => |
38 case SEQ(r1, r2) => |
40 else SEQ(der(c, r1), r2) |
40 else SEQ(der(c, r1), r2) |
41 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
41 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
42 } |
42 } |
43 |
43 |
44 // the derivative w.r.t. a string (iterates der) |
44 // the derivative w.r.t. a string (iterates der) |
45 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
45 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
46 case Nil => r |
46 case Nil => r |
47 case c::s => ders(s, der(c, r)) |
47 case c::s => ders(s, der(c, r)) |
48 } |
48 } |
49 |
49 |
50 // the main matcher function |
50 // the main matcher function |