Keep the compiler pipeline visible throughout this section: source characters become tokens; tokens are checked against grammar; semantic meaning and types are checked; intermediate forms may be produced; and target code is finally generated and optimized. Formal language tools (regular expressions, finite automata, context-free grammars) matter specifically because they make each stage of recognition and translation mathematically precise rather than ad hoc.
A. Translators and the Compiler Pipeline
A translator converts code from one language or form into another. A compiler translates a whole program ahead of time into another form (commonly machine code); an assembler translates assembly language specifically; an interpreter executes or translates in a fundamentally different style, working through the program’s logic directly rather than producing the same kind of complete ahead-of-time output a compiler does. A typical compiler pipeline includes, in order: lexical analysis, syntax analysis, semantic analysis, intermediate-representation generation, optimization, and code generation — all supported throughout by symbol-table management and error handling. Example: the source code “x = a + 3” is first broken into individual tokens (x, =, a, +, 3), then checked against the language’s grammar, then checked for semantic correctness (are the types of a and 3 compatible with addition?), then transformed into an internal intermediate form, and finally mapped onto actual target-machine instructions. Being able to say, for each phase, what specific kind of error it is capable of catching (a lexical error, a syntax error, a semantic/type error) is a reliable, concrete exam skill.
B. Lexical Analysis and Syntax Analysis
Lexical analysis groups the raw input characters into tokens — identifiers, numbers, keywords, and operators. Regular expressions describe the precise patterns that define what a valid token of each type looks like, and finite automata are the formal machines that recognize exactly the languages describable by regular expressions — the two are tightly linked, since a regular expression can be mechanically converted into an equivalent finite automaton that recognizes it. Example: a simplified pattern for an identifier might require a letter followed by any number of letters or digits, and the lexer recognizes an entire matching sequence of characters as a single identifier token, not as separate individual characters.
Syntax analysis then checks whether this sequence of tokens actually follows the programming language’s grammar, and builds a structural representation (a parse tree) of that sequence. Context-free grammars define the productions (rewriting rules) that specify what counts as valid structure in the language. Top-down parsers begin from the grammar’s start symbol and work down toward matching the input; bottom-up parsers instead build upward starting directly from the input tokens. LL and LR are two major parser families with different grammar-handling capabilities, and FIRST and FOLLOW sets are computed directly from the grammar to help construct predictive LL(1) parsing tables. Example: an expression grammar can enforce that multiplication binds more tightly than addition (the standard order of operations) purely through how its nonterminals and productions are structured, without needing any special-case rule bolted on separately.
C. Semantic Analysis and Syntax-Directed Translation
Syntax-directed translation attaches meaning and actions directly to grammar structure, so that as a parse tree is built, associated computation happens alongside it. Semantic analysis then checks the rules grammar alone cannot enforce — most importantly, type checking, which verifies that operations and assignments are actually compatible with the types involved. Example: the grammar may happily allow “x + y” as syntactically valid, but semantic analysis can still reject this expression if x and y have incompatible types and no legal implicit conversion exists between them — syntax and semantics are genuinely separate layers of correctness. Synthesized attributes pass information upward through the parse structure (from children to parent); inherited attributes pass information downward (from parent to children) — together these let a compiler compute meaning across an entire parse tree systematically. A symbol table stores declarations and scope information throughout compilation, tracking which names are visible where and what they refer to.
D. Intermediate Code, Code Generation, and Optimization
Intermediate code is a machine-independent, or semi-independent, representation sitting between the original source syntax and the final target code — it exists so that much of a compiler’s analysis and optimization work can be done once, independent of any specific target machine. Code generation then maps this intermediate representation onto actual target-machine instructions, requiring decisions about instruction selection, address calculation, calling conventions, storage layout, and register allocation (deciding which values live in fast registers versus slower memory). Run-time storage is commonly organized into a stack (for function calls and local variables), a heap (for dynamically allocated data), and static areas (for global and fixed data), depending on the specific language and runtime. Example: a repeated arithmetic expression can first be represented in a simple three-address intermediate form (each instruction has at most three operands) before being converted into actual machine instructions in the final code-generation phase.
Code optimization changes code to improve speed, memory usage, or another objective, without ever changing the program’s required observable behaviour — this constraint on preserving behaviour is absolute and non-negotiable. Examples include constant folding (computing 3×4 as 12 once, at compile time, rather than at every run), eliminating redundant computations (computing the same expression once and reusing the result when it is provably safe to do so), loop transformations, and peephole optimization (small, local pattern-based improvements to generated code). Optimization is always constrained by correctness, by acceptable compilation time, and by the specifics of the target architecture — an apparently “faster” transformation is simply invalid, no matter how clever, if it changes the program’s actual semantics under any input.
Compilers key takeaways: the compiler pipeline is a fixed sequence — lexical analysis, syntax analysis, semantic analysis, intermediate code, optimization, code generation — and each phase catches a genuinely different class of error. Regular expressions and finite automata formalize lexical recognition; context-free grammars and LL/LR parsing formalize syntax recognition. Semantic analysis catches errors that syntax alone cannot, most importantly type incompatibilities. Intermediate code lets much of a compiler’s work stay independent of the final target machine. Every optimization must preserve the program’s observable behaviour exactly — a transformation that changes correctness for the sake of speed is not a valid optimization at all, no matter how much faster it runs.