// NFAs and Thompson's construction +
−
+
−
// helper function for recording 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)+
−
}+
−
+
−
+
−
// state nodes+
−
abstract class State+
−
type States = Set[State]+
−
+
−
case class IntState(i: Int) extends State+
−
+
−
object NewState {+
−
  var counter = 0+
−
  +
−
  def apply() : IntState = {+
−
    counter += 1;+
−
    new IntState(counter - 1)+
−
  }+
−
}+
−
+
−
+
−
case class NFA(states: States, +
−
               start: State, +
−
               delta: (State, Char) => States, +
−
               eps: State => States,+
−
               fins: States) {+
−
  +
−
  def epsclosure(qs: States) : States = {+
−
    val ps = qs ++ qs.flatMap(eps(_))+
−
    if (qs == ps) ps else epsclosure(ps)+
−
  }+
−
+
−
  def deltas(qs: States, s: List[Char]) : States = s match {+
−
    case Nil => epsclosure(qs)+
−
    case c::cs => deltas(epsclosure(epsclosure(qs).flatMap (delta (_, c))), cs)+
−
  }+
−
+
−
  def accepts(s: String) : Boolean = +
−
    deltas(Set(start), s.toList) exists (fins contains (_))+
−
}+
−
+
−
// A small example NFA from the lectures +
−
val Q0 = NewState()+
−
val Q1 = NewState()+
−
val Q2 = NewState()+
−
+
−
val delta : (State, Char) => States = {+
−
  case (Q0, 'a') => Set(Q0)+
−
  case (Q1, 'a') => Set(Q1)+
−
  case (Q2, 'b') => Set(Q2)+
−
  case (_, _) => Set ()+
−
}+
−
+
−
val eps : State => States = {+
−
  case Q0 => Set(Q1, Q2)+
−
  case _ => Set()+
−
}+
−
+
−
val NFA1 = NFA(Set(Q0, Q1, Q2), Q0, delta, eps, Set(Q2))+
−
+
−
NFA1.accepts("aa")+
−
NFA1.accepts("aaaaa")+
−
NFA1.accepts("aaaaabbb")+
−
NFA1.accepts("aaaaabbbaaa")+
−
NFA1.accepts("ac")+
−
+
−
+
−
// explicit construction of some NFAs; used in+
−
// Thompson's construction+
−
+
−
// NFA that does not accept any string+
−
def NFA_NULL() : NFA = {+
−
  val Q = NewState()+
−
  NFA(Set(Q), Q, { case (_, _) => Set() }, { case _ => Set() }, Set())+
−
}+
−
+
−
// NFA that accepts the empty string+
−
def NFA_EMPTY() : NFA = {+
−
  val Q = NewState()+
−
  NFA(Set(Q), Q, { case (_, _) => Set() }, { case _ => Set() }, Set(Q))+
−
}+
−
+
−
// NFA that accepts the string "c"+
−
def NFA_CHAR(c: Char) : NFA = {+
−
  val Q1 = NewState()+
−
  val Q2 = NewState()+
−
  NFA(Set(Q1, Q2), +
−
      Q1, +
−
      { case (Q1, d) if (c == d) => Set(Q2)+
−
        case (_, _) => Set() },+
−
      { case _ => Set() },+
−
      Set(Q2))+
−
}+
−
+
−
// alternative of two NFAs+
−
def NFA_ALT(nfa1: NFA, nfa2: NFA) : NFA = {+
−
  val Q = NewState()+
−
  NFA(Set(Q) ++ nfa1.states ++ nfa2.states,+
−
      Q,+
−
      { case (q, c) if (nfa1.states contains q) => nfa1.delta(q, c)+
−
        case (q, c) if (nfa2.states contains q) => nfa2.delta(q, c)+
−
        case (_, _) => Set() },+
−
      { case Q => Set(nfa1.start, nfa2.start)+
−
        case q if (nfa1.states contains q) => nfa1.eps(q)+
−
        case q if (nfa2.states contains q) => nfa2.eps(q)+
−
        case _ => Set() },+
−
      nfa1.fins ++ nfa2.fins)+
−
}+
−
+
−
// sequence of two NFAs+
−
def NFA_SEQ(nfa1: NFA, nfa2: NFA) : NFA = {+
−
  NFA(nfa1.states ++ nfa2.states,+
−
      nfa1.start,+
−
      { case (q, c) if (nfa1.states contains q) => nfa1.delta(q, c)+
−
        case (q, c) if (nfa2.states contains q) => nfa2.delta(q, c)+
−
        case (_, _) => Set() },+
−
      { case q if (nfa1.fins contains q) => nfa1.eps(q) ++ Set(nfa2.start)+
−
        case q if (nfa1.states contains q) => nfa1.eps(q)+
−
        case q if (nfa2.states contains q) => nfa2.eps(q)+
−
        case _ => Set() },+
−
      nfa2.fins)+
−
}+
−
+
−
// star of an NFA+
−
def NFA_STAR(nfa: NFA) : NFA = {+
−
  val Q = NewState()+
−
  NFA(Set(Q) ++ nfa.states, +
−
      Q,+
−
      nfa.delta,+
−
      { case Q => Set(nfa.start)+
−
        case q if (nfa.fins contains q) => nfa.eps(q) ++ Set(Q)+
−
        case q if (nfa.states contains q) => nfa.eps(q)+
−
        case _ => Set() },+
−
      Set(Q))+
−
}+
−
+
−
+
−
// regular expressions used for Thompson's construction+
−
abstract class Rexp+
−
+
−
case object NULL extends Rexp+
−
case object EMPTY extends Rexp+
−
case class CHAR(c: Char) extends Rexp +
−
case class ALT(r1: Rexp, r2: Rexp) extends Rexp+
−
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp +
−
case class STAR(r: Rexp) extends Rexp+
−
+
−
// some convenience for typing in regular expressions+
−
def charlist2rexp(s : List[Char]) : Rexp = s match {+
−
  case Nil => EMPTY+
−
  case c::Nil => CHAR(c)+
−
  case c::s => SEQ(CHAR(c), charlist2rexp(s))+
−
}+
−
implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)+
−
+
−
+
−
+
−
def thompson (r: Rexp) : NFA = r match {+
−
  case NULL => NFA_NULL()+
−
  case EMPTY => NFA_EMPTY()+
−
  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))+
