Unit 2 - Session 3

18CSC304J
COMPILER DESIGN
UNIT 2
SESSION 3
Topics that will be covered in this Session
• Elimination of Ambiguity
• Elimination of Left Recursion
• Left Factoring
ELIMINATION OF
AMBIGUITY
Eliminating Ambiguity
• There exists no general algorithm to remove ambiguity from grammar
• To check a grammar for ambiguity, we try finding a string that has more than one parse tree. If
any such string exists, then the grammar is ambiguous
• Causes such as left recursion, common prefixes etc. makes the grammar ambiguous
• The removal of these causes may convert the grammar into unambiguous grammar
• However, it is not always compulsory
• Sometimes an ambiguous grammar can be rewritten to eliminate the ambiguity

Eliminating Ambiguity – Example 1
Eliminate ambiguity from the “dangling-else” grammar
• Here “other” stands for any other statement
• Parse tree for the expression

Eliminating Ambiguity – Example 1 – cont…
• Consider the expression
Parse Tree 1
Parse Tree 2
As there are two parse trees for the given
expression, the grammar is ambiguous

Eliminating Ambiguity – Example 1 – cont..
• We can rewrite the dangling-else grammar as the following unambiguous grammar
• The idea is that a statement appearing between a then and an else must be matched
• That is, an interior statement must not end with an unmatched or open then
• A matched statement is either an if-then-else statement containing no open statements or it is

any other kind of unconditional statement
Eliminating Ambiguity – Example 1 – cont..
• Now the expression has only one parse tree

Eliminating Ambiguity – Example 2
Eliminate ambiguity from the “expression” grammar
E → E + E | E * E | ( E ) | id
The reason for ambiguity in this grammar is
• The precedence and associative rules are not imposed in the grammar
We can rewrite the grammar by imposing precedence and associative rules as follows
E→E+T|T
T→T*F|F
F → ( E ) | id
ELIMINATION OF LEFT
RECURSION
Eliminating Left Recursion
• A grammar is left recursive if it has a nonterminal A such that there is a derivation
• A production in which the leftmost symbol on the right side is the same as the nonterminal on
the left side of the production is called a left-recursive production
Eg : E → E + T
• Top down parsing methods cannot handle left-recursive grammars
• So, a transformation is needed to eliminate left recursion
• Left recursion can be eliminated by rewriting the grammar

Rule for Eliminating Immediate Left Recursion
• Suppose we have the following productions:
A → A1 | A2 | … | Am | β1 | β2 | … | βn
• To eliminate left recursion, we can rewrite the grammar as follows
A → β1 A′| β2 A′| … | βn A′
A′ → 1 A′ | 2 A′ | …. | m A′ | ε
• This procedure eliminates all immediate left recursion from the A and A′ productions, but it
does not eliminate left recursion involving derivations of 2 or more steps
Eliminating Immediate Left Recursion – Example
• Eliminate left recursion from the given grammar
E→E+T|T
T→T*F|F
F → ( E ) | id
After eliminating the immediate left recursion, we get
E → T E′
E′ → + T E′ | ε
T → F T′
T′ → * F T′ | ε
F → ( E ) | id
Eliminating Left Recursion Involving Derivations
Eliminating Left Recursion Involving Derivations – Example 1
Eliminate left recursion from the given i=2
grammar
Substitute S productions in A
S → Aa | b
A → Ac | Aad | bd | ε
A → Ac | Sd | ε
Eliminate immediate left recursion in A
Step 1 : Order the non-terminals
A → bdA′ | A′
1–S
A′ → cA′ | adA′ | ε
2–A
The grammar after eliminating left
i=1 recursion is
Check if there is immediate left recursion S → Aa | b

in S. If so eliminate it
A → bdA′ | A′
There is no immediate left recursion in S
A′ → cA′ | adA′ | ε
Eliminating Left Recursion Involving Derivations – Example 2
Eliminate left recursion from the given i=2
grammar
Substitute S productions in L (only where it
S→(L)|a starts with S)
L→L,S|S L→L,S|(L)|a
Step 1 : Order the non-terminals Eliminate immediate left recursion in L
1–S L → ( L ) L′ | a L′
2–L L′ → , S L′ | ε
i=1 The grammar after eliminating left

recursion is
Check if there is immediate left recursion
in S. If so eliminate it S→(L)|a
There is no immediate left recursion in S L → ( L ) L′ | a L′
L′ → , S L′ | ε
LEFT FACTORING
Left Factoring
• Left Factoring is a grammar transformation that is useful for producing a grammar suitable for
predictive parsing
• Left Factoring will be done when more than one production of a non-terminal has the same
prefix (common prefix)
• The basic idea is that when it is not clear which of the two alternative productions to use to
expand a non terminal A, we may be able to rewrite the A-productions to defer the decision
until we have seen enough of the input to make the right choice
• For example, in the above grammar, on seeing the input if, we cannot immediately tell which
production to choose to expand stmt
Left Factoring - Algorithm
Left Factoring – Examples
Example 1 Example 2
Left factor the grammar given below: Left factor the grammar given below:
S→iEtSeS|iEtS|a A→aAB|aBc|aAc
E→b
The grammar after left factoring is
S → i E t S S′ | a A → a A′
S′ → e S | ε A′ → A B | B c | A c
E→b
Left Factoring – Examples – cont..
Example 3 Example 4
Left factor the grammar given below: Left factor the grammar given below:
S→cAd S→aSa|aSb|a|b
A→ab|a
S→cAd S → a S′ | b
A → a A′ S′ → S a | S b | ε
A′ → b | ε

Unit 2 - Session 3

Uploaded by

Copyright:

Available Formats

Unit 2 - Session 3

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 2 - Session 3

Uploaded by

Copyright:

Available Formats

18CSC304J

• There exists no general algorithm to remove ambiguity from grammar

• However, it is not always compulsory

• Sometimes an ambiguous grammar can be rewritten to eliminate the ambiguity

• Here “other” stands for any other statement

• Parse tree for the expression

As there are two parse trees for the given

expression, the grammar is ambiguous

• A matched statement is either an if-then-else statement containing no open statements or it is

• Now the expression has only one parse tree

The reason for ambiguity in this grammar is

• A grammar is left recursive if it has a nonterminal A such that there is a derivation

• Top down parsing methods cannot handle left-recursive grammars

• So, a transformation is needed to eliminate left recursion

• Left recursion can be eliminated by rewriting the grammar

• Suppose we have the following productions:

A → A1 | A2 | … | Am | β1 | β2 | … | βn

• To eliminate left recursion, we can rewrite the grammar as follows

After eliminating the immediate left recursion, we get

Check if there is immediate left recursion S → Aa | b

Step 1 : Order the non-terminals Eliminate immediate left recursion in L

i=1 The grammar after eliminating left

There is no immediate left recursion in S L → ( L ) L′ | a L′

The grammar after left factoring is

The grammar after left factoring is

The grammar after left factoring is

The grammar after left factoring is

You might also like