180 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
180 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
181 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
181 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
182 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
182 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
183 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
183 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
184 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
184 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
185 case (CHAR(d), Empty) => Chr(c) |
185 case (CHAR(d), Empty) => Chr(d) |
186 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
186 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
187 } |
187 } |
|
188 |
|
189 def prj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
|
190 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(prj(r, c, v1)::vs) |
|
191 case (SEQ(r1, r2), Sequ(v1, v2)) => |
|
192 if (flatten(v1) == "") Right(prj(r2, c, v2)) |
|
193 else { if (nullable(r1)) Left(Sequ(prj(r1, c, v1), v2)) |
|
194 else Sequ(prj(r1, c, v1), v2) |
|
195 } |
|
196 case (ALT(r1, r2), Left(v1)) => Left(prj(r1, c, v1)) |
|
197 case (ALT(r1, r2), Right(v2)) => Right(prj(r2, c, v2)) |
|
198 case (CHAR(d), _) => Empty |
|
199 case (RECD(x, r1), _) => Rec(x, prj(r1, c, v)) |
|
200 } |
|
201 |
188 |
202 |
189 // main lexing function (produces a value) |
203 // main lexing function (produces a value) |
190 def lex(r: Rexp, s: List[Char]) : Val = s match { |
204 def lex(r: Rexp, s: List[Char]) : Val = s match { |
191 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
205 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
192 case c::cs => inj(r, c, lex(der(c, r), cs)) |
206 case c::cs => inj(r, c, lex(der(c, r), cs)) |
253 } |
267 } |
254 } |
268 } |
255 |
269 |
256 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
270 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
257 |
271 |
258 lexing_sim(("a" + "ab") | ("b" + ""), "ab") |
272 lexing(("a" | "ab") ~ ("b" | ""), "ab") |
|
273 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") |
|
274 |
|
275 |
|
276 |
259 // brute force search infrastructure |
277 // brute force search infrastructure |
260 |
278 |
261 // enumerates regular expressions until a certain depth |
279 // enumerates regular expressions until a certain depth |
262 def enum(n: Int, s: String) : Set[Rexp] = n match { |
280 def enum(n: Int, s: String) : Set[Rexp] = n match { |
263 case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR) |
281 case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR) |
292 case (Sequ(v1, v2), Sequ(v3, v4)) if (v1 != v3) => ord(v1, v3) |
310 case (Sequ(v1, v2), Sequ(v3, v4)) if (v1 != v3) => ord(v1, v3) |
293 case _ => false |
311 case _ => false |
294 } |
312 } |
295 |
313 |
296 // exhaustively tests values of a regular expression |
314 // exhaustively tests values of a regular expression |
|
315 def vfilter1(f: Rexp => Val => Boolean)(r: Rexp) : Set[(Rexp, Val)] = { |
|
316 val vs = values(r) |
|
317 for (v <- vs; if (f(r)(v))) yield (r, v) |
|
318 } |
|
319 |
297 def vfilter2(f: Rexp => Val => Val => Boolean)(r: Rexp) : Set[(Rexp, Val, Val)] = { |
320 def vfilter2(f: Rexp => Val => Val => Boolean)(r: Rexp) : Set[(Rexp, Val, Val)] = { |
298 val vs = values(r) |
321 val vs = values(r) |
299 for (v1 <- vs; v2 <- vs; if (f(r)(v1)(v2))) yield (r, v1, v2) |
322 for (v1 <- vs; v2 <- vs; if (f(r)(v1)(v2))) yield (r, v1, v2) |
300 } |
323 } |
301 |
324 |
308 enum(3, "a").size |
331 enum(3, "a").size |
309 enum(2, "ab").size |
332 enum(2, "ab").size |
310 enum(2, "abc").size |
333 enum(2, "abc").size |
311 //enum(3, "ab").size |
334 //enum(3, "ab").size |
312 |
335 |
|
336 // test for inj/prj |
|
337 def injprj_test(r:Rexp)(v:Val) : Boolean = |
|
338 if (flatten(v) != "") (inj(r, 'a', prj(r, 'a', v)) != v) else false |
|
339 |
|
340 val injprj_tst = enum(2, "ab").flatMap(vfilter1(injprj_test)) |
|
341 val injprj_smallest = injprj_tst.toList.sortWith { (x,y) => size(x._1) < size(y._1) }.head |
|
342 |
|
343 prj(CHAR('b'), 'a', Chr('b')) |
|
344 inj(CHAR('b'), 'a', Empty) |
|
345 |
|
346 prj(SEQ(ALT(ONE,ONE),CHAR('a')), 'a', Sequ(Right(Empty),Chr('a'))) |
|
347 inj(SEQ(ALT(ONE,ONE),CHAR('a')), 'a', Right(Empty)) |
313 |
348 |
314 // tests for totality |
349 // tests for totality |
315 def totality_test(r: Rexp)(v1: Val)(v2: Val) : Boolean = |
350 def totality_test(r: Rexp)(v1: Val)(v2: Val) : Boolean = |
316 !(ord(v1, v2) || ord(v2, v1)) |
351 !(ord(v1, v2) || ord(v2, v1)) |
317 |
352 |