Parser
A parser builds an AST from a token sequence according to grammar rules, in two families: top-down (recursive descent/LL) and bottom-up (LR/LALR).
Purpose
Structure tokens into a syntax tree — the core of compilers and parsing tools.
Mechanism
LL(k): left-to-right, leftmost derivation, k tokens of lookahead. LR(k): left-to-right, rightmost derivation. Recursive descent: hand-written, one function per nonterminal. PEG uses ordered choice and backtracking.
Use cases
- Compiler implementation
- Data format parsing
- DSL