Compiler Design

Lexical analysis, Parsing, Syntax-directed translation, Runtime environments, Intermediate code generation.

Mark Distribution in Previous GATE

Subject Overview

Compiler Design is a fundamental area of Computer Science that deals with the theory and practice of building compilers – programs that translate source code written in a high-level programming language into an equivalent low-level machine-understandable form (like assembly or machine code). Understanding compiler design is crucial for a GATE CS aspirant as it provides deep insights into how programming languages work, how software interacts with hardware, and the underlying mechanisms of program execution. This subject often carries a weightage of 6-10 marks in the GATE CS exam, typically involving 2-3 questions of 2 marks and 1-2 questions of 1 mark. Questions range from theoretical concepts (phases of compilation, definitions) and conceptual understanding (optimization techniques, runtime environment) to numerical problems (parsing table construction, FIRST/FOLLOW sets, DAG generation, register allocation). A strong grasp of this subject is vital not just for the exam, but also for a holistic understanding of computer systems.

Topic-wise Key Concepts

Abstract Syntax Tree (AST)

An AST is a tree representation of the abstract syntactic structure of source code, where each node denotes a construct in the source code. It abstracts away the concrete syntax (like parentheses or semicolons) and focuses on the essential structure and meaning of the program. ASTs are crucial for semantic analysis, intermediate code generation, and various optimization techniques.

Key Properties:

• Nodes represent operators and keywords, while leaves represent operands and identifiers.

• More compact than a parse tree, omitting unnecessary details like non-terminals that only derive other non-terminals.

• Used as an intermediate representation for subsequent compiler phases.

• Common Pitfalls: Confusing AST with a parse tree. A parse tree shows every detail of the derivation; an AST shows only the essential structure.

• Standard Problem-Solving Technique: Given a grammar and an expression, construct its parse tree first, then derive the AST by eliminating redundant nodes and structuring it based on operator precedence and associativity.

Ambiguous Grammar

A grammar is said to be ambiguous if there exists at least one string that can be generated by the grammar in more than one leftmost derivation, or more than one rightmost derivation, or has more than one parse tree. Ambiguity is undesirable in programming language grammars because it leads to multiple interpretations of the same program statement.

Key Properties:

• Causes difficulty for parsers as they cannot uniquely determine the structure of an input string.

• Common sources include dangling-else problem and lack of operator precedence/associativity rules.

• Common Pitfalls: Not being able to identify ambiguity. A common test is to find a string with two distinct parse trees.

• Standard Problem-Solving Technique: To resolve ambiguity, rewrite the grammar by introducing new non-terminals or by incorporating precedence and associativity rules directly into the grammar productions. For example, for arithmetic expressions, introduce non-terminals like Term and Factor.

Assembler

An assembler is a program that translates assembly language code into machine code. Assembly language uses

mnemonics for operations and symbolic names for memory locations, making it more human-readable than raw machine code. Assemblers typically perform a one-to-one translation of assembly instructions to machine instructions.

• Key Properties:
• Two-Pass Assembler:
• 1. Pass 1: Scans the source code to build a symbol table (mapping symbolic labels to memory addresses) and determines the length of machine instructions.
• 2. Pass 2: Uses the symbol table to translate assembly instructions into machine code, filling in operand addresses.
• Handles pseudo-operations (directives) like ORG, EQU, START, END, which guide the assembly process but don't translate into machine instructions.
• Common Pitfalls: Confusing assembler with compiler or linker. Assembler works at a lower level, translating assembly to machine code.
• Standard Problem-Solving Technique: Trace the assembly process, building a symbol table and calculating location counter values for each instruction and data item.

Backpatching

Backpatching is a technique used in one-pass code generation, particularly for control flow statements (like if-else, while loops) and boolean expressions. It involves generating jump instructions with initially unspecified target addresses, which are later filled in (patched) once the true target address becomes known.

• Key Properties:
• Uses lists of incomplete jumps (e.g., truelist, falselist, nextlist).
• makelist(i): Creates a new list containing only i (an index into the list of quadruples).
• merge(p1, p2): Concatenates lists p1 and p2 , returning the combined list.
• backpatch(p, i): Inserts i as the target label for each of the jumps in list p .
• Standard Problem-Solving Technique: Trace the generation of three-address code for control flow statements, maintaining and updating truelist , falselist , and nextlist as new quadruples are generated.

