equal
deleted
inserted
replaced
52 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
52 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
53 case STAR(r) => 1 + size(r) |
53 case STAR(r) => 1 + size(r) |
54 case RECD(_, r) => 1 + size(r) |
54 case RECD(_, r) => 1 + size(r) |
55 } |
55 } |
56 |
56 |
|
57 // extracts a set of candidate values from a "non-starred" regular expression |
|
58 def values(r: Rexp) : Set[Val] = r match { |
|
59 case NULL => Set() |
|
60 case EMPTY => Set(Void) |
|
61 case CHAR(c) => Set(Chr(c)) |
|
62 case ALT(r1, r2) => values(r1) ++ values(r2) |
|
63 case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2) |
|
64 case STAR(r) => Set(Void) ++ values(r) // to do more would cause the set to be infinite |
|
65 case RECD(_, r) => values(r) |
|
66 } |
|
67 |
57 |
68 |
58 // nullable function: tests whether the regular |
69 // nullable function: tests whether the regular |
59 // expression can recognise the empty string |
70 // expression can recognise the empty string |
60 def nullable (r: Rexp) : Boolean = r match { |
71 def nullable (r: Rexp) : Boolean = r match { |
61 case NULL => false |
72 case NULL => false |
106 case Sequ(v1, v2) => env(v1) ::: env(v2) |
117 case Sequ(v1, v2) => env(v1) ::: env(v2) |
107 case Stars(vs) => vs.flatMap(env) |
118 case Stars(vs) => vs.flatMap(env) |
108 case Rec(x, v) => (x, flatten(v))::env(v) |
119 case Rec(x, v) => (x, flatten(v))::env(v) |
109 } |
120 } |
110 |
121 |
|
122 // injection part |
111 def mkeps(r: Rexp) : Val = r match { |
123 def mkeps(r: Rexp) : Val = r match { |
112 case EMPTY => Void |
124 case EMPTY => Void |
113 case ALT(r1, r2) => |
125 case ALT(r1, r2) => |
114 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
126 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
115 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
127 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
246 val result = code |
258 val result = code |
247 val end = System.nanoTime() |
259 val end = System.nanoTime() |
248 println((end - start)/1.0e9) |
260 println((end - start)/1.0e9) |
249 result |
261 result |
250 } |
262 } |
|
263 |
|
264 val r = ("a" | "ab") ~ ("bcd" | "c") |
|
265 println(lexing(r, "abcd")) |
|
266 println(values(r).mkString("\n")) |
|
267 println(values(r).map(flatten).mkString("\n")) |
251 |
268 |
252 // Two Simple Tests |
269 // Two Simple Tests |
253 //=================== |
270 //=================== |
254 println("prog0 test") |
271 println("prog0 test") |
255 |
272 |