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

Recursive Descent Parsing Concept

How recursive descent parsers map each grammar non-terminal to a parsing function that recognizes it.

Recursive Descent Parsing Concept

You'll learn: How recursive descent parsers map each grammar non-terminal to a parsing function that recognizes it.

The Core Idea

A recursive descent parser is a top-down parsing technique where each non-terminal symbol in your grammar gets its own dedicated parsing function. When that function is called, it tries to recognize and consume the portion of the input that matches its non-terminal's production rules. If a non-terminal appears on the right-hand side of a production, the function simply calls the corresponding function for that non-terminal—hence the "recursive" nature.

How It Works

Think of your grammar as a blueprint and each parsing function as a specialist worker. For example, if your grammar has non-terminals like Expression, Term, and Factor, you'd write three functions: parseExpression(), parseTerm(), and parseFactor().

When parseExpression() encounters a production rule like Expression → Term + Term, it calls parseTerm() twice, checking for a + token in between. Each function is responsible for:

  1. Checking the current token(s)
  2. Consuming tokens that match
  3. Calling other parsing functions for nested non-terminals
  4. Returning success or failure

The Natural Mapping

This approach creates an elegant one-to-one correspondence: grammar structure directly mirrors code structure. The call stack of your parser naturally reflects the derivation tree being constructed. It's like having a phone tree where each person knows exactly whom to call next based on the message type.

Key Takeaway: Recursive descent parsing translates grammar non-terminals directly into functions, where each function recognizes its corresponding syntactic construct by checking tokens and recursively calling other parsing functions as needed.