Scribd
Upload
23 views24 pages

FAFL Final Lecture 26.1 CMH

Uploaded by

shruthi g
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
23 views24 pages

FAFL Final Lecture 26.1 CMH

Uploaded by

shruthi g
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 24

Established as per the Section 2(f) of the UGC Act, 1956

Approved by AICTE, COA and BCI, New Delhi

Lecture 26.1
Substitution, Removal of useless and Left
Recursion
S c h o o l o f C o m p u t i n g a n d I n f o r m a t i o n Te c h n o l o g y

Chaithra M H

AY:2020-2021
OUTLINE

Recap of Previous Lecture

Topic of the Lecture

Objective and Outcome of Lecture

Lecture Discussion

• Substitution with examples


• Definition of Left Recursion with examples
• Definition of useless productions with examples
• Summary
• Quiz
Substitution, Removal of useless and Left
Recursion
Recap of Previous Lecture
• Introduction to
Ambiguous grammar
• Definition of Ambiguous
grammar
Recursion
• Definition of useless and Left
Unambiguous grammar
Removal of
Substitution,
• Examples-ambiguous Course Description
grammar
• Differences between
ambiguous and
unambiguous grammar RECAP OF PREVIOUS LECTURE
Substitution, Removal of useless and Left
Recursion
To p i c o f t h e L e c t u r e
• Substitution with
examples
• Definition of Left
recursion with Recursion
useless and Left
examples Removal of
Substitution,
• Definition of Useless
productions with
examples
• Summary
TOPIC OF THE LECTURE
• Quiz
Substitution, Removal of useless and Left
Recursion
A Substitution rule
A SUBSTITUTION - RULE

Consider the grammar productions as shown


below Equivalent grammar is

Aa Aa

A  aaA A  aaA

A  abBc Substitute B in A A  ababbAc

B  abbA A  abbA

B b
A SUBSTITUTION - RULE

In general
AxBz

B  y1 | y2 |. . . . . | yn

Substitute

Equivalent
A  x y1 z | x y2 z|. . . . . | x yn z grammar
A SUBSTITUTION RULE
Example-1
Consider the productions and simplify the grammar by substitution method :
AaBa
Bab|b

Solution The RHS of production contains B, so B can be replaced. Grammar will


be A  a a b a | a b a

Resulting grammar is G = (V, T, P, S) where


V={A}
T={a,b}
P = { A  a a b a | a b a}
S = { A } is the start symbol
Substitution, Removal of useless and Left
Recursion
Left Recursion definition
LEFT RECURSION - DEFINITION

Definition : A grammar G is said to be left-recursive if there is some non-terminal A

such that A + Aα , if the first symbol on RHS in a sentential form is a variable and if
the derivation is obtained from the same non-terminal then grammar is having left
recursion.

If grammar contains Left recursion, then


how to eliminate Left recursion??
Substitution, Removal of useless and Left
Recursion
Steps to eliminate Left recursion
S T E P S T O E L I M I N AT E L E F T R E C U R S I O N

Consider the A-production of the form


A  A α1| A α2| A α3|. . . | A αn | β1| β2| β3|…. | βm

where βi ‘s do not start with A.

Then A can be replaced by


A  β1 A' | β2 A' | β3 A' | . . . | βm A'

A'  α1 A' | α2 A' | α3 A' |. . . | αnA‘ | ԑ


Substitution, Removal of useless and Left
Recursion
Problems on left recursion
PROBLEMS ON LEFT RECURSION
Example - 1
Eliminate the Left Recursion from the following grammar.
EE+T|T
TT*F|F
F  (E) | id
Solution The Left Recursion can be eliminated as shown below:
Given Substitution Without left recursion Resulting grammar:
A  A αi | βi A  βi A' and A'  α1 A' | ԑ
E  T E’
EE+T|T A=E, E  T E’
α1 = +T, E’  + T E’ |ԑ E’  + T E’ |ԑ
β1 = T
T  F T’
TT*F|F A=T, T  F T’
α1 = *F, T’  * FT’ |ԑ T’  * FT’ |ԑ
β1 = F F  ( E ) | id
F  ( E ) | id Not applicable F  ( E ) | id
PROBLEMS ON LEFT RECURSION
Example - 2
Consider the following grammar and eliminate left recursion-
A→ABd|Aa|a
B→Be|b

Solution The Left Recursion can be eliminated as shown below:

Given Substitution Without left recursion Resulting grammar:


A  A αi | βi A  βi A' and A'  α1 A' | ԑ
A → a A’
A→ABd/Aa/a A=A, A  a A’
α1 = B d, A’  B d A’ | a A’ |ԑ A’ → B d A’ | a A’ | ԑ
α2 = a
B → b B’
β1 = a
B’ → e B’ | ԑ
B→Be/b A=T,
α1 = e, B → b B’
β1 = b B’ → e B’ | ԑ
Substitution, Removal of useless and Left
Recursion
Elimination of Useless production/symbols from context
free grammar
DEFINITION & ELIMINATION OF USELESS PRODUCTION FROM CONTEXT FREE GRAMMAR

Definition :
 A symbol can be useless if it does not appear on the right-hand side of the
production rule and does not take part in the derivation of any string is known as a
useless symbol.
 A variable can be useless if it does not take part in the derivation of any string,
variable is known as a useless variable.

Condition of Useless Symbol :


 We will entitle any variable useful only when it is deriving any terminal.
 And also if a symbol is deriving a terminal but not reachable from Start state.
PROBLEMS OF USELESS SYMBOLS
Example-1
Consider the grammar and eliminate all the useless productions in the given
grammar.
SAB|a
ABC|b
BaB|C
CaC|B
Solution Useful Symbols: {a, b, S, A}. Any combination of useful symbols will also make LHS a
useful symbol.

So we could see that Symbol B and C are useless symbol, remove them (whole
production in which it contains):
S a
Ab

But cause A is not reachable so we will remove A  b as well: S  a


PROBLEMS OF USELESS SYMBOLS
Example-2
Consider the grammar and eliminate all the useless productions in the given grammar
S  A B |A C
AaAb|bAa|a
BbbA|aaB|AB
CabCA|aDb
DbD|aC

Solution First find out useful Symbols: {a, b, A, B, S}


And useless symbols are: {C, D}

So remove them and write the whole grammar again:


SAB
AaAb|bAa|a
B  b b A |a a B |A B
SUMMARY OF THE LECTURE

Definition of
Definition of Left
Substitution with Useless
recursion with
examples productions with
examples
examples
DISCUSSION
5 MINUTES
THANK YOU

You might also like