# HG changeset patch # User Christian Urban # Date 1593461134 -3600 # Node ID f345e89895f53841a5f0a1dec91542dbf255189a # Parent 61a936be50c43c0b4cc129ce94e4440de5609803 updated diff -r 61a936be50c4 -r f345e89895f5 progs/lexer/lexer.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/lexer/lexer.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,308 @@ +// A simple lexer inspired by work of Sulzmann & Lu +//================================================== +// +// Call the test cases with +// +// amm lexer.sc small +// amm lexer.sc fib +// amm lexer.sc loops +// +// amm lexer.sc all + + +// regular expressions including records +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class RECD(x: String, r: Rexp) extends Rexp + // records for extracting strings or tokens + +// values +abstract class Val +case object Empty extends Val +case class Chr(c: Char) extends Val +case class Sequ(v1: Val, v2: Val) extends Val +case class Left(v: Val) extends Val +case class Right(v: Val) extends Val +case class Stars(vs: List[Val]) extends Val +case class Rec(x: String, v: Val) extends Val + +// some convenience for typing in regular expressions +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +def charlist2rexp(s : List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s : String) : Rexp = + charlist2rexp(s.toList) + +implicit def RexpOps(r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps(s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) + def $ (r: Rexp) = RECD(s, r) +} + +def nullable(r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case RECD(_, r1) => nullable(r1) +} + +def der(c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r) => SEQ(der(c, r), STAR(r)) + case RECD(_, r1) => der(c, r1) +} + + +// extracts a string from value +def flatten(v: Val) : String = v match { + case Empty => "" + case Chr(c) => c.toString + case Left(v) => flatten(v) + case Right(v) => flatten(v) + case Sequ(v1, v2) => flatten(v1) ++ flatten(v2) + case Stars(vs) => vs.map(flatten).mkString + case Rec(_, v) => flatten(v) +} + + +// extracts an environment from a value; +// used for tokenising a string +def env(v: Val) : List[(String, String)] = v match { + case Empty => Nil + case Chr(c) => Nil + case Left(v) => env(v) + case Right(v) => env(v) + case Sequ(v1, v2) => env(v1) ::: env(v2) + case Stars(vs) => vs.flatMap(env) + case Rec(x, v) => (x, flatten(v))::env(v) +} + + +// The injection and mkeps part of the lexer +//=========================================== + +def mkeps(r: Rexp) : Val = r match { + case ONE => Empty + case ALT(r1, r2) => + if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) + case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) + case STAR(r) => Stars(Nil) + case RECD(x, r) => Rec(x, mkeps(r)) +} + +def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { + case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) + case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) + case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) + case (CHAR(d), Empty) => Chr(c) + case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) +} + +// some "rectification" functions for simplification +def F_ID(v: Val): Val = v +def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) +def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) +def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Right(v) => Right(f2(v)) + case Left(v) => Left(f1(v)) +} +def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) +} +def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = + (v:Val) => Sequ(f1(Empty), f2(v)) +def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = + (v:Val) => Sequ(f1(v), f2(Empty)) +def F_RECD(f: Val => Val) = (v:Val) => v match { + case Rec(x, v) => Rec(x, f(v)) +} +def F_ERROR(v: Val): Val = throw new Exception("error") + +// simplification +def simp(r: Rexp): (Rexp, Val => Val) = r match { + case ALT(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (ZERO, _) => (r2s, F_RIGHT(f2s)) + case (_, ZERO) => (r1s, F_LEFT(f1s)) + case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) + else (ALT (r1s, r2s), F_ALT(f1s, f2s)) + } + } + case SEQ(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (ZERO, _) => (ZERO, F_ERROR) + case (_, ZERO) => (ZERO, F_ERROR) + case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) + case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) + case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) + } + } + case r => (r, F_ID) +} + +// lexing functions including simplification +def lex_simp(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else + { throw new Exception("lexing error") } + case c::cs => { + val (r_simp, f_simp) = simp(der(c, r)) + inj(r, c, f_simp(lex_simp(r_simp, cs))) + } +} + +def lexing_simp(r: Rexp, s: String) = + env(lex_simp(r, s.toList)) + + +// The Lexing Rules for the WHILE Language + +def PLUS(r: Rexp) = r ~ r.% + +def Range(s : List[Char]) : Rexp = s match { + case Nil => ZERO + case c::Nil => CHAR(c) + case c::s => ALT(CHAR(c), Range(s)) +} +def RANGE(s: String) = Range(s.toList) + +val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_") +val DIGIT = RANGE("0123456789") +val ID = SYM ~ (SYM | DIGIT).% +val NUM = PLUS(DIGIT) +val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" +val SEMI: Rexp = ";" +val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">" +val WHITESPACE = PLUS(" " | "\n" | "\t") +val RPAREN: Rexp = "{" +val LPAREN: Rexp = "}" +val STRING: Rexp = "\"" ~ SYM.% ~ "\"" + + +val WHILE_REGS = (("k" $ KEYWORD) | + ("i" $ ID) | + ("o" $ OP) | + ("n" $ NUM) | + ("s" $ SEMI) | + ("str" $ STRING) | + ("p" $ (LPAREN | RPAREN)) | + ("w" $ WHITESPACE)).% + + +// Two Simple While Tests +//======================== + +@doc("small tests") +@main +def small() = { + + val prog0 = """read n""" + println(s"test: $prog0") + println(lexing_simp(WHILE_REGS, prog0)) + + val prog1 = """read n; write n""" + println(s"test: $prog1") + println(lexing_simp(WHILE_REGS, prog1)) +} + +// Bigger Tests +//============== + +// escapes strings and prints them out as "", "\n" and so on +def esc(raw: String): String = { + import scala.reflect.runtime.universe._ + Literal(Constant(raw)).toString +} + +def escape(tks: List[(String, String)]) = + tks.map{ case (s1, s2) => (s1, esc(s2))} + + +val prog2 = """ +write "Fib"; +read n; +minus1 := 0; +minus2 := 1; +while n > 0 do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 +}; +write "Result"; +write minus2 +""" + +@doc("Fibonacci test") +@main +def fib() = { + println("lexing fib program") + println(escape(lexing_simp(WHILE_REGS, prog2)).mkString("\n")) +} + + +val prog3 = """ +start := 1000; +x := start; +y := start; +z := start; +while 0 < x do { + while 0 < y do { + while 0 < z do { + z := z - 1 + }; + z := start; + y := y - 1 + }; + y := start; + x := x - 1 +} +""" + +@doc("Loops test") +@main +def loops() = { + println("lexing Loops") + println(escape(lexing_simp(WHILE_REGS, prog3)).mkString("\n")) +} + + + + +@doc("All tests.") +@main +def all() = { small(); fib() ; loops() } \ No newline at end of file diff -r 61a936be50c4 -r f345e89895f5 progs/lexer/token.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/lexer/token.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,56 @@ +// This produces more meaningful tokens and +// also filters out comments and whitespaces +// +// call with +// +// amm token.sc +// + +// load the lexer +import $file.lexer +import lexer._ + + +// The tokens for the WHILE language + +abstract class Token +case object T_SEMI extends Token +case object T_LPAREN extends Token +case object T_RPAREN extends Token +case class T_ID(s: String) extends Token +case class T_OP(s: String) extends Token +case class T_NUM(n: Int) extends Token +case class T_KWD(s: String) extends Token +case class T_STR(s: String) extends Token + +val token : PartialFunction[(String, String), Token] = { + case ("s", _) => T_SEMI + case ("p", "{") => T_LPAREN + case ("p", "}") => T_RPAREN + case ("i", s) => T_ID(s) + case ("o", s) => T_OP(s) + case ("n", s) => T_NUM(s.toInt) + case ("k", s) => T_KWD(s) + case ("str", s) => T_STR(s) +} + +// by using collect we filter out all unwanted tokens +def tokenise(s: String) : List[Token] = + lexing_simp(WHILE_REGS, s).collect(token) + + + + +@doc("Tokens for fib and loops programs.") +@main +def main() = { + println("Fib program") + println(tokenise(prog2)) + println("Loops program") + println(tokenise(prog3)) + + for (i <- 0 to 20 by 5) { + println(f"$i%2.0f: ${time(tokenise(prog3 * i))._2}") + } + +} \ No newline at end of file diff -r 61a936be50c4 -r f345e89895f5 progs/lexer/token2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/lexer/token2.scala Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,463 @@ +import scala.language.implicitConversions +import scala.language.reflectiveCalls +import scala.annotation.tailrec + +abstract class Rexp +case object NULL extends Rexp +case object EMPTY extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class RECD(x: String, r: Rexp) extends Rexp +case class CRANGE(cs: String) extends Rexp +case class PLUS(r: Rexp) extends Rexp +case class OPT(r: Rexp) extends Rexp +case class NTIMES(r: Rexp, n: Int) extends Rexp + +abstract class Val +case object Empty extends Val +case class Chr(c: Char) extends Val +case class Seq(v1: Val, v2: Val) extends Val +case class Left(v: Val) extends Val +case class Right(v: Val) extends Val +case class Stars(vs: List[Val]) extends Val +case class Rec(x: String, v: Val) extends Val + +// some convenience for typing in regular expressions +def charlist2rexp(s : List[Char]): Rexp = s match { + case Nil => EMPTY + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) + +implicit def RexpOps(r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps(s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) + def $ (r: Rexp) = RECD(s, r) +} + +// nullable function: tests whether the regular +// expression can recognise the empty string +def nullable (r: Rexp) : Boolean = r match { + case NULL => false + case EMPTY => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case RECD(_, r) => nullable(r) + case CRANGE(_) => false + case PLUS(r) => nullable(r) + case OPT(_) => true + case NTIMES(r, n) => if (n == 0) true else nullable(r) +} + +// derivative of a regular expression w.r.t. a character +def der (c: Char, r: Rexp) : Rexp = r match { + case NULL => NULL + case EMPTY => NULL + case CHAR(d) => if (c == d) EMPTY else NULL + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r) => SEQ(der(c, r), STAR(r)) + case RECD(_, r1) => der(c, r1) + case CRANGE(cs) => if (cs.contains(c)) EMPTY else NULL + case PLUS(r) => SEQ(der(c, r), STAR(r)) + case OPT(r) => ALT(der(c, r), NULL) + case NTIMES(r, n) => if (n == 0) NULL else der(c, SEQ(r, NTIMES(r, n - 1))) +} + +// derivative w.r.t. a string (iterates der) +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, der(c, r)) +} + +// extracts a string from value +def flatten(v: Val) : String = v match { + case Empty => "" + case Chr(c) => c.toString + case Left(v) => flatten(v) + case Right(v) => flatten(v) + case Seq(v1, v2) => flatten(v1) + flatten(v2) + case Stars(vs) => vs.map(flatten).mkString + case Rec(_, v) => flatten(v) +} + +// extracts an environment from a value +def env(v: Val) : List[(String, String)] = v match { + case Empty => Nil + case Chr(c) => Nil + case Left(v) => env(v) + case Right(v) => env(v) + case Seq(v1, v2) => env(v1) ::: env(v2) + case Stars(vs) => vs.flatMap(env) + case Rec(x, v) => (x, flatten(v))::env(v) +} + +// injection part +def mkeps(r: Rexp) : Val = r match { + case EMPTY => Empty + case ALT(r1, r2) => + if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) + case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) + case STAR(r) => Stars(Nil) + case RECD(x, r) => Rec(x, mkeps(r)) + case PLUS(r) => Stars(List(mkeps(r))) + case OPT(_) => Right(Empty) + case NTIMES(r, n) => if (n == 0) Stars(Nil) else Stars(Nil.padTo(n, mkeps(r))) + case _ => { println ("r : " + r.toString); + throw new Exception("mkeps error")} +} + + +def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { + case (STAR(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (SEQ(r1, r2), Seq(v1, v2)) => Seq(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Left(Seq(v1, v2))) => Seq(inj(r1, c, v1), v2) + case (SEQ(r1, r2), Right(v2)) => Seq(mkeps(r1), inj(r2, c, v2)) + case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) + case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) + case (CHAR(_), Empty) => Chr(c) + case (CRANGE(_), Empty) => Chr(c) + case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) + case (PLUS(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (OPT(r), Left(v1)) => Left(inj(r, c, v1)) + case (NTIMES(r, n), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) + case (NTIMES(r, n), Left(Seq(v1, Stars(vs)))) => Stars(inj(r, c, v1)::vs) + case (NTIMES(r, n), Right(Stars(v::vs))) => Stars(mkeps(r)::inj(r, c, v)::vs) + case _ => { println ("r : " + r.toString + " v: " + v.toString); + throw new Exception("inj error")} +} + +// main lexing function (produces a value) +def lex(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") + case c::cs => inj(r, c, lex(der(c, r), cs)) +} + +def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) + +lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab") + +lexing(OPT("ab"), "ab") + +lexing(NTIMES("1", 3), "111") +lexing(NTIMES("1" | EMPTY, 3), "11") + +// some "rectification" functions for simplification +def F_ID(v: Val): Val = v +def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) +def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) +def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Right(v) => Right(f2(v)) + case Left(v) => Left(f1(v)) +} +def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { + case Seq(v1, v2) => Seq(f1(v1), f2(v2)) +} +def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = + (v:Val) => Seq(f1(Empty), f2(v)) +def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = + (v:Val) => Seq(f1(v), f2(Empty)) +def F_RECD(f: Val => Val) = (v:Val) => v match { + case Rec(x, v) => Rec(x, f(v)) +} +def F_ERROR(v: Val): Val = throw new Exception("error") + +// simplification of regular expressions returning also an +// rectification function; no simplification under STAR +def simp(r: Rexp): (Rexp, Val => Val) = r match { + case ALT(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (NULL, _) => (r2s, F_RIGHT(f2s)) + case (_, NULL) => (r1s, F_LEFT(f1s)) + case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) + else (ALT (r1s, r2s), F_ALT(f1s, f2s)) + } + } + case SEQ(r1, r2) => { + val (r1s, f1s) = simp(r1) + val (r2s, f2s) = simp(r2) + (r1s, r2s) match { + case (NULL, _) => (NULL, F_ERROR) + case (_, NULL) => (NULL, F_ERROR) + case (EMPTY, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) + case (_, EMPTY) => (r1s, F_SEQ_Empty2(f1s, f2s)) + case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) + } + } + case RECD(x, r1) => { + val (r1s, f1s) = simp(r1) + (RECD(x, r1s), F_RECD(f1s)) + } + case r => (r, F_ID) +} + +def lex_simp(r: Rexp, s: List[Char]) : Val = s match { + case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") + case c::cs => { + val (r_simp, f_simp) = simp(der(c, r)) + inj(r, c, f_simp(lex_simp(r_simp, cs))) + } +} + +def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) + +lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") + +lexing_simp(OPT("ab"), "ab") + +// Lexing Rules for a Small While Language + +val SYM = CRANGE("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") +val DIGIT = CRANGE("0123456789") +val ID = SYM ~ (SYM | DIGIT).% +val NUM = PLUS(DIGIT) +val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" +val SEMI: Rexp = ";" +val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" +val WHITESPACE = PLUS(" " | "\n" | "\t") +val RPAREN: Rexp = ")" +val LPAREN: Rexp = "(" +val BEGIN: Rexp = "{" +val END: Rexp = "}" +val STRING: Rexp = "\"" ~ SYM.% ~ "\"" + + +val WHILE_REGS = (("k" $ KEYWORD) | + ("i" $ ID) | + ("o" $ OP) | + ("n" $ NUM) | + ("s" $ SEMI) | + ("str" $ STRING) | + ("p" $ (LPAREN | RPAREN)) | + ("b" $ (BEGIN | END)) | + ("w" $ WHITESPACE)).% + +// filters out all white spaces +def tokenise(r: Rexp, s: String) = + env(lexing_simp(r, s)).filterNot { (s) => s._1 == "w"} + +// Testing +//============ + +def time[T](code: => T) = { + val start = System.nanoTime() + val result = code + val end = System.nanoTime() + println((end - start)/1.0e9) + result +} + +println(lexing_simp(OPT("1"), "1")) +println(lexing_simp(OPT("1"), "")) +println(ders("111".toList, NTIMES("1",3))) +println(lexing_simp(NTIMES("1",3), "111")) + +val r1 = ("a" | "ab") ~ ("bcd" | "c") +println(lexing(r1, "abcd")) + +val r2 = ("" | "a") ~ ("ab" | "b") +println(lexing(r2, "ab")) + + +// Two Simple While Tests +//======================== +println("prog0 test") + +val prog0 = """read n""" +println(env(lexing_simp(WHILE_REGS, prog0))) + +println("prog1 test") + +val prog1 = """read n; write (n)""" +println(env(lexing_simp(WHILE_REGS, prog1))) + + +// Big Test +//========== + +def escape(raw: String): String = { + import scala.reflect.runtime.universe._ + Literal(Constant(raw)).toString +} + +val prog2 = """ +write "Fib"; +read n; +minus1 := 0; +minus2 := 1; +while n > 0 do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 +}; +write "Result"; +write minus2 +""" + +val prog3 = """ +start := 1000; +x := start; +y := start; +z := start; +while 0 < x do { + while 0 < y do { + while 0 < z do { + z := z - 1 + }; + z := start; + y := y - 1 + }; + y := start; + x := x - 1 +} +""" + + +println("Tokens") +println(tokenise(WHILE_REGS, prog2).mkString("\n")) + +val fib_tokens = tokenise(WHILE_REGS, prog2) +fib_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n") + + +val test_tokens = tokenise(WHILE_REGS, prog3) +test_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n") + + +/* +for (i <- 1 to 120 by 10) { + print(i.toString + ": ") + time(lexing_simp(WHILE_REGS, prog2 * i)) +} +*/ + +val toks_fib = + List(("k","write"), + ("str","Fib"), + ("s",";"), + ("k","read"), + ("i","n"), + ("s",";"), + ("i","minus1"), + ("o",":="), + ("n","0"), + ("s",";"), + ("i","minus2"), + ("o",":="), + ("n","1"), + ("s",";"), + ("k","while"), + ("i","n"), + ("o",">"), + ("n","0"), + ("k","do"), + ("b","{"), + ("i","temp"), + ("o",":="), + ("i","minus2"), + ("s",";"), + ("i","minus2"), + ("o",":="), + ("i","minus1"), + ("o","+"), + ("i","minus2"), + ("s",";"), + ("i","minus1"), + ("o",":="), + ("i","temp"), + ("s",";"), + ("i","n"), + ("o",":="), + ("i","n"), + ("o","-"), + ("n","1"), + ("b","}"), + ("s",";"), + ("k","write"), + ("str","Result"), + ("s",";"), + ("k","write"), + ("i","minus2")) + +val toks_test = + List(("i","start"), + ("o",":="), + ("n","1000"), + ("s",";"), + ("i","x"), + ("o",":="), + ("i","start"), + ("s",";"), + ("i","y"), + ("o",":="), + ("i","start"), + ("s",";"), + ("i","z"), + ("o",":="), + ("i","start"), + ("s",";"), + ("k","while"), + ("n","0"), + ("o","<"), + ("i","x"), + ("k","do"), + ("b","{"), + ("k","while"), + ("n","0"), + ("o","<"), + ("i","y"), + ("k","do"), + ("b","{"), + ("k","while"), + ("n","0"), + ("o","<"), + ("i","z"), + ("k","do"), + ("b","{"), + ("i","z"), + ("o",":="), + ("i","z"), + ("o","-"), + ("n","1"), + ("b","}"), + ("s",";"), + ("i","z"), + ("o",":="), + ("i","start"), + ("s",";"), + ("i","y"), + ("o",":="), + ("i","y"), + ("o","-"), + ("n","1"), + ("b","}"), + ("s",";"), + ("i","y"), + ("o",":="), + ("i","start"), + ("s",";"), + ("i","x"), + ("o",":="), + ("i","x"), + ("o","-"), + ("n","1"), + ("b","}")) diff -r 61a936be50c4 -r f345e89895f5 progs/lexer/toks.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/lexer/toks.scala Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,136 @@ +abstract class Token +case object T_SEMI extends Token +case object T_LPAREN extends Token +case object T_RPAREN extends Token +case class T_ID(s: String) extends Token +case class T_OP(s: String) extends Token +case class T_NUM(n: Int) extends Token +case class T_KWD(s: String) extends Token +case class T_STR(s: String) extends Token + + +// Loops program +//=============== + +/* +start := 1000; +x := start; +y := start; +z := start; +while 0 < x do { + while 0 < y do { + while 0 < z do { z := z - 1 }; + z := start; + y := y - 1 + }; + y := start; + x := x - 1 +} +*/ + +val loops = + List(T_ID("start"), T_OP(":="), T_NUM(1000), T_SEMI, T_ID("x"), T_OP(":="), + T_ID("start"), T_SEMI, T_ID("y"), T_OP(":="), T_ID("start"), T_SEMI, + T_ID("z"), T_OP(":="), T_ID("start"), T_SEMI, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("x"), T_KWD("do"), T_LPAREN, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("y"), T_KWD("do"), T_LPAREN, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("z"), T_KWD("do"), T_LPAREN, T_ID("z"), T_OP(":="), + T_ID("z"), T_OP("-"), T_NUM(1), T_RPAREN, T_SEMI, T_ID("z"), T_OP(":="), + T_ID("start"), T_SEMI, T_ID("y"), T_OP(":="), T_ID("y"), T_OP("-"), + T_NUM(1), T_RPAREN, T_SEMI, T_ID("y"), T_OP(":="), T_ID("start"), + T_SEMI, T_ID("x"), T_OP(":="), T_ID("x"), T_OP("-"), T_NUM(1), T_RPAREN) + + +// Fib program +//============= + +/* +write "Fib"; +read n; +minus1 := 0; +minus2 := 1; +while n > 0 do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 +}; +write "Result"; +write minus2 +*/ + +val fib = + List(T_KWD("write"), T_STR("Fib"), T_SEMI, T_KWD("read"), T_ID("n"), + T_SEMI, T_ID("minus1"), T_OP(":="), T_NUM(0), T_SEMI, T_ID("minus2"), + T_OP(":="), T_NUM(1), T_SEMI, T_KWD("while"), T_ID("n"), T_OP(">"), + T_NUM(0), T_KWD("do"), T_LPAREN, T_ID("temp"), T_OP(":="), + T_ID("minus2"), T_SEMI, T_ID("minus2"), T_OP(":="), T_ID("minus1"), + T_OP("+"), T_ID("minus2"), T_SEMI, T_ID("minus1"), T_OP(":="), + T_ID("temp"), T_SEMI, T_ID("n"), T_OP(":="), T_ID("n"), T_OP("-"), + T_NUM(1), T_RPAREN, T_SEMI, T_KWD("write"), T_STR("Result"), T_SEMI, + T_KWD("write"), T_ID("minus2")) + + + +// Factors program +//================= + +/* +write "Input n please"; +read n; +write "The factors of n are"; +f := 2; +while n != 1 do { + while (n / f) * f == n do { + write f; + n := n / f + }; + f := f + 1 +} +*/ + +val factors = + List(T_KWD("write"), T_STR("Input n please"), T_SEMI, T_KWD("read"), + T_ID("n"), T_SEMI, T_KWD("write"), T_STR("The factors of n are"), + T_SEMI, T_ID("f"), T_OP(":="), T_NUM(2), T_SEMI, T_KWD("while"), + T_ID("n"), T_OP("!="), T_NUM(1), T_KWD("do"), T_LPAREN, + T_KWD("while"), T_ID("n"), T_OP("/"), T_ID("f"), T_OP("*"), + T_ID("f"), T_OP("=="), T_ID("n"), T_KWD("do"), T_LPAREN, + T_KWD("write"), T_ID("f"), T_SEMI, T_ID("n"), T_OP(":="), + T_ID("n"), T_OP("/"), T_ID("f"), T_RPAREN, T_SEMI, T_ID("f"), + T_OP(":="), T_ID("f"), T_OP("+"), T_NUM(1), T_RPAREN) + + +// Primes program +//================ + +/* +end := 100; +n := 2; +while (n < end) do { + f := 2; + tmp := 0; + while ((f < n / 2 + 1) && (tmp == 0)) do { + if ((n / f) * f == n) then { tmp := 1 } else { skip }; + f := f + 1 + }; + if (tmp == 0) then { write(n) } else { skip }; + n := n + 1 +} +*/ + +val primes = + List(T_ID("end"), T_OP(":="), T_NUM(100), T_SEMI, T_ID("n"), T_OP(":="), + T_NUM(2), T_SEMI, T_KWD("while"), T_ID("n"), T_OP("<"), T_ID("end"), + T_KWD("do"), T_LPAREN, T_ID("f"), T_OP(":="), T_NUM(2), T_SEMI, + T_ID("tmp"), T_OP(":="), T_NUM(0), T_SEMI, T_KWD("while"), T_ID("f"), + T_OP("<"), T_ID("n"), T_OP("/"), T_NUM(2), T_OP("+"), T_NUM(1), + T_OP("&&"), T_ID("tmp"), T_OP("=="), T_NUM(0), T_KWD("do"), T_LPAREN, + T_KWD("if"), T_ID("n"), T_OP("/"), T_ID("f"), T_OP("*"), T_ID("f"), + T_OP("=="), T_ID("n"), T_KWD("then"), T_LPAREN, T_ID("tmp"), T_OP(":="), + T_NUM(1), T_RPAREN, T_KWD("else"), T_LPAREN, T_KWD("skip"), T_RPAREN, + T_SEMI, T_ID("f"), T_OP(":="), T_ID("f"), T_OP("+"), T_NUM(1), + T_RPAREN, T_SEMI, T_KWD("if"), T_ID("tmp"), T_OP("=="), T_NUM(0), + T_KWD("then"), T_LPAREN, T_KWD("write"), T_ID("n"), T_RPAREN, + T_KWD("else"), T_LPAREN, T_KWD("skip"), T_RPAREN, T_SEMI, T_ID("n"), + T_OP(":="), T_ID("n"), T_OP("+"), T_NUM(1), T_RPAREN) diff -r 61a936be50c4 -r f345e89895f5 progs/lexer/toks.scala.orig --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/lexer/toks.scala.orig Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,138 @@ +abstract class Token +case object T_SEMI extends Token +case object T_LPAREN extends Token +case object T_RPAREN extends Token +case class T_ID(s: String) extends Token +case class T_OP(s: String) extends Token +case class T_NUM(n: Int) extends Token +case class T_KWD(s: String) extends Token +case class T_STR(s: String) extends Token + + +// Loops program +//=============== + +/* +start := 1000; +x := start; +y := start; +z := start; +while 0 < x do { + while 0 < y do { + while 0 < z do { z := z - 1 }; + z := start; + y := y - 1 + }; + y := start; + x := x - 1 +} +*/ + +val loops = + List(T_ID("start"), T_OP(":="), T_NUM(1000), T_SEMI, T_ID("x"), T_OP(":="), + T_ID("start"), T_SEMI, T_ID("y"), T_OP(":="), T_ID("start"), T_SEMI, + T_ID("z"), T_OP(":="), T_ID("start"), T_SEMI, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("x"), T_KWD("do"), T_LPAREN, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("y"), T_KWD("do"), T_LPAREN, T_KWD("while"), T_NUM(0), + T_OP("<"), T_ID("z"), T_KWD("do"), T_LPAREN, T_ID("z"), T_OP(":="), + T_ID("z"), T_OP("-"), T_NUM(1), T_RPAREN, T_SEMI, T_ID("z"), T_OP(":="), + T_ID("start"), T_SEMI, T_ID("y"), T_OP(":="), T_ID("y"), T_OP("-"), + T_NUM(1), T_RPAREN, T_SEMI, T_ID("y"), T_OP(":="), T_ID("start"), + T_SEMI, T_ID("x"), T_OP(":="), T_ID("x"), T_OP("-"), T_NUM(1), T_RPAREN) + + + + +// Fib program +//============= + +/* +write "Fib"; +read n; +minus1 := 0; +minus2 := 1; +while n > 0 do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1 +}; +write "Result"; +write minus2 +*/ + +val fib = + List(T_KWD("write"), T_STR("Fib"), T_SEMI, T_KWD("read"), T_ID("n"), + T_SEMI, T_ID("minus1"), T_OP(":="), T_NUM(0), T_SEMI, T_ID("minus2"), + T_OP(":="), T_NUM(1), T_SEMI, T_KWD("while"), T_ID("n"), T_OP(">"), + T_NUM(0), T_KWD("do"), T_LPAREN, T_ID("temp"), T_OP(":="), + T_ID("minus2"), T_SEMI, T_ID("minus2"), T_OP(":="), T_ID("minus1"), + T_OP("+"), T_ID("minus2"), T_SEMI, T_ID("minus1"), T_OP(":="), + T_ID("temp"), T_SEMI, T_ID("n"), T_OP(":="), T_ID("n"), T_OP("-"), + T_NUM(1), T_RPAREN, T_SEMI, T_KWD("write"), T_STR("Result"), T_SEMI, + T_KWD("write"), T_ID("minus2")) + + + +// Factors program +//================= + +/* +write "Input n please"; +read n; +write "The factors of n are"; +f := 2; +while n != 1 do { + while (n / f) * f == n do { + write f; + n := n / f + }; + f := f + 1 +} +*/ + +val factors = + List(T_KWD("write"), T_STR("Input n please"), T_SEMI, T_KWD("read"), + T_ID("n"), T_SEMI, T_KWD("write"), T_STR("The factors of n are"), + T_SEMI, T_ID("f"), T_OP(":="), T_NUM(2), T_SEMI, T_KWD("while"), + T_ID("n"), T_OP("!="), T_NUM(1), T_KWD("do"), T_LPAREN, + T_KWD("while"), T_ID("n"), T_OP("/"), T_ID("f"), T_OP("*"), + T_ID("f"), T_OP("=="), T_ID("n"), T_KWD("do"), T_LPAREN, + T_KWD("write"), T_ID("f"), T_SEMI, T_ID("n"), T_OP(":="), + T_ID("n"), T_OP("/"), T_ID("f"), T_RPAREN, T_SEMI, T_ID("f"), + T_OP(":="), T_ID("f"), T_OP("+"), T_NUM(1), T_RPAREN) + + +// Primes program +//================ + +/* +end := 100; +n := 2; +while (n < end) do { + f := 2; + tmp := 0; + while ((f < n / 2 + 1) && (tmp == 0)) do { + if ((n / f) * f == n) then { tmp := 1 } else { skip }; + f := f + 1 + }; + if (tmp == 0) then { write(n) } else { skip }; + n := n + 1 +} +*/ + +val primes = + List(T_ID("end"), T_OP(":="), T_NUM(100), T_SEMI, T_ID("n"), T_OP(":="), + T_NUM(2), T_SEMI, T_KWD("while"), T_ID("n"), T_OP("<"), T_ID("end"), + T_KWD("do"), T_LPAREN, T_ID("f"), T_OP(":="), T_NUM(2), T_SEMI, + T_ID("tmp"), T_OP(":="), T_NUM(0), T_SEMI, T_KWD("while"), T_ID("f"), + T_OP("<"), T_ID("n"), T_OP("/"), T_NUM(2), T_OP("+"), T_NUM(1), + T_OP("&&"), T_ID("tmp"), T_OP("=="), T_NUM(0), T_KWD("do"), T_LPAREN, + T_KWD("if"), T_ID("n"), T_OP("/"), T_ID("f"), T_OP("*"), T_ID("f"), + T_OP("=="), T_ID("n"), T_KWD("then"), T_LPAREN, T_ID("tmp"), T_OP(":="), + T_NUM(1), T_RPAREN, T_KWD("else"), T_LPAREN, T_KWD("skip"), T_RPAREN, + T_SEMI, T_ID("f"), T_OP(":="), T_ID("f"), T_OP("+"), T_NUM(1), + T_RPAREN, T_SEMI, T_KWD("if"), T_ID("tmp"), T_OP("=="), T_NUM(0), + T_KWD("then"), T_LPAREN, T_KWD("write"), T_ID("n"), T_RPAREN, + T_KWD("else"), T_LPAREN, T_KWD("skip"), T_RPAREN, T_SEMI, T_ID("n"), + T_OP(":="), T_ID("n"), T_OP("+"), T_NUM(1), T_RPAREN) diff -r 61a936be50c4 -r f345e89895f5 progs/matcher/re1.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/matcher/re1.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,171 @@ +// A simple matcher for basic regular expressions +// +// Call the test cases with X = {1,2,3} +// +// amm re1.sc testX +// +// or +// +// amm re1.sc all + +// regular expressions +abstract class Rexp +case object ZERO extends Rexp // matches nothing +case object ONE extends Rexp // matches an empty string +case class CHAR(c: Char) extends Rexp // matches a character c +case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence +case class STAR(r: Rexp) extends Rexp // star + +// nullable function: tests whether a regular +// expression can recognise the empty string +def nullable(r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true +} + +// the derivative of a regular expression w.r.t. a character +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) +} + +// the derivative w.r.t. a string (iterates der) +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, der(c, r)) +} + +// the main matcher function +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders(s.toList, r)) + + +// some examples from the homework + +val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) +der('a', r) +der('b', r) +der('c', r) + +val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) +der('x', r2) +der('y', der('x', r2)) +der('z', der('y', der('x', r2))) + + +// the optional regular expression (one or zero times) +def OPT(r: Rexp) = ALT(r, ONE) + +// the n-times regular expression (explicitly expanded) +def NTIMES(r: Rexp, n: Int) : Rexp = n match { + case 0 => ONE + case 1 => r + case n => SEQ(r, NTIMES(r, n - 1)) +} + + +// Test Cases +//============ + +// the evil regular expression a?{n} a{n} +def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) + +// the evil regular expression (a*)* b +val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +// for measuring time +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start) / (i * 1.0e9) +} + + +// test: (a?{n}) (a{n}) +@doc("Test (a?{n}) (a{n})") +@main +def test1() = { + println("Test (a?{n}) (a{n})") + + for (i <- 0 to 20 by 2) { + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") + } +} + +// test: (a*)* b +@doc("Test (a*)* b") +@main +def test2() = { + println("Test (a*)* b") + + for (i <- 0 to 20 by 2) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") + } +} + +// the size of a regular expressions - for testing purposes +def size(r: Rexp) : Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size(r2) + case SEQ(r1, r2) => 1 + size(r1) + size(r2) + case STAR(r) => 1 + size(r) +} + +// the expicit expansion in EVIL1(n) increases +// drastically its size + +size(EVIL1(1)) // 5 +size(EVIL1(3)) // 17 +size(EVIL1(5)) // 29 +size(EVIL1(7)) // 41 +size(EVIL1(20)) // 119 + +// given a regular expression and building successive +// derivatives might result into bigger and bigger +// regular expressions...here is an example for this: + +// (a+b)* o a o b o (a+b)* +val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b'))) +val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux))) + +size(ders("".toList, BIG)) // 13 +size(ders("ab".toList, BIG)) // 51 +size(ders("abab".toList, BIG)) // 112 +size(ders("ababab".toList, BIG)) // 191 +size(ders("abababab".toList, BIG)) // 288 +size(ders("ababababab".toList, BIG)) // 403 +size(ders("abababababab".toList, BIG)) // 536 + + +size(ders(("ab" * 200).toList, BIG)) // 366808 + +@doc("Test (a + b)* o (a o b) o (a + b)*") +@main +def test3() = { + println("Test (a + b)* o (a o b) o (a + b)*") + + for (i <- 0 to 200 by 10) { + println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f") + } +} + + + + +@doc("All tests.") +@main +def all() = { test1(); test2() ; test3() } \ No newline at end of file diff -r 61a936be50c4 -r f345e89895f5 progs/matcher/re2.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/matcher/re2.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,141 @@ +// A Version with an explicit n-times regular expression; +// this keeps the size of the regular expression in the +// EVIL1 test-case quite small +// +// call the test cases with X = {1,2} +// +// amm re2.sc testX +// +// or +// +// amm re2.sc all + + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class NTIMES(r: Rexp, n: Int) extends Rexp //explicit constructor for n-times + + +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case NTIMES(r, i) => if (i == 0) true else nullable(r) +} + + +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) + case NTIMES(r1, i) => + if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1)) +} + +def ders (s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, der(c, r)) +} + +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders(s.toList, r)) + + +// the optional regular expression: one or zero times +// this regular expression is still defined in terms of ALT +def OPT(r: Rexp) = ALT(r, ONE) + + +// Test Cases + +// evil regular expressions +def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) +val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start) / (i * 1.0e9) +} + + + +// test: (a?{n}) (a{n}) +@doc("Test (a?{n}) (a{n})") +@main +def test1() = { + for (i <- 0 to 1000 by 100) { + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") + } +} + +// test: (a*)* b +@doc("Test (a*)* b") +@main +def test2() = { + for (i <- 0 to 20) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") + } +} + +// the size of a regular expressions - for testing purposes +def size(r: Rexp) : Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size(r2) + case SEQ(r1, r2) => 1 + size(r1) + size(r2) + case STAR(r) => 1 + size(r) + case NTIMES(r, _) => 1 + size(r) +} + +// EVIL1(n) has now a constant size, no matter +// what n is; also the derivative only grows +// moderately + +size(EVIL1(1)) // 7 +size(EVIL1(3)) // 7 +size(EVIL1(5)) // 7 +size(EVIL1(7)) // 7 +size(EVIL1(20)) // 7 + +size(ders("".toList, EVIL1(5))) // 7 +size(ders("a".toList, EVIL1(5))) // 16 +size(ders("aa".toList, EVIL1(5))) // 35 +size(ders("aaa".toList, EVIL1(5))) // 59 +size(ders("aaaa".toList, EVIL1(5))) // 88 +size(ders("aaaaa".toList, EVIL1(5))) // 122 +size(ders("aaaaaa".toList, EVIL1(5))) // 151 + +// but the size of the derivatives can still grow +// quite dramatically in case of EVIL2 + +size(ders("".toList, EVIL2)) // 5 +size(ders("a".toList, EVIL2)) // 12 +size(ders("aa".toList, EVIL2)) // 28 +size(ders("aaa".toList, EVIL2)) // 58 +size(ders("aaaa".toList, EVIL2)) // 116 +size(ders("aaaaa".toList, EVIL2)) // 230 +size(ders("aaaaaa".toList, EVIL2)) // 456 + +size(ders(("a" * 20).toList, EVIL2)) // 7340068 + + + +@doc("All tests.") +@main +def all() = { test1(); test2() } \ No newline at end of file diff -r 61a936be50c4 -r f345e89895f5 progs/matcher/re3.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/matcher/re3.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,144 @@ +// A version with simplification of derivatives; +// this keeps the regular expressions small, which +// is good for the run-time +// +// call the test cases with X = {1,2} +// +// amm re3.sc testX +// +// or +// +// amm re3.sc all + + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class NTIMES(r: Rexp, n: Int) extends Rexp + + + +// the nullable function: tests whether the regular +// expression can recognise the empty string +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case NTIMES(r, i) => if (i == 0) true else nullable(r) +} + +// the derivative of a regular expression w.r.t. a character +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) + case NTIMES(r, i) => + if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1)) +} + +def simp(r: Rexp) : Rexp = r match { + case ALT(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, r2s) => r2s + case (r1s, ZERO) => r1s + case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) + } + case SEQ(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, _) => ZERO + case (_, ZERO) => ZERO + case (ONE, r2s) => r2s + case (r1s, ONE) => r1s + case (r1s, r2s) => SEQ(r1s, r2s) + } + case r => r +} + + +// the derivative w.r.t. a string (iterates der) +def ders(s: List[Char], r: Rexp) : Rexp = s match { + case Nil => r + case c::s => ders(s, simp(der(c, r))) +} + + +// the main matcher function +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders(s.toList, r)) + + +// one or zero +def OPT(r: Rexp) = ALT(r, ONE) + + +// Test Cases + +// evil regular expressions: (a?){n} a{n} and (a*)* b +def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) +val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start)/(i * 1.0e9) +} + + +//test: (a?{n}) (a{n}) +@doc("Test (a?{n}) (a{n})") +@main +def test1() = { + for (i <- 0 to 8000 by 1000) { + println(f"$i: ${time_needed(3, matcher(EVIL1(i), "a" * i))}%.5f") + } +} + +//test: (a*)* b +@doc("Test (a*)* b") +@main +def test2() = { + for (i <- 0 to 6000000 by 500000) { + println(f"$i: ${time_needed(3, matcher(EVIL2, "a" * i))}%.5f") + } +} + +// size of a regular expressions - for testing purposes +def size(r: Rexp) : Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size(r2) + case SEQ(r1, r2) => 1 + size(r1) + size(r2) + case STAR(r) => 1 + size(r) + case NTIMES(r, _) => 1 + size(r) +} + + +// now the size of the derivatives grows +// much, much slower + +size(ders("".toList, EVIL2)) // 5 +size(ders("a".toList, EVIL2)) // 8 +size(ders("aa".toList, EVIL2)) // 8 +size(ders("aaa".toList, EVIL2)) // 8 +size(ders("aaaa".toList, EVIL2)) // 8 +size(ders("aaaaa".toList, EVIL2)) // 8 + + +@doc("All tests.") +@main +def all() = { test1(); test2() } + + diff -r 61a936be50c4 -r f345e89895f5 progs/matcher/re4.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/matcher/re4.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,162 @@ +// (ASIDE!) A version which attempts to move whole strings, +// not just characters, under derivatives whenever possible +// +// call the test cases with X = {1,2} +// +// amm re3.sc testX +// +// or +// +// amm re3.sc all + + +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) extends Rexp +case class ALT(r1: Rexp, r2: Rexp) extends Rexp +case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +case class STAR(r: Rexp) extends Rexp +case class NTIMES(r: Rexp, n: Int) extends Rexp + +// the nullable function: tests whether the regular +// expression can recognise the empty string +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true + case NTIMES(r, i) => if (i == 0) true else nullable(r) +} + +// the derivative of a regular expression w.r.t. a character +def der (c: Char, r: Rexp) : Rexp = r match { + case ZERO => ZERO + case ONE => ZERO + case CHAR(d) => if (c == d) ONE else ZERO + case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) + case SEQ(r1, r2) => + if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) + case NTIMES(r1, i) => + if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1)) +} + +def simp(r: Rexp) : Rexp = r match { + case ALT(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, r2s) => r2s + case (r1s, ZERO) => r1s + case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) + } + case SEQ(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, _) => ZERO + case (_, ZERO) => ZERO + case (ONE, r2s) => r2s + case (r1s, ONE) => r1s + case (r1s, r2s) => SEQ(r1s, r2s) + } + case r => r +} + +// an example +val r = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) +der('x', r) +der('y', der('x', r)) +der('z', der('y', der('x', r))) +simp(der('z', der('y', der('x', r)))) + +// *new* +// the derivative w.r.t. a string (iterates der) +def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match { + case (Nil, r) => r + case (s, ZERO) => ZERO + case (s, ONE) => if (s == Nil) ONE else ZERO + case (s, CHAR(c)) => if (s == List(c)) ONE else + if (s == Nil) CHAR(c) else ZERO + case (s, ALT(r1, r2)) => ALT(ders2(s, r1), ders2(s, r2)) + case (c::s, r) => ders2(s, simp(der(c, r))) +} + +// the main matcher function +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders2(s.toList, r)) + + +// one or zero +def OPT(r: Rexp) = ALT(r, ONE) + + +// Test Cases + +def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) +val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +// for measuring time +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 1 to i) code + val end = System.nanoTime() + (end - start) / (i * 1.0e9) +} + + +// test: (a?{n}) (a{n}) +@doc("Test (a?{n}) (a{n})") +@main +def test1() = { + for (i <- 0 to 11000 by 1000) { + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") + } +} + +// test: (a*)* b +@doc("Test (a*)* b") +@main +def test2() = { + for (i <- 0 to 7000000 by 500000) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") + } +} + +@doc("All tests.") +@main +def all() = { test1(); test2() } + + + +// the size of a regular expressions - for testing purposes +def size(r: Rexp) : Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size(r2) + case SEQ(r1, r2) => 1 + size(r1) + size(r2) + case STAR(r) => 1 + size(r) + case NTIMES(r, _) => 1 + size(r) +} + + +// string of a regular expressions - for testing purposes +def string(r: Rexp) : String = r match { + case ZERO => "0" + case ONE => "1" + case CHAR(c) => c.toString + case ALT(r1, r2) => s"(${string(r1)} + ${string(r2)})" + case SEQ(CHAR(c), CHAR(d)) => s"${c}${d}" + case SEQ(r1, r2) => s"(${string(r1)} ~ ${string(r2)})" + case STAR(r) => s"(${string(r)})*" + case NTIMES(r, n) => s"(${string(r)}){${n}}" +} + + +// further testcases: + +// test: ("a" | "aa")* +val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) + +// test: ("" | "a" | "aa")* +val EVIL4 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) + diff -r 61a936be50c4 -r f345e89895f5 progs/while-compiler-arrays/compile_arrays.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/while-compiler-arrays/compile_arrays.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,240 @@ +// A Small Compiler for the WHILE Language +// +// - this compiler contains support for "static" integer +// arrays (they are mutable but cannot be re-sized) +// +// Call with +// +// amm compile_arrays.sc + + +// the abstract syntax trees for WHILE + +abstract class Stmt +abstract class AExp +abstract class BExp +type Block = List[Stmt] + +// statements +case object Skip extends Stmt +case class ArrayDef(s: String, n: Int) extends Stmt // array definition +case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt +case class While(b: BExp, bl: Block) extends Stmt +case class Assign(s: String, a: AExp) extends Stmt // var := exp +case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt // arr[exp1] := exp2 +case class Write(s: String) extends Stmt + + +// arithmetic expressions +case class Var(s: String) extends AExp +case class Num(i: Int) extends AExp +case class Aop(o: String, a1: AExp, a2: AExp) extends AExp +case class Ref(s: String, a: AExp) extends AExp + +// boolean expressions +case object True extends BExp +case object False extends BExp +case class Bop(o: String, a1: AExp, a2: AExp) extends BExp + + +// compiler headers needed for the JVM +// +// - contains a main method and a method for writing out an integer +// +// - the stack and locals are hard-coded +// + +val beginning = """ +.class public XXX.XXX +.super java/lang/Object + +.method public static write(I)V + .limit locals 1 + .limit stack 2 + getstatic java/lang/System/out Ljava/io/PrintStream; + iload 0 + invokevirtual java/io/PrintStream/print(I)V + return +.end method + +.method public static main([Ljava/lang/String;)V + .limit locals 200 + .limit stack 200 + +; COMPILED CODE STARTS + +""" + +val ending = """ +; COMPILED CODE ENDS + return + +.end method +""" + + + +// for generating new labels +var counter = -1 + +def Fresh(x: String) = { + counter += 1 + x ++ "_" ++ counter.toString() +} + +// environments for variables and indices +type Env = Map[String, Int] + +// convenient string interpolations +// for generating instructions and labels +import scala.language.implicitConversions +import scala.language.reflectiveCalls + +implicit def sring_inters(sc: StringContext) = new { + def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" + def l(args: Any*): String = sc.s(args:_*) ++ ":\n" +} + +def compile_op(op: String) = op match { + case "+" => i"iadd" + case "-" => i"isub" + case "*" => i"imul" +} + +// arithmetic expression compilation +def compile_aexp(a: AExp, env : Env) : String = a match { + case Num(i) => i"ldc $i" + case Var(s) => i"iload ${env(s)}" + case Aop(op, a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ compile_op(op) + case Ref(s, a) => + i"aload ${env(s)}" ++ compile_aexp(a, env) ++ i"iaload" +} + +// boolean expression compilation +def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { + case True => "" + case False => i"goto $jmp" + case Bop("==", a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp" + case Bop("!=", a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp" + case Bop("<", a1, a2) => + compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp" +} + +// statement compilation +def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match { + case Skip => ("", env) + case Assign(x, a) => { + val index = env.getOrElse(x, env.keys.size) + (compile_aexp(a, env) ++ i"istore $index \t\t; $x", env + (x -> index)) + } + case If(b, bl1, bl2) => { + val if_else = Fresh("If_else") + val if_end = Fresh("If_end") + val (instrs1, env1) = compile_block(bl1, env) + val (instrs2, env2) = compile_block(bl2, env1) + (compile_bexp(b, env, if_else) ++ + instrs1 ++ + i"goto $if_end" ++ + l"$if_else" ++ + instrs2 ++ + l"$if_end", env2) + } + case While(b, bl) => { + val loop_begin = Fresh("Loop_begin") + val loop_end = Fresh("Loop_end") + val (instrs1, env1) = compile_block(bl, env) + (l"$loop_begin" ++ + compile_bexp(b, env, loop_end) ++ + instrs1 ++ + i"goto $loop_begin" ++ + l"$loop_end", env1) + } + case Write(x) => + (i"iload ${env(x)} \t\t; $x" ++ + i"invokestatic XXX/XXX/write(I)V", env) + case ArrayDef(s: String, n: Int) => { + val index = if (env.isDefinedAt(s)) throw new Exception("array def error") else + env.keys.size + (i"ldc $n" ++ + i"newarray int" ++ + i"astore $index", env + (s -> index)) + } + case AssignA(s, a1, a2) => { + val index = if (env.isDefinedAt(s)) env(s) else + throw new Exception("array not defined") + (i"aload ${env(s)}" ++ + compile_aexp(a1, env) ++ + compile_aexp(a2, env) ++ + i"iastore", env) + } +} + +// compile a block (i.e. list of statements) +def compile_block(bl: Block, env: Env) : (String, Env) = bl match { + case Nil => ("", env) + case s::bl => { + val (instrs1, env1) = compile_stmt(s, env) + val (instrs2, env2) = compile_block(bl, env1) + (instrs1 ++ instrs2, env2) + } +} + + +// main compile function for blocks (adds headers and proper JVM names) +def compile(bl: Block, class_name: String) : String = { + val instructions = compile_block(bl, Map())._1 + (beginning ++ instructions ++ ending).replace("XXX", class_name) +} + + + +// contrived example involving arrays +val array_test = + List(ArrayDef("a", 10), // array a[10] + ArrayDef("b", 2), // array b[2] + AssignA("a", Num(0), Num(10)), // a[0] := 10 + Assign("x", Ref("a", Num(0))), // x := a[0] + Write("x"), + AssignA("b", Num(1), Num(5)), // b[1] := 5 + Assign("x", Ref("b", Num(1))), // x := b[1] + Write("x")) + + +// prints out the JVM-assembly instructions for fib above +// +// println(compile(array_test, "arr")) +// +// can be assembled by hand with +// +// java -jar jasmin.jar arr.j +// +// and run with +// +// java arr/arr + +// automating the above +import ammonite.ops._ + +def compile_to_file(bl: Block, class_name: String) : Unit = + write.over(pwd / s"$class_name.j", compile(bl, class_name)) + +def compile_and_run(bl: Block, class_name: String) : Unit = { + println(s"Start of compilation") + compile_to_file(bl, class_name) + println(s"generated $class_name.j file") + os.proc("java", "-jar", "jasmin.jar", s"$class_name.j").call() + println(s"generated $class_name.class file ") + println(os.proc("java", s"${class_name}/${class_name}").call().out.text()) + println(s"done.") +} + + + +@main def main() = { + compile_and_run(array_test, "arr") +} + + diff -r 61a936be50c4 -r f345e89895f5 progs/while-compiler-arrays/compile_bfc.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/while-compiler-arrays/compile_bfc.sc Mon Jun 29 21:05:34 2020 +0100 @@ -0,0 +1,457 @@ +// Some more interesting testcases for the +// WHILE compiler with arrays, it includes: +// +// - a small parser for WHILE programs +// +// - transpiles BF programs into WHILE programs +// and then compiles and runs them +// +// - the power-example is the Mandelbrot set: +// +// * 65k for the transpiled WHILE program +// * parsing uses around 30 secs using fastparse +// * the jasmin assembly file is 236k +// * the resulting Java program takes about 20 secs +// +// Call with (X being 0,1,..,4) +// +// amm compile_bfc.sc all +// amm compile_bfc.sc bfcX + + +// load the compiler +import $file.compile_arrays +import compile_arrays._ + +def time_needed[T](i: Int, code: => T) = { + val start = System.nanoTime() + for (j <- 2 to i) code + val result = code + val end = System.nanoTime() + ((end - start) / (i * 1.0e9), result) +} + +// for BF we have to change the write library-function, +// because in BF integers are written out as characters +val beginning = """ +.class public XXX.XXX +.super java/lang/Object + +.method public static write(I)V + .limit locals 1 + .limit stack 2 + getstatic java/lang/System/out Ljava/io/PrintStream; + iload 0 + i2c ; Int => Char + invokevirtual java/io/PrintStream/print(C)V ; println(I)V => print(C)V + return +.end method + +.method public static main([Ljava/lang/String;)V + .limit locals 200 + .limit stack 200 + +; COMPILED CODE STARTS + +""" + + +// modified main compilation function for blocks +def compile(bl: Block, class_name: String) : String = { + val instructions = compile_block(bl, Map())._1 + (beginning ++ instructions ++ ending).replace("XXX", class_name) +} + +// automating the above +import ammonite.ops._ + +def compile_to_file(bl: Block, class_name: String) : Unit = + write.over(pwd / s"$class_name.j", compile(bl, class_name)) + +def compile_and_run(bl: Block, class_name: String) : Unit = { + println(s"Start of compilation") + compile_to_file(bl, class_name) + println(s"generated $class_name.j file") + val (jasmin_time, _) = + time_needed(1, os.proc("java", "-jar", "jasmin.jar", s"$class_name.j").call()) + println(s"generated $class_name.class file (in $jasmin_time secs).") + val (running_time, output) = + time_needed(1, os.proc("java", s"${class_name}/${class_name}").call().out.text()) + println(output) + println(s"done (in $running_time secs).") +} + + +//===================================== +// Grammar Rules for WHILE with arrays +//===================================== + +import fastparse._ +import MultiLineWhitespace._ + +def lowercase [_ : P] = P( CharIn("a-z") ) +def uppercase[_ : P] = P( CharIn("A-Z") ) +def letter[_ : P] = P( lowercase | uppercase ) +def digit [_ : P] = P( CharIn("0-9") ) + +def Number[_ : P]: P[Int] = P( digit.rep(1) ).!.map(_.toInt) +def Ident[_ : P]: P[String] = P( letter ~ (letter | digit | "_").rep ).! + +// arithmetic expressions +def AExp[_ : P]: P[AExp] = + P( P(Te ~ "+" ~ AExp).map{ case (l, r) => Aop("+", l, r)} + | P(Te ~ "-" ~ AExp).map{ case (l, r) => Aop("-", l, r)} + | Te ) +def Te[_ : P]: P[AExp] = + P( P(Fa ~ "*" ~ Te).map{ case (l, r) => Aop("*", l, r)} + | Fa ) +def Fa[_ : P]: P[AExp] = + P( "(" ~ AExp ~ ")" + | P (Ident ~ "[" ~ AExp ~ "]").map{Ref.tupled} + | P(Number).map{Num} + | P(Ident).map{Var} ) + +// boolean expressions +def BExp[_ : P]: P[BExp] = + P( P(AExp ~ "=" ~ AExp).map{ case (x, z) => Bop("=", x, z)} + | P(AExp ~ "!=" ~ AExp).map{ case (x, z) => Bop("!=", x, z)} + | P(AExp ~ "<" ~ AExp).map{ case (x, z) => Bop("<", x, z)} + | P(AExp ~ ">" ~ AExp).map{ case (x, z) => Bop("<", z, x)} + | P("true").map{ _ => True} + | P("false").map{ _ => False} + | "(" ~ BExp ~ ")" ) + +// statements and blocks +def Stmt[_ : P]: P[Stmt] = + P( P("skip").map( _ => Skip) + | P(Ident ~ ":=" ~ AExp).map{Assign.tupled} + | P(Ident ~ "[" ~ AExp ~ "]" ~ ":=" ~ AExp).map{AssignA.tupled} + | P("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block).map{If.tupled} + | P("while" ~ BExp ~ "do" ~ Block).map{While.tupled} + | P("new(" ~ Ident ~ "[" ~ Number ~ "])").map{ArrayDef.tupled} + | P("write(" ~ Ident ~ ")").map{Write} ) + +def Stmts[_ : P]: P[Block] = + P( P(Stmt ~ ";" ~ Stmts).map{ case (x, z) => x :: z } + | P(Stmt).map{s => List(s)} ) + +def Block[_ : P]: P[Block] = + P( "{" ~ Stmts ~ "}" + | P(Stmt).map(s => List(s)) ) + +// some test cases for the parser + +//println(fastparse.parse("(1 + (2 + 5)) + 4", AExp(_)).get) +//println(fastparse.parse("1 + 2 + 3 + 45", AExp(_))) +//println(fastparse.parse("1 + 2 * 3", AExp(_))) +//println(fastparse.parse("x + 2 * 3", AExp(_))) +//println(fastparse.parse("x2 := 5 + a", Stmts(_))) +//println(fastparse.parse("x2 := 5 + a[3+a]", Stmts(_))) +//println(fastparse.parse("a[x2+3] := 5 + a[3+a]", Stmts(_))) +//println(fastparse.parse("{x := 5; y := 8}", Block(_))) +//println(fastparse.parse("if (false) then {x := 5} else {x := 10}", Block(_))) + +val fib = + """n := 10; + minus1 := 0; + minus2 := 1; + temp:=0; + while (n > 0) do { + temp := minus2; + minus2 := minus1 + minus2; + minus1 := temp; + n := n - 1}; + result := minus2; + write(result) + """ + +//println(fastparse.parse(fib, Stmts(_)).get.value) + + + +//====================================== +// BF transpiler into WHILE with arrays +//====================================== + +// simple BF instructions translation +def instr(c: Char) : String = c match { + case '>' => "ptr := ptr + 1;" + case '<' => "ptr := ptr - 1;" + case '+' => "mem[ptr] := mem[ptr] + 1;" + case '-' => "mem[ptr] := mem[ptr] - 1;" + case '.' => "x := mem[ptr]; write x;" + //case ',' => "XXX" // "ptr = getchar();\n" + case '[' => "while (mem[ptr] != 0) do {" + case ']' => "skip};" + case _ => "" +} + +def instrs(prog: String) : String = + prog.toList.map(instr).mkString + + +// Note: Unfortunately, the transpiled mandelbrot.bf program +// is so large that it does not fit inside the limitations of +// what the JVM imposes on methods (only 64K of instructions). +// Therefore some optimisations are first applied to +// BF programs before WHILE programs are created. The +// optimisations are +// +// - replacing BF-loops of the form [-] with a new 0-instruction +// - combining single increment/decrement instructions +// +// The size of the resulting .j-file is 270K. + + +def splice(cs: List[Char], acc: List[(Char, Int)]) : List[(Char, Int)] = (cs, acc) match { + case (Nil, acc) => acc + case (c :: cs, Nil) => splice(cs, List((c, 1))) + case (c :: cs, (d, n) :: acc) => + if (c == d) splice(cs, (c, n + 1) :: acc) + else splice(cs, (c, 1) :: (d, n) :: acc) +} + +def spl(s: String) = splice(s.toList, Nil).reverse + +def instr2(c: Char, n: Int) : String = c match { + case '>' => s"ptr := ptr + $n;" + case '<' => s"ptr := ptr - $n;" + case '0' => s"mem[ptr] := 0;" + case '+' => s"mem[ptr] := mem[ptr] + $n;" + case '-' => s"mem[ptr] := mem[ptr] - $n;" + case '.' => s"x := mem[ptr]; write(x);" + case '[' => "while (mem[ptr] != 0) do {" * n + case ']' => "skip};" * n + case _ => "" +} + +def instrs2(prog: String) : String = + spl(prog.replaceAll("""\[-\]""", "0")).map{ case (c, n) => instr2(c, n) }.mkString + +// adding the "header" to the BF program +def bf_str(prog: String) : String = { + "new(mem[30000]);" ++ + "ptr := 15000;" ++ + instrs2(prog) ++ + "skip" +} + + +def bf_run(prog: String, name: String) = { + println(s"BF pre-processing of $name") + val bf_string = bf_str(prog) + println(s"BF parsing (program length ${bf_string.length} characters)") + val (time, bf_prog) = + time_needed(1, fastparse.parse(bf_string, Stmts(_)).get.value) + println(s"BF generated WHILE program (needed $time for parsing)") + compile_and_run(bf_prog, name) +} + +// a benchmark program (counts down from 'Z' to 'A') +val bf0 = """>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++ + [>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++ + ++++++++[>++++++++++[>++++++++++[>++++++++++[>+ + +++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.""" + +@doc(" Benchmark 'Z' to 'A'.") +@main +def bfc0() = bf_run(bf0, "bench") + +// Sierpinski triangle +val bf1 = """++++++++[>+>++++<<-]>++>>+<[-[>>+<<-]+>>]>+[-<<<[ + ->[+[-]+>++>>>-<<]<[<]>>++++++[<<+++++>>-]+<<++.[-]<< + ]>.>+[>>]>+]""" + +@doc(" Sierpinski triangle.") +@main +def bfc1() = bf_run(bf1, "sier") + +// Hello World +val bf2 = """++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-] + >>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.""" + +@doc(" Hello world.") +@main +def bfc2() = bf_run(bf2, "hello") + +// Fibonacci +val bf3 = """+++++++++++ + >+>>>>++++++++++++++++++++++++++++++++++++++++++++ + >++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+> + +<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[- + <-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<< + -]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]] + >[<<+>>[-]]<<<<<<<]>>>>>[+++++++++++++++++++++++++ + +++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++ + ++++++++++++++++++++++++++++++++++++++++++++.[-]<< + <<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<< + [-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-] + [-]++++++++++.""" + +@doc(" Fibonacci numbers.") +@main +def bfc3() = bf_run(bf3, "fibs") + +// Mandelbrot Set +//---------------- +// +// Note: Parsing of the generated WHILE program (around 60K in size) +// takes approximately 10 minutes to parse with the parser combinators, and +// approximately 30 seconds with fastparse + + +val bf4 = """A mandelbrot set fractal viewer in brainf*** written by Erik Bosman ++++++++++++++[->++>>>+++++>++>+<<<<<<]>>>>>++++++>--->>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-]>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+ +<<<<<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>>+>>>>>>>>>>>>>>>>>>>>>>>>>> +>+<<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+[>>>>>>[>>>>>>>[-]>>]<<<<<<<<<[<<<<<<<<<]>> +>>>>>[-]+<<<<<<++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<+++++++[-[->>> +>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[[-]>>>>>>[>>>>> +>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>> +[>>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<< +<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>+++++++++++++++[[ +>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[ +>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[ +-<<+>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<< +<<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<< +[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>> +>>>>[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+ +<<<<<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>> +>>>>>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<< ++>>>>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<< +<]<+<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<< +<<<]>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[-> +>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<< +<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]<<<<<<<[->+>>>-<<<<]>>>>>>>>>+++++++++++++++++++ ++++++++>>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>[<<<<<<<+<[-<+>>>>+<<[-]]>[-<<[->+>>>- +<<<<]>>>]>>>>>>>>>>>>>[>>[-]>[-]>[-]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>>>>>>[>>>>> +[-<<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>[-<<<<<<<< +<+>>>>>>>>>]>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>>>]+>[- +]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>>>>>>>>]<<< +<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+>>]< +<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[->>>> +>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[-]<->>> +[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[>>>>>>[-< +<<<<+>>>>>]<<<<<[->>>>>+<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>+>>>>>>>> +]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> +]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+> +>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>++++++++ ++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>>>>>>[-<<<<<<<+ +>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[ +-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>>>]>[-<<<<<<[->>>>>+<++<<<<]>>>>>[-< +<<<<+>>>>>]<->+>]<[->+<]<<<<<[->>>>>+<<<<<]>>>>>>[-]<<<<<<+>>>>[-<<<<->>>>]+<<<< +[->>>>->>>>>[>>[-<<->>]+<<[->>->[-<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-] ++>>>>>>[>>>>>>>>>]>+<]]+>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<<<<<<<<<<<[<<<<< +<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<< +[<<<<<<<<<]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<< +<<<+<[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<< +<<<<<<<<<<]>>>>[-]<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+<]>>>>>>>>]<<< +<<<<<+<[>[->>>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>[->>>>+<<<<]>]<[->>>>-<<<<<<< +<<<<<<<+>>>>>>>>>>]<]>>[->>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>>+<<<< +]<<<<<<<<<<<]>>>>>>+<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>>>>>>>>>]<<<<<<<<< +[>[->>>>>+<<<<[->>>>-<<<<<<<<<<<<<<+>>>>>>>>>>>[->>>+<<<]<]>[->>>-<<<<<<<<<<<<<< ++>>>>>>>>>>>]<<]>[->>>>+<<<[->>>-<<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>>+<<<]<<<<<<< +<<<<<]]>[-]>>[-]>[-]>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-< +<<<+>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[ +[>>>>>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+ +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->> +[-<<+>>]<<[->>+>+<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<< +<[>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[ +>[-]<->>>[-<<<+>[<->-<<<<<<<+>>>>>>>]<[->+<]>>>]<<[->>+<<]<+<<<<<<<<<]>>>>>>>>>[ +>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>]> +>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>[-]>>>>+++++++++++++++[[>>>>>>>>>]<<<<<<<<<-<<<<< +<<<<[<<<<<<<<<]>>>>>>>>>-]+[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<< +<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[- +<<<+>>>]<<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>> +>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>>> +[-<<<->>>]<<<[->>>+<<<]>>>>>>>>]<<<<<<<<+<[>[->+>[-<-<<<<<<<<<<+>>>>>>>>>>>>[-<< ++>>]<]>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<<<]>>[-<+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>>]<]> +[-<<+>>]<<<<<<<<<<<<<]]>>>>[-<<<<+>>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>> +>>>>>>]<<<<<<<<+<[>[->+>>[-<<-<<<<<<<<<<+>>>>>>>>>>>[-<+>]>]<[-<-<<<<<<<<<<+>>>> +>>>>>>>]<<]>>>[-<<+>[-<-<<<<<<<<<<+>>>>>>>>>>>]>]<[-<+>]<<<<<<<<<<<<]>>>>>+<<<<< +]>>>>>>>>>[>>>[-]>[-]>[-]>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>>>[-<<<<< +<+>>>>>>]<<<<<<[->>>>>>+<<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>+>[-<-<<<<+>>>> +>]>>[-<<<<<<<[->>>>>+<++<<<<]>>>>>[-<<<<<+>>>>>]<->+>>]<<[->>+<<]<<<<<[->>>>>+<< +<<<]+>>>>[-<<<<->>>>]+<<<<[->>>>->>>>>[>>>[-<<<->>>]+<<<[->>>-<[-<<+>>]<<[->>+<< +<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>[-<<->>]+<<[->>->[-<<<+>>>]< +<<[->>>+<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]< +<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-<<<+>>>]<<<[->>>+>>>>>>[>+>[-<->]<[->+ +<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>[->>>+<<<]>]<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>]<]>>[->>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>]>]<[->>>+<<< +]<<<<<<<<<<<]>>>>>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]]>>>>[-<<<<+> +>>>]<<<<[->>>>+>>>>>[>+>>[-<<->>]<<[->>+<<]>>>>>>>>]<<<<<<<<+<[>[->>>>+<<<[->>>- +<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[ +->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<<<<<<]]>>>>[-]<<<<]>>>>[-<<<<+>> +>>]<<<<[->>>>+>[-]>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+<<+<<<<<]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>[->>>>+<<<[->>>-<<<<<<<<<<<<<+>>>>>>>>>>>[->>+<<]<]>[->>-<<<<<<<< +<<<<<+>>>>>>>>>>>]<<]>[->>>+<<[->>-<<<<<<<<<<<<<+>>>>>>>>>>>]<]>[->>+<<]<<<<<<<< +<<<<]]>>>>>>>>>[>>[-]>[-]>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>[-]>[-]>>>>>[>>>>>[-<<<<+ +>>>>]<<<<[->>>>+<<<+<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<+>>>>> +]<<<<<[->>>>>+<<<+<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>> +>>>>>]+>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+[>+>> +>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>[-<<<<+>>>>]<<<<[->>>>+<<<<<[->>[-<<+ +>>]<<[->>+>>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[> +[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<]>[->>>>>>>>>+<<<<<<<<<]<+>>>>>>>>]<<<<<<<<<[>[- +]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+<<<<<<<<<]>>>>>>>>> +[>+>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>->>>>>[-<<<<<+>>>>>]<<<<<[->>>>>+<<<< +<<[->>>[-<<<+>>>]<<<[->>>+>+<<<<]+>>>>>>>>>]<<<<<<<<[<<<<<<<<<]]>>>>>>>>>[>>>>>> +>>>]<<<<<<<<<[>>[->>>>>>>>>+<<<<<<<<<]<<<<<<<<<<<]>>[->>>>>>>>>+<<<<<<<<<]<<+>>> +>>>>>]<<<<<<<<<[>[-]<->>>>[-<<<<+>[<->-<<<<<<+>>>>>>]<[->+<]>>>>]<<<[->>>+<<<]<+ +<<<<<<<<<]>>>>>>>>>[>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>> +>>>>>>>>>>>>>>>>>>>]>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>+++++++++++++++[[>>>>>>>> +>]<<<<<<<<<-<<<<<<<<<[<<<<<<<<<]>>>>>>>>>-]+>>>>>>>>>>>>>>>>>>>>>+<<<[<<<<<<<<<] +>>>>>>>>>[>>>[-<<<->>>]+<<<[->>>->[-<<<<+>>>>]<<<<[->>>>+<<<<<<<<<<<<<[<<<<<<<<< +]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>[-<<<<->>>>]+<<<<[->>>>-<[-<<<+>>>]<<<[->>>+< +<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]> +>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>->>[-<<<<+>>>>]<<<<[->>>>+<<[-]<<]>>]<<+>>>>[-<<<< +->>>>]+<<<<[->>>>-<<<<<<.>>]>>>>[-<<<<<<<.>>>>>>>]<<<[-]>[-]>[-]>[-]>[-]>[-]>>>[ +>[-]>[-]>[-]>[-]>[-]>[-]>>>]<<<<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-]>>>>]<<<<<<<<< +[<<<<<<<<<]>+++++++++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+>>>>>>>>>+<<<<<<<< +<<<<<<[<<<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+[-]>>[>>>>>>>>>]<<<<< +<<<<[>>>>>>>[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<[<<<<<<<<<]>>>>>>>[-]+>>>]<<<< +<<<<<<]]>>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<<[->>>>>>>+>>[>+>>>>[-<<<<->>>>]<<<<[->>> +>+<<<<]>>>>>>>>]<<+<<<<<<<[>>>>>[->>+<<]<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<< +<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<<<<<<[->>>>>>+<<<<<<]< ++<<<<<<<<<]>>>>>>>-<<<<[-]+<<<]+>>>>>>>[-<<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>->>[>> +>>>[->>+<<]>>>>]<<<<<<<<<[>[-]<->>>>>>>[-<<<<<<<+>[<->-<<<+>>>]<[->+<]>>>>>>>]<< +<<<<[->>>>>>+<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>+<<< +<<[<<<<<<<<<]>>>>>>>>>[>>>>>[-<<<<<->>>>>]+<<<<<[->>>>>->>[-<<<<<<<+>>>>>>>]<<<< +<<<[->>>>>>>+<<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>[-< +<<<<<<->>>>>>>]+<<<<<<<[->>>>>>>-<<[-<<<<<+>>>>>]<<<<<[->>>>>+<<<<<<<<<<<<<<[<<< +<<<<<<]>>>[-]+>>>>>>[>>>>>>>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<< +<<[<<<<<<<<<]>>>>[-]<<<+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>-<<<<<[<<<<<<< +<<]]>>>]<<<<.>>>>>>>>>>[>>>>>>[-]>>>]<<<<<<<<<[<<<<<<<<<]>++++++++++[-[->>>>>>>> +>+<<<<<<<<<]>>>>>>>>>]>>>>>+>>>>>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>>>>>>[-<<<<<< +<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+[-]>[>>>>>>>>>]<<<<<<<<<[>>>>>>>>[-<<<<<<<+>>>>>> +>]<<<<<<<[->>>>>>>+<<<<<<<<[<<<<<<<<<]>>>>>>>>[-]+>>]<<<<<<<<<<]]>>>>>>>>[-<<<<< +<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+>[>+>>>>>[-<<<<<->>>>>]<<<<<[->>>>>+<<<<<]>>>>>> +>>]<+<<<<<<<<[>>>>>>[->>+<<]<<<<<<<<<<<<<<<]>>>>>>>>>[>>>>>>>>>]<<<<<<<<<[>[-]<- +>>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<]<+<<<<<< +<<<]>>>>>>>>-<<<<<[-]+<<<]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>>->[>>> +>>>[->>+<<]>>>]<<<<<<<<<[>[-]<->>>>>>>>[-<<<<<<<<+>[<->-<<+>>]<[->+<]>>>>>>>>]<< +<<<<<[->>>>>>>+<<<<<<<]<+<<<<<<<<<]>+++++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>> ++>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<[<<<<<<<<<]>>>>>>>>>[>>>>>>[-<<<<<<->>>>>>]+< +<<<<<[->>>>>>->>[-<<<<<<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<<<<<<<<<<[<<<<<<< +<<]>>>>[-]+>>>>>[>>>>>>>>>]>+<]]+>>>>>>>>[-<<<<<<<<->>>>>>>>]+<<<<<<<<[->>>>>>>> +-<<[-<<<<<<+>>>>>>]<<<<<<[->>>>>>+<<<<<<<<<<<<<<<[<<<<<<<<<]>>>[-]+>>>>>>[>>>>>> +>>>]>[-]+<]]+>[-<[>>>>>>>>>]<<<<<<<<]>>>>>>>>]<<<<<<<<<[<<<<<<<<<]>>>>[-]<<<++++ ++[-[->>>>>>>>>+<<<<<<<<<]>>>>>>>>>]>>>>>->>>>>>>>>>>>>>>>>>>>>>>>>>>-<<<<<<[<<<< +<<<<<]]>>>]""" + +@doc(" Mandelbrot set.") +@main +def bfc4() = bf_run(bf4, "mand") + + +// +@doc(" All benchmarks.") +@main +def all() = { bfc0(); bfc1(); bfc2(); bfc3(); bfc4() } \ No newline at end of file diff -r 61a936be50c4 -r f345e89895f5 progs/while-compiler-arrays/jasmin.jar Binary file progs/while-compiler-arrays/jasmin.jar has changed