Compiler Design 2025

(a) Which phase of the compiler is responsible for removing comments and white spaces?

1. Syntax Analysis
2. Lexical Analysis
3. Semantic Analysis
4. Intermediate Code Generation

(b) A lexical analyzer uses which of the following automata?

1. PDA
2. Turing Machine
3. DFA/NFA
4. LBA

(c) LL(1) parsers use which parsing technique?

1. Bottom-up
2. Shift-reduce
3. Top-down
4. Operator precedence

(d) Conflicts in LR parsing include

1. Shift-shift
2. Shift-reduce
3. Reduce-reduce
4. Both (ii) and (iii)

(e) Type checking ensures

1. Syntax correctness
2. Register allocation
3. Semantic consistency
4. Pipeline optimization

(f) Pipeline optimization helps reduce

1. Syntax errors
2. Register conflicts
3. Execution stalls
4. Semantic errors

(g) Polymorphism is implemented using

1. NFA
2. Heap
3. Virtual functions
4. Stack frames

(h) Which parser construction method is used by YACC?

1. LL
2. LALR
3. General LR
4. SLR

(i) DAG stands for

1. Directed Applicable Graph
2. Directed Acyclic Graph
3. Data Analysis Graph
4. Data Allocation Graph

(j) LEX tool is used for

1. Parser generation
2. Lexical analysis
3. Syntax analysis
4. Intermediate code generation

(a) What are the various phases of a compiler? Explain each phase in detail by processing the input

a=(b+c)*(b+c)*2

(b) What is meant by lexical analysis, token, pattern and lexeme? Identify the lexemes that make up the token in the following program segment. Indicate the corresponding token and pattern.

Void swap(int i, int j)
{
    int t;
    t = i;
    i = j;
    j = t;
}

(a) Construct set of LR(1) items for the given grammar and check whether it is SLR, CLR or LALR.

S → CC
C → aC
C → d

(b) Consider the grammar

E  → T E₁
E₁ → + T E₁ | ε

T  → F T₁
T₁ → * F T₁ | ε

F  → ( E ) | id

Find the FIRST and FOLLOW set of all the variables.

(a) Consider the following grammar along with translation rules.

S → S₁ # T      { S.val = S₁.val + T.val }
S → T           { S.val = T.val }

T → T₁ % R      { T.val = T₁.val * R.val }
T → R           { T.val = R.val }

R → id          { R.val = id.val }

Here # and % are operators and id is a token that represents an integer and id.val represents the corresponding integer value.

Using this translation scheme, compute the value of S.val for the root of the parse tree for the expression:

20#10%5#8%2%2

(b) Consider the below grammar, which defines simple arithmetic expressions:

E → E + T | E - T | T
T → T * F | T / F | F
F → (E) | id

Now modify the above grammar with unconventional rules of precedence and associativity and then rewrite such that:

1. The expression 3*2+1 will be interpreted as 3*(2+1).
2. The value of 1-2-3 will be 2 rather than -4.

(a) Convert the regular expression (a|b)*ab into NFA, then convert the NFA into minimal DFA.

(b) Differentiate between synthesized and inherited attributes with example.

(a) What are shift-reduce and reduce-reduce conflicts? Explain with examples.

(b) Differentiate between Top-down and Bottom-up parsing with example.

(a) Consider the following C code segment:

a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;

In a compiler, this code segment is represented internally as a Directed Acyclic Graph (DAG).

Draw the DAG representation and find the number of nodes in the DAG.

(b) Explain architecture-dependent code optimization techniques with examples.

(a) How are object-oriented features compiled in C++/Java-like languages?

(b) Consider the following pseudo code:

L1:  t1 = -1
L2:  t2 = 0
L3:  t3 = 0
L4:  t4 = 4 + t3

L5:  t5 = 4 * t2
L6:  t6 = t5 * M
L7:  t7 = t4 + t6
L8:  t8 = a[t7]
L9:  if t8 <= max goto L11

L10: t1 = t8

L11: t3 = t3 + 1
L12: if t3 < M goto L4

L13: t2 = t2 + 1
L14: if t2 < N goto L3

L15: max = t1

Find the number of basic blocks and the number of instructions in the largest basic block.

Write short notes on any two of the following:

(a) Symbol Table

(b) Peephole Optimization

(c) Activation Record

(d) Three Address Code