1 // Simple matcher for basic regular expressions

     1 // Simple matcher for basic regular expressions

     4 

     2 

     5 abstract class Rexp

     3 abstract class Rexp

     6 case object ZERO extends Rexp                    // matches nothing

     4 case object ZERO extends Rexp                    // matches nothing

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

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

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

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

    17   case ONE => true

    15   case ONE => true

    18   case CHAR(_) => false

    16   case CHAR(_) => false

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

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

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

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

    21   case STAR(_) => true

    19   case STAR(_) => true

    23 }

    20 }

    24 

    21 

    26 

    23 

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

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

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

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

    29   case ZERO => ZERO

    26   case ZERO => ZERO

    30   case ONE => ZERO

    27   case ONE => ZERO