Compiler Design - B.Tech. 6th Semester Examination, 2017

2017•Semester 2•Civil-CA•End Semester
Aryabhatta Knowledge University, Patna
B.Tech. 6th Semester Examination, 2017

Compiler Design

Time: 03 HoursCode: 051616Full Marks: 70

Instructions:

  1. There are Nine Questions in this Paper.
  2. Attempt Five questions in all.
  3. Question No. 1 is Compulsory.
  4. The marks are indicated in the right-hand margin.
Q.1 Answer any seven questions:[14]

  1. A grammar that produces more than one parse tree for some sentence is said to be

    1. Ambiguous
    2. context free
    3. disambiguous
    4. regular

  2. What is not the phase of a compiler?

    1. Syntax analyzer
    2. code generator
    3. code optimizer
    4. code linker

  3. Given a grammar \( G=(\{E\}, \{id, +\}, P, E) \); where P is given by \( E \rightarrow E+E | id \). Then FOLLOW(E) will contain

    1. { $ }
    2. { + }
    3. { $, + }
    4. { $, id, + }

  4. Which of the following expressions has no l-value?

    1. a[i+1]
    2. a
    3. 3
    4. *a

  5. Consider the statement "fi (x>=10)", where 'if' has been misspelled. The error is detected by the compiler in the phase

    1. lexical analysis
    2. syntax analysis
    3. semantic analysis
    4. syntactic analysis

  6. Which of the following is not a loop optimization?

    1. Induction variable elimination
    2. Loop unrolling
    3. Loop jamming
    4. Loop heading

  7. If x is a terminal then FIRST(x) is

    1. \( \epsilon \)
    2. { x }
    3. \( x^* \)
    4. \( xx^* \)

  8. Consider following grammar \( S \rightarrow cAd \), \( A \rightarrow ab | a \). For input string cad, how many times the recursive descent parser will backtrack?

    1. 2
    2. 3
    3. 4
    4. 5

  9. The optional access link in the activation record is used for

    1. Pointing to the activation record of the caller
    2. Referring the non-local data held in other activation records
    3. Temporary values, such as those arising in the evaluation of expressions
    4. Pointing to the activation record of the calling procedure.

  10. Suppose two productions are there: \( A \rightarrow \alpha \) and \( A \rightarrow \beta \). The recursive descent parsing without backtracking requires:

    1. first(\( \alpha \)) and first(\( \beta \)) must be in same set
    2. first(\( \alpha \)) and first(\( \beta \)) to be disjoint
    3. first(\( \alpha \)) and first(\( \beta \)) must be equal
    4. Data insufficient
Q.2 Solve this question :[14]

  1. Construct DFA for \( (ab^* | ba^*) \) and minimize the number of states of the above constructed DFA.

Q.3 Solve both questions :[14]

  1. A grammar is given below:
    \( S \rightarrow A \)
    \( A \rightarrow aB | Ad \)
    \( B \rightarrow bBC | f \)
    \( C \rightarrow g \)
    Find the FIRST and FOLLOW set.

  2. Construct a predictive parsing table for the grammar given above.

Q.4 Solve this question :[14]

  1. What is a symbol table? Why is it needed in compiler design? Explain different components of a symbol table with an example.

Q.5 Solve both questions :[14]

  1. Consider the following program fragment:
    prod = 0;
    i = 1;
    do {
        prod = prod + a[i] * b[i];
        i = i + 1;
    } while (i <= 20);
    Generate the three-address code for the above program fragment.

  2. Determine the basic blocks for the computed three-address code.

Q.6 Solve this question :[14]

  1. What is DAG? What is the use of DAG in compiler construction? Construct a DAG for the following statements:
    \( Z = X - Y + X * Y \)
    \( U = V / W + X + V \)

Q.7 Solve both questions :[14]

  1. Explain peephole optimization in detail.

  2. Suppose a basic block is formed from the C assignment statements:
    \( x = a + b + c + d + e + f; \)
    \( y = a + c + e; \)
    (a) Give the three-address statements (only one addition per statement) for this block.
    (b) Use the associative and commutative laws to modify the block to use the fewest possible number of instructions, assuming both \( x \) and \( y \) are live on exit from the block.

Q.8 Solve all questions :[14]

  1. Given the grammar \( G = (S, \{S, A, B\}, \{a, b, c, d\}, P) \) with set of productions \( P \) below compute;

    a. LR(1) sets of items.

    b. Compute the corresponding parsing table for the corresponding shift-reduce parse engine.

    c. Show the actions of the parsing engine as well as the contents of the symbol and state stacks for the input string \( w = \text{"bdac"} \).

    d. Is this grammar LALR(1)? Justify.


    \( S \rightarrow Aa | bAc | Bc | bBa \)
    \( A \rightarrow d \)
    \( B \rightarrow d \)
    Do not forget to augment the grammar with the production \( S' \rightarrow S \).

Q.9 Write short note on (any two) of the following:[14]
    • Syntax-directed definition and translation schemes
    • Handling Reserved Keywords
    • Bottom Up Parsing