| author | Chengsong |
| Tue, 03 Mar 2020 21:56:09 +0000 | |
| changeset 144 | bc340e8f4165 |
| parent 109 | 79f347cb8b4d |
| child 148 | c8ef391dd6f7 |
| permissions | -rw-r--r-- |
| 0 | 1 |
package RexpRelated |
2 |
import scala.language.implicitConversions |
|
3 |
import scala.language.reflectiveCalls |
|
4 |
import scala.annotation.tailrec |
|
5 |
import scala.util.Try |
|
6 |
||
7 |
abstract class Bit |
|
8 |
case object Z extends Bit |
|
9 |
case object S extends Bit |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
10 |
//case class C(c: Char) extends Bit |
| 0 | 11 |
|
12 |
||
13 |
abstract class Rexp |
|
14 |
case object ZERO extends Rexp |
|
15 |
case object ONE extends Rexp |
|
16 |
case class CHAR(c: Char) extends Rexp |
|
17 |
case class ALTS(rs: List[Rexp]) extends Rexp |
|
18 |
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
19 |
case class STAR(r: Rexp) extends Rexp |
|
20 |
case class RECD(x: String, r: Rexp) extends Rexp |
|
21 |
||
22 |
||
23 |
||
24 |
object Rexp{
|
|
25 |
type Bits = List[Bit] |
|
26 |
// abbreviations |
|
27 |
type Mon = (Char, Rexp) |
|
28 |
type Lin = Set[Mon] |
|
29 |
def ALT(r1: Rexp, r2: Rexp) = ALTS(List(r1, r2)) |
|
30 |
def PLUS(r: Rexp) = SEQ(r, STAR(r)) |
|
31 |
def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2)) |
|
32 |
||
33 |
||
34 |
def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
|
|
35 |
case Nil => Nil |
|
36 |
case (x::xs) => {
|
|
37 |
val res = f(x) |
|
38 |
if (acc.contains(res)) distinctBy(xs, f, acc) |
|
39 |
else x::distinctBy(xs, f, res::acc) |
|
40 |
} |
|
41 |
} |
|
42 |
// some convenience for typing in regular expressions |
|
43 |
def charlist2rexp(s : List[Char]): Rexp = s match {
|
|
44 |
case Nil => ONE |
|
45 |
case c::Nil => CHAR(c) |
|
46 |
case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
47 |
} |
|
48 |
implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
49 |
||
50 |
implicit def RexpOps(r: Rexp) = new {
|
|
51 |
def | (s: Rexp) = ALT(r, s) |
|
52 |
def % = STAR(r) |
|
53 |
def ~ (s: Rexp) = SEQ(r, s) |
|
54 |
} |
|
55 |
||
56 |
implicit def stringOps(s: String) = new {
|
|
57 |
def | (r: Rexp) = ALT(s, r) |
|
58 |
def | (r: String) = ALT(s, r) |
|
59 |
def % = STAR(s) |
|
60 |
def ~ (r: Rexp) = SEQ(s, r) |
|
61 |
def ~ (r: String) = SEQ(s, r) |
|
62 |
def $ (r: Rexp) = RECD(s, r) |
|
63 |
} |
|
64 |
||
65 |
// translation into ARexps |
|
66 |
def fuse(bs: Bits, r: ARexp) : ARexp = r match {
|
|
67 |
case AZERO => AZERO |
|
68 |
case AONE(cs) => AONE(bs ++ cs) |
|
69 |
case ACHAR(cs, f) => ACHAR(bs ++ cs, f) |
|
70 |
case AALTS(cs, rs) => AALTS(bs ++ cs, rs) |
|
71 |
case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2) |
|
72 |
case ASTAR(cs, r) => ASTAR(bs ++ cs, r) |
|
73 |
} |
|
74 |
||
75 |
def internalise(r: Rexp) : ARexp = r match {
|
|
76 |
case ZERO => AZERO |
|
77 |
case ONE => AONE(Nil) |
|
78 |
case CHAR(c) => ACHAR(Nil, c) |
|
79 |
case ALTS(List(r1, r2)) => |
|
80 |
AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2)))) |
|
81 |
case ALTS(r1::rs) => {
|
|
82 |
val AALTS(Nil, rs2) = internalise(ALTS(rs)) |
|
83 |
AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _))) |
|
84 |
} |
|
85 |
case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2)) |
|
86 |
case STAR(r) => ASTAR(Nil, internalise(r)) |
|
87 |
case RECD(x, r) => internalise(r) |
|
88 |
} |
|
89 |
||
90 |
internalise(("a" | "ab") ~ ("b" | ""))
|
|
| 5 | 91 |
|
| 0 | 92 |
def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
|
93 |
case (ONE, bs) => (Empty, bs) |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
94 |
case (CHAR(f), bs) => (Chr(f), bs) |
|
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
95 |
case (ALTS(r::Nil), bs) => decode_aux(r, bs)//this case seems only used when we simp a regex before derivatives and it contains things like alt("a")
|
| 0 | 96 |
case (ALTS(rs), bs) => bs match {
|
97 |
case Z::bs1 => {
|
|
98 |
val (v, bs2) = decode_aux(rs.head, bs1) |
|
99 |
(Left(v), bs2) |
|
100 |
} |
|
101 |
case S::bs1 => {
|
|
102 |
val (v, bs2) = decode_aux(ALTS(rs.tail), bs1) |
|
103 |
(Right(v), bs2) |
|
104 |
} |
|
105 |
} |
|
106 |
case (SEQ(r1, r2), bs) => {
|
|
107 |
val (v1, bs1) = decode_aux(r1, bs) |
|
108 |
val (v2, bs2) = decode_aux(r2, bs1) |
|
109 |
(Sequ(v1, v2), bs2) |
|
110 |
} |
|
111 |
case (STAR(r1), S::bs) => {
|
|
112 |
val (v, bs1) = decode_aux(r1, bs) |
|
113 |
//println(v) |
|
114 |
val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
|
115 |
(Stars(v::vs), bs2) |
|
116 |
} |
|
117 |
case (STAR(_), Z::bs) => (Stars(Nil), bs) |
|
118 |
case (RECD(x, r1), bs) => {
|
|
119 |
val (v, bs1) = decode_aux(r1, bs) |
|
120 |
(Rec(x, v), bs1) |
|
121 |
} |
|
| 109 | 122 |
case (r, Nil) => (Stars(Nil), Nil) |
| 0 | 123 |
} |
124 |
||
125 |
def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
|
|
126 |
case (v, Nil) => v |
|
127 |
case _ => throw new Exception("Not decodable")
|
|
128 |
} |
|
| 5 | 129 |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
130 |
def code(v: Val): Bits = v match {
|
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
131 |
case Empty => Nil |
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
132 |
case Chr(a) => Nil |
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
133 |
case Left(v) => Z :: code(v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
134 |
case Right(v) => S :: code(v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
135 |
case Sequ(v1, v2) => code(v1) ::: code(v2) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
136 |
case Stars(Nil) => Z::Nil |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
137 |
case Stars(v::vs) => S::code(v) ::: code(Stars(vs)) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
138 |
} |
| 0 | 139 |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
140 |
|
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
141 |
def retrieve(r: ARexp, v: Val): Bits = (r,v) match {
|
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
142 |
case (AONE(bs), Empty) => bs |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
143 |
case (ACHAR(bs, c), Chr(d)) => bs |
| 14 | 144 |
case (AALTS(bs, a::Nil), v) => bs ++ retrieve(a, v) |
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
145 |
case (AALTS(bs, as), Left(v)) => bs ++ retrieve(as.head,v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
146 |
case (AALTS(bs, as), Right(v)) => bs ++ retrieve(AALTS(Nil,as.tail),v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
147 |
case (ASEQ(bs, a1, a2), Sequ(v1, v2)) => bs ++ retrieve(a1, v1) ++ retrieve(a2, v2) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
148 |
case (ASTAR(bs, a), Stars(Nil)) => bs ++ List(Z) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
149 |
case (ASTAR(bs, a), Stars(v::vs)) => bs ++ List(S) ++ retrieve(a, v) ++ retrieve(ASTAR(Nil, a), Stars(vs)) |
| 59 | 150 |
}//bug here last clause should not add list(S) |
| 0 | 151 |
//erase function: extracts the regx from Aregex |
152 |
def erase(r:ARexp): Rexp = r match{
|
|
153 |
case AZERO => ZERO |
|
154 |
case AONE(_) => ONE |
|
155 |
case ACHAR(bs, f) => CHAR(f) |
|
156 |
case AALTS(bs, rs) => ALTS(rs.map(erase(_))) |
|
157 |
case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2)) |
|
158 |
case ASTAR(cs, r)=> STAR(erase(r)) |
|
159 |
} |
|
160 |
||
161 |
//--------------------------------------------------------------------------------------------------------START OF NON-BITCODE PART |
|
162 |
// nullable function: tests whether the regular |
|
163 |
// expression can recognise the empty string |
|
164 |
def nullable (r: Rexp) : Boolean = r match {
|
|
165 |
case ZERO => false |
|
166 |
case ONE => true |
|
167 |
case CHAR(_) => false |
|
168 |
case ALTS(rs) => rs.exists(nullable) |
|
169 |
case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
170 |
case STAR(_) => true |
|
171 |
case RECD(_, r) => nullable(r) |
|
172 |
//case PLUS(r) => nullable(r) |
|
173 |
} |
|
174 |
||
175 |
// derivative of a regular expression w.r.t. a character |
|
176 |
def der (c: Char, r: Rexp) : Rexp = r match {
|
|
177 |
case ZERO => ZERO |
|
178 |
case ONE => ZERO |
|
179 |
case CHAR(f) => if (c == f) ONE else ZERO |
|
180 |
case ALTS(List(r1, r2)) => ALTS(List(der(c, r1), der(c, r2))) |
|
181 |
case SEQ(r1, r2) => |
|
182 |
if (nullable(r1)) ALTS(List(SEQ(der(c, r1), r2), der(c, r2))) |
|
183 |
else SEQ(der(c, r1), r2) |
|
184 |
case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
185 |
case RECD(_, r1) => der(c, r1) |
|
186 |
//case PLUS(r) => SEQ(der(c, r), STAR(r)) |
|
187 |
} |
|
188 |
||
| 92 | 189 |
def ders (s: List[Char], r: Rexp) : Rexp = s match {
|
190 |
case Nil => r |
|
191 |
case c::s => ders(s, der(c, r)) |
|
192 |
} |
|
193 |
||
194 |
def der_seqo(r:Rexp, s: List[Char],acc: List[Rexp]) : List[Rexp] = s match{
|
|
195 |
case Nil => acc ::: List(r) |
|
196 |
case c::cs => der_seqo(der(c, r), cs, acc ::: List(r)) |
|
197 |
} |
|
198 |
def der_seq_revo(r:Rexp, s: List[Char], acc: List[Rexp]): List[Rexp] = s match{
|
|
199 |
case Nil => r::acc |
|
200 |
case c::cs =>der_seq_revo(r, cs, ders(s, r) :: acc ) |
|
201 |
} |
|
202 |
def re_closeo(l1: List[Rexp], l2: List[Rexp], re_init: Rexp): Rexp = l1 match {
|
|
203 |
case Nil => re_init |
|
204 |
case c::cs => if(nullable(c)) re_closeo(cs, l2.tail, ALT(re_init, l2.head) ) |
|
205 |
else re_closeo(cs, l2.tail, re_init) |
|
206 |
} |
|
| 93 | 207 |
|
| 92 | 208 |
//HERE |
209 |
def closed_string_dero(r1: Rexp, r2: Rexp, s: List[Char]): Rexp = {
|
|
210 |
val l1 = der_seqo(r1, s, Nil) |
|
211 |
val l2 = der_seq_revo(r2, s, Nil) |
|
212 |
val Re = re_closeo((l1.reverse).tail, l2.tail, SEQ(l1.last, l2.head)) |
|
213 |
Re |
|
214 |
} |
|
215 |
//derivative w.r.t string |
|
216 |
def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match {
|
|
217 |
case (Nil, r) => r |
|
218 |
case (s, ZERO) => ZERO |
|
219 |
case (s, ONE) => if (s == Nil) ONE else ZERO |
|
220 |
case (s, CHAR(c)) => if (s == List(c)) ONE else |
|
221 |
if (s == Nil) CHAR(c) else ZERO |
|
222 |
case (s, ALTS(List(r1, r2))) => ALT(ders2(s, r1), ders2(s, r2)) |
|
223 |
case (s, SEQ(r1, r2)) => closed_string_dero(r1, r2, s) |
|
224 |
case (c::cs, STAR(r)) => closed_string_dero(der(c, r), STAR(r), cs) |
|
225 |
} |
|
226 |
||
| 0 | 227 |
def flatten(v: Val) : String = v match {
|
228 |
case Empty => "" |
|
229 |
case Chr(c) => c.toString |
|
230 |
case Left(v) => flatten(v) |
|
231 |
case Right(v) => flatten(v) |
|
232 |
case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
|
233 |
case Stars(vs) => vs.map(flatten).mkString |
|
234 |
case Rec(_, v) => flatten(v) |
|
235 |
} |
|
236 |
||
237 |
// extracts an environment from a value |
|
238 |
def env(v: Val) : List[(String, String)] = v match {
|
|
239 |
case Empty => Nil |
|
240 |
case Chr(c) => Nil |
|
241 |
case Left(v) => env(v) |
|
242 |
case Right(v) => env(v) |
|
243 |
case Sequ(v1, v2) => env(v1) ::: env(v2) |
|
244 |
case Stars(vs) => vs.flatMap(env) |
|
245 |
case Rec(x, v) => (x, flatten(v))::env(v) |
|
246 |
} |
|
247 |
||
248 |
||
249 |
// injection part |
|
250 |
def mkeps(r: Rexp) : Val = r match {
|
|
251 |
case ONE => Empty |
|
252 |
case ALTS(List(r1, r2)) => |
|
253 |
if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
|
254 |
case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
|
255 |
case STAR(r) => Stars(Nil) |
|
256 |
case RECD(x, r) => Rec(x, mkeps(r)) |
|
257 |
//case PLUS(r) => Stars(List(mkeps(r))) |
|
258 |
} |
|
259 |
||
260 |
def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
|
|
261 |
case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
262 |
case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
|
263 |
case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
|
264 |
case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
|
265 |
case (ALTS(List(r1, r2)), Left(v1)) => Left(inj(r1, c, v1)) |
|
266 |
case (ALTS(List(r1, r2)), Right(v2)) => Right(inj(r2, c, v2)) |
|
267 |
case (CHAR(_), Empty) => Chr(c) |
|
268 |
case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
|
269 |
//case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
270 |
} |
|
271 |
def lex(r: Rexp, s: List[Char]) : Val = s match {
|
|
272 |
case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
|
|
273 |
case c::cs => inj(r, c, lex(der(c, r), cs)) |
|
274 |
} |
|
275 |
||
276 |
def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
|
277 |
||
278 |
// some "rectification" functions for simplification |
|
279 |
def F_ID(v: Val): Val = v |
|
280 |
def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
|
281 |
def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
|
282 |
def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
|
|
283 |
case Right(v) => Right(f2(v)) |
|
284 |
case Left(v) => Left(f1(v)) |
|
285 |
} |
|
286 |
def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
|
|
287 |
case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
|
288 |
} |
|
289 |
def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
|
290 |
(v:Val) => Sequ(f1(Empty), f2(v)) |
|
291 |
def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
|
292 |
(v:Val) => Sequ(f1(v), f2(Empty)) |
|
293 |
def F_RECD(f: Val => Val) = (v:Val) => v match {
|
|
294 |
case Rec(x, v) => Rec(x, f(v)) |
|
295 |
} |
|
296 |
def F_ERROR(v: Val): Val = throw new Exception("error")
|
|
297 |
||
298 |
// simplification of regular expressions returning also an |
|
299 |
// rectification function; no simplification under STAR |
|
300 |
def simp(r: Rexp): (Rexp, Val => Val) = r match {
|
|
301 |
case ALTS(List(r1, r2)) => {
|
|
302 |
val (r1s, f1s) = simp(r1) |
|
303 |
val (r2s, f2s) = simp(r2) |
|
304 |
(r1s, r2s) match {
|
|
305 |
case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
|
306 |
case (_, ZERO) => (r1s, F_LEFT(f1s)) |
|
307 |
case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
|
308 |
else (ALTS(List(r1s, r2s)), F_ALT(f1s, f2s)) |
|
309 |
} |
|
310 |
} |
|
311 |
case SEQ(r1, r2) => {
|
|
312 |
val (r1s, f1s) = simp(r1) |
|
313 |
val (r2s, f2s) = simp(r2) |
|
314 |
(r1s, r2s) match {
|
|
315 |
case (ZERO, _) => (ZERO, F_ERROR) |
|
316 |
case (_, ZERO) => (ZERO, F_ERROR) |
|
317 |
case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
|
318 |
case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
|
319 |
case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
|
320 |
} |
|
321 |
} |
|
322 |
case RECD(x, r1) => {
|
|
323 |
val (r1s, f1s) = simp(r1) |
|
324 |
(RECD(x, r1s), F_RECD(f1s)) |
|
325 |
} |
|
326 |
case r => (r, F_ID) |
|
327 |
} |
|
328 |
/* |
|
329 |
val each_simp_time = scala.collection.mutable.ArrayBuffer.empty[Long] |
|
330 |
val each_simp_timeb = scala.collection.mutable.ArrayBuffer.empty[Long] |
|
331 |
*/ |
|
332 |
def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
|
|
333 |
case Nil => {
|
|
334 |
if (nullable(r)) {
|
|
335 |
mkeps(r) |
|
336 |
} |
|
337 |
else throw new Exception("Not matched")
|
|
338 |
} |
|
339 |
case c::cs => {
|
|
340 |
val (r_simp, f_simp) = simp(der(c, r)) |
|
341 |
inj(r, c, f_simp(lex_simp(r_simp, cs))) |
|
342 |
} |
|
343 |
} |
|
344 |
||
345 |
def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
|
346 |
||
347 |
//println(lexing_simp(("a" | "ab") ~ ("b" | ""), "ab"))
|
|
348 |
||
349 |
// filters out all white spaces |
|
350 |
def tokenise(r: Rexp, s: String) = |
|
351 |
env(lexing_simp(r, s)).filterNot { _._1 == "w"}
|
|
352 |
||
353 |
||
354 |
//reads the string from a file |
|
355 |
def fromFile(name: String) : String = |
|
356 |
io.Source.fromFile(name).mkString |
|
357 |
||
358 |
def tokenise_file(r: Rexp, name: String) = |
|
359 |
tokenise(r, fromFile(name)) |
|
360 |
||
361 |
// Testing |
|
362 |
//============ |
|
363 |
||
364 |
def time[T](code: => T) = {
|
|
365 |
val start = System.nanoTime() |
|
366 |
val result = code |
|
367 |
val end = System.nanoTime() |
|
368 |
println((end - start)/1.0e9) |
|
369 |
result |
|
370 |
} |
|
371 |
||
372 |
//--------------------------------------------------------------------------------------------------------END OF NON-BITCODE PART |
|
373 |
||
374 |
// bnullable function: tests whether the aregular |
|
375 |
// expression can recognise the empty string |
|
376 |
def bnullable (r: ARexp) : Boolean = r match {
|
|
377 |
case AZERO => false |
|
378 |
case AONE(_) => true |
|
379 |
case ACHAR(_,_) => false |
|
380 |
case AALTS(_, rs) => rs.exists(bnullable) |
|
381 |
case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2) |
|
382 |
case ASTAR(_, _) => true |
|
383 |
} |
|
384 |
||
385 |
def mkepsBC(r: ARexp) : Bits = r match {
|
|
386 |
case AONE(bs) => bs |
|
387 |
case AALTS(bs, rs) => {
|
|
388 |
val n = rs.indexWhere(bnullable) |
|
389 |
bs ++ mkepsBC(rs(n)) |
|
390 |
} |
|
391 |
case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2) |
|
392 |
case ASTAR(bs, r) => bs ++ List(Z) |
|
393 |
} |
|
394 |
||
395 |
// derivative of a regular expression w.r.t. a character |
|
396 |
def bder(c: Char, r: ARexp) : ARexp = r match {
|
|
397 |
case AZERO => AZERO |
|
398 |
case AONE(_) => AZERO |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
399 |
case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
| 0 | 400 |
case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
401 |
case ASEQ(bs, r1, r2) => |
|
402 |
if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
|
403 |
else ASEQ(bs, bder(c, r1), r2) |
|
404 |
case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
|
405 |
} |
|
| 107 | 406 |
def bder_rf(c: Char, r: ARexp) : ARexp = r match {
|
407 |
case AZERO => AZERO |
|
408 |
case AONE(_) => AZERO |
|
409 |
case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
|
410 |
case AALTS(bs, rs) => AALTS(bs, rs.map(bder_rf(c, _))) |
|
411 |
case ASEQ(bs, r1, r2) => |
|
412 |
if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder_rf(c, r1), r2), fuse(mkepsBC(r1), bder_rf(c, r2))) |
|
413 |
else ASEQ(bs, bder_rf(c, r1), r2) |
|
414 |
case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder_rf(c, r)), ASTAR(Nil, r)) |
|
415 |
} |
|
| 0 | 416 |
// derivative w.r.t. a string (iterates bder) |
417 |
@tailrec |
|
418 |
def bders (s: List[Char], r: ARexp) : ARexp = s match {
|
|
419 |
case Nil => r |
|
420 |
case c::s => bders(s, bder(c, r)) |
|
421 |
} |
|
| 107 | 422 |
|
423 |
def bders_rf(s: List[Char], r: ARexp) : ARexp = s match {
|
|
424 |
case Nil => r |
|
425 |
case c::s => bders_rf(s, bder_rf(c, r)) |
|
426 |
} |
|
427 |
def all_zero_except_alt(rs: List[ARexp], a: ARexp): ARexp = rs match{
|
|
428 |
case Nil => a |
|
429 |
case AZERO :: rs1 => all_zero_except_alt(rs1, a) |
|
430 |
case AALTS(bs, rs1) :: rs2 => {
|
|
431 |
if (a == AZERO) |
|
432 |
all_zero_except_alt(rs2, AALTS(bs, rs1)) |
|
433 |
else |
|
434 |
AZERO |
|
435 |
} |
|
436 |
case r1 :: rs2 => AZERO |
|
437 |
} |
|
| 0 | 438 |
def flats(rs: List[ARexp]): List[ARexp] = rs match {
|
439 |
case Nil => Nil |
|
440 |
case AZERO :: rs1 => flats(rs1) |
|
441 |
case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
442 |
case r1 :: rs2 => r1 :: flats(rs2) |
|
| 15 | 443 |
} |
| 17 | 444 |
/* |
| 15 | 445 |
def remove(v: Val): Val = v match{
|
446 |
case Right(v1) => v1 |
|
447 |
case Left(v1) => v1 |
|
448 |
case _ => throw new Exception("Not removable")
|
|
| 17 | 449 |
}*/ |
| 15 | 450 |
def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v) |
451 |
//an overly complex version |
|
452 |
/* |
|
453 |
if(rel_dist >0){//the regex we are dealing with is not what v points at
|
|
454 |
rs match{
|
|
455 |
case Nil => throw new Exception("Trying to simplify a non-existent value")
|
|
456 |
case AZERO :: rs1 => flats_vsimp(rs1, rel_dist - 1, remove(v)) |
|
457 |
case AALTS(bs, rs1) :: rs2 => flats_vsimp(rs2, rel_dist - 1, augment(v, rs1.length - 1))//rs1 is guaranteed to have a len geq 2 |
|
458 |
case r1 :: rs2 => flats_vsimp(rs2, rel_dist - 1, v) |
|
459 |
} |
|
| 0 | 460 |
} |
| 15 | 461 |
else if(rel_dist == 0){//we are dealing with regex v is pointing to -- "v->r itself"
|
462 |
rs match{//r1 cannot be zero
|
|
463 |
AALTS(bs, rs1) :: rs2 => flats_vsimp( ) |
|
464 |
AZERO::rs2 => throw new Exception("Value corresponds to zero")
|
|
465 |
r1::rs2 => flats_vsimp(rs2, rel_dist - 1, v) |
|
466 |
} |
|
467 |
||
468 |
} |
|
469 |
else{
|
|
470 |
||
471 |
} |
|
472 |
*/ |
|
473 |
def flats_vsimp(rs: List[ARexp], position: Int): Int = (rs, position) match {
|
|
474 |
case (_, 0) => 0 |
|
475 |
case (Nil, _) => 0 |
|
| 16 | 476 |
case (AZERO :: rs1, _) => flats_vsimp(rs1, position - 1) - 1 |
| 15 | 477 |
case (AALTS(bs, rs1) :: rs2, _) => rs1.length - 1 + flats_vsimp(rs2, position - 1) |
478 |
case (r1 :: rs2, _) => flats_vsimp(rs2, position - 1) |
|
479 |
} |
|
| 0 | 480 |
def rflats(rs: List[Rexp]): List[Rexp] = rs match {
|
481 |
case Nil => Nil |
|
482 |
case ZERO :: rs1 => rflats(rs1) |
|
483 |
case ALTS(rs1) :: rs2 => rs1 ::: rflats(rs2) |
|
484 |
case r1 :: rs2 => r1 :: rflats(rs2) |
|
485 |
} |
|
486 |
var flats_time = 0L |
|
487 |
var dist_time = 0L |
|
488 |
||
489 |
def bsimp(r: ARexp): ARexp = r match {
|
|
490 |
case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {
|
|
491 |
case (AZERO, _) => AZERO |
|
492 |
case (_, AZERO) => AZERO |
|
493 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
494 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
495 |
} |
|
496 |
case AALTS(bs1, rs) => {
|
|
497 |
val rs_simp = rs.map(bsimp) |
|
498 |
val flat_res = flats(rs_simp) |
|
499 |
val dist_res = distinctBy(flat_res, erase) |
|
500 |
dist_res match {
|
|
501 |
case Nil => AZERO |
|
| 93 | 502 |
case r :: Nil => fuse(bs1, r) |
| 0 | 503 |
case rs => AALTS(bs1, rs) |
504 |
} |
|
505 |
} |
|
| 5 | 506 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
| 0 | 507 |
case r => r |
508 |
} |
|
| 107 | 509 |
//minimise fuse operation if possible |
510 |
def bsimp_rf(r: ARexp):ARexp = r match {
|
|
511 |
case ASEQ(bs1, r1, r2) => (bsimp_rf(r1), bsimp_rf(r2)) match {
|
|
512 |
case (AZERO, _) => AZERO |
|
513 |
case (_, AZERO) => AZERO |
|
514 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
515 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
516 |
} |
|
517 |
case AALTS(bs1, rs) => {
|
|
518 |
//after map simp, before flats, check if all others simplify to 0s, if yes, do not fuse |
|
519 |
val rs_simp = rs.map(bsimp_rf) |
|
520 |
//prevent fuse from happening |
|
521 |
val fuse_alts = all_zero_except_alt(rs_simp, AZERO)//returns AZERO if not the case, return AALTS if yes |
|
522 |
if(fuse_alts == AZERO){
|
|
523 |
val flat_res = flats(rs_simp) |
|
524 |
val dist_res = distinctBy(flat_res, erase) |
|
525 |
dist_res match {
|
|
526 |
case Nil => AZERO |
|
527 |
case r :: Nil => fuse(bs1, r) |
|
528 |
case rs => AALTS(bs1, rs) |
|
529 |
} |
|
530 |
} |
|
531 |
else{
|
|
532 |
fuse(bs1, fuse_alts) |
|
533 |
} |
|
534 |
} |
|
535 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
536 |
case r => r |
|
537 |
} |
|
| 93 | 538 |
//only print at the top level |
539 |
||
| 17 | 540 |
def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{
|
541 |
case (v, r::Nil) => 0 |
|
| 15 | 542 |
case (Right(v), r::rs) => find_pos(v, rs) + 1 |
| 17 | 543 |
case (Left(v), r::rs) => 0 |
544 |
//case (v, _) => 0 |
|
545 |
} |
|
546 |
def find_pos_aux(v: Val, r: ARexp): Int = r match {
|
|
547 |
case AALTS(bs, rs) => find_pos(v, rs) |
|
548 |
case r => 0 |
|
| 15 | 549 |
} |
| 17 | 550 |
def remove(v: Val, rs: List[ARexp]) : Val = (v,rs) match {//remove the outmost layer of ALTS's Left and Right
|
551 |
//we have to use r to detect the bound of nested L/Rs |
|
552 |
case (v, r::Nil) => v |
|
553 |
case (Right(v), r::rs) => remove(v, rs) |
|
| 15 | 554 |
case (Left(v), r::rs) => v |
| 17 | 555 |
//case (v, r::Nil) => v |
| 15 | 556 |
} |
| 16 | 557 |
def simple_end(v: Val): Boolean = v match {
|
| 15 | 558 |
case Left(v) => return false |
559 |
case Right(v) => return simple_end(v) |
|
560 |
case v => return true |
|
561 |
} |
|
| 17 | 562 |
def isend(v: Val, rs: List[ARexp], position: Int): Boolean = {//TODO: here the slice api i am not familiar with so this call might be incorrect and crash the bsimp2
|
563 |
val rsbh = rs.slice(position + 1, rs.length) |
|
| 15 | 564 |
val out_end = if(flats(rsbh) == Nil) true else false |
565 |
val inner_end = simple_end(v) |
|
566 |
inner_end && out_end |
|
567 |
} |
|
| 16 | 568 |
def get_coat(v: Val, rs: List[Rexp], vs: Val): Val = (v, rs) match{//the dual operation of remove(so-called by myself)
|
| 15 | 569 |
case (Right(v), r::Nil) => Right(vs) |
570 |
case (Left(v), r::rs) => Left(vs) |
|
571 |
case (Right(v), r::rs) => Right(get_coat(v, rs, vs)) |
|
572 |
} |
|
573 |
def coat(v: Val, i: Int) : Val = i match {
|
|
574 |
case 0 => v |
|
575 |
case i => coat(Right(v), i - 1) |
|
576 |
} |
|
| 17 | 577 |
//This version takes a regex and a value, return a simplified regex and its corresponding simplified value |
578 |
def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r,v) match{
|
|
579 |
case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
|
|
580 |
case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
581 |
case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
582 |
case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx. |
|
583 |
case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s)) |
|
584 |
} |
|
585 |
case (AALTS(bs1, rs), v) => {
|
|
586 |
//phase 1 transformation so that aalts(bs1, rs) => aalts(bs1, rsf) and v => vf |
|
587 |
val init_ind = find_pos(v, rs) |
|
588 |
val vs = bsimp2(rs(init_ind), remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
|
589 |
//println(vs) |
|
590 |
val rs_simp = rs.map(bsimp) |
|
591 |
val vs_kernel = rs_simp(init_ind) match {
|
|
592 |
case AALTS(bs2, rs2) => remove(vs._2, rs2)//remove the secondary layer of left and right |
|
593 |
case r => vs._2 |
|
594 |
} |
|
595 |
val flat_res = flats(rs_simp) |
|
596 |
val vs_for_coating = if(isend(vs._2, rs_simp, init_ind)||flat_res.length == 1) vs_kernel else Left(vs_kernel) |
|
597 |
val r_s = rs_simp(init_ind)//or vs._1 |
|
598 |
val shift = flats_vsimp(rs_simp, init_ind) + find_pos_aux(vs._2, rs_simp(init_ind)) |
|
599 |
val new_ind = init_ind + shift |
|
600 |
val vf = coat(vs_for_coating, new_ind) |
|
601 |
//flats2 returns a list of regex and a single v |
|
602 |
//now |- vf: ALTS(bs1, flat_res) |
|
603 |
//phase 2 transformation so that aalts(bs1, rsf) => aalts(bs, rsdb) and vf => vdb |
|
604 |
val dist_res = distinctBy(flat_res, erase) |
|
605 |
val front_part = distinctBy(flat_res.slice(0, new_ind + 1), erase) |
|
606 |
//val size_reduction = new_ind + 1 - front_part.length |
|
607 |
val vdb = if(dist_res.length == front_part.length )//that means the regex we are interested in is at the end of the list |
|
608 |
{
|
|
609 |
coat(vs_kernel, front_part.length - 1) |
|
610 |
} |
|
611 |
else{
|
|
612 |
coat(Left(vs_kernel), front_part.length - 1) |
|
613 |
} |
|
614 |
//println(vdb) |
|
615 |
//we don't need to transform vdb as this phase will not make enough changes to the regex to affect value. |
|
616 |
//the above statement needs verification. but can be left as is now. |
|
617 |
dist_res match {
|
|
618 |
case Nil => (AZERO, undefined) |
|
619 |
case s :: Nil => (fuse(bs1, s), vdb) |
|
620 |
case rs => (AALTS(bs1, rs), vdb) |
|
621 |
} |
|
622 |
} |
|
623 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
624 |
case (r, v) => (r, v) |
|
625 |
} |
|
626 |
def vsimp(r: ARexp, v: Val): Val = bsimp2(r, v)._2 |
|
627 |
/*This version was first intended for returning a function however a value would be simpler. |
|
| 15 | 628 |
def bsimp2(r: ARexp, v: Val): (ARexp, Val => Val) = (r,v) match{
|
629 |
case (ASEQ(bs1, r1, r2), v) => (bsimp2(r1), bsimp2(r2)) match {
|
|
630 |
case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
631 |
case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
632 |
case ((AONE(bs2), f1) , (r2s, f2)) => (fuse(bs1 ++ bs2, r2s), lambda v => v match { case Sequ(_, v) => f2(v) } )
|
|
633 |
case ((r1s, f1), (r2s, f2)) => (ASEQ(bs1, r1s, r2s), lambda v => v match {case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))}
|
|
634 |
} |
|
635 |
case AALTS(bs1, rs) => {
|
|
636 |
val init_ind = find_pos(v, rs) |
|
637 |
val vs = bsimp2(rs[init_ind], remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
|
638 |
val rs_simp = rs.map(bsimp) |
|
639 |
val vs_kernel = rs_simp[init_ind] match {
|
|
640 |
case AALTS(bs2, rs2) => remove(vs, rs_simp[init_ind])//remove the secondary layer of left and right |
|
641 |
case r => vs |
|
642 |
} |
|
643 |
val vs_for_coating = if(isend(vs, rs_simp, init_ind)) vs_kernel else Left(vs_kernel) |
|
644 |
||
645 |
val r_s = rs_simp[init_ind] |
|
646 |
val shift = flats_vsimp(vs, rs_simp, init_ind) + find_pos(vs, rs_simp[init_ind]) |
|
647 |
val vf = coat(vs_for_coating, shift + init_ind) |
|
648 |
||
649 |
val flat_res = flats(rs_simp)//flats2 returns a list of regex and a single v |
|
650 |
val dist_res = distinctBy(flat_res, erase) |
|
651 |
dist_res match {
|
|
652 |
case Nil => AZERO |
|
653 |
case s :: Nil => fuse(bs1, s) |
|
654 |
case rs => AALTS(bs1, rs) |
|
655 |
} |
|
656 |
} |
|
657 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
658 |
case r => r |
|
| 16 | 659 |
}*/ |
| 5 | 660 |
def super_bsimp(r: ARexp): ARexp = r match {
|
661 |
case ASEQ(bs1, r1, r2) => (super_bsimp(r1), super_bsimp(r2)) match {
|
|
| 0 | 662 |
case (AZERO, _) => AZERO |
663 |
case (_, AZERO) => AZERO |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
664 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)//万一是(r1, alts(rs))这种形式呢 |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
665 |
case (AALTS(bs2, rs), r2) => AALTS(bs1 ++ bs2, rs.map(r => r match {case AONE(bs3) => fuse(bs3, r2) case r => ASEQ(Nil, r, r2)} ) )
|
| 0 | 666 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
667 |
} |
|
668 |
case AALTS(bs1, rs) => {
|
|
| 5 | 669 |
val rs_simp = rs.map(super_bsimp) |
| 0 | 670 |
val flat_res = flats(rs_simp) |
671 |
val dist_res = distinctBy(flat_res, erase) |
|
672 |
dist_res match {
|
|
673 |
case Nil => AZERO |
|
674 |
case s :: Nil => fuse(bs1, s) |
|
675 |
case rs => AALTS(bs1, rs) |
|
676 |
} |
|
677 |
} |
|
| 5 | 678 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
| 0 | 679 |
case r => r |
680 |
} |
|
681 |
||
| 5 | 682 |
|
| 0 | 683 |
def simp_weakened(r: Rexp): Rexp = r match {
|
684 |
case SEQ(r1, r2) => (simp_weakened(r1), r2) match {
|
|
685 |
case (ZERO, _) => ZERO |
|
686 |
case (_, ZERO) => ZERO |
|
687 |
case (ONE, r2s) => r2s |
|
688 |
case (r1s, r2s) => SEQ(r1s, r2s) |
|
689 |
} |
|
690 |
case ALTS(rs) => {
|
|
691 |
val rs_simp = rs.map(simp_weakened) |
|
692 |
val flat_res = rflats(rs_simp) |
|
693 |
val dist_res = rs_simp.distinct |
|
694 |
dist_res match {
|
|
695 |
case Nil => ZERO |
|
696 |
case s :: Nil => s |
|
697 |
case rs => ALTS(rs) |
|
698 |
} |
|
699 |
} |
|
700 |
case STAR(r) => STAR(simp_weakened(r)) |
|
701 |
case r => r |
|
702 |
} |
|
703 |
||
704 |
def bders_simp (s: List[Char], r: ARexp) : ARexp = s match {
|
|
705 |
case Nil => r |
|
706 |
case c::s => bders_simp(s, bsimp(bder(c, r))) |
|
707 |
} |
|
| 107 | 708 |
def bders_simp_rf (s: List[Char], r: ARexp) : ARexp = s match {
|
709 |
case Nil => r |
|
710 |
case c::s => bders_simp_rf(s, bsimp_rf(bder(c, r))) |
|
711 |
} |
|
712 |
||
| 14 | 713 |
//----------------------------------------------------------------------------experiment bsimp |
714 |
/* |
|
715 |
||
| 0 | 716 |
*/ |
717 |
/* |
|
718 |
def time[T](code: => T) = {
|
|
719 |
val start = System.nanoTime() |
|
720 |
val result = code |
|
721 |
val end = System.nanoTime() |
|
722 |
println((end - start)/1.0e9) |
|
723 |
result |
|
724 |
} |
|
725 |
*/ |
|
726 |
// main unsimplified lexing function (produces a value) |
|
727 |
def blex(r: ARexp, s: List[Char]) : Bits = s match {
|
|
728 |
case Nil => if (bnullable(r)) mkepsBC(r) else throw new Exception("Not matched")
|
|
729 |
case c::cs => {
|
|
730 |
val der_res = bder(c,r) |
|
731 |
blex(der_res, cs) |
|
732 |
} |
|
733 |
} |
|
734 |
||
735 |
def bpre_lexing(r: Rexp, s: String) = blex(internalise(r), s.toList) |
|
| 14 | 736 |
def blexing(r: Rexp, s: String) : Val = decode(r, blex(internalise(r), s.toList)) |
| 0 | 737 |
|
738 |
var bder_time = 0L |
|
739 |
var bsimp_time = 0L |
|
740 |
var mkepsBC_time = 0L |
|
741 |
var small_de = 2 |
|
742 |
var big_de = 5 |
|
743 |
var usual_de = 3 |
|
744 |
||
745 |
def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
|
|
746 |
case Nil => {
|
|
747 |
if (bnullable(r)) {
|
|
748 |
//println(asize(r)) |
|
| 5 | 749 |
mkepsBC(r) |
| 0 | 750 |
} |
751 |
else throw new Exception("Not matched")
|
|
752 |
} |
|
753 |
case c::cs => {
|
|
754 |
val der_res = bder(c,r) |
|
755 |
val simp_res = bsimp(der_res) |
|
756 |
blex_simp(simp_res, cs) |
|
757 |
} |
|
758 |
} |
|
| 5 | 759 |
def super_blex_simp(r: ARexp, s: List[Char]): Bits = s match {
|
760 |
case Nil => {
|
|
761 |
if (bnullable(r)) {
|
|
762 |
mkepsBC(r) |
|
763 |
} |
|
764 |
else throw new Exception("Not matched")
|
|
765 |
} |
|
766 |
case c::cs => {
|
|
767 |
super_blex_simp(super_bsimp(bder(c,r)), cs) |
|
768 |
} |
|
769 |
} |
|
| 0 | 770 |
def blex_real_simp(r: ARexp, s: List[Char]): ARexp = s match{
|
771 |
case Nil => r |
|
772 |
case c::cs => blex_real_simp(bsimp(bder(c, r)), cs) |
|
773 |
} |
|
774 |
||
775 |
||
776 |
//size: of a Aregx for testing purposes |
|
777 |
def size(r: Rexp) : Int = r match {
|
|
778 |
case ZERO => 1 |
|
779 |
case ONE => 1 |
|
780 |
case CHAR(_) => 1 |
|
781 |
case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
782 |
case ALTS(rs) => 1 + rs.map(size).sum |
|
783 |
case STAR(r) => 1 + size(r) |
|
784 |
} |
|
785 |
||
786 |
def asize(a: ARexp) = size(erase(a)) |
|
787 |
||
788 |
||
789 |
// decoding does not work yet |
|
790 |
def blexing_simp(r: Rexp, s: String) = {
|
|
791 |
val bit_code = blex_simp(internalise(r), s.toList) |
|
| 5 | 792 |
decode(r, bit_code) |
793 |
} |
|
794 |
def super_blexing_simp(r: Rexp, s: String) = {
|
|
795 |
decode(r, super_blex_simp(internalise(r), s.toList)) |
|
| 0 | 796 |
} |
797 |
||
798 |
||
799 |
||
800 |
||
801 |
||
802 |
// Lexing Rules for a Small While Language |
|
803 |
||
804 |
//symbols |
|
805 |
/* |
|
806 |
val SYM = PRED("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".contains(_))
|
|
807 |
||
808 |
//digits |
|
809 |
val DIGIT = PRED("0123456789".contains(_))
|
|
810 |
//identifiers |
|
811 |
val ID = SYM ~ (SYM | DIGIT).% |
|
812 |
//numbers |
|
813 |
val NUM = STAR(DIGIT) |
|
814 |
//keywords |
|
815 |
val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
|
816 |
val AKEYWORD: Rexp = ALTS(List("skip" , "while" , "do" , "if" , "then" , "else" , "read" , "write" , "true" , "false"))
|
|
817 |
//semicolons |
|
818 |
val SEMI: Rexp = ";" |
|
819 |
//operators |
|
820 |
val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" |
|
821 |
val AOP: Rexp = ALTS(List(":=" , "==" , "-" , "+" , "*" , "!=" , "<" , ">" , "<=" , ">=" , "%" , "/"))
|
|
822 |
//whitespaces |
|
823 |
val WHITESPACE = PLUS(" " | "\n" | "\t")
|
|
824 |
//parentheses |
|
825 |
val RPAREN: Rexp = ")" |
|
826 |
val LPAREN: Rexp = "("
|
|
827 |
val BEGIN: Rexp = "{"
|
|
828 |
val END: Rexp = "}" |
|
829 |
//strings...but probably needs not |
|
830 |
val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
|
831 |
||
832 |
||
833 |
||
834 |
val WHILE_REGS = (("k" $ KEYWORD) |
|
|
835 |
("i" $ ID) |
|
|
836 |
("o" $ OP) |
|
|
837 |
("n" $ NUM) |
|
|
838 |
("s" $ SEMI) |
|
|
839 |
("str" $ STRING) |
|
|
840 |
("p" $ (LPAREN | RPAREN)) |
|
|
841 |
("b" $ (BEGIN | END)) |
|
|
842 |
("w" $ WHITESPACE)).%
|
|
843 |
||
844 |
val AWHILE_REGS = ( |
|
845 |
ALTS( |
|
846 |
List( |
|
847 |
("k" $ AKEYWORD),
|
|
848 |
("i" $ ID),
|
|
849 |
("o" $ AOP) ,
|
|
850 |
("n" $ NUM) ,
|
|
851 |
("s" $ SEMI) ,
|
|
852 |
("str" $ STRING),
|
|
853 |
("p" $ (LPAREN | RPAREN)),
|
|
854 |
("b" $ (BEGIN | END)),
|
|
855 |
("w" $ WHITESPACE)
|
|
856 |
) |
|
857 |
) |
|
858 |
).% |
|
859 |
||
860 |
*/ |
|
861 |
||
862 |
||
863 |
//--------------------------------------------------------------------------------------------------------START OF NON-BITCODE PART (TESTING) |
|
864 |
/* |
|
865 |
// Two Simple While programs |
|
866 |
//======================== |
|
867 |
println("prog0 test")
|
|
868 |
||
869 |
val prog0 = """read n""" |
|
870 |
println(env(lexing_simp(WHILE_REGS, prog0))) |
|
871 |
println(tokenise(WHILE_REGS, prog0)) |
|
872 |
||
873 |
println("prog1 test")
|
|
874 |
||
875 |
val prog1 = """read n; write (n)""" |
|
876 |
println(tokenise(WHILE_REGS, prog1)) |
|
877 |
||
878 |
*/ |
|
879 |
// Bigger Tests |
|
880 |
//============== |
|
881 |
||
882 |
def escape(raw: String): String = {
|
|
883 |
import scala.reflect.runtime.universe._ |
|
884 |
Literal(Constant(raw)).toString |
|
885 |
} |
|
886 |
||
887 |
val prog2 = """ |
|
888 |
write "Fib"; |
|
889 |
read n; |
|
890 |
minus1 := 0; |
|
891 |
minus2 := 1; |
|
892 |
while n > 0 do {
|
|
893 |
temp := minus2; |
|
894 |
minus2 := minus1 + minus2; |
|
895 |
minus1 := temp; |
|
896 |
n := n - 1 |
|
897 |
}; |
|
898 |
write "Result"; |
|
899 |
write minus2 |
|
900 |
""" |
|
901 |
||
902 |
val prog3 = """ |
|
903 |
start := 1000; |
|
904 |
x := start; |
|
905 |
y := start; |
|
906 |
z := start; |
|
907 |
while 0 < x do {
|
|
908 |
while 0 < y do {
|
|
909 |
while 0 < z do {
|
|
910 |
z := z - 1 |
|
911 |
}; |
|
912 |
z := start; |
|
913 |
y := y - 1 |
|
914 |
}; |
|
915 |
y := start; |
|
916 |
x := x - 1 |
|
917 |
} |
|
918 |
""" |
|
919 |
/* |
|
920 |
for(i <- 400 to 400 by 1){
|
|
921 |
println(i+":") |
|
922 |
blexing_simp(WHILE_REGS, prog2 * i) |
|
923 |
} */ |
|
924 |
||
925 |
/* |
|
926 |
for (i <- 2 to 5){
|
|
927 |
for(j <- 1 to 3){
|
|
928 |
println(i,j) |
|
929 |
small_de = i |
|
930 |
usual_de = i + j |
|
931 |
big_de = i + 2*j |
|
932 |
blexing_simp(AWHILE_REGS, prog2 * 100) |
|
933 |
} |
|
934 |
}*/ |
|
935 |
||
936 |
/* |
|
937 |
println("Tokens of prog2")
|
|
938 |
println(tokenise(WHILE_REGS, prog2).mkString("\n"))
|
|
939 |
||
940 |
val fib_tokens = tokenise(WHILE_REGS, prog2) |
|
941 |
fib_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n")
|
|
942 |
||
943 |
||
944 |
val test_tokens = tokenise(WHILE_REGS, prog3) |
|
945 |
test_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n")
|
|
946 |
*/ |
|
947 |
||
948 |
/* |
|
949 |
println("time test for blexing_simp")
|
|
950 |
for (i <- 1 to 1 by 1) {
|
|
951 |
lexing_simp(WHILE_REGS, prog2 * i) |
|
952 |
blexing_simp(WHILE_REGS, prog2 * i) |
|
953 |
for( j <- 0 to each_simp_timeb.length - 1){
|
|
954 |
if( each_simp_timeb(j)/each_simp_time(j) >= 10.0 ) |
|
955 |
println(j, each_simp_timeb(j), each_simp_time(j)) |
|
956 |
} |
|
957 |
} |
|
958 |
*/ |
|
959 |
||
960 |
||
961 |
//--------------------------------------------------------------------------------------------------------END OF NON-BITCODE PART (TESTING) |
|
962 |
||
963 |
||
964 |
||
965 |
def clear() = {
|
|
966 |
print("")
|
|
967 |
//print("\33[H\33[2J")
|
|
968 |
} |
|
969 |
||
970 |
//testing the two lexings produce the same value |
|
971 |
//enumerates strings of length n over alphabet cs |
|
972 |
def strs(n: Int, cs: String) : Set[String] = {
|
|
973 |
if (n == 0) Set("")
|
|
974 |
else {
|
|
975 |
val ss = strs(n - 1, cs) |
|
976 |
ss ++ |
|
977 |
(for (s <- ss; c <- cs.toList) yield c + s) |
|
978 |
} |
|
979 |
} |
|
980 |
def enum(n: Int, s: String) : Stream[Rexp] = n match {
|
|
981 |
case 0 => ZERO #:: ONE #:: s.toStream.map(CHAR) |
|
982 |
case n => {
|
|
983 |
val rs = enum(n - 1, s) |
|
984 |
rs #::: |
|
985 |
(for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: |
|
986 |
(for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: |
|
987 |
(for (r1 <- rs) yield STAR(r1)) |
|
988 |
} |
|
989 |
} |
|
990 |
||
991 |
//tests blexing and lexing |
|
992 |
def tests_blexer_simp(ss: Set[String])(r: Rexp) = {
|
|
993 |
clear() |
|
994 |
//println(s"Testing ${r}")
|
|
995 |
for (s <- ss.par) yield {
|
|
996 |
val res1 = Try(Some(lexing_simp(r, s))).getOrElse(None) |
|
| 5 | 997 |
val res2 = Try(Some(super_blexing_simp(r, s))).getOrElse(None) |
| 0 | 998 |
if (res1 != res2) println(s"Disagree on ${r} and ${s}")
|
999 |
if (res1 != res2) println(s" ${res1} != ${res2}")
|
|
1000 |
if (res1 != res2) Some((r, s)) else None |
|
1001 |
} |
|
1002 |
} |
|
1003 |
||
1004 |
||
1005 |
||
| 5 | 1006 |
|
| 0 | 1007 |
/* |
1008 |
def single_expression_explorer(ar: ARexp, ss: Set[String]): Unit = {
|
|
1009 |
for (s <- ss){
|
|
1010 |
||
1011 |
val der_res = bder(c, ar) |
|
1012 |
val simp_res = bsimp(der_res) |
|
1013 |
println(asize(der_res)) |
|
1014 |
println(asize(simp_res)) |
|
1015 |
single_expression_explorer(simp_res, (sc - c)) |
|
1016 |
} |
|
1017 |
}*/ |
|
1018 |
||
1019 |
//single_expression_explorer(internalise(("c"~("a"+"b"))%) , Set('a','b','c'))
|
|
1020 |
||
1021 |
||
1022 |
} |
|
1023 |
||
1024 |
import Rexp.Bits |
|
1025 |
abstract class ARexp |
|
1026 |
case object AZERO extends ARexp |
|
1027 |
case class AONE(bs: Bits) extends ARexp |
|
1028 |
case class ACHAR(bs: Bits, f: Char) extends ARexp |
|
1029 |
case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
|
1030 |
case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
|
1031 |
case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
|
1032 |
||
1033 |
||
1034 |
||
1035 |
abstract class Val |
|
1036 |
case object Empty extends Val |
|
1037 |
case class Chr(c: Char) extends Val |
|
1038 |
case class Sequ(v1: Val, v2: Val) extends Val |
|
1039 |
case class Left(v: Val) extends Val |
|
1040 |
case class Right(v: Val) extends Val |
|
1041 |
case class Stars(vs: List[Val]) extends Val |
|
1042 |
case class Rec(x: String, v: Val) extends Val |
|
| 17 | 1043 |
case object undefined extends Val |
| 0 | 1044 |
//case class Pos(i: Int, v: Val) extends Val |
1045 |
case object Prd extends Val |