Compiler Principles: Basics and Practice | 编译原理基础与实践

📚 Compiler Principles: Basics and Practice | 编译原理基础与实践

Compilers are among the most fundamental pieces of software in computer science, translating high-level programming languages into machine-executable code. Understanding how compilers work is a core requirement in many A-Level Computer Science syllabuses, as it connects programming, hardware, and theoretical computation.

编译器是计算机科学中最基础的软件之一，它将高级编程语言翻译成机器可执行的代码。理解编译器的工作原理是许多 A-Level 计算机科学考纲中的核心要求，因为它将编程、硬件与理论计算紧密联系在一起。

---

1. What Is a Compiler? | 什么是编译器

A compiler is a program that translates source code written in a high-level programming language into an equivalent program in a lower-level language, typically machine code or assembly language. The key property of a compiled program is that the translation happens before execution, producing a standalone executable file.

编译器是一种程序，它将用高级编程语言编写的源代码翻译成等价的低级语言程序，通常是机器码或汇编语言。编译程序的关键特性在于：翻译发生在执行之前，并生成一个独立的可执行文件。

For example, when you write a C program and compile it with GCC, the resulting binary can be run directly by the operating system without needing the original source code or the compiler at runtime. This is fundamentally different from interpretation, which we will compare in a later section.

例如，当你用 GCC 编译一个 C 程序时，生成的目标文件可以直接被操作系统运行，而无需在运行时依赖源代码或编译器。这与解释执行有本质区别，我们将在后文详细比较。

• Source code: The human-readable program written in a high-level language.
• Target code: The machine-readable output, often stored as an executable file.
• Front end: The part of the compiler that analyses source code.
• Back end: The part that generates target code from the analysed source.

• 源代码：用高级语言编写的人类可读程序。
• 目标代码：机器可读的输出，通常存储为可执行文件。
• 前端：编译器负责分析源代码的部分。
• 后端：编译器根据分析结果生成目标代码的部分。

---

2. The Compilation Pipeline | 编译流水线

Modern compilers are organised as a sequence of phases, often called a pipeline. Each phase transforms the program representation step by step, from raw text to executable binary. A typical compiler has six major phases: lexical analysis, syntax analysis, semantic analysis, intermediate code generation, optimisation, and final code generation.

现代编译器被组织为一系列阶段，通常称为流水线。每个阶段逐步转换程序的表示形式，从原始文本到可执行二进制。一个典型编译器有六个主要阶段：词法分析、语法分析、语义分析、中间代码生成、优化和目标代码生成。

Source Text → Lexical Analysis → Syntax Analysis → Semantic Analysis → Intermediate Code → Optimisation → Target Code

源代码 → 词法分析 → 语法分析 → 语义分析 → 中间代码 → 优化 → 目标代码

In A-Level examinations, you are often asked to identify which phase handles a particular task or to trace how a small piece of code is processed. Understanding the boundary between each phase is critical for answering such questions accurately.

在 A-Level 考试中，你常被要求判断某个任务属于哪个阶段，或追踪一小段代码的处理过程。理解各阶段之间的边界是准确回答这类问题的关键。

---

3. Lexical Analysis | 词法分析

Lexical analysis (or scanning) is the first phase of compilation. It reads the raw source code as a stream of characters and groups these characters into meaningful tokens. A token is a classified unit of the language, such as a keyword, identifier, operator, or literal constant.

词法分析（又称扫描）是编译的第一个阶段。它将原始源代码作为字符流读取，并将这些字符分组为有意义的记号。记号是语言的一个分类单元，例如关键字、标识符、运算符或字面量常量。

Consider the assignment statement total = price + 10;. The lexer will produce the following tokens:

考虑赋值语句 total = price + 10;。词法分析器将产生以下记号：

Token Type | 记号类型	Lexeme | 词素
Identifier | 标识符	total
Assignment Operator | 赋值运算符	=
Identifier | 标识符	price
Addition Operator | 加法运算符	+
Integer Literal | 整数字面量	10
Semicolon | 分号	;

A lexical analyser also removes whitespace and comments, which are not needed for the rest of the compilation process. It does not check whether the order of tokens is grammatically valid—that is the task of the next phase.

词法分析器还会删除空白字符和注释，因为编译过程的其余阶段不需要它们。它不会检查记号的排列顺序是否符合语法——这是下一阶段的任务。

---

4. Syntax Analysis | 语法分析

Syntax analysis (or parsing) takes the stream of tokens from the lexer and builds a parse tree (also called a syntax tree) based on the grammatical rules of the programming language. These rules are typically expressed using a context-free grammar (CFG) or, more commonly in practice, a BNF (Backus-Naur Form) notation.

语法分析（又称解析）接收来自词法分析器的记号流，并根据编程语言的语法规则构建语法树（也叫解析树）。这些规则通常用上下文无关文法（CFG）表示，实践中最常用的是 BNF（巴科斯-瑙尔范式）记法。

