# HG changeset patch # User Christian Urban # Date 1564320286 -3600 # Node ID 8d0af38389bcda6e49a18a0d5e53ac9f382d9a59 # Parent 47a299e7010f406295db8f40edc1054de0d13f7c updated to Scala 2.13 diff -r 47a299e7010f -r 8d0af38389bc progs/comb1.scala --- 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" diff -r 47a299e7010f -r 8d0af38389bc progs/comb2.scala --- 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")) diff -r 47a299e7010f -r 8d0af38389bc progs/compile.scala --- 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).!)) } diff -r 47a299e7010f -r 8d0af38389bc progs/fib.j --- 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 diff -r 47a299e7010f -r 8d0af38389bc progs/fun-bare.scala --- 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")) diff -r 47a299e7010f -r 8d0af38389bc progs/token.scala --- 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)) }