diff -r 197babb05539 -r 238c98db6057 Fahad/Scala/POSIX.sc --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Fahad/Scala/POSIX.sc Sun Oct 26 11:17:40 2014 +0000 @@ -0,0 +1,254 @@ +package greeter + +object POSIX { + println("Posix Algorithm") //> Posix Algorithm + + 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])greeter.POSIX.Rexp + implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + //> 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} + + 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: 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} + + // 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: greeter.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: 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 + 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: 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 + + // 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: greeter.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: greeter.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: 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) + 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: greeter.POSIX.Rexp, c: Char, v: greeter.POSIX.Val)greeter.POSIX.Va + //| 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 + + def lexing(r: Rexp, s: String): Val = lex(r, s.toList) + //> 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)) + + // Lexing Rules for a Small While Language + + 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)) + 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)) + 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 + //| )),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(ALT + //| (ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(AL + //| T(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)),CHA + //| 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))))) + 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)))) + 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) + //| ,SEQ(CHAR(l),CHAR(e)))))),SEQ(CHAR(d),CHAR(o))),SEQ(CHAR(i),CHAR(f))),SEQ(C + //| HAR(t),SEQ(CHAR(h),SEQ(CHAR(e),CHAR(n))))),SEQ(CHAR(e),SEQ(CHAR(l),SEQ(CHAR + //| (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(;) + 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(/)) + 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(}) + + /* + * 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 : greeter.POSIX.STAR = STAR(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT + //| (ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(SEQ(CHAR(s),SEQ(CHAR(k),SEQ(CHAR(i),CH + //| AR(p)))),SEQ(CHAR(w),SEQ(CHAR(h),SEQ(CHAR(i),SEQ(CHAR(l),CHAR(e)))))),SEQ(C + //| HAR(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),SEQ + //| (CHAR(e),SEQ(CHAR(a),CHAR(d))))),SEQ(CHAR(w),SEQ(CHAR(r),SEQ(CHAR(i),SEQ(CH + //| AR(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),CHAR(e)))))),SEQ(ALT(ALT(ALT(ALT(AL + //| T(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(ALT(A + //| LT(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)),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 + + val prog0 = """read n""" //> prog0 : String = read n + //env(lexing_simp(WHILE_REGS, prog0)) + + println("Next test") //> Next test +} \ No newline at end of file