Part 1 · 1 chapters · ~8 min

Grammars and Parsing

The Chomsky hierarchy, context-free grammars and BNF, derivations and parse trees, ambiguity and how precedence removes it, pushdown automata, recursive descent, LL and LR parsing in outline, parser generators, and why you should never parse HTML or JSON with a regex.

A grammar and its parser

code

// recursive descent for: expr → term (("+"|"-") term)* ; term → factor (("*"|"/") factor)* ; factor → num | "(" expr ")"
function parse(src: string) {
  const toks = src.match(/\d+|[-+*/()]/g) ?? []; let i = 0;
  const peek = () => toks[i], eat = (t?: string) => { if (t && toks[i] !== t) throw new Error(`expected ${t}`); return toks[i++]; };
  const factor = (): any => peek() === '(' ? (eat('('), ((e) => (eat(')'), e))(expr())) : { num: Number(eat()) };
  const term = () => { let l = factor(); while (peek() === '*' || peek() === '/') l = { op: eat(), l, r: factor() }; return l; };
  const expr = () => { let l = term(); while (peek() === '+' || peek() === '-') l = { op: eat(), l, r: term() }; return l; };
  return expr();
}
parse('2 + 3 * (4 - 1)')   // { op: '+', l: { num: 2 }, r: { op: '*', l: { num: 3 }, r: { op: '-', … } } }

Chomsky level	recognised by	example
regular	finite automaton	tokens, identifiers, numbers
context-free	pushdown automaton (a stack)	nested expressions, JSON, most programming language syntax
context-sensitive	linear-bounded automaton	"declared before use" style constraints
recursively enumerable	Turing machine	anything computable

The stack is the extra power: a pushdown automaton can match brackets because it can remember how many are open. Real compilers lex with automata and parse with a context-free grammar, then check context-sensitive rules (types, scopes) in later passes.

A CONTEXT-FREE GRAMMAR FOR EXPRESSIONS

rules that nest, and a parser that follows them

swipe the figure sideways, or tap expand for full screen

1/4

rules

A context-free grammar has rules whose right-hand sides can refer back to themselves. factor can contain a whole expr in brackets: nesting to any depth, which no regex can do.

recursive rulesnesting regexes cannot do