Compiler Design Introduction: Phases & Architecture Explained

A parser (syntax analyzer) takes token streams and generates parse trees. Parsers are categorized into two main types: Top-Down parsers start from the root symbol and proceed downward, while Bottom-Up parsers (shift-reduce) start from the bottom and construct trees bottom-to-top. Top-Down parsers include: (1) With backtracking using brute force to explore all possibilities; (2) Without backtracking (predictive parsers) that must choose correct productions in advance. Recursive descent parsers use recursion for straightforward design, while non-recursive descent (LR) parsers use stacks to handle left recursion and left factoring. LL(1) parsers require grammars free of left recursion, left factoring, and ambiguity. Bottom-Up parsers include LR parsers (handling left recursion/factoring) and operator precedence parsers (handling ambiguous operator grammars). LR parsers come in four types: LR(0), SLR(1), LALR(1), and CLR(1).

A parser is a program that generates a parse tree for a given string if the string is generated from the underlying grammar; parse trees can be generated using two approaches—top-down parsing (which uses leftmost derivation starting from the start symbol and deciding which production to use at each step) and bottom-up parsing (which uses rightmost derivation in reverse, starting from the string and reducing it back to the start symbol through successive reductions); parsers are classified into top-down parsers (with backtracking and without backtracking, including recursive descent and predictive parsers like LL(1)) and bottom-up parsers (also called shift-reduce parsers, including operator precedence parsers and LR parsers such as LR(0), SLR(1), LALR(1), and CLR(1)), where LR parsers increase in power from LR(0) to SLR(1) to LALR(1) to CLR(1).

Top-down parsing starts from the start symbol and generates the string by making production choices at each step, following leftmost derivation. Bottom-up parsing starts from terminals and works upward to the start symbol, following the reverse of rightmost derivation. The main decision in top-down parsing is which production to use for a variable. The main decision in bottom-up parsing is when to reduce and which production to use. Both approaches construct parse trees but in fundamentally different directions.

There are three types of parsers: universal parser (inefficient and rarely used), top-down parser, and bottom-up parser. Top-down parsing starts from the root node and expands step by step until the output string is generated. LL parsing is a top-down approach where the first L stands for left-to-right scanning and the second L stands for leftmost derivation. The parser scans the input from left to right and always derives the leftmost non-terminal first. Bottom-up parsing starts from the output string and reduces to the root node. LR parsing is a bottom-up approach where the first L stands for left-to-right scanning and the R stands for rightmost derivation in reverse. The parser scans the input from left to right but derives from the rightmost non-terminal in reverse order.

LL(1) grammars must be context-free, unambiguous, left-recursion-free, and left-factored, but satisfying all four properties does not guarantee LL(1). Detection shortcuts: if First(α1) ∩ First(α2) ≠ ∅ for non-epsilon productions, or First(α) ∩ Follow(A) ≠ ∅ for epsilon productions, the grammar is not LL(1). Left factoring eliminates common prefixes to enable LL(1) parsing. LR grammars are classified as LR(0), SLR(1), LALR(1), and CLR(1), where L stands for left-to-right scan and R for rightmost derivation in reverse. The hierarchy is: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1). LL(1) grammars (without null productions) are a subset of SLR(1). Conflicts: shift-reduce conflicts occur when a state has both shift and reduce items; reduce-reduce conflicts occur when a state has multiple reduce items.

Semantic analysis verifies parse trees are meaningful and consistent with language rules. It performs type checking, scope checking, and other semantic checks. Syntax-directed translation associates semantic actions with grammar rules. When productions are recognized, semantic actions execute to generate intermediate code or perform checks. Attributes (values) are evaluated using inherited or synthesized rules.

Semantic analysis combines context-free grammars with semantic rules to perform type checking, scope resolution, and code generation. Attribute grammars associate attributes with grammar symbols, enabling semantic information propagation. Syntax-directed definitions combine grammar productions with semantic rules. Key applications include: scope resolution (ensuring variables are declared), type checking (ensuring type compatibility), symbol table management, error detection, and intermediate code generation. This phase transforms parse trees into annotated trees with semantic information.

Semantic analysis gives meaning to syntactically recognized programs and generates intermediate code. It performs critical verifications: detecting undeclared identifiers, anticipating capacity overflows, verifying type compatibility, and checking label usage. Syntax-directed translation uses the grammar to determine when to inject semantic routines. The grammar (top-down or bottom-up) provides structure for systematic code generation. A semantic grammar is created by transforming the syntax grammar to add semantic actions. For top-down analysis, new non-terminals are added to grammar rules where actions should occur. For bottom-up analysis, new non-terminals handle reductions.

Semantic analysis is the third phase of the compiler. It takes a syntax tree (the output of syntactic analysis) as input and produces a validated syntax tree as output. Semantic analysis checks whether the program has meaning according to the language's rules, such as type checking and scope resolution. It performs type checking to ensure that operations are performed on compatible types. If the program is semantically correct, semantic analysis produces a validated syntax tree; otherwise, it reports errors.

Semantic analysis performs two main categories of checks: (1) Scope resolution checks - verifying whether a variable has been defined before it is used, and (2) Type checks - verifying that the left-hand side and right-hand side of a statement are of the same type.

