1 :load matcher.scala

     2 

     3 // some regular expressions

     4 val LETTER = RANGE("abcdefghijklmnopqrstuvwxyz".toList)

     5 val ID = PLUS(LETTER)

     6 

     7 val DIGIT = RANGE("0123456789".toList)

     8 val NONZERODIGIT = RANGE("123456789".toList)

     9 val NUMBER = ALT(SEQ(NONZERODIGIT, STAR(DIGIT)), "0")

    10 

    11 val LPAREN = CHAR('(')

    12 val RPAREN = CHAR(')')

    13 

    14 val WHITESPACE = PLUS(RANGE(" \n".toList))

    15 val OPS = RANGE("+-*".toList)

    16 

    17 // for classifying the strings that have been recognised

    18 abstract class Token

    19 

    20 case object T_WHITESPACE extends Token

    21 case class T_NUM(s: String) extends Token

    22 case class T_ID(s: String) extends Token

    23 case class T_OP(s: String) extends Token

    24 case object T_LPAREN extends Token

    25 case object T_RPAREN extends Token

    26 case object T_IF extends Token

    27 case object T_THEN extends Token

    28 case object T_ELSE extends Token

    29 

    30 def tokenizer(rs: List[Rule[Token]], s: String) : List[Token] = 

    31   tokenize(rs, s.toList).filterNot(_ match {

    32     case T_WHITESPACE => true

    33     case _ => false

    34   })

    35 

    36 

    37 // lexing rules for arithmetic expressions

    38 val lexing_rules: List[Rule[Token]]= 

    39   List(("if", (s) => T_IF),

    40        ("then", (s) => T_THEN),

    41        ("else", (s) => T_ELSE),

    42        (NUMBER, (s) => T_NUM(s.mkString)),

    43        (ID, (s) => T_ID(s.mkString)),

    44        (WHITESPACE, (s) => T_WHITESPACE),

    45        (LPAREN, (s) => T_LPAREN),

    46        (RPAREN, (s) => T_RPAREN),

    47        (OPS, (s) => T_OP(s.mkString)))

    48 

    49 

    50 // parser combinators with return type T

    51 abstract class Parser[T] {

    52   def parse(ts: List[Token]): Set[(T, List[Token])]

    53 

    54   def parse_all(ts: List[Token]) : Set[T] =

    55     for ((head, tail) <- parse(ts); if (tail == Nil)) yield head

    56 

    57   def || (right : => Parser[T]) : Parser[T] = new AltParser(this, right)

    58   def ==>[S] (f: => T => S) : Parser [S] = new FunParser(this, f)

    59   def ~[S] (right : => Parser[S]) : Parser[(T, S)] = new SeqParser(this, right)

    60   def ~>[S] (right : => Parser[S]) : Parser[S] = this ~ right ==> (x => x._2)

    61   def <~[S] (right : => Parser[S]) : Parser[T] = this ~ right ==> (x => x._1)

    62 

    63 }

    64 

    65 class SeqParser[T, S](p: => Parser[T], q: => Parser[S]) extends Parser[(T, S)] {

    66   def parse(sb: List[Token]) = 

    67     for ((head1, tail1) <- p.parse(sb); 

    68          (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)

    69 }

    70 

    71 class AltParser[T](p: => Parser[T], q: => Parser[T]) extends Parser[T] {

    72   def parse (sb: List[Token]) = p.parse(sb) ++ q.parse(sb)   

    73 }

    74 

    75 class FunParser[T, S](p: => Parser[T], f: T => S) extends Parser[S] {

    76   def parse (sb: List[Token]) = 

    77     for ((head, tail) <- p.parse(sb)) yield (f(head), tail)

    78 }

    79 

    80 

    81 case class TokParser(tok: Token) extends Parser[Token] {

    82   def parse(ts: List[Token]) = ts match {

    83     case t::ts if (t == tok) => Set((t, ts)) 

    84     case _ => Set ()

    85   }

    86 }

    87 

    88 implicit def token2tparser(t: Token) = TokParser(t)

    89 

    90 case object NumParser extends Parser[Int] {

    91   def parse(ts: List[Token]) = ts match {

    92     case T_NUM(s)::ts => Set((s.toInt, ts)) 

    93     case _ => Set ()

    94   }

    95 }

    96 

    97 lazy val E: Parser[Int] = (T ~ T_OP("+") ~ E) ==> { case ((x, y), z) => x + z } || T  // start symbol

    98 lazy val T: Parser[Int] = (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => x * z } || F

    99 lazy val F: Parser[Int] = (T_LPAREN ~> E <~ T_RPAREN) || NumParser

   100    

   101 println(E.parse_all(tokenizer(lexing_rules, "1 + 2 + 3")))

   102 println(E.parse_all(tokenizer(lexing_rules, "1 + 2 * 3")))

   103 println(E.parse_all(tokenizer(lexing_rules, "(1 + 2) * 3")))

   104 

   105 println(E.parse_all(tokenizer(lexing_rules, "(1 - 2) * 3")))

   106 println(E.parse_all(tokenizer(lexing_rules, "(1 + 2) * - 3")))