LL(1) Parser with Left Recursion Example
Q.1. To check given grammar LL(1) or NOT.
S SaP | P
P PbR | R
R cSd | e
Solution :-
Step 1 : Remove Left Recursion
Solution Rules
1. left recursive production = S SaP | P A Aα | β
S PS’ Apply rule
A=S
S’ aPS’ | ∈ A βA’
α = aP
A’ αA’ | ∈
β= P
2. left recursive production = P PbR | R A Aα | β
P RP’ Apply rule
A=P
P’ bRP’ | ∈ A βA’
α = bR
A’ αA’ | ∈
β= R
The grammar after eliminating left recursion is-
S PS’
S’ aPS’ | ∈
P RP’
P’ bRP’ | ∈
R cSd | e
Step 2 : Find FIRST and FOLLOW
Production FIRST FOLLOW
S PS’ S = { c, e } S = { $, d }
S’ aPS’ | ∈ S’= { a, ε} S’= { $, d }
P RP’ P = { c, e } P = { a, $, d }
P’ bRP’ | ∈ P’ = { b, ε } P’= { a, $, d }
R cSd | e R = { c, e } R = { b, a, $, d }
Step 3 : Construct Parsing Table
NT\T a b c d e $
S S PS’ S PS’
S’ S’ aPS’ S’ ε S’ ε
P P RP’ P RP’
P’ P’ ε P’ bRP’ P’ ε P’ ε
R R cSd R e
Step 4 : Result
There is a no multiple entries in one cell,
hence the given grammar is LL(1).
Step 5 : Parsing Tree
String = “ e b e ”
S
P b R
R e
e
Step 6 : Left Most Derivation Step 7 : Stack Implementation
String = “ e b e ” Stack Input Buffer Predictive
$ ede$ PUSH S
S ⇒ P (using S→P) $S ede$ S PS’ (PUSH)
⇒ PbR (using P→PbR) $ S’ P ede$ P RP’ (PUSH)
⇒ RbR (using P→R for first P) $ S’ P’ R ebe$ R e (PUSH)
⇒ ebR (using R→e for first R) $ S’ P’ e ebe$ POP e
⇒ ebe (using R→e for second R) $ S’ P’ be$ P’ bRP’ (PUSH)
$ S’ P’ R b be$ POP b (Match b==b)
$ S’ P’ R e$ R e (PUSH)
$ S’ P’ e e$ POP e (Match e==e)
$ S’ P’ $ P’ ε (PUSH)
$ S’ $ S’ ε (PUSH)
$ $ Accepted
Q.2. To check given grammar LL(1) or NOT.
S S3R | 3P
P P1R | R
R 2R | ∈
Solution :-
Step 1 : Remove Left Recursion
Solution Rules
1. left recursive production = S S3R | 3P A Aα | β
Apply rule
S 3PS’ A=S
A βA’
S’ 3RS’ | ∈ α = 3R
A’ αA’ | ∈
β = 3P
2. left recursive production P P1R | R A Aα | β
Apply rule
P RP’ A=P
A βA’
P’ 1RP’ | ∈ α = 1R
A’ αA’ | ∈
β= R
The grammar after eliminating left recursion is-
S 3PS’
S’ 3RS’ | ∈
P RP’
P’ 1RP’ | ∈
R 2R | ∈
Step 2 : Find FIRST and FOLLOW
Production FIRST FOLLOW
S 3PS’ S= {3} S={$}
S’ 3RS’ | ∈ S’= { 3, ε} S’= { $ }
P RP’ P = { 2, ε } P = { 3, $ }
P’ 1RP’ | ∈ P’ = { 1, ε } P’= { 3, $ }
R 2R | ∈ R = { 2, ε } R = { $, 1, 3 }
Step 3 : Construct Parsing Table
NT\T 1 2 3 $
S S 3PS’
S’ S’ 3PS’ S’ ε
P P RP’ P RP’ P RP’ P RP’
P’ P’ 1RP’ P’ ε P’ ε
R R ε R 2R R ε R ε
Step 4 : Result
There is a no multiple entries in one cell
hence the given grammar is LL(1).
Step 5 : Parsing Tree Step 6 : Left Most Derivation Step 7 : Stack Implementation
String = “ 3 2 1 ” String = “ 3 2 1 ” Stack Input Buffer Predictive
S⇒3P $ 321$ PUSH S
⇒3(P1R) $S 321$ S 3PS’ (PUSH)
⇒3(R1R) $ S' P 3 321$ POP 3 (Match 3==3)
⇒3(2R1R) $ S' P 21$ P RP’ (PUSH)
⇒321R $ S' P’ R 21$ R 2R (PUSH)
⇒321 $ S' P’ R 2 21$ POP 2 (Match 2==2)
$ S' P’ R 1$ R ε (PUSH)
$ S' P’ 1$ P’ 1RP’ (PUSH)
$ S' P’ R 1 1$ POP 1 (Match 1==1)
$ S' P’ R $ R ε (PUSH)
$ S' P’ $ P’ ε (PUSH)
$ S' $ S’ ε (PUSH)
$ $ Accepted
Q.3. To check given grammar LL(1) or NOT.
S B
B bDAe
D Dd ; | ε
A A;E|E
E B|a
Solution :-
Step 1 : Remove Left Recursion
Solution Rules
1. left recursive production = D Dd; | ∈ A Aα | β
Apply rule
D ∈ D’ A=D
A βA’
D’ d;D’ | ∈ α = d;
A’ αA’ | ∈
β= ∈
2. left recursive production A A;E | E A Aα | β
Apply rule
A EA’ A=A
A βA’
A’ ;EA’ | ∈ α = ;E
A’ αA’ | ∈
β= E
The grammar after eliminating left recursion is-
S B
B bDAe
D D’
D’ d;D’ | ∈
A EA’
A’ ;EA’ | ∈
E B|a
Step 2 : Find FIRST and FOLLOW
Production FIRST FOLLOW
S B S= {b} S= {$}
B bDAe B= {b} B = { $, ; , e }
D D’ D = { d, ε } D = { b, a }
D’ d;D’ | ∈ D’= { d, ε } D’= { b, a }
A EA’ A = { b, a } A= {e}
A’ ;EA’ | ∈ A’= { ; , ε } A’= { e }
E B|a E = { b, a } E = {;,e}
Step 3 : Construct Parsing Table
NT\T a b d e ; $
S S B
S’ S’ bDAe
D D D’ D D’ D D’
D’ D’ ε D’ ε D’ d;D’
A A EA’ A EA’
A’ A’ ε A’ ; EA’
E E a E B
Step 4 : Result
There is a no multiple entries in one cell,
hence the given grammar is LL(1).
Step 5 : Parsing Tree Step 6 : Left Most Derivation Step 7 : Stack Implementation
String = “ b a e ” String = “ b a e ” Stack Input Buffer Predictive
S⇒B $ bae$ PUSH S
⇒bDAe $S bae$ S B
⇒bAe $B bae$ B bDAe
⇒ b E A' e $eADb bae$ POP b
⇒ b a A' e $eAD ae$ D ε
⇒bae $e A ae$ A EA’
$ e A’ E ae$ E a
$ e A’ a ae$ POP a
$ e A’ e$ A’ ε
$e e$ POP e
$ $ Accepted
Q.4. To check given grammar LL(1) or NOT.
A Abd | Aa | a
B Be | b
Solution :-
Step 1 : Remove Left Recursion
Solution Rules
1. left recursive production = A ABd | Aa | a A Aα₁ | Aα₂ | … | β₁ | β₂
Apply rule
A a A' A=A
A β₁A' | β₂A'
α1 = Bd
A' BdA' | aA’ | ε A' α₁A' | α₂A' |∈
α2 = a
β=a
2. left recursive production = B Be | b A Aα | β
Apply rule A=B
B bB’ A βA’ α=e
B' eB’ | ε A’ αA’ | ∈ β =b
The grammar after eliminating left recursion is : -
A aA'
A' BdA’ | aA’ | ε
B bB’
B' eB’ | ε
Step 2 : Find FIRST and FOLLOW
Production FIRST FOLLOW
A aA' A= {a} A= {$}
A' BdA’ | aA’ | ε A’= { b, a, ε} A’ = { $ }
B bB’ B= {b} B= {d}
B' eB’ | ε B’= { e, ε } B’= { d }
Step 3 : Construct Parsing Table
NT\T a b d e $
A A aA’
A’ A’ BdA’ A’ BdA’ A’ ε
B B bB’ D D’
B’ B’ ε B’ eB’
Step 4 : Result
There is a no multiple entries in one cell,
hence the given grammar is LL(1).
Step 5 : Parsing Tree Step 6 : Left Most Derivation Step 7 : Stack Implementation
String = “ a a b d ” String = “ a a b d ” Stack Input Buffer Predictive
A ⇒ a A' $ aadb$ PUSH A
⇒ a a A' $A aabd$ A aA’
⇒ a a b d A' $ A' a aabd$ POP a
⇒aabd $ A' abd$ A’ aA’
$ A' a abd$ POP a
$ A' bd$ A’ bdA’
$ A' d b bd$ POP b
$ A' d d$ POP d
$ A' $ A’ ε
$ $ Accepted