1 val DIGIT = RANGE("0123456789")

     2 val NONZERODIGIT = RANGE("123456789")

     3 

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

     5 val LPAREN = CHAR('(')

     6 val RPAREN = CHAR(')')

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

     8 val OPS = RANGE("+-*")

     9 

    10 // for classifying the strings that have been recognised

    11 abstract class Token

    12 case object T_WHITESPACE extends Token

    13 case class T_NUM(s: String) extends Token

    14 case class T_OP(s: String) extends Token

    15 case object T_LPAREN extends Token

    16 case object T_RPAREN extends Token

    17 

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

    19   List((NUMBER, (s) => T_NUM(s.mkString)),

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

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

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

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

    24 

    25 val Tk = Tokenizer(lexing_rules, List(T_WHITESPACE))

    26 

    27 

    28 // parser combinators with input type I and return type T

    29 // and memoisation

    30 

    31 case class SubList[T](s: List[T], l: Int, h: Int) {

    32   def low = l

    33   def high = h

    34   def length = h - l

    35   def sublist(l: Int = l, h: Int = h) = s.slice(l, h)

    36   def set(low: Int = l, high: Int = h) = SubList(s, low, high)

    37 }

    38 

    39 type Ctxt[T] = List[(String, SubList[T])]

    40 

    41 abstract class Parser[I, T] {

    42 

    43   def parse(ts: SubList[I], ctxt: Ctxt[I]): Set[(T, SubList[I])]

    44 

    45   def parse_all(s: List[I]) : Set[T] =

    46     for ((head, tail) <- parse(SubList(s, 0, s.length), Nil); if (tail.sublist() == Nil)) yield head

    47 

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

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

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

    51   def ~>[S] (right : => Parser[I, S]) : Parser[I, S] = this ~ right ==> (_._2)

    52   def <~[S] (right : => Parser[I, S]) : Parser[I, T] = this ~ right ==> (_._1)

    53 }

    54 

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

    56   def parse(sb: SubList[I], ctxt: Ctxt[I]) = 

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

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

    59 }

    60 

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

    62   def parse(sb: SubList[I], ctxt: Ctxt[I]) = p.parse(sb, ctxt) ++ q.parse(sb, ctxt)   

    63 }

    64 

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

    66   def parse(sb: SubList[I], ctxt: Ctxt[I]) = 

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

    68 }

    69 

    70 case object NumParser extends Parser[Token, Int] {

    71   def parse(sb: SubList[Token], ctxt: Ctxt[Token]) = {

    72     if (0 < sb.length) sb.sublist(sb.low, sb.low + 1) match { 

    73       case T_NUM(i)::Nil => Set((i.toInt, sb.set(low = sb.low + 1))) 

    74       case _ => Set()

    75     }

    76     else Set()

    77   }

    78 }

    79 

    80 case class TokParser(t: Token) extends Parser[Token, Token] {

    81   def parse(sb: SubList[Token], ctxt: Ctxt[Token]) = {

    82     if (0 < sb.length && sb.sublist(sb.low, sb.low + 1) == List(t)) Set((t, sb.set(low = sb.low + 1))) 

    83     else Set()

    84   }

    85 }

    86 

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

    88 

    89 class IgnLst[I, T](p: => Parser[I, T]) extends Parser[I, T] {

    90   def parse(sb: SubList[I], ctxt: Ctxt[I]) = {

    91     if (sb.length == 0) Set()

    92     else for ((head, tail) <- p.parse(sb.set(high = sb.high - 1), ctxt)) 

    93          yield (head, tail.set(high = tail.high + 1))

    94   }

    95 }

    96 

    97 class CHECK[I, T](nt: String, p: => Parser[I, T]) extends Parser[I, T] {

    98   def parse(sb: SubList[I], ctxt: Ctxt[I]) = {

    99     val should_trim = ctxt.contains (nt, sb)

   100     if (should_trim && sb.length == 0) Set()

   101     else if (should_trim) new IgnLst(p).parse(sb, (nt, sb)::ctxt)

   102     else p.parse(sb, (nt, sb)::ctxt)

   103   }

   104 }

   105 

   106 lazy val E: Parser[Token, Int] = 

   107   new CHECK("E", (E ~ T_OP("+") ~ E) ==> { case ((x, y), z) => x + z} || 

   108                  (E ~ T_OP("*") ~ E) ==> { case ((x, y), z) => x * z} ||

   109                  (T_LPAREN ~ E ~ T_RPAREN) ==> { case ((x, y), z) => y} ||

   110                  NumParser)

   111 

   112 println(E.parse_all(Tk.fromString("1 + 2 * 3")))

   113 println(E.parse_all(Tk.fromString("(1 + 2) * 3")))