recursive-descent parsing

Imagine each grammar rule becoming a little helper function that knows how to recognize one kind of thing, and these helpers calling each other the way the rules refer to each other. To recognize an Expression you call parseExpression, which calls parseTerm, which calls parseFactor, which might call parseExpression right back when it sees a parenthesis. Recursive-descent parsing is exactly this: a top-down parser written as a set of mutually recursive functions, one per nonterminal.

Each function tries to match its nonterminal against the current position in the token stream. It looks at the next token, decides which production to follow, consumes the tokens that production demands, and calls the functions for any nonterminals inside that production. A function for E -> num | ( E ) checks the next token: if it is a number it consumes it; if it is a left parenthesis it consumes it, calls parseE recursively, then expects a right parenthesis. The program's own call stack does the remembering, mirroring exactly the nesting of the parse tree. When one look-ahead token always suffices to pick the production, this is called predictive recursive descent and needs no backtracking; without that property the parser may have to try a production and back up if it fails.

Recursive descent is the parsing technique most people meet first, and many real compilers, including production C and C-sharp front ends, use a hand-written recursive-descent parser. The appeal is directness: the code looks like the grammar, errors are easy to report precisely, and you can drop in custom handling exactly where you need it. The cost is that, like all top-down methods, it cannot handle left recursion, and a hand-written parser must be maintained by hand as the language grows.