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.
