59 case class APRED(bs: Bits, f: Char => Boolean) extends ARexp |
40 case class APRED(bs: Bits, f: Char => Boolean) extends ARexp |
60 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
41 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
61 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
42 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
62 case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
43 case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
63 |
44 |
64 |
45 // abbreviations |
65 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2)) |
46 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2)) |
66 |
47 |
67 abstract class Val |
48 abstract class Val |
68 case object Empty extends Val |
49 case object Empty extends Val |
69 case class Chr(c: Char) extends Val |
50 case class Chr(c: Char) extends Val |
70 case class Sequ(v1: Val, v2: Val) extends Val |
51 case class Sequ(v1: Val, v2: Val) extends Val |
71 case class Left(v: Val) extends Val |
52 case class Left(v: Val) extends Val |
72 case class Right(v: Val) extends Val |
53 case class Right(v: Val) extends Val |
73 case class Stars(vs: List[Val]) extends Val |
54 case class Stars(vs: List[Val]) extends Val |
74 case class Rec(x: String, v: Val) extends Val |
55 case class Rec(x: String, v: Val) extends Val |
75 case class Pos(i: Int, v: Val) extends Val |
56 |
76 case object Prd extends Val |
57 |
77 |
58 |
78 // some convenience for typing in regular expressions |
59 // some convenience for typing in regular expressions |
79 def charlist2rexp(s : List[Char]): Rexp = s match { |
60 def charlist2rexp(s : List[Char]): Rexp = s match { |
80 case Nil => ONE |
61 case Nil => ONE |
81 case c::Nil => CHAR(c) |
62 case c::Nil => CHAR(c) |
122 case STAR(r) => ASTAR(Nil, internalise(r)) |
103 case STAR(r) => ASTAR(Nil, internalise(r)) |
123 case RECD(x, r) => internalise(r) |
104 case RECD(x, r) => internalise(r) |
124 } |
105 } |
125 |
106 |
126 internalise(("a" | "ab") ~ ("b" | "")) |
107 internalise(("a" | "ab") ~ ("b" | "")) |
127 val action_stack = scala.collection.mutable.ArrayBuffer.empty[Action] |
108 |
128 val next_stack = scala.collection.mutable.ArrayBuffer.empty[Int] |
109 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
129 val regx_stack = scala.collection.mutable.ArrayBuffer.empty[Rexp] |
110 case (ONE, bs) => (Empty, bs) |
130 val pv_stack = scala.collection.mutable.ArrayBuffer.empty[PartialValue] |
111 case (PRED(f), C(c)::bs) => (Chr(c), bs) |
131 var top = 0 |
112 case (ALTS(r::Nil), bs) => decode_aux(r, bs) |
132 //st is the global var stack, made with a linked list? |
113 case (ALTS(rs), bs) => bs match { |
133 @tailrec |
114 case Z::bs1 => { |
134 def decode_stack(sp: Int, bs: Bits): Unit = { |
115 val (v, bs2) = decode_aux(rs.head, bs1) |
135 if(action_stack.isEmpty){ |
116 (Left(v), bs2) |
136 return |
|
137 } |
|
138 val action = action_stack.last |
|
139 action_stack.trimEnd(1) |
|
140 val r = regx_stack.last |
|
141 regx_stack.trimEnd(1) |
|
142 if(action == ST)//we have the rest of the star to finish(ST -> STAR) |
|
143 { |
|
144 bs match { |
|
145 case Z::bs => {//pv -> partial value Each grid in a stack does not hold a whole value but a partial one. |
|
146 pv_stack(sp) = ENDSTS |
|
147 if(next_stack.isEmpty) |
|
148 return |
|
149 val n = next_stack.last |
|
150 next_stack.trimEnd(1) |
|
151 decode_stack(n, bs) |
|
152 } |
117 } |
153 case S::bs => { |
118 case S::bs1 => { |
154 for(i <- 0 to next_stack.length - 1){ |
119 val (v, bs2) = decode_aux(ALTS(rs.tail), bs1) |
155 next_stack(i) = next_stack(i) + 1 |
120 (Right(v), bs2) |
156 } |
|
157 next_stack += (sp + 1) |
|
158 regx_stack += r |
|
159 action_stack += ST |
|
160 pv_stack.insert(sp + 1, Plhdr) |
|
161 action_stack += NST |
|
162 regx_stack += r |
|
163 decode_stack(sp, bs) |
|
164 } |
121 } |
165 case _ => println("Sequence not decodable") |
122 } |
166 } |
123 case (SEQ(r1, r2), bs) => { |
167 |
124 val (v1, bs1) = decode_aux(r1, bs) |
168 } |
125 val (v2, bs2) = decode_aux(r2, bs1) |
169 else if(action == NST){ |
126 (Sequ(v1, v2), bs2) |
170 (r, bs) match{ |
127 } |
171 case (ONE, bs) => { |
128 case (STAR(r1), S::bs) => { |
172 pv_stack(sp) = Empt |
129 val (v, bs1) = decode_aux(r1, bs) |
173 if(next_stack.isEmpty) |
130 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
174 return |
131 (Stars(v::vs), bs2) |
175 val n = next_stack.last |
132 } |
176 next_stack.trimEnd(1) |
133 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
177 decode_stack(n, bs) |
134 case (RECD(x, r1), bs) => { |
178 } |
135 val (v, bs1) = decode_aux(r1, bs) |
179 case (PRED(f), C(c)::bs) => { |
136 (Rec(x, v), bs1) |
180 pv_stack(sp) = Ch(c) |
137 } |
181 if(next_stack.isEmpty) |
138 } |
182 return |
139 |
183 val n = next_stack.last |
|
184 next_stack.trimEnd(1) |
|
185 decode_stack(n, bs) |
|
186 } |
|
187 case (ALTS(rs), Z::bs1) => { |
|
188 pv_stack(sp) = ALTSTART |
|
189 pv_stack.insert(sp + 1, LEF) |
|
190 pv_stack.insert(sp + 2, Plhdr) |
|
191 pv_stack.insert(sp + 3, ALTEND) |
|
192 for(i <- 0 to next_stack.length - 1){ |
|
193 next_stack(i) = next_stack(i) + 3 |
|
194 } |
|
195 regx_stack += rs.head |
|
196 action_stack += NST |
|
197 decode_stack(sp + 2, bs1) |
|
198 } |
|
199 case (ALTS(rs), S::bs1) => { |
|
200 pv_stack(sp) = ALTSTART |
|
201 pv_stack.insert(sp + 1, RIG) |
|
202 pv_stack.insert(sp + 2, Plhdr) |
|
203 for(i <- 0 to next_stack.length - 1){ |
|
204 next_stack(i) = next_stack(i) + 2 |
|
205 } |
|
206 regx_stack += ALTS(rs.tail) |
|
207 action_stack += AL |
|
208 decode_stack(sp + 2, bs1) |
|
209 } |
|
210 /* |
|
211 val le = rs.length |
|
212 val det = bs.take(le - 1) |
|
213 val chosen = det.indexWhere(_ == Z) |
|
214 action_stack += NST |
|
215 pv_stack.insert(sp + 1, Plhdr) |
|
216 for(i <- 0 to next_stack.length - 1){ |
|
217 next_stack(i) = next_stack(i) + 1 |
|
218 } |
|
219 if(chosen == -1){ |
|
220 pv_stack(sp) = Posi(le) |
|
221 regx_stack += rs(le - 1) |
|
222 decode_stack(sp + 1, bs.drop(le - 1)) |
|
223 } |
|
224 else{ |
|
225 pv_stack(sp) = Posi(chosen + 1) |
|
226 regx_stack += rs(chosen) |
|
227 decode_stack(sp + 1, bs.drop(chosen + 1)) |
|
228 }*/ |
|
229 case (SEQ(r1, r2), bs) => { |
|
230 action_stack += NST |
|
231 action_stack += NST |
|
232 for(i <- 0 to next_stack.length - 1){ |
|
233 next_stack(i) = next_stack(i) + 2 |
|
234 } |
|
235 next_stack += (sp + 2) |
|
236 regx_stack += r2 |
|
237 regx_stack += r1 |
|
238 pv_stack.insert(sp + 1, Plhdr) |
|
239 pv_stack.insert(sp + 2, Plhdr) |
|
240 pv_stack(sp) = Seque |
|
241 decode_stack(sp + 1, bs) |
|
242 } |
|
243 case (STAR(r1), S::bs) => { |
|
244 action_stack += ST |
|
245 regx_stack += r1 |
|
246 action_stack += NST |
|
247 regx_stack += r1 |
|
248 for(i <- 0 to next_stack.length - 1){ |
|
249 next_stack(i) = next_stack(i) + 2 |
|
250 } |
|
251 next_stack += sp + 2 |
|
252 pv_stack(sp) = STS |
|
253 pv_stack.insert(sp + 1, Plhdr) |
|
254 pv_stack.insert(sp + 1, Plhdr) |
|
255 decode_stack(sp + 1, bs) |
|
256 } |
|
257 case (STAR(_), Z::bs) => { |
|
258 pv_stack(sp) = STS |
|
259 pv_stack.insert(sp + 1, ENDSTS) |
|
260 if(next_stack.isEmpty) |
|
261 return |
|
262 for(i <- 0 to next_stack.length - 1){ |
|
263 next_stack(i) = next_stack(i) + 1 |
|
264 } |
|
265 val n = next_stack.last |
|
266 next_stack.trimEnd(1) |
|
267 decode_stack(n, bs) |
|
268 } |
|
269 case (RECD(x, r1), bs) => { |
|
270 pv_stack(sp) = RECRD(x) |
|
271 pv_stack.insert(sp + 1, Plhdr) |
|
272 for(i <- 0 to next_stack.length - 1){ |
|
273 next_stack(i) = next_stack(i) + 1 |
|
274 } |
|
275 action_stack += NST |
|
276 regx_stack += r1 |
|
277 decode_stack(sp + 1, bs) |
|
278 }//shouldn't go beyond this point |
|
279 case (_, _) => println("Error with NST") |
|
280 } |
|
281 } |
|
282 else{//action is AL |
|
283 r match { |
|
284 case (ALTS(r1::Nil)) => { |
|
285 pv_stack.insert(sp + 1, ALTEND) |
|
286 for(i <- 0 to next_stack.length - 1){ |
|
287 next_stack(i) = next_stack(i) + 1 |
|
288 } |
|
289 action_stack += NST |
|
290 regx_stack += r1 |
|
291 decode_stack(sp, bs) |
|
292 } |
|
293 case (ALTS(rs)) => { |
|
294 bs match { |
|
295 case (Z::bs1) => { |
|
296 pv_stack(sp) = LEF |
|
297 pv_stack.insert(sp + 1, ALTEND) |
|
298 pv_stack.insert(sp + 1, Plhdr) |
|
299 for(i <- 0 to next_stack.length - 1){ |
|
300 next_stack(i) = next_stack(i) + 2 |
|
301 } |
|
302 regx_stack += rs.head |
|
303 action_stack += NST |
|
304 decode_stack(sp + 1, bs1) |
|
305 } |
|
306 case (S::bs2) => { |
|
307 pv_stack(sp) = RIG |
|
308 pv_stack.insert(sp + 1, Plhdr) |
|
309 for(i <- 0 to next_stack.length - 1){ |
|
310 next_stack(i) = next_stack(i) + 1 |
|
311 } |
|
312 regx_stack += ALTS(rs.tail) |
|
313 action_stack += AL |
|
314 decode_stack(sp + 1, bs2) |
|
315 } |
|
316 case _ => println("Not decodable") |
|
317 } |
|
318 } |
|
319 case (rs) => println(r,bs) |
|
320 } |
|
321 } |
|
322 } |
|
323 //advantage: may decode chunks of bits |
|
324 def decode(r: Rexp, bs: Bits) = { |
|
325 action_stack.clear() |
|
326 next_stack.clear() |
|
327 regx_stack.clear() |
|
328 pv_stack.clear() |
|
329 |
|
330 action_stack += NST |
|
331 regx_stack += r |
|
332 pv_stack += Plhdr |
|
333 |
|
334 decode_stack(0, bs) |
|
335 } |
|
336 /* |
|
337 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match { |
140 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match { |
338 case (v, Nil) => v |
141 case (v, Nil) => v |
339 case _ => throw new Exception("Not decodable") |
142 case _ => throw new Exception("Not decodable") |
340 } |
143 } |
341 */ |
144 |
342 |
145 |
343 //erase function: extracts the regx from Aregex |
146 //erase function: extracts the regx from Aregex |
344 def erase(r:ARexp): Rexp = r match{ |
147 def erase(r:ARexp): Rexp = r match{ |
345 case AZERO => ZERO |
148 case AZERO => ZERO |
346 case AONE(_) => ONE |
149 case AONE(_) => ONE |
526 // tokenise(r, fromFile(name)) |
316 // tokenise(r, fromFile(name)) |
527 |
317 |
528 |
318 |
529 // Some Tests |
319 // Some Tests |
530 //============ |
320 //============ |
531 def compute_and_print(r: Rexp, s: String){ |
321 |
532 //println(r) |
|
533 //println(s) |
|
534 lexing_simp(r, s) |
|
535 println(pv_stack) |
|
536 } |
|
537 println("simple tests:") |
322 println("simple tests:") |
538 /* |
323 |
539 println(lexing_simp((SYM.%), "abcd")) |
324 println(lexing_simp((SYM.%), "abcd")) |
540 println(lexing_simp(((SYM.%) | NUM), "12345")) |
325 println(lexing_simp(((SYM.%) | NUM), "12345")) |
541 println(lexing_simp((WHILE_REGS), "abcd")) |
326 println(lexing_simp((WHILE_REGS), "abcd")) |
542 println(lexing_simp((WHILE_REGS), "12345")) |
327 println(lexing_simp((WHILE_REGS), "12345")) |
543 println(lexing_simp((WHILE_REGS), "\nwrite \"Fib\";")) |
328 println(lexing_simp((WHILE_REGS), """write "Fib";""")) |
544 */ |
329 |
545 compute_and_print((SYM.%), "abcd") |
330 |
546 compute_and_print(((SYM.%) | NUM), "12345") |
|
547 compute_and_print((WHILE_REGS), "abcd") |
|
548 compute_and_print((WHILE_REGS), "12345") |
|
549 compute_and_print((WHILE_REGS), "\nwrite \"Fib\";") |
|
550 |
331 |
551 def time[T](code: => T) = { |
332 def time[T](code: => T) = { |
552 val start = System.nanoTime() |
333 val start = System.nanoTime() |
553 val result = code |
334 val result = code |
554 val end = System.nanoTime() |
335 val end = System.nanoTime() |