比赛的要求：
SysY语言使用非标准的输入输出库，怎么用Clang验证汇编代码的正确性？
链接I/O库后，将I/O函数的原型定义出来，并用extern声明，最终需要的是汇编代码，而非执行代码，所以用extern声明之后能够将其编译为汇编代码
第一章 引论
编译过程和编译程序的结构
C/C++编译系统
编译阶段的组合：
==中间代码生成及以前归前端，代码优化和目标代码生成归后端==
前中后端划分的好处：
词法分析：
正则表达式：
词法分析的自动构造程序
语法分析：
语法推导树→抽象语法树
下图所示为自顶向下的推导过程
抽象语法树：
Clang可以打印抽象语法树：
Clang –cc1 –ast-dump foo.c，foo.c是文件名
语法分析的自动生成工具：
语义分析：
常见的语义错误：类型不匹配、变量/函数未声明、重复声明、函数参数个数、类型不匹配等等
中间代码（IR）生成：
代码优化：
目标代码生成：
符号表管理与错误处理：
解释程序和一些软件工具
翻译的方式：编译or解释
编译：先翻译后执行，保存目标程序，一次翻译，多次执行
解释：边翻译边执行，即翻译一句就执行一句，翻译完毕也执行完毕，只保存原程序无需保存完整的目标程序，执行一次需要翻译一次。
PL/0语言
编译工具链：（相关使用在 educoder 和PPT中都有）
gcc/g++及其命令行参数
Clang及其命令行参数
arm-gcc可以生成arm架构的汇编代码（交叉编译）
qemu-arm
Makefile基础（见PPT）
cmake
第二章 文法与语言
文法的直观概念
文法是阐述语法的一个工具，语句是语法的实例
自底向上的规约——自顶向下的推导
规约：
推导：
推导可能会有回溯
推导过程按照语法规则推导出的都是句型，没有语法单位的全是终结符的句型叫做句子，例如下图右上角中
我 喜欢 音乐是句子，其他都是句型
巴科斯范式
符号和符号串
符号串的运算：
举例：
这里
$$
(a|b)^*=(a|b)^n,n\geq0
\
(a|b)^+=(a|b)^n,n>0
\
理解这个式子可以从其意义理解，都表示由a或b构成的一个串，区别在是否能为空串\epsilon
$$区分闭包和幂运算
符号串集合的运算：
$\alpha^0=\varepsilon$ ，而$A^0= { \varepsilon }$，区别在于前者长度为0，后者长度为1
举例：
文法与语言的形式化定义
定义：
所有的非终结符都用大写字母，所有的终结符都用小写字母
例如：
G1[S]:S→aSb,S→ab是最常见的形式，G1是文法的名字，S是开始符，冒号右边的是规则集
再例如：
下图有类似的作业题：
直接推导和直接规约：
规约是推导的逆运算
对应的有多步推导和多步规约
上图不成立原因是其为一步推导，但推导箭头上有+号，是多步推导的符号
箭头上是
*，表示星步推导，0~n步推导
句型和句子：
句子中都是终结符
语言：
文法的等价：
设计文法：
设计文法G，使得L(G)为能被5整除的有符号整数集
文法的类型
0型文法、1型文法、2型文法、3型文法
都由四部分（非终结符、终结符、产生式规则、起止符号）
0型文法：
- 产生式左侧至少含有一个非终结符
1型文法（上下文有关文法）：
- 产生式左侧至少含有一个非终结符
- 左侧符号串的长度不大于右侧符号串的长度（空规则除外）
1型文法又叫上下文有关文法：
p考虑 γAδ → γβθδ
A被替换成βθ,跟A的上下文相关
2型文法（上下文无关文法）：
- 产生式左部均为一非终结符
因为左侧均为单个非终结符，所以上下文无关，不用考虑上下文即可替换
3型文法（正规文法/有限自动机）：
只能是以下两者之一，不能混用
四种文法的关系：
上下文无关文法及其语法树
给定文法G[S]
- 问文法的语言
- 问文法的类型
给定语言，设计文法
从一个句型到另一个句型的推导往往不唯一
最左推导、最右推导（规范推导）
规范推导的逆过程，叫做规范规约
语法树：
上面的例子中最左、最右、随意推导得出的语法树都是该树，但并非所有文法都是如此
而下面的例子就既有最左推导，又有最右推导
语法的二义性：
如果文法G的某个句子存至少两棵不同的语法树，则称文法G是二义性的。
如果文法是无二义性的，一个句子的语法树反映了该句子的全部推导过程；
如果文法是无二义性的，一个句子的最左（最右）推导是唯一的。
示例：
证明语法的二义性：举一个例子
而且由于二义性问题是不可判定问题，即不存在一个算法，能在有限步骤内，确切判定一个文法是否是二义的，所以这种要证明语法二义性的题目一般都是有二义性的语言的二义性：
如果一个语言不存在无二义性的文法，则称该语言是先天二义性的。
前例$i+i\times i$的一个无二义性的文法：
句型的分析
文法推导和规约
有两种分析方法：自顶向下（Antlr）和自底向上（Bison）
自顶向下
上图可能会产生回溯，所以需要穷举，根本原因是 非终结符A的由终结符a开头的产生式有两个，所以不知道选哪个
改进方法是提公因式：
自底而上
规约是推导的逆过程，所以推导过程中存在的问题规约中也会遇到
解决方案：按照句柄规约—规范规约（移进-规约）
简单优先分析法：
优先级相等：有符号同时出现在产生式的右部，则从该产生式从左往右数在表里填上等号（左右关系是严格的）
优先级小于：
要先规约出A才能与c结合规约"S→cAd"，所以c<A优先级大于：与小于同理，只不过是从左往右看，所以小于中出现过的关系大于中就不会再出现。
由"S→cAd"和"A→ab"知b>d优先表中空缺的地方表示不可能，如果出现表示语法错误
上图右边的过程的做法：
只要符号栈最右侧的符号优先级$\leq$输入串最左侧的符号，就移进
$>$时则规约
==短语、直接短语、句柄==
短语：一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语
直接短语/简单短语：跟短语比，限定高度为2的子树。
句柄：直接短语中的最左直接短语为该句型的句柄。
例子：
不断地找句柄，做规约
又一个例子：
短语、直接短语、句柄
上面网页里的例子都做一遍
短语全都是由终结符构成：==错误！==短语由叶子结点的符号构成，但叶子结点也可以是非终结符，如上面链接中的例子
(Sd(T)db)句型中的每个符号都可能构成短语
文法中的多余规则和$epsilon(\epsilon)$规则
视频中有讲，但大概率不考，这里忽略
例题
往年考试题
==即使是考试题，也可能出有二义性的句子，要求画出语法推导树！！！！！==
小结
第三章 词法分析
单词的形式化描述工具
正规文法：
正规式(正则表达式)，及其表达的语言(正规集)
有限次使用上述步骤而定义的表达式仍是正规表达式，它们表示的符号串的集合是正规集
例如：
正规式等价：
若两个正规式表示的正规集相同，则称这两个正规式等价
正规式的代数定律：
一共很多，下面两个定律是容易记错的
正规式应用举例：
标识符和整数
正规式→正规文法的转换1、正规文法的终结符要和正规式的字母表相同
2、从形如
S→r的产生式开始3、按下表规则转换
A→xA|y并不具有一般性，反例如上图所示==最特殊的是$A→x^*y$，产生式是四个==
正规式→正规文法一个转换的例子：
正规文法→正规式的转换
正规文法→正规式一个转换的例子：
上面的例子：
结果应该是？
$$
A→(ac)^* (ad|b)
\
B→(ac)^* (bc|d)
$$
==待验证==
有穷自动机
本质上和状态转换图相同，但有穷自动机只回答Yes/No
分为不确定的有穷自动机（NFA）和确定的有穷自动机（DFA）
DFA
回答Yes/No的问题
可以有多个终止状态
举例：
NFA
DFA是NFA的特例
举例：$(a|b)^* abb$
a用0表达，b用1表达时就是以011结尾的二进制符号串，可以再转化成能被四整除的整数
要会计算Move(I,a)
状态集I的空闭包：该状态集不接受任何有意义的符号所能到达的所有的状态的集合
首先包含自己，所以一定不为空
四个转换
NFA→DFA
子集转化法（子集法）
好的画法是画表格
再一个例子
再一个例子
DFA最小化（化简）
化简需要两点：
1、消除不可达的状态；
2、消除无法到达终态的状态；
3、合并等价状态；
分割法：
分出结束态
找不同，分割阵营
只要存在不同就分成两个阵营
不断执行上述步骤（类似并查集）
NFA→正规式
按下面的规则转换
举例：
正规式→NFA
规则：
举例：
正规文法→NFA
NFA比正规文法多一个终结状态
NFA的字母表=文法的终结符
见下例：
即按照下面的规则：（正规文法只允许下面三种转移出现）
举例：
NFA→正规文法
和上面思路相反：
含$\epsilon$转移时建议转换成DFA确定化之后再转换成正规文法：
但也可以按照上图底部的规则来做
例子：
上图不能直接写成B直接推出两个0，因为这是正规文法，不能是俩零
词法分析程序构造
https://www.bilibili.com/video/BV1bF411g7Eh
如以下四步所示：
- 设计正规文法/正规式
- 正规文法/正规式→NFA
- NFA→（确定化）DFA
- DFA最小化
Flex
Flex文件结构：
Flex的I/O
Flex的其他函数及宏
注意事项
一个例子：wordcount程序进行计数
SysY2022词法分析的例子：
第四章 自顶向下语法分析
语法分析方法：
$FIRST(\alpha)$-可以从α推出的串首为终结符的符号集
同一非终结符的多个产生式，若右部的FIRST集无交集，则推导是确定的
注意下例中epsilon的特殊性
$FOLLOW(A)$-非终结符的后续终结符号集
注意FOLLOW集是在文法推导式中找A后面可能因其他非终结符而出现的终结符
而FIRST集是在文法推导式中找α自己可能推出的位于首位的终结符
示例：
$SELECT(A→\alpha)$-产生式的可选集
综合FIRST集和FOLLOW集得到SELECT集
求SELECT集：经验可以加快求的速度
如果右部只有终结符，则非终结符就是SELECT集
如果右部是
aA这种，则a即为所求如果右部全都是非终结符，如
AB，则要考虑A和B是否可能为空，再带入其各自的FIRST集如果右部能推出为空，则要计算FOLLOW集
LL(1)文法
对每个非终结符各自的所有产生式，SELECT集的交集都应该是∅
判断是不是LL(1)文法：
LL(1)文法的判别
右部的FIRST集，左部的FOLLOW集
若每个左部仅有一个产生式，则没必要求SELECT集，直接满足LL(1)
但下面的用
|隔开的容易被认错
但一些时候，如上例，不需要每一步都计算
求FIRST(X)算法：
==对于$X→Y_1Y_2··Y_n$，要考虑前面的非终结符为空的情况==
求FOLLOW(A)算法：
在所有产生式中找A，再在出现A的地方找A后一个符号的FIRST集
==例子==：
非LL(1)文法只需要找出一个交集不为空的例子即可
LL(1)文法需要对每个交集进行验证
非LL(1)文法到LL(1)文法
直接左递归：形如A→Aα，A出现在产生式最左侧
FOLLOW集不考虑epsilon
提取左公共因子
提取完之后将除了公共因子的括号内的部分命名为新的符号
消除左递归
==将左递归改为右递归==
例：
再一例：（算术表达式文法）
对于间接左递归
==间接左递归→左递归 →右递归==
间接左递归到左递归通过带入进行转换
消除一切左递归的方法：
重点就是对所有非终结符进行随机排序
再从左往右进行消除，消除的时候只看比自己排序靠前的构成的递归
==例子==：
两个不同的顺序进行左递归的消除
顺序不同，可能是否属于LL(1)的回答也不同
考试的时候多试试，既然这样问，就暗示会有转化为LL(1)文法的方法
LL(1)分析：递归下降分析法
基本思想
好像不考 不看了
LL(1)分析：表驱动分析法
思想：
例题
已知文法G[S]，试用LL(1)分析法分析串xxx
步骤：
证明文法是LL(1)文法（通过计算SELECT集）
如果不是LL(1)文法的话要使用
提取左公因子/消除左递归的方法转换成LL(1)文法根据SELECT集合填写LL(1)分析表
根据分析表进行分析（注意将产生式右部的符号压栈时要==逆序==，最左的放在栈顶）
LL(1)出错处理
不考没看
第五章 自底向上【优先】分析
简单优先分析法没看
算符优先分析法
==OG文法可能是二义文法，但OPG文法一定是无二义性文法==
==不是规范规约，分析结果未必是语法树==
FIRSTVT和LASTVT会算就行了
最左素短语
判断是否为算符文法：有没有两个非终结符相邻，没有的话才是算符文法
算符文法定义如下：
一个例子：
b是句型bbA的短语短语b不含A，与性质2不矛盾，因为此b非彼b
算符文法的算符优先关系定义：
算符优先文法定义如下：
任意两个终结符之间算符优先关系固定且唯一
素短语和最左素短语
- 素短语
- 至少含有一个终结符
- 除自身之外不包含其他素短语
- 最左边的素短语成为最左素短语
- 素短语
最左素短语定理：
FIRSTVT和LASTVT
填表
小于：右侧非终结符的FIRSTVT集
大于：左侧非终结符的LASTVT集
==小于号按行填，大于号按列填==
一个例子：
顺序：
- 计算文法的FIRSTVT和LASTVT
- 构造优先关系表
- G[E]是算符优先文法
- 分析串
i+i*i#
第六章 LR分析
LR(k)：L(Left to right parsing), R(right-most derivation in reverse), K(look ahead k token(s))
LL(1)可以类比，但LL(1)是自顶向下的推导
每一步句柄都在栈顶
LR(0)分析
可归前缀和活前缀
识别活前缀的DFA
画NFA的时候保留产生式的序号
这里的DFA与正常DFA不同
这里的可以回溯
- 需要先写出扩充文法
S’- 对每个产生式都构造识别活前缀的NFA
- 将所有NFA按照一定规则添加边连成一个整体
- 将NFA确定化得到DFA
- 根据DFA对输入串进行分析
构造LR(0)项目集规范族
与上面状态用数字区分不同，状态也可以直接用产生式命名
LR(0)项目分类：
DFA与LR(0)分析表的关系：
移进项目
待约项目
规约项目
接受项目
冲突：
移进-规约冲突 和 规约-规约冲突
不存在上述两种冲突的话，就是LR(0)文法，可以采用LR(0)分析
存在上述冲突时，可以采用LR(1)分析法进行分析
SLR(1)分析
步骤：
- 拓广文法
- 求Follow()集
- 求LR(0)项目集族及识别活前缀的DFA
- 通过求规约符号集左侧符号的Follow集，看Follow集与移进符号（·号==后面==的符号）有无交集，无交集则为SLR(1)文法
- 构造SLR(1)分析表
- SLR(1)分析法分析目标串
有移进-规约冲突时，如果可以用FOLLOW集来区分的话，就是SLR(1)文法
- ==诸如【A→$\epsilon$】这样的会被写成【A→·】，也算是规约项目，会和其他移进项目冲突==
例子：
LR(1)分析法
SLR(1)法存在的问题
LR(1)分析法在构造项目时，将特定位置的后继符信息一并纳入考量范围
LR(1)的基本思想
搜索符的继承与传播
Move时不计算前瞻符号
LR(1)分析表的构造
==句点后面是非终结符时要加上所有其起始的产生式==
一个例子：
判断是否属于LR(1)文法
==移进符号集和搜索集（前瞻符号集）两两相交为空集，则可以称作LR(1)文法，即没有移进和规约的冲突==
再一个例子：
LALR(1)分析
对LR(1)文法的项目进行同心项目集合合并，结果没有LR(1)项目冲突，则可以称之为LALR(1)文法
合并后产生规约-规约冲突的文法：（合并同心集只会产生规约-规约冲突）
特点：
“大小上与LR(0)/SLR相当”：甚至在合并同心集之后可能退化为SLR文法
==学的顺序是LR(0)→SLR(1)→LR(1)→LALR(1)==
==但LALR(1)在LR(1)的基础上合并了同心集，减少状态数量的同时也导致导致分析能力下降==
几种文法的关系：
但凡能自顶向下的都可以自底向上规约
二义性文法的应用
估计不考 没看
总结
LL(1)文法不能出现左递归，但LR文法可以接受左递归
四种分析法共性：
FOLLOW集消除移进-规约冲突，求规约那个产生式的左部的非终结符的FOLLOW集，看FOLLOW集和要移进的符号有没有重合
前向搜索符号集消除规约-规约冲突，明白具体在什么时候可以规约，所以说前向搜索符号集是FOLLOW集的子集
如下图所示：
LR(0)：任何符号都用指定产生式规约
SLR(0)：FOLLOW集中的符号才使用指定产生式规约
LR(1)：前瞻符集合中的符号才能使用指定产生式规约
LALR(1)：在LR(1)分析法的基础上化简，合并同心项目集，合并后无规约规约冲突，则可以使用LALR(1)分析法
基本概念
第七章 语法制导的语义计算
基于属性文法的语义计算
属性文法
综合属性（自下而上）
终结符的综合属性是由词法分析器提供的词法值
继承属性（自上而下）
父结点和==兄长==
L-翻译模式既有综合属性，又有继承属性； S-翻译模式只有综合属性。
仅含有综合属性时可以在LR分析的同时构造带注释的语法树，而如果含继承属性时需要先构造语法树，再计算属性
语义计算
S-属性文法和L-属性文法
S-属性文法
L-属性文法
基于S-属性文法的语义计算就是在LR分析的同时计算语义
基于L-属性文法的语义计算要先dfs建立语法树，再计算语义，按照下面的算法：
（先计算所有孩子的继承属性，递归遍历所有儿子之后，再计算自己的综合属性）
一个例子：
相对来说能用LL(1)比用LR(1)可以更容易地画出语法树
==LL(1)文法要求同一个非终结符的产生式的SELECT集没有交集==
且左递归文法一眼就不是LL(1)文法
语法树中继承属性值写在符号的左侧，综合属性值写在符号的右侧
算继承属性→遍历儿子→算综合属性
基于翻译模式的语义计算
翻译模式：
S和L翻译模式：
S-翻译模式例子：
由于语义就跟在符号旁边，所以像上图里可以把语义视作一个结点，根据属性花括号在产生式中的位置，来决定语法树中属性的位置
L-翻译模式自顶向下
要求文法是LL(1)的
步骤：
继承属性对应形参，综合属性对应返回值
除了上面使用递归下降子程序之外，还有非递归的方法
不考没看
L-翻译模式自底向上
三种方法：
- 从翻译模式中删除嵌入在产生式中间的语义动作
- 继承属性的求值结果以综合属性值存放在语义栈中，对继承属性的访问变成对语义栈中某个综合属性的访问
- 模拟继承属性的计算
第一种方法适用于没有继承属性出现时，可以将嵌入在产生式中的予以动作用非终结符代替
第二种方法：适用于继承属性是简单拷贝综合属性得到的
综合属性值在语义栈中位置不能确定的情形
第三种方法：模拟继承属性的计算
与上面第二种方法类似，但这时继承属性不是简单拷贝自综合属性，而是要通过一定计算
这样通过引入非终结符M，可以直接拷贝A的综合属性运算的结果
一个例子：
第八章 静态语义分析和中间代码生成
符号表
静态语义分析
中间代码生成
TAC（三地址码或四元式）表示
抽象语法树仅表示了程序的结构，但三地址码TAC包含了标号和跳转指令，更接近目标程序。所以AST是更高级的中间代码表示形式，而TAC是较为低级的中间代码表示形式
三地址码：
几种翻译模式
赋值语句和算术表达式的翻译模式
==举例==：
说明语句的翻译模式
**==举例==**：
数组说明和数组引用的翻译
数组元素地址计算：
举例：
布尔表达式的翻译
**==举例==**：
优化的翻译模式
短路代码：
**==举例==**：
控制语句的翻译
if-then语句
if-then-else语句
while-do语句
顺序复合语句
break语句
过程调用的翻译
第九章 运行时存储组织
活动记录
下图是**==R第一遍被调用时R自己的display表==**
所以没有指向S的指针
下图是**==R第二遍被调用时第二个R的display表==**
display表的维护
过程调用：
第十章 代码优化与目标代码生成
优化方法可能会反复使用，这会导致需要多次优化
基本块、流图和循环
基本块
基本块
基本块的入口：
- 程序的第一条语句
- （条件or无条件）跳转语句的跳转目标语句
- 条件跳转语句的下一条语句（不是目标语句，是下一条语句）
举例：
（基本块划分）
流图
定义：
上面的例子：
常用的优化方法
删除公共子表达式
局部公共子表达式
全局公共子表达式
有的能删除，有的不能
删除无用代码
常量合并
代码移动
不管循环执行多少次都得到相同结果的表达式，要在进入循环之前就对他们求值
强度削弱
基本归纳变量：
（用同族变量替代，记得将归纳变量初始化）
循环优化
入口结点：
自然循环：**==只能有一个入口==**
- 强连通子图
- 只有一个入口
必经节点/支配结点
==首先，必经结点一定包含自身==
到n的必经节点也一定是到n的所有前驱结点的必经结点：(否则的话就存在不需要经过该“必经结点”就能到达n的路径了)
自身==并==上所有前驱结点的==交==集
自身==并==上所有前驱结点的==交==集
举例：
回边：被支配结点到支配结点之间的边
D(n)是必经结点集合
自然循环的性质：
自然循环的识别：
求循环的方法：
- 找支配结点集
- 根据支配结点找回边
- 每个回边对应一个自然循环
常用代码优化技术
窥孔优化
删除冗余的存取（store/load）操作
以及下面一长串：
局部优化
以基本块为窗口的窥孔优化
叶结点下面标记倡廉或标识符，右边标记变量名（变量定值表）
有向无环图DAG构造：
构造的同时要进行优化：
例子：
再写出优化后的四元式（三地址码）
可能的进一步优化：（下图还是要保留T
2和T6的）但后面出了基本块之后不活跃都可以删掉
循环优化
不能代码外提的例子：
代码外提的条件：
全局优化
方法一样
目标代码生成技术
- 本文链接：https://wan-nan.github.io/2022/05/03/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86%E7%AC%94%E8%AE%B0/
- 版权声明：本博客所有文章除特别声明外，均默认采用 许可协议。