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)) }