1 package POSIX

     2 

     3 object PosixAlgo {

     4 

     5   abstract class Rexp

     6   case object NULL extends Rexp

     7   case object EMPTY extends Rexp

     8   case class CHAR(c: Char) extends Rexp

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

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

    11   case class STAR(r: Rexp) extends Rexp

    12   case class RECD(x: String, r: Rexp) extends Rexp

    13 

    14 	abstract class Val

    15   case object Void extends Val

    16   case class Chr(c: Char) extends Val

    17   case class Sequ(v1: Val, v2: Val) extends Val

    18   case class Left(v: Val) extends Val

    19   case class Right(v: Val) extends Val

    20   case class Stars(vs: List[Val]) extends Val

    21   case class Rec(x: String, v: Val) extends Val

    22 

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

    24     case NULL => false

    25     case EMPTY => true

    26     case CHAR(_) => false

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

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

    29     case STAR(_) => true

    30     case RECD(_, r1) => nullable(r1)

    31   }                                               //> nullable: (r: POSIX.PosixAlgo.Rexp)Boolean

    32   

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

    34     case NULL => NULL

    35     case EMPTY => NULL

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

    37     case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

    38     case SEQ(r1, r2) =>

    39       if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

    40       else SEQ(der(c, r1), r2)

    41     case STAR(r) => SEQ(der(c, r), STAR(r))

    42     case RECD(_, r1) => der(c, r1)

    43   }                                               //> der: (c: Char, r: POSIX.PosixAlgo.Rexp)POSIX.PosixAlgo.Rexp

    44 }