41 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
41 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
42 else SEQ(der(c, r1), r2) |
42 else SEQ(der(c, r1), r2) |
43 case STAR(r) => SEQ(der(c, r), STAR(r)) |
43 case STAR(r) => SEQ(der(c, r), STAR(r)) |
44 } |
44 } |
45 |
45 |
46 def down(p: Pat) : Rexp = p match { |
46 def down (p: Pat) : Rexp = p match { |
47 case VAR(x: String, w: String, r: Rexp) => r |
47 case VAR(x: String, w: String, r: Rexp) => r |
48 case GRP(x: String, w: String, p: Pat) => down(p) |
48 case GRP(x: String, w: String, p: Pat) => down(p) |
49 case PSEQ(p1: Pat, p2: Pat) => SEQ(down(p1), down(p2)) |
49 case PSEQ(p1: Pat, p2: Pat) => SEQ(down(p1), down(p2)) |
50 case PALT(p1: Pat, p2: Pat) => ALT(down(p1), down(p2)) |
50 case PALT(p1: Pat, p2: Pat) => ALT(down(p1), down(p2)) |
51 case PSTAR(p: Pat) => STAR(down(p)) |
51 case PSTAR(p: Pat) => STAR(down(p)) |
52 } |
52 } |
53 |
53 |
54 def empty(p: Pat) : Pat = p match { |
54 def empty (p: Pat) : Pat = p match { |
55 case VAR(x: String, w: String, r: Rexp) => |
55 case VAR(x: String, w: String, r: Rexp) => |
56 if (nullable(r)) VAR(x, w, EMPTY) |
56 if (nullable(r)) VAR(x, w, EMPTY) |
57 else VAR(x, w, NULL) |
57 else VAR(x, w, NULL) |
58 case GRP(x: String, w: String, p: Pat) => GRP(x, w, empty(p)) |
58 case GRP(x: String, w: String, p: Pat) => GRP(x, w, empty(p)) |
59 case PSEQ(p1: Pat, p2: Pat) => PSEQ(empty(p1), empty(p2)) |
59 case PSEQ(p1: Pat, p2: Pat) => PSEQ(empty(p1), empty(p2)) |
60 case PALT(p1: Pat, p2: Pat) => PALT(empty(p1), empty(p2)) |
60 case PALT(p1: Pat, p2: Pat) => PALT(empty(p1), empty(p2)) |
61 case PSTAR(p: Pat) => PSTAR(empty(p)) |
61 case PSTAR(p: Pat) => PSTAR(empty(p)) |
62 } |
62 } |
63 |
63 |
64 def patder(c: Char, p: Pat) : Pat = p match { |
64 def patder (c: Char, p: Pat) : Pat = p match { |
65 case VAR(x: String, w: String, r: Rexp) => VAR(x, w + c, der(c, r)) |
65 case VAR(x: String, w: String, r: Rexp) => VAR(x, w + c, der(c, r)) |
66 case GRP(x: String, w: String, p: Pat) => GRP(x, w + c, patder(c, p)) |
66 case GRP(x: String, w: String, p: Pat) => GRP(x, w + c, patder(c, p)) |
67 case PSEQ(p1: Pat, p2: Pat) => |
67 case PSEQ(p1: Pat, p2: Pat) => |
68 if (nullable(down(p1))) PALT(PSEQ(patder(c, p1), p2), PSEQ(empty(p1), patder(c, p2))) |
68 if (nullable(down(p1))) PALT(PSEQ(patder(c, p1), p2), PSEQ(empty(p1), patder(c, p2))) |
69 else PSEQ(patder(c, p1), p2) |
69 else PSEQ(patder(c, p1), p2) |
76 case c::s => patders(s, patder(c, p)) |
76 case c::s => patders(s, patder(c, p)) |
77 } |
77 } |
78 |
78 |
79 type Env = Set[List[(String, String)]] |
79 type Env = Set[List[(String, String)]] |
80 |
80 |
81 def special(p: Pat, env: Env) : Env = |
81 def special (p: Pat, env: Env) : Env = |
82 if (env == Set() && nullable(down(p))) Set(Nil) else env |
82 if (env == Set() && nullable(down(p))) Set(Nil) else env |
83 |
83 |
84 |
84 def env (p: Pat) : Env = p match { |
85 def env(p: Pat) : Env = p match { |
|
86 case VAR(x: String, w: String, r: Rexp) => |
85 case VAR(x: String, w: String, r: Rexp) => |
87 if (nullable(r)) Set(List((x, w))) else Set() |
86 if (nullable(r)) Set(List((x, w))) else Set() |
88 case GRP(x: String, w: String, p1: Pat) => |
87 case GRP(x: String, w: String, p1: Pat) => |
89 special(p, for (e <- env(p1)) yield List((x, w)) ++ e) |
88 special(p, for (e <- env(p1)) yield List((x, w)) ++ e) |
90 case PSEQ(p1: Pat, p2: Pat) => |
89 case PSEQ(p1: Pat, p2: Pat) => |
91 special(p, for (e1 <- env(p1); e2 <- env(p2)) yield (e1 ++ e2)) |
90 special(p, for (e1 <- env(p1); e2 <- env(p2)) yield (e1 ++ e2)) |
92 case PALT(p1: Pat, p2: Pat) => special(p, env(p1) ++ env(p2)) |
91 case PALT(p1: Pat, p2: Pat) => special(p, env(p1) ++ env(p2)) |
93 case PSTAR(p1: Pat) => special(p, env(p1)) |
92 case PSTAR(p1: Pat) => special(p, env(p1)) |
94 } |
93 } |
95 |
94 |
96 def matcher(p: Pat, s: String) = env(empty(patders(s.toList, p))) |
95 def matcher (p: Pat, s: String) = env(empty(patders(s.toList, p))) |
97 |
96 |
98 |
97 |
99 // some convenience for typing in regular expressions |
98 // some convenience for typing in regular expressions |
100 def charlist2rexp(s : List[Char]) : Rexp = s match { |
99 def charlist2rexp (s : List[Char]) : Rexp = s match { |
101 case Nil => EMPTY |
100 case Nil => EMPTY |
102 case c::Nil => CHAR(c) |
101 case c::Nil => CHAR(c) |
103 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
102 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
104 } |
103 } |
105 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
104 implicit def string2rexp (s : String) : Rexp = charlist2rexp(s.toList) |
106 |
105 |
107 implicit def RexpOps(r: Rexp) = new { |
106 implicit def RexpOps (r: Rexp) = new { |
108 def | (s: Rexp) = ALT(r, s) |
107 def | (s: Rexp) = ALT(r, s) |
109 def % = STAR(r) |
108 def % = STAR(r) |
110 def ~ (s: Rexp) = SEQ(r, s) |
109 def ~ (s: Rexp) = SEQ(r, s) |
111 } |
110 } |
112 |
111 |
113 implicit def stringOps(s: String) = new { |
112 implicit def stringOps (s: String) = new { |
114 def | (r: Rexp) = ALT(s, r) |
113 def | (r: Rexp) = ALT(s, r) |
115 def | (r: String) = ALT(s, r) |
114 def | (r: String) = ALT(s, r) |
116 def % = STAR(s) |
115 def % = STAR(s) |
117 def ~ (r: Rexp) = SEQ(s, r) |
116 def ~ (r: Rexp) = SEQ(s, r) |
118 def ~ (r: String) = SEQ(s, r) |
117 def ~ (r: String) = SEQ(s, r) |
119 } |
118 } |
120 |
119 |
121 implicit def PatOps(p: Pat) = new { |
120 implicit def PatOps (p: Pat) = new { |
122 def | (q: Pat) = PALT(p, q) |
121 def | (q: Pat) = PALT(p, q) |
123 def % = PSTAR(p) |
122 def % = PSTAR(p) |
124 def ~ (q: Pat) = PSEQ(p, q) |
123 def ~ (q: Pat) = PSEQ(p, q) |
125 } |
124 } |
126 |
125 |