1. 编译程序流程

1.1. c 语言编译流程

1.2. 编译器编译流程

2. 语法描述

2.1. 上下文无关文法

2.2. 句子 & 句型 & 语言

1. 1. 推导出来的都是句型
   2. 但是如果句型中只含有终结符，那就是句子
   3. 所有的句子合起来，才是语言
   4. 语言就是一种集合，是这个文法能够表示出来的所有的句子的集合，形式如下：

2.3. 文法

文法就是推导的式子。

2.3.1. 文法化简

2.4. 判断是否为正则文法

2.5. 文法二义性

2.6. 二义性消除

【武汉大学】编译原理混子速成—面向期末试卷复习4: 消除文法二义性总结_哔哩哔哩_bilibili

2.7. 文法二义性证明——根据最左 \ 最右推导有两种

一个结果，两个树。

2.8. 语言二义性

如果文法没有二义性，也可能使得语言是二义性的。

2.9. 二义性的性质

二义性文法可以转化为无二义性的文法。

2.10. 上下文无关文法的限制

2.11. 文法的类型

3. 词法分析

3.1. DFA

S0 只能是一个（元素）

F 可以有很多（集合）

3.2. NFA

3.3. DFA 和 NFA 区别

3.4. NFA 转换为 DFA（NFA 的确定化）

3.4.1. 先对 NFA 转换，用以下规则

3.4.2. 构造状态转换矩阵

3.4.3. 转换为数字

I 这一列从上到下依次排序，然后对应转换后两列的值。

3.4.4. 化简

3.5. 正规式和正规集的转换

4. 语法分析——自上而下

自上而下必须要满足三点：

1. 1. 消除左递归
   2. 消除回溯(即提取公共左因子)
   3. 对于文法中，只要有 A->a|b，那么就需要判断：

1. 1. 1. 如果 a 或者 b 中有空字，那就判断另一个的 FIRST 和左边的非终结符的 FOLLOW
      2. 如果 a 和 b 中都没有空字，那就判断 FIRST(a)和 FIRST(b)

这两种的交集都得是空集才是 ll(1)。

4.1. 消除左递归

1. 竖线后面的写前来，后面跟一个 A'
2. 递归后面剩下的写前来，后面跟一个 A'，加竖线和空串

4.2. 构造非终结符的 FIRST 集合

4.2.1. 步骤

1. 找出所有的非终结符，遍历所有的文法，直到规则不发生变化为止
2. 如果是符号，就将其加入到 FIRST（左边的非终结符）
3. 如果不是符号，就将“->”右边的非终结符的 FIRST 有的元素（除了空字），加入到左边的非终结符的 FIRST 集合中

first 看的是所有的产生式。

4.3. 构造非终结符的 FOLLOW 集合

4.3.1. 步骤

后面如果是一个非终结符，最终能够推出来的是‘空’，那么就是第三种情况。

4.3.2. 例题

1.

2.

构造 FOLLOW(E) 的时候，因为 E 在右边只有第七个式子出现了，它后面是“)”，所以加”)“。(遵循的是最“朴素”的方法)

又因为他是开始符，所以将“#”也放进去。

如果加入的 FIRST 集合里面有空，那就需要将这个也考虑进去，就是符合第三点了，要将其 FOLLOW(左边) 除去空加进去。

4.4. 分析表构建

是根据 FIRST 和 FOLLOW 集进行构造。

1. 如果 FIRST 中没有空，直接在 FIRST 里的元素上写上产生式
2. 如果 FIRST 中有空，除了要在非空元素上写上产生式，还要在 FOLLOW 集里的元素写上产生空的产生式

4.5. LL(1)的意义

4.6. 证明不是 LL(1)文法

4.6.1. 左递归

4.6.2. 回溯

4.6.3. first 和 follow 的冲突

FIRST(右边) 交 FOLLOW(左边) 如果不是空集，不是 LL(1)。

