Learn Compiler Design : From B K Sharma

Unit II
Top-Down Parsing with
Recursive-Decent Parser
Learn Compiler Design : From B K Sharma

Unit II: Syllabus

• Syntax Analysis and Syntax Directed
Translation
• Syntax Analysis:
– CFGs
– Top Down Parsing
– Brute Force Approach
– Recursive Descent Parsing
– Transformation on the grammars
Learn Compiler Design : From B K Sharma

Unit II: Syllabus

– Predictive Parsing
– Bottom Up Parsing
– Operator Precedence Parsing
– LR Parsers
• SLR,
• LALR
• LR
• Parser Generator
Learn Compiler Design : From B K Sharma

Unit II: Syllabus

• Syntax Directed Definitions
– Construction of syntax trees
– Bottom Up Evaluation of S-attributed
definition
– L-attribute Definition
– Top Town translation
– Bottom Up Evaluation of inherited attributes
– Recursive Evaluation
– Analysis of Syntax Directed Definition
Learn Compiler Design: From B. K. Sharma
Summary of Lesson 16: Ambiguity in CFG and
Removal
1: In the top down parsing, the parsing starts
from the start symbol builds a leftmost derivation
for an input string.
2: In the Bottom up parsing, the parsing starts
from input symbol, builds a rightmost derivation in
reverse for the start symbol of the grammar.
3: Top-down parsing with full backup is a "brute-
force" method of parsing
4: The problem with brute-force approach of top-
down parsing is that it may require backtracking to
correct the wrong choice of production
Learn Compiler Design: From B. K. Sharma

Mapping of Lesson with Course Outcome

(CO)
Lesson CO3
Lesson 17: Top Down Understand LL, LR,
Parsing with and SLR parsing
recursive-decent techniques.
parser
Learn Compiler Design : From B K Sharma

Parsing Methods

Top-Down Bottom-Up
Recursive-descent parsing Shift-reduce parsing
Predictive Parsing Operator precedence parsing
LR parsing
LL Parsing
Simple LR Parsing

Look Ahead (LA) LR parsing

Canonical LR Parsing (LR(1))
Learn Compiler Design : From B K Sharma

Top-Down Parsing

Backtracking Non-Backtracking

Recursive Descendant Parsing Predictive Parsing

LL Parsing
The term descent refers to the direction in which
the parse tree is built.
A special case of recursive-descent parser that
needs no backtracking is called a predictive parser
a.k.a. LL parsing.
Learn Compiler Design : From B K Sharma

What is recursive decent parser?

It uses recursive functions to
recognize the input and may or may not
use Backtracking.

The form of recursive descent parser

that does not require backtracking is
also called predictive Parser.
Learn Compiler Design : From B K Sharma

What is recursive decent parser?

Associates a procedure with each
nonterminal in the grammar.
Makes recursive calls to parse the
input string.

A recursive call is one where procedure

A calls itself or calls procedure B which
then calls procedure A again
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Learn Compiler Design : From B K Sharma
Let us consider the following grammar:
E → TE′ Procedure E()
E′ → +TE′ | - TE’ | ε {
G T → FT′ T();
T′ →∗ FT′| / FT’ | ε E’();
F → (E) | number }

Procedure T() procedure E’()

