【期末速成】编译原理
第一章
编译程序和解释程序的区别
编译程序和解释程序的区别：编译程序产生目标代码（比如 C++ 产生 .exe 文件），解释程序不产生目标代码，比如 js 的 JIT 。
编译过程
第二章
上下文无关文法
推导、句型、句子、语言
推导是从文法的开始符号出发，按照产生式一步步替换，直到生成终结符串的过程。最左推导：每次都替换最左边的非终结符。
从开始符号出发，经过零次或多次推导所得到的、包含终结符和/或非终结符的符号串，叫做句型。句型可以是中间过程，不一定是最终的全终结符串。
如果一个句型中只包含终结符（即没有非终结符了），那么这个句型称为一个“句子”。
一个文法所能生成的所有句子的集合，称为这个文法的语言。
最左推导和最右推导
文法
产生式 → 推导语言（给出文法产生式，求语言）
✅【题型示例 1】
已知文法 G：
S → aS | b
问：该文法产生的语言是什么？
✅【解析思路】
分析每个推导路径：
S → aS → aaS → aaaS → … → aaab
即：任意多个a开头，最后以b结尾。
✅【答案】
该文法生成的语言为：
L = { aⁿb | n ≥ 0 }
即：任意个 a 后跟一个 b
✅【题型示例 2】
已知文法：
S → aSa | bSb | ε
问：该文法描述的语言是？
✅【解析思路】
- 这个文法是递归对称的，从两边同时加入
a和a，或b和b。 - ε 为中间终止。
✅【答案】
这是一个回文语言：
L = { w ∈ {a, b}* | w 是回文串 }
语言 → 构造文法产生式（反推文法）
✅【题型示例 3】
已知语言：
L = { aⁿbⁿ | n ≥ 1 }
问：构造文法 G，使 G 能生成 L。
✅【思路】
这个语言包含匹配数量的 a 和 b，可用递归文法表示。
✅【答案】
S → aSb | ab
推导示例：
- S → ab
- S → aSb → aab b
- S → a aSb b → aaabbb
✅【题型示例 4】
语言：
L = { w ∈ {a, b}* | 每个 a 后面都跟着 b }
✅【构造思路】
我们需要生成满足规则：所有 a 后都必须被 b 跟随。
可以通过：
S → bS | a b S | ε
推导例：
- ε
- ab
- abb
- ababb
✅【题型示例 5】
语言：所有由偶数个 a 和偶数个 b 组成的字符串。
文法二义性
如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法中存在某个句子，它有两个不同的最左（最右）推导，则这个文法是二义的。
文法的二义性和语言的二义性是两个不同的概念。
文法分类（形式语言体系）
文法的分类：
- 0 型文法：无限制（左边至少一个大写字母）
- 1 型文法：上下文有关（右边长度大于等于左边长度）
- 2 型文法：上下文无关（左边只能有一个大写字母）
- 3 型文法：正规文法（又分为左右线性）DFA、NFA
一个文法形成的语言是唯一的。
单词符号的五种分类
举例为：const a = 1;
语法分析树
给定文法 G：
E → E + T | T
T → T * F | F
F → (E) | id
输入串：id + id * id
- 最左推导过程（Leftmost Derivation）：
E ⇒ E + T⇒ T + T⇒ F + T⇒ id + T⇒ id + T * F⇒ id + F * F⇒ id + id * id
- 对应语法分析树：
E/ | \E + T| / | \T T * F| | |F F id| |id id
第三章
状态转换图
DFA、NFA
正规式 => NFA：
NFA => DFA （子集法），以及 DFA 的最小化：
正规文法 -> 正规式
第四章
LL(1)分析条件
消除左递归：
如果出现没有左递归的情况，直接不用修改原封不动照抄一遍即可。
预测分析表的构造
first 集 和 follow 集
预测分析表构造
现根据 first 构造：
然后根据 follow 构造：
递归下降分析程序构造
不考。
第五章
规范规约
- 素短语 = 不能再分的小短语（最小单位） = 由非终结符推导出来的、不可再拆的连续子串.
- 句柄：最左直接短语
- 直接短语：一个父节点只有一个子节点，且是叶子节点
- 短语：所有子树的叶子短语集合
算符优先表
- firstR，Qab里面的 a也算进去，然后 Q-cR | a 里面的 c和 a 也要算进去，然后因为 a 重复，所以只取一个。
- Q 的 lastvt 是 a 和 b，因为 倒数第一个终结符，一个是 a，还有一个是R，但是 R是非终结符，所有看 Qab ，最后一个是 b，所以 a，b；然后加上 cR 中的 c，一共是 c a b
第六章
翻译模式翻译句子
这道题技巧可以先看到具有三个 / ，而 / 只有 R-R/S 可以推出，所以先把三个 / 推出，其他的就比较轻松了。
第七章
表达式翻译为中间代码
- 三地址代码（四元式）
- 三元式
- 间接三元式
- 后缀式（逆波兰表达式）
- 抽象语法树（AST）
将下面这个表达式：
x = (a + b) * (c - d) + e
翻译为以下形式：
- 三地址代码（四元式）
- 三元式
- 间接三元式
- 后缀式
- 抽象语法树（AST）
1️⃣ 三地址代码（四元式）
我们先进行中间变量拆分：
t1 = a + b
t2 = c - d
t3 = t1 * t2
t4 = t3 + e
x = t4
| 编号 | 运算 | 参数1 | 参数2 | 结果 |
|---|---|---|---|---|
| (1) | + | a | b | t1 |
| (2) | - | c | d | t2 |
| (3) | * | t1 | t2 | t3 |
| (4) | + | t3 | e | t4 |
| (5) | := | t4 | - | x |
2️⃣ 三元式（编号表示中间结果）
| 编号 | 运算 | 参数1 | 参数2 |
|---|---|---|---|
| (0) | + | a | b |
| (1) | - | c | d |
| (2) | * | (0) | (1) |
| (3) | + | (2) | e |
| (4) | := | (3) | x |
3️⃣ 间接三元式
将三元式存储在数组中，通过地址引用执行：
地址表：
0: + a b
1: - c d
2: * 0 1
3: + 2 e
4: := 3 x
主程序中只保留地址列表 [0, 1, 2, 3, 4] 表示执行顺序。
4️⃣ 后缀式（逆波兰式）
后缀表达式的顺序为：
a b + c d - * e + x =
或写成两个阶段：
表达式部分：a b + c d - * e +
赋值部分：x =
5️⃣ 抽象语法树（AST）
=/ \x +/ \* e/ \+ -/ \ / \a b c d