5. 语法分析——自下而上

5.1. 概念

5.1.1. 短语

• 短语：任意一颗子树中，如果根结点经过若干步才推导出了叶子结点，则这些叶子结点组成的序列就是相对于这棵子树的短语

5.1.2. 直接短语

• 直接短语：属于短语，只不过不能经过若干步的推导了，必须一步就能推导出来叶子结点来，这些叶子结点组成的序列才是相对于这颗子树的直接短语

就是叶子和其父节点只能有一层。

5.1.3. 句柄

直接短语中的最左直接短语为该句型的句柄

也就是语法树中，最左最小树上的叶子。

5.1.4. 素短语

素短语，是指至少含有一个终结符的短语，并且除自身外，不包含更小的素短语。

5.1.5. 最左素短语

最左素短语是句型中最左边的素短语。

5.1.6. 例子

5.2. 提取公共左因子的方法 （消除回溯）

5.3. 规范推导&最右推导、规范规约&最左规约

1. 1. 推导是从开始符号，根据产生式，生成句子。（自顶向下）
   2. 规约是从句子，根据产生式，生成开始符号。（自底向上）
   3. 推导的规范是最右
   4. 规约的规范是最左（就是说标准是从左边开始进行规约）

5.4. 算符优先级规则

1. 后出现的优先级高。
2. 两条原则：

1. 1. 设终结符 a 在非终结符 A 的前面，那么 a <· 所有 A 的 firstVT
   2. 设非终结符 A 在终结符 a 的前面，那么 A 的 lastVT ·> a

VT 就是 VT 就是终结符的意思。

5.5. FIRSTVT 规则

5.6. LastVT 规则

5.7. 总结这两个规则

5.8. 算符优先文法

就是说，#S#：

#<FIRSTVT(S)

LASTVT(S)>#

也就是， 给 S 加上一对尖括号：#<S>#

5.9. LR(0) 文法

5.9.1. 概念

5.9.1.1. 字的前缀

5.9.1.2. 活前缀

5.9.1.3. 项目

5.9.1.4. 项目集

5.9.1.5. 项目集I的闭包CLOSURE(I)

5.9.1.6. 项目集规范族

如果推导了之后，·在非终结符之前，那么需要将这个非终结符的所有产生式写在下方。

5.9.2. 拓广文法

