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

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

Compiler Design

Time: 03 HoursCode: 051616Full Marks: 70

Instructions:

  1. The marks are indicated in the right-hand margin.
  2. There are NINE questions in this paper.
  3. Attempt FIVE questions in all.
  4. Question No. 1 is compulsory.
Q.1 Choose the correct answer for any seven of the following:[14]

  1. What is the number of tokens in the following C statement? printf("I=%d and I=%x",I and I)

    1. 3
    2. 26
    3. 10
    4. 21

  2. Consider the following two statements: P: Every regular grammar is LL(1). Q: Every regular set has LR(1) grammar. Which of the following is true?

    1. Both P and Q are true
    2. P is true and Q is false
    3. P is false and Q is true
    4. Both P and Q are false

  3. What is the similarity between LR, LALR and SLR?

    1. Use of same algorithm, but different parsing table
    2. Same parsing table, but different algorithm
    3. Their parsing tables and algorithms are similar but use top-down approach
    4. Both parsing tables and algorithms are different

  4. Consider the following grammar: \( S \rightarrow aSbS | bSaS | \epsilon \). How many different parse trees are possible for string ababab?

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

  5. A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar: \( S \rightarrow xxW \) {PRINT "1"}, \( S \rightarrow y \) {print "2"}, \( S \rightarrow Sz \) {print "3"}. What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

    1. 23131
    2. 11233
    3. 11231
    4. 33211

  6. The most powerful parser is

    1. SLR
    2. LALR
    3. Canonical LR
    4. Operator-precedence

  7. In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

    1. \( (L \cup D)^* \)
    2. \( L(L \cup D)^* \)
    3. \( (L.D)^* \)
    4. \( L.(L.D)^* \)

  8. In operator precedence parsing, precedence relations are defined

    1. for all pairs of non-terminals
    2. for all pairs of terminals
    3. to delimit the handle
    4. None of the above

  9. A bottom-up parser generates

    1. right-most derivation
    2. right-most derivation in reverse
    3. left-most derivation
    4. left-most derivation in reverse

  10. A grammar that produces more than one parse tree for some sentence is called

    1. ambiguous
    2. unambiguous
    3. regular
    4. None of the above
Q.2 Solve both questions :[14]

  1. What do you understand by left recursion and left factoring? How are these eliminated? Explain with the help of suitable example.

  2. What do you understand by bootstrapping? Explain with the help of suitable example.

Q.3 Solve all questions :[14]

  1. How can addressing modes be used for reducing the memory access time?

  2. What are activation records? Explain its purpose in compilers.

  3. What are the optimization techniques applied on procedures calls? Explain with an example.

Q.4 Solve both questions :[14]

  1. Given the Syntax-Directed Definition below with the synthesized attribute val. Draw the annotated parse tree for the expression \( (3+4)*(5+6) \):
    \( L \rightarrow E \) ; \( L.val = E.val \)
    \( E \rightarrow T \) ; \( E.val = T.val \)
    \( E \rightarrow E_1+T \) ; \( E.val = E_1.val+T.val \)
    \( T \rightarrow F \) ; \( T.val = F.val \)
    \( T \rightarrow T_1*F \) ; \( T.val = T_1.val*F.val \)
    \( F \rightarrow (E) \) ; \( F.val = E.val \)
    \( F \rightarrow digit \) ; \( F.val = digit.lexval \)

  2. Construct a Syntax-Directed Translation scheme that translates arithmetic expressions from infix into postfix notation. Your solution should include the context-free grammar, the semantic attributes for each of the grammar symbols, and semantic rules. Show the application of your scheme to the input "3*4+5*2".

Q.5 Solve all questions :[14]

  1. What is the advantage of using machine independent intermediate representation during translation process?

  2. Explain, with example, what three address codes are. Give some common three address statements.

  3. Find the three address codes of the following program. There are four bytes per word:
    Sum = 0
    For(i = 1; i <= 20; i++)
    Sum = Sum + a[i] + b[i];

Q.6 Solve all questions :[14]

  1. Find the CNF (Chomsky Normal Form) for the following CFG:
    \( S \rightarrow ABA \)
    \( A \rightarrow aA | \epsilon \)
    \( B \rightarrow bB | \epsilon \)

  2. Eliminate null productions from the following CFG:
    \( S \rightarrow Xa \)
    \( X \rightarrow aX | bX | \epsilon \)

  3. Convert the following grammar to GNF :
    \( A_1 \rightarrow A_2A_3 \)
    \( A_2 \rightarrow A_3A_1 | b \)
    \( A_3 \rightarrow A_1A_2 | a \)

Q.7 Solve all questions :[14]

  1. What are the advantages of LALR parsing over SLR and CLR methods?

  2. Write the algorithm to compute FIRST and FOLLOW for a given grammar.

  3. What is shift-reduce conflict?

Q.8 Solve this question :[14]

  1. What are intermediate codes in compilers? Why is it needed in compiler design? Discuss different types of intermediate codes generated by intermediate code generation phase.

Q.9 Solve both questions :[14]

  1. What is parsing? What is the difference between Top-down parsing, Bottom-up parsing and Predictive parsing?

  2. Explain the working of each phase of compiler in detail with an example.