diff -r 56afb5950289 -r e5afb97b54f6 Fahad/Eclipse/ScalaProjects/src/Handouts/Posix.sc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Fahad/Eclipse/ScalaProjects/src/Handouts/Posix.sc	Tue Nov 04 19:51:39 2014 +0000
@@ -0,0 +1,283 @@
+package Handouts
+
+object Posix {
+
+  abstract class Rexp
+  case object NULL extends Rexp
+  case object EMPTY extends Rexp
+  case class CHAR(c: Char) extends Rexp
+  case class ALT(r1: Rexp, r2: Rexp) extends Rexp
+  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
+  case class Sequ(v1: Val, v2: Val) extends Val
+  case class Left(v: Val) extends Val
+  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])Handouts.Posix.Rexp
+  implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+                                                  //> string2rexp: (s: String)Handouts.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: Handouts.Posix.Rexp)AnyRef{def |(s: Handouts.Posix.Rexp): Hand
+                                                  //| outs.Posix.ALT; def %: Handouts.Posix.STAR; def ~(s: Handouts.Posix.Rexp): 
+                                                  //| Handouts.Posix.SEQ}
+
+  implicit def stringOps(s: String) = new {
+    def |(r: Rexp) = ALT(s, r)
+    def |(r: String) = ALT(s, r)
+    def % = STAR(s)
+    def ~(r: Rexp) = SEQ(s, r)
+    def ~(r: String) = SEQ(s, r)
+    def $(r: Rexp) = RECD(s, r)
+  }                                               //> stringOps: (s: String)AnyRef{def |(r: Handouts.Posix.Rexp): Handouts.Posix.
+                                                  //| ALT; def |(r: String): Handouts.Posix.ALT; def %: Handouts.Posix.STAR; def 
+                                                  //| ~(r: Handouts.Posix.Rexp): Handouts.Posix.SEQ; def ~(r: String): Handouts.P
+                                                  //| osix.SEQ; def $(r: Handouts.Posix.Rexp): Handouts.Posix.RECD}
+
+  // size of a regular expressions - for testing purposes
+  def size(r: Rexp): Int = r match {
+    case NULL => 1
+    case EMPTY => 1
+    case CHAR(_) => 1
+    case ALT(r1, r2) => 1 + size(r1) + size(r2)
+    case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+    case STAR(r) => 1 + size(r)
+    case RECD(_, r) => 1 + size(r)
+  }                                               //> size: (r: Handouts.Posix.Rexp)Int
+
+  // nullable function: tests whether the regular
+  // expression can recognise the empty string
+  def nullable(r: Rexp): Boolean = r match {
+    case NULL => false
+    case EMPTY => true
+    case CHAR(_) => false
+    case ALT(r1, r2) => nullable(r1) || nullable(r2)
+    case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+    case STAR(_) => true
+    case RECD(_, r1) => nullable(r1)
+  }                                               //> nullable: (r: Handouts.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
+    case EMPTY => NULL
+    case CHAR(d) => if (c == d) EMPTY else NULL
+    case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
+    case SEQ(r1, r2) =>
+      if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
+      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: Handouts.Posix.Rexp)Handouts.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: Handouts.Posix.Rexp)Handouts.Posix.Rexp
+
+  // extracts a string from value
+  def flatten(v: Val): String = v match {
+    case Void => ""
+    case Chr(c) => c.toString
+    case Left(v) => flatten(v)
+    case Right(v) => flatten(v)
+    case Sequ(v1, v2) => flatten(v1) + flatten(v2)
+    case Stars(vs) => vs.map(flatten).mkString
+    case Rec(_, v) => flatten(v)
+  }                                               //> flatten: (v: Handouts.Posix.Val)String
+
+  // extracts an environment from a value
+  def env(v: Val): List[(String, String)] = v match {
+    case Void => Nil
+    case Chr(c) => Nil
+    case Left(v) => env(v)
+    case Right(v) => env(v)
+    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: Handouts.Posix.Val)List[(String, String)]
+
+  def mkeps(r: Rexp): Val = r match {
+    case EMPTY => Void
+    case ALT(r1, r2) =>
+      if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+    case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+    case STAR(r) => Stars(Nil)
+    case RECD(x, r) => Rec(x, mkeps(r))
+  }                                               //> mkeps: (r: Handouts.Posix.Rexp)Handouts.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)
+    case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+    case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+    case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+    case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+    case (CHAR(d), Void) => Chr(d)
+    case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+  }                                               //> inj: (r: Handouts.Posix.Rexp, c: Char, v: Handouts.Posix.Val)Handouts.Posix
+                                                  //| .Val
+
+  // 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: Handouts.Posix.Rexp, s: List[Char])Handouts.Posix.Val
+
+  def lexing(r: Rexp, s: String): Val = lex(r, s.toList)
+                                                  //> lexing: (r: Handouts.Posix.Rexp, s: String)Handouts.Posix.Val
+
+  val r = (("1" $ "a") | (("2" $ "b") | ("3" $ "ab"))).%
+                                                  //> r  : Handouts.Posix.STAR = STAR(ALT(RECD(1,CHAR(a)),ALT(RECD(2,CHAR(b)),REC
+                                                  //| D(3,SEQ(CHAR(a),CHAR(b))))))
+  env(lexing(r, "ba"))                            //> res0: List[(String, String)] = List((2,b), (1,a))
+
+  val r1 = "a" | "b"                              //> r1  : Handouts.Posix.ALT = ALT(CHAR(a),CHAR(b))
+  lexing(r1, "a")                                 //> res1: Handouts.Posix.Val = Left(Chr(a))
+
+  // Lexing Rules for a Small While Language
+
+  def PLUS(r: Rexp) = r ~ r.%                     //> PLUS: (r: Handouts.Posix.Rexp)Handouts.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  : Handouts.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)),CH
+                                                  //| AR(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  : Handouts.Posix.ALT = 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))
+  val ID = SYM ~ (SYM | DIGIT).%                  //> ID  : Handouts.Posix.SEQ = SEQ(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)),CH
+                                                  //| AR(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))
+                                                  //| ,CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CHAR(y)),CHAR(z)),STAR(ALT(AL
+                                                  //| T(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A
+                                                  //| LT(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)),CH
+                                                  //| AR(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),
+                                                  //| CHAR(1)),CHAR(2)),CHAR(3)),CHAR(4)),CHAR(5)),CHAR(6)),CHAR(7)),CHAR(8)),CHA
+                                                  //| R(9)))))
+  val NUM = PLUS(DIGIT)                           //> NUM  : Handouts.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)),CH
+                                                  //| AR(9)),STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(CHAR(0),CHAR(1)),CHAR(2)),C
+                                                  //| HAR(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  : Handouts.Posix.Rexp = ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CH
+                                                  //| AR(s),SEQ(CHAR(k),SEQ(CHAR(i),CHAR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i
+                                                  //| ),SEQ(CHAR(l),CHAR(e)))))),SEQ(CHAR(d),CHAR(o))),SEQ(CHAR(i),CHAR(f))),SEQ(
+                                                  //| CHAR(t),SEQ(CHAR(h),SEQ(CHAR(e),CHAR(n))))),SEQ(CHAR(e),SEQ(CHAR(l),SEQ(CHA
+                                                  //| R(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),
+                                                  //| SEQ(CHAR(u),CHAR(e))))),SEQ(CHAR(f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHA
+                                                  //| R(e))))))
+  val SEMI: Rexp = ";"                            //> SEMI  : Handouts.Posix.Rexp = CHAR(;)
+  val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"
+                                                  //> OP  : Handouts.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(/))
+  val WHITESPACE = PLUS(" " | "\n" | "\t")        //> WHITESPACE  : Handouts.Posix.SEQ = SEQ(ALT(ALT(CHAR( ),CHAR(
+                                                  //| )),CHAR(	)),STAR(ALT(ALT(CHAR( ),CHAR(
+                                                  //| )),CHAR(	))))
+  val RPAREN: Rexp = ")"                          //> RPAREN  : Handouts.Posix.Rexp = CHAR())
+  val LPAREN: Rexp = "("                          //> LPAREN  : Handouts.Posix.Rexp = CHAR(()
+  val BEGIN: Rexp = "{"                           //> BEGIN  : Handouts.Posix.Rexp = CHAR({)
+  val END: Rexp = "}"                             //> END  : Handouts.Posix.Rexp = CHAR(})
+
+  /*
+ * val WHILE_REGS = (("k" $ KEYWORD) |
+                  ("i" $ ID) |
+                  ("o" $ OP) |
+                  ("n" $ NUM) |
+                  ("s" $ SEMI) |
+                  ("p" $ (LPAREN | RPAREN)) |
+                  ("b" $ (BEGIN | END)) |
+                  ("w" $ WHITESPACE)).%
+*/
+
+  val WHILE_REGS = (KEYWORD |
+    ID |
+    OP |
+    NUM |
+    SEMI |
+    LPAREN | RPAREN |
+    BEGIN | END |
+    WHITESPACE).%                                 //> WHILE_REGS  : Handouts.Posix.STAR = STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(AL
+                                                  //| T(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHAR(s),SEQ(CHAR(k),SEQ(CHAR(i),C
+                                                  //| HAR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i),SEQ(CHAR(l),CHAR(e)))))),SEQ(
+                                                  //| CHAR(d),CHAR(o))),SEQ(CHAR(i),CHAR(f))),SEQ(CHAR(t),SEQ(CHAR(h),SEQ(CHAR(e)
+                                                  //| ,CHAR(n))))),SEQ(CHAR(e),SEQ(CHAR(l),SEQ(CHAR(s),CHAR(e))))),SEQ(CHAR(r),SE
+                                                  //| Q(CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w),SEQ(CHAR(r),SEQ(CHAR(i),SEQ(C
+                                                  //| HAR(t),CHAR(e)))))),SEQ(CHAR(t),SEQ(CHAR(r),SEQ(CHAR(u),CHAR(e))))),SEQ(CHA
+                                                  //| R(f),SEQ(CHAR(a),SEQ(CHAR(l),SEQ(CHAR(s),CHAR(e)))))),SEQ(ALT(ALT(ALT(ALT(A
+                                                  //| LT(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)),CHAR(t)),CHAR(u)),CHAR(v)),CHAR(w)),CHAR(x)),CH
+                                                  //| AR(y)),CHAR(z)),STAR(AL
+                                                  //| 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
+
+  val abc = List('a', 'b', 'c')                   //> abc  : List[Char] = List(a, b, c)
+  val nullRexp = null                             //> nullRexp  : Null = null
+  val myRexp = charlist2rexp(abc)                 //> myRexp  : Handouts.Posix.Rexp = SEQ(CHAR(a),SEQ(CHAR(b),CHAR(c)))
+  val myRexp2 = string2rexp("FahadAusaf")         //> myRexp2  : Handouts.Posix.Rexp = SEQ(CHAR(F),SEQ(CHAR(a),SEQ(CHAR(h),SEQ(CH
+                                                  //| AR(a),SEQ(CHAR(d),SEQ(CHAR(A),SEQ(CHAR(u),SEQ(CHAR(s),SEQ(CHAR(a),CHAR(f)))
+                                                  //| )))))))
+
+  RexpOps(myRexp2)                                //> res2: AnyRef{def |(s: Handouts.Posix.Rexp): Handouts.Posix.ALT; def %: Hand
+                                                  //| outs.Posix.STAR; def ~(s: Handouts.Posix.Rexp): Handouts.Posix.SEQ} = Hando
+                                                  //| uts.Posix$$anonfun$main$1$$anon$1@6ee3572b
+
+  stringOps("Fahad")                              //> res3: AnyRef{def |(r: Handouts.Posix.Rexp): Handouts.Posix.ALT; def |(r: St
+                                                  //| ring): Handouts.Posix.ALT; def %: Handouts.Posix.STAR; def ~(r: Handouts.Po
+                                                  //| six.Rexp): Handouts.Posix.SEQ; def ~(r: String): Handouts.Posix.SEQ; def $(
+                                                  //| r: Handouts.Posix.Rexp): Handouts.Posix.RECD} = Handouts.Posix$$anonfun$mai
+                                                  //| n$1$$anon$2@f7000ed
+
+  size(myRexp2)                                   //> res4: Int = 19
+  nullable(nullRexp)                              //> scala.MatchError: null
+                                                  //| 	at Handouts.Posix$$anonfun$main$1.nullable$1(Handouts.Posix.scala:58)
+                                                  //| 	at Handouts.Posix$$anonfun$main$1.apply$mcV$sp(Handouts.Posix.scala:200)
+                                                  //| 
+                                                  //| 	at org.scalaide.worksheet.runtime.library.WorksheetSupport$$anonfun$$exe
+                                                  //| cute$1.apply$mcV$sp(WorksheetSupport.scala:76)
+                                                  //| 	at org.scalaide.worksheet.runtime.library.WorksheetSupport$.redirected(W
+                                                  //| orksheetSupport.scala:65)
+                                                  //| 	at org.scalaide.worksheet.runtime.library.WorksheetSupport$.$execute(Wor
+                                                  //| ksheetSupport.scala:75)
+                                                  //| 	at Handouts.Posix$.main(Handouts.Posix.scala:21)
+                                                  //| 	at Handouts.Posix.main(Handouts.Posix.scala)
+
+  val newRexp = der('a', myRexp)
+
+  //this is some crap
+}
\ No newline at end of file