Back to Study Material GATE Exam

Compiler Design

A compiler is a program that translates source code written in a high-level programming language into low-level code, typically machine code or assembly, t...

Compiler Design

Overview of Compiler Design: Phases and Their Roles

A compiler is a program that translates source code written in a high-level programming language into low-level code, typically machine code or assembly, that a processor can execute directly. Understanding how a compiler works is important not just for building compilers but for understanding programming language semantics, optimization, and the nature of translation in general.

The compilation process is organized into a sequence of phases, each performing a specific transformation on the program representation. The first phase is lexical analysis, performed by the lexer or scanner. The lexer reads the stream of characters in the source file and groups them into tokens, which are meaningful units like keywords, identifiers, operators, and literals. The lexer is typically implemented using a DFA constructed from regular expressions that describe each token type.

The second phase is syntax analysis, performed by the parser. The parser takes the stream of tokens and builds a parse tree or abstract syntax tree that reflects the grammatical structure of the program. Parsers use context-free grammars to define the syntax of the language. There are two main parsing strategies: top-down parsing, which starts from the grammar's start symbol and tries to match the input, and bottom-up parsing, which starts from the input and tries to reduce it to the start symbol.

The third phase is semantic analysis. Here the compiler checks for semantic errors that the grammar cannot catch, such as type mismatches, undeclared variables, and incorrect function call signatures. The symbol table, which stores information about identifiers declared in the program, plays a central role in this phase.

The fourth phase is intermediate code generation. The compiler produces an intermediate representation of the program, such as three-address code or a control flow graph, that is independent of both the source language and the target machine. This abstraction makes it easier to apply optimizations before final code generation.

Subsequent phases include code optimization, which improves the intermediate code for efficiency, and code generation, which produces the final target code. Many compilers also include a linker and assembler as downstream tools. Understanding the division of responsibilities across these phases is the foundation of Compiler Design for GATE.

Lexical Analysis and Syntax Analysis in Depth

Lexical analysis is the first transformation a compiler applies to source code. The lexer scans the input character by character and groups characters into tokens according to the pattern rules specified by regular expressions. Each token has a type, such as identifier, integer literal, or operator, and a value, which is the actual text matched.

The implementation of a lexer relies directly on the automata theory covered in TOC. Regular expressions for each token type are combined using the union operation, and the resulting expression is converted to an NFA using Thompson's construction, then to a DFA using subset construction, and finally minimized. The resulting DFA is the heart of the lexer. When building a lexer by hand or with a tool like Lex, you define patterns and the lexer generator does the automaton construction for you.

Tokens that look like keywords, such as if, else, while, and for, are often handled by first recognizing them as identifiers and then checking a reserved word table. White space and comments are typically recognized and discarded rather than passed to the parser as tokens.

Syntax analysis uses a context-free grammar to define the valid sentence structure of the program. The parser takes the token stream and either builds a concrete or abstract syntax tree or reports syntax errors. Top-down parsers work by predicting which production to apply based on the current input token. The LL(1) parser is the most studied top-down parser: the first L means it reads input left to right, the second L means it produces a leftmost derivation, and the 1 means it uses one token of lookahead.

For a grammar to be LL(1), it must have no left recursion and no ambiguity, and the FIRST and FOLLOW sets of alternatives must be disjoint. Eliminating left recursion is done by transforming left-recursive rules into right-recursive ones with an extra nonterminal. Left factoring resolves rules that start with the same terminals.

Bottom-up parsers, particularly LR parsers and their variants SLR, LALR, and canonical LR, are more powerful than LL parsers and can handle a broader class of grammars. The LR parsing algorithm uses a stack to track the parse state and a parsing table to decide whether to shift the next token onto the stack or reduce the top of the stack using a production. GATE questions frequently ask about constructing or reading these parsing tables.

Semantic Analysis, Intermediate Code, and Optimization

Once the parser has verified that the program is syntactically correct and constructed a parse tree or abstract syntax tree, the compiler moves into semantic analysis. This phase enforces the meaning rules of the language that go beyond what a grammar can express. Type checking is the central activity: the compiler verifies that operations are applied to operands of compatible types, that functions are called with the right number and types of arguments, and that variables are declared before use.

The symbol table is the data structure that makes semantic analysis possible. It maps identifier names to their attributes, including type, scope, and memory location. When the compiler encounters a declaration, it adds an entry to the symbol table. When it encounters a use of an identifier, it looks up the entry to retrieve the attributes. Scope rules determine which declarations are visible at each point in the program: in most languages, inner scopes can shadow outer ones, and the symbol table implementation must handle this, often using a stack of scopes or a scoped hash table.

Attribute grammars are the theoretical framework for describing semantic analysis. Each grammar symbol has a set of attributes, and each production rule has a set of semantic rules that define how to compute the attributes of a node from the attributes of its children or parent. Synthesized attributes flow upward in the parse tree from children to parents. Inherited attributes flow downward from parents and siblings. A grammar is an S-attributed grammar if all attributes are synthesized. An L-attributed grammar allows inherited attributes but only from left siblings and parents, which makes it compatible with a single left-to-right traversal.

Intermediate code generation translates the decorated syntax tree into a lower-level but still machine-independent representation. Three-address code is the most commonly studied form: each instruction has at most one operator, two operands, and one result. Quadruples and triples are two implementation formats for three-address code.

Code optimization improves the intermediate code without changing what the program computes. Machine-independent optimizations include constant folding, dead code elimination, common subexpression elimination, and loop invariant code motion. Loop optimizations are especially valuable because programs spend most of their time in loops. For GATE, focus on recognizing basic blocks, constructing control flow graphs, and identifying the optimizations applicable to a given code fragment.