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 Seq(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(v: Val) : List[(String, String)] = 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 Seq(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(x, v) => (x, 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 |
101 case ALT(r1, r2) => |
101 case ALT(r1, r2) => |
102 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
102 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
103 case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) |
103 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
104 case STAR(r) => Stars(Nil) |
104 case STAR(r) => Stars(Nil) |
105 case RECD(x, r) => Rec(x, mkeps(r)) |
105 case RECD(x, r) => Rec(x, mkeps(r)) |
106 } |
106 } |
107 |
107 |
108 |
108 |
109 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
109 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match { |
110 case (STAR(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
110 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
111 case (SEQ(r1, r2), Seq(v1, v2)) => Seq(inj(r1, c, v1), v2) |
111 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
112 case (SEQ(r1, r2), Left(Seq(v1, v2))) => Seq(inj(r1, c, v1), v2) |
112 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
113 case (SEQ(r1, r2), Right(v2)) => Seq(mkeps(r1), inj(r2, c, v2)) |
113 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
114 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
114 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
115 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
115 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
116 case (CHAR(d), Empty) => Chr(c) |
116 case (CHAR(d), Empty) => Chr(c) |
117 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
117 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
118 } |
118 } |
138 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
138 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
139 case Right(v) => Right(f2(v)) |
139 case Right(v) => Right(f2(v)) |
140 case Left(v) => Left(f1(v)) |
140 case Left(v) => Left(f1(v)) |
141 } |
141 } |
142 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
142 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
143 case Seq(v1, v2) => Seq(f1(v1), f2(v2)) |
143 case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
144 } |
144 } |
145 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
145 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
146 (v:Val) => Seq(f1(Empty), f2(v)) |
146 (v:Val) => Sequ(f1(Empty), f2(v)) |
147 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
147 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
148 (v:Val) => Seq(f1(v), f2(Empty)) |
148 (v:Val) => Sequ(f1(v), f2(Empty)) |
149 def F_RECD(f: Val => Val) = (v:Val) => v match { |
149 def F_RECD(f: Val => Val) = (v:Val) => v match { |
150 case Rec(x, v) => Rec(x, f(v)) |
150 case Rec(x, v) => Rec(x, f(v)) |
151 } |
151 } |
152 def F_ERROR(v: Val): Val = throw new Exception("error") |
152 def F_ERROR(v: Val): Val = throw new Exception("error") |
153 |
153 |