1 abstract class Rexp

     2 

     3 case object NULL extends Rexp

     4 case object EMPTY extends Rexp

     5 case class CHAR(c: Char) extends Rexp

     6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp

     7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp

     8 case class STAR(r: Rexp) extends Rexp

     9 

    10 // whether it can match the empty string

    11 def nullable (r: Rexp) : Boolean = r match {

    12   case NULL => false

    13   case EMPTY => true

    14   case CHAR(_) => false

    15   case ALT(r1, r2) => nullable(r1) || nullable(r2)

    16   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

    17   case STAR(_) => true

    18 }

    19 

    20 // derivative of a regular expression

    21 def deriv (r: Rexp, c: Char) : Rexp = r match {

    22   case NULL => NULL

    23   case EMPTY => NULL

    24   case CHAR(d) => if (c == d) EMPTY else NULL

    25   case ALT(r1, r2) => ALT(deriv(r1, c), deriv(r2, c))

    26   case SEQ(r1, r2) => 

    27     if (nullable(r1)) ALT(SEQ(deriv(r1, c), r2), deriv(r2, c))

    28     else SEQ(deriv(r1, c), r2)

    29   case STAR(r) => SEQ(deriv(r, c), STAR(r))

    30 }

    31 

    32 def derivs (r: Rexp, s: List[Char]) : Rexp = s match {

    33   case Nil => r

    34   case c::cs => derivs(deriv(r, c), cs)

    35 }

    36 

    37 // regular expression matching

    38 def matches(r: Rexp, s: String) : Boolean = nullable(derivs(r, s.toList))

    39 

    40 /* Examples */

    41 

    42 println(matches(SEQ(SEQ(CHAR('c'), CHAR('a')), CHAR('b')),"cab"))

    43 println(matches(STAR(CHAR('a')),"aaa"))

    44 

    45 /* Convenience using implicits */

    46 implicit def string2rexp(s : String) : Rexp = {

    47   s.foldRight (EMPTY: Rexp) ( (c, r) => SEQ(CHAR(c), r) )

    48 }

    49 

    50 println(matches("cab" ,"cab"))

    51 println(matches(STAR("a"),"aaa"))

    52 println(matches(STAR("a"),"aaab"))