1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
3 import scala.annotation.tailrec |
|
4 |
3 |
5 abstract class Rexp |
4 abstract class Rexp |
6 case object ZERO extends Rexp |
5 case object ZERO extends Rexp |
7 case object ONE extends Rexp |
6 case object ONE extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
7 case class CHAR(c: Char) extends Rexp |
118 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
117 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
119 } |
118 } |
120 |
119 |
121 // main lexing function (produces a value) |
120 // main lexing function (produces a value) |
122 def lex(r: Rexp, s: List[Char]) : Val = s match { |
121 def lex(r: Rexp, s: List[Char]) : Val = s match { |
123 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
122 case Nil => if (nullable(r)) mkeps(r) |
|
123 else throw new Exception("Not matched") |
124 case c::cs => inj(r, c, lex(der(c, r), cs)) |
124 case c::cs => inj(r, c, lex(der(c, r), cs)) |
125 } |
125 } |
126 |
126 |
127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
128 |
128 |
129 lexing(("ab" | "ab") ~ ("b" | ONE), "ab") |
129 |
|
130 lexing(("ab" | "a") ~ ("b" | ONE), "ab") |
|
131 |
|
132 |
130 |
133 |
131 // some "rectification" functions for simplification |
134 // some "rectification" functions for simplification |
132 def F_ID(v: Val): Val = v |
135 def F_ID(v: Val): Val = v |
133 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
136 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
134 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
137 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
192 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") |
195 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab") |
193 |
196 |
194 // Lexing Rules for a Small While Language |
197 // Lexing Rules for a Small While Language |
195 |
198 |
196 def PLUS(r: Rexp) = r ~ r.% |
199 def PLUS(r: Rexp) = r ~ r.% |
|
200 |
197 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |
201 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |
198 val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" |
202 val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" |
199 val ID = SYM ~ (SYM | DIGIT).% |
203 val ID = SYM ~ (SYM | DIGIT).% |
200 val NUM = PLUS(DIGIT) |
204 val NUM = PLUS(DIGIT) |
201 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
205 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
268 write minus2 |
272 write minus2 |
269 """ |
273 """ |
270 |
274 |
271 println("Tokens") |
275 println("Tokens") |
272 println(env(lexing_simp(WHILE_REGS, prog2))) |
276 println(env(lexing_simp(WHILE_REGS, prog2))) |
273 |
277 println(env(lexing_simp(WHILE_REGS, prog2)).filterNot{_._1 == "w"}.mkString("\n")) |
274 for (i <- 1 to 80) { |
278 |
|
279 // some more timing tests |
|
280 for (i <- 1 to 101 by 10) { |
275 print(i.toString + ": ") |
281 print(i.toString + ": ") |
276 time(lexing_simp(WHILE_REGS, prog2 * i)) |
282 time(lexing_simp(WHILE_REGS, prog2 * i)) |
277 } |
283 } |
278 |
284 |
279 |
285 |