Compiler phases and structure
The analysis and synthesis phases of a compiler, what each phase takes in and gives out, the symbol table and error handler, passes, and which phase reports which kind of error.
CD · GATE CS 2027
Compiler Design
10 topics and 22 sheets. Open a topic for its sheets and the topics it depends on.
Topics
Lexical analysis
Tokens, lexemes and patterns, longest match and rule priority, counting tokens in C fragments, lexical errors, input buffering with sentinels, and how a regular expression becomes a DFA for the scanner.
Top-down parsing: FIRST, FOLLOW and LL(1)
Derivations, parse trees and ambiguity, left recursion removal and left factoring, FIRST and FOLLOW computed to a fixed point, the LL(1) table and its conflicts, predictive parsing traces and recursive descent.
Bottom-up parsing: LR(0), SLR, LALR and CLR
Handles and shift-reduce parsing, operator precedence, LR(0) items and automata, SLR, CLR(1) and LALR(1) tables, shift-reduce and reduce-reduce conflicts, state counts, and which grammar falls in which class.
Syntax-directed translation
Syntax-directed definitions with synthesized and inherited attributes, S-attributed and L-attributed definitions, dependency graphs and evaluation order, and translation schemes evaluated on given inputs.
Runtime environments
Static, stack and heap storage, activation records and the control stack, access links and displays, static and dynamic scoping, and parameter passing by value, reference, value-result and name.
Intermediate code generation
Syntax trees, DAGs, postfix and three-address code, quadruples, triples and indirect triples, SSA form, array addressing, translation of control flow and Boolean expressions, and backpatching.
Basic blocks, DAGs and local optimisation
Leaders, basic blocks and flow graphs, loops and dominators, the DAG of a block, common-subexpression and dead-code elimination, folding, copy propagation, strength reduction, peephole rules and register counts.
Data-flow analysis: constant propagation, liveness and CSE
The data-flow framework, reaching definitions, available expressions for global common-subexpression elimination, liveness solved backward by iteration, and constant propagation on its lattice.
Compiler Design revision: traps, patterns and last day
The Compiler Design traps sheet, the question-pattern sheet and the last-day master sheet.
All Compiler Design sheets
Compiler Phases and Structure
The six phases of a compiler in order, split into the analysis front end and the synthesis back end, with the input and output of each phase. One assignment is followed through every phase, from tokens to target code. A table assigns typical errors to the phase that reports them (lexical, syntax, semantic, or none because the fault appears only at run time). Also covers the symbol table and what it stores, error recovery strategies, passes, front end and back end reuse, and compilers versus interpreters.
Lexical Analysis and Tokens
Tokens, lexemes and patterns with a reference table, the two disambiguation rules (longest match, then the earliest rule) and how keywords are separated from identifiers. Script-counted token totals for C fragments including a+++b, a--->b, string literals with escapes and comments. A transition diagram for relational operators shows lookahead and retraction. Also covers input buffering with sentinels, lexical errors and their recovery, the structure of a Lex specification, and turning a regular expression into a minimal DFA.
Ambiguity and Grammar Clean-up
Context-free grammar vocabulary for parsing: sentential forms, leftmost and rightmost derivations, parse trees and ambiguity, with script-counted parse trees for the classic ambiguous grammars. How precedence and associativity are built into a grammar with one non-terminal per level. Removal of immediate and indirect left recursion with the general algorithm and worked results, left factoring step by step, and why neither transformation removes ambiguity: the left-factored dangling-else grammar still has an LL(1) conflict.
FIRST and FOLLOW
The two fixed-point procedures for FIRST and FOLLOW written as ordered steps, FIRST of a string of symbols, and the rules that trip students: ε lives only in FIRST, $ only in FOLLOW, and the copy rule runs from the head into the last non-terminal. Worked sets for the LL(1) expression grammar with the FOLLOW sets shown pass by pass, a chain of nullable symbols, an original grammar where nullable symbols expose later terminals, and the FOLLOW of a start symbol that also appears inside a body. All sets come from a script.
LL(1) Tables and Predictive Parsing
The LL(1) condition for every pair of alternatives, the procedure that fills M[A, a], and the full table for the expression grammar. A complete predictive-parsing trace of id + id * id with stack, input and action, recursive descent as one procedure per non-terminal, panic-mode recovery with synchronising sets, signals that rule out LL(1) at a glance, a script-found conflict, and LL(1) facts that past questions test.
Shift-Reduce Parsing and Handles
Bottom-up parsing as a rightmost derivation in reverse: handles, handle pruning and viable prefixes. A full SLR-driven trace of id * id + id with states, input and action, counted shifts and reductions, the four actions, and the two kinds of conflict with their usual causes. Operator-precedence parsing in brief: operator grammars, the precedence relations computed from LEADING and TRAILING sets, and the limits of the method. All tables and traces come from a script.
LR(0) Automaton and SLR Tables
LR(0) items, closure and goto, and the canonical collection built step by step, with the seven-state automaton of S → AA, A → aA | b drawn and its LR(0) and SLR tables in full. How to count items versus states, when a state is free of LR(0) conflicts, why the expression grammar fails LR(0) on * and passes SLR, how ε-productions create complete items in the start state, and a solved past question that counts LR(0) shift-reduce conflicts cell by cell. Every set, table and count comes from a script.
CLR(1) and LALR(1) Parsing
LR(1) items and the closure rule that computes lookaheads from FIRST(βa). The ten canonical LR(1) states of S → AA, A → aA | b and how equal cores merge into the seven LALR(1) states. Why S → L = R | R is LALR(1) but not SLR(1), why a grammar can be CLR(1) but not LALR(1) (merging creates reduce-reduce conflicts, never shift-reduce ones), state-count facts for the standard grammars, LALR error detection, and a solved past question. Every state, lookahead and count comes from a script.
Which Parser Accepts Which Grammar
A master comparison of LL(1), LR(0), SLR(1), LALR(1) and CLR(1) parsers: direction, items, where reductions go, state counts and the conflicts each can have. A class map with seven script-checked separating grammars, including an LL(1) grammar that is not LALR(1), an ordered conflict-detection routine, statements about grammar classes that hold and those that do not, and the difference between grammar classes and language classes.
Syntax-Directed Definitions and Attributes
Syntax-directed definitions: grammar plus semantic rules, synthesized and inherited attributes, the annotated parse tree of 2 * 3 + 4 with every value, dependency graphs and topological evaluation order. S-attributed and L-attributed definitions compared, a routine that classifies any rule, an inherited attribute passing a declared type down a list of names, and solved past questions on classification and evaluation. Values come from a script that runs the rules on a real parser.
Translation Schemes and Evaluations
Syntax-directed translation schemes: actions embedded in production bodies, postfix schemes executed at reductions, and marker non-terminals for actions in the middle of a body. Script-run evaluations: infix to postfix output, the print order of a scheme with ε-productions, operators with invented semantics where the grammar decides precedence and associativity, a type-and-width computation for arrays, an inherited attribute carried through an LL grammar, and bottom-up evaluation with a value stack.
Runtime Storage and Activation Records
Run-time memory layout (code, static data, heap, stack), static, stack and heap allocation and what each supports, the fields of an activation record, activation trees and the control stack with script-counted activations for recursive calls, calling and return sequences, and how non-local names are reached under nested procedures with access links or a display. A diagram shows four live frames whose control links and access links differ.
Scoping and Parameter Passing
Static and dynamic scoping rules with three script-run programs, including nested procedures where the access link and the control link lead to different variables. Parameter passing by value, reference, value-result and name compared, with outputs of the same programs under every mode: aliasing through f(x, x), a global changed inside the callee, and the swap(i, a[i]) failure under call by name. Conventions that change the answer, such as the copy-back order of value-result, are marked.
Intermediate Representations
The intermediate forms GATE asks about, side by side on the same expressions: syntax trees and DAGs with node counts, postfix notation, three-address code instruction kinds, quadruples, triples and indirect triples with their trade-offs, and static single assignment form with φ-functions. Script-produced TAC with and without common-subexpression reuse, temporary counts, and the value-numbering method that builds a DAG.
Control Flow and Backpatching
Syntax-directed generation of three-address code for expressions and assignments, array addressing with the row-major offset formula and its variants, code layouts for if, if-else and while, short-circuit (jumping) code for Boolean expressions, and backpatching with truelist, falselist and nextlist on a fully traced example that the script generated instruction by instruction. Includes a solved past question on one-pass translation.
Basic Blocks, Flow Graphs and Loops
The leader rules and the partition of three-address code into basic blocks, flow-graph edges for fall-through and jumps, dominators, back edges and natural loops, worked on a ten-line loop that is drawn as a flow graph. Two solved past questions count blocks and the largest block, and the traps about jump lines versus jump targets. Every leader, edge and loop comes from a script.
Block DAGs and Local Optimisation
The DAG of a basic block built by value numbering, drawn for a classic block and used for local common-subexpression and dead-code elimination. The local rewrites (constant folding and propagation, copy propagation, algebraic identities, strength reduction, dead code) applied in sequence to one block with a script check that the live results never change, peephole rules, and register and temporary counts: Ershov labels for an expression tree and the maximum number of live values in a straight-line block.
Reaching Definitions, Available Expressions
The data-flow framework (direction, transfer function, meet, boundary and initial values) and the round-robin iterative algorithm. Reaching definitions with gen and kill sets and a round-by-round fixed point on a four-block loop, used for use-definition chains and constant propagation. Available expressions with e_gen and e_kill, the intersection meet, why non-entry blocks start at the full set, and how the result drives global common-subexpression elimination. All sets come from a script.
Liveness and Constant Propagation
Live-variable analysis: use and def sets, the backward equations, a pass-by-pass iteration on a four-block flow graph with a loop, statement-level liveness inside a block, and what liveness is used for (register allocation, dead stores). Constant propagation: the UNDEF, constant, NAC lattice, its meet table, the transfer function, a worked branch-and-join example, a loop, and why the iterative result can be weaker than checking each path. Every set and value comes from a script.
Compiler Design Traps
Thirty common mistakes across the Compiler Design syllabus, each written as the wrong belief, the correct rule and a short check or example: token counting, FIRST and FOLLOW, LL(1) and the LR family, syntax-directed translation, runtime environments, intermediate code, basic blocks, DAGs and data-flow analysis. Each row points to the sheet that explains it.
Question Patterns and Routines
The recurring Compiler Design question shapes, each with the cue that identifies it, the routine to run, the check that most often changes the answer, and the sheet that holds the method: token counts, phase of an error, FIRST and FOLLOW, LL(1) tests, LR state and conflict counts, parser classes, SDT outputs, runtime outputs, TAC and DAG counts, basic blocks, liveness, available expressions and constant propagation.
Master Last-Day Revision Sheet
A one-page summary of the Compiler Design pack: phases and their errors, scanner rules, FIRST and FOLLOW, the LL(1) test, the LR family with state counts and separating grammars, S- and L-attributed definitions, activation records, scoping and parameter passing, TAC forms, leaders and DAGs, and the data-flow analyses with their equations. All numbers are the script-checked values used on the topic sheets.
Connected subjects
Theory of ComputationData StructuresProgramming in CComputer Organization & Architecture