Recursive Descent Parsers

## Taking the grammar literally A **recursive-descent parser** is a top-down parser in which every nonterminal of the grammar becomes one function. Parsing begins by calling the function for the start rule; that function calls the functions for the symbols on the right-hand side of its rule, left to right, and returns the fragment of tree it built. Recursion in the grammar — a block that may contain another block — becomes recursion in the code, which is where the name comes from. For a small job-scheduling description language the rules might be: ```pseudocode job -> 'job' NAME block block -> '{' directives '}' directives -> directive directives | (nothing) directive -> 'every' DURATION | 'retry' NUMBER | 'run' STRING ``` Four rules, four functions. Nothing else is needed: there is no table, no generated state machine, no separate driver loop. ## The contract every rule function honours A hand-written parser stays readable only while each function keeps the same two-part bargain: - **It is entered with the input positioned at the first token of its rule**, and it returns with the input positioned immediately after the last token of its rule. - **It consumes nothing it does not own.** The function for `block` consumes the braces and whatever `directives` consumes, then stops. It never reads past its own closing brace to help its caller decide something. Breaking that bargain in one function is the classic way a hand-written parser becomes unmaintainable, because every caller then has to know which tokens that one function might have eaten. ## One token of lookahead, and the three helpers A predictive parser never guesses and never backtracks. It examines — but does not consume — the next token, then commits. | helper | consumes a token | typically used for | |---|---|---| | `peek()` | never | deciding which alternative to take | | `match(kind)` | only when the kind matches | optional and repeated pieces | | `expect(kind)` | yes, or raises a parse error | a piece the rule requires | The decision procedure inside a function with several alternatives is mechanical: 1. For each alternative, work out the set of tokens it can begin with. 2. Check those sets do not overlap. If two alternatives can begin with the same token, one token of lookahead cannot separate them and this technique does not apply as written. 3. Branch on `peek()` against those sets; if the token belongs to none of them, raise an error that lists the tokens which would have been accepted. For `directive` the three sets are `{'every'}`, `{'retry'}` and `{'run'}` — disjoint, so the choice is a three-way branch on a single token. Because each token is inspected a bounded number of times and consumed exactly once, parsing runs in time linear in the number of tokens, where the input size is the token count rather than the character count. ## Why nesting is free The reason this technique suits nested configuration and description languages is that the **call stack is the parser's memory of depth**. A `block` inside a `block` is just `parse_block` calling `parse_directive` calling `parse_block` again; the pushdown behaviour that the grammar needs comes from the runtime's own call stack instead of an explicit stack the parser maintains. The shape of the code is the shape of the language, so a reviewer who knows the rules can read the parser, and a debugger's stack trace at the point of failure reads as the path through the grammar. ## What it buys, and what it costs - **Buys:** ordinary code you can step through; an error raised at the exact point of failure, inside the function that knows what it wanted next; a natural place to hang an ad-hoc rule (a directive legal only inside another directive) that a pure rule set expresses clumsily; tree construction and validation in the same pass. - **Costs:** the grammar exists only implicitly, spread across the functions, so nothing checks the alternatives for overlap — you find a clash by reasoning or by a failing test; an alternative that can derive nothing at all needs more than a first-token test to select; and a rule whose first symbol is the rule itself cannot be written this way at all, because the function would re-enter itself before consuming anything. One operational consequence follows directly from the call-stack trick: the stack depth equals the nesting depth of the input. A parser exposed to untrusted documents therefore needs an explicit depth counter checked on entry to the recursive functions, because unbounded nesting in a hostile input is a denial-of-service shape and a larger stack only moves the threshold.