equal
deleted
inserted
replaced
1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
3 import scala.annotation.tailrec |
3 import scala.annotation.tailrec |
4 import scala.io.Source |
4 import scala.io.Source |
|
5 import scala.util._ |
5 |
6 |
6 abstract class Rexp |
7 abstract class Rexp |
7 case object ZERO extends Rexp |
8 case object ZERO extends Rexp |
8 case object ONE extends Rexp |
9 case object ONE extends Rexp |
9 case class CHARS(f: Char => Boolean) extends Rexp |
10 case class CHARS(f: Char => Boolean) extends Rexp |
155 def lex(r: Rexp, s: List[Char]) : Val = s match { |
156 def lex(r: Rexp, s: List[Char]) : Val = s match { |
156 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
157 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
157 case c::cs => inj(r, c, lex(der(c, r), cs)) |
158 case c::cs => inj(r, c, lex(der(c, r), cs)) |
158 } |
159 } |
159 |
160 |
160 import scala.util._ |
161 |
|
162 |
161 def lexing(r: Rexp, s: String) : Try[Val] = Try(lex(r, s.toList)) |
163 def lexing(r: Rexp, s: String) : Try[Val] = Try(lex(r, s.toList)) |
162 |
164 |
163 |
165 |
164 // some "rectification" functions for simplification |
166 // some "rectification" functions for simplification |
165 def F_ID(v: Val): Val = v |
167 def F_ID(v: Val): Val = v |
216 val (r_simp, f_simp) = simp(der(c, r)) |
218 val (r_simp, f_simp) = simp(der(c, r)) |
217 inj(r, c, f_simp(lex_simp(r_simp, cs))) |
219 inj(r, c, f_simp(lex_simp(r_simp, cs))) |
218 } |
220 } |
219 } |
221 } |
220 |
222 |
221 def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
223 def lexing_simp(r: Rexp, s: String) : Try[Val] = Try(lex_simp(r, s.toList)) |
222 |
224 |
223 |
225 |
224 // Some Tests |
226 // Some Tests |
225 //============ |
227 //============ |
226 |
228 |
247 // Some more Tests |
249 // Some more Tests |
248 //================= |
250 //================= |
249 val ALL = CHARS((c) => true) |
251 val ALL = CHARS((c) => true) |
250 val reg = ALL.% ~ "a" ~ NTIMES(ALL, 3) ~ "bc" |
252 val reg = ALL.% ~ "a" ~ NTIMES(ALL, 3) ~ "bc" |
251 |
253 |
252 println(lexing(reg, "axaybzbc")) // true |
254 println(lexing(reg, "axaybzbc")) // true |
253 println(lexing(reg, "aaaaxaybzbc")) // true |
255 println(lexing(reg, "aaaaxaybzbc")) // true |
254 println(nullable(ders("axaybzbd".toList, reg))) // false |
256 |
255 println(lexing(reg, "axaybzbd")) // false |
257 println(nullable(ders("axaybzbd".toList, reg))) // false |
|
258 println(lexing(reg, "axaybzbd")) // false |
256 |
259 |
257 |
260 |
258 |
261 |
259 |
262 |
260 // Two Simple Tests for the While Language |
263 // Two Simple Tests for the While Language |
300 |
303 |
301 |
304 |
302 println("prog0 test") |
305 println("prog0 test") |
303 |
306 |
304 val prog0 = """read n""" |
307 val prog0 = """read n""" |
305 println(env(lexing_simp(WHILE_REGS, prog0))) |
308 println(env(lexing_simp(WHILE_REGS, prog0).get)) |
306 |
309 |
307 println("prog1 test") |
310 println("prog1 test") |
308 |
311 |
309 val prog1 = """read n; write (n)""" |
312 val prog1 = """read n; write (n)""" |
310 println(env(lexing_simp(WHILE_REGS, prog1))) |
313 println(env(lexing_simp(WHILE_REGS, prog1).get)) |
311 |
314 |
312 |
315 |
313 // Bigger Test |
316 // Bigger Test |
314 //============= |
317 //============= |
315 val prog2 = """ |
318 val prog2 = """ |
325 if isprime == 1 then write i else skip; |
328 if isprime == 1 then write i else skip; |
326 i := i + 1 |
329 i := i + 1 |
327 }""" |
330 }""" |
328 |
331 |
329 println("prog2 test - tokens") |
332 println("prog2 test - tokens") |
330 println(env(lexing_simp(WHILE_REGS, prog2))) |
333 println(env(lexing_simp(WHILE_REGS, prog2).get)) |
|
334 |
|
335 |
|
336 // replicate prog2 |
|
337 |
|
338 println("prog2 replicated test") |
|
339 for (i <- 1 to 88 by 5) { |
|
340 println(i + ": " + "%.5f".format(time_needed(2, lexing_simp(WHILE_REGS, prog2 * i)))) |
|
341 } |
331 |
342 |
332 |
343 |
333 val prog3 = """ |
344 val prog3 = """ |
334 write "fib"; |
345 write "fib"; |
335 read n; |
346 read n; |
344 write "result"; |
355 write "result"; |
345 write minus2 |
356 write minus2 |
346 """ |
357 """ |
347 |
358 |
348 println("prog3 test - tokens") |
359 println("prog3 test - tokens") |
349 println(env(lexing_simp(WHILE_REGS, prog3))) |
360 println(env(lexing_simp(WHILE_REGS, prog3).get)) |
350 |
361 |
351 println("prog2 replicated test") |
362 |
352 |
|
353 for (i <- 1 to 88) { |
|
354 println(i + ": " + "%.5f".format(time_needed(2, lexing_simp(WHILE_REGS, prog2 * i)))) |
|
355 } |
|
356 |
363 |
357 |
364 |
358 // Sulzmann's tests |
365 // Sulzmann's tests |
359 //================== |
366 //================== |
360 |
367 |
375 //======================= |
382 //======================= |
376 |
383 |
377 val reWord = CHARS("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" contains _) |
384 val reWord = CHARS("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" contains _) |
378 |
385 |
379 val reWordStar = STAR(reWord) |
386 val reWordStar = STAR(reWord) |
380 val reWordPlus = reWord ~ reWordStar |
387 val reWordPlus = PLUS(reWord) |
381 val optionSet1 = "-" | "+" | "." |
388 val optionSet1 = "-" | "+" | "." |
382 val optionSet2 = "-" | "." |
389 val optionSet2 = "-" | "." |
383 val atTheRate = "@" |
390 val atTheRate = "@" |
384 val period = "." |
391 val period = "." |
385 val optionSet3 = "," | ";" |
392 val optionSet3 = "," | ";" |