Automata, Regular Expressions & Parsing

Regular Languages, DFA, and NFA

A finite automaton recognizes a language by reading an input left to right and accepting exactly when the final state is accepting. A DFA has one transition for each state-symbol pair, so an input of length $n$ follows one state sequence in $O(n)$ time. An NFA may have several labeled transitions and $\varepsilon$-transitions that consume no input; simulation maintains the set of all states reachable after each prefix.

The $\varepsilon$-closure of a set contains every state reachable through zero or more $\varepsilon$-transitions. Subset construction converts an NFA to a DFA by treating each reachable, closed NFA-state subset as one DFA state. A subset is accepting if it contains an accepting NFA state. An $m$-state NFA can theoretically induce $2^m$ subsets, though only reachable subsets are built.

DFA minimization removes unreachable states and merges states with indistinguishable future behavior. Hopcroft's partition-refinement algorithm begins with accepting and rejecting blocks and repeatedly splits them using incoming transitions, running in $O(|\Sigma|m\log m)$. The minimal DFA is unique up to state renaming. Regular languages are closed under union, intersection, complement, difference, concatenation, Kleene star, reversal, homomorphism, and inverse homomorphism.

flowchart TD
    INPUT["Read next symbol c"]
    NFA["NFA active-state set"]
    CLOSURE["Move on c and take epsilon closure"]
    DFA["DFA subset-state"]
    NEXT["Take one transition on c"]
    INPUT --> NFA
    NFA --> CLOSURE
    CLOSURE -->|"next reachable set"| NFA
    INPUT --> DFA
    DFA --> NEXT
    NEXT -->|"next subset-state"| DFA

Regex Construction and Engine Safety

Classical regular expressions use literals, alternation, concatenation, repetition, and grouping. Thompson construction composes these operations into an $O(m)$-state $\varepsilon$-NFA for an expression of size $m$. Simulating its active-state set takes polynomial time, commonly $O(nm)$ for input length $n$, and never needs to enumerate matching paths separately.

Brzozowski's derivative $\partial_c(R)$ denotes the language remaining after consuming $c$. Repeated derivatives recognize a string by testing whether the final residual expression is nullable. Normalizing and memoizing derivatives constructs DFA-like states lazily.

A backtracking engine instead selects alternatives recursively and revisits choices after failure. This supports convenient nonregular extensions but permits exponential behavior when nested or overlapping quantifiers describe many equivalent decompositions. Atomic groups and possessive quantifiers can suppress selected retries; automata-based engines provide predictable execution for purely regular patterns.

Context-Free Grammars and Preparation

A context-free grammar contains terminals, nonterminals, productions, and a start symbol. A derivation replaces nonterminals according to productions; a parse tree records the resulting hierarchy, and its leaves spell the input. A grammar is ambiguous when one input has multiple parse trees, as with an expression grammar lacking precedence and associativity.

Top-down parsing cannot directly handle $E\rightarrow E+T\mid T$, because expanding $E$ recurses without consuming input. Immediate left recursion becomes $E\rightarrow TE'$ and $E'\rightarrow +TE'\mid\varepsilon$. Left factoring changes $A\rightarrow\alpha\beta_1\mid\alpha\beta_2$ into $A\rightarrow\alpha A'$ followed by alternatives for $A'$.

$\operatorname{FIRST}(X)$ contains terminals that can begin strings derived from $X$, including $\varepsilon$ when nullable. $\operatorname{FOLLOW}(A)$ contains terminals that may immediately follow $A$, plus the end marker for the start symbol. An LL(1) table uses these sets to select one production from one lookahead token. A pushdown automaton supplies the unbounded stack needed for nesting: terminals match input, while nonterminals expand into production bodies.

Predictive and Shift-Reduce Parsing

Recursive descent assigns a procedure to each nonterminal and works well for prepared predictive grammars. LL parsers formalize this with a table, reading left to right and constructing a leftmost derivation. Pratt parsing specializes in expressions: null denotations parse atoms and prefixes, left denotations parse postfix and infix uses, and binding powers encode precedence and associativity.

Shift-reduce parsers maintain states and recognized symbols. A shift consumes a token; a reduction replaces a production body with its left-hand nonterminal. LR items track positions within productions. SLR chooses reductions using FOLLOW sets, LALR merges canonical states with the same LR(0) core, and canonical LR preserves item-specific lookahead for more power and larger tables.

Generalized and Practical Parsing

