equal
deleted
inserted
replaced
|
1 // Simple Tokenizer according to Sulzmann & Lu |
|
2 |
1 import scala.language.implicitConversions |
3 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
4 import scala.language.reflectiveCalls |
3 |
5 |
4 abstract class Rexp |
6 abstract class Rexp |
5 case object ZERO extends Rexp |
7 case object ZERO extends Rexp |
7 case class CHAR(c: Char) extends Rexp |
9 case class CHAR(c: Char) extends Rexp |
8 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class STAR(r: Rexp) extends Rexp |
12 case class STAR(r: Rexp) extends Rexp |
11 case class RECD(x: String, r: Rexp) extends Rexp |
13 case class RECD(x: String, r: Rexp) extends Rexp |
12 |
14 |
13 abstract class Val |
15 abstract class Val |
14 case object Empty extends Val |
16 case object Empty extends Val |
15 case class Chr(c: Char) extends Val |
17 case class Chr(c: Char) extends Val |
16 case class Sequ(v1: Val, v2: Val) extends Val |
18 case class Sequ(v1: Val, v2: Val) extends Val |
17 case class Left(v: Val) extends Val |
19 case class Left(v: Val) extends Val |
23 def charlist2rexp(s : List[Char]): Rexp = s match { |
25 def charlist2rexp(s : List[Char]): Rexp = s match { |
24 case Nil => ONE |
26 case Nil => ONE |
25 case c::Nil => CHAR(c) |
27 case c::Nil => CHAR(c) |
26 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
28 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
27 } |
29 } |
28 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
30 implicit def string2rexp(s : String) : Rexp = |
|
31 charlist2rexp(s.toList) |
29 |
32 |
30 implicit def RexpOps(r: Rexp) = new { |
33 implicit def RexpOps(r: Rexp) = new { |
31 def | (s: Rexp) = ALT(r, s) |
34 def | (s: Rexp) = ALT(r, s) |
32 def % = STAR(r) |
35 def % = STAR(r) |
33 def ~ (s: Rexp) = SEQ(r, s) |
36 def ~ (s: Rexp) = SEQ(r, s) |
39 def % = STAR(s) |
42 def % = STAR(s) |
40 def ~ (r: Rexp) = SEQ(s, r) |
43 def ~ (r: Rexp) = SEQ(s, r) |
41 def ~ (r: String) = SEQ(s, r) |
44 def ~ (r: String) = SEQ(s, r) |
42 def $ (r: Rexp) = RECD(s, r) |
45 def $ (r: Rexp) = RECD(s, r) |
43 } |
46 } |
|
47 |
|
48 // A test for more conveninet syntax |
|
49 val re : Rexp = ("ab" | "a") ~ ("b" | ONE) |
44 |
50 |
45 // nullable function: tests whether the regular |
51 // nullable function: tests whether the regular |
46 // expression can recognise the empty string |
52 // expression can recognise the empty string |
47 def nullable (r: Rexp) : Boolean = r match { |
53 def nullable (r: Rexp) : Boolean = r match { |
48 case ZERO => false |
54 case ZERO => false |
83 case Stars(vs) => vs.map(flatten).mkString |
89 case Stars(vs) => vs.map(flatten).mkString |
84 case Rec(_, v) => flatten(v) |
90 case Rec(_, v) => flatten(v) |
85 } |
91 } |
86 |
92 |
87 // extracts an environment from a value |
93 // extracts an environment from a value |
|
94 // used for tokenise a string |
88 def env(v: Val) : List[(String, String)] = v match { |
95 def env(v: Val) : List[(String, String)] = v match { |
89 case Empty => Nil |
96 case Empty => Nil |
90 case Chr(c) => Nil |
97 case Chr(c) => Nil |
91 case Left(v) => env(v) |
98 case Left(v) => env(v) |
92 case Right(v) => env(v) |
99 case Right(v) => env(v) |
124 case c::cs => inj(r, c, lex(der(c, r), cs)) |
131 case c::cs => inj(r, c, lex(der(c, r), cs)) |
125 } |
132 } |
126 |
133 |
127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
134 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
128 |
135 |
129 |
136 // a simple test for extracting an environment |
130 lexing(("ab" | "a") ~ ("b" | ONE), "ab") |
137 val re1 : Rexp = ("first" $ ("a" | "ab")) ~ ("second" $ ("b" | ONE)) |
|
138 env(lexing(re1, "ab")) |
131 |
139 |
132 // some "rectification" functions for simplification |
140 // some "rectification" functions for simplification |
133 def F_ID(v: Val): Val = v |
141 def F_ID(v: Val): Val = v |
134 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
142 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
135 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
143 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
241 |
249 |
242 // Two Simple While Tests |
250 // Two Simple While Tests |
243 //======================== |
251 //======================== |
244 println("prog0 test") |
252 println("prog0 test") |
245 |
253 |
246 val prog0 = """read n""" |
254 val prog0 = """read if""" |
247 println(env(lexing_simp(WHILE_REGS, prog0))) |
255 println(env(lexing_simp(WHILE_REGS, prog0))) |
248 |
256 |
249 println("prog1 test") |
257 println("prog1 test") |
250 |
258 |
251 val prog1 = """read n; write (n)""" |
259 val prog1 = """read n; write (n)""" |