Basic Blocks

A basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end. Basic blocks are fundamental units for many code optimization techniques.

• Key Properties:
• No jumps into the middle of a basic block.
• No jumps out of the middle of a basic block.
• The first statement is called a leader .
• Standard Problem-Solving Technique:
• 1. Identify leaders :
• ▪ The first statement of the program is a leader.
• ▪ Any statement that is the target of a conditional or unconditional jump is a leader.
• ▪ Any statement immediately following a conditional or unconditional jump is a leader.
• 2. For each leader, its basic block consists of the leader and all subsequent statements up to, but not including, the next leader or the end of the program.

Code Optimization

Code optimization is the phase of a compiler that attempts to improve the intermediate code or target code to make it run faster, use less memory, or consume less power, without changing the program's observable behavior. It can be machine-independent or machine-dependent.

• Key Types/Techniques:

• Machine-Independent:

• ▪ Peephole Optimization: Examines a small sliding window of instructions and replaces suboptimal sequences with better ones (e.g., redundant loads/stores, strength reduction).

• ▪ Common Subexpression Elimination (CSE): Identifies and removes redundant computations of the same expression.

• ▪ Dead Code Elimination: Removes code that is never executed or whose results are never used.

• ▪ Constant Folding: Evaluates constant expressions at compile time (e.g., $2 * 3 + 5$ becomes 11).

• ▪ Loop Optimizations: Loop invariant code motion, induction variable elimination, loop unrolling.

• ▪ Strength Reduction: Replacing expensive operations with cheaper ones (e.g., $x * 2$ with $x + x$ or $x \ll 1$).

• Machine-Dependent: Register allocation, instruction scheduling.

• Key Property: Optimization must preserve the semantic equivalence of the program.

• Common Pitfalls: Misidentifying opportunities for optimization or applying an optimization that changes program behavior.

Compilation Phases

The compilation process is typically divided into several phases, each performing a specific task in the translation of source code to target code. These phases operate sequentially, with the output of one phase serving as the input to the next.

Phases in Order:

• 1. Lexical Analysis (Scanning): Breaks source code into tokens.
• 2. Syntax Analysis (Parsing): Checks grammar rules and builds a parse tree/AST.
• 3. Semantic Analysis: Checks for type compatibility, undeclared variables, etc. (meaning of the program).
• 4. Intermediate Code Generation: Creates an abstract machine-independent representation (e.g., three-address code).
• 5. Code Optimization: Improves the intermediate or target code for efficiency.
• 6. Code Generation: Translates intermediate code into target machine code (e.g., assembly).

Supporting Components:

• Symbol Table Management: Stores information about identifiers, used across multiple phases.

• Error Handling: Detects and reports errors at each phase.

• Common Pitfalls: Confusing the order or specific responsibilities of each phase.

Compiler Tokenization (Lexical Analysis)

Compiler tokenization, or Lexical Analysis, is the first phase of a compiler where the input stream of characters is grouped into meaningful sequences called tokens . Each token represents a basic unit of the language, such as keywords, identifiers, operators, or literals.

• Core Idea: Converts a stream of characters into a stream of tokens.

Key Properties:

• Tokens are defined by regular expressions .

• Lexical analyzers (scanners) are typically implemented using Finite Automata (NFA or DFA).

• Handles whitespace and comments, usually discarding them.

• Longest Match Rule: When multiple token patterns match a prefix of the input, the longest possible token is chosen.

• Precedence Rule: If multiple patterns match the same longest prefix, the pattern listed first (or with higher precedence) is chosen.

• Common Pitfalls: Incorrectly applying longest match or precedence rules.

• Standard Problem-Solving Technique: Given a string and a set of regular expressions for tokens, identify the sequence of tokens.

Directed Acyclic Graph (DAG)

A DAG is a directed graph data structure used as an intermediate representation for basic blocks in compilers. Nodes in a DAG represent operations, and edges represent the flow of values between operations. It effectively highlights common subexpressions and the order of operations within a basic block.

Key Properties:

• Each node has a unique value. If an expression is computed multiple times, it corresponds to a single node in the DAG.

• Leaf nodes are identifiers or constants. Interior nodes are operators.

• Used for common subexpression elimination, dead code elimination, and reordering of operations.

