2026春《编译原理》笔记
- 第一章 引论
- 1.1 术语解释
- 1.2 编译程序的构成
- 1.3 解释程序
- 1.4 例题
- 尚未复习到的
- 第二章 文法和语言
- 2.1 符号和符号串
- 2.2 文法和语言的形式化定义
第一章 引论
1.1 术语解释
- 编译程序：编译程序是把一种（高级）语言编写的程序（称为源程序）翻译成等价的另一种（低级）语言程序（成为目标语言）的程序。
- 源程序：用户用高级语言书写的原始程序，即编译前输入给编译程序的程序。
- 目标程序：程序经过编译后得到的结果程序。
- 前端：由与源语言有关而与目标机器无关的部分组成，通常包括词法分析、语法分析、语义分析、中间代码生成、符号表的建立以及与机器无关的代码优化工作、相应的符号表管理和错误处理。
- 后端：由编译程序中与目标机器有关的部分组成。一般来讲这些部分与源语言无关而仅仅依赖于中间语言。后端包括目标代码生成、与机器有关的代码优化、相应的符号表管理和错误处理。
- 遍：对源程序或中间表示形式从头到尾扫描一次，并在扫描过程中作相关的加工处理，生成新的中间表示形式或目标程序。
1.2 编译程序的构成
- 词法分析程序。扫描字符串表示的源程序，根据词法规则识别出具有独立意义的单词符号，输出单词符号流。
- 语法分析程序。根据语法规则，把单词符号流分解成语法短语，可表示成语法树。
- 语义分析程序。对语法成分的类型、含义进行检查，以保证程序各部分能有机地结合在一起，并为以后生成目标代码收集必要的信息，如类型、目标地址等。
- 中间代码生成程序。将源程序转换为一种结构简单、含义明确的中间表示形式，以便进一步转换为目标代码。
- 代码优化程序。对中间代码进行改进以获得高效的代码，占用空间少、运行速度快。
- 目标代码生成程序。将中间代码转换成特定机器上的目标代码。
- 符号表管理程序。编译过程中的各种信息被保留在不同符号表里，编译各阶段都涉及符号表的构造、查找和更新。
- 出错处理程序。报告编译各阶段发生的错误性质和发生错误的语句，并将错误造成的影响限制在尽可能小的范围内，使编译程序能继续处理源程序的余下部分。
1.3 解释程序
解释程序是解释、执行高级语言源程序的程序。
与编译程序的不同：
- 编译程序把源程序翻译成等价的目标程序（只翻译，不执行），此后目标程序的运行不再依赖于编译程序。
- 解释程序则边翻译（解释）边执行，不产生目标代码，直接输出源程序的运行结果。源程序的每一次运行都离不开解释程序。
1.4 例题
分析以下错误信息，指出是哪个编译阶段报告的？
- else没有匹配的if。【语法分析】
- 数组下标越界。【语义分析/运行期】
- 使用的函数未定义。【语法分析】
- 在数字中出现非数字字符。【词法分析】
尚未复习到的
编译工具链；PL/0语言。
第二章 文法和语言
语言（语法、语句、语义）的相关概念，文法-语法-语句的关系。巴科斯范式（BNF，Backus–Naur Form）。
文法（Grammar）： 描述语言的语法结构的形式规则。
2.1 符号和符号串
字母表：元素的非空有穷集合，其元素称为符号，因此也成为符号表，一般记作\(∑\)。
符号串：由字母表中的符号组成的任何有穷序列称为（该字母表上的）符号串。特别地，不含任何符号的有穷序列称为空串，记为\(ε\)。单词和源程序都是符号串。
- 符号串的有关运算：符号串的长度、头、尾、固有头、固有尾、或（|或者+，PPT中采用前者）、连接、方幂、集合、闭包（字母表上所有有穷长的串的集合）、正闭包。符号串集合的和（并）、乘积（交）、方幂、闭包。
2.2 文法和语言的形式化定义
文法：文法 \(G\) 定义为一个四元组 \((V_N，V_T，P，S)\)，记为 \(G ＝ (V_N，V_T，P，S)\)。其中，
- \(V_N\) 是非空有穷集合，称为非终结符集，其元素称为非终结符；
- \(V_T\) 是有穷集合，称为终结符集，其元素称为终结符；
- \(P\) 是非空有穷集合，称为规则集，其元素是字母表 \(V_N∪V_T\) 上的规则，\(V_N∪V_T\) 称为文法的字母表 \(V\)，且 \(V_N ∩V_T = Φ\)；
- \(S ∈ V_N\)，称为开始符。
例如，定义文法 \(G ＝(V_N，V_T，P，S)\)，其中
\(V_N = \{S\}\), \(V_T = \{a, b\}\), \(P = \{S → aSb， S → ab\}\), \(S = S\)。
推导与规约：直接（一步）推导/规约，间接（多步）推导/规约，0步或0步以上推导与归约。
句型：设文法 \(G ＝(V_N，V_T，P，S)\), 对于 \(β ∈ V* = (V_N∪V_T)*\) ，如果 \(S\) 能够经过0步或0步以上推导出 \(β\)，则称 \(β\) 是文法 \(G\) 的句型。
Note: β 可以在 G 中推导出来！
句子：如果 \(β\) 是 \(G\) 的句型，且 \(β ∈ (V_T)*\)，则称 \(β\) 是 \(G\) 的句子。
语言：文法 \(G ＝(V_N，V_T，P，S)\) 能够产生的所有句子的集合称为 \(G\) 的语言，记为 \(L(G) = \{β︱S 经过0步或0步以上推导出 β，β ∈ V_T*\}\)。
对于两个文法 \(G_1\), \(G_2\)，如果 \(L(G_1) = L(G_2)\)，则称文法 \(G_1\) 和 \(G_2\) 是等价的。
文法设计。递归思想。