Derekokich

Regex.fullMatch("aaaaab", "a*b") // True
Regex.fullMatch("aaaabc", "a*b") // False
Regex.matchAnywhere("abcde", "cde") // True

Derekokich

object Regex {
    def fullMatch(input: String, pattern: String) = {
        val parsed = RegexParser(pattern).getOrElse(
            throw new RuntimeException("Failed to parse regex")
        )
        val nfa = NFA.regexToNFA(parsed)
        NFAEvaluator.evaluate(nfa, input)
    }   

    def matchAnywhere(input: String, pattern: String) = 

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(

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

    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

    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 highExpr: Parser[RegexExpr] = or | midExpr

Derekokich

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

Derekokich

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