1 // A simple lexer inspired by work of Sulzmann & Lu

     2 //==================================================

     3 //

     4 

     5 // regular expressions including records

     6 abstract class Rexp 

     7 case object ZERO extends Rexp

     8 case object ONE extends Rexp

     9 case class CHAR(c: Char) extends Rexp

    10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 

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

    12 case class STAR(r: Rexp) extends Rexp 

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

    14                 // records for extracting strings or tokens

    15   

    16 // values  

    17 abstract class Val

    18 case object Empty extends Val

    19 case class Chr(c: Char) extends Val

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

    21 case class Left(v: Val) extends Val

    22 case class Right(v: Val) extends Val

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

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

    25    

    26 // some convenience for typing in regular expressions

    27 

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

    29   case Nil => ONE

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

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

    32 }

    33 implicit def string2rexp(s : String) : Rexp = 

    34   charlist2rexp(s.toList)

    35 

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

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

    38   def % = STAR(r)

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

    40 }

    41 

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

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

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

    45   def % = STAR(s)

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

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

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

    49 }

    50 

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

    52   case ZERO => false

    53   case ONE => true

    54   case CHAR(_) => false

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

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

    57   case STAR(_) => true

    58   case RECD(_, r1) => nullable(r1)

    59 }

    60 

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

    62   case ZERO => ZERO

    63   case ONE => ZERO

    64   case CHAR(d) => if (c == d) ONE else ZERO

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

    66   case SEQ(r1, r2) => 

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

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

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

    70   case RECD(_, r1) => der(c, r1)

    71 }

    72 

    73 

    74 // extracts a string from a value

    75 def flatten(v: Val) : String = v match {

    76   case Empty => ""

    77   case Chr(c) => c.toString

    78   case Left(v) => flatten(v)

    79   case Right(v) => flatten(v)

    80   case Sequ(v1, v2) => flatten(v1) ++ flatten(v2)

    81   case Stars(vs) => vs.map(flatten).mkString

    82   case Rec(_, v) => flatten(v)

    83 }

    84 

    85 

    86 // extracts an environment from a value;

    87 // used for tokenising a string

    88 def env(v: Val) : List[(String, String)] = v match {

    89   case Empty => Nil

    90   case Chr(c) => Nil

    91   case Left(v) => env(v)

    92   case Right(v) => env(v)

    93   case Sequ(v1, v2) => env(v1) ::: env(v2)

    94   case Stars(vs) => vs.flatMap(env)

    95   case Rec(x, v) => (x, flatten(v))::env(v)

    96 }

    97 

    98 

    99 // The injection and mkeps part of the lexer

   100 //===========================================

   101 

   102 def mkeps(r: Rexp) : Val = r match {

   103   case ONE => Empty

   104   case ALT(r1, r2) => 

   105     if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))

   106   case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))

   107   case STAR(r) => Stars(Nil)

   108   case RECD(x, r) => Rec(x, mkeps(r))

   109 }

   110 

   111 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {

   112   case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)

   113   case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)

   114   case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)

   115   case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))

   116   case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))

   117   case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))

   118   case (CHAR(d), Empty) => Chr(c) 

   119   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))

   120 }

   121 

   122 // lexing functions including simplification

   123 def lex(r: Rexp, s: List[Char]) : Val = s match {

   124   case Nil => if (nullable(r)) mkeps(r) else 

   125     { throw new Exception("lexing error") } 

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

   127 }

   128 

   129 def lexing(r: Rexp, s: String) = 

   130   env(lex(r, s.toList))

   131 

   132 

   133 // The Lexing Rules for the WHILE Language

   134 

   135 def PLUS(r: Rexp) = r ~ r.%

   136 

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

   138   case Nil => ZERO

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

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

   141 }

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

   143 

   144 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")

   145 val DIGIT = RANGE("0123456789")

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

   147 val NUM = PLUS(DIGIT)

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

   149 val SEMI: Rexp = ";"

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

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

   152 val RPAREN: Rexp = "{"

   153 val LPAREN: Rexp = "}"

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

   155 

   156 

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

   158                   ("i" $ ID) | 

   159                   ("o" $ OP) | 

   160                   ("n" $ NUM) | 

   161                   ("s" $ SEMI) | 

   162                   ("str" $ STRING) |

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

   164                   ("w" $ WHITESPACE)).%

   165 

   166 val KY : Rexp = "if" | "read" | "write"

   167 val WH : Rexp = " " | "\n"

   168 

   169 val TRIV_REGS = (("k" $ KY) | 

   170                   ("w" $ WHITESPACE)).%

   171 

   172 // Two Simple While Tests

   173 //========================

   174 

   175 @doc("small tests")

   176 @main

   177 def small() = {

   178 

   179   val prog0 = """if"""

   180   println(s"test: $prog0")

   181   println(lexing(WHILE_REGS, prog0))

   182 

   183   val prog1 = """iffoo"""

   184   println(s"test: $prog1")

   185   println(lexing(WHILE_REGS, prog1))

   186 

   187   val prog2 = """read  n; write n"""  

   188   println(s"test: $prog2")

   189   println(lexing(WHILE_REGS, prog2))

   190 }

   191