For the statement total = price + 10;, a parser would construct a tree where the root is an assignment node, with the left child representing the identifier total and the right child representing the expression price + 10.

对于语句 total = price + 10;，解析器会构建一棵树，其中根节点是赋值节点，左孩子表示标识符 total，右孩子表示表达式 price + 10。

Assignment(=) → left: total, right: Addition(+) → left: price, right: 10

赋值(=) → 左: total, 右: 加法(+) → 左: price, 右: 10

If the token sequence does not conform to the grammar, the parser reports a syntax error. For example, the statement 10 + = price; would be rejected because the grammar does not allow an assignment operator to follow an addition operator.

如果记号序列不符合文法，解析器会报告语法错误。例如，语句 10 + = price; 将被拒绝，因为文法不允许赋值运算符紧跟在加法运算符之后。

At A-Level, you should be able to read a simple BNF grammar and use it to determine whether a given string is valid. You should also understand the concept of recursion in grammar definitions, such as in expressions like <expression> ::= <number> | <expression> + <number>.

在 A-Level 阶段，你应该能够阅读简单的 BNF 文法，并据此判断给定字符串是否合法。你还应理解语法定义中的递归概念，例如表达式规则：<expression> ::= <number> | <expression> + <number>。

---

5. Semantic Analysis | 语义分析

Semantic analysis checks the meaning of the program—whether it is logically consistent according to the language’s rules. While syntax checks form, semantics checks meaning. This phase uses the parse tree and a symbol table to verify type correctness, variable declaration, and scope rules.

语义分析检查程序的意义——即程序是否符合语言规则所要求的逻辑一致性。语法检查的是形式，而语义检查的是含义。此阶段使用语法树和符号表来验证类型正确性、变量声明以及作用域规则。

Common tasks performed during semantic analysis include:

语义分析阶段执行的常见任务包括：

• Type checking: Ensuring that operations are applied to compatible types, e.g. you cannot add an integer to a boolean in most languages.
• Declaration checking: Ensuring that every variable is declared before use.
• Scope resolution: Determining which declaration of a name refers to which use, especially with nested blocks.
• Type coercion: Inserting implicit conversions, e.g. converting an int to a float when needed.

• 类型检查：确保操作符用于兼容的数据类型，例如在大多数语言中，不能将布尔值直接与整数相加。
• 声明检查：确保每个变量在使用之前已经声明。
• 作用域解析：确定名称的每次使用对应哪个声明，尤其在嵌套代码块中。
• 类型强制转换：插入隐式类型转换，例如在需要时将 int 转为 float。

If semantic errors are found, such as assigning a string to an integer variable, the compiler aborts with an error message. These errors cannot be detected by the parser because they are not about grammatical structure—they are about meaning.

如果发现语义错误，例如将字符串赋值给整数变量，编译器会中止并报错。这些错误无法被解析器检测到，因为它们不是关于语法结构的，而是关于含义的。

---

6. Intermediate Code Generation | 中间代码生成

After semantic analysis, the compiler generates an intermediate representation (IR). This is a machine-independent code that lies between the high-level source and the low-level target code. A common form of IR is three-address code, where each instruction contains at most three operands.

语义分析之后，编译器生成中间表示（IR）。这是一种与机器无关的代码，介于高级源代码和低级目标代码之间。中间表示的一种常见形式是三地址码，每条指令最多包含三个操作数。

For the statement total = price + 10;, the three-address code would be:

对于语句 total = price + 10;，三地址码为：

t1 = price + 10
total = t1

The use of a temporary variable t1 makes the computation explicit and easier to optimise. Intermediate code also allows the compiler to be retargeted: the same IR can be translated to x86, ARM, RISC-V, or any other instruction set architecture.

使用临时变量 t1 使计算过程显式化，也更容易进行优化。中间代码还使得编译器具有可移植性：同一份 IR 可以被翻译成 x86、ARM、RISC-V 或任何其他指令集架构。

A-Level questions may ask you to write simple three-address code for a given expression, or to identify why intermediate code is beneficial. The two key benefits are (1) architecture independence and (2) enabling systematic optimisation.

A-Level 题目可能会要求你为给定表达式编写简单的三地址码，或说明中间代码的好处。两大好处是：(1) 架构无关性；(2) 便于进行系统化优化。

---

7. Optimisation | 代码优化

Optimisation is the phase where the intermediate code is improved to make the final executable faster, smaller, or more energy-efficient—without changing the program’s observable behaviour. Optimisation can occur at many levels, from reducing redundant calculations to reordering instructions for better CPU pipelining.

优化是改进中间代码的阶段，其目标是使最终可执行文件运行更快、体积更小或能耗更低——同时不改变程序的可观察行为。优化可以在多个层面进行，从消除冗余计算到为更好的 CPU 流水线而重排指令。

