Course contentsShow
← Computer Science
Lesson 1952 of 2,87244. Lexical Analysis and ParsingFree lesson

Implementing Recursive Descent Functions

Writing parsing functions that match terminals, call other functions for non-terminals, and handle alternatives.

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:

  1. Match terminals directly against input tokens
  2. Call other functions for non-terminals
  3. 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.