Back to Study Material GATE Exam

Last Minute Notes Compiler Design

Lexical Analysis: The lexer converts a character stream into tokens using DFAs built from regular expressions. Key terms: token type (identifier, keyword, ...

Last Minute Notes Compiler Design

Quick Revision: Lexical Analysis and Top-Down Parsing

Lexical Analysis: The lexer converts a character stream into tokens using DFAs built from regular expressions. Key terms: token type (identifier, keyword, literal), lexeme (actual text matched), pattern (regular expression defining the token). Lex and Flex are common lexer generator tools. White space and comments are scanned but typically discarded.

Regular expressions to DFA pipeline: write RE, convert to NFA via Thompson's construction, convert NFA to DFA via subset construction, minimize DFA via table-filling. Each step is well-defined and mechanical. For GATE, know which tokens cannot be described by regular expressions (balanced brackets, nested structures) and why.

Top-Down Parsing: starts from start symbol and expands productions to match input. Leftmost derivation is produced. Requires no left recursion and no ambiguity for LL(1).

FIRST set rules: FIRST of terminal a is a. FIRST of epsilon is epsilon. FIRST of nonterminal A includes FIRST of the first symbol of each production, propagating epsilon through nullable prefixes.

FOLLOW set rules: FOLLOW of start symbol includes end-of-input marker. For A goes to alpha B beta, FOLLOW of B includes FIRST of beta minus epsilon, and if beta is nullable includes FOLLOW of A.

LL(1) table: entry M of A and a gets production A goes to alpha when a is in FIRST of alpha, or when epsilon is in FIRST of alpha and a is in FOLLOW of A. Conflict in any cell means grammar is not LL(1).

Left recursion elimination: A goes to A alpha or A goes to beta becomes A goes to beta A prime and A prime goes to alpha A prime or epsilon. Left factoring: A goes to alpha beta1 or alpha beta2 becomes A goes to alpha A prime and A prime goes to beta1 or beta2.

LL(1) parsing uses an explicit stack. Start by pushing end marker and start symbol. On each step, if top is a terminal match it, else expand using table entry. Error if mismatch.

Quick recall: LL(1) cannot handle left recursion or ambiguous grammars. It is simpler to implement but less powerful than LR. Most arithmetic expression grammars require left-recursion elimination before LL(1) parsing.

Quick Revision: LR Parsing and Syntax-Directed Translation

LR Parsing: reads input left to right, produces rightmost derivation in reverse. Uses a stack of states and a parsing table with shift and reduce actions.

LR(0) items: productions with a dot. Closure: for each dot before a nonterminal B, add all B productions with dot at start. Goto: advance dot past a given symbol across all relevant items.

SLR(1) reduce rule: add reduce action for A goes to alpha in state s only for tokens in FOLLOW of A. Shift-reduce conflict: a state has both a shift and a reduce on the same token. Reduce-reduce conflict: a state has two different reduces on the same token. If either conflict appears, the grammar is not SLR(1).

LALR(1): merge LR(1) states that have identical cores (items without lookaheads). Smaller tables than canonical LR(1). Handles more grammars than SLR(1). May introduce reduce-reduce conflicts that canonical LR(1) avoids.

Power ranking: LR(0) is weakest, then SLR(1), then LALR(1), then canonical LR(1) is strongest among the LR family. LL(1) and LR(0) are incomparable: each handles some grammars the other cannot.

Syntax-Directed Translation: attaches semantic rules to grammar productions. Synthesized attributes computed from children. Inherited attributes computed from parent and left siblings. S-attributed: all synthesized, can be evaluated in single bottom-up pass. L-attributed: synthesized plus left-to-right inherited, can be evaluated in single left-to-right pass.

Annotated parse tree evaluation: assign attributes to nodes, evaluate leaves first, then internal nodes in dependency order. For GATE questions, trace the evaluation step by step using the given semantic rules.

Translation schemes: embed actions in grammar productions in the positions where they should execute during parsing. For SDT in top-down parsers, only L-attributed definitions can be evaluated on the fly.

Key facts: three-address code uses at most two operands and one operator per instruction. Quadruples store operator, two operands, result. Triples store operator and two operands, with the triple number serving as implicit result reference.

Quick Revision: Code Optimization and Runtime Environments

Code Optimization transforms intermediate code to improve execution speed or reduce memory use without changing program semantics. Optimizations are either machine-independent or machine-dependent.

Basic blocks are maximal sequences of instructions with one entry point and one exit point. No branches into the middle and no branches out except at the end. Control flow graphs connect basic blocks with directed edges showing possible execution flow.

Machine-independent optimizations to know for GATE: constant folding evaluates constant expressions at compile time. Constant propagation replaces a variable with its known constant value. Dead code elimination removes code whose results are never used. Common subexpression elimination identifies expressions that compute the same value and computes them only once. Copy propagation replaces a copy assignment with the original. Loop invariant code motion moves computations from inside a loop to outside if the result does not change across iterations.

Dataflow analysis computes information about how data values flow through the program. Reaching definitions analysis determines which assignments can reach a given program point. Live variable analysis determines which variables might be read after a given program point. These analyses underpin many optimizations.

Runtime Environments manage memory during execution. The text segment holds compiled code. The data segment holds global and static variables. The heap holds dynamically allocated memory. The stack holds activation records for function calls.

Activation record contents: return address, old frame pointer or control link, access link for lexical scoping, actual parameters, local variables, temporary storage. Stack grows toward lower addresses in most architectures.

For recursive calls, each call creates a new activation record on the stack. The access link in each record points to the enclosing scope's record. The control link points to the caller's record and is used to restore the stack on return.

For GATE last-minute preparation: know the three sources of optimization opportunity (redundant computation, dead code, loop inefficiency), be able to trace a small dataflow analysis by hand, and be able to draw the stack after a sequence of function calls for a simple recursive example. These three skills together cover most of the runtime and optimization questions GATE has asked in recent years.