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