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

2023•Semester 3•Civil-CA•End Semester
Bihar Engineering University, Patna
B.Tech. 6th Semester Examination, 2023

Compiler Design

Time: 03 HoursCode: 105601Full 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.
  5. Symbols used (if any) have their usual meanings.
Q.1 Answer any seven questions of the following:[14]

  1. Which of the following is the most powerful parser?

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

  2. A top down parser generates

    1. Rightmost derivation
    2. Rightmost derivation in reverse
    3. Left most Derivation
    4. Left most derivation in reverse

  3. 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

  4. Three-address code involves

    1. Exactly 3 address
    2. At most 3 addresses
    3. No unary operator
    4. None

  5. Handle pruning forms the basis of

    1. Bottom up parsing
    2. Top down parsing
    3. Predictive parsing
    4. Recursive descent parsing

  6. Left factoring guarantees

    1. Not occurring of backtracking
    2. Cycle free parse tree
    3. Error free target code
    4. Correct LL(1) parsing table

  7. Consider a grammar \( A \rightarrow aS_1 | aS_2 \). The left factored grammar produced from the grammar is

    1. \( A' \rightarrow aA, A \rightarrow S_1 | S_2 \)
    2. \( A' \rightarrow aA, A \rightarrow aS_1 | aS_2 \)
    3. \( A' \rightarrow S_1 | S_2, A \rightarrow S_1 | S_2 \)
    4. None of these

  8. Synthesized attributes are calculated

    1. From the values of attributes of the children of the node
    2. From the values of attributes of the parent of the node
    3. From the values of attributes of the siblings of the node
    4. None of these

  9. The method which merges the bodies of two loops is

    1. Loop rolling
    2. Loop Jamming
    3. Constant folding
    4. None of the above

  10. For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if

    1. The LALR (1) parser for G has S-R conflicts
    2. The LR(0) parser for G has S-R conflicts
    3. The SLR(1) parser for G has S-R conflicts
    4. The SLR(0) parser for G has S-R conflicts
Q.2 Solve both questions :[14]

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

  2. What is an activation record? Explain how they are used to access various local and global variables.

Q.3 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.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. Find the FIRST and FOLLOW from the following production:
    \( S \rightarrow aBDh \)
    \( B \rightarrow cC \)
    \( C \rightarrow bC | \epsilon \)
    \( D \rightarrow EF \)
    \( E \rightarrow g | \epsilon \)
    \( F \rightarrow f | \epsilon \)

Q.5 Solve both questions :[14]

  1. Construct the predictive parsing table for the following grammar:
    \( S \rightarrow A \)
    \( A \rightarrow aB | Ad \)
    \( B \rightarrow bBC | f \)
    \( C \rightarrow cg \)

  2. Explain how type checking and error reporting are performed in compiler. Draw syntax tree and DAG for the statement: \( a = (a*b+c)\wedge(b+c)*b+c \)

Q.6 Solve all questions :[14]

  1. What is handle? Consider the grammar: \( E \rightarrow E+E | E*E | id \). Find the handles of the right sentential forms of the reduction for the string \( id_1 + id_2 * id_3 \).

  2. When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the grammar is ambiguous or not: \( A \rightarrow AA | (A) | a \)

  3. Discuss about operator precedence parser.

Q.7 Solve both questions :[14]

  1. Differentiate between S-attribute SDT and L-attribute SDT with suitable examples.

  2. Consider the following grammar: \( E \rightarrow E+T | T \), \( T \rightarrow T*F | F \), \( F \rightarrow id \). Draw a SLR state transition diagram for the above grammar. Also draw the SLR parse table.

Q.8 Solve both questions :[14]

  1. Consider the following grammar: \( S \rightarrow CC \), \( C \rightarrow cC | d \). Find the LR(1) set of items.

  2. Translate the expression \( a=(a+b)*(c+d)+(a+b+c) \) into (i) Quadruple (ii) Triple (iii) Indirect triple.

Q.9 Write short notes on any two of the following:[14]
    • LEX and YACC
    • Peephole Optimization
    • Symbol Table
    • Predictive parser