Derekokich

    def parenExpr: Parser[RegexExpr] = "(" ~> highExpr <~ ")"
    def lit: Parser[RegexExpr] = charLit | parenExpr

Derekokich

    def repeat: Parser[RegexExpr] = lit <~ "*" 
        ^^ { case l => Repeat(l) } 
    def plus: Parser[RegexExpr] = lit <~ "+" 
        ^^ { case p => Plus(p) }
    def lowExpr: Parser[RegexExpr] = repeat | plus | lit

Derekokich

   def concat: Parser[RegexExpr] = rep(lowExpr) 
        ^^ { case list => listToConcat(list)}
    def midExpr: Parser[RegexExpr] = concat | lowExpr

Derekokich

    def or: Parser[RegexExpr] = midExpr ~ "|" ~ midExpr 
        ^^ { case l ~ "|" ~ r => Or(l, r)}

Derekokich

    def highExpr: Parser[RegexExpr] = or | midExpr

Derekokich

    def listToConcat(list: List[RegexExpr]): RegexExpr = list match {
        case head :: Nil => head
        case head :: rest => Concat(head, listToConcat(rest))
    }

    def apply(input: String): Option[RegexExpr] = {
        parseAll(highExpr, input) match {
            case Success(result, _) => Some(result)
            case failure : NoSuccess => None
        }

Derekokich

    def concat: Parser[RegexExpr] = rep(lowExpr) 
        ^^ { case list => listToConcat(list)}
    def midExpr: Parser[RegexExpr] = concat | lowExpr

Derekokich

    def concat: Parser[RegexExpr] = rep(lowExpr) 
        ^^ { case list => listToConcat(list)}
    def midExpr: Parser[RegexExpr] = concat | lowExpr

Derekokich

object NFA {
    def regexToNFA(regex: RegexExpr): State = 
        regexToNFA(regex, Match())

    private def regexToNFA(regex: RegexExpr, 
                           andThen: State): State = {       
        regex match {
            case Literal(c) => new Consume(c, andThen)
            case Concat(first, second) => {
                // Convert first to an NFA. The "out" of that is

Derekokich

object NFAEvaluator {
    def evaluate(nfa: State, input: String): Boolean = 
        evaluate(Set(nfa), input)

    def evaluate(nfas: Set[State], input: String): Boolean = {
        input match {
            case "" => 
                evaluateStates(nfas, None).exists(_ == Match())
            case string => 
                evaluate(