1 

     2 import scala.language.implicitConversions    

     3 import scala.language.reflectiveCalls

     4 import scala.annotation.tailrec   

     5 

     6 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {

     7   case Nil => Nil

     8   case (x::xs) => {

     9     val res = f(x)

    10     if (acc.contains(res)) distinctBy(xs, f, acc)  

    11     else x::distinctBy(xs, f, res::acc)

    12   }

    13 } 

    14 

    15 abstract class Bit

    16 case object Z extends Bit

    17 case object S extends Bit

    18 case class C(c: Char) extends Bit

    19 

    20 

    21 type Bits = List[Bit]

    22 

    23 abstract class Action

    24 case object ST extends Action

    25 case object NST extends Action

    26 case object AL extends Action

    27 

    28 abstract class PartialValue

    29 case object Plhdr extends PartialValue

    30 case object STS extends PartialValue

    31 case object ENDSTS extends PartialValue

    32 case class Ch(c: Char) extends PartialValue

    33 case object Empt extends PartialValue

    34 case object Seque extends PartialValue

    35 case class Posi(i: Int) extends PartialValue

    36 case class RECRD(x: String) extends PartialValue

    37 case object ALTSTART extends  PartialValue

    38 case object ALTEND extends PartialValue

    39 case object RIG extends PartialValue

    40 case object LEF extends PartialValue

    41 

    42 abstract class Rexp 

    43 case object ZERO extends Rexp

    44 case object ONE extends Rexp

    45 case class PRED(f: Char => Boolean) extends Rexp

    46 case class ALTS(rs: List[Rexp]) extends Rexp 

    47 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

    48 case class STAR(r: Rexp) extends Rexp 

    49 case class RECD(x: String, r: Rexp) extends Rexp

    50 

    51 // abbreviations

    52 def CHAR(c: Char) = PRED(_ == c)

    53 def ALT(r1: Rexp, r2: Rexp) = ALTS(List(r1, r2))

    54 def PLUS(r: Rexp) = SEQ(r, STAR(r))

    55 

    56 abstract class ARexp 

    57 case object AZERO extends ARexp

    58 case class AONE(bs: Bits) extends ARexp

    59 case class APRED(bs: Bits, f: Char => Boolean) extends ARexp

    60 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp 

    61 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp 

    62 case class ASTAR(bs: Bits, r: ARexp) extends ARexp 

    63 

    64 

    65 def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2))

    66 

    67 abstract class Val

    68 case object Empty extends Val

    69 case class Chr(c: Char) extends Val

    70 case class Sequ(v1: Val, v2: Val) extends Val

    71 case class Left(v: Val) extends Val

    72 case class Right(v: Val) extends Val

    73 case class Stars(vs: List[Val]) extends Val

    74 case class Rec(x: String, v: Val) extends Val

    75 case class Pos(i: Int, v: Val) extends Val

    76 case object Prd extends Val

    77    

    78 // some convenience for typing in regular expressions

    79 def charlist2rexp(s : List[Char]): Rexp = s match {

    80   case Nil => ONE

    81   case c::Nil => CHAR(c)

    82   case c::s => SEQ(CHAR(c), charlist2rexp(s))

    83 }

    84 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)

    85 

    86 implicit def RexpOps(r: Rexp) = new {

    87   def | (s: Rexp) = ALT(r, s)

    88   def % = STAR(r)

    89   def ~ (s: Rexp) = SEQ(r, s)

    90 }

    91 

    92 implicit def stringOps(s: String) = new {

    93   def | (r: Rexp) = ALT(s, r)

    94   def | (r: String) = ALT(s, r)

    95   def % = STAR(s)

    96   def ~ (r: Rexp) = SEQ(s, r)

    97   def ~ (r: String) = SEQ(s, r)

    98   def $ (r: Rexp) = RECD(s, r)

    99 }

   100 

   101 // translation into ARexps

   102 def fuse(bs: Bits, r: ARexp) : ARexp = r match {

   103   case AZERO => AZERO

   104   case AONE(cs) => AONE(bs ++ cs)

   105   case APRED(cs, f) => APRED(bs ++ cs, f)

   106   case AALTS(cs, rs) => AALTS(bs ++ cs, rs)

   107   case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)

   108   case ASTAR(cs, r) => ASTAR(bs ++ cs, r)

   109 }

   110 

   111 def internalise(r: Rexp) : ARexp = r match {

   112   case ZERO => AZERO

   113   case ONE => AONE(Nil)

   114   case PRED(f) => APRED(Nil, f)

   115   case ALTS(List(r1, r2)) => 

   116     AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2))))

   117   case ALTS(r1::rs) => {

   118      val AALTS(Nil, rs2) = internalise(ALTS(rs))

   119      AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _)))

   120   }

   121   case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2))

   122   case STAR(r) => ASTAR(Nil, internalise(r))

   123   case RECD(x, r) => internalise(r)

   124 }

   125 

   126 internalise(("a" | "ab") ~ ("b" | ""))

   127 val action_stack = scala.collection.mutable.ArrayBuffer.empty[Action]

   128 val next_stack = scala.collection.mutable.ArrayBuffer.empty[Int]

   129 val regx_stack = scala.collection.mutable.ArrayBuffer.empty[Rexp]

   130 val pv_stack = scala.collection.mutable.ArrayBuffer.empty[PartialValue]

   131 var top = 0

   132 //st is the global var stack, made with a linked list?

   133 @tailrec

   134 def decode_stack(sp: Int, bs: Bits): Unit = {

   135 if(action_stack.isEmpty){

   136   return 

   137 }

   138 val action = action_stack.last

   139 action_stack.trimEnd(1)

   140 val r = regx_stack.last

   141 regx_stack.trimEnd(1)

   142 if(action == ST)//we have the rest of the star to finish(ST -> STAR)

   143 {

   144   bs match {

   145     case Z::bs => {//pv -> partial value  Each grid in a stack does not hold a whole value but a partial one.

   146       pv_stack(sp) = ENDSTS

   147       if(next_stack.isEmpty)

   148         return 

   149       val n = next_stack.last

   150       next_stack.trimEnd(1)

   151       decode_stack(n, bs)

   152     }

   153     case S::bs => {

   154       for(i <- 0 to next_stack.length - 1){

   155         next_stack(i) = next_stack(i) + 1

   156       }

   157       next_stack += (sp + 1)

   158       regx_stack += r  

   159       action_stack += ST

   160       pv_stack.insert(sp + 1, Plhdr)

   161       action_stack += NST

   162       regx_stack += r 

   163       decode_stack(sp, bs)

   164     }

   165     case _ => println("Sequence not decodable")

   166   }

   167 

   168 }

   169 else if(action == NST){

   170   (r, bs) match{

   171     case (ONE, bs) => {

   172       pv_stack(sp) = Empt

   173       if(next_stack.isEmpty)

   174         return 

   175       val n = next_stack.last

   176       next_stack.trimEnd(1)

   177       decode_stack(n, bs)

   178     }

   179     case (PRED(f), C(c)::bs) => {

   180       pv_stack(sp) = Ch(c)

   181       if(next_stack.isEmpty)

   182         return 

   183       val n = next_stack.last

   184       next_stack.trimEnd(1)

   185       decode_stack(n, bs)

   186     }

   187     case (ALTS(rs), Z::bs1) => {

   188       pv_stack(sp) = ALTSTART

   189       pv_stack.insert(sp + 1, LEF)

   190       pv_stack.insert(sp + 2, Plhdr)

   191       pv_stack.insert(sp + 3, ALTEND)

   192       for(i <- 0 to next_stack.length - 1){

   193         next_stack(i) = next_stack(i) + 3

   194       }

   195       regx_stack += rs.head

   196       action_stack += NST

   197       decode_stack(sp + 2, bs1)

   198     }

   199     case (ALTS(rs), S::bs1) => {

   200       pv_stack(sp) = ALTSTART

   201       pv_stack.insert(sp + 1, RIG)

   202       pv_stack.insert(sp + 2, Plhdr)

   203       for(i <- 0 to next_stack.length - 1){

   204         next_stack(i) = next_stack(i) + 2

   205       }

   206       regx_stack += ALTS(rs.tail)

   207       action_stack += AL

   208       decode_stack(sp + 2, bs1)		

   209     }

   210       /*

   211       val le = rs.length

   212       val det = bs.take(le - 1)

   213       val chosen =  det.indexWhere(_ == Z)

   214       action_stack += NST

   215       pv_stack.insert(sp + 1, Plhdr)

   216       for(i <- 0 to next_stack.length - 1){

   217         next_stack(i) = next_stack(i) + 1

   218       }

   219       if(chosen ==  -1){

   220         pv_stack(sp) = Posi(le)

   221         regx_stack += rs(le - 1)

   222         decode_stack(sp + 1, bs.drop(le - 1))

   223       }

   224       else{

   225         pv_stack(sp) = Posi(chosen + 1)

   226         regx_stack += rs(chosen)

   227         decode_stack(sp + 1, bs.drop(chosen + 1))

   228       }*/

   229     case (SEQ(r1, r2), bs) => {

   230       action_stack += NST

   231       action_stack += NST

   232       for(i <- 0 to next_stack.length - 1){

   233         next_stack(i) = next_stack(i) + 2

   234       }

   235       next_stack += (sp + 2)

   236       regx_stack += r2

   237       regx_stack += r1

   238       pv_stack.insert(sp + 1, Plhdr)

   239       pv_stack.insert(sp + 2, Plhdr)

   240       pv_stack(sp) = Seque

   241       decode_stack(sp + 1, bs)

   242     }

   243     case (STAR(r1), S::bs) => {

   244       action_stack += ST

   245       regx_stack += r1

   246       action_stack += NST

   247       regx_stack += r1

   248       for(i <- 0 to next_stack.length - 1){

   249         next_stack(i) = next_stack(i) + 2

   250       }

   251       next_stack += sp + 2

   252       pv_stack(sp) = STS

   253       pv_stack.insert(sp + 1, Plhdr)

   254       pv_stack.insert(sp + 1, Plhdr)

   255       decode_stack(sp + 1, bs)

   256     }

   257     case (STAR(_), Z::bs) => {

   258       pv_stack(sp) = STS 

   259       pv_stack.insert(sp + 1, ENDSTS)

   260       if(next_stack.isEmpty)

   261         return 

   262       for(i <- 0 to next_stack.length - 1){

   263         next_stack(i) = next_stack(i) + 1

   264       }

   265       val n = next_stack.last

   266       next_stack.trimEnd(1)

   267       decode_stack(n, bs)

   268     }

   269     case (RECD(x, r1), bs) => {

   270       pv_stack(sp) = RECRD(x)

   271       pv_stack.insert(sp + 1, Plhdr)

   272       for(i <- 0 to next_stack.length - 1){

   273         next_stack(i) = next_stack(i) + 1

   274       }

   275       action_stack += NST

   276       regx_stack += r1

   277       decode_stack(sp + 1, bs)

   278     }//shouldn't go beyond this point

   279     case (_, _) => println("Error with NST")

   280   }

   281 }

   282 else{//action is AL

   283   r match {

   284     case (ALTS(r1::Nil)) => {

   285       pv_stack.insert(sp + 1, ALTEND)

   286       for(i <- 0 to next_stack.length - 1){

   287         next_stack(i) = next_stack(i) + 1

   288       }

   289       action_stack += NST

   290       regx_stack += r1

   291       decode_stack(sp, bs)

   292     }

   293     case (ALTS(rs)) => {

   294       bs match {

   295         case (Z::bs1) => {

   296           pv_stack(sp) = LEF

   297           pv_stack.insert(sp + 1, ALTEND)

   298           pv_stack.insert(sp + 1, Plhdr)

   299           for(i <- 0 to next_stack.length - 1){

   300             next_stack(i) = next_stack(i) + 2

   301           }

   302           regx_stack += rs.head

   303           action_stack += NST

   304           decode_stack(sp + 1, bs1)

   305         }

   306         case (S::bs2) => {

   307           pv_stack(sp) = RIG

   308           pv_stack.insert(sp + 1, Plhdr)

   309           for(i <- 0 to next_stack.length - 1){

   310             next_stack(i) = next_stack(i) + 1

   311           }

   312           regx_stack += ALTS(rs.tail)

   313           action_stack += AL

   314           decode_stack(sp + 1, bs2)

   315         }

   316         case _ => println("Not decodable")

   317       }

   318     }

   319     case (rs) => println(r,bs)

   320   }

   321 }

   322 }

   323 //advantage: may decode chunks of bits

   324 def decode(r: Rexp, bs: Bits) = {

   325   action_stack.clear()

   326   next_stack.clear()

   327   regx_stack.clear()

   328   pv_stack.clear()

   329 

   330   action_stack += NST

   331   regx_stack += r

   332   pv_stack += Plhdr

   333 

   334   decode_stack(0, bs)

   335 }

   336 /*

   337 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {

   338   case (v, Nil) => v

   339   case _ => throw new Exception("Not decodable")

   340 }

   341 */

   342 

   343 //erase function: extracts the regx from Aregex

   344 def erase(r:ARexp): Rexp = r match{

   345   case AZERO => ZERO

   346   case AONE(_) => ONE

   347   case APRED(bs, f) => PRED(f)

   348   case AALTS(bs, rs) => ALTS(rs.map(erase(_)))

   349   case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2))

   350   case ASTAR(cs, r)=> STAR(erase(r))

   351 }

   352 

   353 // nullable function: tests whether the aregular 

   354 // expression can recognise the empty string

   355 def nullable (r: ARexp) : Boolean = r match {

   356   case AZERO => false

   357   case AONE(_) => true

   358   case APRED(_,_) => false

   359   case AALTS(_, rs) => rs.exists(nullable)

   360   case ASEQ(_, r1, r2) => nullable(r1) && nullable(r2)

   361   case ASTAR(_, _) => true

   362 }

   363 

   364 def mkepsBC(r: ARexp) : Bits = r match {

   365   case AONE(bs) => bs

   366   case AALTS(bs, rs) => {

   367     val n = rs.indexWhere(nullable)

   368     bs ++ mkepsBC(rs(n))

   369   }

   370   case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)

   371   case ASTAR(bs, r) => bs ++ List(Z)

   372 }

   373 

   374 // derivative of a regular expression w.r.t. a character

   375 def der(c: Char, r: ARexp) : ARexp = r match {

   376   case AZERO => AZERO

   377   case AONE(_) => AZERO

   378   case APRED(bs, f) => if (f(c)) AONE(bs:::List(C(c))) else AZERO

   379   case AALTS(bs, rs) => AALTS(bs, rs.map(der(c, _)))

   380   case ASEQ(bs, r1, r2) => 

   381     if (nullable(r1)) AALT(bs, ASEQ(Nil, der(c, r1), r2), fuse(mkepsBC(r1), der(c, r2)))

   382     else ASEQ(bs, der(c, r1), r2)

   383   case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), der(c, r)), ASTAR(Nil, r))

   384 }

   385 

   386 // derivative w.r.t. a string (iterates der)

   387 @tailrec

   388 def ders (s: List[Char], r: ARexp) : ARexp = s match {

   389   case Nil => r

   390   case c::s => ders(s, der(c, r))

   391 }

   392 

   393 // main unsimplified lexing function (produces a value)

   394 def lex(r: ARexp, s: List[Char]) : Bits = s match {

   395   case Nil => if (nullable(r)) mkepsBC(r) else throw new Exception("Not matched")

   396   case c::cs => lex(der(c, r), cs)

   397 }

   398 

   399 def pre_lexing(r: Rexp, s: String) = lex(internalise(r), s.toList)

   400 //def lexing(r: Rexp, s: String) : Val = decode(r, lex(internalise(r), s.toList))

   401 

   402 

   403 def flats(rs: List[ARexp]): List[ARexp] = rs match {

   404     case Nil => Nil

   405     case AZERO :: rs1 => flats(rs1)

   406     case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)

   407     case r1 :: rs2 => r1 :: flats(rs2)

   408   }

   409 

   410 def simp(r: ARexp): ARexp = r match {

   411   case ASEQ(bs1, r1, r2) => (simp(r1), simp(r2)) match {

   412       case (AZERO, _) => AZERO

   413       case (_, AZERO) => AZERO

   414       case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)

   415       case (r1s, r2s) => ASEQ(bs1, r1s, r2s)

   416   }

   417   case AALTS(bs1, rs) => distinctBy(flats(rs.map(simp)), erase) match {

   418     case Nil => AZERO

   419     case s :: Nil => fuse(bs1, s)

   420     case rs => AALTS(bs1, rs)  

   421   }

   422   case r => r

   423 }

   424 

   425 def ders_simp (s: List[Char], r: ARexp) : ARexp = s match {

   426   case Nil => r

   427   case c::s => ders_simp(s, simp(der(c, r)))

   428 }

   429 

   430 def lex_simp(r: ARexp, s: List[Char]) : Bits = s match {

   431   case Nil => {

   432     if (nullable(r)) {

   433       //println(asize(r))

   434       mkepsBC(r)

   435     }

   436    else throw new Exception("Not matched")

   437   }

   438   case c::cs => lex_simp(simp(der(c, r)), cs)

   439 }

   440 

   441 //size: of a Aregx for testing purposes 

   442 def size(r: Rexp) : Int = r match {

   443   case ZERO => 1

   444   case ONE => 1

   445   case PRED(_) => 1

   446   case SEQ(r1, r2) => 1 + size(r1) + size(r2)

   447   case ALTS(rs) => 1 + rs.map(size).sum

   448   case STAR(r) => 1 + size(r)

   449 }

   450 

   451 def asize(a: ARexp) = size(erase(a))

   452 

   453 

   454 // decoding does not work yet

   455 def lexing_simp(r: Rexp, s: String) = {

   456   val final_derivative = lex_simp(internalise(r), s.toList)

   457   println("The length of bit sequence:")

   458   println((final_derivative.length))

   459   //println(final_derivative)

   460   decode(r, final_derivative) 

   461   //println(vsize(value))

   462 }

   463 

   464 

   465 def vsize(v: Val): Int = v match {

   466   case Empty => 1

   467   case Chr(c) => 1

   468   case Sequ(v1, v2) => vsize(v1) + vsize(v2) + 1

   469   case Left(v1) => vsize(v1) + 1

   470   case Right(v1) => vsize(v1) + 1

   471   case Stars(vs) => vs.map(vsize(_)).sum + 1

   472   case Rec(x, v1) => vsize(v1) + 1

   473   case Pos(i, v1) => vsize(v1) + 1

   474   case Prd => 1

   475 }

   476 

   477 

   478 // Lexing Rules for a Small While Language

   479 

   480 //symbols

   481 val SYM = PRED("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".contains(_))

   482 //digits

   483 val DIGIT = PRED("0123456789".contains(_))

   484 //identifiers

   485 val ID = SYM ~ (SYM | DIGIT).% 

   486 //numbers

   487 val NUM = PLUS(DIGIT)

   488 //keywords

   489 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false"

   490 //semicolons

   491 val SEMI: Rexp = ";"

   492 //operators

   493 val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/"

   494 //whitespaces

   495 val WHITESPACE = PLUS(" " | "\n" | "\t")

   496 //parentheses

   497 val RPAREN: Rexp = ")"

   498 val LPAREN: Rexp = "("

   499 val BEGIN: Rexp = "{"

   500 val END: Rexp = "}"

   501 //strings...but probably needs not

   502 val STRING: Rexp = "\"" ~ SYM.% ~ "\""

   503 

   504 

   505 

   506 val WHILE_REGS = (("k" $ KEYWORD) | 

   507                   ("i" $ ID) | 

   508                   ("o" $ OP) | 

   509                   ("n" $ NUM) | 

   510                   ("s" $ SEMI) | 

   511                   ("str" $ STRING) |

   512                   ("p" $ (LPAREN | RPAREN)) | 

   513                   ("b" $ (BEGIN | END)) | 

   514                   ("w" $ WHITESPACE)).%

   515 

   516 // filters out all white spaces

   517 //def tokenise(r: Rexp, s: String) = 

   518 //  env(lexing_simp(r, s)).filterNot { _._1 == "w"}

   519 

   520 

   521 //reads the string from a file 

   522 //def fromFile(name: String) : String = 

   523 //  io.Source.fromFile(name).mkString

   524 

   525 //def tokenise_file(r: Rexp, name: String) = 

   526 //  tokenise(r, fromFile(name))

   527  

   528 

   529 // Some Tests

   530 //============

   531 def compute_and_print(r: Rexp, s: String){

   532   //println(r)

   533   //println(s)

   534   lexing_simp(r, s)

   535   println(pv_stack)

   536 }

   537 println("simple tests:")

   538 /*

   539 println(lexing_simp((SYM.%), "abcd"))

   540 println(lexing_simp(((SYM.%) | NUM), "12345"))

   541 println(lexing_simp((WHILE_REGS), "abcd"))

   542 println(lexing_simp((WHILE_REGS), "12345"))

   543 println(lexing_simp((WHILE_REGS), "\nwrite \"Fib\";"))

   544 */

   545 compute_and_print((SYM.%), "abcd")

   546 compute_and_print(((SYM.%) | NUM), "12345")

   547 compute_and_print((WHILE_REGS), "abcd")

   548 compute_and_print((WHILE_REGS), "12345")

   549 compute_and_print((WHILE_REGS), "\nwrite \"Fib\";")

   550 

   551 def time[T](code: => T) = {

   552   val start = System.nanoTime()

   553   val result = code

   554   val end = System.nanoTime()

   555   println((end - start)/1.0e9)

   556   result

   557 }

   558 

   559 val prog2 = """

   560 write "Fib";

   561 read n;

   562 minus1 := 0;

   563 minus2 := 1;

   564 while n > 0 do {

   565   temp := minus2;

   566   minus2 := minus1 + minus2;

   567   minus1 := temp;

   568   n := n -x 1

   569 };

   570 write "Result";

   571 write minus2

   572 """

   573 /*

   574 

   575 val prog2 = """

   576 write "Fib";

   577 """

   578 

   579 */

   580 

   581 println("Iteration test with fib")

   582 for (i <- 900 to 1000 by 50) {

   583   print(i.toString + ":  ")

   584   time(lexing_simp((WHILE_REGS), (prog2 * i)))

   585   //time(lex_simp(internalise(WHILE_REGS), (prog2 * i).toList))

   586 }

   587 

   588 

   589 /*

   590 def recurseTest(i:Int):Unit={

   591    try{

   592       recurseTest(i+1)

   593    } catch { case e:java.lang.StackOverflowError => 

   594       println("Recursion depth on this system is " + i + ".")

   595    }

   596 }

   597 recurseTest(0)

   598 */