Latest Activity In Study Groups

Join Your Study Groups

VU Past Papers, MCQs and More

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

Assignment No. 02
Semester: Fall 2014
Compiler Construction CS606


Total Marks: 20


Due Date: 08/12/2014




To learn and understand basic concepts of Parse Trees, Top Down Parsers, Predictive

Parsing, First and Follow Sets in building a Lexical analyzer.


It should be clear that your assignment will not get any credit (zero marks will be awarded) if:


  • The assignment is submitted after due date.
  • The submitted assignment does not open or file corrupt.
  • The assignment is copied (from other student or copy from handouts or internet).
  • Student name and ID are not mentioned in the assignment file.
  • It is in some format other than .doc or .docx(MS Word Document).

For any query about the assignment, contact at

Question No 1:                                                                                                                       Marks 10

Consider the following grammar; you are required to write left most derivation of the string “aebb”.


Question No 2:                                                                                                                        Marks 10             

Consider the following grammar for arithmetic expressions:


A à id X

X àA Y |ε

Y à- X | + X | / X | * X


Show the first set for the non-terminals X and Y in the grammar.




Views: 1807

Replies to This Discussion

Question 2 ka First and follow set ka solution hai kisi k pas

May it could be helpful for 2nd question..

first(x) for all grammar symbols x

Apply following rules:

  1. If X is terminal, FIRST(X) = {X}.
  2. If X → ε is a production, then add ε to FIRST(X).
  3. If X is a non-terminal, and X → Y1 Y2 … Yk is a production, and ε is in all of FIRST(Y1), …, FIRST(Yk), then add ε to FIRST(X).
  4. If X is a non-terminal, and X → Y1 Y2 … Yk is a production, then add a to FIRST(X) if for some i, a is in FIRST(Yi), and ε is in all of FIRST(Y1), …, FIRST(Yi-1).

Applying rules 1 and 2 is obvious. Applying rules 3 and 4 for FIRST(Y1 Y2 … Yk) can be done as follows:

Add all the non-ε symbols of FIRST(Y1) to FIRST(Y1 Y2 … Yk). If ε ∈ FIRST(Y1), add all the non-ε symbols of FIRST(Y2). If ε ∈ FIRST(Y1) and ε ∈ FIRST(Y2), add all the non-ε symbols of FIRST(Y3), and so on. Finally, add ε to FIRST(Y1 Y2 … Yk) if ε ∈ FIRST(Yi), for all 1 ≤ i ≤ k.


Consider the following grammar.

E → E + T | T
T → T * F | F
F → (E) | id

Grammar after removing left recursion:

E → TX
X → +TX | ε
T → FY
Y → *FY | ε
F → (E) | id

For the above grammar, following the above rules, the FIRST sets could be computed as follows:

FIRST(E) = FIRST(T) = FIRST(F) = {(, id}

FIRST(X) = {+, ε}

FIRST(Y) = {*, ε}

sorry,abhi kuch keh nahi sakti..

thanks for sharing old file..

mujhay b kuch aesa hi lag rha hai..but...

can you explain 1st ques from old solution file?

if S ―> aS | Ab

then how it can be?

First (S) = {a, b, c, d , e}


sorry mujy b nahi pta kesy aya . ma to bus compare kr k ans bta raha hon .

Upload kr dia hai assignment . Ab Allah kher kry kia bnta hai

assignment upload karo plz



can you explain 1st ques from old solution file?

if S ―> aS | Ab

then how it can be?

First (S) = {a, b, c, d , e}

مَلیکا ایمان appi.

S ―> aS | Ab

A ―> XYZ |ε

Yh islay hy  Q ky A ky andr XYZ hy Ju yh show kr rhy hain

a,b tu S ky apny hu Gy Hain aur c,d,e XYZ ky hu gy hain wo

isLy hoWy HaiN q ky S ky andr A nonterminal Show raha hy aur

A ky andr XYZ show hu rahy hn 

dear..explain some logic ..k ye alphabetics kis logic k through or kyun aa rhay hein??

simple si bat hy Appi ju Terminal hain wo 1st sets bny gy

then iska First just {a,b} hona chahiaye na k  {a,b,c,d,e}.. 


© 2022   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service