Glossary of Compiler Design Terms

How to Use This Glossary

This glossary provides clear, concise definitions of all important terms in compiler design. Terms are organized alphabetically, with cross-references to related concepts. Use this as a quick reference when studying — if you encounter an unfamiliar term in lectures or textbooks, look it up here for a student-friendly explanation with context.

A

Abstract Syntax Tree (AST): A simplified tree representation of program structure. Unlike the full parse tree, an AST omits grammar-specific details (like intermediate nonterminals) and retains only the semantically meaningful nodes — operators, operands, declarations, and statements. The AST is the primary data structure passed from the parser to semantic analysis and code generation.

Activation Record (Stack Frame): A block of memory allocated on the stack each time a function is called. Contains the function's local variables, parameters, return address, and saved registers. Destroyed automatically when the function returns. Enables recursion because each call gets its own independent storage.

Ambiguous Grammar: A grammar that produces two or more distinct parse trees for the same input string. For example, E → E+E | E*E | id is ambiguous because a+b*c can be parsed two ways. Must be resolved through precedence rules or grammar rewriting.

Attribute Grammar: A formal framework that augments a context-free grammar with attributes (properties) attached to grammar symbols and semantic rules that define how to compute attribute values. Used to specify type checking, code generation, and other semantic computations declaratively.

Augmented Grammar: The original grammar with an added production S' → S (where S is the original start symbol). Used in LR parsing to provide a unique acceptance state — the parser accepts when it reduces by this added production.

B

Backend: The portion of a compiler that converts intermediate representation to target machine code. Includes instruction selection, register allocation, and instruction scheduling. The backend is target-specific — different backends for x86, ARM, MIPS, etc.

Basic Block: A maximal sequence of consecutive instructions with no branches in (except at entry) and no branches out (except at exit). Within a basic block, every instruction executes exactly once if the block is entered. Used as the unit for local optimization.

Binding: The association between a name (identifier) and its definition. Static binding is determined at compile time (most variables in C). Dynamic binding is determined at runtime (virtual methods in OOP). The symbol table records bindings.

Bottom-Up Parsing: Parsing strategy that builds the parse tree from leaves (input tokens) upward to the root (start symbol). Uses shift-reduce actions. More powerful than top-down parsing — can handle left-recursive grammars. LR, SLR, LALR, and CLR are all bottom-up methods.

Bytecode: An intermediate representation designed for execution by a virtual machine rather than real hardware. Higher-level than machine code (more portable) but lower-level than source code (faster to interpret). Examples: Java bytecode (JVM), Python bytecode (CPython), .NET CIL.

C

Calling Convention: The protocol defining how functions receive parameters and return results at the machine level — which registers carry arguments, who saves/restores registers, where the return value goes. Different platforms use different conventions (System V ABI for Linux, Microsoft x64 for Windows).

Code Generation: The final compiler phase that translates intermediate representation into target machine instructions. Involves instruction selection (choosing which machine instructions to use), register allocation (mapping variables to CPU registers), and instruction scheduling (ordering instructions to minimize pipeline stalls).

Code Optimization: Transformations applied to intermediate or target code that improve performance or reduce size without changing program semantics. Local optimizations work within basic blocks; global optimizations work across blocks; interprocedural optimizations cross function boundaries.

Common Subexpression Elimination (CSE): An optimization that identifies expressions computed multiple times with the same operands and replaces redundant computations with a reference to the first result. Example: if a+b appears twice and neither a nor b changes between them, compute once and reuse.

Context-Free Grammar (CFG): A formal grammar where every production rule has a single nonterminal on the left side, meaning replacements are independent of surrounding context. The standard formalism for specifying programming language syntax. Recognized by pushdown automata and parsed by LL/LR algorithms.

Cross-Compiler: A compiler that runs on one platform (the host) but generates code for a different platform (the target). Example: compiling ARM code on an x86 laptop for deployment to a mobile device.

D

Dead Code: Code that can never be executed (unreachable) or whose results are never used. Dead code elimination removes such code to reduce program size and improve cache behavior. Examples: code after an unconditional return, variables assigned but never read.

Dependency Graph: A directed graph showing how attributes depend on each other in an attribute grammar. Nodes represent attribute instances; edges represent dependencies. Used to determine a valid evaluation order — attributes must be computed after all their dependencies.

Derivation: The process of repeatedly applying production rules to transform the start symbol into a string of terminals. A leftmost derivation always expands the leftmost nonterminal; a rightmost derivation always expands the rightmost.

Deterministic Finite Automaton (DFA): A finite-state machine where for each state and input symbol, exactly one transition exists. Used in lexers because they provide O(1)-per-character processing with no backtracking. Every NFA can be converted to an equivalent DFA.

F