Standard Problem-Solving Technique:

1. For each statement x = y op z :

• ▪ If y or z are not in the DAG, create nodes for them.

• ▪ If op is not in the DAG with children y and z , create a node for it.

• ▪ Add x as a label to the node representing y op z .

• 2. If x = y , make x a label for the node representing y .

Expression Evaluation

Expression evaluation is the process of computing the value of an arithmetic or logical expression according to operator precedence and associativity rules. Compilers often convert infix expressions to postfix or prefix notation for easier evaluation using a stack-based approach.

• Key Notations:
• Infix: Operators between operands (e.g., $a + b * c$).
• Postfix (Reverse Polish Notation - RPN): Operators after operands (e.g., $a\ b\ c * +$).
• Prefix (Polish Notation): Operators before operands (e.g., $+ a * b\ c$).
• Key Properties:
• Precedence: Determines which operator is evaluated first (e.g., multiplication before addition).
• Associativity: Determines evaluation order for operators of the same precedence (e.g., left-to-right for $+$, $-$, $*$, $/$; right-to-left for $^{\wedge}$).
• Standard Problem-Solving Technique:
• Infix to Postfix/Prefix: Use a stack to manage operators based on precedence and associativity.
• Postfix Evaluation: Scan from left to right. Push operands onto a stack. When an operator is encountered, pop required operands, perform operation, push result back.

First and Follow

FIRST and FOLLOW sets are crucial for constructing predictive (LL(1)) parsing tables and for resolving ambiguities in grammars. They help determine which production to apply or which token to expect next.

• FIRST(X): The set of terminal symbols that begin strings derived from $X$. If $X$ can derive $\epsilon$ (empty string), then $\epsilon$ is in $\text{FIRST}(X)$.
• FOLLOW(A): The set of terminal symbols that can immediately follow the non-terminal $A$ in some sentential form. $\text{FOLLOW}(A)$ never contains $\epsilon$.
• Important Formulas/Rules:
• 1. FIRST for a terminal a: $\text{FIRST}(a) = \{a\}$.
• 2. FIRST for $\epsilon$: $\text{FIRST}(\epsilon) = \{\epsilon\}$.
• 3. FIRST for a non-terminal A: For each production $A \rightarrow X_1X_2\dots X_k$:
• ▪ Add $\text{FIRST}(X_1) - \{\epsilon\}$ to $\text{FIRST}(A)$.
• ▪ If $\epsilon \in \text{FIRST}(X_i)$ for all $i = 1\dots j-1$, then add $\text{FIRST}(X_j) - \{\epsilon\}$ to $\text{FIRST}(A)$.
• ▪ If $\epsilon \in \text{FIRST}(X_i)$ for all $i = 1\dots k$, then add $\epsilon$ to $\text{FIRST}(A)$.
• 4. FOLLOW for a non-terminal A:
• ▪ Place \ (end-marker) in $\text{FOLLOW}(S)$ where $S$ is the start symbol.
• ▪ For each production $A \rightarrow \alpha B \beta$: Add $\text{FIRST}(\beta) - \{\epsilon\}$ to $\text{FOLLOW}(B)$.
• ▪ For each production $A \rightarrow \alpha B$ or $A \rightarrow \alpha B \beta$ where $\epsilon \in \text{FIRST}(\beta)$: Add $\text{FOLLOW}(A)$ to $\text{FOLLOW}(B)$.
• Common Pitfalls: Incorrectly handling $\epsilon$ productions, or not iterating until sets stabilize.
• Standard Problem-Solving Technique: Apply rules iteratively until no new terminals can be added to any set.

Grammar

A grammar is a formal system that describes the syntax of a language. It consists of a set of terminal symbols (the basic symbols of the language), non-terminal symbols (syntactic variables), a start symbol, and a set of production rules that specify how non-terminals can be replaced by sequences of terminals and non-terminals.

• Formal Definition: A Context-Free Grammar (CFG) is a 4-tuple $G = (V, T, P, S)$, where:
• $V$: Finite set of non-terminal symbols.
• $T$: Finite set of terminal symbols ($V \cap T = \emptyset$).
• $P$: Finite set of production rules of the form $A \rightarrow \alpha$, where $A \in V$ and $\\$alpha \in (V \cup T)^*$.
• $S \in V$: Start symbol.