Recursivedescent

Recursivedescent is a term used to describe the parsing approach known as recursive descent, a top-down method for analyzing the structure of a sequence according to a context-free grammar. In practice, a recursivedescent parser is built from a set of mutually recursive procedures, with each procedure corresponding to a nonterminal of the grammar. The procedures consume tokens and call other procedures to match the right-hand sides of grammar rules.

The core idea is straightforward: the entry point invokes the procedure for the start symbol, and each nonterminal’s rule is implemented as code that either matches terminal symbols directly or delegates to other nonterminal procedures. Lookahead is typically used to decide which alternative to take, and the parser often reports syntax errors when the input cannot be matched. This technique is especially common for small to medium-sized languages or interpreters, where simplicity and clarity of implementation are priorities.

Left recursion is incompatible with a pure recursivedescent approach, as it can lead to infinite recursion. To handle a broader class of grammars, grammars are usually transformed to an equivalent left-factored, non-left-recursive form, or backtracking may be introduced at the cost of potential inefficiency. There are variants such as backtracking recursive descent, which can parse more complex grammars but may suffer from exponential behavior in worst cases.

Recursivedescent is closely related to other top-down parsing concepts, such as LL parsing and predictive parsing. It is commonly used in compilers and language interpreters and remains a foundational technique taught for understanding parsing and language design.