CS606 Midterm Past Paper 2005

CS606 Compiler Construction · Mid Term Examination – Spring 2005 · Time Allowed: 90 Minutes

1. The duration of this examination is 90 Mins.
2. This examination is closed book, closed notes, closed neighbors.

Q4. Some of the examination consists of multiple-choice questions. Choose only one choice as your answer.

1. If you believe that two (or more) of the choices are correct for a particular question, choose the best one.
2. On the other hand, if you believe that all of the choices provided for a particular question are wrong then select the one that appears to you as being the least wrong.

**WARNING: Please note that Virtual University takes serious action against unfair means. Anyone found involved in cheating will get an `F` grade in this course.

Q1. Total Questions: 4

Marks : 20

Given the following grammar and input string "bool id , id , id" 1. Decl 2. Type 3. IdList Type IdList

bool | int

IdList , id

| float

| id

a. show the leftmost derivation of the input string b. show the parse tree of the input string c. create a new equivalent grammar that has left recursion removed d. show the parse tree for the above input string on the new grammar

Q2. Find the First and Follow sets for the following grammars:

Marks : 10

1. Exp 2. ExpTail 3. Var 4. VarTail

Q3. – Exp | (Exp) | Var ExpTail

– Exp | id VarTail (Exp) |

Marks : 15

Consider the following grammar of lists. Note that there are four different terminals: "(", ")", "a", and "," 1. S 2. 3. 4. 5. A�

a

( A ) S A , S

a) Show that the grammar is not LL(1) hint: you should be able to do this by computing some of the FIRST sets b) Rewrite the grammar so that it is suitable for recursive decent parsing c) If you were going to build a table driven top-down parser for this grammar from (b), how big would the table be? (how many entries would it have)

Q4. Marks : 10

Use the subset construction to create a DFA that is equivalent to the following NFA that uses the alphabet a,b. Show your work. Note: The states with '*' are final states.