E`->E是固定必须写的，剩余就拆开。

5.9.3. LR(0)分析表的构造

拓广文法如果没有 S'，那么就需要写上 S'->S。

5.9.4. 构造LR(0) 项目集规范族，并画DFA

另一个题（题目要求画 LR(0)，但是不是 LR(0)文法）：

还有一个题：

5.9.5. 判断是否是 LR(0)

5.9.6. ACTION 和 GOTO 表构造

1. action 就是 VT，goto 就是 VN。
2. ACTION 写的是 rj 或者 sj， GOTO 写的是序号（表示下一步到达哪个状态）。

1. 1. 初始的项目集规范族 在哪，acc 就在哪
   2. 其余的包含有规约项目的，都填 rj
   3. 其余的普通的，都填 sj

1. 在 S 中，这个 j 需要写的是拓广文法里面的序号，而不是 I（方框里的）编号；r 反过来
2. acc 应该写在拓广文法里 0 号式子在 I 里面的编号是几，和#交界处。

这个题就是 I1 和#交界处。

5.9.7. 总

5.9.7.1. 第一题：

5.9.7.2. 第二题

5.10. SLR(1) 文法

和 LR(0)不同之处，就是填结束状态 Rj 的时候：

1. 1. LR(0)全部都写上 Rj
   2. 但是 SLR 只在 FOLLOW 集里的，才写 Rj

eg:

5.10.1. 第一题（非 SLR 文法的例子）

归根到底是：FOLLOW(R) 交 {=} = {=}所以不是 SLR(1)文法。

5.10.2. 第二题

判断是否为 SLR(1)文法：

就是用

这种情况下的状态，看：{终结符}交 FOLLOW{开始符}=空集吗？

1. 1. 如果是空集，LR(0) 文法就是 SLR(1)文法
   2. 反之不是
   3. 终结符是看规约项目的终结符，开始符是看移进项目的开始符。

5.10.3. 判断是否是 SLR 文法

LR(0) 文法能力弱，有互相冲突

5.11. LR(1)文法

5.11.1. LR(1)项目集族

5.11.1.1. 带向前搜索符的项目集规范族：写出，后面的 b？

方法：

eg1:

eg2:

一个例子：

另 一个例子：

5.11.2. 构造项目集族 1

与 LR(0) 不同的是，LR(1) 的 I0 不是将所有式子前都加上 ·，而是：

1. 1. 1. 将第一个式子加上点
      2. 看这个点后面的非终结符能够推出来的产生式
      3. 将这些写在最开始的方框

         

      4. 再一个，这些方框也不写 I，只写数字

5.11.3. 构造项目集族 2

注意：

1. 1. ·后面的如果是非终结符，那还需要进行再一次的

   2. 

5.11.4. 分析输入串的过程

5.11.5. 总（构造 LR(1)分析表）

5.11.5.1. 第一题

如果没有到末尾，那就看当前推导的符号，属于哪个表：

1. 1. 如果推导的符号是 GOTO 表中的的，那就在 GOTO 里面写数字
   2. 如果推导的符号是 ACTION 表中的，那就在 ACTION 里面写上 s 或者 r（根据完成与否选择写哪个）

eg1：

I11 的时候：

1. 1. 1. 推导 L 和 R 到达的状态都是 GOTO 表中的，那就在 GOTO 的 L 和 R 上写上数字 10 和 13
      2. 推导*和 i 到达的状态都是 ACTION 表中的，那就在 ACTION 表中的 ＊和 i 写上 S11 和 S12（）

I2 的时候：

1. 1. 1. 推导的是 =，到达的状态是 I6 ，所以在 ACTION 的=中写上 S6
      2. I2 里面自己已经有一个完成的式子：R->L·,#，所以需要在 拓广文法 中找 R->L的编号，找到是 6，所以在 2 状态的#上，写上 S6 。

eg2：

I8 的时候：

自己的方框中，·已经到末尾了，所以需要在=和#的 ACION 里写上 r6。（下标是 6 的原因是托广文法R->L的编号是 6）

5.11.5.2. 第二题

5.11.6. LR(1)分析输入串

是根据当前符号栈的栈顶元素和输入串的第一个元素，对应到分析表找：

1. 1. 如果是 Sx ，那就将 x写到状态栈，进行移进
   2. 如果是 Rx，那就对应着找拓广文法的 x编号的产生式，进行规约

5.12. LALR(1)文法

5.12.1. 流程

5.12.2. LALR(1) 可能的冲突

6. 区分LR(0),SLR(1),LR(1),LALR(1)文法

6.1. 项目的划分（判断冲突要用）

6.2. 为什么要拓广文法

因为在规约 b 和 c 的时候，不知道是规约上面的 S 还是下面的 S，所以添加了一条：S`->S。

6.3. LR(0)文法

6.4. SLR(1)文法

6.5. LR(0) 和 SLR(1)的联系

1. LR(0) 包含于 SLR(1)。
2. 判断方法：

1. 1. 如果没有冲突，那就是 LR(0) 文法
   2. 如果有冲突，

1. 1. 1. 能解决，那就是 SLR(1)文法
      2. 不能解决，两个都不是

6.6. LR(1)文法

与 SLR(1) 不同的是项目集规范族是带向前搜索符的。

向前搜索符就是：,______ 这种形式的。

6.7. LALR(1)文法

6.8. LR(1)文法 和LALR(1)文法的联系

