(SEM V) THEORY EXAMINATION 2023-24 COMPILER DESIGN

B.Tech (Semester V) | AKTU / UPTU | Exam Year: 2023–24
Maximum Marks: 100 | Time: 3 Hours | Paper ID: 310677

This question paper focuses on testing the students’ understanding of the design, structure, and optimization techniques of compilers.
It covers major compiler construction phases — Lexical Analysis, Syntax and Semantic Analysis, Intermediate Code Generation, Optimization, and Code Generation.

The paper is divided into three main sections (A, B, C) to evaluate both conceptual understanding and problem-solving skills related to parsing, syntax-directed translation, and optimization.

SECTION A – Short Answer Questions (10 × 2 = 20 Marks)

Students must attempt all ten short questions.
This section assesses conceptual clarity of compiler construction principles and terminology.

Sample Questions (Page 1):

Define bootstrapping in the context of compilers.

Which phase of a compiler is optional and why?

Explain the concept of shift-reduce parsing.

Differentiate between Parse Tree and Syntax Tree with examples.

Define syntax-directed translation schemes.

What are the two types of attributes associated with grammar symbols?

Discuss how scope information is represented in a symbol table.

What is meant by an Activation Record?

Discuss two design issues in code generation.

Explain the concept of global data-flow analysis.

Concepts Covered:
Compiler phases, parsing, syntax trees, syntax-directed translation, symbol table design, activation records, optimization, and data flow analysis.

SECTION B – Descriptive / Medium-Length Questions (3 × 10 = 30 Marks)

Students are required to attempt any three questions.
This section focuses on intermediate-level analytical and theoretical problems on lexical and syntax analysis, code generation, and optimization.

Sample Questions (Page 1):

Describe the relationship between finite state machines and regular expressions. Explain how regular expressions are used in lexical analysis and pattern matching.

Construct LR(1) and LALR parsing tables for the grammar:

Explain the concepts of quadruples and triples in syntax-directed translation.

Describe a simple stack allocation scheme for memory management.

Explain the role of the code generator and how it translates intermediate code to target code.

Concepts Covered:
Regular expressions, LR(1)/LALR parsing, syntax-directed translation, intermediate code forms, stack allocation, and code generator design.

SECTION C – Analytical / Long Answer Questions (5 × 10 = 50 Marks)

Students must attempt one part from each question (Q3–Q7).
This section covers problem-solving, grammar design, code optimization, and semantic error handling.

Sample Questions (Pages 1–2):

Q3.
a. Construct an NFA for the regular expression a(b|c)*.
b. Check whether the grammar E → E+E | E*E | id is ambiguous. If yes, convert it into an unambiguous grammar.

Q4.
a. Check whether the grammar S → PQy, P → Sy|x, Q → yS is LR(0) or not.
b. For the grammar:

E → E + T | T   T → T * F | F   F → (E) | id

Construct the shift-reduce parsing tree for id * (id + id).

Q5.
a. Write syntax-directed definitions for the statement:

S → id = E   E → E + E | E * E | -E | (E) | id 

b. Explain how syntax-directed translation handles array references in arithmetic expressions.

Q6.
a. Define a Symbol Table and explain data structures used in its implementation.
b. Discuss semantic errors, their detection, and challenges in handling them. Provide suitable examples.

Q7.
a. Apply common subexpression elimination to optimize the block:

1. x = a + b   2. y = x * c   3. z = y – d

b. Construct a Directed Acyclic Graph (DAG) for the block:

1. x = a + b   2. y = c - d   3. z = x * y

Concepts Covered:
NFA construction, ambiguity detection, LR(0) parsing, syntax-directed translation, symbol table management, DAG creation, and code optimization techniques.

Learning Outcomes:

After completing this paper, students will be able to:

Understand the phases and architecture of a compiler.

Analyze grammars and construct parsing tables.

Implement syntax-directed translation and intermediate code forms.

Detect and resolve semantic and optimization issues in code generation.

Understand data-flow analysis and code optimization in compiler back-end design.

S → aAd | bBd | aBe | bAe   A → f   B → f