Implementing Recursive Descent Functions
What you'll learn: How to translate grammar rules into actual parsing functions that recognize language structures by matching terminals and recursively calling other functions for non-terminals.
From Grammar to Code
Now that you understand recursive descent parsing conceptually, it's time to write the actual functions. Each non-terminal in your grammar becomes a function. These functions do three things:
- Match terminals directly against input tokens
- Call other functions for non-terminals
- Handle alternatives (the
|choices in grammar rules)
The Pattern
Think of each parsing function as a mini-recognizer for its grammar rule. If your grammar says:
expression → term '+' term
term → NUMBER
You'd write two functions. The expression() function calls term(), checks for a '+' token, then calls term() again. The term() function checks if the current token is a NUMBER.
Structure of a Recursive Descent Function
Each function typically:
- Checks what the current token is (using lookahead)
- Consumes tokens when they match (advances the input pointer)
- Calls other parsing functions for non-terminals in the rule
- Returns success/failure or constructs a parse tree node
- Backtracks or reports errors when matches fail
For alternatives (A → B | C), the function tries the first option; if that fails, it tries the second. This is why predictive parsing (knowing which alternative to choose) makes the parser more efficient.
The beauty of this approach is that the recursive structure of the grammar naturally maps to the call stack of your program—each nested rule becomes a nested function call.
Key Takeaway: Recursive descent functions directly mirror grammar rules: match terminals with token checks, handle non-terminals with function calls, and use conditionals or try-catch patterns for alternatives.