Catastrophic Backtracking — Finite Automata Fix Outage

package io.thecodeforge.compiler.lexer;

import java.util.ArrayList;
import java.util.List;

/**
 * Represents a state in a Non-deterministic Finite Automaton.
 * Includes support for epsilon transitions used in Thompson's Construction.
 * I always keep this class tiny and immutable in real projects — helps debugging.
 */
public class NfaState {
    private final int id;
    private final List<Transition> transitions = new ArrayList<>();
    private boolean isAccepting = false;

    public NfaState(int id) {
        this.id = id;
    }

    public void addTransition(char input, NfaState target) {
        transitions.add(new Transition(input, target));
    }

    public void addEpsilonTransition(NfaState target) {
        transitions.add(new Transition('\0', target));
    }

    private record Transition(char input, NfaState target) {}
}

package io.thecodeforge.compiler.lexer;

/**
 * A production-grade DFA runner for a simple 'ID' token pattern: [a-zA-Z][a-zA-Z0-9]*
 * This is the exact pattern I used in my first toy compiler — it taught me more than any textbook.
 */
public class DfaLexer {
    private enum State { START, IN_ID, REJECT }

    public boolean isValidIdentifier(String input) {
        State currentState = State.START;

        for (char c : input.toCharArray()) {
            currentState = transition(currentState, c);
            if (currentState == State.REJECT) return false;
        }

        return currentState == State.IN_ID;
    }

    private State transition(State s, char c) {
        return switch (s) {
            case START -> Character.isLetter(c) ? State.IN_ID : State.REJECT;
            case IN_ID -> Character.isLetterOrDigit(c) ? State.IN_ID : State.REJECT;
            default -> State.REJECT;
        };
    }
}

package io.thecodeforge.compiler.lexer;

import java.util.*;

public class SubsetConstruction {
    public static DFA convertNfaToDfa(NFA nfa) {
        Set<Set<NfaState>> dfaStates = new LinkedHashSet<>();
        Map<Set<NfaState>, Map<Character, Set<NfaState>>> transitions = new HashMap<>();
        
        // Start with epsilon closure of start state
        Set<NfaState> startSet = epsilonClosure(nfa.getStartState());
        dfaStates.add(startSet);
        Queue<Set<NfaState>> queue = new LinkedList<>();
        queue.add(startSet);
        
        while (!queue.isEmpty()) {
            Set<NfaState> currentSet = queue.poll();
            Map<Character, Set<NfaState>> trans = new HashMap<>();
            for (NfaState s : currentSet) {
                for (Transition t : s.getTransitions()) {
                    if (t.getInput() != '\0') {
                        Set<NfaState> targetSet = epsilonClosure(t.getTarget());
                        if (!targetSet.isEmpty()) {
                            trans.merge(t.getInput(), targetSet, (a, b) -> { a.addAll(b); return a; });
                        }
                    }
                }
            }
            for (Map.Entry<Character, Set<NfaState>> entry : trans.entrySet()) {
                if (!dfaStates.contains(entry.getValue())) {
                    dfaStates.add(entry.getValue());
                    queue.add(entry.getValue());
                }
                // Record transition
            }
            transitions.put(currentSet, trans);
        }
        
        // Build DFA object from dfaStates and transitions
        return new DFA(dfaStates, transitions, nfa.getAcceptingStates());
    }
    
    private static Set<NfaState> epsilonClosure(NfaState state) {
        Set<NfaState> closure = new HashSet<>();
        // BFS over epsilon transitions
        Deque<NfaState> stack = new ArrayDeque<>();
        stack.push(state);
        while (!stack.isEmpty()) {
            NfaState s = stack.pop();
            if (!closure.contains(s)) {
                closure.add(s);
                for (Transition t : s.getTransitions()) {
                    if (t.getInput() == '\0') {
                        stack.push(t.getTarget());
                    }
                }
            }
        }
        return closure;
    }
}

# io.thecodeforge.infrastructure
FROM ubuntu:22.04

# Install flex (Fast Lexical Analyzer Generator)
RUN apt-get update && apt-get install -y flex gcc make

WORKDIR /compiler-forge
COPY scanner.l .

# Generate C code from regex definitions and compile
RUN flex scanner.l && gcc lex.yy.c -o scanner

ENTRYPOINT ["./scanner"]

package io.thecodeforge.security;

import com.google.re2j.Pattern;
import com.google.re2j.Matcher;

public class SafeRegexMatcher {
    public static boolean isValidEmail(String email) {
        // Safe DFA-based regex using RE2J (Java port of RE2)
        Pattern pattern = Pattern.compile("^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,}$");
        Matcher matcher = pattern.matcher(email);
        return matcher.matches(); // O(n) guaranteed
    }
}