progs/re0.scala
changeset 490 4fee50f38305
parent 93 4794759139ea
child 499 dfd0f41f8668
equal deleted inserted replaced
489:e28d7a327870 490:4fee50f38305
     1 import scala.annotation.tailrec
     1 import scala.annotation.tailrec
       
     2 import scala.language.implicitConversions
     2 
     3 
     3 abstract class Rexp
     4 abstract class Rexp
     4 
     5 
     5 case object NULL extends Rexp
     6 case object NULL extends Rexp
     6 case object EMPTY extends Rexp
     7 case object EMPTY extends Rexp
    70   case NOT(r) => NOT(der (c, r))
    71   case NOT(r) => NOT(der (c, r))
    71   case REP(r, i) => 
    72   case REP(r, i) => 
    72     if (i == 0) NULL else SEQ(der(c, r), REP(r, i - 1))
    73     if (i == 0) NULL else SEQ(der(c, r), REP(r, i - 1))
    73 }
    74 }
    74 
    75 
       
    76 
    75 // derivative w.r.t. a string (iterates der)
    77 // derivative w.r.t. a string (iterates der)
    76 @tailrec
    78 @tailrec
    77 def ders (s: List[Char], r: Rexp) : Rexp = s match {
    79 def ders (s: List[Char], r: Rexp) : Rexp = s match {
    78   case Nil => r
    80   case Nil => r
    79   case c::s => ders(s, der(c, r))
    81   case c::s => ders(s, der(c, r))