(SEM VI) CARRY OVER THEORY EXAMINATION 2017-18 COMPILER DESIGN

Compiler Design (ECS-603)

Complete Section-Wise Explanation – B.Tech Semester VI

Introduction to the Subject

Compiler Design is a core computer science subject that explains how a high-level programming language is translated into machine-level code. It connects theory with practical system software concepts such as language translation, parsing, code generation, optimization, and error handling.

This subject helps students understand:

How programming languages work internally                     How syntax and grammar are analyzed

How intermediate code is generated and optimized           How errors are detected and recovered

How efficient machine code is finally produced

The paper is divided into three sections: A, B, and C, and each section checks a different depth of understanding.

SECTION A – Fundamental Concepts

Pattern:
Attempt all questions
10 questions × 2 marks = 20 marks

Nature of Section A

Section A checks whether your basic definitions and concepts are clear. These questions are short, but they cover almost the entire syllabus. Answers should be precise, correct, and to the point.

Explanation of Section A Topics

A translator is a system software that converts one form of program into another. A compiler, interpreter, and assembler are all types of translators.

A compiler translates a complete high-level language program into machine code at once, whereas an assembler translates assembly language into machine language instruction by instruction.

NFA to DFA conversion is done because DFA is easier to implement. The conversion uses the subset construction algorithm, where each DFA state represents a set of NFA states.

A symbol table is a data structure used by the compiler to store information about identifiers such as variable names, data types, scope, and memory locations.

Common data structures for symbol table include arrays, linked lists, hash tables, and trees. Hash tables are preferred due to faster access.

An activation record is a memory block created for each function call that stores parameters, local variables, return address, and control information.

Postfix notation (Reverse Polish Notation) places operators after operands and removes the need for parentheses, making expression evaluation easier.

Three-address code is an intermediate representation where each instruction contains at most three operands, simplifying optimization.

Quadruples represent three-address code using four fields: operator, operand1, operand2, and result.

A regular expression is a formal way to describe a set of strings using symbols and operators, mainly used in lexical analysis.

SECTION B – Grammar, Parsing & Automata

Pattern:

Attempt any three questions
3 questions × 10 marks = 30 marks

Nature of Section B

This section tests your understanding of grammar, parsing techniques, and automata theory. Answers must be written in paragraph form, with algorithms, steps, and explanations where required.

Explanation of Important Questions

Regular Expressions Problems
These questions test your ability to represent specific string patterns formally. You must carefully interpret the language condition (such as symbol position or repetition) and construct a correct regular expression.

Thompson’s Construction for NFA
This method converts a regular expression into an NFA using ε-moves. It builds automata step-by-step for operators like union, concatenation, and closure.

Elimination of Left Recursion
Left recursion causes infinite loops in top-down parsers. The solution involves rewriting the grammar to remove immediate or indirect left recursion while preserving the language.

NFA to DFA Conversion
This question again emphasizes subset construction, showing how each DFA state is formed from a group of NFA states and transitions are defined accordingly.

Non-Recursive Predictive Parsing
This method uses a stack, input buffer, and predictive parsing table to parse strings without recursion. Constructing the parsing table requires FIRST and FOLLOW sets.

SECTION C – Parsing, Code Generation & Optimization

Pattern:
Attempt one part from each question
5 questions × 10 marks = 50 marks

This section carries the highest weightage and determines overall performance. Answers must be structured, logical, and complete.

Question 3 – Operator Precedence & LR Parsing

Operator-Precedence Parsing
This parsing technique is used for expression grammars. You must explain the algorithm, construct the precedence table, and parse the given input string step by step.

LR(1) and LALR Parsing Tables
This question tests advanced parsing concepts. LR(1) parsing uses look-ahead symbols to avoid conflicts, while LALR reduces table size by merging states.

Question 4 – Postfix Translation & SLR Parsing

Postfix Notation and STDS
You explain postfix notation and use a syntax-directed translation scheme to convert an infix expression into postfix form.

SLR Parsing Table Construction
This involves constructing LR(0) items, FOLLOW sets, and parsing tables. You must also analyze conflicts and suggest a final parsing table.

Question 5 – Error Handling & Intermediate Code

Logical and Syntactic Errors
Logical errors occur due to incorrect program logic, while syntactic errors violate grammar rules. Error recovery methods include panic mode, phrase-level recovery, and error productions.

Three-Address Code for Array Expressions
This problem tests your understanding of memory addressing, indexing, and intermediate code generation for multi-dimensional arrays.

Question 6 – Code Optimization

Common Sub-Expression Elimination
This optimization removes repeated calculations to improve efficiency. You must explain both local and global cases with examples.

Basic Blocks and Flow Graph
This involves identifying leaders, forming basic blocks, creating flow graphs, and applying loop optimization techniques to improve performance.

Question 7 – Advanced Optimization Tools

Loop Optimization and Global Data Flow Analysis
Loop optimization improves execution speed by reducing repeated computations. Global data flow analysis tracks how data values move through the program.

Directed Acyclic Graph (DAG) and YACC
DAGs represent expressions efficiently and help eliminate redundant operations.
YACC is a parser generator used to create syntax analyzers automatically.