(SEM V ) THEORY EXAMINATION 2021-22 COMPILER DESIGN

B.Tech (Sem V) – Theory Notes & Exam Answers

SECTION A – Short Answer Type

a. Parse Tree vs Abstract Syntax Tree (AST)
A parse tree shows the complete grammatical structure of the source program including all grammar symbols, while an AST is a simplified version that removes unnecessary grammar details and represents the essential structure.

b. Problems with Top-Down Parser
Top-down parsers cannot handle left recursion, require grammar transformations like left factoring, and may face backtracking issues.

c. Errors in Compilation Process
Lexical errors, syntactic errors, semantic errors, runtime errors, and logical errors may occur during compilation.

d. Types of Attributes
Two types of attributes are synthesized attributes and inherited attributes, used in syntax-directed translation.

e. Language Translator and Compiler
A language translator converts code from one language to another. A compiler translates high-level language into machine code.

f. Hashing
Hashing is a technique used to store and retrieve data efficiently using a hash function, commonly used in symbol tables.

g. Left Factoring
Left factoring removes common prefixes in grammar productions to make them suitable for predictive parsing.

h. Left Recursion
A grammar is left recursive if a non-terminal derives itself as the leftmost symbol.
Given grammar:
E → E+E | E*E | a | b
Yes, it is left recursive.

i. Ambiguous Grammar
A grammar is ambiguous if it produces more than one parse tree for the same string.
Example:
E → E+E | id

j. Shift-Reduce Conflicts
Shift-reduce conflict and reduce-reduce conflict occur during bottom-up parsing.

SECTION B – Descriptive Answers

Activation Record & Runtime Storage

An activation record stores information about a function call such as parameters, return address, local variables, and temporaries. It plays a key role in runtime storage management.

Intermediate Code Representation

For expression:
(x + y)*(y + z) + (x + y + z)
Intermediate representations include quadruples, triples, and indirect triples, which help in optimization and code generation.

Basic Block, Flow Graph & Next Use

A basic block is a sequence of instructions with single entry and exit.
A flow graph represents control flow among basic blocks.
Next-use information helps in register allocation.

Predictive Parsing

Predictive parsing uses FIRST and FOLLOW sets to build a parse table and avoids backtracking.

SECTION C – Long Answer Type

SLR Parsing Table

SLR parser uses LR(0) items and FOLLOW sets to build parsing tables. It is simpler but less powerful than LALR and CLR parsers.

Stack vs Heap Allocation

Stack allocation is fast and uses LIFO order, while heap allocation is flexible but slower and used for dynamic memory.
 

Syntax Directed Definition

SDD associates grammar rules with semantic rules to generate intermediate code.
 

DAG & Peephole Optimization

DAG removes redundant computations in basic blocks.
Peephole optimization improves code by eliminating inefficient instruction patterns.
 

Lexical & Syntactic Errors

Lexical errors occur during tokenization, while syntactic errors occur due to grammar violations. Error recovery includes panic mode and phrase-level recovery.
 

Induction Variable Optimization

Induction variables change linearly in loops and can be optimized to reduce repeated calculations.
 

LL(1) Grammar Test

A grammar is LL(1) if parsing table has no conflicts. FIRST and FOLLOW sets are used for testing.
 

Static vs Dynamic Scope

Static scope is determined at compile time, while dynamic scope is decided at runtime.
 

Code Generator Issues

Instruction selection, register allocation, and instruction scheduling are major design issues.
 

Three Address Code

Three address code represents control structures using labels, jumps, and temporary variables.