编译原理学习笔记

不讲不考察的内容

参考：编译原理 - 学习笔记 - Zhang T’s Blog

1.5 编译程序的生成
第七章作用域
第八章

日常课堂笔记

非确定集与确定集的分辨

一个状态（字符集合）在接收到同样的字符串时，会转变到不同的状态（集合），导致了它的非确定性。

NFA 转换为 DFA

所谓的状态闭包是指，从当前节点，经过 ε 符（无条件转移）能到达的所有节点的集合，包括当前节点自己。

分解

A -> 1 -> B 指 B 从 A 接收 1

self 0 指该节点有一个指向自己的、以接收到的字符为 0 为条件的无限循环

1/0 指该节点有两条指向下一节点的、分别以 0 和 1 为条件的状态转移

ε 不代表什么都接收，而是无条件转移的意思

A -> 1(0|1)*(1|0) -> B

A -> 1 -> C -> E(self 0/1) -> D -> 1/0 -> B
A -> 1*(0|1)0* -> B

A -> C(self 1) -> C -> 0/1 -> D -> E(self 0) -> B

状态转移矩阵

第一行 I 是起始点的状态闭包，在求第一行 Ia 的时候，除了要列出可以从 I 中某个元素接收 a 的节点，还要在全部列出后补充 Ia 这些节点的状态闭包，即可以从 Ia 某个节点通过 ε 前往的节点。

然后，新的集合添加到下一行，进行重复的步骤。

最后，为每一行从头到尾添加节点编号，进行化简。

DFA 化简

将终止态和非终止态分开

用非终止态开始一个一个字符开始测试

测试完得到一些划分

两个字符到同一个状态集合就算等价，不一定只能是到一个状态

例如，{3,4,5,6} 中的 3,4,5 接收 a 不到达同一个状态，那就也不是同一个功能，需要分开。

LR(0)

编译原理学习笔记（七）~LR (0) 分析_海轰 Pro 的博客 - CSDN 博客

LR(1)

在 LR (0) 的基础后面加 #,{c,d} 等

LL(1)

期中考试复习课

流程

词法分析包括：标识符、常数、字符串、关键字、界符

中间代码、优化器会出简答题

出错处理：词法分析中关键词与标识符冲突、界符写错（没有大括号），打印 / 显示出来

表格管理：不断地在每个步骤生成结果，保存到表格中

一个典型的编译器通常由以下几个模块组成，每个模块都有不同的功能和任务：

词法分析器：也称为扫描器（Scanner），它是编译器的第一个模块，负责将源代码中的字符序列转换为有意义的单词（Token）序列，并为每个 Token 分配一个 Token 种类（Token Type）。
语法分析器：也称为解析器（Parser），它是编译器的第二个模块，负责将 Token 序列转换为抽象语法树（AST）或语法分析树，以及对语法错误进行检测和报告。
语义分析器：它是编译器的第三个模块，负责对 AST 进行类型检查、语义检查、符号表管理等操作，以及生成中间代码或目标代码。
中间代码生成器：它是编译器的第四个模块，负责将 AST 或符号表转换为中间表示（IR），并进行优化和优化。
目标代码生成器：它是编译器的第五个模块，负责将 IR 转换为目标机器的汇编代码或机器码，并进行优化和优化。
目标代码优化器：它是编译器的第六个模块，负责对生成的目标代码进行优化，以提高程序的执行效率和减少程序的存储空间。
目标代码链接器：它是编译器的最后一个模块，负责将多个目标文件和库文件链接成一个可执行文件，以及进行地址和符号重定位等操作。

编译器的工作流程通常包括以下几个步骤：

词法分析：将源代码中的字符序列转换为有意义的单词序列，并为每个单词分配 Token 种类。
语法分析：将 Token 序列转换为语法分析树或抽象语法树，以及对语法错误进行检测和报告。
语义分析：对语法分析树或抽象语法树进行类型检查、语义检查、符号表管理等操作，以及生成中间代码或目标代码。
中间代码生成：将 AST 或符号表转换为中间表示（IR），并进行优化和优化。
目标代码生成：将 IR 转换为目标机器的汇编代码或机器码，并进行优化和优化。
目标代码优化：对生成的目标代码进行优化，以提高程序的执行效率和减少程序的存储空间。
目标代码链接：将多个目标文件和库文件链接成一个可执行文件，并进行地址和符号重定位等操作。

遍

扫描越多遍越不好

文法

ε 空串的意思，起到一个语义复写的作用，把属性复写成综合属性往上传

空集和空字符串不是一个东西

右箭头产生式符号

右箭头加星号推导

句型：从开始符号经过 N 步推导，之间生成的任何字符串都是句型

句子：相比句型，只有有终结符的，才是句子

