A demonstration of the CPS coding style

Regex_Parser.scala

object Main {

  class Regex
  case class Literal(s: String) extends Regex
  case class Concat(r1: Regex, r2: Regex) extends Regex
  case class Choice(r1: Regex, r2: Regex) extends Regex
  case class Star(r: Regex) extends Regex

  def accept(regex: Regex, chars: Seq[Char], k: Seq[Char] => Boolean): Boolean =
    regex match {
      case Literal(expect) =>
        if (chars.take(expect.length).sameElements(expect))
          k(chars.drop(expect.length))
        else
          false
      case Concat(regex1, regex2) => accept(regex1, chars, remaining => accept(regex2, remaining, k))
      case Choice(regex1, regex2) => accept(regex1, chars, k) || accept(regex2, chars, k)
      case Star(repeatable)       => k(chars) || accept(repeatable, chars, remaining => accept(regex, remaining, k))
    }

  def complete(remaining: Seq[Char]): Boolean = remaining.length == 0

  def main(args: Array[String]) = {
    val regex1 = Concat(Star(Literal("ab")), Literal("abc")) // (ab*)abc matches abababc
    val regex2 = Choice(Star(Literal("ab")), Concat(Literal("a"), Star(Literal("ba")))) // (ab)*|a(ba)* matches abababa
    accept(regex1, "abababc", complete) // true
    accept(regex2, "abababa", complete) // true
    accept(regex1, "abababcd", complete) // false
  }
}