LR(1)文法 包含于 LALR(1)文法。

6.9. 各文法之间的联系

6.10. 例题

6.11. 判断是哪类 LR 文法

6.11.1. 判断是否是 LR(0) ：

6.11.2. 判断是否是 SLR(1) ：

移进项目·后面的终结符 和 规约项目的开始符：{=} 交 FOLLOW(R) =空集

如果为空，能解决冲突

如果不为空，不能解决冲突

6.11.3. 判断是否是 LR(1)

LR(1) 的冲突是看：

移进项目·后面的终结符 和 规约项目的向前搜索符的交集是否为空。

为空，是 LR(1)

不为空，不是 LR(1)

6.12. LR 文法的图的差异

1. LR(1)

rj 状态出现多次的。

1. LR(0)

r 状态填满了一整行。

1. SLR(1)

rj 状态只出现一次的。

6.13. 直接根据项目集判断

6.14. 判断是否是 LALR(1)文法

6.15. 移进-规约 & 规约-规约的判定

1. 移进-规约：

1. 1. 在一个状态里，同时存在移进项目和规约项目

1. 规约-规约：

1. 1. 在一个状态里，同时存在两个规约的式子（不知道用哪个式子规约）

7. 语义分析

7.1. 写四元式和汇编指令以及书写后缀表达式（逆波兰式）

7.1.1. 四元式

7.2. 三元式

7.2.1. 间接三元式

7.3. 符号说明

JNZ：Jump Not Zero 非零跳转

7.4. 三元式翻译数组

7.5. 布尔表达式翻译

真出口的地址是 108，假出口的地址是 q。

7.6. 循环优化和局部优化

7.6.1. 局部优化

1. 合并已知量：

1. 删除公共子表达式：

1. 无用赋值

1. 冗余运算

T3 和 T4 做了无用的计算，应该直接使用 T1 和 T2 进行计算。

7.6.2. 循环优化

• 归纳变量（Induction Variable） 是指一个变量在循环中以某种固定的模式（如线性变化）进行更新。

• • 例如：i = i + 1 或 j = j - 2。

• 这些变量的值通常是循环迭代次数的函数。

7.6.2.1. 示例：

for (int i = 0; i < n; i++) {
    int j = 2 * i;  // j 是 i 的线性归纳变量
    ...
    }

• 变量 j 的值完全由变量 i 决定（j = 2 * i）。

8. 总结几种文法

在编译原理中，LL(1) 文法是语法分析中的一种文法类型，用于描述适合自顶向下分析的上下文无关文法。

其中 LL(1) 的 LL 含义为：

1. 第一个 L：从左到右扫描输入串（Left-to-right）。
2. 第二个 L：构造最左推导（Leftmost derivation）。
3. (1)：指向前看一个符号（Lookahead 1 symbol）来确定语法分析动作。

8.1.1. 详细说明：

• 左到右扫描：指的是分析器从输入的字符串第一个字符开始，依次从左到右逐个读取符号。
• 最左推导：在语法分析中，分析器基于文法规则从起始符号开始，通过替换非终结符生成输入字符串，每次选择替换非终结符时总是按照从左到右的顺序进行。
• 向前看一个符号：分析器在分析时，只需要根据当前符号和接下来的一个输入符号（Lookahead符号）来决定如何进行推导。

因此，LL(1) 文法的限制使其能够被高效地用于构建自顶向下的预测分析器，且无需回溯。

在编译原理中，LR(1)、LR(0)、SLR(1) 和 LALR(1) 是描述适合自底向上语法分析的文法类型。它们各自的含义如下：

---

8.1.2. 1. LR(1) 文法

• L: 从左到右扫描输入串（Left-to-right）。
• R: 构造最右推导的逆过程（Rightmost derivation in reverse）。
• (1): 向前看一个符号（Lookahead 1 symbol）来决定如何进行归约。

8.1.2.1. 特点：

