189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
import scala.language.implicitConversions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
import scala.language.reflectiveCalls
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
abstract class Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
def simp : Rexp = this
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
case object NULL extends Rexp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
case object EMPTY extends Rexp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
case class CHAR(c: Char) extends Rexp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
case class ALT(r1: Rexp, r2: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
override def toString = r1.toString + " | " + r2.toString
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
override def simp = (r1.simp, r2.simp) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
14 |
case (NULL, r) => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
15 |
case (r, NULL) => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
16 |
case (r, EMPTY) => if (nullable(r)) r else ALT(r, EMPTY)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
case (EMPTY, r) => if (nullable(r)) r else ALT(r, EMPTY)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
case (r1, r2) => if (r1 == r2) r1 else ALT(r1, r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
19 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
21 |
case class RANGE(cs: List[Char]) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
//override def toString = cs.mkString("[",",","]")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
23 |
override def toString = "[" + cs.head + " .. " + cs.last + "]"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
24 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
25 |
object RANGE {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
def apply(s: String) : RANGE = RANGE(s.toList)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
override def toString = r1.toString + " ~ " + r2.toString
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
override def simp = (r1.simp, r2.simp) match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
case (NULL, _) => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
case (_, NULL) => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
case (EMPTY, r) => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
case (r, EMPTY) => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
case (r1, r2) => SEQ(r1, r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
case class PLUS(r: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
39 |
override def simp = r.simp match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
case NULL => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
case EMPTY => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
case r => PLUS(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
case class STAR(r: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
override def simp = r.simp match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
case NULL => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
case EMPTY => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
case r => STAR(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
case class NTIMES(r: Rexp, n: Int) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
override def simp = if (n == 0) EMPTY else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
r.simp match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
case NULL => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
case EMPTY => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
case r => NTIMES(r, n)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
}
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
case class NUPTOM(r: Rexp, n: Int, m: Int) extends Rexp {
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
override def simp = if (m == 0) EMPTY else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
r.simp match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
case NULL => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
case EMPTY => EMPTY
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
case r => NUPTOM(r, n, m)
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
66 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
}
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
def NMTIMES(r: Rexp, n: Int, m: Int) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
if(m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
else NUPTOM(r, n, m - n)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
case class NOT(r: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
override def simp = NOT(r.simp)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
case class OPT(r: Rexp) extends Rexp {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
override def simp = OPT(r.simp)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
// nullable function: tests whether the regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
82 |
// expression can recognise the empty string
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
def nullable (r: Rexp) : Boolean = r match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
84 |
case NULL => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
case EMPTY => true
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
case CHAR(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
case ALT(r1, r2) => nullable(r1) || nullable(r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
88 |
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
case STAR(_) => true
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
case PLUS(r) => nullable(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
91 |
case NTIMES(r, i) => if (i == 0) true else nullable(r)
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
case NUPTOM(r, i, j) => if (i == 0) true else nullable(r)
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
93 |
case RANGE(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
94 |
case NOT(r) => !(nullable(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
95 |
case OPT(_) => true
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
96 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
97 |
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
def zeroable (r: Rexp) : Boolean = r match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
case NULL => true
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
case EMPTY => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
case CHAR(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
case STAR(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
case PLUS(r) => zeroable(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
case NTIMES(r, i) => if (i == 0) false else zeroable(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
case RANGE(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
case NOT(r) => !(zeroable(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
case OPT(_) => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
113 |
// derivative of a regular expression w.r.t. a character
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
114 |
def der (c: Char, r: Rexp) : Rexp = r match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
115 |
case NULL => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
116 |
case EMPTY => NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
117 |
case CHAR(d) => if (c == d) EMPTY else NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
118 |
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
119 |
case SEQ(r1, r2) =>
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
120 |
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
else SEQ(der(c, r1), r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
122 |
case STAR(r) => SEQ(der(c, r), STAR(r))
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
case PLUS(r) => SEQ(der(c, r), STAR(r))
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
124 |
case NTIMES(r, i) =>
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
125 |
if (i == 0) NULL else der(c, SEQ(r, NTIMES(r, i - 1)))
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
case NUPTOM(r, i, j) =>
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
if (i == 0 && j == 0) NULL else
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
if (i == 0) ALT(der(c, NTIMES(r, j)), der(c, NUPTOM(r, 0, j - 1)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
else der(c, SEQ(r, NUPTOM(r, i - 1, j)))
|
189
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
130 |
case RANGE(cs) => if (cs contains c) EMPTY else NULL
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
131 |
case NOT(r) => NOT(der (c, r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
132 |
case OPT(r) => der(c, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
133 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
134 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
135 |
// derivative w.r.t. a string (iterates der)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
136 |
def ders (s: List[Char], r: Rexp) : Rexp = s match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
case Nil => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
case c::s => ders(s, der(c, r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
139 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
140 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
def ders_simp (s: List[Char], r: Rexp) : Rexp = s match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
142 |
case Nil => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
143 |
case c::s => ders_simp(s, der(c, r).simp)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
144 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
145 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
146 |
// main matcher function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
147 |
def matcher(r: Rexp, s: String) : Boolean = nullable(ders_simp(s.toList, r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
148 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
149 |
// some convenience for typing in regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
150 |
def charlist2rexp(s : List[Char]) : Rexp = s match {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
151 |
case Nil => EMPTY
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
152 |
case c::Nil => CHAR(c)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
153 |
case c::s => SEQ(CHAR(c), charlist2rexp(s))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
154 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
155 |
implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
156 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
157 |
implicit def RexpOps (r: Rexp) = new {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
158 |
def | (s: Rexp) = ALT(r, s)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
159 |
def % = STAR(r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
160 |
def ~ (s: Rexp) = SEQ(r, s)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
161 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
162 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
163 |
implicit def stringOps (s: String) = new {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
164 |
def | (r: Rexp) = ALT(s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
165 |
def | (r: String) = ALT(s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
166 |
def % = STAR(s)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
167 |
def ~ (r: Rexp) = SEQ(s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
168 |
def ~ (r: String) = SEQ(s, r)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
169 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
170 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
171 |
println("EMAIL:")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
172 |
val LOWERCASE = "abcdefghijklmnopqrstuvwxyz"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
173 |
val DIGITS = "0123456789"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
174 |
val EMAIL = PLUS(RANGE(LOWERCASE + DIGITS + "_" + "." + "-")) ~ "@" ~
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
175 |
PLUS(RANGE(LOWERCASE + DIGITS + "." + "-")) ~ "." ~
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
176 |
NMTIMES(RANGE(LOWERCASE + "."), 2, 6)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
177 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
178 |
val my_email = "christian.urban@kcl.ac.uk"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
179 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
180 |
println(EMAIL);
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
181 |
println(matcher(EMAIL, my_email))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
182 |
println(ders_simp(my_email.toList, EMAIL))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
183 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
184 |
println("COMMENTS:")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
185 |
val ALL = RANGE(LOWERCASE + " ")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
186 |
val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ "*/"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
187 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
188 |
println(matcher(COMMENT, "/**/"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
189 |
println(matcher(COMMENT, "/*foobar_comment*/"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
190 |
println(matcher(COMMENT, "/*test*/test*/"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
191 |
println(matcher(COMMENT, "/*test/*test*/"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
192 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
193 |
println("EVILS:")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
194 |
val EVIL1 = PLUS(PLUS("a" ~ "a" ~ "a"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
195 |
val EVIL2 = PLUS(PLUS("aaaaaaaaaaaaaaaaaaa" ~ OPT("a"))) // 19 as ~ a?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
196 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
197 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
198 |
//40 * aaa matches
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
199 |
//43 * aaa + aa does not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
200 |
//45 * aaa + a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
201 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
202 |
println("EVIL1:")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
203 |
println(matcher(EVIL1, "aaa" * 40))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
204 |
println(matcher(EVIL1, "aaa" * 43 + "aa"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
205 |
println(matcher(EVIL1, "aaa" * 45 + "a"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
206 |
println("EVIL2:")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
207 |
println(matcher(EVIL2, "aaa" * 40))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
208 |
println(matcher(EVIL2, "aaa" * 43 + "aa"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
209 |
println(matcher(EVIL2, "aaa" * 45 + "a"))
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
210 |
|
192
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
211 |
println("TEST for bug pointed out by Filips Ivanovs")
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
212 |
val test = NMTIMES(RANGE(LOWERCASE + "."), 2, 6)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
213 |
|
192
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
214 |
println(matcher(test,"a"))
|
190
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
215 |
println(matcher(test,"ab"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
216 |
println(matcher(test,"abcdef"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
217 |
println(matcher(test,"abc"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
218 |
println(matcher(test,"...."))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
219 |
println(matcher(test,"asdfg"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
220 |
println(matcher(test,"abcdefg"))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
221 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
222 |
println(test)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
223 |
println(ders_simp("a".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
224 |
println(ders_simp("aa".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
225 |
println(ders_simp("aaa".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
226 |
println(ders_simp("aaaa".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
227 |
println(ders_simp("aaaaa".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
228 |
println(ders_simp("aaaaaa".toList, test))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
229 |
println(ders_simp("aaaaaaa".toList, test))
|
208
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
230 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
231 |
def TEST(s: String, r: Rexp) = {
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
232 |
println("Rexp |" + s + "|")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
233 |
println("Derivative:\n" + ders_simp(s.toList, r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
234 |
println("Is Nullable: " + nullable(ders_simp(s.toList, r)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
235 |
println("Is Zeroable: " + zeroable(ders_simp(s.toList, r)))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
236 |
Console.readLine
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
237 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
238 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
239 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
240 |
val ALL2 = "a" | "f"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
241 |
val COMMENT2 = ("/*" ~ NOT(ALL2.% ~ "*/" ~ ALL2.%) ~ "*/")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
242 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
243 |
println("1) TEST TEST")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
244 |
TEST("", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
245 |
TEST("/", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
246 |
TEST("/*", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
247 |
TEST("/*f", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
248 |
TEST("/*f*", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
249 |
TEST("/*f*/", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
250 |
TEST("/*f*/ ", COMMENT2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
251 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
252 |
val ALL3 = "a" | "f"
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
253 |
val COMMENT3 = ("/" ~ NOT(ALL3.% ~ "&" ~ ALL3.%) ~ "&")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
254 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
255 |
println("2) TEST TEST")
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
256 |
TEST("", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
257 |
TEST("/", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
258 |
TEST("/", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
259 |
TEST("/f", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
260 |
TEST("/f&", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
261 |
TEST("/f& ", COMMENT3)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
262 |
|