1 // Simple matcher for basic regular expressions

     1 // Simple matcher for basic regular expressions

     2 

     2 

     3 

     4 

     4 abstract class Rexp

     5 abstract class Rexp

     5 case object ZERO extends Rexp                    // matches nothing

     6 case object ZERO extends Rexp                    // matches nothing

     6 case object ONE extends Rexp                     // matches the empty string

     7 case object ONE extends Rexp                     // matches the empty string

     7 case class CHAR(c: Char) extends Rexp            // matches a character c

     8 case class CHAR(c: Char) extends Rexp            // matches a character c

    16   case ONE => true

    17   case ONE => true

    17   case CHAR(_) => false

    18   case CHAR(_) => false

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

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

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

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

    20   case STAR(_) => true

    21   case STAR(_) => true

    21 

    24 

    22 }

    25 }

    23 

    26 

    24 // derivative of a regular expression w.r.t. a character

    27 // derivative of a regular expression w.r.t. a character

    25 def der (c: Char, r: Rexp) : Rexp = r match {

    28 def der (c: Char, r: Rexp) : Rexp = r match {