【期末复习】编译原理

1. 语法描述

1.1. 上下文无关文法

1.2. 句子 & 句型 & 语言

1. 1. 推导出来的都是句型
   2. 但是如果句型中只含有终结符，那就是句子
   3. 所有的句子合起来，才是语言

1.3. 文法

文法就是推导的式子。

1.4. 文法二义性

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

1.6. 语言二义性

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

1.7. 二义性的性质

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

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

1.9. 文法的类型

2. 词法分析

2.1. DFA

S0 只能是一个（元素）

F 可以有很多（集合）

2.2. NFA

2.3. DFA 和 NFA 区别

2.4. NFA 转换为 DFA

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

2.4.2. 构造状态转换矩阵

2.4.3. 转换为数字

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

2.4.4. 化简

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

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

3.1. 消除左递归

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

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

3.2.1. 步骤

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

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

3.3.1. 步骤

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

3.3.2. 例题

3.4. 分析表构建

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

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

3.5. LL(1)的意义

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

4.1. 概念

4.1.1. 短语

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

4.1.2. 直接短语

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

4.1.3. 句柄

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

4.1.4. 素短语

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

4.1.5. 最左素短语

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

4.1.6. 例子

4.2. 规范规约&最右推导

4.3. 算符优先级规则

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

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

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

4.4. LR 分析

4.4.1. LR 分析器

4.4.2. LR(0)分析器

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

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

4.4.4. ACTION 和 GOTO 表构造造

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

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

4.5. LR(1)分析表

4.5.1. 构造

另一个例子