236 Write("minus1")) // write minus1 |
236 Write("minus1")) // write minus1 |
237 |
237 |
238 |
238 |
239 compile_run(fib_test, "fib") |
239 compile_run(fib_test, "fib") |
240 |
240 |
|
241 |
241 val arr_test = |
242 val arr_test = |
242 List(Assign("x", Num(0)), |
243 List(Array("a", 10), // a[10] |
243 Array("a", 10)) |
244 Array("b", 2), // b[2] |
244 |
245 AssignA("a", Num(0), Num(10)), // a[0] := 10 |
245 compile_block(arr_test, Map())._1.mkString |
246 Assign("x", Ref("a", Num(0))), // x := a[0] |
246 compile_run(arr_test, "arr") |
247 Write("x"), // write x |
247 |
248 AssignA("b", Num(1), Num(5)), // b[1] := 5 |
248 |
249 Assign("x", Ref("b", Num(1))), // x := b[1] |
249 val arr_test = |
250 Write("x")) // write x |
250 List(Array("a", 10), |
251 |
251 Array("b", 2), |
252 compile_run(arr_test, "a") |
252 AssignA("a", Num(0), Num(10)), |
253 |
253 Assign("x", Ref("a", Num(0))), |
254 |
254 Write("x"), |
255 //==================== |
255 AssignA("b", Num(1), Num(5)), |
256 // Parser Combinators |
256 Assign("x", Ref("b", Num(1))), |
257 //==================== |
257 Write("x")) |
258 |
258 |
259 import scala.language.implicitConversions |
259 //compile_run(arr_test, "a") |
260 import scala.language.reflectiveCalls |
|
261 |
|
262 |
|
263 abstract class Parser[I <% Seq[_], T] { |
|
264 def parse(ts: I): Set[(T, I)] |
|
265 |
|
266 def parse_all(ts: I) : Set[T] = |
|
267 for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head |
|
268 } |
|
269 |
|
270 class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] { |
|
271 def parse(sb: I) = |
|
272 for ((head1, tail1) <- p.parse(sb); |
|
273 (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2) |
|
274 } |
|
275 |
|
276 class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] { |
|
277 def parse(sb: I) = p.parse(sb) ++ q.parse(sb) |
|
278 } |
|
279 |
|
280 class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] { |
|
281 def parse(sb: I) = |
|
282 for ((head, tail) <- p.parse(sb)) yield (f(head), tail) |
|
283 } |
|
284 |
|
285 |
|
286 import scala.util.matching.Regex |
|
287 case class RegexParser(reg: Regex) extends Parser[String, String] { |
|
288 def parse(sb: String) = reg.findPrefixMatchOf(sb) match { |
|
289 case None => Set() |
|
290 case Some(m) => Set((m.matched, m.after.toString)) |
|
291 } |
|
292 } |
|
293 |
|
294 def StringParser(s: String) = RegexParser(Regex.quote(s).r) |
|
295 |
|
296 |
|
297 implicit def string2parser(s : String) = StringParser(s) |
|
298 |
|
299 implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new { |
|
300 def | (q : => Parser[I, T]) = new AltParser[I, T](p, q) |
|
301 def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f) |
|
302 def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q) |
|
303 } |
|
304 |
|
305 implicit def StringOps(s: String) = new { |
|
306 def | (q : => Parser[String, String]) = new AltParser[String, String](s, q) |
|
307 def | (r: String) = new AltParser[String, String](s, r) |
|
308 def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f) |
|
309 def ~[S](q : => Parser[String, S]) = |
|
310 new SeqParser[String, String, S](s, q) |
|
311 def ~ (r: String) = |
|
312 new SeqParser[String, String, String](s, r) |
|
313 } |
|
314 |
|
315 |
|
316 val NumParser = RegexParser("[0-9]+".r) ==> (s => s.toInt : Int) |
|
317 val IdParser = RegexParser("[a-z][a-z,0-9]*".r) |
|
318 |
|
319 |
|
320 |
|
321 // Grammar Rules |
|
322 |
|
323 lazy val AExp: Parser[String, AExp] = |
|
324 (Te ~ "+" ~ AExp) ==> { case ((x, _), z) => Aop("+", x, z):AExp } | |
|
325 (Te ~ "-" ~ AExp) ==> { case ((x, _), z) => Aop("-", x, z):AExp } | Te |
|
326 lazy val Te: Parser[String, AExp] = |
|
327 (Fa ~ "*" ~ Te) ==> { case ((x, _), z) => Aop("*", x, z):AExp } | Fa |
|
328 lazy val Fa: Parser[String, AExp] = |
|
329 ("(" ~ AExp ~ ")") ==> { case ((_, y), _) => y } | |
|
330 (IdParser ~ "[" ~ AExp ~ "]") ==> { case (((x, _), y), _) => Ref(x, y) } | |
|
331 IdParser ==> Var | |
|
332 NumParser ==> Num |
|
333 |
|
334 // boolean expressions |
|
335 lazy val BExp: Parser[String, BExp] = |
|
336 (AExp ~ "=" ~ AExp) ==> { case ((x, y), z) => Bop("=", x, z):BExp } | |
|
337 (AExp ~ "!=" ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z):BExp } | |
|
338 (AExp ~ "<" ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z):BExp } | |
|
339 (AExp ~ ">" ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x):BExp } | |
|
340 ("true" ==> ((_) => True:BExp )) | |
|
341 ("false" ==> ((_) => False:BExp )) | |
|
342 ("(" ~ BExp ~ ")") ==> { case ((x, y), z) => y} |
|
343 |
|
344 lazy val Stmt: Parser[String, Stmt] = |
|
345 ("skip" ==> (_ => Skip: Stmt)) | |
|
346 (IdParser ~ ":=" ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } | |
|
347 (IdParser ~ "[" ~ AExp ~ "]" ~ ":=" ~ AExp) ==> { |
|
348 case (((((x, y), z), v), w), u) => AssignA(x, z, u): Stmt } | |
|
349 ("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block) ==> |
|
350 { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } | |
|
351 ("while" ~ BExp ~ "do" ~ Block) ==> { case (((x, y), z), w) => While(y, w) } | |
|
352 ("new" ~ IdParser ~ "[" ~ NumParser ~ "]") ==> { case ((((x, y), z), u), v) => Array(y, u) } | |
|
353 ("write" ~ IdParser) ==> { case (_, y) => Write(y) } |
|
354 |
|
355 lazy val Stmts: Parser[String, Block] = |
|
356 (Stmt ~ ";" ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } | |
|
357 (Stmt ==> ((s) => List(s) : Block)) |
|
358 |
|
359 |
|
360 lazy val Block: Parser[String, Block] = |
|
361 ("{" ~ Stmts ~ "}") ==> { case ((x, y), z) => y} | |
|
362 (Stmt ==> (s => List(s))) |
|
363 |
|
364 Stmts.parse_all("x2:=5+a") |
|
365 Stmts.parse_all("x2:=5+a[3+a]") |
|
366 Stmts.parse_all("a[x2+3]:=5+a[3+a]") |
|
367 Block.parse_all("{x:=5;y:=8}") |
|
368 Block.parse_all("if(false)then{x:=5}else{x:=10}") |
|
369 |
|
370 |
|
371 |
|
372 val fib = """ |
|
373 n := 10; |
|
374 minus1 := 0; |
|
375 minus2 := 1; |
|
376 temp:=0; |
|
377 while (n > 0) do { |
|
378 temp := minus2; |
|
379 minus2 := minus1 + minus2; |
|
380 minus1 := temp; |
|
381 n := n - 1}; |
|
382 result := minus2; |
|
383 write result |
|
384 """.replaceAll("\\s+", "") |
|
385 |
|
386 val fib_prog = Stmts.parse_all(fib).toList |
|
387 //compile_run(fib_prog.head, "fib") |
|
388 |
|
389 |
|
390 // BF |
|
391 |
|
392 // simple instructions |
|
393 def instr(c: Char) : String = c match { |
|
394 case '>' => "ptr := ptr + 1;" |
|
395 case '<' => "ptr := ptr - 1;" |
|
396 case '+' => "field[ptr] := field[ptr] + 1;" |
|
397 case '-' => "field[ptr] := field[ptr] - 1;" |
|
398 case '.' => "x := field[ptr]; write x;" |
|
399 //case ',' => "XXX" // "ptr = getchar();\n" |
|
400 case '[' => "while (field[ptr] != 0) do {" |
|
401 case ']' => "skip};" |
|
402 case _ => "" |
|
403 } |
|
404 |
|
405 def instrs(prog: String) : String = |
|
406 prog.toList.map(instr).mkString |
|
407 |
|
408 |
|
409 def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { |
|
410 case (Nil, acc) => acc |
|
411 case (c :: cs, Nil) => splice(cs, List((c, 1))) |
|
412 case (c :: cs, (d, n) :: acc) => |
|
413 if (c == d) splice(cs, (c, n + 1) :: acc) |
|
414 else splice(cs, (c, 1) :: (d, n) :: acc) |
|
415 } |
|
416 |
|
417 def spl(s: String) = splice(s.toList, Nil).reverse |
|
418 |
|
419 def instr2(c: Char, n: Int) : String = c match { |
|
420 case '>' => "ptr := ptr + " + n.toString + ";" |
|
421 case '<' => "ptr := ptr - " + n.toString + ";" |
|
422 case '+' => "field[ptr] := field[ptr] + " + n.toString + ";" |
|
423 case '-' => "field[ptr] := field[ptr] - " + n.toString + ";" |
|
424 case '.' => "x := field[ptr]; write x;" //* n |
|
425 //case ',' => "*ptr = getchar();\n" * n |
|
426 case '[' => "while (field[ptr] != 0) do {" * n |
|
427 case ']' => "skip};" * n |
|
428 case _ => "" |
|
429 } |
|
430 |
|
431 def instrs2(prog: String) : String = |
|
432 spl(prog).map{ case (c, n) => instr2(c, n) }.mkString |
|
433 |
|
434 |
|
435 def bf_str(prog: String) : String = { |
|
436 "\n" ++ |
|
437 //"new field[30000];\n" ++ |
|
438 "ptr := 15000;" ++ |
|
439 instrs2(prog) ++ |
|
440 "skip" |
|
441 } |
|
442 |
|
443 def bf_run(prog: String, name: String) = { |
|
444 println("BF processing start") |
|
445 val bf_string = bf_str(prog).replaceAll("\\s", "") |
|
446 println(s"BF parsing start (string length ${bf_string.length})") |
|
447 val bf_prog = Stmts.parse_all(bf_string).toList.head |
|
448 println("BF Compile start") |
|
449 compile_run(Array("field", 30000) :: bf_prog, name) |
|
450 } |
|
451 |
|
452 |
|
453 |
|
454 val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ |
|
455 ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< |
|
456 ]>.>+[>>]>+]""" |
|
457 |
|
458 bf_run(bf1, "sier") |
|
459 |
|
460 bf_run("""++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++ |
|
461 ..+++.>>.<-.<.+++.------.--------.>>+.>++.""", "hello") |
|
462 |
|
463 bf_run("""+++++++++++ |
|
464 >+>>>>++++++++++++++++++++++++++++++++++++++++++++ |
|
465 >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> |
|
466 +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- |
|
467 <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< |
|
468 -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] |
|
469 >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ |
|
470 +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ |
|
471 ++++++++++++++++++++++++++++++++++++++++++++.[-]<< |
|
472 <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< |
|
473 [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]""", "fibs") |