Earley parsing uses prediction, scanning, and completion at each input position. It handles arbitrary context-free grammars in $O(n^3)$ worst-case time, improves for unambiguous and deterministic grammars, and can produce a shared parse forest. CYK fills a triangular interval table for a grammar in Chomsky normal form in $O(n^3|G|)$ time.

A lexer normally applies maximal munch: choose the longest token starting at the current position, then use rule priority for ties. Modes change active rules inside strings, comments, interpolation, or embedded languages. Parsers should build ASTs with source spans rather than preserve every grammar node. Panic-mode recovery skips to a synchronizing token; local recovery inserts or deletes a likely token and must always make progress.

Pretty-printers reconstruct text with precedence-aware parentheses and layout rules. Streaming parsers retain only enough state for the next chunk, while incremental parsers reuse immutable subtrees and restartable lexer states after local edits.

from dataclasses import dataclass
from typing import TypeAlias


@dataclass(frozen=True)
class Token:
    kind: str
    text: str
    position: int


AST: TypeAlias = tuple


def lex(source: str) -> list[Token]:
    tokens: list[Token] = []
    kinds = {"+": "PLUS", "-": "MINUS", "*": "STAR", "/": "SLASH",
             "^": "CARET", "(": "LPAREN", ")": "RPAREN"}
    i = 0
    while i < len(source):
        char = source[i]
        if char.isspace():
            i += 1
        elif char.isdigit() or (char == "." and i + 1 < len(source) and source[i+1].isdigit()):
            start, dots = i, 0
            while i < len(source) and (source[i].isdigit() or source[i] == "."):
                dots += source[i] == "."
                if dots > 1:
                    raise SyntaxError(f"invalid number at position {start}")
                i += 1
            tokens.append(Token("NUMBER", source[start:i], start))
        elif char.isalpha() or char == "_":
            start = i
            i += 1
            while i < len(source) and (source[i].isalnum() or source[i] == "_"):
                i += 1
            tokens.append(Token("NAME", source[start:i], start))
        elif char in kinds:
            tokens.append(Token(kinds[char], char, i))
            i += 1
        else:
            raise SyntaxError(f"unexpected character {char!r} at position {i}")
    tokens.append(Token("EOF", "", len(source)))
    return tokens


class PrattParser:
    INFIX_BP = {"PLUS": (10, 11), "MINUS": (10, 11),
                "STAR": (20, 21), "SLASH": (20, 21), "CARET": (30, 30)}

    def __init__(self, tokens: list[Token]):
        self.tokens, self.index = tokens, 0

    @property
    def current(self) -> Token:
        return self.tokens[self.index]

    def advance(self) -> Token:
        token = self.current
        self.index += 1
        return token

    def expect(self, kind: str) -> Token:
        if self.current.kind != kind:
            raise SyntaxError(f"expected {kind} at {self.current.position}, got {self.current.kind}")
        return self.advance()

    def parse(self) -> AST:
        result = self.expression(0)
        self.expect("EOF")
        return result

    def expression(self, minimum_bp: int) -> AST:
        token = self.advance()
        if token.kind == "NUMBER":
            left = ("number", float(token.text))
        elif token.kind == "NAME":
            left = ("name", token.text)
        elif token.kind in {"PLUS", "MINUS"}:
            left = ("unary", token.text, self.expression(25))
        elif token.kind == "LPAREN":
            left = self.expression(0)
            self.expect("RPAREN")
        else:
            raise SyntaxError(f"expected expression at {token.position}")

        while self.current.kind in self.INFIX_BP:
            left_bp, right_bp = self.INFIX_BP[self.current.kind]
            if left_bp < minimum_bp:
                break
            operator = self.advance()
            left = ("binary", operator.text, left, self.expression(right_bp))
        return left


def parse(source: str) -> AST:
    return PrattParser(lex(source)).parse()


if __name__ == "__main__":
    assert parse("1 + 2 * 3") == (
        "binary", "+", ("number", 1.0),
        ("binary", "*", ("number", 2.0), ("number", 3.0)),
    )
    assert parse("2 ^ 3 ^ 2") == (
        "binary", "^", ("number", 2.0),
        ("binary", "^", ("number", 3.0), ("number", 2.0)),
    )
    for expression in ["1 + 2 * 3", "-x ^ 2 + y", "2 ^ 3 ^ 2", "(alpha + 4) / 2"]:
        print(expression, "=>", parse(expression))