41 def ~ (r: Rexp) = SEQ(s, r) |
41 def ~ (r: Rexp) = SEQ(s, r) |
42 def ~ (r: String) = SEQ(s, r) |
42 def ~ (r: String) = SEQ(s, r) |
43 def $ (r: Rexp) = RECD(s, r) |
43 def $ (r: Rexp) = RECD(s, r) |
44 } |
44 } |
45 |
45 |
|
46 def pretty(r: Rexp) : String = r match { |
|
47 case NULL => "0" |
|
48 case EMPTY => "e" |
|
49 case CHAR(c) => c.toString |
|
50 case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")" |
|
51 case SEQ(r1, r2) => pretty(r1) ++ pretty(r2) |
|
52 case STAR(r) => "(" ++ pretty(r) ++ ")*" |
|
53 case RECD(x, r) => "(" ++ x ++ " : " ++ pretty(r) ++ ")" |
|
54 } |
|
55 |
|
56 def vpretty(v: Val) : String = v match { |
|
57 case Void => "()" |
|
58 case Chr(c) => c.toString |
|
59 case Left(v) => "Left(" ++ vpretty(v) ++ ")" |
|
60 case Right(v) => "Right(" ++ vpretty(v) ++ ")" |
|
61 case Sequ(v1, v2) => vpretty(v1) ++ " ~ " ++ vpretty(v2) |
|
62 case Stars(vs) => vs.flatMap(vpretty).mkString("[", ",", "]") |
|
63 case Rec(x, v) => "(" ++ x ++ ":" ++ vpretty(v) ++ ")" |
|
64 } |
|
65 |
|
66 |
46 // size of a regular expressions - for testing purposes |
67 // size of a regular expressions - for testing purposes |
47 def size(r: Rexp) : Int = r match { |
68 def size(r: Rexp) : Int = r match { |
48 case NULL => 1 |
69 case NULL => 1 |
49 case EMPTY => 1 |
70 case EMPTY => 1 |
50 case CHAR(_) => 1 |
71 case CHAR(_) => 1 |
57 // extracts a set of candidate values from a "non-starred" regular expression |
78 // extracts a set of candidate values from a "non-starred" regular expression |
58 def values(r: Rexp) : Set[Val] = r match { |
79 def values(r: Rexp) : Set[Val] = r match { |
59 case NULL => Set() |
80 case NULL => Set() |
60 case EMPTY => Set(Void) |
81 case EMPTY => Set(Void) |
61 case CHAR(c) => Set(Chr(c)) |
82 case CHAR(c) => Set(Chr(c)) |
62 case ALT(r1, r2) => values(r1) ++ values(r2) |
83 case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ |
|
84 (for (v2 <- values(r2)) yield Right(v2)) |
63 case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2) |
85 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 |
86 case STAR(r) => Set(Void) ++ values(r) // to do more would cause the set to be infinite |
65 case RECD(_, r) => values(r) |
87 case RECD(_, r) => values(r) |
66 } |
88 } |
67 |
89 |
269 val r2 = ("" | "a") ~ ("ab" | "b") |
291 val r2 = ("" | "a") ~ ("ab" | "b") |
270 println(lexing(r2, "ab")) |
292 println(lexing(r2, "ab")) |
271 println(values(r2).mkString("\n")) |
293 println(values(r2).mkString("\n")) |
272 println(values(r2).toList.map(flatten).mkString("\n")) |
294 println(values(r2).toList.map(flatten).mkString("\n")) |
273 |
295 |
|
296 //Some experiments |
|
297 //================ |
|
298 |
|
299 val reg0 = ("" | "a") ~ ("ab" | "b") |
|
300 val reg1 = der('a', reg0) |
|
301 val reg2 = der('b', reg1) |
|
302 println(List(reg0, reg1, reg2).map(pretty).mkString("\n")) |
|
303 println(lexing(reg0, "ab")) |
|
304 |
|
305 val val0 = values(reg0) |
|
306 val val1 = values(reg1) |
|
307 val val2 = values(reg2) |
274 |
308 |
275 |
309 |
276 // Two Simple Tests |
310 // Two Simple Tests |
277 //=================== |
311 //=================== |
278 println("prog0 test") |
312 println("prog0 test") |