127 case Right(v) => flatten(v) |
127 case Right(v) => flatten(v) |
128 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
128 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
129 case Stars(vs) => vs.map(flatten).mkString |
129 case Stars(vs) => vs.map(flatten).mkString |
130 case Rec(_, v) => flatten(v) |
130 case Rec(_, v) => flatten(v) |
131 } |
131 } |
|
132 |
|
133 def flattens(v: Val) : List[String] = v match { |
|
134 case Void => List("") |
|
135 case Chr(c) => List(c.toString) |
|
136 case Left(v) => flattens(v) |
|
137 case Right(v) => flattens(v) |
|
138 case Sequ(v1, v2) => flattens(v1) ::: flattens(v2) |
|
139 case Stars(vs) => vs.flatMap(flattens) |
|
140 case Rec(_, v) => flattens(v) |
|
141 } |
|
142 |
132 |
143 |
133 // extracts an environment from a value |
144 // extracts an environment from a value |
134 def env(v: Val) : List[(String, String)] = v match { |
145 def env(v: Val) : List[(String, String)] = v match { |
135 case Void => Nil |
146 case Void => Nil |
136 case Chr(c) => Nil |
147 case Chr(c) => Nil |
255 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1==v3) => ord(v2, r2, v4) |
266 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1==v3) => ord(v2, r2, v4) |
256 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1!=v3) => ord(v1, r1, v3) |
267 case (Sequ(v1,v2), SEQ(r1,r2), Sequ(v3,v4)) if(v1!=v3) => ord(v1, r1, v3) |
257 case _ => false |
268 case _ => false |
258 } |
269 } |
259 |
270 |
260 def tst(r: Rexp, c: Char) : Set[(Rexp, Val, Val, Val, Val)] = { |
271 def tst(r: Rexp, c: Char) : Set[(Rexp, Val, Val, Val, Val, List[String], List[String])] = { |
261 val r_der = der(c, r) |
272 val r_der = der(c, r) |
262 val vs = values(r_der) |
273 val vs = values(r_der) |
263 for (v1 <- vs; v2 <- vs; |
274 for (v1 <- vs; v2 <- vs; |
264 if (v1 != v2 && ord(v1, r_der, v2) && ord(inj(r, c, v2), r, inj(r, c, v1)))) |
275 if (v1 != v2 && ord(v1, r_der, v2) && ord(inj(r, c, v2), r, inj(r, c, v1)) && |
265 yield (r, v1, v2, inj(r, c, v1), inj(r, c, v2)) |
276 (flatten(inj(r, c, v1)) == flatten(inj(r, c, v2))))) |
266 } |
277 yield (r, v1, v2, inj(r, c, v1), inj(r, c, v2), flattens(inj(r, c, v1)), flattens(inj(r, c, v2))) |
267 |
278 } |
268 def comp(r1: (Rexp, Val, Val, Val, Val), r2: (Rexp, Val, Val, Val, Val)) = size(r1._1) < size(r2._1) |
279 |
269 |
280 def tst2(r: Rexp, c: Char) : Set[(Rexp, Val, Val, Val, Val, List[String], List[String])] = { |
270 |
281 val r_der = der(c, r) |
271 val smallest = enum(3, "a").flatMap(tst(_, 'a')).toList.sortWith { comp }.head |
282 val vs = values(r_der) |
|
283 for (v1 <- vs; v2 <- vs; |
|
284 if (v1 != v2 && ord(v1, r_der, v2) && ord(proj(r, c, v2), r_der, proj(r, c, v1))) |
|
285 yield (r, v1, v2, proj(r, c, v1), proj(r, c, v2), flattens(inj(r, c, v1)), flattens(inj(r, c, v2))) |
|
286 } |
|
287 |
|
288 def comp(r1: (Rexp, Val, Val, Val, Val, List[String], List[String]), |
|
289 r2: (Rexp, Val, Val, Val, Val, List[String], List[String])) = size(r1._1) < size(r2._1) |
|
290 |
|
291 |
|
292 val smallest = enum(3, "a").flatMap(tst(_, 'a')).toList.sortWith { comp } |
272 |
293 |
273 smallest match { |
294 smallest match { |
274 case (r, v1, v2, v3, v4) => List(pretty(r), |
295 case Nil => "none" |
|
296 case (r, v1, v2, v3, v4, s1, s2)::_ => List(pretty(r), |
275 pretty(der('a', r)), |
297 pretty(der('a', r)), |
276 vpretty(v1), |
298 vpretty(v1), |
277 vpretty(v2), |
299 vpretty(v2), |
278 vpretty(v3), |
300 vpretty(v3), |
279 vpretty(v4)).mkString("\n") } |
301 vpretty(v4), s1, s2).mkString("\n") } |
280 |
302 |
281 // Lexing Rules for a Small While Language |
303 // Lexing Rules for a Small While Language |
282 |
304 |
283 def PLUS(r: Rexp) = r ~ r.% |
305 def PLUS(r: Rexp) = r ~ r.% |
284 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |
306 val SYM = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" |