COMPILER DESIGN
UNIT -2 Syntax Analysis
KVSM, Dept of CSE , SRKREC
Department of Computer Science and Engineering
S R K R Engineering College,
Bhimavaram-534204
Outline
UNIT-II Syntax Analysis:
The Role of a Parser, CFG(Definition of CFG, Derivations and Parse Trees, Ambiguity), Writing Grammar(Eliminating Ambiguity, Elimination of Left Recursion and Left Factoring in CFG), Top-down Parsing (Recursive-Descent Parsing and Predictive Parsing), Bottom-up Parsing(Shift Reduce Parsing).
KVSM, Dept of CSE , SRKREC
Outline
Contents :
KVSM, Dept of CSE , SRKREC
Left-Recursion
A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of its LHS.
A grammar containing a production having left recursion is called as Left Recursive Grammar.
KVSM, Dept of CSE , SRKREC
Left-Recursion
The productions of the form A → A α / β are called left recursive.
Left recursion is considered to be a problematic situation for Top down parsers.
Therefore, left recursion has to be eliminated from the CFG.
Left-Recursion Elimination
we can eliminate the left recursion by replacing the pair of productions with following :
A → β A’
A’ → α A’ / ∈
KVSM, Dept of CSE , SRKREC
Elimination of Left-Recursion
Problem-1: Consider the following grammar and eliminate left recursion-
S → S0S1S / 01
Solution:
The grammar after eliminating left recursion is-
S → 01A
A → 0S1SA / ∈
KVSM, Dept of CSE , SRKREC
Elimination of Left-Recursion
Problem-: Consider the following grammar and eliminate left recursion-
E → E + E / E * E / a
Solution:
The grammar after eliminating left recursion is-
E → a A
A → + E A / * E A / ∈
KVSM, Dept of CSE , SRKREC
Elimination of Left-Recursion
Problem-: Consider the following grammar and eliminate left recursion-
E 🡪 E + T / T
T🡪T * F / F
F🡪(E) / id
Solution:
The grammar after eliminating left recursion is-
E → T E’
E’→ + T E’ / ∈
T🡪 F T’
T’ 🡪 * F T’ / ∈
F🡪(E) / id
KVSM, Dept of CSE , SRKREC
Elimination of Left-Recursion
Consider the following grammar and eliminate left recursion-
A → A B d / Aa / a / b
B → B e / b / c
Solution:
The grammar after eliminating left recursion is-
A → a A’ / b A’
A’ → B d A’ / aA’ / ∈
B → b B’ / c B’
B’ → e B’ / ∈
KVSM, Dept of CSE , SRKREC
Left-Factoring
Left factoring is a process by which the grammar with common prefixes is transformed to make it useful for Top down parsers.
Example
A → αβ1 / αβ2 / β3
This kind of grammar creates a problematic situation for Top down parsers.
Top down parsers can not decide which production must be chosen to parse the string in hand.
To remove this confusion, we use left factoring.
KVSM, Dept of CSE , SRKREC
Elimination of Left-Factoring
Problem-1: Do left factoring in the following grammar-
A → a AB / a Bc / a Cc / db
A → a A’ /db
A’ → AB / Bc / Cc
This is the grammar with no left factoring.
KVSM, Dept of CSE , SRKREC
Elimination of Left-Factoring
Problem-2: Do left factoring in the following grammar-
A → a bB / a Bc / a Cc / a b C / e
A → a A’ /e
A’ → bB / Bc / Cc / b C
Here still there is left factoring
A → a A’
A’ → b A’’ / B c / Cc
A’’ → B / C
This is the grammar with no left factoring.
KVSM, Dept of CSE , SRKREC
Left-Recursion vs Left-Factoring
Left Recursion: A grammar is left recursive if it has a nonterminal A such that there is a derivation A -> Aα | β where α and β are sequences of terminals and nonterminals that do not start with A.
While designing a top down-parser, if the left recursion exist in the grammar then the parser falls in an infinite loop, here because A is trying to match A itself, which is not possible. We can eliminate the above left recursion by rewriting the offending production. As-
A -> βA'
A' -> αA' | epsilon
Left Factoring: Left factoring is required to eliminate non-determinism of a grammar. Suppose a grammar, S -> abS | aSb
Here, S is deriving the same terminal a in the production rule(two alternative choices for S), which follows non-determinism. We can rewrite the production to defer the decision of S as-
S -> aS'
S' -> bS | Sb
Thus, S' can be replaced for bS or Sb
KVSM, Dept of CSE , SRKREC
Thank You
K V S MURTHY
Assistant Prof,
CSE Dept
SRKR Engineering College.
9848290433
kvssrmurthy75@gmail.com
kvssr.murthy@srkrec.edu.in
KVSM, Dept of CSE , SRKREC