{ {
F(); if NextInputChar = "+" or "-" then
T’(); read(NextInputChar);
} T();
E’();
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:
E → TE′
E′ → +TE′ | - TE’ | ε
G T → FT′
T′ →∗ FT′| / FT’ | ε
F → (E) | number
Procedure T’()
{
if NextInputChar = “*" or “/" then
read(NextInputChar);
F();
T’();
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:
E → TE′ Procedure F()
E′ → +TE′ | - TE’ | ε {
if NextInputChar = “(" then
G T → FT′ read(NextInputChar);
T′ →∗ FT′| / FT’ | E();
F → (E) | number if NextInputChar = “)" then
read(NextInputChar);
else
print(“Syntax Error”);
else if NextInputChar = “number" then
read(NextInputChar);
else
print(“Syntax Error”);
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Parsing of Input E 1 + (2 * 3) / 4
T E’

F T’
+ E’
T
ε
1 ε
F T’

( E ) / F T’

4 ε
T E’

F T’ ε

2 * F T’

ε
3
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Tracing the Parser
Let us consider the following input: 1 + (2 * 3) /
4
NextInputChar=“1”
Call E ()
{
Call T()
Call F();
NextInputChar = "+" /* Match 1 with F */
Call T’(); /* Match epsilon */
Call E’();
NextInputChar = "(" /* Match + */
Call T()
Call F();
/* Match (, looking for E ) */
NextInputChar = "2”
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Tracing the Parser
Call E 1 + (2 * 3) / 4
Call T
Call F
/* Match 2 with F */
NextInputChar = "*“
Call T’
/* Match * */
NextInputChar = "3“
Call F
/* Match 3 with F */
NextInputChar = ")“
Call T’
/* Match epsilon */
Call E’
/* Match epsilon */
NextInputChar = "/" /* Match ")" */
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Tracing the Parser
1 + (2 * 3) / 4
Call T’
NextInputChar = "4" /* Match "/" */
Call F /* Match 4 with F */
NextInputChar = EOF
Call T’ /* Match epsilon */
Call T’ /* Match epsilon */
Call E’ /* Match epsilon */
/* Match EOF*/
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:
In this grammar, the non-terminals E  T + E | T
are T and E. T  ( E )
G | int
For production E  T
| int * T
bool E1()
{ For production E  T + E
return T();
} bool E2()
{
return T() && term(PLUS) && E();
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:
Functions for non-terminal T(E) E  T + E | T
bool T1() T  ( E )
{ | int
return term(OPEN) && E() && | int * T
term(CLOSE);
}

Functions for non-terminal Tint

bool T2()
{
return term(INT);
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:

Functions for non-terminal T int * T E  T + E | T

T  ( E )
| int
bool T3() | int * T
{
return term(INT) && term(TIMES)
&& T();
}
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

Let us consider the following grammar:

stmt  if expr then stmt tail S→iEtST

| while ( expr ) stmt |w(E)S
stmt()
{
if (lookahead == ‘if’)
{match(‘if’); expr(); match(‘then’); stmt(); tail(); }
else (lookahead == ‘while’)
{match(‘while’); match(‘(‘); expr(); match(‘)’);
stmt(); }
else error();
}
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

Minute Paper
Write down the algorithm using Recursive
procedures to implement the following
Grammar.
E → TE′
E′ → +TE′
T → FT′
T′ →∗ FT′|ε
F → (E)|id
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

Minute Paper: ANSWER
E → TE′
E′ → +TE′
T → FT′
T′ →∗ FT′|ε
F → (E)|id
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

Minute Paper: ANSWER
E → TE′
E′ → +TE′
T → FT′
T′ →∗ FT′|ε
F → (E)|id
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

Minute Paper: ANSWER
E → TE′
E′ → +TE′
T → FT′
T′ →∗ FT′|ε
F → (E)|id
Learn Compiler Design : From B K Sharma

Top-Down Parsing: Recursive Descent Parser

To implement a recursive descent parser,
the grammar must hold the following
properties:
It should not be left recursive.
It should be left-factored.
Language should have a recursion facility.
If the grammar is not left-factored, the
recursive descent parser will have to use
backtracking.
Learn Compiler Design: From B. K. Sharma
Summary of Lesson 17: Top Down Parsing with
recursive decent parser
1: A recursive decent parser associates a procedure
with each non-terminal in the grammar and makes
recursive calls to parse the input string.

2: A special case of recursive-descent parser that

needs no backtracking is called a predictive parser
a.k.a. LL parsing.

3: To implement a recursive descent parser, the

grammar should not be left recursive, it should be left
factored.

4. If the grammar is not left-factored, the recursive

descent parser will have to use backtracking.
Learn Compiler Design : From B K Sharma

Read PPT named Working of Predictive

Parser