Compiler Design

Syntax Analysis
Module 2 (Part-1)
Outline-Half of Module 2

 Role of Parser-Parse Tree - Elimination of Ambiguity – Top Down Parsing –

Recursive Descent Parsing - LL (1) Grammars – Shift Reduce Parsers-
Operator Precedence Parsing
 The role of parser

token
Source Lexical Parse tree Rest of Intermediate
Parser
program Analyzer Front End representation
getNext
Token

Symbol
table
Syntax Analysis

 After lexical analysis (scanning), we have a series of tokens.

 In syntax analysis (or parsing), we want to interpret what those
tokens mean.
 Goal: Recover the structure described by that series of tokens.
 Goal: Report errors if those tokens do not properly encode a structure.
Uses of grammars

E -> E + T | T
T -> T * F | F
F -> (E) | id
After removing Left Recursion

E -> TE’
E’ -> +TE’ | Ɛ
T -> FT’
T’ -> *FT’ | Ɛ
F -> (E) | id
 Context free grammars

 Terminals
 Nonterminals
 Start symbol expression -> expression + term
 productions expression -> expression – term
expression -> term
term -> term * factor
term -> term / factor
term -> factor
factor -> (expression)
factor -> id
Derivations

 Productions are treated as rewriting rules to generate a string

 Rightmost and leftmost derivations
 E -> E + E | E * E | -E | (E) | id
 Derivations for –(id+id)
 E => -E => -(E) => -(E+E) => -(id+E)=>-(id+id)
Parse trees

 -(id+id)
 E => -E => -(E) => -(E+E) => -(id+E)=>-(id+id)
Ambiguity

 For some strings there exist more than one parse tree
 Or more than one leftmost derivation
 Or more than one rightmost derivation
 Example: id+id*id
Example of ambiguity

 E -> E + E
 E -> E * E
 E -> id
 For the string id + id * id
 We can't use associativity here as there are two different operators, +
and *. Hence, we need to use "Precedence".
 The order of evaluation must be: id + (id * id) as * has more precedence
than +. The operator with the highest priority must be evaluated first.
Hence, the operators with high priority are to be arranged in the lower
levels of the parse tree.
 If id = 2:
 If + id * id = 2 + 2 * 2 = 6
Hence, the first
derivation tree is the
correct parse tree.
Converting into unambiguous
grammar
 We should write the grammar so that all the highest priority
operators stay in lower levels. Every production should follow a
recursion based on the associativity of the operator used.
 +, -, *, / are left associative operators. Hence, the productions using
these operators must follow left recursion
 ^ and = are right-associative operators. Hence, the productions using
these operators must follow the right recursion.
Elimination of left recursion

 A grammar is left recursive if it has a non-terminal A such that there is

a derivation A=> Aα +

 Top down parsing methods cant handle left-recursive grammars

 A simple rule for direct left recursion elimination:
 For a rule like:
 A -> A α|β
 We may replace it with
 A -> β A’
 A’ -> α A’ | ɛ
Left factoring

 Left factoring is a grammar transformation that is useful for

producing a grammar suitable for predictive or top-down parsing.
 Consider following grammar:
 Stmt -> if expr then stmt else stmt
 | if expr then stmt
 On seeing input if it is not clear for the parser which production
to use
 We can easily perform left factoring:
 If we have A->αβ1 | αβ2 then we replace it with
 A -> αA’
 A’ -> β1 | β2
Left factoring (cont.)
 Algorithm
 For each non-terminal A, find the longest prefix α common to two or
more of its alternatives. If α<> ɛ, then replace all of A-productions A-
>αβ1 |αβ2 | … | αβn | γ by
 A -> αA’ | γ
 A’ -> β1 |β2 | … | βn
 Example for Left Factoring

 A → aAB / aBc / aAc

 This can be written as
 A → aA’
 A’ → AB / Bc / Ac

Again, this is a grammar with

common prefixes.
A → aA’
A’ → AD / Bc
D→B/c
This is a left factored grammar.
Parsing Techniques
Top Down Parsing
 Introduction

 A Top-down parser tries to create a parse tree from the root

