equal
deleted
inserted
replaced
100 case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2)) |
100 case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2)) |
101 case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2)) |
101 case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2)) |
102 case STAR(r1) => NFA_STAR(thompson(r1)) |
102 case STAR(r1) => NFA_STAR(thompson(r1)) |
103 } |
103 } |
104 |
104 |
105 |
|
106 def tmatches(r: Rexp, s: String) : Boolean = |
|
107 thompson(r).accepts(s.toList) |
|
108 |
|
109 def tmatches2(r: Rexp, s: String) : Boolean = |
|
110 thompson(r).accepts2(s.toList) |
|
111 |
|
112 |
|
113 //optional regular expression (one or zero times) |
105 //optional regular expression (one or zero times) |
114 def OPT(r: Rexp) = ALT(r, ONE) |
106 def OPT(r: Rexp) = ALT(r, ONE) |
115 |
107 |
116 //n-times regular expression (explicitly expanded) |
108 //n-times regular expression (explicitly expanded) |
117 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
109 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
119 case 1 => r |
111 case 1 => r |
120 case n => SEQ(r, NTIMES(r, n - 1)) |
112 case n => SEQ(r, NTIMES(r, n - 1)) |
121 } |
113 } |
122 |
114 |
123 |
115 |
|
116 def tmatches(r: Rexp, s: String) : Boolean = |
|
117 thompson(r).accepts(s.toList) |
|
118 |
|
119 def tmatches2(r: Rexp, s: String) : Boolean = |
|
120 thompson(r).accepts2(s.toList) |
|
121 |
|
122 |
124 // Test Cases |
123 // Test Cases |
|
124 |
125 |
125 |
126 // the evil regular expression a?{n} a{n} |
126 // the evil regular expression a?{n} a{n} |
127 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
127 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
128 |
128 |
129 // the evil regular expression (a*)*b |
129 // the evil regular expression (a*)*b |
133 def time_needed[T](i: Int, code: => T) = { |
133 def time_needed[T](i: Int, code: => T) = { |
134 val start = System.nanoTime() |
134 val start = System.nanoTime() |
135 for (j <- 1 to i) code |
135 for (j <- 1 to i) code |
136 val end = System.nanoTime() |
136 val end = System.nanoTime() |
137 (end - start)/(i * 1.0e9) |
137 (end - start)/(i * 1.0e9) |
138 |
138 } |
139 |
139 |
140 // the size of the NFA can be large, |
140 // the size of the NFA can be large, |
141 // thus slowing down the breadth-first search |
141 // thus slowing down the breadth-first search |
142 |
142 |
143 for (i <- 1 to 10) { |
143 for (i <- 1 to 10) { |