1 // A simple matcher for basic regular expressions

     2 

     3 abstract class Rexp

     4 case object ZERO extends Rexp                    // matches nothing

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

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

     7 case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative

     8 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence

     9 case class STAR(r: Rexp) extends Rexp            // star

    10 

    11 // nullable function: tests whether a regular 

    12 // expression can recognise the empty string

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

    14   case ZERO => false

    15   case ONE => true

    16   case CHAR(_) => false

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

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

    19   case STAR(_) => true

    20 }

    21 

    22 // the derivative of a regular expression w.r.t. a character

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

    24   case ZERO => ZERO

    25   case ONE => ZERO

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

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

    28   case SEQ(r1, r2) => 

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

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

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

    32 }

    33 

    34 // the derivative w.r.t. a string (iterates der)

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

    36   case Nil => r

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

    38 }

    39 

    40 // the main matcher function

    41 def matcher(r: Rexp, s: String) : Boolean = 

    42   nullable(ders(s.toList, r))

    43 

    44 

    45 // examples from the homework

    46 

    47 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))

    48 der('a', r)

    49 der('b', r)

    50 der('c', r)

    51 

    52 val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z'))

    53 der('x', r2)

    54 der('y', der('x', r2))

    55 der('z', der('y', der('x', r2)))

    56 

    57 

    58 // the optional regular expression (one or zero times)

    59 def OPT(r: Rexp) = ALT(r, ONE)

    60 

    61 // the n-times regular expression (explicitly expanded)

    62 def NTIMES(r: Rexp, n: Int) : Rexp = n match {

    63   case 0 => ONE

    64   case 1 => r

    65   case n => SEQ(r, NTIMES(r, n - 1))

    66 }

    67 

    68 

    69 // Test Cases

    70 

    71 // the evil regular expression  a?{n} a{n}

    72 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))

    73 

    74 // the evil regular expression (a*)*b

    75 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

    76 

    77 // for measuring time

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

    79   val start = System.nanoTime()

    80   for (j <- 1 to i) code

    81   val end = System.nanoTime()

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

    83 }

    84 

    85 

    86 // test: (a?{n}) (a{n})

    87 println("Test (a?{n}) (a{n})")

    88 

    89 for (i <- 0 to 20 by 2) {

    90   println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f")

    91 }

    92 

    93 // test: (a*)* b

    94 println("Test (a*)* b")

    95 

    96 for (i <- 0 to 20 by 2) {

    97   println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f")

    98 }

    99 

   100 

   101 // the size of a regular expressions - for testing purposes 

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

   103   case ZERO => 1

   104   case ONE => 1

   105   case CHAR(_) => 1

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

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

   108   case STAR(r) => 1 + size(r)

   109 }

   110 

   111 // the expicit expansion in EVIL1(n) increases

   112 // drastically its size

   113 

   114 size(EVIL1(1))  // 5

   115 size(EVIL1(3))  // 17

   116 size(EVIL1(5))  // 29

   117 size(EVIL1(7))  // 41

   118 size(EVIL1(20)) // 119

   119 

   120 // given a regular expression and building successive

   121 // derivatives might result into bigger and bigger

   122 // regular expressions...here is an example for this:

   123 

   124 // (a+b)* o a o b o (a+b)*

   125 val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b')))

   126 val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux)))

   127 

   128 size(ders("".toList, BIG))              // 13

   129 size(ders("ab".toList, BIG))            // 51

   130 size(ders("abab".toList, BIG))          // 112

   131 size(ders("ababab".toList, BIG))        // 191

   132 size(ders("abababab".toList, BIG))      // 288

   133 size(ders("ababababab".toList, BIG))    // 403

   134 size(ders("abababababab".toList, BIG))  // 536

   135 

   136 

   137 size(ders(("ab" * 200).toList, BIG))    // 366808

   138 

   139 for (i <- 0 to 200 by 10) {

   140   println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f")

   141 }

   142 

   143 

   144 

   145 

   146 //////////////////////////////////////

   147 def concat(A: Set[String], B: Set[String]) : Set[String] =

   148   for (s1 <- A; s2 <- B) yield s1 ++ s2

   149   

   150 

   151 val A = Set("foo", "bar")

   152 val B = Set("a", "b")

   153 

   154