1 package greeter |
|
2 |
|
3 |
|
4 object POSIX { |
|
5 println("Posix Algorithm") //> Posix Algorithm |
|
6 |
|
7 abstract class Rexp |
|
8 case object NULL extends Rexp |
|
9 case object EMPTY extends Rexp |
|
10 case class CHAR(c: Char) extends Rexp |
|
11 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
12 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
13 case class STAR(r: Rexp) extends Rexp |
|
14 case class RECD(x: String, r: Rexp) extends Rexp |
|
15 |
|
16 abstract class Val |
|
17 case object Void extends Val |
|
18 case class Chr(c: Char) extends Val |
|
19 case class Sequ(v1: Val, v2: Val) extends Val |
|
20 case class Left(v: Val) extends Val |
|
21 case class Right(v: Val) extends Val |
|
22 case class Stars(vs: List[Val]) extends Val |
|
23 case class Rec(x: String, v: Val) extends Val |
|
24 |
|
25 def charlist2rexp(s: List[Char]): Rexp = s match { |
|
26 case Nil => EMPTY |
|
27 case c :: Nil => CHAR(c) |
|
28 case c :: s => SEQ(CHAR(c), charlist2rexp(s)) |
|
29 } //> charlist2rexp: (s: List[Char])greeter.POSIX.Rexp |
|
30 implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) |
|
31 //> string2rexp: (s: String)greeter.POSIX.Rexp |
|
32 |
|
33 implicit def RexpOps(r: Rexp) = new { |
|
34 def |(s: Rexp) = ALT(r, s) |
|
35 def % = STAR(r) |
|
36 def ~(s: Rexp) = SEQ(r, s) |
|
37 } //> RexpOps: (r: greeter.POSIX.Rexp)AnyRef{def |(s: greeter.POSIX.Rexp): greete |
|
38 //| r.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greet |
|
39 //| er.POSIX.SEQ} |
|
40 |
|
41 implicit def stringOps(s: String) = new { |
|
42 def |(r: Rexp) = ALT(s, r) |
|
43 def |(r: String) = ALT(s, r) |
|
44 def % = STAR(s) |
|
45 def ~(r: Rexp) = SEQ(s, r) |
|
46 def ~(r: String) = SEQ(s, r) |
|
47 def $(r: Rexp) = RECD(s, r) |
|
48 } //> stringOps: (s: String)AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.AL |
|
49 //| T; def |(r: String): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r: |
|
50 //| greeter.POSIX.Rexp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SE |
|
51 //| Q; def $(r: greeter.POSIX.Rexp): greeter.POSIX.RECD} |
|
52 |
|
53 // size of a regular expressions - for testing purposes |
|
54 def size(r: Rexp): Int = r match { |
|
55 case NULL => 1 |
|
56 case EMPTY => 1 |
|
57 case CHAR(_) => 1 |
|
58 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
|
59 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
60 case STAR(r) => 1 + size(r) |
|
61 case RECD(_, r) => 1 + size(r) |
|
62 } //> size: (r: greeter.POSIX.Rexp)Int |
|
63 |
|
64 // nullable function: tests whether the regular |
|
65 // expression can recognise the empty string |
|
66 def nullable(r: Rexp): Boolean = r match { |
|
67 case NULL => false |
|
68 case EMPTY => true |
|
69 case CHAR(_) => false |
|
70 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
71 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
72 case STAR(_) => true |
|
73 case RECD(_, r1) => nullable(r1) |
|
74 } //> nullable: (r: greeter.POSIX.Rexp)Boolean |
|
75 |
|
76 // derivative of a regular expression w.r.t. a character |
|
77 def der(c: Char, r: Rexp): Rexp = r match { |
|
78 case NULL => NULL |
|
79 case EMPTY => NULL |
|
80 case CHAR(d) => if (c == d) EMPTY else NULL |
|
81 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
82 case SEQ(r1, r2) => |
|
83 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
84 else SEQ(der(c, r1), r2) |
|
85 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
86 case RECD(_, r1) => der(c, r1) |
|
87 } //> der: (c: Char, r: greeter.POSIX.Rexp)greeter.POSIX.Rexp |
|
88 |
|
89 // derivative w.r.t. a string (iterates der) |
|
90 def ders(s: List[Char], r: Rexp): Rexp = s match { |
|
91 case Nil => r |
|
92 case c :: s => ders(s, der(c, r)) |
|
93 } //> ders: (s: List[Char], r: greeter.POSIX.Rexp)greeter.POSIX.Rexp |
|
94 |
|
95 // extracts a string from value |
|
96 def flatten(v: Val): String = v match { |
|
97 case Void => "" |
|
98 case Chr(c) => c.toString |
|
99 case Left(v) => flatten(v) |
|
100 case Right(v) => flatten(v) |
|
101 case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
|
102 case Stars(vs) => vs.map(flatten).mkString |
|
103 case Rec(_, v) => flatten(v) |
|
104 } //> flatten: (v: greeter.POSIX.Val)String |
|
105 |
|
106 // extracts an environment from a value |
|
107 def env(v: Val): List[(String, String)] = v match { |
|
108 case Void => Nil |
|
109 case Chr(c) => Nil |
|
110 case Left(v) => env(v) |
|
111 case Right(v) => env(v) |
|
112 case Sequ(v1, v2) => env(v1) ::: env(v2) |
|
113 case Stars(vs) => vs.flatMap(env) |
|
114 case Rec(x, v) => (x, flatten(v)) :: env(v) |
|
115 } //> env: (v: greeter.POSIX.Val)List[(String, String)] |
|
116 |
|
117 def mkeps(r: Rexp): Val = r match { |
|
118 case EMPTY => Void |
|
119 case ALT(r1, r2) => |
|
120 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
|
121 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
|
122 case STAR(r) => Stars(Nil) |
|
123 case RECD(x, r) => Rec(x, mkeps(r)) |
|
124 } //> mkeps: (r: greeter.POSIX.Rexp)greeter.POSIX.Val |
|
125 |
|
126 def inj(r: Rexp, c: Char, v: Val): Val = (r, v) match { |
|
127 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1) :: vs) |
|
128 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
|
129 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
|
130 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
|
131 case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1)) |
|
132 case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2)) |
|
133 case (CHAR(d), Void) => Chr(d) |
|
134 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
|
135 } //> inj: (r: greeter.POSIX.Rexp, c: Char, v: greeter.POSIX.Val)greeter.POSIX.Va |
|
136 //| l |
|
137 |
|
138 // main lexing function (produces a value) |
|
139 def lex(r: Rexp, s: List[Char]): Val = s match { |
|
140 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
|
141 case c :: cs => inj(r, c, lex(der(c, r), cs)) |
|
142 } //> lex: (r: greeter.POSIX.Rexp, s: List[Char])greeter.POSIX.Val |
|
143 |
|
144 def lexing(r: Rexp, s: String): Val = lex(r, s.toList) |
|
145 //> lexing: (r: greeter.POSIX.Rexp, s: String)greeter.POSIX.Val |
|
146 |
|
147 val r = (("1" $ "a") | (("2" $ "b") | ("3" $ "ab"))).% |
|
148 //> r : greeter.POSIX.STAR = STAR(ALT(RECD(1,CHAR(a)),ALT(RECD(2,CHAR(b)),RECD |
|
149 //| (3,SEQ(CHAR(a),CHAR(b)))))) |
|
150 env(lexing(r, "ba")) //> res0: List[(String, String)] = List((2,b), (1,a)) |
|
151 |
|
152 val r1 = "a" | "b" //> r1 : greeter.POSIX.ALT = ALT(CHAR(a),CHAR(b)) |
|
153 lexing(r1, "a") //> res1: greeter.POSIX.Val = Left(Chr(a)) |
|
154 |
|
155 // Lexing Rules for a Small While Language |
|
156 |
|
157 def PLUS(r: Rexp) = r ~ r.% //> PLUS: (r: greeter.POSIX.Rexp)greeter.POSIX.SEQ |
|
158 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" |
|
159 //> SYM : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT( |
|
160 //| ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHAR(c |
|
161 //| )),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k)), |
|
162 //| CHAR(l)),CHAR(m)),CHAR(n)),CHAR(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHA |
|
163 //| R(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z)) |
|
164 val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" |
|
165 //> DIGIT : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CH |
|
166 //| AR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR( |
|
167 //| 9)) |
|
168 val ID = SYM ~ (SYM | DIGIT).% //> ID : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A |
|
169 //| LT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHA |
|
170 //| R(c)),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k |
|
171 //| )),CHAR(l)),CHAR(m)),CHAR(n)),CHAR(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)), |
|
172 //| CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z)),STAR(ALT(ALT |
|
173 //| (ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(AL |
|
174 //| T(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHAR(c)),CHAR(d)),CHAR(e)),CHAR(f)), |
|
175 //| CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k)),CHAR(l)),CHAR(m)),CHAR(n)),CHA |
|
176 //| R(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w |
|
177 //| )),CHAR(x)),CHAR(y)),CHAR(z)),ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),C |
|
178 //| HAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR |
|
179 //| (9))))) |
|
180 val NUM = PLUS(DIGIT) //> NUM : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0), |
|
181 //| CHAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHA |
|
182 //| R(9)),STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CHAR(1)),CHAR(2)),CH |
|
183 //| AR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(9)))) |
|
184 val KEYWORD: Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
|
185 //> KEYWORD : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHA |
|
186 //| R(s),SEQ(CHAR(k),SEQ(CHAR(i),CHAR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i) |
|
187 //| ,SEQ(CHAR(l),CHAR(e)))))),SEQ(CHAR(d),CHAR(o))),SEQ(CHAR(i),CHAR(f))),SEQ(C |
|
188 //| HAR(t),SEQ(CHAR(h),SEQ(CHAR(e),CHAR(n))))),SEQ(CHAR(e),SEQ(CHAR(l),SEQ(CHAR |
|
189 //| (s),CHAR(e))))),SEQ(CHAR(r),SEQ(CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w) |
|
190 //| ,SEQ(CHAR(r),SEQ(CHAR(i),SEQ(CHAR(t),CHAR(e)))))),SEQ(CHAR(t),SEQ(CHAR(r),S |
|
191 //| EQ(CHAR(u),CHAR(e))))),SEQ(CHAR(f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHAR |
|
192 //| (e)))))) |
|
193 val SEMI: Rexp = ";" //> SEMI : greeter.POSIX.Rexp = CHAR(;) |
|
194 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" |
|
195 //> OP : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ( |
|
196 //| CHAR(:),CHAR(=)),SEQ(CHAR(=),CHAR(=))),CHAR(-)),CHAR(+)),CHAR(*)),SEQ(CHAR( |
|
197 //| !),CHAR(=))),CHAR(<)),CHAR(>)),SEQ(CHAR(<),CHAR(=))),SEQ(CHAR(>),CHAR(=))), |
|
198 //| CHAR(%)),CHAR(/)) |
|
199 val WHITESPACE = PLUS(" " | "\n" | "\t") //> WHITESPACE : greeter.POSIX.SEQ = SEQ(ALT(ALT(CHAR( ),CHAR( |
|
200 //| )),CHAR( )),STAR(ALT(ALT(CHAR( ),CHAR( |
|
201 //| )),CHAR( )))) |
|
202 val RPAREN: Rexp = ")" //> RPAREN : greeter.POSIX.Rexp = CHAR()) |
|
203 val LPAREN: Rexp = "(" //> LPAREN : greeter.POSIX.Rexp = CHAR(() |
|
204 val BEGIN: Rexp = "{" //> BEGIN : greeter.POSIX.Rexp = CHAR({) |
|
205 val END: Rexp = "}" //> END : greeter.POSIX.Rexp = CHAR(}) |
|
206 |
|
207 /* |
|
208 * val WHILE_REGS = (("k" $ KEYWORD) | |
|
209 ("i" $ ID) | |
|
210 ("o" $ OP) | |
|
211 ("n" $ NUM) | |
|
212 ("s" $ SEMI) | |
|
213 ("p" $ (LPAREN | RPAREN)) | |
|
214 ("b" $ (BEGIN | END)) | |
|
215 ("w" $ WHITESPACE)).% |
|
216 */ |
|
217 |
|
218 val WHILE_REGS = (KEYWORD | |
|
219 ID | |
|
220 OP | |
|
221 NUM | |
|
222 SEMI | |
|
223 LPAREN | RPAREN | |
|
224 BEGIN | END | |
|
225 WHITESPACE).% //> WHILE_REGS : greeter.POSIX.STAR = STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT |
|
226 //| (ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHAR(s),SEQ(CHAR(k),SEQ(CHAR(i),CH |
|
227 //| AR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i),SEQ(CHAR(l),CHAR(e)))))),SEQ(C |
|
228 //| HAR(d),CHAR(o))),SEQ(CHAR(i),CHAR(f))),SEQ(CHAR(t),SEQ(CHAR(h),SEQ(CHAR(e), |
|
229 //| CHAR(n))))),SEQ(CHAR(e),SEQ(CHAR(l),SEQ(CHAR(s),CHAR(e))))),SEQ(CHAR(r),SEQ |
|
230 //| (CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w),SEQ(CHAR(r),SEQ(CHAR(i),SEQ(CH |
|
231 //| AR(t),CHAR(e)))))),SEQ(CHAR(t),SEQ(CHAR(r),SEQ(CHAR(u),CHAR(e))))),SEQ(CHAR |
|
232 //| (f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHAR(e)))))),SEQ(ALT(ALT(ALT(ALT(AL |
|
233 //| T(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A |
|
234 //| LT(ALT(CHAR(a),CHAR(b)),CHAR(c)),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h |
|
235 //| )),CHAR(i)),CHAR(j)),CHAR(k)),CHAR(l)),CHAR(m)),CHAR(n)),CHAR(o)),CHAR(p)), |
|
236 //| CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHA |
|
237 //| R(y)),CHAR(z)),STAR(ALT |
|
238 //| Output exceeds cutoff limit. |
|
239 |
|
240 // Some Tests |
|
241 //============ |
|
242 |
|
243 def time[T](code: => T) = { |
|
244 val start = System.nanoTime() |
|
245 val result = code |
|
246 val end = System.nanoTime() |
|
247 println((end - start) / 1.0e9) |
|
248 result |
|
249 } //> time: [T](code: => T)T |
|
250 |
|
251 |
|
252 val abc = List('a', 'b', 'c') //> abc : List[Char] = List(a, b, c) |
|
253 val nullRexp = null //> nullRexp : Null = null |
|
254 val myRexp = charlist2rexp(abc) //> myRexp : greeter.POSIX.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c))) |
|
255 val myRexp2 = string2rexp("FahadAusaf") //> myRexp2 : greeter.POSIX.Rexp = SEQ(CHAR(F),SEQ(CHAR(a),SEQ(CHAR(h),SEQ(CHA |
|
256 //| R(a),SEQ(CHAR(d),SEQ(CHAR(A),SEQ(CHAR(u),SEQ(CHAR(s),SEQ(CHAR(a),CHAR(f)))) |
|
257 //| )))))) |
|
258 |
|
259 RexpOps(myRexp2) //> res2: AnyRef{def |(s: greeter.POSIX.Rexp): greeter.POSIX.ALT; def %: greete |
|
260 //| r.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greeter.POSIX.SEQ} = greeter.PO |
|
261 //| SIX$$anonfun$main$1$$anon$1@37ecb28e |
|
262 |
|
263 stringOps("Fahad") //> res3: AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.ALT; def |(r: Stri |
|
264 //| ng): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r: greeter.POSIX.R |
|
265 //| exp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SEQ; def $(r: gree |
|
266 //| ter.POSIX.Rexp): greeter.POSIX.RECD} = greeter.POSIX$$anonfun$main$1$$anon$ |
|
267 //| 2@14bea551 |
|
268 |
|
269 size(myRexp2) //> res4: Int = 19 |
|
270 nullable(nullRexp) //> scala.MatchError: null |
|
271 //| at greeter.POSIX$$anonfun$main$1.nullable$1(greeter.POSIX.scala:59) |
|
272 //| at greeter.POSIX$$anonfun$main$1.apply$mcV$sp(greeter.POSIX.scala:202) |
|
273 //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$$anonfun$$exe |
|
274 //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76) |
|
275 //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.redirected(W |
|
276 //| orksheetSupport.scala:65) |
|
277 //| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.$execute(Wor |
|
278 //| ksheetSupport.scala:75) |
|
279 //| at greeter.POSIX$.main(greeter.POSIX.scala:3) |
|
280 //| at greeter.POSIX.main(greeter.POSIX.scala) |
|
281 |
|
282 val newRexp = der('a',myRexp) |
|
283 |
|
284 |
|
285 |
|
286 |
|
287 |
|
288 |
|
289 |
|
290 |
|
291 |
|
292 |
|
293 |
|
294 |
|
295 |
|
296 |
|
297 |
|
298 |
|
299 |
|
300 |
|
301 |
|
302 |
|
303 |
|
304 //this is some crap |
|
305 } |
|