1 trait RegExp {

     2   def nullable: Boolean

     3   def derive(c: Char): RegExp

     4 }

     5 

     6 case object Empty extends RegExp {

     7   def nullable = false

     8   def derive(c: Char) = Empty

     9 }

    10 

    11 case object Eps extends RegExp {

    12   def nullable = true

    13   def derive(c: Char) = Empty

    14 }

    15 

    16 case class Str(s: String) extends RegExp {

    17   def nullable = s.isEmpty

    18   def derive(c: Char) =

    19     if (s.isEmpty || s.head != c) Empty

    20     else Str(s.tail)

    21 }

    22 

    23 case class Cat(r: RegExp, s: RegExp) extends RegExp {

    24   def nullable = r.nullable && s.nullable

    25   def derive(c: Char) =

    26     if (r.nullable) Or(Cat(r.derive(c), s), s.derive(c)) 

    27     else Cat(r.derive(c), s)

    28 }

    29 

    30 case class Star(r: RegExp) extends RegExp {

    31   def nullable = true

    32   def derive(c: Char) = Cat(r.derive(c), this)

    33 }

    34 

    35 case class Or(r: RegExp, s: RegExp) extends RegExp {

    36   def nullable = r.nullable || s.nullable

    37   def derive(c: Char) = Or(r.derive(c), s.derive(c))

    38 }

    39 

    40 case class And(r: RegExp, s: RegExp) extends RegExp {

    41   def nullable = r.nullable && s.nullable

    42   def derive(c: Char) = And(r.derive(c), s.derive(c))

    43 }

    44 

    45 case class Not(r: RegExp) extends RegExp {

    46   def nullable = !r.nullable

    47   def derive(c: Char) = Not(r.derive(c))

    48 }

    49 

    50 

    51 

    52 

    53 object Matcher {

    54   def matches(r: RegExp, s: String): Boolean = {

    55     if (s.isEmpty) r.nullable

    56     else matches(r.derive(s.head), s.tail)

    57   }

    58 }

    59 

    60 

    61 object Pimps {

    62   implicit def string2RegExp(s: String) = Str(s)

    63 

    64   implicit def regExpOps(r: RegExp) = new {

    65     def | (s: RegExp) = Or(r, s)

    66     def & (s: RegExp) = And(r, s)

    67     def % = Star(r)

    68     def %(n: Int) = rep(r, n)

    69     def ? = Or(Eps, r)

    70     def ! = Not(r)

    71     def ++ (s: RegExp) = Cat(r, s)

    72     def ~ (s: String) = Matcher.matches(r, s)

    73   }

    74 

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

    76     def | (r: RegExp) = Or(s, r)

    77     def | (r: String) = Or(s, r)

    78     def & (r: RegExp) = And(s, r)

    79     def & (r: String) = And(s, r)

    80     def % = Star(s)

    81     def % (n: Int) = rep(Str(s), n)

    82     def ? = Or(Eps, s)

    83     def ! = Not(s)

    84     def ++ (r: RegExp) = Cat(s, r)

    85     def ++ (r: String) = Cat(s, r)

    86     def ~ (t: String) = Matcher.matches(s, t)

    87   }

    88 

    89   def rep(r: RegExp, n: Int): RegExp =

    90     if (n <= 0) Star(r)

    91     else Cat(r, rep(r, n - 1))

    92 }

    93 

    94 

    95 object Test {

    96   import Pimps._

    97 

    98   val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

    99   val int = ("+" | "-").? ++ digit.%(1)

   100   val real = ("+" | "-").? ++ digit.%(1) ++ ("." ++ digit.%(1)).? ++ (("e" | "E") ++ ("+" | "-").? ++ digit.%(1)).?

   101 

   102   def main(args: Array[String]) {

   103     val ints = List("0", "-4534", "+049", "99")

   104     val reals = List("0.9", "-12.8", "+91.0", "9e12", "+9.21E-12", "-512E+01")

   105     val errs = List("", "-", "+", "+-1", "-+2", "2-")

   106 

   107     ints.foreach(s => assert(int ~ s))

   108     reals.foreach(s => assert(!(int ~ s)))

   109     errs.foreach(s => assert(!(int ~ s)))

   110 

   111     ints.foreach(s => assert(real ~ s))

   112     reals.foreach(s => assert(real ~ s))

   113     errs.foreach(s => assert(!(real ~ s)))

   114   }

   115 }