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

(a) Explain the role of a lexical analyzer in a compiler. Describe the terms token, lexeme, and pattern with suitable examples. [6]

(b) Consider the regular expression (a|b)*abb. Construct an NFA using Thompson's construction, then convert it into an equivalent DFA using the subset construction algorithm. Show the transition table and the minimized DFA. [8]

Consider the following augmented grammar:

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

(a) Construct the canonical collection of LR(0) items (the set of item sets) for this grammar. [8]

(b) Build the SLR(1) parsing table (ACTION and GOTO) and show, using a stack, how the input string id * id + id is parsed. [8]

(a) Differentiate between machine-dependent and machine-independent code optimization. [4]

(b) For the following three-address code, construct the basic blocks, draw the control flow graph, and apply the optimizations common sub-expression elimination, dead code elimination, and constant folding. Show the optimized code at each step. [8]

1.  t1 = 4 * i
2.  t2 = a[t1]
3.  t3 = 4 * i
4.  t4 = b[t3]
5.  t5 = t2 + t4
6.  c   = t5
7.  t6 = 4 * i
8.  d   = t6

(a) Distinguish between synthesized and inherited attributes. Explain S-attributed and L-attributed definitions with examples. [5]

(b) Write a syntax-directed definition that generates three-address code for the assignment statement a = b * -c + b * -c. Show the annotated parse tree and the generated three-address instructions. [5]

Explain the different phases of a compiler with a neat block diagram. Show the intermediate output produced by each phase for the source statement position = initial + rate * 60.

For the grammar below, compute the FIRST and FOLLOW sets of every non-terminal and construct the LL(1) predictive parsing table. State whether the grammar is LL(1).

S -> a B D h
B -> c C
C -> b C | epsilon
D -> E F
E -> g | epsilon
F -> f | epsilon

What is left recursion and why is it a problem for top-down parsers? Eliminate left recursion and perform left factoring on the following grammar:

A -> A c | A a d | b d | epsilon
S -> i E t S | i E t S e S | a

Describe the data structures used for implementing a symbol table. Compare the use of a linear list versus a hash table for symbol table organization, commenting on insertion and lookup time complexity. How is scope information handled in a block-structured language?

Explain the three representations of three-address code: quadruples, triples, and indirect triples. Represent the expression a = b * -c + b * -c in all three forms and comment on the relative advantages of each.

(a) What are the major issues in the design of a code generator? [3]

(b) Generate target code for the three-address statements t = a - b, u = a - c, v = t + u, d = v + u using a simple code generator and the register-descriptor / address-descriptor based getReg() function. Assume two registers are available. [3]

Show that the grammar E -> E + E | E * E | ( E ) | id is ambiguous by giving two distinct parse trees (or leftmost derivations) for the string id + id * id. How can operator precedence and associativity rules be used to remove this ambiguity?

Explain the following loop optimization techniques with an example for each: (a) loop-invariant code motion, (b) strength reduction, (c) induction variable elimination.

Compare LL(1), SLR(1), LALR(1), and canonical LR(1) parsers in terms of grammar class power, parsing table size, and ability to detect errors. Why is LALR(1) the most commonly used method in practical parser generators such as YACC?