|
153
|
1 |
// Part 1 about Regular Expression Matching
|
|
|
2 |
//==========================================
|
|
|
3 |
|
|
221
|
4 |
// Regular Expressions
|
|
153
|
5 |
abstract class Rexp
|
|
|
6 |
case object ZERO extends Rexp
|
|
|
7 |
case object ONE extends Rexp
|
|
|
8 |
case class CHAR(c: Char) extends Rexp
|
|
228
|
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 |
|
|
153
|
13 |
|
|
228
|
14 |
// some convenience for typing regular expressions
|
|
153
|
15 |
|
|
228
|
16 |
import scala.language.implicitConversions
|
|
|
17 |
import scala.language.reflectiveCalls
|
|
153
|
18 |
|
|
|
19 |
def charlist2rexp(s: List[Char]): Rexp = s match {
|
|
|
20 |
case Nil => ONE
|
|
|
21 |
case c::Nil => CHAR(c)
|
|
|
22 |
case c::s => SEQ(CHAR(c), charlist2rexp(s))
|
|
|
23 |
}
|
|
|
24 |
implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
|
|
|
25 |
|
|
|
26 |
implicit def RexpOps (r: Rexp) = new {
|
|
|
27 |
def | (s: Rexp) = ALT(r, s)
|
|
|
28 |
def % = STAR(r)
|
|
|
29 |
def ~ (s: Rexp) = SEQ(r, s)
|
|
|
30 |
}
|
|
|
31 |
|
|
|
32 |
implicit def stringOps (s: String) = new {
|
|
|
33 |
def | (r: Rexp) = ALT(s, r)
|
|
|
34 |
def | (r: String) = ALT(s, r)
|
|
|
35 |
def % = STAR(s)
|
|
|
36 |
def ~ (r: Rexp) = SEQ(s, r)
|
|
|
37 |
def ~ (r: String) = SEQ(s, r)
|
|
|
38 |
}
|
|
|
39 |
|
|
221
|
40 |
// (1) Complete the function nullable according to
|
|
228
|
41 |
// the definition given in the coursework; this
|
|
153
|
42 |
// function checks whether a regular expression
|
|
221
|
43 |
// can match the empty string and Returns a boolean
|
|
|
44 |
// accordingly.
|
|
153
|
45 |
|
|
228
|
46 |
def nullable (r: Rexp) : Boolean = r match{
|
|
153
|
47 |
case ZERO => false
|
|
|
48 |
case ONE => true
|
|
|
49 |
case CHAR(_) => false
|
|
228
|
50 |
case ALT(a,b)=>nullable(a)||nullable(b)
|
|
|
51 |
case SEQ(a,b) => nullable(a) && nullable(b)
|
|
153
|
52 |
case STAR(_) => true
|
|
|
53 |
}
|
|
|
54 |
|
|
228
|
55 |
|
|
|
56 |
/*val rex = "1~0.%|11"
|
|
|
57 |
|
|
|
58 |
assert(der('1',rex) == SEQ(ONE,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1)))))))))
|
|
|
59 |
|
|
|
60 |
assert(der('1',der('1',rex)) ==
|
|
|
61 |
ALT(SEQ(ZERO,SEQ(CHAR(~),SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),SEQ(CHAR(|),
|
|
|
62 |
SEQ(CHAR(1),CHAR(1)))))))),SEQ(ZERO,SEQ(CHAR(0),SEQ(CHAR(.),SEQ(CHAR(%),
|
|
|
63 |
SEQ(CHAR(|),SEQ(CHAR(1),CHAR(1))))))))*/
|
|
|
64 |
|
|
221
|
65 |
// (2) Complete the function der according to
|
|
153
|
66 |
// the definition given in the coursework; this
|
|
228
|
67 |
// function calculates the derivative of a
|
|
221
|
68 |
// regular expression w.r.t. a character.
|
|
153
|
69 |
|
|
228
|
70 |
def der (c: Char, r: Rexp) : Rexp = r match{
|
|
153
|
71 |
case ZERO => ZERO
|
|
|
72 |
case ONE => ZERO
|
|
228
|
73 |
case CHAR(d) => if (c==d) ONE else ZERO
|
|
|
74 |
case ALT(a,b) => der(c,a)|der(c,b)
|
|
|
75 |
case SEQ(a,b) => if(nullable(a)) {(der(c,a)~b)|der(c,b)}
|
|
|
76 |
else der(c,a)~b
|
|
|
77 |
case STAR(a) => der(c,a)~STAR(a)
|
|
153
|
78 |
}
|
|
|
79 |
|
|
228
|
80 |
println(der('a', ZERO | ONE))// == (ZERO | ZERO)
|
|
|
81 |
println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE)
|
|
|
82 |
println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a')))
|
|
|
83 |
println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a'))))
|
|
|
84 |
|
|
|
85 |
|
|
|
86 |
//ALT(SEQ(ZERO,ZERO),ZERO)
|
|
|
87 |
//ALT(ALT(ZERO,ZERO),ALT(ZERO,ZERO))
|
|
|
88 |
|
|
|
89 |
// * == |
|
|
|
90 |
// + == ~
|
|
221
|
91 |
// (3) Complete the simp function according to
|
|
153
|
92 |
// the specification given in the coursework; this
|
|
221
|
93 |
// function simplifies a regular expression from
|
|
228
|
94 |
// the inside out, like you would simplify arithmetic
|
|
|
95 |
// expressions; however it does not simplify inside
|
|
221
|
96 |
// STAR-regular expressions.
|
|
153
|
97 |
|
|
228
|
98 |
/*
|
|
|
99 |
def simp(r: Rexp) : Rexp = r match{
|
|
|
100 |
case SEQ(ZERO,_) => ZERO
|
|
|
101 |
case SEQ(_,ZERO) => ZERO
|
|
|
102 |
case SEQ(ONE,a) => simp(a)
|
|
|
103 |
case SEQ(a,ONE) => simp(a)
|
|
|
104 |
case ALT(ZERO,a) => simp(a)
|
|
|
105 |
case ALT(a,ZERO) => simp(a)
|
|
|
106 |
case ALT(a,b) => if(a == b) simp(a) else r
|
|
|
107 |
case _ => r
|
|
|
108 |
}*/
|
|
|
109 |
|
|
|
110 |
def simp(r: Rexp) : Rexp = r match{
|
|
|
111 |
case SEQ(a,b) =>{ val sa = simp(a)
|
|
|
112 |
val sb = simp(b)
|
|
|
113 |
if(sa == ZERO || sb == ZERO) ZERO
|
|
|
114 |
else if(sa == ONE) sb
|
|
|
115 |
else if(sb == ONE) sa
|
|
|
116 |
else SEQ(sa,sb)
|
|
|
117 |
}
|
|
|
118 |
case ALT(a,b) =>{ val sa = simp(a)
|
|
|
119 |
val sb = simp(b)
|
|
|
120 |
if(sa == ONE || sb == ONE) ONE
|
|
|
121 |
else if(sa == ZERO) sb
|
|
|
122 |
else if(sb == ZERO) sa
|
|
|
123 |
else if(sa == sb) sa
|
|
|
124 |
else ALT(sa,sb)
|
|
|
125 |
}
|
|
|
126 |
//case STAR(STAR(a)) => simp(STAR(a))
|
|
|
127 |
//case STAR(a) => STAR(simp(a))
|
|
|
128 |
case _ => r
|
|
|
129 |
/*
|
|
|
130 |
case SEQ(ZERO,_) => ZERO
|
|
|
131 |
case SEQ(_,ZERO) => ZERO
|
|
|
132 |
case SEQ(ONE,a) => simp(a)
|
|
|
133 |
case SEQ(a,ONE) => simp(a)
|
|
|
134 |
case SEQ(a,b) => SEQ(simp(a),simp(b))
|
|
|
135 |
//case ALT(ZERO,a) => simp(a)
|
|
|
136 |
case ALT(a,ZERO) => simp(a)
|
|
|
137 |
case ALT(ONE,_) => ONE
|
|
|
138 |
case ALT(_,ONE) => ONE
|
|
|
139 |
case ALT(a,b) => {val sa = simp(a)
|
|
|
140 |
if(sa == simp(b)) sa else r
|
|
|
141 |
}
|
|
|
142 |
case STAR(STAR(a)) => simp(STAR(a))
|
|
|
143 |
case STAR(a) => STAR(simp(a))
|
|
|
144 |
case _ => r*/
|
|
153
|
145 |
}
|
|
|
146 |
|
|
221
|
147 |
|
|
228
|
148 |
/*val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
|
|
|
149 |
println("TEST: " + simp(der('a', der('a', EVIL))))
|
|
|
150 |
println(simp(ONE))
|
|
|
151 |
val r1 = ALT(ZERO,ONE)
|
|
|
152 |
val r2 = SEQ(ONE,ZERO)
|
|
|
153 |
val r3 = SEQ(r1,SEQ(r2,r1))
|
|
|
154 |
println("R1 = " + simp(r1))
|
|
|
155 |
println(simp(r2))
|
|
|
156 |
println(simp(r3))
|
|
|
157 |
*/
|
|
|
158 |
|
|
|
159 |
// (4) Complete the two functions below; the first
|
|
153
|
160 |
// calculates the derivative w.r.t. a string; the second
|
|
|
161 |
// is the regular expression matcher taking a regular
|
|
|
162 |
// expression and a string and checks whether the
|
|
228
|
163 |
// string matches the regular expression
|
|
153
|
164 |
|
|
228
|
165 |
def ders (s: List[Char], r: Rexp ="") : Rexp = s match{
|
|
153
|
166 |
case Nil => r
|
|
228
|
167 |
case a::z => ders(z,simp(der(a,r)))
|
|
153
|
168 |
}
|
|
|
169 |
|
|
228
|
170 |
def matcher(r: Rexp, s: String): Boolean = {
|
|
|
171 |
val derivatives = simp(ders(s.toList,r))
|
|
|
172 |
nullable(derivatives)
|
|
|
173 |
}
|
|
153
|
174 |
|
|
221
|
175 |
// (5) Complete the size function for regular
|
|
228
|
176 |
// expressions according to the specification
|
|
153
|
177 |
// given in the coursework.
|
|
|
178 |
|
|
228
|
179 |
def size(r: Rexp): Int = r match{
|
|
153
|
180 |
case ZERO => 1
|
|
|
181 |
case ONE => 1
|
|
|
182 |
case CHAR(_) => 1
|
|
228
|
183 |
case SEQ(a,b) => 1 + size(a) + size(b)
|
|
|
184 |
case ALT(a,b) => 1 + size(a) + size(b)
|
|
|
185 |
case STAR(a) => 1 + size(a)
|
|
153
|
186 |
}
|
|
|
187 |
|
|
228
|
188 |
println(der('a', ZERO | ONE))// == (ZERO | ZERO)
|
|
|
189 |
println(der('a', (CHAR('a') | ONE) ~ CHAR('a')))// ==ALT((ONE | ZERO) ~ CHAR('a'), ONE)
|
|
|
190 |
println(der('a', STAR(CHAR('a'))))// == (ONE ~ STAR(CHAR('a')))
|
|
|
191 |
println(der('b', STAR(CHAR('a'))))// == (ZERO ~ STAR(CHAR('a'))))
|
|
153
|
192 |
// some testing data
|
|
|
193 |
/*
|
|
228
|
194 |
|
|
|
195 |
assert(matcher(("a" ~ "b") ~ "c", "abc") == true) // => true
|
|
|
196 |
assert(matcher(("a" ~ "b") ~ "c", "ab") == false) // => false
|
|
|
197 |
|
|
153
|
198 |
|
|
|
199 |
// the supposedly 'evil' regular expression (a*)* b
|
|
228
|
200 |
//val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
|
|
|
201 |
|
|
153
|
202 |
|
|
228
|
203 |
assert(matcher(EVIL, "a" * 1000 ++ "b") == true) // => true
|
|
|
204 |
assert(matcher(EVIL, "a" * 1000) == false) // => false
|
|
153
|
205 |
|
|
|
206 |
// size without simplifications
|
|
228
|
207 |
assert("28 " + size(der('a', der('a', EVIL))) ==28)// => 28
|
|
|
208 |
assert("58 " + size(der('a', der('a', der('a', EVIL)))) ==58)// => 58
|
|
153
|
209 |
|
|
|
210 |
// size with simplification
|
|
228
|
211 |
assert("8 " + size(simp(der('a', der('a', EVIL)))) ==8)// => 8
|
|
|
212 |
assert("8 " + size(simp(der('a', der('a', der('a', EVIL))))) ==8) // => 8
|
|
153
|
213 |
|
|
228
|
214 |
*/
|
|
|
215 |
|
|
|
216 |
|
|
|
217 |
/*
|
|
|
218 |
// Python needs around 30 seconds for matching 28 a's with EVIL.
|
|
221
|
219 |
// Java 9 and later increase this to an "astonishing" 40000 a's in
|
|
228
|
220 |
// 30 seconds.
|
|
153
|
221 |
//
|
|
228
|
222 |
// Lets see how long it really takes to match strings with
|
|
|
223 |
// 5 Million a's...it should be in the range of a couple
|
|
|
224 |
// of seconds.
|
|
153
|
225 |
|
|
|
226 |
def time_needed[T](i: Int, code: => T) = {
|
|
|
227 |
val start = System.nanoTime()
|
|
|
228 |
for (j <- 1 to i) code
|
|
|
229 |
val end = System.nanoTime()
|
|
|
230 |
(end - start)/(i * 1.0e9)
|
|
|
231 |
}
|
|
|
232 |
|
|
|
233 |
for (i <- 0 to 5000000 by 500000) {
|
|
|
234 |
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))))
|
|
|
235 |
}
|
|
221
|
236 |
|
|
228
|
237 |
// another "power" test case
|
|
|
238 |
simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE
|
|
221
|
239 |
|
|
|
240 |
// the Iterator produces the rexp
|
|
|
241 |
//
|
|
|
242 |
// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)
|
|
|
243 |
//
|
|
228
|
244 |
// where SEQ is nested 50 times.
|
|
|
245 |
|
|
153
|
246 |
*/
|