【期末速成】编译原理

第一章

编译程序和解释程序的区别

编译程序和解释程序的区别：编译程序产生目标代码（比如 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

1. 最左推导过程（Leftmost Derivation）：

  E ⇒ E + T
	⇒ T + T
	⇒ F + T
	⇒ id + T
	⇒ id + T * F
	⇒ id + F * F
	⇒ id + id * id

2. 对应语法分析树：

             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

翻译为以下形式：

1. 三地址代码（四元式）
2. 三元式
3. 间接三元式
4. 后缀式
5. 抽象语法树（AST）

1️⃣ 三地址代码（四元式）

我们先进行中间变量拆分：

t1 = a + b
t2 = c - d
t3 = t1 * t2
t4 = t3 + e
x  = t4

2️⃣ 三元式（编号表示中间结果）

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