−
}+
−
+
−
// some examples for Thompson's+
−
val A = thompson(CHAR('a'))+
−
+
−
println(A.accepts("a"))   // true +
−
println(A.accepts("c"))   // false +
−
println(A.accepts("aa"))  // false+
−
+
−
val B = thompson(ALT("ab","ac"))+
−
 +
−
println(B.accepts("ab"))   // true +
−
println(B.accepts("ac"))   // true +
−
println(B.accepts("bb"))   // false +
−
println(B.accepts("aa"))   // false +
−
+
−
val C = thompson(STAR("ab"))+
−
+
−
println(C.accepts(""))       // true+
−
println(C.accepts("a"))      // false +
−
println(C.accepts("ababab")) // true+
−
println(C.accepts("ab"))     // true+
−
println(C.accepts("ac"))     // false +
−
println(C.accepts("bb"))     // false +
−
println(C.accepts("aa"))     // false +
−
+
−
// regular expression matcher using Thompson's+
−
def matcher(r: Rexp, s: String) : Boolean = thompson(r).accepts(s)+
−
+
−
+
−
//optional+
−
def OPT(r: Rexp) = ALT(r, EMPTY)+
−
+
−
//n-times+
−
def NTIMES(r: Rexp, n: Int) : Rexp = n match {+
−
  case 0 => EMPTY+
−
  case 1 => r+
−
  case n => SEQ(r, NTIMES(r, n - 1))+
−
}+
−
+
−
// evil regular exproession+
−
def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))+
−
+
−
// test harness for the matcher+
−
for (i <- 0 to 100 by 5) {+
−
  println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i))))+
−
}+
−
+
−
+
−
// regular expression matching via search and backtracking+
−
def accepts2(nfa: NFA, s: String) : Boolean = {+
−
+
−
  def search(q: State, s: List[Char]) : Boolean = s match {+
−
    case Nil => nfa.fins contains (q)+
−
    case c::cs => +
−
      (nfa.delta(q, c) exists (search(_, cs))) || +
−
      (nfa.eps(q) exists (search(_, c::cs)))+
−
  }+
−
+
−
  search(nfa.start, s.toList)+
−
}+
−
+
−
def matcher2(r: Rexp, s: String) : Boolean = accepts2(thompson(r), s)+
−
+
−
// test harness for the backtracking matcher+
−
for (i <- 0 to 20 by 1) {+
−
  println(i + ": " + "%.5f".format(time_needed(1, matcher2(EVIL(i), "a" * i))))+
−
}+
−
+
−
+
−
+
−
+
−