1 // Christian's Solution for CW 1

     2 import scala.language.implicitConversions

     3 

     4 // basic regular expressions

     5 abstract class Rexp

     6 case object ZERO extends Rexp

     7 case object ONE 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  

    13 // extended regular expressions 

    14 case class RANGE(cs: Set[Char]) extends Rexp             // set of characters

    15 case class PLUS(r: Rexp) extends Rexp                    // plus

    16 case class OPTIONAL(r: Rexp) extends Rexp                // optional

    17 case class INTER(r1: Rexp, r2: Rexp) extends Rexp        // intersection

    18 case class NTIMES(r: Rexp, n: Int) extends Rexp          // n-times

    19 case class UPTO(r: Rexp, n: Int) extends Rexp            // up n-times

    20 case class FROM(r: Rexp, n: Int) extends Rexp            // from n-times

    21 case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times

    22 case class NOT(r: Rexp) extends Rexp                     // not

    23 

    24 // general version of CHAR, RANGE and ALL

    25 case class CFUN(f: Char => Boolean) extends Rexp         // subsuming CHAR and RANGE

    26 

    27 def FCHAR(c: Char) = CFUN(c == _)

    28 val FALL = CFUN(_ => true)

    29 def FRANGE(cs: Set[Char]) = CFUN(cs.contains(_))

    30 

    31 // the nullable function: tests whether the regular 

    32 // expression can recognise the empty string

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

    34   case ZERO => false

    35   case ONE => true

    36   case CHAR(_) => false

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

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

    39   case STAR(_) => true

    40   case RANGE(_) => false

    41   case PLUS(r) => nullable(r)

    42   case OPTIONAL(_) => true

    43   case INTER(r1, r2) => nullable(r1) && nullable(r2)

    44   case NTIMES(r, n) => if (n == 0) true else nullable(r)

    45   case UPTO(_, _) => true

    46   case FROM(r, n) => if (n == 0) true else nullable(r)

    47   case BETWEEN(r, n, m) => if (n == 0) true else nullable(r)

    48   case NOT(r) => !nullable(r)

    49   case CFUN(_) => false

    50 }

    51 

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

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

    54   case ZERO => ZERO

    55   case ONE => ZERO

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

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

    58   case SEQ(r1, r2) => 

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

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

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

    62   case RANGE(cs) => if (cs contains c) ONE else ZERO

    63   case PLUS(r) => SEQ(der(c, r), STAR(r))

    64   case OPTIONAL(r) => der(c, r)

    65   case INTER(r1, r2) => INTER(der(c, r1), der(c, r2))

    66   case NTIMES(r, n) => 

    67     if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))

    68   case UPTO(r, n) =>

    69     if (n == 0) ZERO else SEQ(der(c, r), UPTO(r, n - 1))

    70   case FROM(r, n) =>

    71     if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROM(r, n - 1))

    72   case BETWEEN(r, n, m) =>

    73     if (m < n) ZERO else

    74     if (n == 0 && m == 0) ZERO else 

    75     if (n == 0) SEQ(der(c, r), UPTO(r, m - 1)) 

    76     else SEQ(der(c, r), BETWEEN(r, n - 1, m - 1)) 

    77   case NOT(r) => NOT(der (c, r))

    78   case CFUN(f) => if (f(c)) ONE else ZERO

    79 }

    80 

    81 // simplification

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

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

    84     case (ZERO, r2s) => r2s

    85     case (r1s, ZERO) => r1s

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

    87   }

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

    89     case (ZERO, _) => ZERO

    90     case (_, ZERO) => ZERO

    91     case (ONE, r2s) => r2s

    92     case (r1s, ONE) => r1s

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

    94   }

    95   case r => r

    96 }

    97 

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

    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 // the main matcher function

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

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

   107 

   108 

   109 // Test Cases

   110 //============

   111 

   112 // some syntactic convenience

   113 

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

   115   case Nil => ONE

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

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

   118 }

   119 

   120 given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))

   121 

   122 extension (r: Rexp) {

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

   124   def % = STAR(r)

   125 }

   126 

   127 

   128 println("EMAIL:")

   129 val LOWERCASE = ('a' to 'z').toSet

   130 val DIGITS = ('0' to '9').toSet

   131 val SYMBOLS1 = ("_.-").toSet

   132 val SYMBOLS2 = (".-").toSet

   133 val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS1)) ~ "@" ~ 

   134               PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS2)) ~ "." ~

   135               BETWEEN(CFUN(LOWERCASE | Set('.')), 2, 6) }

   136 

   137 val my_email = "christian.urban@kcl.ac.uk"

   138 

   139 println(EMAIL);

   140 println(matcher(EMAIL, my_email))

   141 println(ders(my_email.toList,EMAIL))

   142 

   143 val ALL = CFUN((c:Char) => true)

   144 val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ " * /"

   145 

   146 println(matcher(COMMENT, "/**/"))

   147 println(matcher(COMMENT, "/*foobar*/"))

   148 println(matcher(COMMENT, "/*test*/test*/"))

   149 println(matcher(COMMENT, "/*test/*test*/"))

   150 

   151 

   152 println("\n\nTEST TEST\n")

   153 

   154 val r1 = PLUS(PLUS(SEQ(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))))

   155 val r2 = PLUS(PLUS(SEQ(BETWEEN(CHAR('a'), 19, 19), OPTIONAL(CHAR('a')))))

   156 val s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

   157 val s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

   158 val s3 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

   159 for (s <- List(s1,s2,s3)) {

   160   println(matcher(r1, s))

   161   println(matcher(r2, s))

   162 }

   163 

   164  

   165 // for measuring time

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

   167   val start = System.nanoTime()

   168   for (j <- 1 to i) code

   169   val end = System.nanoTime()

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

   171 }

   172 

   173 

   174 //@main

   175 def test(file: String) = {

   176     println("Test a{n}")

   177 

   178     for (i <- 0 to 200000 by 5000) {

   179       val re = NTIMES(SEQ(SEQ(CHAR('a'), CHAR('b')), CHAR('c')), i)

   180 

   181       print(f"$i: ${time_needed(2, matcher(re, "abc" * i))}%.5f")

   182       println(s" ${matcher(re, "abcd" * i)}")

   183     }

   184 }

   185