72 def OPT(r: Rexp) = ALT(r, ONE) |
72 def OPT(r: Rexp) = ALT(r, ONE) |
73 |
73 |
74 //evil regular expressions |
74 //evil regular expressions |
75 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
75 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
76 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
76 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
77 |
77 val EVIL3 = SEQ(STAR(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a')))), CHAR('b')) |
78 |
78 |
79 def time_needed[T](i: Int, code: => T) = { |
79 def time_needed[T](i: Int, code: => T) = { |
80 val start = System.nanoTime() |
80 val start = System.nanoTime() |
81 for (j <- 1 to i) code |
81 for (j <- 1 to i) code |
82 val end = System.nanoTime() |
82 val end = System.nanoTime() |
92 for (i <- 1 to 8001 by 1000) { |
92 for (i <- 1 to 8001 by 1000) { |
93 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) |
93 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) |
94 } |
94 } |
95 |
95 |
96 //test: (a*)* b |
96 //test: (a*)* b |
97 for (i <- 1 to 7000001 by 500000) { |
97 for (i <- 1 to 5000001 by 500000) { |
98 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
98 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
99 } |
99 } |
100 |
100 |
101 for (i <- 1 to 7000001 by 500000) { |
101 for (i <- 1 to 5000001 by 500000) { |
102 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
102 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
103 } |
103 } |
104 |
104 |
|
105 |
|
106 val r0 = simp(der('a', EVIL3)) |
|
107 val r1 = simp(der('a', r0)) |
|
108 val r2 = simp(der('a', r1)) |
|
109 val r3 = simp(der('a', r2)) |
|
110 val r4 = simp(der('a', r3)) |
|
111 val r5 = simp(der('a', r4)) |
|
112 val r6 = simp(der('a', r5)) |
|
113 |
|
114 //test: (a|aa)* b |
|
115 for (i <- 1 to 7001 by 500) { |
|
116 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i ++ "c")))) |
|
117 } |
|
118 |