This lecture covers three critical compiler design topics: (1) Three Address Code (TAC) optimization techniques including expression analysis, reordering independent statements, and variable reuse to minimize temporary variables; (2) Static Single Assignment (SSA) code generation by first optimizing TAC and then renaming variables to ensure each variable has exactly one definition; (3) Control Flow Graph (CFG) construction where basic blocks are defined as maximal sequences of instructions where control enters only at the first statement and leaves only at the last, with leaders serving as entry points and all control transfers targeting other leaders. These intermediate representations form the foundation for code optimization and assembly code generation in compilers.

Four primary intermediate code representations exist: postfix notation, three address code, syntax tree, and DAG. Three Address Code (TAC) is the most popular format, where each instruction contains at most three operands. For example, 'A + B + C' becomes T1 = A + B, T2 = A + B, T3 = T2 + C. Syntax trees are condensed parse trees using only terminals. DAGs eliminate redundant computations by sharing common subexpressions. TAC uses seven instruction types: binary operations (x = y op z), unary operations (x = op y), assignment (x = y), conditional jumps (if x op y goto L), unconditional jumps (goto L), array indexing (x = a[i]), and pointer dereferencing (x = *p).

Intermediate code serves as a bridge between the front-end (lexical, syntax, and semantic analysis) and back-end (code generation) of a compiler, enabling portability across different programming languages and target machines. The two main categories of intermediate representations are linear representations (postfix code, three-address code, and SSA code) and nonlinear representations (syntax trees and DAGs). Three-address code, where each instruction has at most three addresses, is particularly useful for converting high-level code to assembly code. SSA (Static Single Assignment) code ensures each variable is assigned exactly once, simplifying optimization. Syntax trees represent expressions with operators as internal nodes and operands as leaf nodes, while DAGs eliminate common subexpressions by sharing nodes, making them crucial for code optimization.

Intermediate code generation is a compiler phase that converts high-level source code into low-level intermediate representations to facilitate optimization. Three Address Code (TAC) is a widely-used intermediate representation where each instruction contains at most one operator on the right-hand side, using temporary variables (t1, t2, etc.) and supporting assignment, unary operations, copy, unconditional jumps, conditional jumps, function calls, and indexed addressing. TAC can be implemented using quadruples (four-field records), triples (space-efficient with positional results), or indirect triples (enabling efficient instruction movement). Static Single Assignment (SSA) is another intermediate representation where each variable has exactly one definition in the program text, making compiler optimizations like constant propagation and dead code elimination significantly easier. SSA uses phi functions to handle variable definitions at control flow merge points, ensuring single-definition properties while correctly representing program behavior. Both representations serve as foundational concepts for compiler optimization studies.

Intermediate Code Generation involves DAG construction and three-address code formats. For DAG: assign IDs to unique terminals, process from innermost brackets, create nodes for operations, reuse nodes for shared subexpressions. Three-address code formats include quadruples (operator, arg1, arg2, result), triples (operator, arg1, arg2), indirect triples (using addresses), and static single assignment (each variable assigned once). The DAG optimizes expressions by eliminating redundant computations.

Code optimization is the process of improving a program's efficiency without changing its output; it includes machine-dependent techniques such as register allocation and instruction scheduling that leverage specific hardware features, and machine-independent techniques like constant folding and dead code elimination that work across different platforms.

Register allocation assigns program variables to CPU registers, balancing register pressure against spill costs. The process involves graph coloring, linear scan, and graph coloring algorithms. Optimization strategies include dead code elimination, constant propagation, loop optimization, and instruction selection. The code generator must handle complex scenarios like register renaming, instruction scheduling, and architectural constraints while maintaining program correctness and optimizing performance.

LLVM IR is the core of LLVM, represented as bitcode (.bc files). It is strongly typed with higher-level constructs like function definitions and calls, abstracting away architecture-specific calling conventions. LLVM IR has infinite registers, simplifying analysis by making each variable assignment a distinct operation. The back-end performs machine-dependent optimization including instruction selection, register allocation, and code generation for target architectures.

Machine-dependent optimizations in code generation involve improving target code through techniques like peephole optimization (examining short instruction sequences and replacing them with better alternatives), redundant load/store elimination (removing unnecessary memory operations), unreachable code elimination (removing code that cannot be executed), flow control optimization (simplifying jump instructions), instruction selection (choosing appropriate target instructions based on IR level and architecture), machine idioms (using built-in efficient instructions like INCR), register allocation (assigning variables to CPU registers for faster access), and evaluation order selection (determining the optimal sequence for executing operations to maximize efficiency).

The code generation phase takes the optimized intermediate representation as input and generates target machine code or assembly code. This phase is machine-dependent because it must produce instructions valid for the target CPU's instruction set. Machine-dependent code optimization operates on the generated assembly code and uses the specific features of the target CPU. For example, if a CPU has a 'branch if less than' instruction, two separate instructions (a comparison and a conditional branch) can be replaced with a single 'branch if less than' instruction, reducing code size and execution time. The compiler is divided into front end (lexical analysis, syntax analysis, semantic analysis, intermediate code generation) and back end (intermediate code optimization, code generation, machine-dependent optimization). The front end is source-language-dependent but machine-independent, while the back end is machine-dependent.