towards the leafs scanning input from left to right
 It can be also viewed as finding a leftmost derivation for an input
string
 Example: id+id*id

E -> TE’ E E E E E E
lm lm lm lm lm
E’ -> +TE’ | Ɛ T E’ T E’ T E’ T E’ T E’
T -> FT’
T’ -> *FT’ | Ɛ F T’ F T’ F T’ F T’ + T E’

F -> (E) | id id id Ɛ id Ɛ
 Recursive descent parsing

 Consists of a set of procedures, one for each nonterminal

 Execution begins with the procedure for start symbol
 A typical procedure for a non-terminal

void A() {
choose an A-production, A->X1X2..Xk
for (i=1 to k) {
if (Xi is a nonterminal
call procedure Xi();
else if (Xi equals the current input symbol a)
advance the input to the next symbol;
else /* an error has occurred */
}
}
Recursive descent parsing (cont)

 General recursive descent may require backtracking

 The previous code needs to be modified to allow backtracking
 In general form it cant choose an A-production easily.
 So we need to try all alternatives
 If one failed the input pointer needs to be reset and another alternative
should be tried
 Recursive descent parsers cant be used for left-recursive grammars
Example

S->cAd
A->ab | a Input: cad

S S S

c A d c A d c A d

a b a
LL(1) Grammars

 Predictive parsers are those recursive descent parsers needing no

backtracking
 Grammars for which we can create predictive parsers are called LL(1)
 The first L means scanning input from left to right
 The second L means leftmost derivation
 And 1 stands for using one input symbol for lookahead

*
Finding FIRST()
Finding FOLLOW()
Construction of predictive parsing
table
 Create a Table with Non Terminals on the Rows and Terminals and $ on
the columns.
 For each production A->α in grammar do the following:
1. For each terminal a in First(α) add A-> in M[A,a]
2. If ɛ is in First(α), then for each terminal b in Follow(A) add A-> ɛ to M[A,b]. If
ɛ is in First(α) and $ is in Follow(A), add A-> ɛ to M[A,$] as well
 If after performing the above, there is no production in M[A,a] then set
M[A,a] to error
Exercise-1

FIRST FOLLOW
 S->aABb {a} {$}
 A->c/Ɛ
{c, Ɛ} {d,b}
 B->d/Ɛ
{d, Ɛ} {b}
a b c d $
S S->aABb
A A->Ɛ A->c A->Ɛ
B Parse the string ‘acdb’
B->Ɛ B->d
 Parsing the string ‘acdb’

Stack Input Output

$S acdb$ S->aABb
$bBAa acdb$ Pop a
$bBA cdb$ A->c
$bBc cdb$ Pop c
$bB db$ B->d
$bd db$ Pop d
$b b$ Pop b
$ $ Accept
 Exercise-2

E -> TE’
E’ -> +TE’ | Ɛ
T -> FT’
T’ -> *FT’ | Ɛ
F -> (E) | id
 First Follow

E -> TE’ E {id, (} { ), $}

E’ {+, ɛ} { ), $}
E’ -> +TE’ | Ɛ {id, (} {+,), $}
T -> FT’ T
T’ {*,ɛ} {+,), $}
T’ -> *FT’ | Ɛ {*, +, ), $}
F -> (E) | id F {id, (}
Input Symbol
Non -
terminal id + * ( ) $
E E -> TE’ E -> TE’

E’ E’ -> +TE’ E’ -> Ɛ E’ -> Ɛ

T T -> FT’ T -> FT’

T’ T’ -> Ɛ T’ -> *FT’ T’ -> Ɛ T’ -> Ɛ

F F -> id F -> (E)

Parsing Example id +id
 Exercise-3 (I/P string is ibta)
S -> iEtSS’ | a
S’ -> eS | Ɛ
E -> b

Input Symbol
Non -
terminal a b e i t $
S S -> a S -> iEtSS’

S’ S’ -> Ɛ S’ -> Ɛ
S’ -> eS
E E -> b
Exercise-4

( ) a $
 S->(L)/a S S->(L) S->a
 L->SL’ L L->SL’ L->SL’
 L’->)SL’/ Ɛ L’ L’->)SL’
L’-> Ɛ