Common optimisation techniques include:

常见的优化技术包括：

• Constant folding: Evaluating constant expressions at compile time, e.g. replacing 3 × 4 with 12.
• Common subexpression elimination: Computing a repeated expression once and reusing the result.
• Dead code elimination: Removing code that is never executed or whose result is never used.
• Loop unrolling: Replicating loop bodies to reduce overhead and improve parallelism.

• 常量折叠：在编译时计算常量表达式，例如将 3 × 4 替换为 12。
• 公共子表达式消除：将重复出现的表达式只计算一次并复用结果。
• 死代码消除：删除从不执行的代码或结果从未被使用的代码。
• 循环展开：复制循环体以减少循环开销并提高并行度。

It is important to note that the compiler must preserve the semantics of the original program. An optimisation that changes the program’s output is incorrect, no matter how much faster it makes the code. This is called the correctness constraint.

必须注意：编译器必须保持原程序的语义。任何改变程序输出的优化无论让代码多快，都是错误的。这被称为正确性约束。

---

8. Code Generation | 目标代码生成

The final phase of compilation is code generation, where the optimised intermediate code is translated into the target machine’s assembly language or machine code. This phase also performs register allocation—deciding which variables should be held in CPU registers versus main memory.

编译的最后阶段是代码生成，将优化后的中间代码翻译为目标机器的汇编语言或机器码。此阶段还执行寄存器分配——决定哪些变量应保存在 CPU 寄存器中，哪些存放在主存中。

For total = price + 10;, a simplified assembly output on a load-store architecture might be:

对于 total = price + 10;，在一个加载-存储架构上，简化后的汇编输出可能是：

LDR R0, price
ADD R0, R0, #10
STR R0, total

LDR R0, price  加载 price 到寄存器 R0
ADD R0, R0, #10  R0 加 10
STR R0, total  将 R0 存回 total

The generated code must be linked with library routines before it becomes a fully executable program. Linking resolves references to external functions such as printf or malloc. Some compilers, such as GCC, invoke the linker automatically after compilation.

生成的代码必须先与库例程链接，才能成为完全可执行的程序。链接解决对外部函数的引用，例如 printf 或 malloc。某些编译器（如 GCC）会在编译后自动调用链接器。

---

9. Compiler vs Interpreter | 编译器与解释器

While compilers translate an entire program in advance, interpreters translate and execute source code line by line or statement by statement at runtime. Both approaches have advantages and disadvantages, and this comparison is a favourite exam question.

编译器预先翻译整个程序，而解释器则在运行时逐行或逐条语句地翻译并执行源代码。两种方式各有优缺点，这一对比是考试中的热门题目。

Criterion | 比较项	Compiler | 编译器	Interpreter | 解释器
Execution speed | 执行速度	Fast, because all translation is done upfront.	Slower, because translation occurs during execution.
Error detection | 错误检测	All errors reported at compile time.	Errors reported as each statement is executed.
Distribution | 分发	Executable is self-contained, source not required.	Source code must be present at runtime.
Debugging | 调试	More difficult; debuggers work on machine-level info.	Easier; often provides line-by-line feedback.
Examples | 示例	C, C++, Go, Rust	Python (CPython), JavaScript (older engines), Ruby

编译器：
执行速度 | 快，因为所有翻译提前完成。
错误检测 | 编译时一次性报告所有错误。
分发 | 可执行文件自包含，不需要源代码。
调试 | 较困难；调试器基于机器级信息。
示例 | C, C++, Go, Rust

解释器：
执行速度 | 慢，因为翻译发生在执行期间。
错误检测 | 每条语句执行时报告错误。
分发 | 运行时必须存在源代码。
调试 | 较容易；通常提供逐行反馈。
示例 | Python (CPython), JavaScript (旧引擎), Ruby

Many modern languages, such as Java, use a hybrid approach: source code is compiled to bytecode, which is then interpreted or JIT-compiled by a virtual machine. This combines portability with reasonable performance.

许多现代语言（如 Java）采用混合方案：源代码先被编译成字节码，再由虚拟机解释执行或即时编译（JIT）。这兼顾了可移植性与合理的性能。

---

10. Practical Applications and the Real-World Context | 实践应用与真实场景

Compiler technology is not confined to programming language compilers. The same front-end/back-end architecture is used in database query optimisers (SQL to execution plans), regular expression engines, and HTML parsers in web browsers. Understanding compilation gives you transferable skills for any software that processes structured text.

编译技术并不局限于编程语言编译器。相同的前端/后端架构也应用于数据库查询优化器（SQL 到执行计划）、正则表达式引擎，以及 Web 浏览器中的 HTML 解析器。理解编译原理为处理任何结构化文本的软件提供了可迁移的技能。