FIRST Set: For a grammar symbol X, FIRST(X) is the set of all terminal symbols that can appear at the beginning of strings derived from X. If X can derive the empty string, then ε ∈ FIRST(X). Essential for constructing LL(1) parsing tables.

FOLLOW Set: For a nonterminal A, FOLLOW(A) is the set of terminal symbols that can appear immediately after A in some derivation from the start symbol. Always includes $ (end-of-input) for the start symbol. Used together with FIRST sets for LL(1) table construction.

Frontend: The portion of a compiler that analyzes source code — lexical analysis, parsing, and semantic analysis. Language-specific but target-independent. A compiler can have multiple frontends (for different languages) sharing a single backend.

G-H

Garbage Collection: Automatic reclamation of dynamically allocated memory that is no longer reachable by the program. Eliminates manual memory management (and associated bugs). Algorithms include mark-and-sweep, reference counting, and generational collection.

Handle: In bottom-up parsing, the handle is the substring of the current sentential form that matches the right-hand side of a production and should be reduced next. Identifying the handle correctly is the core challenge of shift-reduce parsing.

Hash Table: The preferred data structure for symbol tables due to O(1) average-case lookup, insertion, and deletion. Identifiers are hashed to array indices; collisions handled by chaining or open addressing.

I-L

Intermediate Representation (IR): A language-independent, machine-independent representation used between the frontend and backend. Enables optimizations that are neither source-specific nor target-specific. Common forms: three-address code, SSA form, control flow graphs.

Interpreter: A program that executes source code directly without prior compilation to machine code. Reads statements one at a time, translates each to operations, and executes immediately. Faster development cycle but slower execution than compiled code.

LR Item: A grammar production with a dot marking the current parsing position. A → X•YZ means X has been seen (shifted), and Y is expected next. Sets of items form the states in an LR parser's automaton.

Lexeme: The actual character sequence in source code that forms a token. For the token INTEGER, the lexeme might be "42" or "100". For the token KEYWORD_IF, the lexeme is always "if".

M-O

Nondeterministic Finite Automaton (NFA): A finite-state machine that may have multiple transitions for the same (state, input) pair, or epsilon (ε) transitions that consume no input. Easier to construct from regular expressions but must be converted to DFA for efficient execution.

Object Code: Machine language output produced by the assembler. Contains binary-encoded instructions but may have unresolved external references that the linker must fix. Stored in object files (.o or .obj).

Optimization Pass: A single traversal of the IR that applies one type of optimization. Compilers typically run multiple passes in sequence, as one optimization may enable another (e.g., constant propagation enables constant folding).

P-R

Parse Tree (Concrete Syntax Tree): A tree showing the complete derivation of input from the grammar. Every internal node is a nonterminal, every leaf is a terminal. More detailed than an AST — includes all grammar artifacts.

Peephole Optimization: Optimization applied to a small sliding window of consecutive instructions. Looks for patterns that can be replaced with more efficient sequences. Example: replacing LOAD R1, X; STORE X, R1 (useless load-store pair) with nothing.

Register Allocation: The process of assigning program variables to a limited number of CPU registers. Since registers are fastest, keeping frequently-used values in registers dramatically improves performance. Often modeled as graph coloring — variables that are live simultaneously cannot share a register.

Regular Expression: A pattern notation for describing sets of strings. Used in lexical analysis to define token patterns. Operators include concatenation, alternation (|), and Kleene star (*). Equivalent in power to finite automata.

S-T

Scope: The region of a program where a binding (name → declaration) is active. Lexical scope is determined by program text structure; dynamic scope is determined by the runtime call chain. Most modern languages use lexical scoping.

Semantic Analysis: The compiler phase that checks meaning and consistency beyond syntax — type compatibility, scope validity, declaration before use, correct number of function arguments. Produces an annotated AST with type information attached.

Symbol Table: A data structure mapping identifier names to their attributes (type, scope, memory address, etc.). Maintained throughout compilation and consulted by every phase from semantic analysis to code generation.

Synthesized Attribute: An attribute of a parse tree node computed from the attributes of its children. Flows upward through the tree. Example: the type of an expression is synthesized from the types of its operands.

Three-Address Code: An IR format where each instruction has at most three addresses (two operands and one result). Example: t1 = a + b. Easy to optimize and translate to machine code. Named because most instructions reference three locations.

Top-Down Parsing: Parsing strategy that builds the parse tree from the root (start symbol) downward to the leaves (input tokens). LL(1) and recursive descent are top-down methods. Cannot directly handle left-recursive grammars.

Type Checking: Verifying that operations in a program are applied to compatible types. Static type checking happens at compile time; dynamic type checking happens at runtime. Catches errors like adding a string to an integer or calling a non-function value.