Recursive Descent Parser:
A Recursive Descent Parser is a top-down parser built from a set of mutually recursive
procedures. Each non-terminal in the grammar has its own function, and parsing is done from
left to right, following leftmost derivations.
Key Concepts
Feature Description
Starts from the start symbol and breaks input down using grammar
Top-Down Parsing
rules
One Function per Rule Each non-terminal has its own recursive function
Uses Lookahead Decisions are based on 1-token lookahead (LL(1) grammar)
Handles Simple
Best suited for grammars without left recursion or ambiguity
Grammars
Backtracking (optional) May backtrack if not predictive (but predictive parsing avoids this)
Limitations
Cannot handle left-recursive grammars
May require grammar rewriting (eliminating left recursion, applying left factoring)
Predictive Parsing: A Special Case
A Predictive Parser is a non-backtracking recursive descent parser:
Requires LL(1) grammar
Grammar must be left-recursion free and left-factored
Grammar Transformation Example
Before (Left-Recursive) After (LL(1), for Recursive Descent)
E→E+T|T E → T E'
T→T*F|F E' → + T E' | ε
F → ( E ) | id T → F T'T' → * F T' | ε
Recursive Descent Algorithm Template
S() {
// Assume production: S → X1 X2 ... Xk
for (i = 1 to k) {
if (Xi is non-terminal)
call Xi();
else if (Xi matches current input)
advance input;
else
error(); // or backtrack
}
}
Example Grammar
E → i E'
E' → + i E' | ε
Function Implementations
void E() {
if (input == 'i') {
input++; // consume 'i'
E_prime(); // handle rest
} else {
error();
}
}
void E_prime() {
if (input == '+') {
input++; // consume '+'
if (input == 'i') {
input++; // consume 'i'
E_prime();
} else {
error();
}
} else {
return; // ε production
}
}
Advantages
Easy to implement
Readable (each function mirrors grammar)
Good for small compilers or interpreters
Integrates well with semantic actions
Disadvantages
Needs LL(1) grammar
Cannot handle ambiguous or left-recursive rules
Error recovery is limited unless explicitly handled
Predictive Parsing:
Predictive Parsing is a type of top-down parsing that does not require backtracking. It predicts
which production to use by looking ahead at the next input token. It is most commonly
implemented using a recursive descent parser or a non-recursive table-driven parser, and it is
based on LL(1) grammars.
Key Characteristics of Predictive Parsing
Feature Description
Top-Down Builds parse tree from the root and expands non-terminals
No
Only one production is chosen using a lookahead token
Backtracking
Feature Description
Parses Left-to-right, constructs Leftmost derivation, and uses 1-token
LL(1) Grammar
lookahead
Deterministic Each parsing decision is uniquely determined
Fast & Efficient Because it avoids ambiguity and backtracking
LL(1) Grammar Requirements
To be parsed by a predictive parser, a grammar must:
1. Be free from left recursion
2. Be left factored
3. Have disjoint FIRST and FOLLOW sets for all applicable productions
Grammar Example (After Left Recursion Removal)
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
This grammar is LL(1) and can be used by a predictive parser.
Predictive Parsing Table (Conceptual View)
Non-Terminal id + * ( ) $
E E → T E' E → T E'
E' E' → + T E' E' → ε E' → ε
T T → F T' T → F T'
T' T' → ε T' → * F T' T' → ε T' → ε
F F → id F→(E)
The parser uses the table to decide which rule to apply based on the current non-terminal and
the lookahead token.
Algorithm for Table-Driven Predictive Parser
stack = [ '$', 'E' ]
input = ['id', '+', 'id', '$']
while stack is not empty:
top = stack.pop()
current_token = input[0]
if top is a terminal:
if top == current_token:
input.pop(0)
else:
error()
elif top is a non-terminal:
rule = parsing_table[top][current_token]
if rule:
push RHS of rule to stack (in reverse order)
else:
error()
Advantages
No backtracking
Faster and more efficient than general top-down parsers
Simple to implement with either recursion or a parsing table
Excellent for use in syntax analyzers of compilers
Limitations
Works only with LL(1) grammars
Not suitable for ambiguous or complex grammars
Sure! Let's break this down in simple terms for better understanding:
Predictive Parser (Pseudo Code)
Here's a step-by-step pseudo-code for a table-driven predictive parser:
Pseudo-Code
Initialize:
Stack ← [ $, StartSymbol ] // Push $ and start symbol (like E) on stack
Input ← string + $ // Append $ at the end of input
Repeat until stack is empty:
Top ← Top of Stack
CurrentToken ← First symbol in Input
If Top is a terminal:
If Top == CurrentToken:
Pop the stack
Advance the input
Else:
Error: Terminal mismatch
Else If Top is a non-terminal:
Look up the parsing table using (Top, CurrentToken)
If there is a rule:
Pop the stack
Push the right-hand side of the rule (in reverse order)
Else:
Error: No matching rule
If stack is empty and input is $:
Parsing successful
Else:
Error: Input not fully consumed
Tracing Input String Using Predictive Parser (Step-by-Step)
Let’s use a small LL(1) grammar and trace an example.
Grammar:
E → T E'
E' → + T E' | ε
T → id
Predictive Parsing Table:
Non-Terminal id + $
E E → T E'
E' E' → + T E' E' → ε
T T → id
Input: id + id $
Initial Stack: [$, E]
Trace Table:
Step Stack Input Action
1 E$ id + id $ E → T E'
2 E' T $ id + id $ T → id
3 E' id $ id + id $ Match id
4 E' $ + id $ E' → + T E'
5 E' T + $ + id $ Match +
6 E' T $ id $ T → id
Step Stack Input Action
7 E' id $ id $ Match id
8 E' $ $ E' → ε
9 $ $ Match $ → ✅ Successful Parse
Simple Explanation:
Start with the start symbol E
Use grammar rules and a lookahead token to choose what to expand
Push rule's right side to stack (in reverse)
Match terminals directly
Use ε rule (empty) if no further input fits
Finish when both input and stack reach $