0 型文法最简单、表达能力最强，1 型文法增加了约束条件，2、3 型增加了更多。约束条件越多，表达能力越弱。

第三章

NFA DFA 的区别

DFA 只有一个起点
NFA 上面是一个字符串，DFA 上面是一个字符
NFA 同一个状态出发，同一个条件可以到达不同的状态；DFA 只能到达同一个状态

改写、化简、状态矩阵

就是一开始学的图

确定化

最少化

正规式改写 DFA

1(0|1)*101

自上而下语法树构造

左递归的消除

E->Ex|Ey|z

把所有包含左递归的候选式提取出来 E -> E (x|y)|z

X=x|y Y=z

E->EX|Y

用通用格式改写

E->YE’

E’->XE’|e

再代入 X 和 Y

E->zE’

E’->xE’|yE’|e

直接左递归是指产生式中右边的第一个符号就是左边的符号，间接左递归则不是。

把间接左递归通过代入的方式，改写成直接左递归，再使用直接左递归通用的改写方式

LL(1)

意义

第一个 L：从左往右输入，每次读入一个非终结符进行推导

第二个 L：产生式使用最左推导

1：每次只需要看右边的第一个数字

LL 代表左向右扫描输入，左推导，1 代表在任何时候，仅仅需要查看输入的下一个符号。

三个条件

不能存在左递归和二义性

可以通过 FIRST 集和 FOLLOW 集构造出一个 LL (1) 分析表

LL (1) 语法符合哪三个条件：不允许有左递归（改写），求 FIRST 集（从下往上，每个产生式的候选式相交为空、左边的符号能否推出 epsilon，如果一个产生式的候选式 L 推导出来之后能推出 epsilon，要拿它的 FOLLOW 集与每一个 FIRST 集相交）

如果一个文法的候选式可以推导出 ε，则 FIRST 和 FOLLOW 集都为空

求 FIRST 集和 FOLLOW 集

求 FOLLOW 集以右边为主

FOLLOW 集里是不可能有 epsilon 的，最多只有#

最后一节新课（第七章）

抽象语法树 (AST)

操作符在中间，左右两边的子结点是两个数
在属性文法阶段生成抽象语法树
逆波兰式：使用后序遍历抽象语法树的结果
考试可能会考给一个逆波兰式，把抽象语法树写出来
AST 对编程是很重要的工具，因为操作符就是 “操作码”、子结点就是 “操作数”

DAG 图

DAG 图是抽象语法树的简化表达形式

三地址代码

难度比较大，后面还有四元式、三元式、间接三元式，要注意区别。作用域及其之后的内容不考察。

三地址代码是代码的逻辑表达形式，两个操作数加上一个运算符就是三地址了（如 a+b）

三地址语句是中间代码的一种抽象形式，四元式（操作码、两个操作数、操作结果）是三地址代码在内存中的一种存放形式。因此四元式表格中会有很多操作数是子树的操作结果（帮助自底向上运算）。

三元式相比四元式，省去了操作结果，把需要中间结果参与运算的地方替换成了运算这个中间结果的指令的编号（内存地址）。缺点：如果指令编号发生变化，则绑定操作结果的指令都出错了。为了解决这个缺点，有了间接三元式。

间接三元式的表格中的编号（1、2 等）指的并不是表格第一列的指令编号（内存地址），而是指向了间接码表中的间接代码，间接代码再去指向指令编号。需要调整运算顺序时，只需重新安排间接码表，无需改动三元式。

期末复习课

上下文无关文法

上下文无关文法（Context-Free Grammar, CFG）是一种形式文法，其产生式规则只能够在左侧非终结符号周围添加或删除终结符号，而不考虑符号周围的上下文信息。在上下文无关文法中，每个产生式规则都由一个非终结符号和一个由终结符号和非终结符号构成的字符串组成，用符号 “->” 分隔。

最左推导：每次都从产生式最多边第一个符号开始推导

语法的二义性：二义性文法是指存在两种或多种不同的解析方式，即存在多个推导树的上下文无关文法。这种情况会导致语法分析器无法准确地确定语法结构，进而产生歧义。

为了避免二义性，可以采取以下几种方法：

优先级和结合性：在产生式规则中添加优先级和结合性的限制，例如在上述文法中，可以修改为 E -> E * E | num 和 E -> E + E | num，从而明确乘法优先于加法。
左递归消除：将产生式规则中的左递归转化为右递归，例如将 E -> E + E 转化为 E -> E + T 和 T -> E，从而消除左递归，减少二义性。
增加限制条件：在文法中增加限制条件，例如在上述文法中，可以限制加号和乘号不能同时出现，从而避免二义性。

第三章

词法分析

词法分析的目标