• LR(1) 分析器可以通过状态和一个向前看符号来唯一确定下一步的分析动作。
• 是最强的自底向上文法，能够处理所有的 SLR 和 LALR 文法，但相应的状态集可能非常庞大。

---

8.1.3. 2. LR(0) 文法

• 和 LR(1) 类似，但 (0) 表示没有向前看符号（Lookahead 0 symbol）。
• 分析器的决定仅依赖于当前的状态和栈内容，而不考虑后续输入。

8.1.3.1. 特点：

• 限制性更强，只能解析简单的文法。
• LR(0) 项目集构造时仅根据项目中的点位置（不需要考虑向前看符号）。

---

8.1.4. 3. SLR(1) 文法

• SLR: 简化 LR（Simple LR）。
• 基于 LR(0) 项目集的基础上，将 向前看符号 的使用限制为 FOLLOW 集。

8.1.4.1. 特点：

• 相比 LR(1)，SLR(1) 的状态集合更小，因此更高效。
• 只能解析某些 LR(1) 文法，某些复杂文法可能无法解析。

---

8.1.5. 4. LALR(1) 文法

• LALR: Look-Ahead LR。
• 是 LR(1) 文法的简化版本，合并了具有相同核心的 LR(1) 状态，从而减少了状态数量。
• 向前看符号仅限于合并状态后的一个集合。

8.1.5.1. 特点：

• 在实践中被广泛使用（如 YACC 工具生成的解析器）。
• 和 LR(1) 的解析能力相同，但状态集比 LR(1) 小，接近 SLR(1) 的规模。

---

8.1.6. 总结对比

文法类型	向前看符号	状态数量	分析能力
LR(0)	无	最少	最弱（只能解析简单文法）
SLR(1)	FOLLOW 集	较少	中等
LALR(1)	合并后状态	较少	和 LR(1) 一样
LR(1)	具体符号	最多	最强

通常，LALR(1) 在实际编译器构造中最常用，因为它在解析能力和效率之间提供了良好的平衡。

8.1.6.1. 画 DFA（均已 LR(0) 为规范进行比较）

8.1.6.1.1. LR(0)

1. I0 是按照闭包进行画的，所有项目前加上点
2. 按照点后面的符号，依次进行推导，推导一次后，需要将点后移，后移遇到的符号有两种情况：

1. 1. 如果是非终结符，就需要再从拓广文法中找到这个非终结符开始的产生式，加上点，框到一起
   2. 如果是非终结符，不用管

1. 直至推导为规约项目

8.1.6.1.2. SLR(1)

1. 步骤和 LR(0)相同
2. 但是填 S 的时候，只给 FOLLOW 集的填。

8.1.6.1.3. LR(1)

1. 需要在 I0 后面加上向前搜索符
2. 其余步骤和 LR(0) 相同
3. 规约项目是 ·在逗号前，即为规约项目

8.1.6.1.4. LALR(1)

1. 需要在 I0 后面加上向前搜索符
2. 其余步骤和 LR(0) 相同
3. 化简的时候：

1. 1. 合并同心集（表达式相同，只有向前搜索符不同）

8.1.6.2. 画分析表

8.1.6.2.1. LR(0)

1. 未完成的项目就写 S。
2. 完成的项目就写 R，下标是拓广文法中的编号。

8.1.6.2.2. SLR(1)

1. 和 LR(0) 相同

1. 1. 但不是一整行都写，是在非终结符的 FOLLOW 集写。

8.1.6.2.3. LR(1)

1. 未完成的项目就写 S。
2. 完成的项目就写 R，下标是拓广文法中的编号。

1. 1. 完成的项目是指 ·在逗号之前。
   2. 不是在 FOLLOW 集写，是在 ,后面的向前搜索符里写。

8.1.6.2.4. LALR(1)

1. 和 LR(0) 相同

1. 1. 同心集分析的时候，只需要分析其中的一个