Lecture# 07

Compiler Construction
A Simple Syntax-Directed Translator,
(Part-III)

by Safdar Hussain

Topics
• Parsing Types (Top-down parsing, Bottom-up parsing)
• Recursive descent parsing, Predictive Parsing, Predictive Parser (Pseudo Code)
• Tracing the input string using Predictive Parser
 Overview
• This chapter contains introductory material
• Building a simple compiler
– Syntax Definition
– Syntax-Directed Translation
– Parsing
– A Translator for Simple Expressions
– The Lexical Analyzer

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 2

 Parsing
• Parsing = process of determining if a string of tokens
can be generated by a grammar
• For any CF grammar there is a parser that takes at
most O(n3) time to parse a string of n tokens
• Linear algorithms suffice for parsing programming
language
• Top-down parsing “constructs” parse tree from root
to leaves
• Bottom-up parsing “constructs” parse tree from
leaves to root

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 3

 Top-down vs Bottom-up Parsing
• The popularity of Top-down parsers is due to the fact
that efficient parsers can be constructed more easily
by hand using top-down methods.

• Bottom-up parsers can handle a larger class of

grammars and translation schemes, so software tools
for generating parsers directly from grammars often
use bottom-up methods.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 4

Grammar (for Top-down Parsing)

A grammar for subset (some) statements in C and Java

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 5

Grammar (for Top-down Parsing)

A grammar for subset (some) statements in C and Java

Input string: for ( ; expr ; expr ) other

A parse tree according to above grammar

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 6
 Top-down Parsing
• The current terminal being scanned in the input is
frequently referred to as the lookahead symbol.

• Initially, the lookahead symbol is the first, i.e.,

leftmost, terminal of the input string.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 7

Top-down Parsing

Input string: for ( ; expr ; expr ) other Grammar

Lookahead
symbol, at
initial/start

Top-down parsing with scanning the input from left to right 8

 Top-down Parsing (Key Points)
• In general, the selection of a production for a
nonterminal may involve trial-and-error that is, we
may have to try a production and backtrack to try
another production if the first is found to be
unsuitable.
• A production is unsuitable if, after using the
production, we cannot complete the tree to match
the input string.
• A special case of parsing namely the predictive
parsing does not need backtracking.

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 9

 Predictive Parsing
• Recursive descent parsing is a top-down parsing
method
– Every nonterminal has one (recursive) procedure
responsible for parsing the nonterminal’s syntactic
category of input tokens
– When a nonterminal has multiple productions, each
production is implemented in a branch of a selection
statement based on input look-ahead information
• Predictive parsing is a special form of recursive
descent parsing where we use one lookahead token
to unambiguously determine the parse operations

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 10

Example Predictive Parser (Grammar)
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 11

Example Predictive Parser (Pseudo Code)
procedure match(t : token); procedure simple();
begin begin
if lookahead = t then if lookahead = ‘integer’ then
lookahead := nexttoken() match(‘integer’)
else error() else if lookahead = ‘char’ then
end; match(‘char’)
else if lookahead = ‘num’ then
procedure type(); match(‘num’);
begin match(‘dotdot’);
if lookahead in , ‘integer’, ‘char’, ‘num’ - then match(‘num’)
simple() else error()
else if lookahead = ‘^’ then end; Grammar
match(‘^’); match(id)
type  simple
else if lookahead = ‘array’ then
| ^ id
match(‘array’); match(‘[‘); simple();
| array [ simple ] of type
match(‘]’); match(‘of’); type()
simple  integer
else error()
| char
end; | num dotdot num

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 12

Example Predictive Parser (Pseudo Code)
procedure match(t : token); procedure simple();
begin begin
if lookahead = t then if lookahead = ‘integer’ then
lookahead := nexttoken() match(‘integer’)
else error() else if lookahead = ‘char’ then
end; match(‘char’)
else if lookahead = ‘num’ then
procedure type(); match(‘num’);
begin match(‘dotdot’);
if lookahead in , ‘integer’, ‘char’, ‘num’ - then match(‘num’)
simple() else error()
else if lookahead = ‘^’ then end; Grammar
match(‘^’); match(id)
type  simple
else if lookahead = ‘array’ then
| ^ id
match(‘array’); match(‘[‘); simple();
| array [ simple ] of type
match(‘]’); match(‘of’); type()
simple  integer
else error()
| char
end; | num dotdot num
Input string: array [ num dotdot num ] of integer
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 13
 Tracing
Input: array [ num dotdot num ] of integer
To initialize the parser:
set global variable : lookahead = array
call procedure: type

Procedure call to type with lookahead = array results in the actions:

match( array ); match(‘*‘); simple; match(‘+’); match(of); type

Procedure call to simple with lookahead = num results in the actions:

match (num); match (dotdot); match (num)

Procedure call to type with lookahead = integer results in the actions:

simple

Procedure call to simple with lookahead = integer results in the actions:

match ( integer )

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 14

Example Predictive Parser (Execution Step 1) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
Check lookahead type()
and call match

match(‘array’)

Input: array [ num dotdot num ] of integer

lookahead 15
Example Predictive Parser (Execution Step 2) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’)

Input: array [ num dotdot num ] of integer

lookahead 16
Example Predictive Parser (Execution Step 3) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple()

match(‘num’)

Input: array [ num dotdot num ] of integer

lookahead 17
Example Predictive Parser (Execution Step 4) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple()

match(‘num’) match(‘dotdot’)

Input: array [ num dotdot num ] of integer

lookahead 18
Example Predictive Parser (Execution Step 5) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple()

match(‘num’) match(‘dotdot’) match(‘num’)

Input: array [ num dotdot num ] of integer

lookahead 19
Example Predictive Parser (Execution Step 6) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple() match(‘]’)

match(‘num’) match(‘dotdot’) match(‘num’)

Input: array [ num dotdot num ] of integer

lookahead 20
Example Predictive Parser (Execution Step 7) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple() match(‘]’) match(‘of’)

match(‘num’) match(‘dotdot’) match(‘num’)

Input: array [ num dotdot num ] of integer

lookahead 21
Example Predictive Parser (Execution Step 8) Grammar
type  simple
| ^ id
| array [ simple ] of type
simple  integer
| char
| num dotdot num
type()

match(‘array’) match(‘[’) simple() match(‘]’) match(‘of’) type()

match(‘num’) match(‘dotdot’) match(‘num’) simple()

match(‘integer’)
Input: array [ num dotdot num ] of integer

lookahead
22
 Limitations
Q: Can we apply the previous technique to every grammar?
A: NO:

type  simple
| array [ simple ] of type
simple  integer
| array digit
digit  0|1|2|3|4|5|6|7|8|9

consider the string “array 6”

the predictive parser starts with type and lookahead= array
apply production type  simple OR type  array digit ??

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 23

 Question
• Construct recursive-descent parsers, starting with the following
grammar:

• S -> + S S | - S S | a

Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK 24

 Solution
• Construct recursive-descent parsers, starting with the following
grammar: S -> + S S | - S S | a
Recursive-descent parser Continued….
void S() void match(Terminal t)
{ {
switch(lookahead) if(lookahead = t)
{ {
case "+": lookahead = nextTerminal();
match("+"); S(); S(); }
break; else
case "-": {
match("-"); S(); S(); throw new SyntaxException()
break; }
case "a": }
match("a");
break;
default:
throw new SyntaxException();
}
}
25
Safdar Hussain, Lecturer CS, Khwaja Fareed University, RYK
The End

26