THEORY EXAMINATION (SEM–VI) 2016-17 COMPILER DESIGN

COMPILER DESIGN – ECS603

B.Tech (SEM VI) – Section-wise Solved Answers

SECTION A (Short Answer Type)

(a) Why should compiler phases be grouped?

Compiler phases are grouped to reduce repeated scanning of source code and improve efficiency. Grouping also simplifies implementation and helps in better coordination between related phases such as syntax and semantic analysis.

(b) Regular expression for strings with even number of a’s and b’s

A suitable regular expression is:
**(aa + bb + (ab + ba)(aa + bb)(ab + ba)) **
This ensures both a and b appear an even number of times.

(c) CFG for palindrome

A context-free grammar for palindrome over {a, b} is:
S → aSa | bSb | a | b | ε
This grammar produces strings that read the same forwards and backwards.

(d) Why are quadruples preferred over triples?

Quadruples avoid ambiguity because they use explicit temporary names. This makes code movement and optimization easier compared to triples, where references depend on statement position.

(e) Syntax directed translation for case statement

In syntax directed translation, semantic rules are attached to grammar productions. For a case statement, labels are generated for each case, and control transfers using conditional jumps.

(f) What is a syntax tree?

A syntax tree is a hierarchical representation of program structure. Operators appear as internal nodes and operands as leaves. It represents expression evaluation order clearly.

(g) Register assignment for outer loops

Registers are allocated to frequently used variables inside loops. For outer loops, variables with the longest live range are assigned registers to minimize memory access.

(h) Criteria for code improving transformations

Transformations should preserve program meaning, reduce execution time, minimize memory access, and avoid increasing code size unnecessarily.

(i) Flow graph representation

A flow graph represents control flow using basic blocks as nodes and edges showing execution order. Loops are shown by backward edges.

(j) Use of algebraic identities in optimization

Algebraic identities simplify expressions, remove redundant operations, and reduce computation time, for example replacing x + 0 with x.

SECTION B (Descriptive Answer Type)

(a) Phases of compilation with example

Compilation involves lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimization, and target code generation.
For a=(b+c)*(b+c)*2, repeated expressions are identified and optimized.

(b) Minimized DFA

The DFA is first constructed from the regular expression, unreachable states are removed, and equivalent states are merged to obtain a minimal DFA.

(c) Ambiguous grammar

A grammar is ambiguous if a string has more than one parse tree.
Grammar E → E+E | E(E) | id is ambiguous because expressions like id+id+id can be parsed in multiple ways.

(d) NFA for regular expression

An NFA is constructed using Thompson’s construction where * creates loops and | creates branching transitions.

(e) Symbol table lookup

Symbol tables use hashing or tree structures for fast lookup. They store identifier name, type, scope, and memory location.

(f) Algorithm for basic blocks

A statement is a leader if it is the first statement, a jump target, or follows a jump. Each leader begins a basic block.

(g) Optimization of basic blocks

Common sub-expression elimination, dead code elimination, and constant folding are applied within basic blocks to improve efficiency.

(h) Run-time memory subdivision

Memory is divided into code area, static data, stack (for function calls), and heap (for dynamic allocation).

SECTION C (Long Answer Type)

(3) SLR parsing table

SLR parsing table is built using LR(0) items and FOLLOW sets. Parsing actions for input abab are shown step-by-step using shift and reduce operations.

(4) Intermediate code generation

Assignment statements use three-address code.
Case statements use conditional jumps and labels to control execution flow.

(5) DAG and instruction sequence

A DAG removes common sub-expressions.
For a + a*(b-c) + (b-c)*d, (b-c) is computed once and reused.