结果（五类词）：标识符，关键字，阶符，，分隔符，常数

正则表达式（正规式）：正则闭包和正法闭包的区别

正规式改写为 NFA DFA DFA 化简必考

NFA 和 DFA 的三个区别：

状态转换规则不同：DFA 中，每个状态只能由当前输入的字符转换到唯一的一个状态，即对于每个状态和输入符号，只有唯一的下一个状态；而在 NFA 中，对于每个状态和输入符号，可以转移到零个或多个状态。
状态转移表的大小不同：由于 DFA 状态转移规则的唯一性，DFA 可以使用状态转移表来表示状态转换；而 NFA 由于其状态转换规则的非确定性，需要使用更复杂的转换关系来表示，通常采用状态转移图来表示，因此状态转移表的大小也不同。
接受输入的方式不同：DFA 接受输入的方式是在最终状态上标记一个可接受状态，即只有当输入字符串结束时，DFA 最终状态是可接受状态时，DFA 才能接受该输入；而在 NFA 中，可以有多个可接受状态，只要有一个状态是可接受状态，NFA 就可以接受输入字符串。

总之，DFA 具有确定性、状态转移表简单、只有一个接受状态等特点，适合处理结构相对简单的输入；而 NFA 具有非确定性、状态转移图复杂、可有多个接受状态等特点，适合处理结构相对复杂的输入。

第四章

语法分析

从上往下推导和从下往上推导

从上往下推导是一种自顶向下的分析方法，它从语法的起始符号开始，通过不断地将它展开为更小的非终结符号，直到最终生成语法的终结符号序列。这个过程可以看作是一种自上而下的递归过程，常用的方法有递归下降分析（Recursive Descent Parsing）和预测分析（Predictive Parsing）。从上往下推导的一个特点是它需要提前知道语法的结构，也就是需要一个预测的语法分析表或递归下降分析程序。

从下往上推导是一种自底向上的分析方法，它从输入符号开始，逐步合并符号直到生成起始符号。这个过程可以看作是一种自底向上的规约过程，常用的方法有移进 - 归约分析（Shift-Reduce Parsing）和 LR 分析（LR Parsing）。从下往上推导的一个特点是它不需要提前知道语法的结构，而是通过观察输入符号和栈中的符号来进行规约操作，直到最终生成起始符号。

从上往下推导和从下往上推导在语法分析过程中的顺序和方式上存在一些区别。从上往下推导是自顶向下的展开过程，它从起始符号开始逐步展开直到终结符号；而从下往上推导是自底向上的合并过程，它从终结符号开始逐步合并直到起始符号。此外，从上往下推导需要预先知道语法的结构，而从下往上推导则是根据输入符号和栈中符号进行动态的规约操作。

左递归改写

从上往下推导时如何避免回溯

预测分析表（Predictive Parsing Table）：使用预测分析表可以在每个推导步骤中直接确定要选择的产生式，而无需回溯。预测分析表是一个二维表，行代表非终结符号，列代表终结符号（包括一个特殊的 “结束符号”），表格中的每个单元格包含相应非终结符和终结符组合的产生式。预测分析表的构建需要使用文法的 FIRST 和 FOLLOW 集合，确保表中没有冲突的项。
递归下降分析（Recursive Descent Parsing）：递归下降分析是一种基于递归的从上往下推导方法，每个非终结符号对应一个递归子程序。通过编写递归子程序来递归地展开非终结符号，遇到终结符号时进行匹配，避免回溯。确保在递归子程序中按照正确的顺序调用子程序，避免出现回溯。
预测子程序（Predictive Subroutine）：预测子程序是一种将递归下降分析与预测分析表相结合的方法。通过使用递归子程序和预测分析表中的产生式，可以在每个推导步骤中直接选择正确的产生式，避免回溯。
提前处理可选项：在编写文法时，可以将可选项提前处理为多个产生式，而不是使用可选项标记。这样可以减少回溯的机会，使得在每个推导步骤中能够直接选择正确的产生式。
语法设计的优化：通过优化文法的设计，可以减少回溯的可能性。例如，避免使用左递归、消除公共前缀等。

FIRST 集的求法

书上 LL (1) 模型：指针扫描字符串（看看）

第五章

LR(0)

LR (0)：使用状态机来模拟堆栈 (LR 分析法，它的模型时什么？根据 LR 的分析表来判断四个动作，ACCEPT、空白出错等。规约（必会）：栈顶形成句柄时要将句柄弹出来，将栈顶的字符规约成一个符号，此时需要查 GOTO 表，这决定了新的字符进入新的栈顶之后，新的字符是什么字段) - r 规约 s 移进 accept:1，空白：出错

移进和规约冲突等，LR (0) 就不行了