Scribd
Upload
108 views11 pages

Elimination of Left Recursion and Solving Non-Deterministic Grammars

This document discusses eliminating left recursion from context-free grammars. It begins by defining left and right recursion in productions. It then discusses how left recursion can cause issues for top-down parsers when calculating first sets. The key method presented is to eliminate left recursion by replacing productions of the form A → Aα | β with A → βA' and A' → αA' | ε. Several examples are worked through applying this transformation to remove left recursion. The document also discusses how this process can be used to determinize grammars by eliminating ambiguity from productions with common prefixes.

Uploaded by

abdul rehman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
108 views11 pages

Elimination of Left Recursion and Solving Non-Deterministic Grammars

This document discusses eliminating left recursion from context-free grammars. It begins by defining left and right recursion in productions. It then discusses how left recursion can cause issues for top-down parsers when calculating first sets. The key method presented is to eliminate left recursion by replacing productions of the form A → Aα | β with A → βA' and A' → αA' | ε. Several examples are worked through applying this transformation to remove left recursion. The document also discusses how this process can be used to determinize grammars by eliminating ambiguity from productions with common prefixes.

Uploaded by

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

ELIMINATION OF LEFT

RECURSION AND
SOLVING NON-
DETERMINISTIC
GRAMMARS
Left and Right Recursion
 If the left most symbol of the right hand side is
equal to right hand side then it is left recursion
 A -> A α | β

 And if the Right most symbol of the right hand side


is equal to right hand side then it is right recursion
 A -> α A | β
Problem with Top Down Parsers
 Suppose the grammar were
E→E+T|T
T→T*F|F
F → (E) | id

Calculate first sets?


Eliminating Left Recursion
 Left recursion in a production may be removed by
transforming the grammar in the following way.
 Replace
A  A | 
with
A  A'
A'  A' | .
Example: Eliminating Left
Recursion
 Consider the left recursive grammar
EE+T|T
Apply the transformation to E:
E  T E'
E'  + T E' | .
Example:
 S->S0S1S | 01

 S  01S’
 S’  OS1SS’ / €
Example:
 A  AB / Aa / a

 A  a A’
 A’  B  A’ / €

 A  a A’
 A’  aA’ / €
 Eliminate repeated step for final answer.
Example:
 A  Ac/ Aad/bd/c

 A  bdA’/cA’
 A’ cA’/adA’/ €
Deterministic and Non Deterministic
Grammar
 Non Deterministic Grammar
 A -> α β1 | α β2 | α β3

 On seeing α, you have three options……. Which one


to choose?

 A -> α A’
 A’ -> β1 | β2 | β3
Examples
 A->aSSbS | aSaSb | abb
|b
 A->aSSbS | aSaSb |
abb | b
Equivalent to
 S-> aS’ | b
 S’ -> SSbS | SaSb | bb
 S-> aS’ | b
 Again same prefixes…..  S’ -> SS’’ | bb
 S’’ -> SbS|aSb
 S’ -> SS’’ | bb
 S’’ -> SbS|aSb
Exercise
 S -> bSSaaS | bSSaSb | bSb | a

 A  bSA’ / a
 A’  SaaS / SaSb / Sb
 A’  SaA’’ /Sb
 A’’  aS/Sb

You might also like