lexical-grammar-regular-syntactic-context-free
IN premise — entries/2026/06/21/wiki-Tokenization_lexical_analysis-chunk-1.md
Created 2026-06-21T09:50:10+00:00
Lexical grammars are regular languages (handled by FSMs with regular expressions); syntactic grammars are context-free languages (handled by parsers with stacks).
Summary
This captures the standard compiler design fact that the two levels of grammar require different tools: recognizing tokens (like keywords and identifiers) is simple enough for a state machine, while figuring out sentence structure (like nested if-then-else blocks) needs a stack-based parser. It matters because it tells the system that lexical and syntactic processing cannot be collapsed into one mechanism; they must be treated as separate stages with different complexity budgets and failure modes.