FIRST (S) = {(,a} FOLLOW(S)= {),$}

FIRST (L) = {(,a} FOLLOW(L)= {)}
FIRST (L’) = {),Ɛ} FOLLOW(L’)= {)}
 Parse the string (a)
Limitation

 After the construction of the parsing table, if for any non-terminal

symbol in the table we have more than one production rule for any
terminal symbol in the table column, then the grammar is not LL(1).
Otherwise, then grammar is considered as LL(1).
Non-recursive predicting parsing

a + b $

Predictive
parsing output
stack X
Y program
Z
$
Parsing
Table
M
Predictive parsing algorithm

Set ip point to the first symbol of w;

Set X to the top stack symbol;
While (X<>$) { /* stack is not empty */
if (X is a) pop the stack and advance ip;
else if (X is a terminal) error();
else if (M[X,a] is an error entry) error();
else if (M[X,a] = X->Y1Y2..Yk) {
output the production X->Y1Y2..Yk;
pop the stack;
push Yk,…,Y2,Y1 on to the stack with Y1 on top;
}
set X to the top stack symbol;
}
Bottom-up Parsing
 Introduction

 Constructs parse tree for an input string beginning at the leaves

(the bottom) and working towards the root (the top)
 Example: id*id

E -> E + T | T id*id F * id T * id T*F F E

T -> T * F | F
T*F F
F -> (E) | id id F F id

id id F id T*F

id F id

id
Shift-reduce parser

 The general idea is to shift some symbols of input to the stack until a
reduction can be applied
 At each reduction step, a specific substring matching the body of a
production is replaced by the nonterminal at the head of the production
 The key decisions during bottom-up parsing are about when to reduce
and about what production to apply
 A reduction is a reverse of a step in a derivation
 The goal of a bottom-up parser is to construct a derivation in reverse:
 E=>T=>T*F=>T*id=>F*id=>id*id
 Handle pruning

 A Handle is a substring that matches the body of a production and

whose reduction represents one step along the reverse of a
rightmost derivation

Right sentential form Handle Reducing production

id*id id F->id
F*id F T->F
T*id id F->id
T*F T*F E->T*F
Shift reduce parsing

 A stack is used to hold grammar symbols

 Handle always appear on top of the stack
 Initial configuration:
Stack Input
$ w$
 Acceptance configuration
Stack Input
$S $
 Shift reduce parsing (cont.)

 Basic operations:
 Shift
 Reduce Stack Input Action
 Accept $ id*id$ shift
 Error $id *id$ reduce by F->id
 Example 1: id*id $F *id$ reduce by T->F
$T *id$ shift
$T* id$ shift
E-> E+T/T $T*id $ reduce by F->id
T->T*F/F $T*F $ reduce by T->T*F
F->id reduce by E->T
$T $
$E $ accept
Note: You don't need left-recursion elimination if you use shift-reduce parsing
 Example 2

Stack Input Action

E->E-E $ id-id*id$ Shift
E->E*E $id -id*id$ Reduce
E->id
$E -id*id$ Shift
$E- id*id$ Shift
String
$E-id *id$ Reduce
id-id*id
$E-E *id$ Reduce
$E *id$ Shift
$E* id$ Shift
$E*id $ Reduce
$E*E $ Reduce
$E $ Accept
Example 3

S->(L)/a
L->L,S/S
Parse the input string (a, (a,a))
Stack Input Action
$ (a,(a,a))$ Shift
$( a,(a,a))$ Shift
$(a ,(a,a))$ Reduce Continue this
$(S ,(a,a))$ Reduce parsing table and
$(L ,(a,a))$ Shift find the answer
$(L, (a,a))$ Shift
$(L,( a,a))$ Shift
. . .
. . .
Example 4

 E –> 2E2
E –> 3E3
E –> 4
 Perform Shift Reduce parsing for input string “32423”.
Operator Precedence Parsing

 Operator precedence parsing is a type of Shift Reduce Parsing. In

operator precedence parsing, an operator grammar and an input
string are fed as input to the operator precedence parser, which
may generate a parse tree. Note that a parse tree will only be
generated if the input string gets accepted.
 In operator precedence parsing, the shift and reduce operations
