// Thompson Construction+
−
//=======================+
−
+
−
import $file.dfa, dfa._ +
−
import $file.nfa, nfa._+
−
import $file.enfa, enfa._+
−
+
−
+
−
// states for Thompson construction+
−
case class TState(i: Int) extends State+
−
+
−
object TState {+
−
  var counter = 0+
−
  +
−
  def apply() : TState = {+
−
    counter += 1;+
−
    new TState(counter)+
−
  }+
−
}+
−
+
−
+
−
// some types abbreviations+
−
type NFAt = NFA[TState, Char]+
−
type NFAtrans = (TState, Char) :=> Set[TState]+
−
type eNFAtrans = (TState, Option[Char]) :=> Set[TState]+
−
+
−
 +
−
// NFA that does not accept any string+
−
def NFA_ZERO(): NFAt = {+
−
  val Q = TState()+
−
  NFA(Set(Q), { case _ => Set() }, Set())+
−
}+
−
+
−
// NFA that accepts the empty string+
−
def NFA_ONE() : NFAt = {+
−
  val Q = TState()+
−
  NFA(Set(Q), { case _ => Set() }, Set(Q))+
−
}+
−
+
−
// NFA that accepts the string "c"+
−
def NFA_CHAR(c: Char) : NFAt = {+
−
  val Q1 = TState()+
−
  val Q2 = TState()+
−
  NFA(Set(Q1), { case (Q1, d) if (c == d) => Set(Q2) }, Set(Q2))+
−
}+
−
+
−
+
−
// for composing an eNFA transition with an NFA transition+
−
// | is for set union+
−
extension (f: eNFAtrans) {+
−
  def +++(g: NFAtrans) : eNFAtrans = +
−
  { case (q, None) =>  applyOrElse(f, (q, None)) +
−
    case (q, Some(c)) => applyOrElse(f, (q, Some(c))) | applyOrElse(g, (q, c))  }+
−
}+
−
+
−
+
−
// sequence of two NFAs+
−
def NFA_SEQ(nfa1: NFAt, nfa2: NFAt) : NFAt = {+
−
  val new_delta : eNFAtrans = +
−
    { case (q, None) if nfa1.fins(q) => nfa2.starts }+
−
  +
−
  eNFA(nfa1.starts, +
−
       new_delta +++ nfa1.delta +++ nfa2.delta, +
−
       nfa2.fins)+
−
}+
−
+
−
// alternative of two NFAs+
−
def NFA_ALT(nfa1: NFAt, nfa2: NFAt) : NFAt = {+
−
  val new_delta : NFAtrans = { +
−
    case (q, c) =>  applyOrElse(nfa1.delta, (q, c)) | +
−
                    applyOrElse(nfa2.delta, (q, c)) }+
−
  val new_fins = (q: TState) => nfa1.fins(q) || nfa2.fins(q)+
−
+
−
  NFA(nfa1.starts | nfa2.starts, new_delta, new_fins)+
−
}+
−
+
−
// star of a NFA+
−
def NFA_STAR(nfa: NFAt) : NFAt = {+
−
  val Q = TState()+
−
  val new_delta : eNFAtrans = +
−
    { case (Q, None) => nfa.starts+
−
      case (q, None) if nfa.fins(q) => Set(Q) }+
−
+
−
  eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q))+
−
}+
−
+
−
+
−
// We are now ready to translate regular expressions+
−
// into DFAs (via eNFAs and NFAs, and the subset construction)+
−
+
−
// regular expressions+
−
abstract class Rexp+
−
case object ZERO extends Rexp                    // matches nothing+
−
case object ONE extends Rexp                     // matches the empty string+
−
case class CHAR(c: Char) extends Rexp            // matches a character c+
−
case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative+
−
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence+
−
case class STAR(r: Rexp) extends Rexp            // star+
−
+
−
// thompson construction +
−
def thompson (r: Rexp) : NFAt = r match {+
−
  case ZERO => NFA_ZERO()+
−
  case ONE => NFA_ONE()+
−
  case CHAR(c) => NFA_CHAR(c)  +
−
  case ALT(r1, r2) => NFA_ALT(thompson(r1), thompson(r2))+
−
  case SEQ(r1, r2) => NFA_SEQ(thompson(r1), thompson(r2))+
−
  case STAR(r1) => NFA_STAR(thompson(r1))+
−
}+
−
+
−
//optional regular expression (one or zero times)+
−
def OPT(r: Rexp) = ALT(r, ONE)+
−
+
−
//n-times regular expression (explicitly expanded)+
−
def NTIMES(r: Rexp, n: Int) : Rexp = n match {+
−
  case 0 => ONE+
−
  case 1 => r+
−
  case n => SEQ(r, NTIMES(r, n - 1))+
−
}+
−
+
−
+
−
def tmatches_nfa(r: Rexp, s: String) : Boolean =+
−
  thompson(r).accepts(s.toList)+
−
+
−
def tmatches_nfa2(r: Rexp, s: String) : Boolean =+
−
  thompson(r).accepts2(s.toList)+
−
+
−
// dfas via subset construction+
−
def tmatches_dfa(r: Rexp, s: String) : Boolean =+
−
  subset(thompson(r)).accepts(s.toList)+
−
+
−
// Test Cases+
−
//============+
−
+
−
// the evil regular expression  a?{n} a{n}+
−
def EVIL1(n: Int) : Rexp = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))+
−
+
−
// the evil regular expression (a*)*b+
−
val EVIL2 : Rexp = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))+
−
+
−
//for measuring time+
−
def time_needed[T](i: Int, code: => T) = {+
−
  val start = System.nanoTime()+
−
  for (j <- 1 to i) code+
−
  val end = System.nanoTime()+
−
  (end - start)/(i * 1.0e9)+
−
}+
−
+
−
// the size of the NFA can be large, +
−
// thus slowing down the breadth-first search+
−
println("Breadth-first search EVIL1 / EVIL2")+
−
+
−
for (i <- 1 to 13) {+
−
  println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i))))+
−
}+
−
+
−
for (i <- 1 to 100 by 5) {+
−
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i))))+
−
}+
−
+
−
+
−
// the backtracking that is needed in depth-first +
−
// search can be painfully slow+
−
println("Depth-first search EVIL1 / EVIL2")+
−
+
−
for (i <- 1 to 9) {+
−
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i))))+
−
}+
−
+
−
for (i <- 1 to 7) {+
−
  println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i))))+
−
}+
−
+
−
+
−
+
−
// while my thompson->enfa->subset->partial-function-chain+
−
// is probably not the most effcient way to obtain a fast DFA +
−
// (the test below should be much faster with a more direct +
−
// construction), in general the DFAs can be slow because of +
−
// the state explosion in the subset construction+
−
+
−
for (i <- 1 to 7) {+
−
  println(i + ": " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i))))+
−
}+
−
+
−
for (i <- 1 to 100 by 5) {+
−
  println(i + " " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i))))+
−
}+
−
+
−
+
−
+
−
+
−
+
−