EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
Syllabus of Module 1
The structure of a compiler and applications of compiler technology; Lexical analysis ‐ The role of a lexical
analyzer, specification of tokens, recognition of tokens, hand‐written lexical analyzers, LEX, examples of LEX
programs. Introduction to syntax analysis ‐Role of a parser, use of context‐free grammars (CFG) in the
specification of the syntax of programming languages, techniques for writing grammars for programming
languages (removal left recursion, etc.), non‐ context‐free constructs in programming languages, parse trees and
ambiguity, examples of programming language grammars
2 marks questions
Lexical Analysis
1. Explain with an example how tokens are specified using regular expressions.
2. Design a regular expression for identifiers in C language that start with an alphabet and are followed by
alphanumeric characters. Justify your design.
3. Demonstrate how a hand-written lexical analyzer can be implemented to recognize integer and floating-point
constants.
4. Write a LEX program to recognize keywords if, else, and while. Explain its working.
5. Evaluate the advantages and limitations of LEX-based lexical analyzers compared to hand-written ones.
6. Propose modifications in a given LEX program to eliminate ambiguities when recognizing identifiers and
keywords.
Syntax Analysis & Grammars
7. *Construct a context-free grammar (CFG) for simple arithmetic expressions containing +, –, , /, and parentheses.
8. Analyze the ambiguity in the following grammar:
E → E + E | E * E | id
Provide a modified unambiguous grammar.
9. Apply left-recursion removal on the following grammar:
A → Aα | β. Show step-by-step transformation.
10. Compare and contrast top-down and bottom-up parsing strategies with suitable examples.
11. Evaluate the effectiveness of LL(1) parsing table construction for the grammar:
S → aSb | ε.
1
EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
12. Design an LR parsing table for the grammar:
S → CC
C → cC | d.
Parse Trees and Ambiguity
13. Construct a parse tree for the input string id + id * id using the grammar:
E → E + T | T,
T → T * F | F,
F → id.
14. Analyze the role of associativity and precedence rules in resolving ambiguity with an example.
15. Evaluate why certain programming language constructs (like indentation in Python) cannot be described using
CFGs.
16. Propose an alternative grammar or parsing strategy for handling the dangling else problem.
Syntax-Directed Translation & Code Generation
17. Design a syntax-directed translation scheme for arithmetic expressions to postfix form.
18. Analyze the role of synthesized and inherited attributes in attribute grammars. Provide suitable examples.
19. Evaluate the limitations of syntax-directed definitions when dealing with non-context-free features of a language.
20. Create an annotated parse tree for the expression (3+4)*5 using a translation scheme for postfix conversion.
Code Generation & Optimization
21. Develop an algorithm to generate three-address code (TAC) for assignment statements of the form x = y + z * w.
22. Analyze the difference between syntax-tree and DAG (Directed Acyclic Graph) representations in code
optimization.
23. Evaluate different register allocation strategies in code generation and their impact on efficiency.
24. Propose a target code generation algorithm for arithmetic expressions using stack-based architecture.
25. Design and explain an intermediate code generation algorithm that minimizes the number of temporary variables.
2
EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
5 marks questions
Unit 1 – Structure & Applications of Compiler Technology
1. Explain the phases of a compiler with a neat diagram. Illustrate with an example how input
source code is transformed into target code.
2. Analyze two real-world applications of compiler technology outside programming languages
(e.g., databases, text processing). Justify their relevance.
3. Evaluate the impact of compiler optimizations on execution efficiency with suitable examples.
4. Propose a modified compiler structure for a Just-In-Time (JIT) compilation environment.
Unit 2 – Lexical Analysis
5. Design a lexical analyzer using LEX for recognizing C identifiers, constants, and arithmetic
operators. Explain the working.
6. Analyze how ambiguity arises in token recognition when keywords and identifiers overlap.
Suggest strategies to resolve it.
7. Evaluate the performance trade-offs between hand-written lexical analyzers and those generated
using LEX.
8. Create a LEX program that recognizes both valid email addresses and integer constants. Explain
its limitations.
Unit 3 – Syntax Analysis
9. Apply left-recursion removal and left-factoring techniques to the following grammar and show
the resulting grammar step by step:
E → E + T | T
T → T * F | F
F → (E) | id
10.Analyze how parse trees differ in top-down and bottom-up parsing for the string id + id * id.
Illustrate with diagrams.
3
EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
11.Evaluate why predictive parsing (LL(1)) cannot handle left-recursive grammars and ambiguous
grammars. Provide examples.
12.Design an LR parsing table for the grammar:
S → S a | b
and demonstrate parsing of the string b a a.
Unit 4 – Parse Trees & Ambiguity
13.Construct an unambiguous grammar for arithmetic expressions with precedence (*, / > +, -) and
associativity rules. Prove its correctness with parse trees.
14.Analyze the dangling else problem in CFGs and explain two different strategies to resolve it.
15.Evaluate the limitations of context-free grammars in describing indentation-based languages like
Python. Suggest possible solutions.
16.Propose a modified parsing approach that combines CFGs with semantic rules to resolve
ambiguities in programming language constructs.
Unit 5 – Syntax Directed Translation & Code Generation
17.Design a syntax-directed translation scheme to convert arithmetic expressions into postfix form.
Demonstrate it on the expression (a+b)*c.
18.Analyze the role of synthesized and inherited attributes in syntax-directed definitions. Provide a
detailed example for type checking.
19.Evaluate different register allocation strategies in target code generation and discuss their effect
on execution efficiency.
20.Create an algorithm to generate optimized three-address code for boolean expressions involving
relational and logical operators.
4
EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
10 marks questions
Unit 1 – Structure of Compiler & Applications
1. Explain the complete structure of a compiler with a neat diagram. For each phase, illustrate its function
using the input statement x = a + b * c.
2. Analyze the role of compiler technology in modern software systems such as interpreters, virtual
machines, and domain-specific languages. Provide detailed examples.
3. Evaluate the necessity of intermediate representation in compiler design. Compare and contrast syntax
trees, DAGs, and three-address code with examples.
Unit 2 – Lexical Analysis
4. Design a lexical analyzer using LEX to recognize: (i) C identifiers, (ii) numeric constants, and (iii)
relational operators. Explain step-by-step execution with an input string.
5. Analyze the challenges in token recognition when multiple token patterns overlap (e.g., keywords vs
identifiers, float vs int). Suggest strategies to resolve these conflicts with examples.
6. Evaluate the efficiency and maintainability of hand-written lexical analyzers versus those generated by
LEX. Provide advantages and disadvantages with case studies.
Unit 3 – Syntax Analysis
7. Apply left-recursion removal and left-factoring techniques to the following grammar. Construct the LL(1)
parsing table and show step-by-step parsing of id + id * id.
E → E + T | T
T → T * F | F
F → (E) | id
8. Analyze the ambiguity of the given grammar:
S → iEtS | iEtSeS | a
where i = if, t = then, e = else, a = assignment. Illustrate how dangling else creates multiple parse trees.
9. Evaluate the suitability of top-down parsing versus bottom-up parsing for modern programming
languages. Discuss with detailed reasoning and examples.
5
EXERCISE BANK - COMPILER DESIGN - PCCCS701 (MODULE 1)
10. Design a canonical LR(1) parsing table for the grammar:
S → L = R | R
L → *R | id
R → L.
Explain how the parser processes the input id = *id.
Unit 4 – Parse Trees & Ambiguity
11. Construct an unambiguous grammar for arithmetic expressions with precedence rules (*, / higher than +,
-) and left-to-right associativity. Generate parse trees for a - b - c and a + b * c.
12. Analyze how ambiguity affects compiler implementation. Discuss two case studies (e.g., operator
precedence and dangling else). Provide examples of how ambiguity resolution is handled.
Unit 5 – Syntax Directed Translation & Code Generation
13. Design a syntax-directed translation scheme for converting arithmetic expressions into postfix notation.
Demonstrate it with the expression (a+b)*(c-d). Draw the annotated parse tree.
14. Evaluate the role of attribute grammars in semantic analysis. Discuss with examples of type checking and
expression evaluation.
15. Create an algorithm for generating optimized three-address code for boolean expressions involving
logical operators (&&, ||) and relational operators (<, >). Illustrate with a sample input program.