1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
3 import scala.annotation.tailrec |
3 import scala.annotation.tailrec |
4 |
4 |
5 abstract class Rexp |
5 abstract class Rexp |
6 case object NULL extends Rexp |
6 case object ZERO extends Rexp |
7 case object EMPTY extends Rexp |
7 case object ONE extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
13 |
13 |
14 abstract class Val |
14 abstract class Val |
15 case object Void extends Val |
15 case object Empty extends Val |
16 case class Chr(c: Char) extends Val |
16 case class Chr(c: Char) extends Val |
17 case class Sequ(v1: Val, v2: Val) extends Val |
17 case class Sequ(v1: Val, v2: Val) extends Val |
18 case class Left(v: Val) extends Val |
18 case class Left(v: Val) extends Val |
19 case class Right(v: Val) extends Val |
19 case class Right(v: Val) extends Val |
20 case class Stars(vs: List[Val]) extends Val |
20 case class Stars(vs: List[Val]) extends Val |
21 case class Rec(x: String, v: Val) extends Val |
21 case class Rec(x: String, v: Val) extends Val |
22 |
22 |
23 // some convenience for typing in regular expressions |
23 // some convenience for typing in regular expressions |
24 def charlist2rexp(s : List[Char]): Rexp = s match { |
24 def charlist2rexp(s : List[Char]): Rexp = s match { |
25 case Nil => EMPTY |
25 case Nil => ONE |
26 case c::Nil => CHAR(c) |
26 case c::Nil => CHAR(c) |
27 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
27 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
28 } |
28 } |
29 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
29 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
30 |
30 |
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 { |
46 def pretty(r: Rexp) : String = r match { |
47 case NULL => "0" |
47 case ZERO => "0" |
48 case EMPTY => "e" |
48 case ONE => "e" |
49 case CHAR(c) => c.toString |
49 case CHAR(c) => c.toString |
50 case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")" |
50 case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")" |
51 case SEQ(r1, r2) => pretty(r1) ++ pretty(r2) |
51 case SEQ(r1, r2) => pretty(r1) ++ pretty(r2) |
52 case STAR(r) => "(" ++ pretty(r) ++ ")*" |
52 case STAR(r) => "(" ++ pretty(r) ++ ")*" |
53 case RECD(x, r) => "(" ++ x ++ " : " ++ pretty(r) ++ ")" |
53 case RECD(x, r) => "(" ++ x ++ " : " ++ pretty(r) ++ ")" |
54 } |
54 } |
55 |
55 |
56 def vpretty(v: Val) : String = v match { |
56 def vpretty(v: Val) : String = v match { |
57 case Void => "()" |
57 case Empty => "()" |
58 case Chr(c) => c.toString |
58 case Chr(c) => c.toString |
59 case Left(v) => "Left(" ++ vpretty(v) ++ ")" |
59 case Left(v) => "Left(" ++ vpretty(v) ++ ")" |
60 case Right(v) => "Right(" ++ vpretty(v) ++ ")" |
60 case Right(v) => "Right(" ++ vpretty(v) ++ ")" |
61 case Sequ(v1, v2) => vpretty(v1) ++ " ~ " ++ vpretty(v2) |
61 case Sequ(v1, v2) => vpretty(v1) ++ " ~ " ++ vpretty(v2) |
62 case Stars(vs) => vs.flatMap(vpretty).mkString("[", ",", "]") |
62 case Stars(vs) => vs.flatMap(vpretty).mkString("[", ",", "]") |
64 } |
64 } |
65 |
65 |
66 |
66 |
67 // size of a regular expressions - for testing purposes |
67 // size of a regular expressions - for testing purposes |
68 def size(r: Rexp) : Int = r match { |
68 def size(r: Rexp) : Int = r match { |
69 case NULL => 1 |
69 case ZERO => 1 |
70 case EMPTY => 1 |
70 case ONE => 1 |
71 case CHAR(_) => 1 |
71 case CHAR(_) => 1 |
72 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
72 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
73 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
73 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
74 case STAR(r) => 1 + size(r) |
74 case STAR(r) => 1 + size(r) |
75 case RECD(_, r) => 1 + size(r) |
75 case RECD(_, r) => 1 + size(r) |
76 } |
76 } |
77 |
77 |
78 // 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 |
79 def values(r: Rexp) : Set[Val] = r match { |
79 def values(r: Rexp) : Set[Val] = r match { |
80 case NULL => Set() |
80 case ZERO => Set() |
81 case EMPTY => Set(Void) |
81 case ONE => Set(Empty) |
82 case CHAR(c) => Set(Chr(c)) |
82 case CHAR(c) => Set(Chr(c)) |
83 case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ |
83 case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++ |
84 (for (v2 <- values(r2)) yield Right(v2)) |
84 (for (v2 <- values(r2)) yield Right(v2)) |
85 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) |
86 case STAR(r) => Set(Void) ++ values(r) // to do more would cause the set to be infinite |
86 case STAR(r) => Set(Empty) ++ values(r) // to do more would cause the set to be infinite |
87 case RECD(_, r) => values(r) |
87 case RECD(_, r) => values(r) |
88 } |
88 } |
89 |
89 |
90 // zeroable function: tests whether the regular |
90 // zeroable function: tests whether the regular |
91 // expression cannot regognise any string |
91 // expression cannot regognise any string |
92 def zeroable (r: Rexp) : Boolean = r match { |
92 def zeroable (r: Rexp) : Boolean = r match { |
93 case NULL => true |
93 case ZERO => true |
94 case EMPTY => false |
94 case ONE => false |
95 case CHAR(_) => false |
95 case CHAR(_) => false |
96 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
96 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
97 case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) |
97 case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) |
98 case STAR(_) => false |
98 case STAR(_) => false |
99 case RECD(_, r1) => zeroable(r1) |
99 case RECD(_, r1) => zeroable(r1) |
101 |
101 |
102 |
102 |
103 // nullable function: tests whether the regular |
103 // nullable function: tests whether the regular |
104 // expression can recognise the empty string |
104 // expression can recognise the empty string |
105 def nullable (r: Rexp) : Boolean = r match { |
105 def nullable (r: Rexp) : Boolean = r match { |
106 case NULL => false |
106 case ZERO => false |
107 case EMPTY => true |
107 case ONE => true |
108 case CHAR(_) => false |
108 case CHAR(_) => false |
109 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
109 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
110 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
110 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
111 case STAR(_) => true |
111 case STAR(_) => true |
112 case RECD(_, r1) => nullable(r1) |
112 case RECD(_, r1) => nullable(r1) |
113 } |
113 } |
114 |
114 |
115 // derivative of a regular expression w.r.t. a character |
115 // derivative of a regular expression w.r.t. a character |
116 def der (c: Char, r: Rexp) : Rexp = r match { |
116 def der (c: Char, r: Rexp) : Rexp = r match { |
117 case NULL => NULL |
117 case ZERO => ZERO |
118 case EMPTY => NULL |
118 case ONE => ZERO |
119 case CHAR(d) => if (c == d) EMPTY else NULL |
119 case CHAR(d) => if (c == d) ONE else ZERO |
120 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
120 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
121 case SEQ(r1, r2) => |
121 case SEQ(r1, r2) => |
122 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
122 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
123 else SEQ(der(c, r1), r2) |
123 else SEQ(der(c, r1), r2) |
124 case STAR(r) => SEQ(der(c, r), STAR(r)) |
124 case STAR(r) => SEQ(der(c, r), STAR(r)) |
131 case c::s => ders(s, der(c, r)) |
131 case c::s => ders(s, der(c, r)) |
132 } |
132 } |
133 |
133 |
134 // extracts a string from value |
134 // extracts a string from value |
135 def flatten(v: Val) : String = v match { |
135 def flatten(v: Val) : String = v match { |
136 case Void => "" |
136 case Empty => "" |
137 case Chr(c) => c.toString |
137 case Chr(c) => c.toString |
138 case Left(v) => flatten(v) |
138 case Left(v) => flatten(v) |
139 case Right(v) => flatten(v) |
139 case Right(v) => flatten(v) |
140 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
140 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
141 case Stars(vs) => vs.map(flatten).mkString |
141 case Stars(vs) => vs.map(flatten).mkString |
142 case Rec(_, v) => flatten(v) |
142 case Rec(_, v) => flatten(v) |
143 } |
143 } |
144 |
144 |
145 def flattens(v: Val) : List[String] = v match { |
145 def flattens(v: Val) : List[String] = v match { |
146 case Void => List("") |
146 case Empty => List("") |
147 case Chr(c) => List(c.toString) |
147 case Chr(c) => List(c.toString) |
148 case Left(v) => flattens(v) |
148 case Left(v) => flattens(v) |
149 case Right(v) => flattens(v) |
149 case Right(v) => flattens(v) |
150 case Sequ(v1, v2) => flattens(v1) ::: flattens(v2) |
150 case Sequ(v1, v2) => flattens(v1) ::: flattens(v2) |
151 case Stars(vs) => vs.flatMap(flattens) |
151 case Stars(vs) => vs.flatMap(flattens) |
153 } |
153 } |
154 |
154 |
155 |
155 |
156 // extracts an environment from a value |
156 // extracts an environment from a value |
157 def env(v: Val) : List[(String, String)] = v match { |
157 def env(v: Val) : List[(String, String)] = v match { |
158 case Void => Nil |
158 case Empty => Nil |
159 case Chr(c) => Nil |
159 case Chr(c) => Nil |
160 case Left(v) => env(v) |
160 case Left(v) => env(v) |
161 case Right(v) => env(v) |
161 case Right(v) => env(v) |
162 case Sequ(v1, v2) => env(v1) ::: env(v2) |
162 case Sequ(v1, v2) => env(v1) ::: env(v2) |
163 case Stars(vs) => vs.flatMap(env) |
163 case Stars(vs) => vs.flatMap(env) |
164 case Rec(x, v) => (x, flatten(v))::env(v) |
164 case Rec(x, v) => (x, flatten(v))::env(v) |
165 } |
165 } |
166 |
166 |
167 // injection part |
167 // injection part |
168 def mkeps(r: Rexp) : Val = r match { |
168 def mkeps(r: Rexp) : Val = r match { |
169 case EMPTY => Void |
169 case ONE => Empty |
170 case ALT(r1, r2) => |
170 case ALT(r1, r2) => |
171 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
171 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
172 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
172 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
173 case STAR(r) => Stars(Nil) |
173 case STAR(r) => Stars(Nil) |
174 case RECD(x, r) => Rec(x, mkeps(r)) |
174 case RECD(x, r) => Rec(x, mkeps(r)) |
180 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
180 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
181 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
181 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
182 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
182 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
183 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
183 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
184 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
184 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
185 case (CHAR(d), Void) => Chr(c) |
185 case (CHAR(d), Empty) => Chr(c) |
186 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
186 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
187 } |
187 } |
188 |
188 |
189 // main lexing function (produces a value) |
189 // main lexing function (produces a value) |
190 def lex(r: Rexp, s: List[Char]) : Val = s match { |
190 def lex(r: Rexp, s: List[Char]) : Val = s match { |
205 case Left(v) => Left(f1(v)) |
205 case Left(v) => Left(f1(v)) |
206 } |
206 } |
207 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
207 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
208 case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
208 case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
209 } |
209 } |
210 def F_SEQ_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v)) |
210 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Empty), f2(v)) |
211 def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void)) |
211 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Empty)) |
212 def F_RECD(f: Val => Val) = (v:Val) => v match { |
212 def F_RECD(f: Val => Val) = (v:Val) => v match { |
213 case Rec(x, v) => Rec(x, f(v)) |
213 case Rec(x, v) => Rec(x, f(v)) |
214 } |
214 } |
215 def F_ERROR(v: Val): Val = throw new Exception("error") |
215 def F_ERROR(v: Val): Val = throw new Exception("error") |
216 |
216 |
219 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
219 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
220 case ALT(r1, r2) => { |
220 case ALT(r1, r2) => { |
221 val (r1s, f1s) = simp(r1) |
221 val (r1s, f1s) = simp(r1) |
222 val (r2s, f2s) = simp(r2) |
222 val (r2s, f2s) = simp(r2) |
223 (r1s, r2s) match { |
223 (r1s, r2s) match { |
224 case (NULL, _) => (r2s, F_RIGHT(f2s)) |
224 case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
225 case (_, NULL) => (r1s, F_LEFT(f1s)) |
225 case (_, ZERO) => (r1s, F_LEFT(f1s)) |
226 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
226 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
227 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) |
227 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) |
228 } |
228 } |
229 } |
229 } |
230 case SEQ(r1, r2) => { |
230 case SEQ(r1, r2) => { |
231 val (r1s, f1s) = simp(r1) |
231 val (r1s, f1s) = simp(r1) |
232 val (r2s, f2s) = simp(r2) |
232 val (r2s, f2s) = simp(r2) |
233 (r1s, r2s) match { |
233 (r1s, r2s) match { |
234 case (NULL, _) => (NULL, F_ERROR) |
234 case (ZERO, _) => (ZERO, F_ERROR) |
235 case (_, NULL) => (NULL, F_ERROR) |
235 case (_, ZERO) => (ZERO, F_ERROR) |
236 case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s)) |
236 case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
237 case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s)) |
237 case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
238 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
238 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
239 } |
239 } |
240 } |
240 } |
241 case RECD(x, r1) => { |
241 case RECD(x, r1) => { |
242 val (r1s, f1s) = simp(r1) |
242 val (r1s, f1s) = simp(r1) |
258 lexing_sim(("a" + "ab") | ("b" + ""), "ab") |
258 lexing_sim(("a" + "ab") | ("b" + ""), "ab") |
259 // brute force search infrastructure |
259 // brute force search infrastructure |
260 |
260 |
261 // enumerates regular expressions until a certain depth |
261 // enumerates regular expressions until a certain depth |
262 def enum(n: Int, s: String) : Set[Rexp] = n match { |
262 def enum(n: Int, s: String) : Set[Rexp] = n match { |
263 case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR) |
263 case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR) |
264 case n => { |
264 case n => { |
265 val rs = enum(n - 1, s) |
265 val rs = enum(n - 1, s) |
266 rs ++ |
266 rs ++ |
267 (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++ |
267 (for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) ++ |
268 (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) |
268 (for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) |
269 } |
269 } |
270 } |
270 } |
271 |
271 |
272 def ordr(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match { |
272 def ordr(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match { |
273 case (Void, EMPTY, Void) => true |
273 case (Empty, ONE, Empty) => true |
274 case (Chr(c1), CHAR(c2), Chr(c3)) if (c1 == c2 && c1 == c3) => true |
274 case (Chr(c1), CHAR(c2), Chr(c3)) if (c1 == c2 && c1 == c3) => true |
275 case (Left(v1), ALT(r1, r2), Left(v2)) => ordr(v1, r1, v2) |
275 case (Left(v1), ALT(r1, r2), Left(v2)) => ordr(v1, r1, v2) |
276 case (Right(v1), ALT(r1, r2), Right(v2)) => ordr(v1, r2, v2) |
276 case (Right(v1), ALT(r1, r2), Right(v2)) => ordr(v1, r2, v2) |
277 case (Left(v1), ALT(r1, r2), Right(v2)) => flatten(v2).length <= flatten(v1).length |
277 case (Left(v1), ALT(r1, r2), Right(v2)) => flatten(v2).length <= flatten(v1).length |
278 case (Right(v1), ALT(r1, r2), Left(v2)) => flatten(v2).length < flatten(v1).length |
278 case (Right(v1), ALT(r1, r2), Left(v2)) => flatten(v2).length < flatten(v1).length |
280 case (Sequ(v1, v2), SEQ(r1, r2), Sequ(v3, v4)) if (v1 != v3) => ordr(v1, r1, v3) |
280 case (Sequ(v1, v2), SEQ(r1, r2), Sequ(v3, v4)) if (v1 != v3) => ordr(v1, r1, v3) |
281 case _ => false |
281 case _ => false |
282 } |
282 } |
283 |
283 |
284 def ord(v1: Val, v2: Val) : Boolean = (v1, v2) match { |
284 def ord(v1: Val, v2: Val) : Boolean = (v1, v2) match { |
285 case (Void, Void) => true |
285 case (Empty, Empty) => true |
286 case (Chr(c1), Chr(c2)) if (c1 == c2) => true |
286 case (Chr(c1), Chr(c2)) if (c1 == c2) => true |
287 case (Left(v1), Left(v2)) => ord(v1, v2) |
287 case (Left(v1), Left(v2)) => ord(v1, v2) |
288 case (Right(v1), Right(v2)) => ord(v1, v2) |
288 case (Right(v1), Right(v2)) => ord(v1, v2) |
289 case (Left(v1), Right(v2)) => flatten(v2).length <= flatten(v1).length |
289 case (Left(v1), Right(v2)) => flatten(v2).length <= flatten(v1).length |
290 case (Right(v1), Left(v2)) => flatten(v2).length < flatten(v1).length |
290 case (Right(v1), Left(v2)) => flatten(v2).length < flatten(v1).length |
557 print(i.toString + ": ") |
557 print(i.toString + ": ") |
558 time(lexing_simp(WHILE_REGS, prog2 * i)) |
558 time(lexing_simp(WHILE_REGS, prog2 * i)) |
559 } |
559 } |
560 |
560 |
561 |
561 |
562 val a0 = (EMPTY | "a") ~ (EMPTY | "ab") |
562 val a0 = (ONE | "a") ~ (ONE | "ab") |
563 val a1 = der('a', a0) |
563 val a1 = der('a', a0) |
564 pretty(a1) |
564 pretty(a1) |
565 val m = mkeps(a1) |
565 val m = mkeps(a1) |
566 vpretty(m) |
566 vpretty(m) |
567 val v = inj(a0, 'a', m) |
567 val v = inj(a0, 'a', m) |
568 vpretty(v) |
568 vpretty(v) |
569 |
569 |
570 val a0 = (EMPTY | "a") ~ (EMPTY | "ab") |
570 val a0 = (ONE | "a") ~ (ONE | "ab") |
571 val a1 = der('a', a0) |
571 val a1 = der('a', a0) |
572 pretty(a1) |
572 pretty(a1) |
573 values(a1).toList |
573 values(a1).toList |
574 val List(u2,_,u1) = values(a1).toList |
574 val List(u2,_,u1) = values(a1).toList |
575 vpretty(u1) |
575 vpretty(u1) |