lexer-fsm-parser-pushdown-automaton

IN premise — entries/2026/06/21/wiki-Tokenization_lexical_analysis-chunk-1.md

Created 2026-06-21T09:50:10+00:00

In compiler design, the lexer uses a finite-state machine (FSM) while the parser uses a pushdown automaton (stack-based); regular expressions cannot count or match recursive structures.

Summary

The compiler splits its work into two stages because they demand different levels of memory: recognizing simple tokens only needs to track which state it is in, but parsing sentences with nested or recursive structure (like matching brackets or grammar rules) requires a stack to remember what is still open. This division isn't an arbitrary design choice; the extra machinery at the parsing stage is forced by the fact that regular pattern-matching simply cannot count or verify that structures are properly closed.

Dependents

These beliefs depend on this one:

IN compiler-theory-illuminates-tokenizer-model-separation — The formal language hierarchy separating lexer-level processing (regular languages, finite-state machines) from parser-level processing (context-free languages, pushdown automata) has a structural analog in LLM architecture: subword tokenization (BPE/WordPiece) operates at the finite-state statistical level while attention provides the unbounded context-sensitivity that finite-state processing cannot, illuminating why tokenization remains a separate preprocessing stage rather than being absorbed into the model's core computation.