CSC344 Assignment 3 (Scala)

Write a Scala program that performs pattern matching on strings, where patterns are expressed using only the concatenation, alternation ("|") and optional ("?") operators of regular expressions (no loops/"*", no escape characters). Each run of the program should accept a pattern, and then any number of strings, reporting only whether they match. Your program should represent expressions (as trees) and evaluate on the inputs, without using the Scala regular expression library. For example:

pattern? ((h|j)ello worl?d)|(42)
string? hello world
match
string? jello word
match
string? 42
match
string? 24
no match
string? hello world42
no match

Bootstrap

A flat grammar for patterns is:

  E -> c | EE | E'|'E | E'?' | '(' E ')'

Where c is any character other than "()|?", and where option('?') has highest precedence, then concatentation, then alternation('|'). This can be transformed into an ugly but deterministically parseable form:

  S  -> E$
  E  -> T E2
  E2 -> '|' E3 
  E2 -> NIL
  E3 -> T E2
  T  -> F T2
  T2 -> F T2
  T2 -> NIL
  F  -> A F2
  F2 -> '?' F2
  F2 -> NIL
  A  -> c
  A  -> '(' A2
  A2 -> E ')'

where '$' is eof/end-of-string, and NIL means empty (which in these productions means take the rhs only if others do not apply). Some Scala classes represeting this might be:

    abstract class S
    case class E(left: T, right: Option[E2]) extends S
    case class E2(left: E3) extends S
    case class E3(left: T, right: Option[E2]) extends S
    case class T(left: F, right: Option[T2]) extends S
    case class T2(left: F, right: Option[T2]) extends S
    case class F(left: A, right: Option[F2]) extends S
    case class F2(left: Option[F2]) extends S
    case class A(opt1: Option[C], opt2: Option[A2]) extends S
    case class A2(left: E) extends S
    case class C(content: Char) extends S

with ...

  var input: String;
  var inputIndex = 0;
  ...
  def parseS(): E = { parseE() }
  def parseE(): E = { E(parseT(),parseE2()) }
  def parse2() : Option[E2] = {
    if (inputIndex < input.length && input.charAt(inputIndex) == '|') {
      ++inputIndex;
      Some(E2(parseE3));
    }
    else
      None
  }
   ...

and ...

  val root: E;
  var candidate : String;
  var candidateIndex = 0;
  ...
  def matchS() : Boolean = { matchE(root) && candidateIndex == candidate.length }
  ...
  def matchT2(t: Option[T2]) = t match {
    case Some(s) => matchF(s.left) && matchT2(s.right)
    case None => true;
  }
  ...

Doug Lea