The most direct way to turn a grammar into a program: one function per rule. expr() handles + and −, term() handles * and /, factor() handles numbers and parenthesised sub-expressions — so the tree of calls at run time is the parse tree. Precedence needs no table: it is the nesting order of the functions; parentheses re-enter expr() at the bottom.
THE TECHNIQUE expr → term → factor
Grammar: expr → term (('+'|'−') term)*; term → factor (('*'|'/') factor)*; factor → number | '(' expr ')'. Precedence falls out of the hierarchy — * binds before + because factor is nested below term below expr. Type an expression (single-digit numbers, + − * /, parens). live demo
HISTORY & CREDIT 1961, not the Pascal era
“Wirth invented recursive descent” — no; he invented popularized it (Pascal, PL/0). It is a 1961 technique. cited
1959–60 · Backus & Naur — BNF, the grammar notation recursive descent mirrors one-function-per-rule. 1961 · Ned Irons (Jan, CACM 4(1)) — the first parser of any kind described in print; Peter Lucas (Dec, IBM Vienna) — the top-down parser built from mutually recursive procedures, one per variable. Independent, near-simultaneous. 1968 / 1971 · Lewis & Stearns define LL(k) — exactly the grammars a predictive (no-backtrack, k-token) recursive descent handles; Knuth’s “Top-Down Syntax Analysis” pins down when it works (FIRST/FOLLOW). 1970s / 2000s · Wirth spreads it through Pascal & PL/0; GCC (3.4+) and Clang replace generated LR tables with hand-written recursive descent — for the error messages and control tables can’t give.
The predictive form (LL(1), one-token lookahead) never backtracks and runs in linear time — backtracking recursive descent is a slower, distinct variant. Irons & Lucas, 1961
RECOMMEND FOR I-13 the compiler's OWN parser is one of these
It runs — and it is a door already open: I-13’s own compiler is a hand-written recursive-descent parser. The expression evaluates and consumes all input:
$ i13 run rd.i13 # expr/term/factor over code points, threading [value, pos]
2*(3+4) -> value 14, endpos 7 (all consumed) 2*3+4 -> 10 (2+3)*4 -> 20
Recommend:nothing new — one recursive function per rule, each returning [value, pos] (the array-return thread); parentheses re-enter expr; precedence is the call hierarchy (verified 2*(3+4)=14 with endpos 7, 2*3+4=10, (2+3)*4=20). The only guard I-13 forces is a bounds check before reading past the input — honest, since out-of-range indexing is rejected. Note: pairs with Pratt (126) — same answers, two paradigms: recursive descent puts precedence in the grammar shape, Pratt puts it on the tokens. Both are the reading half of the 8/19 benchmark’s own front end.