Question 1
(a) What are the classifications of a compiler?
From the notes, compilers can be classified as:
1. Assembler-based compilers – translate assembly language into machine code.
2. Interpreter-based compilers – directly execute high-level language programs line by
line.
3. Preprocessor-based compilers – handle macros, includes, and directives before
compilation.
4. High-level language compilers – for C, C++, Java, Fortran, etc.
Additionally, compilers can also be classified by their phases:
Analysis phase (machine independent)
Synthesis phase (machine dependent)
(b) What is compilation process?
The compilation process is divided into phases:
1. Lexical Analysis (Scanning) – converts characters into tokens.
2. Syntax Analysis (Parsing) – checks grammar and builds syntax tree.
3. Semantic Analysis – ensures meaning is correct (e.g., type checking).
4. Intermediate Code Generation – produces machine-independent representation.
5. Code Optimization – improves efficiency of code.
6. Code Generation – produces final machine/assembly code.
7. Symbol Table & Error Handling – support throughout all phases.
Question 2
(a) Lexical analysis of program
main ()
{
int x,y,z;
z = x + y;
}
Lexemes: main, (, ), {, int, x, ,, y, ,, z, ;, z, =, x, +, y, ;, }
Tokens:
o main → IDENTIFIER
o ( → LEFT_PAREN
o ) → RIGHT_PAREN
o { → LEFT_BRACE
o int → KEYWORD(INT)
o x, y, z → IDENTIFIER
o , → COMMA
o ;→ SEMICOLON
o =→ ASSIGNMENT_OPERATOR
o +→ ADDITION_OPERATOR
o }→ RIGHT_BRACE
Attributes of tokens:
o Identifiers (x, y, z) → stored in symbol table with type = int.
o Operators (=, +) → category = arithmetic/assignment operator.
o Keywords (int) → predefined meaning.
o Delimiters (;, ,, {, }) → structural tokens.
(b) Regular expression for an identifier
From the notes:
IDENTIFIER = [a-zA-Z][a-zA-Z0-9]*
(c) Transition diagram for Identifiers and Keywords
Identifiers: Start with a letter → followed by letters/digits repeatedly.
Keywords: Same as identifiers but matched against a reserved words table (if, while,
int, etc.).
(Transition diagram is a DFA: Start → Letter → (Letter/Digit) → Accepting state*).
Question 3
(a) Compiler-Construction Tools:
1. Lexical Analyzer generators (e.g., Lex, Flex) – convert regular expressions into DFA-
based scanners.
2. Parser generators (e.g., YACC) – generate syntax analyzers from grammar.
3. Syntax-directed translation engines – attach semantic actions to grammar rules.
4. Code-generator generators – produce machine code.
5. Data flow analysis tools – for optimization.
(b) Three-Address Code (TAC)
TAC breaks expressions into simple instructions with at most 3 operands:
o x := y op z
o x := op y
o x := y
(c) Three-address code for (a+b) * (a+b+c):
t1 = a + b
t2 = a + b + c
t3 = t1 * t2
Question 4
(a) Types of Compilers:
1. Single-pass compilers – translate in one scan.
2. Multi-pass compilers – need several passes.
3. Load-and-go compilers – compile and execute immediately.
4. Cross-compilers – compile code for another machine.
5. Optimizing compilers – focus on performance.
6. Incremental compilers – recompile only parts of program.
(b) Symbol Table Management and Error Handling
Symbol Table: Stores identifiers, types, scope, memory locations. Efficient data
structures like hash tables are used.
Error Handling:
o Lexical errors (illegal characters)
o Syntax errors (grammar mistakes)
o Semantic errors (type mismatch)
o Logical/runtime errors (wrong output
Question 5
(a) Relationship between parser and lexical analyzer
Lexical analyzer → converts character stream → tokens.
Parser → takes tokens → checks grammar, builds parse tree.
The parser requests tokens from the lexical analyzer as needed.
(b) Parsing in Compiler Design
Parsing is the process of analyzing tokens against grammar rules to check syntactic correctness
and produce a parse tree.
Question 6
Steps in a Top-Down Parser:
1. Start with the start symbol of grammar.
2. Expand leftmost nonterminal using productions (leftmost derivation).
3. Match input tokens with derivation.
4. If mismatch → backtrack or use predictive parsing.
5. Continue until all tokens are consumed and start symbol is derived.