1 // CW 1

     2 import scala.language.implicitConversions    

     3 import scala.language.reflectiveCalls 

     4 

     5 abstract class Rexp

     6 case object ZERO extends Rexp                            // matches nothing

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

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

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

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

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

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

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

    14 case class OPT(r: Rexp) extends Rexp                     // optional

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

    16 case class UPNTIMES(r: Rexp, n: Int) extends Rexp        // up n-times

    17 case class FROMNTIMES(r: Rexp, n: Int) extends Rexp      // from n-times

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

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

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

    21 

    22 def CHAR(c: Char) = CFUN(d => c == d)

    23 val ALL = CFUN(_ => true)

    24 def RANGE(cs: Set[Char]) = CFUN(d => cs.contains(d))

    25 

    26 def CHAR(c: Char) = CFUN(c == _)

    27 val ALL = CFUN(_ => true)

    28 def RANGE(cs: Set[Char]) = CFUN(cs.contains(_))

    29 

    30 

    31 // 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 OPT(_) => true

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

    44   case UPNTIMES(_, _) => true

    45   case FROMNTIMES(r, n) => if (n == 0) true else nullable(r)

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

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

    48   case CFUN(_) => false

    49 }

    50 

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

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

    53   case ZERO => ZERO

    54   case ONE => ZERO

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

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

    57   case SEQ(r1, r2) => 

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

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

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

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

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

    63   case OPT(r) => der(c, r)

    64   case NTIMES(r, n) => 

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

    66   case UPNTIMES(r, n) =>

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

    68   case FROMNTIMES(r, n) =>

    69     if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROMNTIMES(r, n - 1))

    70   case NMTIMES(r, n, m) =>

    71     if (m < n) ZERO else

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

    73     if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1)) 

    74     else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1)) 

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

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

    77 }

    78 

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

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

    81     case (ZERO, r2s) => r2s

    82     case (r1s, ZERO) => r1s

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

    84   }

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

    86     case (ZERO, _) => ZERO

    87     case (_, ZERO) => ZERO

    88     case (ONE, r2s) => r2s

    89     case (r1s, ONE) => r1s

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

    91   }

    92   case r => r

    93 }

    94 

    95 

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

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

    98   case Nil => r

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

   100 }

   101 

   102 def ders_simp (s: List[Char], r: Rexp) : Rexp = s match {

   103   case Nil => r

   104   case c::s => ders_simp(s, simp(der(c, r)))

   105 }

   106 

   107 // main matcher function including simplification

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

   109   nullable(ders_simp(s.toList, r))

   110 

   111 

   112 

   113 // some convenience for typing in regular expressions

   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 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)

   120 

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

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

   123   def % = STAR(r)

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

   125 }

   126 

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

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

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

   130   def % = STAR(s)

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

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

   133 }

   134 

   135 val r1 = NTIMES("a", 3)

   136 val r2 = NTIMES(OPT("a"), 3)

   137 val r3 = UPNTIMES("a", 3)

   138 val r4 = UPNTIMES(OPT("a"), 3)

   139 val r5 = NMTIMES("a", 3, 5)

   140 val r6 = NMTIMES(OPT("a"), 3, 5)

   141 

   142 val rs = List(r1, r2, r3, r4, r5, r6)

   143 

   144 rs.map(matcher(_, ""))

   145 rs.map(matcher(_, "a"))

   146 rs.map(matcher(_, "aa"))

   147 rs.map(matcher(_, "aaa"))

   148 rs.map(matcher(_, "aaaa"))

   149 rs.map(matcher(_, "aaaaa"))

   150 rs.map(matcher(_, "aaaaaa"))

   151 

   152 println("EMAIL:")

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

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

   155 val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | ("_.-").toSet)) ~ "@" ~ 

   156               PLUS(CFUN(LOWERCASE | DIGITS | (".-").toSet)) ~ "." ~

   157               NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6) }

   158 

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

   160 

   161 println(EMAIL);

   162 println(matcher(EMAIL, my_email))

   163 println(ders_simp(my_email.toList, EMAIL))

   164 

   165 println("COMMENTS:")

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

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

   168 

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

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

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

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

   173 

   174 println("EVILS:")

   175 val EVIL1 = PLUS(PLUS("a" ~ "a" ~ "a"))

   176 val EVIL2 = PLUS(PLUS("aaaaaaaaaaaaaaaaaaa" ~ OPT("a")))  // 19 as ~ a?

   177 

   178 

   179 //40 * aaa matches

   180 //43 * aaa + aa does not

   181 //45 * aaa + a

   182 

   183 println("EVIL1:")

   184 println(matcher(EVIL1, "aaa" * 40))

   185 println(matcher(EVIL1, "aaa" * 43 + "aa"))

   186 println(matcher(EVIL1, "aaa" * 45 + "a"))

   187 println("EVIL2:")

   188 println(matcher(EVIL2, "aaa" * 40))

   189 println(matcher(EVIL2, "aaa" * 43 + "aa"))

   190 println(matcher(EVIL2, "aaa" * 45 + "a"))

   191 

   192 println("TEST for bug pointed out by Filips Ivanovs")

   193 val test = NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6)

   194   

   195 println(matcher(test,"a"))

   196 println(matcher(test,"ab"))

   197 println(matcher(test,"abcdef"))

   198 println(matcher(test,"abc"))

   199 println(matcher(test,"...."))

   200 println(matcher(test,"asdfg"))

   201 println(matcher(test,"abcdefg"))

   202 

   203 println(test)

   204 println(ders_simp("a".toList, test))

   205 println(ders_simp("aa".toList, test))

   206 println(ders_simp("aaa".toList, test))

   207 println(ders_simp("aaaa".toList, test))

   208 println(ders_simp("aaaaa".toList, test))

   209 println(ders_simp("aaaaaa".toList, test))

   210 println(ders_simp("aaaaaaa".toList, test))

   211 

   212 def TEST(s: String, r: Rexp) = {

   213   println("Rexp |" + s + "|")

   214   println("Derivative:\n" + ders_simp(s.toList, r))

   215   println("Is Nullable: " + nullable(ders_simp(s.toList, r)))

   216   Console.readLine

   217 }

   218 

   219 

   220 val ALL2 = "a" | "f"

   221 val COMMENT2 = ("/*" ~ NOT(ALL2.% ~ "*/" ~ ALL2.%) ~ "*/")

   222 

   223 println("1) TEST TEST")

   224 TEST("", COMMENT2)

   225 TEST("/", COMMENT2)

   226 TEST("/*", COMMENT2)

   227 TEST("/*f", COMMENT2)

   228 TEST("/*f*", COMMENT2)

   229 TEST("/*f*/", COMMENT2)

   230 TEST("/*f*/ ", COMMENT2)

   231 

   232 val ALL3 = "a" | "f"

   233 val COMMENT3 = ("/" ~ NOT(ALL3.% ~ "&" ~ ALL3.%) ~ "&")

   234 

   235 println("2) TEST TEST")

   236 TEST("", COMMENT3)

   237 TEST("/", COMMENT3)

   238 TEST("/", COMMENT3)

   239 TEST("/f", COMMENT3)

   240 TEST("/f&", COMMENT3)

   241 TEST("/f& ", COMMENT3)

   242 

   243 //test: ("a" | "aa") ~ ("a" | "aa")*

   244 val auxEVIL3 = ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))

   245 val EVIL3 = SEQ(auxEVIL3, STAR(auxEVIL3))

   246 val EVIL3p = FROMNTIMES(auxEVIL3, 1)

   247 

   248 

   249 for (i <- 1 to 100 by 1) {

   250   println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i))) + " size: " + 

   251 	  size(ders(("a" * i).toList, EVIL3)))

   252 }

   253 

   254 

   255 

   256 val t1 = EVIL3

   257 val t2 = simp(der('a', t1))

   258 val t3 = simp(der('a', t2))

   259 val t4 = simp(der('a', t3))

   260 

   261 val t1 = EVIL3p

   262 val t2 = simp(der('a', t1))

   263 val t3 = simp(der('a', t2))

   264 val t4 = simp(der('a', t3))