--- a/Fahad/Scala/POSIX.sc Sat Nov 08 12:19:37 2014 +0000
+++ b/Fahad/Scala/POSIX.sc Sun Nov 09 19:14:23 2014 +0000
@@ -1,8 +1,9 @@
package greeter
-
+
+
object POSIX {
- println("Posix Algorithm") //> Posix Algorithm
-
+ println("Posix Algorithm") //> Posix Algorithm
+
abstract class Rexp
case object NULL extends Rexp
case object EMPTY extends Rexp
@@ -11,7 +12,7 @@
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
case class STAR(r: Rexp) extends Rexp
case class RECD(x: String, r: Rexp) extends Rexp
-
+
abstract class Val
case object Void extends Val
case class Chr(c: Char) extends Val
@@ -20,23 +21,23 @@
case class Right(v: Val) extends Val
case class Stars(vs: List[Val]) extends Val
case class Rec(x: String, v: Val) extends Val
-
+
def charlist2rexp(s: List[Char]): Rexp = s match {
case Nil => EMPTY
case c :: Nil => CHAR(c)
case c :: s => SEQ(CHAR(c), charlist2rexp(s))
- } //> charlist2rexp: (s: List[Char])greeter.POSIX.Rexp
+ } //> charlist2rexp: (s: List[Char])greeter.POSIX.Rexp
implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
- //> string2rexp: (s: String)greeter.POSIX.Rexp
-
+ //> string2rexp: (s: String)greeter.POSIX.Rexp
+
implicit def RexpOps(r: Rexp) = new {
def |(s: Rexp) = ALT(r, s)
def % = STAR(r)
def ~(s: Rexp) = SEQ(r, s)
} //> RexpOps: (r: greeter.POSIX.Rexp)AnyRef{def |(s: greeter.POSIX.Rexp): greete
//| r.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greet
- //| er.POSIX.SEQ}
-
+ //| er.POSIX.SEQ}
+
implicit def stringOps(s: String) = new {
def |(r: Rexp) = ALT(s, r)
def |(r: String) = ALT(s, r)
@@ -47,8 +48,8 @@
} //> stringOps: (s: String)AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.AL
//| T; def |(r: String): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r:
//| greeter.POSIX.Rexp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SE
- //| Q; def $(r: greeter.POSIX.Rexp): greeter.POSIX.RECD}
-
+ //| Q; def $(r: greeter.POSIX.Rexp): greeter.POSIX.RECD}
+
// size of a regular expressions - for testing purposes
def size(r: Rexp): Int = r match {
case NULL => 1
@@ -58,8 +59,8 @@
case SEQ(r1, r2) => 1 + size(r1) + size(r2)
case STAR(r) => 1 + size(r)
case RECD(_, r) => 1 + size(r)
- } //> size: (r: greeter.POSIX.Rexp)Int
-
+ } //> size: (r: greeter.POSIX.Rexp)Int
+
// nullable function: tests whether the regular
// expression can recognise the empty string
def nullable(r: Rexp): Boolean = r match {
@@ -70,8 +71,8 @@
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
case STAR(_) => true
case RECD(_, r1) => nullable(r1)
- } //> nullable: (r: greeter.POSIX.Rexp)Boolean
-
+ } //> nullable: (r: greeter.POSIX.Rexp)Boolean
+
// derivative of a regular expression w.r.t. a character
def der(c: Char, r: Rexp): Rexp = r match {
case NULL => NULL
@@ -83,14 +84,14 @@
else SEQ(der(c, r1), r2)
case STAR(r) => SEQ(der(c, r), STAR(r))
case RECD(_, r1) => der(c, r1)
- } //> der: (c: Char, r: greeter.POSIX.Rexp)greeter.POSIX.Rexp
-
+ } //> der: (c: Char, r: greeter.POSIX.Rexp)greeter.POSIX.Rexp
+
// derivative w.r.t. a string (iterates der)
def ders(s: List[Char], r: Rexp): Rexp = s match {
case Nil => r
case c :: s => ders(s, der(c, r))
- } //> ders: (s: List[Char], r: greeter.POSIX.Rexp)greeter.POSIX.Rexp
-
+ } //> ders: (s: List[Char], r: greeter.POSIX.Rexp)greeter.POSIX.Rexp
+
// extracts a string from value
def flatten(v: Val): String = v match {
case Void => ""
@@ -100,8 +101,8 @@
case Sequ(v1, v2) => flatten(v1) + flatten(v2)
case Stars(vs) => vs.map(flatten).mkString
case Rec(_, v) => flatten(v)
- } //> flatten: (v: greeter.POSIX.Val)String
-
+ } //> flatten: (v: greeter.POSIX.Val)String
+
// extracts an environment from a value
def env(v: Val): List[(String, String)] = v match {
case Void => Nil
@@ -111,8 +112,8 @@
case Sequ(v1, v2) => env(v1) ::: env(v2)
case Stars(vs) => vs.flatMap(env)
case Rec(x, v) => (x, flatten(v)) :: env(v)
- } //> env: (v: greeter.POSIX.Val)List[(String, String)]
-
+ } //> env: (v: greeter.POSIX.Val)List[(String, String)]
+
def mkeps(r: Rexp): Val = r match {
case EMPTY => Void
case ALT(r1, r2) =>
@@ -120,8 +121,8 @@
case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
case STAR(r) => Stars(Nil)
case RECD(x, r) => Rec(x, mkeps(r))
- } //> mkeps: (r: greeter.POSIX.Rexp)greeter.POSIX.Val
-
+ } //> mkeps: (r: greeter.POSIX.Rexp)greeter.POSIX.Val
+
def inj(r: Rexp, c: Char, v: Val): Val = (r, v) match {
case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1) :: vs)
case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
@@ -132,38 +133,38 @@
case (CHAR(d), Void) => Chr(d)
case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
} //> inj: (r: greeter.POSIX.Rexp, c: Char, v: greeter.POSIX.Val)greeter.POSIX.Va
- //| l
-
+ //| l
+
// main lexing function (produces a value)
def lex(r: Rexp, s: List[Char]): Val = s match {
case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
case c :: cs => inj(r, c, lex(der(c, r), cs))
- } //> lex: (r: greeter.POSIX.Rexp, s: List[Char])greeter.POSIX.Val
-
+ } //> lex: (r: greeter.POSIX.Rexp, s: List[Char])greeter.POSIX.Val
+
def lexing(r: Rexp, s: String): Val = lex(r, s.toList)
- //> lexing: (r: greeter.POSIX.Rexp, s: String)greeter.POSIX.Val
-
+ //> lexing: (r: greeter.POSIX.Rexp, s: String)greeter.POSIX.Val
+
val r = (("1" $ "a") | (("2" $ "b") | ("3" $ "ab"))).%
//> r : greeter.POSIX.STAR = STAR(ALT(RECD(1,CHAR(a)),ALT(RECD(2,CHAR(b)),RECD
- //| (3,SEQ(CHAR(a),CHAR(b))))))
- env(lexing(r, "ba")) //> res0: List[(String, String)] = List((2,b), (1,a))
-
- val r1 = "a" | "b" //> r1 : greeter.POSIX.ALT = ALT(CHAR(a),CHAR(b))
- lexing(r1, "a") //> res1: greeter.POSIX.Val = Left(Chr(a))
-
+ //| (3,SEQ(CHAR(a),CHAR(b))))))
+ env(lexing(r, "ba")) //> res0: List[(String, String)] = List((2,b), (1,a))
+
+ val r1 = "a" | "b" //> r1 : greeter.POSIX.ALT = ALT(CHAR(a),CHAR(b))
+ lexing(r1, "a") //> res1: greeter.POSIX.Val = Left(Chr(a))
+
// Lexing Rules for a Small While Language
-
- def PLUS(r: Rexp) = r ~ r.% //> PLUS: (r: greeter.POSIX.Rexp)greeter.POSIX.SEQ
+
+ def PLUS(r: Rexp) = r ~ r.% //> PLUS: (r: greeter.POSIX.Rexp)greeter.POSIX.SEQ
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"
//> SYM : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(
//| ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHAR(c
//| )),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k)),
//| CHAR(l)),CHAR(m)),CHAR(n)),CHAR(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHA
- //| R(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z))
+ //| R(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z))
val DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
//> DIGIT : greeter.POSIX.ALT = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CH
//| AR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(
- //| 9))
+ //| 9))
val ID = SYM ~ (SYM | DIGIT).% //> ID : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A
//| LT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(a),CHAR(b)),CHA
//| R(c)),CHAR(d)),CHAR(e)),CHAR(f)),CHAR(g)),CHAR(h)),CHAR(i)),CHAR(j)),CHAR(k
@@ -175,11 +176,11 @@
//| R(o)),CHAR(p)),CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w
//| )),CHAR(x)),CHAR(y)),CHAR(z)),ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),C
//| HAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR
- //| (9)))))
+ //| (9)))))
val NUM = PLUS(DIGIT) //> NUM : greeter.POSIX.SEQ = SEQ(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),
//| CHAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHA
//| R(9)),STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CHAR(1)),CHAR(2)),CH
- //| AR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(9))))
+ //| AR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHAR(9))))
val KEYWORD: Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false"
//> KEYWORD : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHA
//| R(s),SEQ(CHAR(k),SEQ(CHAR(i),CHAR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i)
@@ -188,21 +189,21 @@
//| (s),CHAR(e))))),SEQ(CHAR(r),SEQ(CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w)
//| ,SEQ(CHAR(r),SEQ(CHAR(i),SEQ(CHAR(t),CHAR(e)))))),SEQ(CHAR(t),SEQ(CHAR(r),S
//| EQ(CHAR(u),CHAR(e))))),SEQ(CHAR(f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHAR
- //| (e))))))
- val SEMI: Rexp = ";" //> SEMI : greeter.POSIX.Rexp = CHAR(;)
+ //| (e))))))
+ val SEMI: Rexp = ";" //> SEMI : greeter.POSIX.Rexp = CHAR(;)
val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"
//> OP : greeter.POSIX.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(
//| CHAR(:),CHAR(=)),SEQ(CHAR(=),CHAR(=))),CHAR(-)),CHAR(+)),CHAR(*)),SEQ(CHAR(
//| !),CHAR(=))),CHAR(<)),CHAR(>)),SEQ(CHAR(<),CHAR(=))),SEQ(CHAR(>),CHAR(=))),
- //| CHAR(%)),CHAR(/))
+ //| CHAR(%)),CHAR(/))
val WHITESPACE = PLUS(" " | "\n" | "\t") //> WHITESPACE : greeter.POSIX.SEQ = SEQ(ALT(ALT(CHAR( ),CHAR(
//| )),CHAR( )),STAR(ALT(ALT(CHAR( ),CHAR(
- //| )),CHAR( ))))
- val RPAREN: Rexp = ")" //> RPAREN : greeter.POSIX.Rexp = CHAR())
- val LPAREN: Rexp = "(" //> LPAREN : greeter.POSIX.Rexp = CHAR(()
- val BEGIN: Rexp = "{" //> BEGIN : greeter.POSIX.Rexp = CHAR({)
- val END: Rexp = "}" //> END : greeter.POSIX.Rexp = CHAR(})
-
+ //| )),CHAR( ))))
+ val RPAREN: Rexp = ")" //> RPAREN : greeter.POSIX.Rexp = CHAR())
+ val LPAREN: Rexp = "(" //> LPAREN : greeter.POSIX.Rexp = CHAR(()
+ val BEGIN: Rexp = "{" //> BEGIN : greeter.POSIX.Rexp = CHAR({)
+ val END: Rexp = "}" //> END : greeter.POSIX.Rexp = CHAR(})
+
/*
* val WHILE_REGS = (("k" $ KEYWORD) |
("i" $ ID) |
@@ -213,7 +214,7 @@
("b" $ (BEGIN | END)) |
("w" $ WHITESPACE)).%
*/
-
+
val WHILE_REGS = (KEYWORD |
ID |
OP |
@@ -235,48 +236,48 @@
//| CHAR(q)),CHAR(r)),CHAR(s)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHA
//| R(y)),CHAR(z)),STAR(ALT
//| Output exceeds cutoff limit.
-
+
// Some Tests
//============
-
+
def time[T](code: => T) = {
val start = System.nanoTime()
val result = code
val end = System.nanoTime()
println((end - start) / 1.0e9)
result
- } //> time: [T](code: => T)T
-
+ } //> time: [T](code: => T)T
+
- val abc = List('a', 'b', 'c') //> abc : List[Char] = List(a, b, c)
- val nullRexp = null //> nullRexp : Null = null
- val myRexp = charlist2rexp(abc) //> myRexp : greeter.POSIX.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c)))
+ val abc = List('a', 'b', 'c') //> abc : List[Char] = List(a, b, c)
+ val nullRexp = null //> nullRexp : Null = null
+ val myRexp = charlist2rexp(abc) //> myRexp : greeter.POSIX.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c)))
val myRexp2 = string2rexp("FahadAusaf") //> myRexp2 : greeter.POSIX.Rexp = SEQ(CHAR(F),SEQ(CHAR(a),SEQ(CHAR(h),SEQ(CHA
//| R(a),SEQ(CHAR(d),SEQ(CHAR(A),SEQ(CHAR(u),SEQ(CHAR(s),SEQ(CHAR(a),CHAR(f))))
- //| ))))))
+ //| ))))))
RexpOps(myRexp2) //> res2: AnyRef{def |(s: greeter.POSIX.Rexp): greeter.POSIX.ALT; def %: greete
//| r.POSIX.STAR; def ~(s: greeter.POSIX.Rexp): greeter.POSIX.SEQ} = greeter.PO
- //| SIX$$anonfun$main$1$$anon$1@37ecb28e
+ //| SIX$$anonfun$main$1$$anon$1@37ecb28e
stringOps("Fahad") //> res3: AnyRef{def |(r: greeter.POSIX.Rexp): greeter.POSIX.ALT; def |(r: Stri
//| ng): greeter.POSIX.ALT; def %: greeter.POSIX.STAR; def ~(r: greeter.POSIX.R
//| exp): greeter.POSIX.SEQ; def ~(r: String): greeter.POSIX.SEQ; def $(r: gree
//| ter.POSIX.Rexp): greeter.POSIX.RECD} = greeter.POSIX$$anonfun$main$1$$anon$
- //| 2@14bea551
+ //| 2@14bea551
- size(myRexp2) //> res4: Int = 19
- nullable(nullRexp) //> scala.MatchError: null
- //| at greeter.POSIX$$anonfun$main$1.nullable$1(greeter.POSIX.scala:59)
- //| at greeter.POSIX$$anonfun$main$1.apply$mcV$sp(greeter.POSIX.scala:202)
+ size(myRexp2) //> res4: Int = 19
+ nullable(nullRexp) //> scala.MatchError: null
+ //| at greeter.POSIX$$anonfun$main$1.nullable$1(greeter.POSIX.scala:59)
+ //| at greeter.POSIX$$anonfun$main$1.apply$mcV$sp(greeter.POSIX.scala:202)
//| at org.scalaide.worksheet.runtime.library.WorksheetSupport$$anonfun$$exe
- //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76)
+ //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76)
//| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.redirected(W
- //| orksheetSupport.scala:65)
+ //| orksheetSupport.scala:65)
//| at org.scalaide.worksheet.runtime.library.WorksheetSupport$.$execute(Wor
- //| ksheetSupport.scala:75)
- //| at greeter.POSIX$.main(greeter.POSIX.scala:3)
- //| at greeter.POSIX.main(greeter.POSIX.scala)
+ //| ksheetSupport.scala:75)
+ //| at greeter.POSIX$.main(greeter.POSIX.scala:3)
+ //| at greeter.POSIX.main(greeter.POSIX.scala)
val newRexp = der('a',myRexp)
@@ -301,4 +302,4 @@
//this is some crap
-}
\ No newline at end of file
+}