def nullable(r: Rexp) : Boolean = r match {+ −
case ZERO => false+ −
case ONE => true+ −
case CHAR(_) => false+ −
case ALT(r1, r2) => nullable(r1) || nullable(r2)+ −
case SEQ(r1, r2) => nullable(r1) && nullable(r2)+ −
case STAR(_) => true+ −
}+ −
+ −
def der(c: Char, r: Rexp) : Rexp = r match {+ −
case ZERO => ZERO+ −
case ONE => ZERO+ −
case CHAR(d) => if (c == d) ONE else ZERO+ −
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))+ −
case SEQ(r1, r2) => + −
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))+ −
else SEQ(der(c, r1), r2)+ −
case STAR(r) => SEQ(der(c, r), STAR(r))+ −
}+ −
+ −
def ders(s: List[Char], r: Rexp) : Rexp = s match {+ −
case Nil => r+ −
case c::s => ders(s, der(c, r))+ −
}+ −
+ −
def matcher(r: Rexp, s: String) : Boolean = + −
nullable(ders(s.toList, r))+ −