(SEM VI) THEORY EXAMINATION 2018-19 COMPILER DESIGN

SECTION A – Short Answer Notes (2 Marks Each)

1. Two Parts of Compilation

Compilation is broadly divided into analysis (front end) and synthesis (back end).
The analysis part checks the source program for errors and converts it into an intermediate form. It includes lexical analysis, syntax analysis, and semantic analysis.
The synthesis part takes this intermediate representation and generates optimized target machine code.

2. Viable Prefix

A viable prefix is a prefix of a right-sentential form that does not extend beyond the rightmost handle. It represents a valid state during shift-reduce parsing and helps detect syntax errors early.

3. Classification of Compilers

Compilers can be classified as single-pass and multi-pass, optimizing and non-optimizing, cross compilers, and source-to-source compilers. The classification depends on how many times the source code is scanned and the purpose of compilation.

4. Error Recovery Strategies in Lexical Analysis

Lexical analyzer handles errors using strategies such as panic mode recovery, error correction by deletion or insertion of characters, and replacement of invalid characters so that compilation can continue.

5. Dangling Else Problem

The dangling else problem arises in nested conditional statements where it is ambiguous to which if an else belongs. By convention, the else is associated with the nearest unmatched if.

6. Types of Intermediate Code Representation

Intermediate code can be represented using three-address code, syntax trees, DAGs, and postfix notation. These representations help in optimization and machine-independent analysis.

7. Peephole Optimization

Peephole optimization is a local optimization technique where a small window of target code instructions is examined to remove redundant or inefficient instructions without changing program meaning.

SECTION B – Descriptive Answers (7 Marks Each)

1. Quadruples, Triples and Indirect Triples

For the expression
(x+y)∗(y+z)+(x+y+z)(x+y)*(y+z)+(x+y+z)(x+y)∗(y+z)+(x+y+z)

Quadruples store operator, operands, and result explicitly, making them easy to modify.
Triples remove explicit result names and use positions instead.
Indirect triples add a pointer table to overcome reordering issues of triples.

(Explain with step-by-step table format in exam.)

2. Problems with Top-Down Parsing & FIRST/FOLLOW

Top-down parsing suffers from left recursion, backtracking, and ambiguity.
FIRST gives the set of terminals that begin strings derived from a non-terminal.
FOLLOW gives terminals that can appear immediately after a non-terminal.
Both are essential for constructing predictive parsers.

3. Shift Reduce Parsing

Shift-reduce parsing uses a stack and input buffer.
Operations include shift, reduce, accept, and error.
For given grammar and input (a,(a,a)), parsing proceeds by shifting symbols and reducing them using grammar rules until the start symbol is obtained.

4. Global Data Flow Analysis

Global data flow analysis collects information about the flow of data across basic blocks.
It helps detect dead code, common sub-expressions, and loop-invariant code, improving overall code optimization.

5. LR(0) Parsing Table

LR(0) parsing constructs item sets, builds DFA states, and generates ACTION and GOTO tables.
It is powerful but may face shift-reduce conflicts when grammar is not LR(0).

SECTION C – Long Answer Notes (7 Marks Each)

1. NFA to DFA Conversion

NFA is converted to DFA using subset construction method.
Each DFA state represents a set of NFA states.
After construction, DFA is minimized by merging equivalent states.

2. Parameter Passing Mechanisms

Common mechanisms include call by value, call by reference, call by result, call by value-result, and call by name.
Each differs in how data is transferred between calling and called functions.

3. DAG Representation

DAG represents expressions by eliminating redundant computations.
For a := b*-c + b*-c, common sub-expression b*-c is evaluated once and reused.

4. Static vs Dynamic Scope

In static scope, variable binding is resolved at compile time using lexical structure.
In dynamic scope, binding depends on runtime call sequence.
Static scope uses access links to reach non-local variables.

5. Loop Optimization Concepts

Loop unrolling reduces loop overhead            Loop jamming combines adjacent loops

Dominators identify control flow                     Viable prefix ensures parsing correctness

These techniques improve execution speed.

6. Syntax Directed Translation

Syntax-directed translation attaches semantic rules to grammar productions.
Annotated parse trees evaluate expressions like (4*7+1)*2 step by step using attributes.

7. Error Recovery in Operator Precedence Parsing

Error recovery detects invalid precedence relations and skips input symbols until a valid configuration is reached, allowing parsing to continue.