Scribd
Upload
41 views7 pages

Assignment 2 (21B-219-CS)

The document outlines an assignment for the Compiler Construction course at Usman Institute of Technology, focusing on converting grammars into equivalent LL(1) grammars and constructing parse tables. It details the elimination of left recursion, left factoring, and the creation of first and follow sets for the given grammars. Additionally, it includes steps for creating an LR(0) parse table and state machine for a specified input string.

Uploaded by

A I M E N
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
41 views7 pages

Assignment 2 (21B-219-CS)

The document outlines an assignment for the Compiler Construction course at Usman Institute of Technology, focusing on converting grammars into equivalent LL(1) grammars and constructing parse tables. It details the elimination of left recursion, left factoring, and the creation of first and follow sets for the given grammars. Additionally, it includes steps for creating an LR(0) parse table and state machine for a specified input string.

Uploaded by

A I M E N
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 7

USMAN INSTITUTE OF TECHNOLOGY

Affiliated with NED University of Engineering & Technology, Karachi

Department of Computer Science


B.S. Computer Science Batch-2021

ASSIGNMENT NO: 2

Course Name: Compiler Construction Course


Code: CS - 412

By

AIMEN 21B-219-CS
1.Convert the following grammar into an equivalent LL(1) grammar
and derive the LL(1) parse table: a) S -> a | (b L L) L -> L , a | b
1. Eliminate Left Recursion:
The given grammar has left recursion in the rule L -> L , a.
To eliminate it, we can rewrite the rule as:
L -> bR
R -> , a L | ε

2. Left Factor the Grammar:


The rule S -> a | (b L L) needs to be left factored.
We can rewrite it as:
S -> a
S -> (b L L')
L' -> L

3. The resulting LL(1) grammar is:


S -> a
S -> (b L L')
L' -> L
L -> bR
R -> , a L | ε

First Sets:
FIRST(S) = {a, (}
FIRST(L') = {b}
FIRST(L) = {b}
FIRST(R) = {ε, ,}
Follow Sets:
FOLLOW(S) = {$}
FOLLOW(L')= {)}
FOLLOW(L) = {, )}
FOLLOW(R)= {L, )}
4. Constructing the LL(1) Parse Table:

b) A -> AB | B B -> Bd | e

1. Eliminate Left Recursion:


The given grammar has left recursion in the rule A -> AB.
To eliminate it, we can rewrite the rule as:
A -> BA’
A’ -> B | ε
Again, the given grammar has left recursion in the rule B -> Bd.
To eliminate it, we can rewrite the rule as:
B -> e B'
B' -> d B' | ε
2. The resulting LL(1) grammar is:
A -> B A'
A' -> B A' | ε
B -> e B'
B' -> d B' | ε
First Sets:
First(A) = First(B) = { e }
First(A') = { e, ε }
First(B) = { e }
First(B') = { d, ε }
Follow Sets:
Follow(A) = { $, d }
Follow(A') = { $, d }
Follow(B) = { e, $, d }
Follow(B') = { $, d }
3. Constructing the LL(1) Parse Table:

2. Given the following grammar, create the state machine and LR (0)
parse table: also create a stack table and tree for the input “dfdfeg”.
A -> AB | B B -> dC | eC C -> f | g

Step 1: Augmented Grammar


Add a new start symbol S':
S' -> A
A -> AB | B
B -> dC | eC
C -> f | g

Step 2: LR(0) Items


State I₀:
S' → ·A
A → ·AB
A → ·B
B → ·dC
B → ·eC
C → ·f
C → ·g
Transitions from I₀:
• On A, go to I₁.
• On B, go to I₂.  On d, go to I₃.  On e, go to I₄.
• On f go to I₅.
• On g, go to I₆.

State I₁:
S' → A·
No further transitions from I₁.

State I₂
A → B·
No further transitions from I₂.

State I₃
B → d·C
C → ·f
C → ·g Transitions
from I₃:
• On f, go to I₅.
• On g, go to I₆.

State I₄
B → e·C
C → ·f
C → ·g Transitions
from I4I₄I4:
• On f, go to I₅.
• On g, go to I₆.

State I₅
C → f·
No further transitions from I₅.

State I₆
C → g·
No further transitions from I₆.

State I₇
B → dC·
No further transitions from I₇

State I₈
B → eC·
No further transitions from I₈

Step 3: LR(0) Parse Table

Actions Goto
Step 4: Parse Input String dfdfeg

You might also like