In the A-Level practical context, you may be asked to:

在 A-Level 实践环境中，你可能会被要求：

• Trace the tokenisation of a short code snippet by hand.
• Write a BNF grammar for a very small language, such as a valid date format.
• Convert a simple arithmetic expression into three-address code.
• Explain what happens when a compiler detects a syntax error versus a semantic error.
• Compare the trade-offs of compiled versus interpreted languages for a given scenario.

• 手工追踪一小段代码的词法分析（记号化）过程。
• 为一个极小的语言编写 BNF 文法，例如有效的日期格式。
• 将简单算术表达式转换为三地址码。
• 解释编译器检测到语法错误与语义错误时分别会发生什么。
• 针对给定场景比较编译型与解释型语言的利弊权衡。

When answering such questions, always use precise terminology. Write lexical analysis rather than just “scanning”, and describe the specific output, such as a token stream, parse tree, or symbol table. Examiners award marks for accurate vocabulary.

回答此类问题时，务必使用精确术语。写 词法分析 而不仅仅是”扫描”，并描述具体产物，如记号流、语法树或符号表。阅卷官会为准确的词汇打分。

---

11. Limitations and Common Misconceptions | 局限性与常见误区

A common misconception is that the parser detects all errors in a program. In fact, a program can be perfectly grammatical yet entirely meaningless, such as int x = “hello”; in C. This type of error is caught by semantic analysis, in the form of a type mismatch.

一个常见误区是认为解析器能检测出程序中的所有错误。事实上，一个程序可能语法完全正确却毫无意义，例如 C 语言中的 int x = “hello”;。这类错误由语义分析以类型不匹配的形式捕获。

Another misconception is that compilation and linking are the same thing. Compilation translates a single source file into an object file; linking combines multiple object files and libraries into a single executable. A large project with hundreds of source files will compile each file separately and link them in one final step.

另一个误区是认为编译与链接是同一回事。编译将单个源文件翻译为目标文件；链接将多个目标文件和库合并为单个可执行文件。一个包含数百个源文件的大型项目会分别编译每个文件，最后再统一链接。

Students also sometimes confuse the three-address code with actual assembly. Remember: three-address code is an abstract, machine-independent representation; assembly uses specific registers, memory addresses, and instructions of a target CPU. Only the final phase produces real assembly.

学生有时还会混淆三地址码与真实汇编。请记住：三地址码是抽象的、与机器无关的表示；汇编使用目标 CPU 的具体寄存器、内存地址和指令。只有最后阶段才产生真正的汇编代码。

Finally, keep in mind that optimisation never changes the meaning of the program. If an optimised program produces different results from the unoptimised version, that is a compiler bug, not a feature of optimisation.

最后，请记住：优化永远不会改变程序的含义。如果优化后的程序与未优化版本产生不同的结果，那是编译器缺陷，而不是优化的特性。

---

12. Exam Strategy and Summary | 考试策略与总结

To master compiler principles for your A-Level examination, build a mental map of the pipeline and connect each phase to its input and output. Here is a compact revision table you can reproduce in your notes:

为了在 A-Level 考试中掌握编译原理，请构建流水线的思维导图，并将每个阶段与其输入和输出联系起来。以下是一个紧凑的复习表，你可以抄录到笔记中：

Phase | 阶段	Input | 输入	Output | 输出
Lexical | 词法	Character stream | 字符流	Token stream | 记号流
Syntax | 语法	Token stream | 记号流	Parse tree | 语法树
Semantic | 语义	Parse tree + symbol table | 语法树 + 符号表	Annotated tree | 标注后的语法树
IR generation | 中间代码生成	Annotated tree | 标注后的语法树	Three-address code | 三地址码
Optimisation | 优化	Three-address code | 三地址码	Optimised IR | 优化后的 IR
Code generation | 目标代码生成	Optimised IR | 优化后的 IR	Assembly / machine code | 汇编 / 机器码

Beyond memorising the six phases, practise applying them to short example programs. Write a small piece of pseudo-code and ask yourself: which tokens will the lexer produce? What does the parse tree look like? Are there any semantic issues? What would the three-address code be? This active practice embeds the concepts far more deeply than passive reading.

除了记忆六个阶段，还要练习将它们应用于短小的示例程序。写一小段伪代码，然后问自己：词法分析器会产生哪些记号？语法树是什么形状？是否存在语义问题？三地址码是怎样的？这种主动练习比被动阅读更能将概念内化。

Compilers are the bridge between human thought and machine execution. Mastering their stages not only earns you marks but also gives you a profound appreciation of how every program you write is ultimately brought to life.

编译器是人类思维与机器执行之间的桥梁。掌握其各个阶段不仅为你赢得分数，更让你深刻体会到：你编写的每一个程序究竟是如何最终成为现实的。

---

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）