编译原理章节整理
bjfu编译原理复习资料整理，仅供参考
编译原理章节整理
第一章
判断：
-
编译器生成的目标程序都是可执行的程序。（错误）
-
汇编器将高级语言程序翻译成汇编语言程序。（错误）
3. 编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。（错误）
4. 因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。（错误）
5. 编译程序的五个组成部分缺一不可。（错误，中间代码生成和代码优化并不是必不可少的）
6. 许多编译程序在识别出语法单位后并不真正构造语法树。（正确）
7. 高级语言程序到低级语言程序的转换是基于语义的等价变换。（正确）
8. 含有优化部分的编译程序的执行效率高。（错误）
9. 优化的任务在于对中间代码进行加工和变换，以其能产生运行结果更为准确的目标代码。（错误）
10. 编译前端主要由与源语言和目标机相关的那些部分组成。（错误）
11. 无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序至少扫描一遍。（正确）
12. 在编译过程中，既可以将几个不同的阶段合为一遍，也可以把一个阶段的工作分为若干遍。 （正确）
13. 取编译程序前端改写其后端以生成不同机器上的目标代码，目前技术上还难以实现。（错误）
14. 支持程序设计人员进行程序计开发的工具，除了编译程序以外，还需要编辑程序、链接程序和调试程序等其他一些工具。 （正确）
x+y=1是语法错误
float % float, 数组下标越界是语义错误
第二章
内容：
① 符号串和符号串集合的运算、文法和语言的定义
s0=ε，s1=s，s2=ss
设s=01，则
s0=ε
s1=01
s2=0101
A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪……称为集合A的正闭包。
A*＝ A0 ∪A＋称为集合A的闭包
语言是由句子组成的集合，是由一组符号所构成的集合
集合{a,aa,aaa,…} 为字母表∑上的一个语言
文法是对语言结构的定义与描述。（或称为“语法”）。
文法的形式定义：文法G[S]=（VN，VT，P，S）
从左到右：非终结符号集、终结符号集、产生式或规则的集合、开始符号（识别符号）S∈ VN ，S至少要在一条规则中作为左部出现
句子是所有终结符号组成的句型。句子：i+i*i，句型：E+E*i
语言是文法G[S]所产生的所有句子的集合
② 几个重要概念：规范推导、规范归约、递归文法
最右推导也称为规范推导。
规范推导的逆过程，称为最左归约，也称为规范归约。
用最左推导所推导出的句型称为最左句型
用最右推导所推导出的句型称为最右句型，通常称为规范句型
递归规则：规则右部有与左部相同的符号
含有递归规则的文法，为直接递归文法：
G[S]：
S→L|SL|SD
L→a|b|…|z
D→0|1|…|9
间接递归文法：
A→Ba
B→Ab
6zXTJXBaYd6D10PAAXSAA%3D%3D%3D------WebKitFormBoundaryM4y5s6M1P40XPgBV--Boundary3rTEoyCyzKkPvajEp
③ 文法的BNF、EBNF表示
EBNF在此基础上又增加了三种元符号：{ }, [ ], ()
④ 文法和语言的分类
文法和语言分类：0型、1型、2型、3型
这几类文法的差别在于对产生式施加不同的限制。
0型文法（L0）称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。
举例：
0型文法
G[S]:
S→ABS|AB
AB→BA
A→0
B→1
1型文法（L1），左边可以有多个字符，但必须有一个非终结符
P： αAβ ::= αγβ ，其中 A∈VN，α，β ∈V*， γ ∈V＋
称为上下文敏感或上下文有关。也即只有在α 、 β这样的上下文中才能把A改写为γ
举例：
1型文法
G[S]:
S→aSBE
S→aBE
BE→bE
aB→ab
bB→bb
bE→be
eE→ee
2型文法（L2），左边只能有一个字符，而且必须是非终结符
P： A::= β 其中 A∈ VN ，β∈V*
称为上下文无关文法。也即把A改写为β时，不必考虑上下文。
举例：
2型文法
G[S]:
S→AB
A→BS|0
B→SA|1
S→ε
2型文法（L2），左边只能有一个字符，而且必须是非终结符
P： A::= β 其中 A∈ VN ，β∈V*
（左线性）P： A:=a 或 A::=Ba 其中 A、B∈VN a∈ V*T
（右线性）P： A:=a 或 A::=aB 其中 A、B∈VN a∈ V*T
3型文法称为正则文法（又称正则语言）。它是对2型文法进行进一步限制。左线性和右线性文法是相互等价的
举例：
3型文法
G[S]：
S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
重点：
① 在理解基本概念的基础上，根据给定的语言写出文法、根据给定的文法确定语言
例题1，已知文法求语言：
G[S]
S ::= AB
A ::= aA|a
B ::= bB|b
L(G[S])={a^mb^n|m,n≥1}
例题2，已知语言{ab^na|n≥1}构造文法：
G1[S]：
S→aBa,
B→b|bB
G2[S]：
S→aBa,
B→b|Bb
② 判文法的二义性
若文法是二义性的，则在编译时就会产生不确定性
文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。
解决文法的二义性：1. 运算优先级，2. 把排除二义性的规则合并到原有文法中，如：
G[E]：
E→E+E|E*E|(E)|i
改写为：
E::= E+T | T
T ::= T*F | F
F ::= (E) | i
第三章
内容：
词法分析程序的任务
编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，再由语法分析程序接下去处理。
单词类别用整数编码表示：关键字（1）、标识符（2）、常数（3）、运算符（4）、分界符（5）
词法分析程序的手工实现
单词的文法--状态图--流程图--伪码
词法分析程序的自动构造
正规式：正规集的描述机制
例子：(a|b)*(aa|bb) (a|b)* 所有含有两个相继的a或相继的b的符号串
有穷自动机（NFA、DFA）：正规集的识别机制
有穷自动机是一种数学模型，具有离散的输入与输出，系统可处于有穷状态中的任何一个
它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合
引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具
分类：确定的有穷自动机（DFA）、不确定的有穷自动机（NFA）
① 确定的有穷自动机（DFA）
M=(Σ,Q, f, S, Z)
从左到右依次为：有穷字母表、有穷集、转换函数、唯一的初态、终态集（ f：Q×Σ→Q，f（q1，a）=q2 ）
例子:
M:（{a,b},{0,1,2,3},f，0，{3}）
f（0，a）=1 f（0，b）=2
f（1，a）=3 f（1，b）=2
f（2，a）=1 f（2，b）=3
f（3，a）=3 f（3，b）=3
输入字符
状态 a b
0 1 2
1 3 2
2 1 3
3 3 3
对于符号串abaab
δ（0，abaab）
=δ（1，baab）
=δ（2，aab）
=δ（1，ab）
=δ（3，b）
=3 (接受)
对于符号串abab
δ（0，abab）
=δ（1，bab）
=δ（2，ab）
=δ（1，b）
=2 (拒绝)
② 不确定的有穷自动机（NFA）
M=(Σ, Q, f,S, Z)
f是一个多值函数 f：Q×Σ→2^Q （Q的幂集，Q中所有子集组成的集合）
例子：
NFA确定化的两个概念：
-
状态集合I的e-闭包，表示为ε-closure(I)
① 若q∈I，则q∈ε-closure(I)；
② 若q∈I，则从q出发经过任意条ε弧而能到达的任何状态q'都属于ε-closure(I)。
理解：集合I内所有状态和这些状态经过ε弧能到达的状态
-
I是状态集，由I中的状态出发，经过一条a弧可能到达的状态的集合称为move（I，a），则
理解：I集合中状态经过a弧到达的状态（注意这里不包括集合中的状态）
Ia= ε_closure ( move( I , a ) )
理解：move集合中状态经过 ε弧能到达的状态
基于上述概念将NFA转DFA（非常好懂）：
理解：初始状态和ε弧能到的在一个集合，求其经过任一弧能到的新集合（集合状态不一定与之前集合重合）。如果不是空集，就以这个集合经过任一弧求能到的新集合。把这些不同的集合分别视为一个状态。
DFA的最小化：
最简的DFA = 它没有多余状态和等价状态
多余状态：任何输入串不能到达的状态（多余状态和只有多余状态能到达的状态）
等价状态：状态S和T等价的条件是
① 一致性条件：状态S和T必须同时为终态或非终态
② 蔓延性条件：对于所有输入符号，S和T必须转换到等价的状态里
理解：1. 把状态按终态和非终态划分；2.不是等价状态（转换到的状态不等价）则划分；3.重新设置状态号
有穷自动机NFA和正规式等价
有穷自动机NFA和正规文法等价
NFA→正规文法
正规文法→NFA
判断：
1．对任意一个右线性文法G，都存在一个NFA M，满足L(G) = L(M).
2．对任意一个右线性文法G，都存在一个DFA M，满足L(G) = L(M).
3．对任何正规表达式e，都存在一个NFA M，满足L(M) = L(e) .
4．对任何正规表达式e，都存在一个DFA M，满足L(M) = L(e) .
quan
LEX的实现原理和源程序的基本组成
LEX的工作原理是将LEX源程序中的正规式转换成DFA，进一步通过控制程序识别单词
第四章
有关概念:短语、简单短语、句柄、最左素短语
理解：短语就是某句型中的子串，这个子串是由某个非终结符通过至少一步推导得到的子串，而简单短语就是由某个非终结符通过一步推导得到的子串。
任一句型的最左简单短语称为该句型的句柄。
重点掌握并能灵活运用的算法：
① 消除左递归的方法（改写为EBNF或改写为右递归）
规则二：结合规则一进行
方法二：也很常用，方便理解
② 递归子程序法的伪码描述
③ 通过构造FIRST集合、FOLLOW集合判定LL(1)文法，构造LL(1)分析表，使用LL(1)分析法分析语法成份的过程
理解：不考虑存在 | 的情况（分成两条），ε则follow(左)，否则first(右)
④ 通过构造LR(0)、SLR(1)分析表判定是否为LR(0)、SLR(1)文法，使用LR分析法分析语法成份的过程
活前缀：规范句型（通过规范 推导 / 归约 得到的句型）中不含句柄右边任何符号的前缀
https://www.cnblogs.com/getianao/p/10195493.html
https://blog.****.net/qq_36744540/article/details/73499641
Si:移进，并将状态i进栈
ri:用第i个产生式归约，同时状态栈与符号栈退出相应个符号，根据GOTO表将相应状态入栈
理解：出现点在最后，看A的follow集标记为ri
⑤ 通过求解FIRSTVT集、LASTVT集构造算符优先分析表，使用算符优先分析法分析语法成分
理解：firstvt靠最左的终结符，lastvt靠最右的终结符
理解：最左素短语是i