Compiler Design - Question and Answers
Compiler Design - Question and Answers
Part - I (Short Answer Type Questions)
a) Why do we need compilers?
Compilers translate high-level programming languages into machine code, making it possible for computers to execute
programs efficiently.
b) Differentiate Assembler and Interpreter.
- Assembler: Converts assembly language into machine code.
- Interpreter: Translates and executes high-level code line by line without generating machine code.
c) What is the use of Loader and Linker?
- Loader: Loads executable code into memory for execution.
- Linker: Combines multiple object files and resolves external references to create a complete executable.
d) What is Bootstrapping?
Bootstrapping is the process of writing a compiler in the source programming language it is intended to compile.
e) Distinguish Lexeme, Token, and Pattern.
- Lexeme: Actual text (e.g., "while").
- Token: Classification (e.g., WHILE_KEYWORD).
- Pattern: Rule describing a token's form (e.g., regular expressions).
f) What do you mean by input buffering?
Input buffering is used to efficiently read large inputs by storing input streams in memory to reduce disk I/O during lexical
analysis.
g) NFA for (a/b)*abb and (a*b/bc*):
For (a/b)*abb:
Start -> (a/b loop) -> a -> b -> b -> Accept
For (a*b/bc*):
Start -> (a loop) -> b -> Accept
OR
Start -> b -> (c loop) -> Accept
h) Explain the role of parser.
A parser checks syntax according to grammar rules and generates parse trees to represent program structure.
i) What is shift-reduce and reduce-reduce conflict?
- Shift-Reduce Conflict: When the parser can't decide whether to shift (read) or reduce (apply a rule).
- Reduce-Reduce Conflict: When the parser can't decide which reduction rule to apply.
j) Find LR(0) items of A -> WXYZ.
LR(0) items:
- [A -> .WXYZ]
- [A -> W.XYZ]
- [A -> WX.YZ]
- [A -> WXY.Z]
- [A -> WXYZ.]
Part - II (Focused Short Answer Questions)
a) DFA for (a/b)*abb:
States:
q0 -> (a/b loop) -> q1(a) -> q2(b) -> q3(b) -> Accept
b) Difference between rightmost and leftmost derivation with derivation tree:
For grammar E -> E+E | E*E | (E) | id,
- Leftmost: Replace leftmost non-terminal first.
- Rightmost: Replace rightmost non-terminal first.
Example derivation of "id + id * id":
Leftmost:
E -> E+E -> id+E -> id+E*E -> id+id*id
Rightmost:
E -> E+E -> E+E*E -> E+id*E -> E+id*id -> id+id*id
c) Left factoring and removing left factoring:
Grammar:
S -> iCtS | iCtSeS | a
Left factored:
S -> iCtS X | a
X -> eS | epsilon
d) Types of LR parsers:
- SLR(1): Simple LR.
- CLR(1): Canonical LR.
- LALR(1): Look-Ahead LR.
Operation: All use a parsing table and stack to shift and reduce symbols based on grammar.
e) CLOSURE and GOTO:
- CLOSURE(I): Adds items to I when a dot precedes a non-terminal, including its productions.
- GOTO(I, X): Transition from state I over symbol X to a new state.
Part - III (Long Answer Questions)
03. Different Phases of Compiler:
1. Lexical Analysis: Tokenization.
2. Syntax Analysis: Parse tree generation.
3. Semantic Analysis: Type checking.
4. Intermediate Code Generation: Intermediate representation.
5. Code Optimization: Improve code performance.
6. Code Generation: Machine code output.
7. Error Handling: Detect and report errors.
04. FIRST and FOLLOW of the Grammar:
Grammar:
E -> TE'
E' -> +TE' | epsilon
T -> FT'
T' -> *FT' | epsilon
F -> (E) | id
FIRST:
FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
FIRST(E') = { +, epsilon }
FIRST(T') = { *, epsilon }
FOLLOW:
FOLLOW(E) = { $, ) }
FOLLOW(E') = FOLLOW(E) = { $, ) }
FOLLOW(T) = FIRST(E') = { +, $, ) }
FOLLOW(T') = FOLLOW(T) = { +, $, ) }
FOLLOW(F) = FOLLOW(T) = { *, +, $, ) }
05. Parse string w = (a) using SLR parser for A -> (A) | a:
LR(0) Items:
1. [A -> .(A)]
2. [A -> ( .A)]
3. [A -> (A .)]
4. [A -> .a]
5. [A -> a .]
Parsing Steps:
Stack | Input | Action
------|-------|--------
$ | (a)$ | Shift (
$( | a)$ | Shift a
$(a | )$ | Reduce A -> a
$(A | )$ | Shift )
$(A) | $ | Reduce A -> (A)
$A |$ | Accept
