BE Computer Engineering (Pokhara University) Compiler Design (PU, CMP 422) Question Paper 2079

(a) With a neat block diagram, explain the different phases of a compiler. Trace the output produced by each phase for the source statement position = initial + rate * 60. (8)

(b) Differentiate between a compiler and an interpreter. State two advantages of dividing the compiler into front-end and back-end. (4)

Consider the following grammar:

E  -> T E'
E' -> + T E' | epsilon
T  -> F T'
T' -> * F T' | epsilon
F  -> ( E ) | id

(a) Compute the FIRST and FOLLOW sets for every non-terminal. (6)

(b) Construct the LL(1) predictive parsing table and show that the grammar is LL(1). (5)

(c) Using the parsing table, show the stack-input moves made by the predictive parser while parsing the input string id + id * id. (3)

Consider the augmented grammar:

S' -> S
S  -> C C
C  -> c C | d

(a) Construct the canonical collection of LR(0) items (the set of item states) and draw the DFA of viable prefixes. (8)

(b) Build the SLR(1) parsing table (ACTION and GOTO). (4)

(c) Show the sequence of parser actions (shift/reduce) for the input string cdd. (2)

(a) Define a basic block and a flow graph. For the three-address code given below, partition the code into basic blocks and draw the control flow graph. (5)

1:  i = 1
2:  j = 1
3:  t1 = 10 * i
4:  t2 = t1 + j
5:  t3 = 8 * t2
6:  a[t3] = 0.0
7:  j = j + 1
8:  if j <= 10 goto 3
9:  i = i + 1
10: if i <= 10 goto 2

(b) Explain any three machine-independent code optimization techniques with suitable examples (common subexpression elimination, dead code elimination, loop-invariant code motion). (5)

(a) Write a regular expression that describes identifiers in C (a letter or underscore followed by any number of letters, digits, or underscores). (2)

(b) Construct an NFA for the regular expression (a|b)*abb using Thompson's construction, and convert it to a DFA using subset construction. (4)

(a) Show that the grammar E -> E + E | E * E | id is ambiguous by giving two distinct parse trees for the string id + id * id. (3)

(b) Eliminate left recursion and perform left factoring (where required) on the following grammar: (3)

A -> A c | A a d | b d | c

(a) Differentiate between synthesized attributes and inherited attributes with one example each. (3)

(b) Write a syntax-directed definition (with semantic rules) for a desk calculator that evaluates arithmetic expressions involving +, *, and parentheses over integer numbers. (3)

(a) What is three-address code? List the common forms used to represent it (quadruples, triples, indirect triples). (2)

(b) Generate the three-address code and write the quadruple representation for the expression: a = b * -c + b * -c. (4)

(a) What information is stored in a symbol table? Explain how a symbol table handles nested scopes (block structure). (3)

(b) Compare the use of a linear list and a hash table as data structures for implementing a symbol table, with respect to insertion and lookup time. (3)

(a) State the major issues in the design of a code generator. (3)

(b) Construct the DAG for the expression a + a * (b - c) + (b - c) * d and explain how the DAG helps in detecting common subexpressions. (3)

(a) Classify the types of errors detected by a compiler (lexical, syntactic, semantic) with one example of each. (3)

(b) Explain panic-mode and phrase-level error recovery strategies used in syntax analysis. (3)

Write short notes on any TWO of the following: (3+3)

(a) Peephole optimization

(b) Loop optimization techniques

(c) Bootstrapping of a compiler