以下内容
大部分
来自wzl 巨佬的博客：
编译原理复习总结-耗子尾汁_吾仄lo咚锵的博客-CSDN博客
少部分
来自个人总结，也缺少一些东西，仅仅是个人复习编译原理自用，如果一定要用请务必结合上面大佬博客加下面大佬视频
以下是个人期末复习参考的大佬b站视频
如有侵权，十分抱歉 ，请联系我删除！
编译原理复习大纲
第一章
解释
（Interpret）的过程是把源程序代码一行一行的读懂，然后一行一行的执行，发生在运行时，产物是
运行结果
编译
（Compile）的过程是把整个源程序代码翻译成另外一种代码，翻译后的代码等待被执行或者被优化等等，发生在运行之前，产物是
另一份代码
。
为什么需要编译器：因为不能出错
汇编语言->机器语言（11对应）
编译：高级语言->低级语言
编译程序的结构
: 1.词法分析器，2.语法分析器3.语义分析和中间代码产生器4.优化器5.目标代码生成
1.词法分析器：又称扫描器
2.语法分析器：分析器
遍
：编译过程五个阶段仅仅是逻辑功能上的 一种划分。具体实现时，受不同语言，设计要求，使用对象和计算机条件的限制，往往将编译程序组织为若干遍，
所谓的“遍”是对源程序或源程序中间结果 从头到尾扫描一遍，并作有关的加工处理，生成新的中间结果或者目标程序
在主存可能情况下，一般还是遍数尽可能少一点，并不是所有语言都可以用单遍编译此程序实现
编译前端和后端
概念上，我们有时候把编译程序划分为编译前端和编译后端，
前端
主要由与源语言有关但是与目标机无关的那部分组成，
这部分通常包括词法分析，语法分析，语义分析和中间代码
生成。而且有一些代码的优化工作也可以包括在前端。
后端
包括：编译程序中与目标机有关的那些部分。
如与目标机有关的代码优化和目标代码生成
。后端不依赖于源语言而仅仅依赖于中间语言。
第二章
词法规则
的描述工具：有限自动机
语法规则
描述工具：上下文无关文法
关于闭包
:分为正闭包和自反传递闭包：（补充文本）
注意空字 ε
乔姆斯基四型文法
：
0型文法：短语文法（不重点）
1型文法：上下文有关文法
2型文法：上下文无关文法
3型文法：也称右线性文法，但也有另一种形式：左线性文法， 由于三型文法等价于正规式所以也称作正规文法
上下文无关文法
（重点）：
上下文无关文法是一个四元式（Vt，Vn，S，P）（符号不会打书本28页）） 这里的NT都是大写
Vt：非空有限集合，他的每个元素成为终结符号，（一般小写字母）
Vn是一个非空有限集，它的每个元素成为非终结符号，Vt∩Vn = 空（一般用大写字母）
S：是一个非终结符号，称为开始符号；
P ：一个产生式集合，每个产生式形式P->Vn a∈（Vt∪Vn）
句型，句子
假定G是一个文法，S是它的开始符号，称 S ⟹ * α是一个句型，仅含终结符的句型是一个句子。
注意 * 指0步以上推导，+指1步以上推导（把+记住成正就好记）
语言
文法G所产生的句子的
全体
就是一个语言
最左推导和最右推导
自顶向下
（给你非终结符让你推导出非终结符）
最左推导：被替换的总是当前符号串中的最左非终结符
最右推导：被替换的总是当前符号串中最右的非终结符（规范推导）
自底向上
(归约 比如给你aaaabbbb 让你归约 给你终结符让你归约成非终结符)
最右归约：被归约的总为当前符号串最右
最左规约：被归约的总为当前符号串最左（规范归约）
规范：右推左规
把规范推导逆着看就是规范归约
语法树
1.
子树：任意一结点及其后继
直接子树（树高为2）：叶子节点的父节点
一颗语法树< – >多种推导序列
以可语法树< – >唯一最左推导和最右推导
2.
二义性文法：L（G） 的某个句子对应不只有一颗语法树
无二义性文法：L（G）产生的每一个句子都只有一颗语法树
3.
短语
：每棵子树的叶子
直接短语：简单短语是一次性能推导出来的，一次推导出叶子节点
句柄
：
直接短语中的最左直接短语为该句型的句柄
。（就是在规范分析中最先被归约的子串，可以在语法树中找最左的叶子节点）
（注意题目说的是推导过程每一步的句柄还是语法树的句柄）
素短语
：至少包含一个终结符 且不包含更小素短语的短语
化简文法
1.从S开始一步步看，将含有永远消不掉的符号的产生式消去
2.删除 ε产生式 如 A-> ε
3.删除形如A->B的单产生式0
第三章（词法分析）
右线性文法：形如 A->aB 以及 A->a （非终结符号只能在右边）
状态转换图
（右线性文法，无ε产生式时 ）
1.用状态图和正规式描述标识符
结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出节点状态下可能出现得输入字符或字符类。 其中0为初态，2为终态（用双圈表示）。终态结上打个星号*意味着多读进了一个不属于标识符部分得字符，应把它退还给输入串。
正规式与正规集
p47
Σ 为字母表 如 Σ = {A,B,0,1}
1
| 正规式 | 正规集 |
|---|---|
| ba * | Σ 上所有以b为首后跟任意多个a的字 |
| a（a|b）* | Σ上所有以a为首的字 |
| (a|b)* (aa|bb)(a|b) * | Σ上所有含有两个相继的a或两个相继的b的字 |
2
| 正规式 | 正规集 |
|---|---|
| （A|B）(A|B|0|1)* | Σ 上的“标识符”的全体 |
| （0|1）（0|1）* | Σ 上“数”的全体 |
如果两个正规式所表达的正规集相同，则认为二者等价
确定有限自动机
（DFA）p47页
非确定有限自动机
（NFA）p49页
LEX
（词法分析器的语言p58 上课有讲?） LEX用来描述和自动产生所需的各种词法分析器，包括正规式定义和识别规则两部分，将LEX程序编译后所得结果程序记为L，其作用同有限自动机一样，可用来识别和产生单词符号。
正规式
：将文法的终结符号，用* | · 连接成的表达式（这里的*是自反闭包的意思）
1.由正规式构造DFA（分裂法）
2.确定化最小化。(注意最小化，我感觉b站这个大佬视频讲的最小化之前状态集合太少了，感觉最小化方法不太行，我自己百度的)
（1.的规则看补充）
第四章（自下而上语法分析）
自顶向下的语法分析
LL(K)分析->LL(1)
递归下降分析
预测分析
消除左递归性
：
A->Aα|β ={ A->βA‘ ,A’ = αA’|ε}
求First集
（p78底部）和
Follow 集
（p79）
判断LL（1）文法
1）已经化简无左递归
2）对G中每个产生式A->r1|r2|…rm 其各候选式均满足：
1.First（ri）∩First（j） = ∅（两两不相交）
2.若有候选式为ε（A->ε），则First（ri）（这边指其余候选式）∩ Follow（A）=∅
求LL(1)分析表的三个规则
对于A->ri
1. 求First(ri) = a ,则在m[A，a]处填入此表达式
2.若First(ri) = ε，则求Follow(A) = b(A->ε)
3.其余空着
第五章（自下而上的语法分析）
自底向上的语法分析
简单优先
算符优先
优先函数
LR分析：LR(0)<SLR(1)<LALR(1)<LR(1)<无二义性
句型，句子
假定G是一个文法，S是它的开始符号，称 S ⟹ * α是一个句型，仅含终结符的句型是一个句子。
注意 * 指0步以上推导，+指1步以上推导（把+记住成正就好记）
语言
文法G所产生的句子的
全体
就是一个语言
最左推导和最右推导
自顶向下
（给你非终结符让你推导出非终结符）
最左推导：被替换的总是当前符号串中的最左非终结符
最右推导：被替换的总是当前符号串中最右的非终结符（规范推导）
自底向上
(归约 比如给你aaaabbbb 让你归约 给你终结符让你归约成非终结符)
最右归约：被归约的总为当前符号串最右
最左规约：被归约的总为当前符号串最左（规范归约）
规范：右推左规
把规范推导逆着看就是规范归约
前缀、活前缀
字的前缀是指该字的任意首部。例如字abc的前缀有ε、a、ab或abc。
所谓活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。之所以称为活前缀，是因为在右边增添一些终结符号之后，就可以使它成为一个规范句型。在LR分析工作过程中的任何时候，栈里的文法符号(自栈底而上)X1X2…Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。因此只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。（我也不太懂活前缀= v =）
关于课本有一题p102面例5.7 wzl大佬（上面链接博客）给了详细解题过程，对概念建立有所帮助
LR(0)项目
1.规约项目（A->α· ） 2.接受项目（s-> α·）
2移进项目（A->α·xβ） 4.待约项目（A->α·Xβ）
LR（0）项目指右边某位置上标有· 的产生式
eg.A->xyz 有四个项目 A->·xyz A->x·yz A->xy·z. A->xyz·
所有等价项目组成一个项目集工，成为项目闭包，每个项目集闭包对应自动机的一个状态
项目集的构造：求基本项目集工的闭包=>找等价项目 eg.S->cc·B 这个时候看出B是一个待约项目则需要去找B能推出什么 B->·ccB B->·b （看b站视频做题理解一下，我第一次看这边也没看懂，直接跳过看做题）
判断LR(0)文法：无冲突项目（移进-归约 归约-归约 冲突）
LR(0)分析表
（看b站视频）
判断SLR(1)文法
1.DFA中存在冲突项目（移进-归约 归约-归约）
2 In = {A1 -> α·a1β,A2->α·a2β …… ,B1->α·,B2->α·} （这里的In指的是一个状态也叫项目集）
当{a1,a2,….,am}（注意：这个是下一个需要移进的符号的集合）,FOLLOW(B1)，FOLLOW(B2)…两两不相交时为
SLR(1)
文法
SLR(1)分析表：
与LR(0)不同点在于：对于每一个归约项目 A->α求FOLLOW(A)得到的输入符号处填rn，其余都和LR(0)相同。
第六章（属性文法和语法制导翻译）
属性定义
：在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为
属性
）。
1.
属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等
2.
属性可以进行计算和传递
语义规则
：
对于文法的每个产生式都配备了一组属性的计算规则
属性文法
(也称属性翻译文法)是在上下文无关文法的基础上为每个文法符号(终结符或非终结符)配备若干相关的“值”(称为属性)。.
属性通常分为两类：
综合属性
（自下而上传递信息）和
继承属性
（自下而上传递信息）
所谓
语法制导翻译法
，
直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则
具体定义请看课本p136页 尾部（说实话我没看明白，有点抽象）
来自课本的特别强调:
1
.终结符
只有
综合属性
，它们由词法分析器提供
2.
非终结符
既可以有
综合属性
，也可以有
继承属性
，文法开始符号的所有继承属性作为属性计算的初始值
S-属性文法：只含有
综合属性
，通常可借助于LR分析器实现，自下而上计算
L-属性文法：可以通过自上而下分析方法（LL（1））的同时实现L属性文法的计算，
S-属性文法一定是L-属性文法
L－属性文法适合于一遍扫描的自上而下分析
S－属性文法适合于一遍扫描的自下而上分析
第七章（语义分析和中间代码生成）
常见中间语言形式：
1.后缀式（逆波兰表示法）操作数在前，算符写在后
2.图表示法：DAG,抽象语法树
3.三地址代码