equal
deleted
inserted
replaced
50 // main matcher function |
50 // main matcher function |
51 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
51 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
52 |
52 |
53 //example |
53 //example |
54 //val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
54 //val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
55 //der('b', r) |
55 //der('a', r) |
56 //der('b', r) |
56 //der('b', r) |
57 |
57 |
58 //one or zero |
58 //one or zero |
59 def OPT(r: Rexp) = ALT(r, EMPTY) |
59 def OPT(r: Rexp) = ALT(r, EMPTY) |
60 |
60 |
63 case 0 => EMPTY |
63 case 0 => EMPTY |
64 case 1 => r |
64 case 1 => r |
65 case n => SEQ(r, NTIMES(r, n - 1)) |
65 case n => SEQ(r, NTIMES(r, n - 1)) |
66 } |
66 } |
67 |
67 |
68 def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
68 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
69 |
69 |
70 def time_needed[T](i: Int, code: => T) = { |
70 def time_needed[T](i: Int, code: => T) = { |
71 val start = System.nanoTime() |
71 val start = System.nanoTime() |
72 for (j <- 1 to i) code |
72 for (j <- 1 to i) code |
73 val end = System.nanoTime() |
73 val end = System.nanoTime() |
74 (end - start)/(i * 1.0e9) |
74 (end - start)/(i * 1.0e9) |
75 } |
75 } |
76 |
76 |
77 for (i <- 1 to 29) { |
77 for (i <- 1 to 29) { |
78 println(i + ": " + "%.5f".format(time_needed(1, matcher(RTEST(i), "a" * i)))) |
78 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
79 } |
79 } |
80 |
80 |
81 |
81 |