1 import scala.language.implicitConversions

     2 import scala.language.reflectiveCalls

     3 import scala.util._

     4 import scala.annotation.tailrec

     5 

     6 sealed abstract class Rexp

     7 

     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 

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

    16   case Nil => EMPTY

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

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

    19 }

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

    21 

    22 

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

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

    25   def % = STAR(r)

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

    27 }

    28 

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

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

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

    32   def % = STAR(s)

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

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

    35 }

    36 

    37 def Range(s : List[Char]) : Rexp = s match {

    38   case Nil => NULL

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

    40   case c::s => ALT(CHAR(c), Range(s))

    41 }

    42 def RANGE(s: String) = Range(s.toList)

    43 

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

    45 

    46 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")

    47 val DIGIT = RANGE("0123456789")

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

    49 val NUM = PLUS(DIGIT)

    50 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" 

    51 val SEMI: Rexp = ";"

    52 val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"

    53 val WHITESPACE = PLUS(RANGE(" \n"))

    54 val RPAREN: Rexp = ")"

    55 val LPAREN: Rexp = "("

    56 val BEGIN: Rexp = "{"

    57 val END: Rexp = "}"

    58 

    59 //regular expressions ranked by position in the list

    60 val regs: List[Rexp] = 

    61   List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE)

    62 

    63 def nullable (r: Rexp) : Boolean = r match {

    64   case NULL => false

    65   case EMPTY => true

    66   case CHAR(_) => false

    67   case ALT(r1, r2) => nullable(r1) || nullable(r2)

    68   case SEQ(r1, r2) => nullable(r1) && nullable(r2)

    69   case STAR(_) => true

    70 }

    71 

    72 def zeroable (r: Rexp) : Boolean = r match {

    73   case NULL => true

    74   case EMPTY => false

    75   case CHAR(_) => false

    76   case ALT(r1, r2) => zeroable(r1) && zeroable(r2)

    77   case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)

    78   case STAR(_) => false

    79 }

    80 

    81 def der (c: Char, r: Rexp) : Rexp = r match {

    82   case NULL => NULL

    83   case EMPTY => NULL  

    84   case CHAR(d) => if (c == d) EMPTY else NULL

    85   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

    86   case SEQ(r1, r2) => 

    87     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

    88     else SEQ(der(c, r1), r2)

    89   case STAR(r) => SEQ(der(c, r), STAR(r))

    90 }

    91 

    92 // returns the position of the last Some-element in the list

    93 def last(stack: List[Option[Rexp]]) : Int = stack match {

    94   case Nil => 0

    95   case None::stack => last(stack)

    96   case Some(r)::stack => 1 + stack.length

    97 }

    98 

    99 // calculates derivatives until all of them are zeroable

   100 @tailrec

   101 def munch(cs: List[Char], rs: List[Rexp], stack: List[Option[Rexp]]) : Int = (cs, rs) match {

   102   case (_, Nil) => last(stack)

   103   case (Nil, _) => last(stack)

   104   case (c::cs, rs) => {

   105     val ds = rs.map(der(c, _))

   106     val rs_nzero = ds.filterNot(zeroable(_))

   107     val rs_nulls = ds.filter(nullable(_))

   108     val opt = Try(Some(rs_nulls.head)) getOrElse None

   109     munch(cs, rs_nzero, opt::stack)

   110   }

   111 }

   112 

   113 // iterates the munching function and prints 

   114 // out the component strings

   115 @tailrec

   116 def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, rs, Nil) match {

   117   case 0 if (s == "") => println("EOF")

   118   case 0 => println(s"Lexing error: $s")

   119   case n => {

   120     val (head, tail) = s.splitAt(n)

   121     print(s"|${head.replaceAll("\n","Ret")}|")

   122     tokenize(tail, rs)

   123   }

   124 }

   125 

   126 val test_prog = """

   127 start := XXX;

   128 x := start;

   129 y := start;

   130 z := start;

   131 while 0 < x do {

   132  while 0 < y do {

   133   while 0 < z do {

   134     z := z - 1

   135   };

   136   z := start;

   137   y := y - 1

   138  };     

   139  y := start;

   140  x := x - 1

   141 };

   142 write x;

   143 write y;

   144 write z

   145 """

   146 

   147 tokenize(test_prog, regs)