6 case object ONE extends Rexp |
6 case object ONE extends Rexp |
7 case class CHAR(c: Char) extends Rexp |
7 case class CHAR(c: Char) extends Rexp |
8 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
8 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
9 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class STAR(r: Rexp) extends Rexp |
10 case class STAR(r: Rexp) extends Rexp |
11 case class RECD(x: String, r: Rexp) extends Rexp |
11 case class RECD[A](f: String => A, r: Rexp) extends Rexp |
12 |
12 |
13 abstract class Val |
13 abstract class Val |
14 case object Empty extends Val |
14 case object Empty extends Val |
15 case class Chr(c: Char) extends Val |
15 case class Chr(c: Char) extends Val |
16 case class Sequ(v1: Val, v2: Val) extends Val |
16 case class Sequ(v1: Val, v2: Val) extends Val |
17 case class Left(v: Val) extends Val |
17 case class Left(v: Val) extends Val |
18 case class Right(v: Val) extends Val |
18 case class Right(v: Val) extends Val |
19 case class Stars(vs: List[Val]) extends Val |
19 case class Stars(vs: List[Val]) extends Val |
20 case class Rec(x: String, v: Val) extends Val |
20 case class Rec[A](f: String => A, v: Val) extends Val |
21 |
21 |
22 // some convenience for typing in regular expressions |
22 // some convenience for typing in regular expressions |
23 def charlist2rexp(s : List[Char]): Rexp = s match { |
23 def charlist2rexp(s : List[Char]): Rexp = s match { |
24 case Nil => ONE |
24 case Nil => ONE |
25 case c::Nil => CHAR(c) |
25 case c::Nil => CHAR(c) |
77 def flatten(v: Val) : String = v match { |
77 def flatten(v: Val) : String = v match { |
78 case Empty => "" |
78 case Empty => "" |
79 case Chr(c) => c.toString |
79 case Chr(c) => c.toString |
80 case Left(v) => flatten(v) |
80 case Left(v) => flatten(v) |
81 case Right(v) => flatten(v) |
81 case Right(v) => flatten(v) |
82 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
82 case Sequ(v1, v2) => flatten(v1) ++ flatten(v2) |
83 case Stars(vs) => vs.map(flatten).mkString |
83 case Stars(vs) => vs.map(flatten).mkString |
84 case Rec(_, v) => flatten(v) |
84 case Rec(_, v) => flatten(v) |
85 } |
85 } |
86 |
86 |
87 // extracts an environment from a value |
87 // extracts an environment from a value |
88 def env(v: Val) : List[(String, String)] = v match { |
88 def env[A](v: Val) : List[A] = v match { |
89 case Empty => Nil |
89 case Empty => Nil |
90 case Chr(c) => Nil |
90 case Chr(c) => Nil |
91 case Left(v) => env(v) |
91 case Left(v) => env(v) |
92 case Right(v) => env(v) |
92 case Right(v) => env(v) |
93 case Sequ(v1, v2) => env(v1) ::: env(v2) |
93 case Sequ(v1, v2) => env(v1) ::: env(v2) |
94 case Stars(vs) => vs.flatMap(env) |
94 case Stars(vs) => vs.flatMap(env) |
95 case Rec(x, v) => (x, flatten(v))::env(v) |
95 case Rec(f, v) => ((f:String => A)(flatten(v)))::env(v) |
96 } |
96 } |
97 |
97 |
98 // injection part |
98 // injection part |
99 def mkeps(r: Rexp) : Val = r match { |
99 def mkeps(r: Rexp) : Val = r match { |
100 case ONE => Empty |
100 case ONE => Empty |
209 val BEGIN: Rexp = "{" |
209 val BEGIN: Rexp = "{" |
210 val END: Rexp = "}" |
210 val END: Rexp = "}" |
211 val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
211 val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
212 |
212 |
213 |
213 |
214 val WHILE_REGS = (("k" $ KEYWORD) | |
214 val WHILE_REGS = (((s) => Token $ KEYWORD) | |
215 ("i" $ ID) | |
215 ("i" $ ID) | |
216 ("o" $ OP) | |
216 ("o" $ OP) | |
217 ("n" $ NUM) | |
217 ("n" $ NUM) | |
218 ("s" $ SEMI) | |
218 ("s" $ SEMI) | |
219 ("str" $ STRING) | |
219 ("str" $ STRING) | |
220 ("p" $ (LPAREN | RPAREN)) | |
220 ("p" $ (LPAREN | RPAREN)) | |
221 ("b" $ (BEGIN | END)) | |
221 ("b" $ (BEGIN | END)) | |
222 ("w" $ WHITESPACE)).% |
222 ("w" $ WHITESPACE)).% |
|
223 |
|
224 |
|
225 |
|
226 |
|
227 // extracts an environment from a value |
|
228 def env(v: Val) : List[Token] = v match { |
|
229 case Empty => Nil |
|
230 case Chr(c) => Nil |
|
231 case Left(v) => env(v) |
|
232 case Right(v) => env(v) |
|
233 case Sequ(v1, v2) => env(v1) ::: env(v2) |
|
234 case Stars(vs) => vs.flatMap(env) |
|
235 case Rec(f, v) => (f(flatten(v)))::env(v) |
|
236 } |
223 |
237 |
224 // Testing |
238 // Testing |
225 //============ |
239 //============ |
226 |
240 |
227 def time[T](code: => T) = { |
241 def time[T](code: => T) = { |
280 for (i <- 1 to 21 by 10) { |
294 for (i <- 1 to 21 by 10) { |
281 print(i.toString + ": ") |
295 print(i.toString + ": ") |
282 time(lexing_simp(WHILE_REGS, prog2 * i)) |
296 time(lexing_simp(WHILE_REGS, prog2 * i)) |
283 } |
297 } |
284 |
298 |
285 |
299 abstract class Token |
|
300 case class KeyToken(s: String) extends Token |
|
301 case class IdToken(s: String) extends Token |
|
302 |
|
303 list[(STRING, STRING)]=> List(TOKEN) |