--- /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
--- /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
--- /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","}"))
--- /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)
--- /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)
--- /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
--- /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
--- /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() }
+
+
--- /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')))))
+
--- /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")
+}
+
+
--- /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
Binary file progs/while-compiler-arrays/jasmin.jar has changed