UNIT 1 [ 2MARKS]
1. What are the two main parts of compilation? Explain briefly.
• Analysis Phase (Front End): Breaks source code into tokens,
checks syntax and semantics, and generates intermediate code.
• Synthesis Phase (Back End): Optimizes intermediate code and
generates target machine code.
2. Define tokens, patterns and lexemes.
• Token: A category or class of lexemes (e.g., identifier, keyword).
• Pattern: A rule describing the structure of a token (e.g., [a-zA-
Z][a-zA-Z0-9]* for identifiers).
• Lexeme: The actual text from the source code that matches a
pattern (e.g., count, sum).
3. What is the structure of LEX program?
A LEX program has three sections, separated by %%:
1. Definitions – Define macros and import headers.
2. Rules – Regular expressions and corresponding actions.
3. User Subroutines – Additional C code (like main() or helper
functions).
Example:
lex
CopyEdit
%{
#include <stdio.h>
%}
%%
[0-9]+ { printf("Number\n"); }
[a-zA-Z]+ { printf("Word\n"); }
%%
int main() { yylex(); return 0; }
4. Mention the issues in Lexical Analyzer.
• Error Handling: Detecting and recovering from lexical errors.
• Token Recognition: Efficiently identifying tokens.
• Lookahead Handling: Sometimes more than one character
needs to be read ahead.
• Interaction with Parser: Must provide tokens in a way the
parser expects.
5. Write a regular expression for the following language description.
a. String of a’s and b’s such that the character third from the right is
b:
Let the string be: xbyy where x is any string of a’s and b’s, and yy is
any two characters.
Regex: (a|b)*b(a|b)(a|b)
b. String of x’s and y’s that only contains three y’s:
This means exactly three y’s anywhere in the string.
Regex: (x* y x*){3}
(Note: This ensures three y’s appear, surrounded by any number of
x’s.)
UNIT 2 [ 2MARKS]
1. What is handle pruning?
Handle pruning is a process used in bottom-up parsing where a
handle (a substring matching the right-hand side of a production and
reducible to a non-terminal) is identified and replaced (reduced) by
its corresponding non-terminal. This process continues until the
entire input is reduced to the start symbol.
2. What are the various conflicts that occur during shift-reduce
parsing?
The two main conflicts are:
• Shift-Reduce Conflict: The parser cannot decide whether to
shift (read more input) or reduce (apply a production rule).
• Reduce-Reduce Conflict: The parser has a choice between two
or more reductions and cannot decide which one to apply.
3. List some error recovery strategies in syntax analyzer.
• Panic Mode Recovery: Skips input symbols until a synchronizing
token is found.
• Phrase Level Recovery: Replaces or inserts tokens to continue
parsing.
• Error Productions: Adds grammar rules to catch common
errors.
• Global Correction: Tries to find the minimal changes needed to
correct the input (used in theory, not practical).
4. Eliminate the left recursion for the grammar:
S → Sc | Sad | bd | ε
We first identify the left-recursive productions: S → Sc | Sad
And the non-left-recursive ones: S → bd | ε
Let’s transform it:
plaintext
CopyEdit
S → bd S' | ε S'
S' → c S' | ad S' | ε
So, left recursion is eliminated using a new non-terminal S'.
5. Identify the FIRST and FOLLOW functions for the grammar:
Given:
less
CopyEdit
S → ACB | CbB | Ba
A → da | YC
B→g|ε
C→h|ε
FIRST sets:
• FIRST(A): d, FIRST(YC)` (but Y is undefined, possibly a typo?)
(Assuming Y is a typo and should not be considered) So,
FIRST(A) = {d, h, ε}
• FIRST(B): {g, ε}
• FIRST(C): {h, ε}
Now for S:
• S → ACB → First(A)
o A can be d, h, or ε.
o If A → ε, then check FIRST(C), and then B.
• S → CbB → FIRST(C) → h, or if ε, then b
• S → Ba → FIRST(B) → g, or if ε, then a
So FIRST(S): {d, h, b, g, a}
FOLLOW sets:
• FOLLOW(S): $ (end of input symbol)
• FOLLOW(A): FIRST(C) = {h, ε}
If C → ε, then check FIRST(B), and so on...
• FOLLOW(C): FIRST(B) = {g, ε}
If B → ε, then follow(S)
• FOLLOW(B): follow(S) = $
(Due to epsilon in multiple productions, FOLLOW sets can get large;
this is a sketch for exam-level answers.)
UNIT 3[ 2MARKS]
1. Translate the arithmetic expression a * -(b + c) into:
(a) Syntax Tree:
markdown
CopyEdit
*
/\
a -
|
+
/\
b c
(b) Postfix Notation:
css
CopyEdit
bc+-a*
2. Differentiate S-attributed SDD and L-attributed SDD:
Feature S-attributed SDD L-attributed SDD
Attributes Only synthesized Both synthesized and inherited
Used attributes attributes
Evaluation Bottom-up (used in
Top-down (used in LL parsing)
Order LR parsing)
More flexible, supports a wider
Simplicity Simpler to implement
range of grammars
3. Syntax Directed Definition for a Simple Desk Calculator:
Grammar:
r
CopyEdit
E→E+T|T
T→T*F|F
F → (E) | digit
Semantic Rules (SDD):
r
CopyEdit
E → E1 + T { E.val = E1.val + T.val }
E→T { E.val = T.val }
T → T1 * F { T.val = T1.val * F.val }
T→F { T.val = F.val }
F → (E) { F.val = E.val }
F → digit { F.val = digit.lexval }
4. Define Type Checking:
Type Checking is the process of verifying that operands in
expressions are compatible with the expected data types. It ensures
correctness of operations (e.g., preventing int + string) either at
compile-time (static type checking) or runtime (dynamic type
checking).
5. Three-address code for:
d = (a - b) + (a - c) + (a - c)
Step-by-step TAC:
ini
CopyEdit
t1 = a - b
t2 = a - c
t3 = t1 + t2
t4 = a - c
t5 = t3 + t4
d = t5
UNIT 4 [ 2MARKS]
1. What are the properties of an optimizing compiler?
• Improves performance (speed or memory usage) of the
generated code.
• Preserves correctness of the original program.
• Portable and retargetable (can support multiple platforms).
• Performs machine-independent and machine-dependent
optimizations.
2. Delineate peephole optimization.
Peephole optimization is a local optimization technique that
examines a small set of instructions (a “peephole”) to find and
replace inefficient sequences with more efficient ones.
Example:
csharp
CopyEdit
MOV R1, R2
MOV R2, R1
→ Removed as redundant
3. What do you mean by copy propagation?
Copy propagation replaces the occurrences of a variable that was
assigned the value of another variable.
Example:
makefile
CopyEdit
x=y
z=x
→z=y
4. Identify the constructs for optimization in a basic block.
• Common subexpression elimination
• Dead code elimination
• Constant folding
• Copy propagation
• Strength reduction
5. What is the purpose of next use information?
It tells whether a variable will be used again in the future within a
basic block.
Useful for:
• Register allocation
• Dead code elimination
6. Mention the applications of DAGs.
DAG (Directed Acyclic Graph) is used to:
• Detect common subexpressions
• Optimize code by eliminating redundant computations
• Determine evaluation order
• Track dependencies between operations
7. What are the advantages and disadvantages of register allocation
and assignments?
Advantages:
• Faster access to data (registers are faster than memory)
• Reduces memory traffic
Disadvantages:
• Limited number of registers
• Complex allocation can increase compilation time
8. Define Flowgraph.
A flowgraph (control flow graph) is a directed graph where:
• Nodes represent basic blocks
• Edges represent possible flow of control
Used for:
• Code optimization
• Data flow analysis
9. What are the different types of optimizations that can be applied
to a basic block?
• Constant folding
• Common subexpression elimination
• Copy propagation
• Dead code elimination
• Strength reduction
10. Identify the process of live variable analysis and why it is
important for optimizing register usage?
Live variable analysis determines which variables are "live" (needed
later) at each point in the program.
Why it matters:
• Helps in register allocation (don’t allocate registers to variables
no longer needed)
• Assists in dead code elimination
• Reduces memory access and register pressure
UNIT 5[ 2MARKS]
1. What are the three storage allocation strategies?
• Static Allocation: Memory is assigned at compile time.
• Stack Allocation: Memory is assigned and freed in LIFO order
during runtime.
• Heap Allocation: Memory is allocated and freed dynamically
(non-LIFO).
2. Draw the activation tree for the code:
c
CopyEdit
int main() {
printf(...);
scanf(...);
int show_data(username);
printf(...);
}
int show_data(char *user) {
printf(...);
return 0;
}
Activation Tree:
less
CopyEdit
main
|
show_data
(Only one function call inside main, so main calls show_data once.)
3. What is Heap Management?
Heap management refers to the process of allocating and
deallocating memory in the heap area at runtime. It handles
dynamic memory allocation, e.g., malloc() in C or new in Java.
4. Uses of Register and Address Descriptors in Code Generation:
• Register Descriptor: Tracks which variables are stored in which
registers.
• Address Descriptor: Tracks where the current value of a
variable is located (memory, register, or both).
They help in:
• Minimizing memory access
• Efficient code generation
• Avoiding unnecessary loads/stores
5. Object code for x = (a * b – c) / d:
Typical three-address code:
c
CopyEdit
t1 = a * b
t2 = t1 - c
t3 = t2 / d
x = t3
Assuming registers:
css
CopyEdit
MUL R1, a, b
SUB R2, R1, c
DIV R3, R2, d
MOV x, R3
6. Difference between Stack and Heap Memory:
Stack Heap
Managed in LIFO order Managed via dynamic allocation
Fast allocation and deallocation Slower due to overhead
Limited size Large size available
Used for local variables Used for dynamic memory (malloc)
7. Benefits and Limitations of Stack Allocation:
Benefits:
• Simple and efficient
• Automatic memory management
Limitations:
• Not suitable for dynamic/lifetime-unknown data
• Fixed size – risk of stack overflow
8. Role of Static Link and Dynamic Link:
• Static Link: Points to the activation record of the static (lexical)
parent, used to access non-local variables.
• Dynamic Link: Points to the activation record of the caller,
used for control flow and returning.
Together, they help in:
• Accessing variables from outer scopes (static link)
• Proper return and call structure (dynamic link)
9. Key Challenges in Designing a Simple Code Generator:
• Instruction selection for target architecture
• Register allocation and spilling
• Handling addressing modes
• Minimizing code size and maximizing speed
• Preserving semantics during optimization
10. Why is Instruction Scheduling Important in Code Generation?
Instruction scheduling:
• Reduces stalls and pipeline hazards in CPUs
• Improves parallelism in execution
• Increases instruction-level efficiency
• Helps in making best use of available registers and execution
units
