1 // Part 1 about Regular Expression Matching

     2 //==========================================

     3 

     4 object CW8a {

     5 

     6 abstract class Rexp

     7 case object ZERO extends Rexp

     8 case object ONE extends Rexp

     9 case class CHAR(c: Char) extends Rexp

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

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

    12 case class STAR(r: Rexp) extends Rexp 

    13 

    14 // some convenience for typing in regular expressions

    15 

    16 import scala.language.implicitConversions    

    17 import scala.language.reflectiveCalls 

    18 

    19 

    20 def charlist2rexp(s: List[Char]): Rexp = s match {

    21   case Nil => ONE

    22   case c::Nil => CHAR(c)

    23   case c::s => SEQ(CHAR(c), charlist2rexp(s))

    24 }

    25 implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)

    26 

    27 implicit def RexpOps (r: Rexp) = new {

    28   def | (s: Rexp) = ALT(r, s)

    29   def % = STAR(r)

    30   def ~ (s: Rexp) = SEQ(r, s)

    31 }

    32 

    33 implicit def stringOps (s: String) = new {

    34   def | (r: Rexp) = ALT(s, r)

    35   def | (r: String) = ALT(s, r)

    36   def % = STAR(s)

    37   def ~ (r: Rexp) = SEQ(s, r)

    38   def ~ (r: String) = SEQ(s, r)

    39 }

    40 

    41 // (1a) Complete the function nullable according to

    42 // the definition given in the coursework; this 

    43 // function checks whether a regular expression

    44 // can match the empty string

    45 

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

    47   case ZERO => false

    48   case ONE => true

    49   case CHAR(_) => false

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

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

    52   case STAR(_) => true

    53 }

    54 

    55 // (1b) Complete the function der according to

    56 // the definition given in the coursework; this

    57 // function calculates the derivative of a 

    58 // regular expression w.r.t. a character

    59 

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

    61   case ZERO => ZERO

    62   case ONE => ZERO

    63   case CHAR(d) => if (c == d) ONE else ZERO

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

    65   case SEQ(r1, r2) => 

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

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

    68   case STAR(r1) => SEQ(der(c, r1), STAR(r1))

    69 }

    70 

    71 // (1c) Complete the function der according to

    72 // the specification given in the coursework; this

    73 // function simplifies a regular expression;

    74 // however it does not simplify inside STAR-regular

    75 // expressions

    76 

    77 def simp(r: Rexp) : Rexp = r match {

    78   case ALT(r1, r2) => (simp(r1), simp(r2)) match {

    79     case (ZERO, r2s) => r2s

    80     case (r1s, ZERO) => r1s

    81     case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)

    82   }

    83   case SEQ(r1, r2) =>  (simp(r1), simp(r2)) match {

    84     case (ZERO, _) => ZERO

    85     case (_, ZERO) => ZERO

    86     case (ONE, r2s) => r2s

    87     case (r1s, ONE) => r1s

    88     case (r1s, r2s) => SEQ(r1s, r2s)

    89   }

    90   case r => r

    91 }

    92 

    93 // (1d) Complete the two functions below; the first 

    94 // calculates the derivative w.r.t. a string; the second

    95 // is the regular expression matcher taking a regular

    96 // expression and a string and checks whether the

    97 // string matches the regular expression

    98 

    99 def ders (s: List[Char], r: Rexp) : Rexp = s match {

   100   case Nil => r

   101   case c::s => ders(s, simp(der(c, r)))

   102 }

   103 

   104 // main matcher function

   105 def matcher(r: Rexp, s: String): Boolean = nullable(ders(s.toList, r))

   106 

   107 // (1e) Complete the size function for regular

   108 // expressions  according to the specification 

   109 // given in the coursework.

   110 

   111 def size(r: Rexp): Int = r match {

   112   case ZERO => 1

   113   case ONE => 1

   114   case CHAR(_) => 1

   115   case ALT(r1, r2) => 1 + size(r1) + size (r2)

   116   case SEQ(r1, r2) => 1 + size(r1) + size (r2)

   117   case STAR(r1) => 1 + size(r1)

   118 }

   119 

   120 

   121 

   122 // some testing data

   123 /*

   124 matcher(("a" ~ "b") ~ "c", "abc")  // => true

   125 matcher(("a" ~ "b") ~ "c", "ab")   // => false

   126 

   127 // the supposedly 'evil' regular expression (a*)* b

   128 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

   129 

   130 matcher(EVIL, "a" * 1000 ++ "b")   // => true

   131 matcher(EVIL, "a" * 1000)          // => false

   132 

   133 // size without simplifications

   134 size(der('a', der('a', EVIL)))             // => 28

   135 size(der('a', der('a', der('a', EVIL))))   // => 58

   136 

   137 // size with simplification

   138 size(simp(der('a', der('a', EVIL))))           // => 8

   139 size(simp(der('a', der('a', der('a', EVIL))))) // => 8

   140 

   141 // Java needs around 30 seconds for matching 28 a's with EVIL. 

   142 //

   143 // Lets see how long it takes to match strings with 

   144 // 0.5 Million a's...it should be in the range of some

   145 // seconds.

   146 

   147 def time_needed[T](i: Int, code: => T) = {

   148   val start = System.nanoTime()

   149   for (j <- 1 to i) code

   150   val end = System.nanoTime()

   151   (end - start)/(i * 1.0e9)

   152 }

   153 

   154 for (i <- 0 to 5000000 by 500000) {

   155   println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))

   156 }

   157 */

   158 

   159 }