--- a/progs/comb1.scala Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/comb1.scala Sun Jul 28 14:24:46 2019 +0100
@@ -1,11 +1,11 @@
import scala.language.implicitConversions
import scala.language.reflectiveCalls
-/* Note, in the lectures I did not show the type consraint
- * I <% Seq[_] , which means that the input type I can be
- * treated, or seen, as a sequence. */
+/* Note, in the lectures I did not show the implicit type consraint
+ * I => Seq[_] , which means that the input type I needs to be
+ * a sequence, subtype of Seq. */
-abstract class Parser[I <% Seq[_], T] {
+abstract class Parser[I, T](implicit ev: I => Seq[_]) {
def parse(ts: I): Set[(T, I)]
def parse_all(ts: I) : Set[T] =
@@ -13,20 +13,20 @@
if (tail.isEmpty)) yield head
}
-class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T],
- q: => Parser[I, S]) extends Parser[I, (T, S)] {
+class SeqParser[I, T, S](p: => Parser[I, T],
+ q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] {
def parse(sb: I) =
for ((head1, tail1) <- p.parse(sb);
(head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
}
-class AltParser[I <% Seq[_], T](p: => Parser[I, T],
- q: => Parser[I, T]) extends Parser[I, T] {
+class AltParser[I, T](p: => Parser[I, T],
+ q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] {
def parse(sb: I) = p.parse(sb) ++ q.parse(sb)
}
-class FunParser[I <% Seq[_], T, S](p: => Parser[I, T],
- f: T => S) extends Parser[I, S] {
+class FunParser[I, T, S](p: => Parser[I, T],
+ f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] {
def parse(sb: I) =
for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
}
@@ -48,13 +48,16 @@
val NumParser = RegexParser("[0-9]+".r)
def StringParser(s: String) = RegexParser(Regex.quote(s).r)
-val NumParserInt = NumParser ==> (s => s.toInt)
+// NumParserInt transforms a "string integer" into an Int;
+// needs new, because FunParser is not a case class
+val NumParserInt = new FunParser(NumParser, (s: String) => s.toInt)
+
// convenience
implicit def string2parser(s: String) = StringParser(s)
implicit def char2parser(c: Char) = CharParser(c)
-implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
+implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new {
def | (q : => Parser[I, T]) = new AltParser[I, T](p, q)
def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
@@ -70,6 +73,9 @@
new SeqParser[String, String, String](s, r)
}
+// NumParserInt can now be written as
+val NumParserInt = NumParser ==> (s => s.toInt)
+
lazy val Pal : Parser[String, String] =
(("a" ~ Pal ~ "a") ==> { case ((x, y), z) => x + y + z } |
@@ -80,7 +86,7 @@
println("Palindrome: " + Pal.parse_all("abaaaba"))
-// well-nested parenthesis parser
+// well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' )
lazy val P : Parser[String, String] =
"(" ~ P ~ ")" ~ P ==> { case (((_, x), _), y) => "{" + x + "}" + y } | ""
@@ -89,7 +95,7 @@
P.parse_all(")(")
P.parse_all("()")
-// arithmetic expressions
+// Arithmetic Expressions
lazy val E: Parser[String, Int] =
(T ~ "+" ~ E) ==> { case ((x, y), z) => x + z } |
@@ -149,15 +155,13 @@
U.parse_all("1" * 100 + "0")
lazy val UCount : Parser[String, Int] =
- ("1" ~ UCount) ==> { case (x, y) => y + 1 } |
- "" ==> { x => 0 }
+ ("1" ~ UCount) ==> { case (x, y) => y + 1 } | "" ==> { x => 0 }
UCount.parse("11111")
UCount.parse_all("11111")
-
// Single Character parser
lazy val One : Parser[String, String] = "1"
lazy val Two : Parser[String, String] = "2"
--- a/progs/comb2.scala Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/comb2.scala Sun Jul 28 14:24:46 2019 +0100
@@ -1,28 +1,28 @@
-// A parser and evaluator for the while language
+// A parser and interpreter for the While language
//
import scala.language.implicitConversions
import scala.language.reflectiveCalls
-abstract class Parser[I <% Seq[_], T] {
+abstract class Parser[I, T](implicit ev: I => Seq[_]) {
def parse(ts: I): Set[(T, I)]
def parse_all(ts: I) : Set[T] =
for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head
}
-class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {
+class SeqParser[I, T, S](p: => Parser[I, T], q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, (T, S)] {
def parse(sb: I) =
for ((head1, tail1) <- p.parse(sb);
(head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)
}
-class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {
+class AltParser[I, T](p: => Parser[I, T], q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] {
def parse(sb: I) = p.parse(sb) ++ q.parse(sb)
}
-class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {
+class FunParser[I, T, S](p: => Parser[I, T], f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] {
def parse(sb: I) =
for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
}
@@ -48,7 +48,7 @@
implicit def string2parser(s : String) = StringParser(s)
-implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = new {
+implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new {
def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
@@ -141,7 +141,7 @@
// an interpreter for the WHILE language
type Env = Map[String, Int]
-def eval_aexp(a: AExp, env : Env) : Int = a match {
+def eval_aexp(a: AExp, env: Env) : Int = a match {
case Num(i) => i
case Var(s) => env(s)
case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
@@ -174,4 +174,6 @@
def eval(bl: Block) : Env = eval_bl(bl, Map())
+// parse + evaluate fib program; then lookup what is
+// stored under the variable result
println(eval(Block.parse_all(fib).head)("result"))
--- a/progs/compile.scala Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/compile.scala Sun Jul 28 14:24:46 2019 +0100
@@ -1,6 +1,7 @@
// A Small Compiler for the WHILE Language
// (it does not use a parser and lexer)
+
// the abstract syntax trees
abstract class Stmt
abstract class AExp
@@ -85,16 +86,18 @@
.limit locals 200
.limit stack 200
+; COMPILED CODE STARTS
+
"""
val ending = """
-
+; COMPILED CODE ENDS
return
.end method
"""
-println("Start compilation")
+// Compiler functions
// for generating new labels
@@ -105,46 +108,51 @@
x ++ "_" ++ counter.toString()
}
-// environments and instructions
+// convenient string interpolations
+// for 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"
+}
+
+
+// environments
type Env = Map[String, String]
-type Instrs = List[String]
// arithmetic expression compilation
-def compile_aexp(a: AExp, env : Env) : Instrs = a match {
- case Num(i) => List("ldc " + i.toString + "\n")
- case Var(s) => List("iload " + env(s) + "\n")
+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("+", a1, a2) =>
- compile_aexp(a1, env) ++
- compile_aexp(a2, env) ++ List("iadd\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"iadd"
case Aop("-", a1, a2) =>
- compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("isub\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"isub"
case Aop("*", a1, a2) =>
- compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ List("imul\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"imul"
}
// boolean expression compilation
-def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match {
- case True => Nil
- case False => List("goto " + jmp + "\n")
+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) ++
- List("if_icmpne " + jmp + "\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpne $jmp"
case Bop("!=", a1, a2) =>
- compile_aexp(a1, env) ++ compile_aexp(a2, env) ++
- List("if_icmpeq " + jmp + "\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpeq $jmp"
case Bop("<", a1, a2) =>
- compile_aexp(a1, env) ++ compile_aexp(a2, env) ++
- List("if_icmpge " + jmp + "\n")
+ compile_aexp(a1, env) ++ compile_aexp(a2, env) ++ i"if_icmpge $jmp"
}
// statement compilation
-def compile_stmt(s: Stmt, env: Env) : (Instrs, Env) = s match {
- case Skip => (Nil, env)
+def compile_stmt(s: Stmt, env: Env) : (String, Env) = s match {
+ case Skip => ("", env)
case Assign(x, a) => {
val index = if (env.isDefinedAt(x)) env(x) else
env.keys.size.toString
- (compile_aexp(a, env) ++
- List("istore " + index + "\n"), env + (x -> index))
+ (compile_aexp(a, env) ++ i"istore $index", env + (x -> index))
}
case If(b, bl1, bl2) => {
val if_else = Fresh("If_else")
@@ -153,35 +161,35 @@
val (instrs2, env2) = compile_block(bl2, env1)
(compile_bexp(b, env, if_else) ++
instrs1 ++
- List("goto " + if_end + "\n") ++
- List("\n" + if_else + ":\n\n") ++
+ i"goto $if_end" ++
+ l"$if_else" ++
instrs2 ++
- List("\n" + if_end + ":\n\n"), env2)
+ 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)
- (List("\n" + loop_begin + ":\n\n") ++
+ (l"$loop_begin" ++
compile_bexp(b, env, loop_end) ++
instrs1 ++
- List("goto " + loop_begin + "\n") ++
- List("\n" + loop_end + ":\n\n"), env1)
+ i"goto $loop_begin" ++
+ l"$loop_end", env1)
}
case Write(x) =>
- (List("iload " + env(x) + "\n" +
- "invokestatic XXX/XXX/write(I)V\n"), env)
+ (i"iload ${env(x)}" ++
+ i"invokestatic XXX/XXX/write(I)V", env)
case Read(x) => {
val index = if (env.isDefinedAt(x)) env(x) else
env.keys.size.toString
- (List("invokestatic XXX/XXX/read()I\n" +
- "istore " + index + "\n"), env + (x -> index))
+ (i"invokestatic XXX/XXX/read()I" ++
+ i"istore $index", env + (x -> index))
}
}
// compilation of a block (i.e. list of instructions)
-def compile_block(bl: Block, env: Env) : (Instrs, Env) = bl match {
- case Nil => (Nil, env)
+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)
@@ -237,6 +245,7 @@
def compile_run(bl: Block, class_name: String) : Unit = {
println("Start compilation")
compile_all(bl, class_name)
+ println("running")
println("Time: " + time_needed(1, ("java " + class_name + "/" + class_name).!))
}
--- a/progs/fib.j Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/fib.j Sun Jul 28 14:24:46 2019 +0100
@@ -17,28 +17,18 @@
return
.end method
-.method public static writes(Ljava/lang/String;)V
- .limit stack 2
- .limit locals 1
- getstatic java/lang/System/out Ljava/io/PrintStream;
- aload 0
- invokevirtual java/io/PrintStream/println(Ljava/lang/String;)V
- return
-.end method
-
.method public static read()I
.limit locals 10
.limit stack 10
ldc 0
istore 1 ; this will hold our final integer
-
Label1:
getstatic java/lang/System/in Ljava/io/InputStream;
invokevirtual java/io/InputStream/read()I
istore 2
iload 2
- ldc 10 ; the newline delimiter
+ ldc 10 ; the newline delimiter
isub
ifeq Label2
iload 2
@@ -54,11 +44,10 @@
imul
iadd
istore 1
- goto Label2
goto Label1
-
Label2:
- iload 1 ; when we come here we have our integer computed in local variable 1
+ ;when we come here we have our integer computed in local variable 1
+ iload 1
ireturn
.end method
@@ -66,40 +55,38 @@
.limit locals 200
.limit stack 200
-ldc 10
-istore 0
-ldc 0
-istore 1
-ldc 1
-istore 2
-ldc 0
-istore 3
-
-Loop_begin_0:
+; COMPILED CODE STARTS
-ldc 0
-iload 0
-if_icmpge Loop_end_1
-iload 2
-istore 3
-iload 1
-iload 2
-iadd
-istore 2
-iload 3
-istore 1
-iload 0
-ldc 1
-isub
-istore 0
-goto Loop_begin_0
+ ldc 10
+ istore 0
+ ldc 0
+ istore 1
+ ldc 1
+ istore 2
+ ldc 0
+ istore 3
+Loop_begin_0:
+ ldc 0
+ iload 0
+ if_icmpge Loop_end_1
+ iload 2
+ istore 3
+ iload 1
+ iload 2
+ iadd
+ istore 2
+ iload 3
+ istore 1
+ iload 0
+ ldc 1
+ isub
+ istore 0
+ goto Loop_begin_0
+Loop_end_1:
+ iload 1
+ invokestatic fib/fib/write(I)V
-Loop_end_1:
-
-iload 1
-invokestatic fib/fib/write(I)V
-
-
+; COMPILED CODE ENDS
return
.end method
--- a/progs/fun-bare.scala Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/fun-bare.scala Sun Jul 28 14:24:46 2019 +0100
@@ -1,4 +1,5 @@
-// A Small Compiler for a simple functional language
+// A Small Compiler for a Simple Functional Language
+// (it does not use a parser and lexer)
// Abstract syntax trees
abstract class Exp
@@ -69,83 +70,92 @@
x ++ "_" ++ counter.toString()
}
+// convenient string interpolations
+// for instructions, labels and methods
+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 m(args: Any*): String = sc.s(args:_*) ++ "\n"
+}
type Env = Map[String, Int]
-type Instrs = List[String]
// compile expressions
-def compile_exp(a: Exp, env : Env) : Instrs = a match {
- case Num(i) => List("ldc " + i.toString + "\n")
- case Var(s) => List("iload " + env(s).toString + "\n")
- case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("iadd\n")
- case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("isub\n")
- case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("imul\n")
- case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("idiv\n")
- case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("irem\n")
+def compile_exp(a: Exp, env : Env) : String = a match {
+ case Num(i) => i"ldc $i"
+ case Var(s) => i"iload ${env(s)}"
+ case Aop("+", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"iadd"
+ case Aop("-", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"isub"
+ case Aop("*", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"imul"
+ case Aop("/", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"idiv"
+ case Aop("%", a1, a2) => compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"irem"
case If(b, a1, a2) => {
val if_else = Fresh("If_else")
val if_end = Fresh("If_end")
compile_bexp(b, env, if_else) ++
compile_exp(a1, env) ++
- List("goto " + if_end + "\n") ++
- List("\n" + if_else + ":\n\n") ++
+ i"goto $if_end" ++
+ l"$if_else" ++
compile_exp(a2, env) ++
- List("\n" + if_end + ":\n\n")
+ l"$if_end"
}
- case Call(n, args) => {
+ case Call(name, args) => {
val is = "I" * args.length
- args.flatMap(a => compile_exp(a, env)) ++
- List ("invokestatic XXX/XXX/" + n + "(" + is + ")I\n")
+ args.map(a => compile_exp(a, env)).mkString ++
+ i"invokestatic XXX/XXX/$name($is)I"
}
case Sequ(a1, a2) => {
- compile_exp(a1, env) ++ List("pop\n") ++ compile_exp(a2, env)
+ compile_exp(a1, env) ++ i"pop" ++ compile_exp(a2, env)
}
case Write(a1) => {
compile_exp(a1, env) ++
- List("dup\n",
- "invokestatic XXX/XXX/write(I)V\n")
+ i"dup" ++
+ i"invokestatic XXX/XXX/write(I)V"
}
}
// compile boolean expressions
-def compile_bexp(b: BExp, env : Env, jmp: String) : Instrs = b match {
+def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match {
case Bop("==", a1, a2) =>
- compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpne " + jmp + "\n")
+ compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpne $jmp"
case Bop("!=", a1, a2) =>
- compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpeq " + jmp + "\n")
+ compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpeq $jmp"
case Bop("<", a1, a2) =>
- compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpge " + jmp + "\n")
+ compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpge $jmp"
case Bop("<=", a1, a2) =>
- compile_exp(a1, env) ++ compile_exp(a2, env) ++ List("if_icmpgt " + jmp + "\n")
+ compile_exp(a1, env) ++ compile_exp(a2, env) ++ i"if_icmpgt $jmp"
}
// compile function for declarations and main
-def compile_decl(d: Decl) : Instrs = d match {
+def compile_decl(d: Decl) : String = d match {
case Def(name, args, a) => {
val env = args.zipWithIndex.toMap
val is = "I" * args.length
- List(".method public static " + name + "(" + is + ")I \n",
- ".limit locals " + args.length.toString + "\n",
- ".limit stack " + (1 + max_stack_exp(a)).toString + "\n",
- name + "_Start:\n") ++
+ m".method public static $name($is)I" ++
+ m".limit locals ${args.length.toString}" ++
+ m".limit stack ${1 + max_stack_exp(a)}" ++
+ l"${name}_Start" ++
compile_exp(a, env) ++
- List("ireturn\n",
- ".end method \n\n")
+ i"ireturn" ++
+ m".end method\n"
}
case Main(a) => {
- List(".method public static main([Ljava/lang/String;)V\n",
- ".limit locals 200\n",
- ".limit stack 200\n") ++
+ m".method public static main([Ljava/lang/String;)V" ++
+ m".limit locals 200" ++
+ m".limit stack 200" ++
compile_exp(a, Map()) ++
- List("invokestatic XXX/XXX/write(I)V\n",
- "return\n",
- ".end method\n")
+ i"invokestatic XXX/XXX/write(I)V" ++
+ i"return" ++
+ m".end method\n"
}
}
// main compilation function
def compile(prog: List[Decl], class_name: String) : String = {
- val instructions = prog.flatMap(compile_decl).mkString
+ val instructions = prog.map(compile_decl).mkString
(library + instructions).replaceAllLiterally("XXX", class_name)
}
@@ -171,4 +181,4 @@
Write(Call("facT",List(Num(10), Num(1)))))))
// prints out the JVM instructions
-println(compile(test, "fact"))
+println(compile(test_prog, "fact"))
--- a/progs/token.scala Sun Jul 28 01:00:41 2019 +0100
+++ b/progs/token.scala Sun Jul 28 14:24:46 2019 +0100
@@ -1,4 +1,4 @@
-// Simple Tokenizer according to Sulzmann & Lu
+// A Simple Tokenizer according to Sulzmann & Lu
import scala.language.implicitConversions
import scala.language.reflectiveCalls
@@ -48,7 +48,7 @@
// A test for more conveninet syntax
val re : Rexp = ("ab" | "a") ~ ("b" | ONE)
-// nullable function: tests whether the regular
+// the nullable function: tests whether the regular
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
case ZERO => false
@@ -60,7 +60,7 @@
case RECD(_, r1) => nullable(r1)
}
-// derivative of a regular expression w.r.t. a character
+// 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
@@ -73,7 +73,7 @@
case RECD(_, r1) => der(c, r1)
}
-// derivative w.r.t. a string (iterates der)
+// 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))
@@ -90,7 +90,7 @@
case Rec(_, v) => flatten(v)
}
-// extracts an environment from a value
+// extracts an environment from a value;
// used for tokenise a string
def env(v: Val) : List[(String, String)] = v match {
case Empty => Nil
@@ -102,7 +102,10 @@
case Rec(x, v) => (x, flatten(v))::env(v)
}
-// injection part
+// The Injection Part of the Tokeniser
+
+// calculates a value for how a nullable regex
+// matches the empty string
def mkeps(r: Rexp) : Val = r match {
case ONE => Empty
case ALT(r1, r2) =>
@@ -112,7 +115,7 @@
case RECD(x, r) => Rec(x, mkeps(r))
}
-
+// injects back a character into a value
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)
@@ -124,7 +127,7 @@
case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
}
-// main lexing function (produces a value)
+// the 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")
@@ -157,8 +160,8 @@
}
def F_ERROR(v: Val): Val = throw new Exception("error")
-// simplification of regular expressions returning also an
-// rectification function; no simplification under STAR
+// simplification of regular expressions returns now 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)
@@ -188,6 +191,7 @@
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("Not matched")
case c::cs => {
@@ -200,7 +204,7 @@
lexing_simp(("a" | "ab") ~ ("b" | ""), "ab")
-// Lexing Rules for a Small While Language
+// The Lexing Rules for a Small While Language
def PLUS(r: Rexp) = r ~ r.%
@@ -285,7 +289,7 @@
// some more timing tests with
// i copies of the program
-for (i <- 1 to 21 by 10) {
+for (i <- 0 to 20 by 10) {
print(i.toString + ": ")
time(lexing_simp(WHILE_REGS, prog2 * i))
}