Parsing

A parser turns a flat token list into a tree whose shape is dictated entirely by the grammar. It decides what is applied to what — and it is not allowed to decide whether any of it means anything.

Two trees for the same input `1 + 2 * 3`: one with a node for every grammar rule and every comma, one with five nodes. The difference is not tidiness — it decides which tools you can build.

One function per grammar rule, the call stack as the parse stack. It is the technique most production compilers actually use — and the one that loops forever if you hand it a left-recursive grammar.

Replace the tower of precedence functions with one loop and a table of binding powers. Prefix handlers, infix handlers, and a single comparison that decides whether to keep going — this is the parsing technique most worth actually knowing.

Left-to-right scan, leftmost derivation, k tokens of lookahead. The FIRST and FOLLOW sets are the mechanical answer to "which production do I pick", and the reason some grammars simply cannot be parsed top-down.

Bottom-up: never choose a production until the whole right-hand side is on the stack. It handles left recursion natively, accepts a strictly larger class of grammars than LL — and reports its problems as "conflict in state 143".

Two actions, one stack. Walk `1 + 2` through a bottom-up parser one move at a time and watch the tree assemble itself from the leaves upward — then see exactly what a conflict is.

LR accepts a strictly larger class of grammars. Clang, rustc, Roslyn, V8 and Go all hand-write recursive descent anyway. The reason is not ignorance or inertia — it is error messages, incremental reparse, and what an IDE needs.

ANTLR, Bison, tree-sitter and LALRPOP turn a grammar file into a parser. What you buy is a machine-checked grammar and cheap change; what you pay is diagnostics, debuggability and a build step.