are done based on the priority between the symbol at the top of
the stack and the current input symbol.
 The operator precedence parser performs the operator
precedence parsing using operator grammar.
Rules for performing Operator
Precedence parsing

A grammar is said to be an operator grammar if it follows

these two properties:
[Link] should be no ε (epsilon) on the right-hand side of
any production.
[Link] should be no two non-terminals adjacent to each
other.
Examples of operator grammar are A + B, A - B, A x B, etc.
Relations

 There are three operator precedence relations.

 a ⋗ b: This relation implies that terminal “a” has higher precedence
than terminal “b”.
 a ⋖ b: This relation implies that terminal “a” has lower precedence than
terminal “b”.
 a ≐ b: This relation implies that terminal “a” has equal precedence to
terminal “b”.
 Now, let’s see the steps to perform the operator precedence parsing.
Precedence Table

 A precedence table is used in operator precedence parsing to establish

the relative precedence of operators and to resolve shift-reduce conflicts
during the parsing process.
 The table instructs the parser when to shift (consume the input and
proceed to the next token) and when to reduce (apply a production rule
to reduce a set of tokens to a non-terminal symbol).
 It is an essential Data Structure for building a shift-reduce parser.
Example 1

 T → T+T
 T → T*T
 T → id

+ * id $
+ ⋗ ⋖ ⋖ ⋗
* ⋗ ⋗ ⋖ ⋗
Id ⋗ ⋗ — ⋗
$ ⋖ ⋖ ⋖ A
 Parsing the string id+id*id

Stack Relation Input Buffer Parsing Action

$ ⋖ id+id*id$ Shift
$id ⋗ +id*id$ Reduce by T → id
$T ⋖ +id*id$ Shift
$T+ ⋖ Id*id$ Shift
$T+id ⋗ *id$ Reduce by T → id
$T+T ⋖ *id$ Shift
$T+T* ⋖ id$ Shift
$T+T*id ⋗ $ Reduce by T → id
$T+T*T ⋗ $ Reduce by T → T *
T
$T+T ⋗ $ Reduce by T → T +
Using functions

 Compilers using operator-precedence parsers need not store the table of

precedence relations. In most cases, the table can be encoded by two
precedence functions f and g that map terminal symbols to integers. We
attempt to select f and g so that, for symbols a and b. 1. f (a) < g(b)
whenever a g(b) whenever a ·> b.
Algorithm for Constructing
Precedence Functions:
1. Create functions fa for each grammar terminal a and for the end of
string symbol.
2. Partition the symbols in groups so that fa and gb are in the same group
if a = b (there can be symbols in the same group even if they are not
connected by this relation).
Algorithm contd..

1. Create a directed graph whose nodes are in the groups, next for each
symbols a and b do: place an edge from the group of gb to the group
of fa if a b place an edge from the group of fa to that of gb.
2. If the constructed graph has a cycle then no precedence functions
exist. When there are no cycles collect the length of the longest paths
from the groups of fa and gb respectively.
Precedence Graph
LEADING and TRAILING
Computation of LEADING:
• Leading is defined for every non-terminal.
• Terminals that can be the first terminal in a string derived from that
non-terminal.
• LEADING(A)={ a| A=>+ γaδ },where γ is ε or any non-terminal,
=>+ indicates derivation in one or more steps, A is a non-terminal.
Computation of TRAILING:
• Trailing is defined for every non-terminal.
• Terminals that can be the last terminal in a string derived from that
non-terminal.
• TRAILING(A)={ a| A=>+ γaδ },where δ is ε or any non-terminal,
=>+ indicates derivation in one or more steps, A is a non-terminal.
Example
Compute LEADING and TRAILING:
Example OP using Leading and
Trailing
 E→E + T
 E→T
 T→T * F
 T→F
 F→(E)
 F→id
Parse the string (id+id)*id$
If the grammar is not according to OP
rules, convert it
 P->SR/S
 R->bSR/bS
 S->WbS/W
 W->L*W/L
 L->id
 Converting this to OP Grammar
 P->SbP/SbS/S
 S->WbS/W
 W->L*W/L
 L->id