编译原理期末复习-按考点

Ocean University of China

第一章引论

翻译器、编译器、解释器

翻译器：把一种语言变成另外一种语言（语义等价）
编译器：翻译器的一种
解释器：不产生目标代码，解释执行源程序（根据程序和输入给出输出）

解释器执行的效率比编译器生成的机器代码的执行效率低（解释器缺少了类似于编译器的优化过程）。

解释器直接执行用编程语言编写的指令。它在执行程序时，会逐条将源代码解释成机器语言并执行，因此运行速度相对较慢。

编译程序的各个阶段

词法分析
语法分析
语义分析
中间代码生成（以上是“前端”）
独立于机器的代码优化（以下是“后端”）
代码生成
依赖于机器的代码优化

类型检查通常出现在语义分析中。

编译器在语法分析阶段会将记号流构造成抽象语法树。

编译器会在词法分析阶段去掉源程序的注释。

编译程序各阶段的工作都可能涉及到：错误管理

编译程序的各个阶段都可能会涉及到符号表管理

e.g. 对一段程序进行编译时，将while识别为关键字的编译阶段是词法分析。

语法分析阶段，编译器会检查程序中的单词序列是否遵守特定的语法规则。

语义分析阶段，编译器检查变量和常量是否有正确的类型、函数是否正确地调用。

（往年考题）编译器各阶段中，词法分析器和语法分析器的典型关系是以语法分析器为主导，词法分析器作为子程序被调用。

编译器在词法分析阶段可以将来自编译器各个阶段的错误信息和源程序联系起来。

第二章词法分析

对源程序的翻译

e.g. 如果对下列源程序进行词法分析，请问词法分析器应该返回多少个记号？

printf("Total=%d\n", score);

答：返回7个记号：printf, (, "Total=%d\n", ,, score, ), ;.

这里把双引号内的识别为字符串，算一个记号。

正规式

“ $L^*$ ”：闭包，表示零个或多个

“ $L^+$ ”：正闭包，表示一个或多个

正规定义

e.g. C语言标识符的正规定义：

letter_ → A | B | … | Z | a | b | … | z | _

digit → 0 | 1 | … | 9

id → letter_ ( letter_ | digit )*

一些缩写：

一个或多个实例：一元后缀算符“+”。
零个或一个实例：一元后缀算符“？”。
字符组：[abc]表示正规式a | b | c。缩写字符组[a-z]表示正规式a | b | … | z。

状态转换图

在这里插入图片描述

开始状态、状态、接受状态（俩圈）、动作。

Thompson算法（正规式→有限自动机）

在这里插入图片描述

要记住“或”运算和“闭包”运算的构造形式。

NFA&DFA

NFA：不确定的有限自动机
DFA：确定的有限自动机
理解：NFA有可能会出现一个输入对应一个节点后方的多个箭头，而DFA不会出现这种情况。

子集构造法（NFA→DFA）

在这里插入图片描述

运算	描述
$\varepsilon-closure(s)$	从NFA状态s出发，只用 $\varepsilon$ 转换能达到的NFA状态集合; $\varepsilon-closure$ 均包含自身（常用于没有ε转换的题目中）
$\varepsilon-closure(T)$	T是一个集合，包含多个状态（节点）
$m o v e (T, a)$	从状态集合T中的状态（节点）开始，经过a转换能够到达的状态集合
⭐ $\varepsilon-closure(move(A, a))$	从A状态开始经过一步a转换，再可以经过若干次ε转换

子集构造法：

DFA的一个状态是NFA的一个状态集合。

算法：

在这里插入图片描述

	输入符号	输入符号
	a	b
A	B	C
B	B	D
C	B	C
D	B	C

初始状态： $A=\varepsilon-closure(s_0)=\{0, 1, 2, 4, 7\}$
其他“新”状态： $B=\varepsilon-closure(move(A, a))=\varepsilon-closure(\{3, 8\})=\{1,2,3,4,6,7,8\}$ , $C=\varepsilon-closure(move(A, b))=\varepsilon-closure(\{5\})=\{1,2,3,4,5,6,7\}$ , $D=\varepsilon-closure(move(B, b))=\varepsilon-closure(\{5, 9\})=\{1,2,4,5,6,7,9\}$ .
其他状态：e.g. $\varepsilon-closure(move(B, a))=\varepsilon-closure(\{3, 8\})=\{1,2,3,4,6,7,8\}=B$ .
确定DFA的接受状态：在DFA中，一个状态（或更具体地说，一个状态的子集）被认为是接受状态，如果它包含NFA的一个或多个接受状态。换句话说，如果DFA的某个状态子集包含NFA的至少一个接受状态，那么该DFA状态就是接受状态。

在这里插入图片描述

子集构造法不一定得到最简单的DFA：

在这里插入图片描述

练习：用子集构造法将下面的NFA转换成DFA。

在这里插入图片描述

解：

$A=\varepsilon-closure(s_0)=\{0\}$ （只包含自身）

$B=\varepsilon-closure(move(A, a))=\varepsilon-closure(\{0, 1\})=\{0, 1\}$

$\varepsilon-closure(move(A, b))=\varepsilon-closure(\{0\})=\{0\}=A$

$\varepsilon-closure(move(B, a))=\varepsilon-closure(\{0,1\})=\{0,1\}=B$

$C=\varepsilon-closure(move(B, b))=\varepsilon-closure(\{0,2\})=\{0,2\}$

$\varepsilon-closure(move(C, a))=\varepsilon-closure(\{0，1\})=\{0，1\}=B$

$\varepsilon-closure(move(C, b))=\varepsilon-closure(\{0\})=\{0\}=A$

	输入符号	输入符号
	a	b
A	B	A
B	B	C
C	B	A

DFA的化简

如果转换函数并非全函数，化简前可以引入死状态（“dead” state）变换成全函数。

在这里插入图片描述

可区别状态&不可区别状态：

可区别状态：对该DFA，分别从s和t出发，输入w，一个最终停留在某个接受状态，另一个停留在某个非接受状态。
不可区别状态：找不到任何输入（串）w来区别两个状态。

极小化DFA状态数算法思路：

初始，划分成两个子集：接受状态子集和非接受状态子集。
检查每个子集，如果还可以划分，则继续划分，直到没有任何一个子集可划分为止。
若要G的两个状态s和t在同一子集中，当且仅当对任意输入符号a，s和t的a转换是到同一子集中。

在这里插入图片描述

上述例子中， $move(\{A,B,C\},b)=\{C,D\}$ ，C和D可区分（一个在接受状态，一个在非接受状态），所以 ${A,B,C\}$ 可拆。

原本的状态转换表：

	输入符号	输入符号
	a	b
A	B	C
B	B	D
C	B	C
D	B	C

练习：将下面的DFA状态数最小化

	a	b
S0	S5	S2
S1	S6	S2
S2	S0	S4
S3	S3	S5
S4	S6	S2
S5	S3	S0
S6	S3	S1

划分结果： ${S_0, S_1\}, \{S_2\}, \{S_3\}, \{S_4\}, \{S_5, S_6\}$ .

第三章语法分析

上下文无关文法

上下文无关文法G是四元组 $V_T,V_N,S,P)$ ，分别是：终结符集合、非终结符集合、开始符号、产生式集合。

在这里插入图片描述

最左推导、最右推导（最右推导又称规范推导）

分析树：（这是 $- (i d + i d)$ 的推导分析树）

在这里插入图片描述

消除二义性

在这里插入图片描述

e.g. if-then-else

正确语义：每个else和它左边最接近的还没配对的then相配。

在这里插入图片描述

消除左递归

左递归：给定文法G，若有 $A→\alpha→^*A\gamma(\gamma\ne\varepsilon)$ ，则称非终结符A是左递归的。（→*是“经过任意步推导”的意思）

由形式为 $A→A\alpha$ 的产生式引起的左递归称为直接左递归。

⭐【背】 $A→A\alpha_1|A\alpha_2|\beta_1|\beta_2$ 消除左递归：

$A→\beta_1A'|\beta_2A'$

$A'→\alpha_1A'|\alpha_2A'|\varepsilon$

e.g. 消除下列算术表达文法的左递归：

$E \to E + T ∣ T$

$T \to T * F ∣ F$

$F \to (E) ∣ i d$

解：消除E和T的直接左递归：

$E \to T E^{'}$

$E'→+TE'|\varepsilon$

$T \to F T^{'}$

$T'→*FT'|\varepsilon$

$F \to (E) ∣ i d$

对于非直接左递归的：1.变成直接左递归；2.消除直接左递归

e.g. 文法：

$S \to A a ∣ b$

$A→Sd|\varepsilon$

解：1. $S \to A a ∣ b$ $A→Aad|bd|\varepsilon$

2. $S \to A a ∣ b$ $A \to b d A^{'} ∣ A^{'}$ $A'→adA'|\varepsilon$

无用符号和无用产生式：

无用符号：X至少出现在一个句子的推导中，则说X是有用的，否则称X为无用符号。（推导：把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。）
无用产生式：如果一个产生式左部或右部含有无用符号，则此产生式称为无用产生式。

在这里插入图片描述

提左因子

$A→\alpha\beta_1|\alpha\beta_2$

左因子：α

提左因子：

$A→\alpha A'$

$A'→\beta_1|\beta_2$

形式语言的Chomsky分类

【背】

0型文法：短语文法
1型文法：上下文有关文法
2型文法：上下文无关文法
3型文法：正规文法（正规式）

0型文法描述能力最强，3型文法描述能力最弱。

FIRST和FOLLOW集合

FIRST-第一个 FOLLOW-跟着的

本部分举例用的文法如下：

$E \to T E^{'}$

$E'→+TE'|\varepsilon$

$T \to F T^{'}$

$T'→*FT'|\varepsilon$

$F \to (E) ∣ i d$

FIRST(X)计算：

X是终结符→FIRST(X)={X}（终结符：类似于id这样的）
X→ε是产生式→ε∈FIRST(X)
$X→Y_1Y_2...Y_k$ 是产生式，则对某个i，若 $\varepsilon \in FIRST(Y_1)...FIRST(Y_{i-1})$ ，而 $a\in FIRST(Y_i)$ ，则 $a\in FIRST(X)$ 。若 $\varepsilon \in FIRST(Y_1)...FIRST(Y_k)$ ，则 $\varepsilon \in FIRST(X)$ 。

对上述第三条规则的理解：前面若干个“空”，就跳过，到没有空的那儿开始看。

求上述例子的FIRST集合：

FIRST(E)=FIRST(TE’)=FIRST(T)=FIRST(FT’)=FIRST(F)={(, id}.

FIRST(E’)=FIRST(+TE’)∪FIRST(ε)={+, ε}.

FIRST(T’)=FIRST(*FT’)∪FIRST(ε)={*, ε}.

FOLLOW(A)计算：

A是开始符号→$∈FOLLOW(A)
若有产生式 $B→\alpha A \beta$ ，则FIRST(β)中除ε以外的一切符号都属于FOLLOW(A).（β的开头都跟在A的后面）
⭐若有产生式 $B→\alpha A$ ，或产生式 $B→\alpha A \beta$ 而 $\varepsilon \in FIRST(\beta)$ ，则 $FOLLOW(B)\subseteq FOLLOW(A)$ ，即FOLLOW(B)中的一切符号都要放入FOLLOW(A)中。（理解：A后面没东西了→B后面的就是A后面的）（⭐这里要注意 $B→\alpha A$ 中B和A的顺序问题，B在左，A在右）

对于上述的第二条和第三条规则，在求解的时候，应该着重看产生式的右部。

FOLLOW集合里不会出现ε。

求上述例子的FOLLOW集合：

E是开始符号→$∈FOLLOW(E)

FOLLOW(E)={$, )}

FOLLOW(E’)=FOLLOW(E)={$, )}

FOLLOW(T)=(FIRST(E’)-{ε})∪FOLLOW(E’)={+, $, )}（因为** $\varepsilon \in FIRST(E')$ ，所以要并上第二部分的“FOLLOW(E’)”）（注意第二条规则里的“除ε以外”）**

FOLLOW(T’)=FOLLOW(T)={+, $, )}

FOLLOW(F)=(FIRST(T’)-{ε})∪FOLLOW(T)∪FOLLOW(T’)={*, +, $, )}

LL(1)文法

含义：从左到右分析，最左推导，每步向前搜索一个输入符号。

定义：

任何两个产生式 $A→\alpha | \beta$ 都满足下列条件：（这里的“两个产生式”是指$A→\alpha $和$ A→\beta $）

FIRST(α)∩FIRST(β)=Ф
若β经过若干次推导可得ε，那么FIRST(α)∩FOLLOW(A)=Ф

理解：两个产生式的FIRST集合不相交，如果β能推到空，就用FOLLOW(A)代替FIRST(β)。

LL(1)文法的性质：

没有公共左因子（显然）
不是二义的
不含左递归

不符合LL(1)文法定义的文法举例：

$S \to A B$

$A→ab|\varepsilon$

$B \to a C$

$C→\dots$

上述文法中， $a\in FIRST(ab)\cap FOLLOW(A)$ .

递归下降的预测分析

属于自上而下分析。

在这里插入图片描述

递归下降预测分析举例：

在这里插入图片描述

非递归的预测分析（LL(1)分析）

在这里插入图片描述

栈	输入	动作
$…	…$	…

栈顶为$且输入只剩$时，分析成功。
栈顶与输入的头部相等且不为$时，弹出栈顶，输入指针后移。
栈顶是终结符但不是输入头部的那个终结符，则报错。→调用错误恢复例程
栈顶是非终结符（一般是那些大写字母）时，访问预测分析表M[X, a]。如果表里有产生式，则用产生式右部代替栈顶（逆序压栈）。“动作”栏中打印“输出【产生式】”。如果M[X, a]是空白单元格，则调用错误恢复例程。

给定预测分析表，写接受输入某某某的动作

在这里插入图片描述

接受输入id*id+id的动作：

在这里插入图片描述

在非递归的预测分析中，已经扫描过的符号加上栈中的文法符号（从栈顶到栈底），构成最左推导的句型。

（句型：一个文法从开始符号能推出的所有串；句子：只含终结符的句型）

构造预测分析表

步骤：对文法的每个产生式A→α，执行下述操作：

对FIRST(α)中的每个终结符a，把【产生式】A→α加入M[A, a]。（注意区分里面的α和a）
如果ε在FIRST(α)中，对FOLLOW(A)的每个终结符b（包括$），把A→α加入M[A, b]

e.g. 对于文法：

$E \to T E^{'}$

$E'→+TE'|\varepsilon$

$T \to F T^{'}$

$T'→*FT'|\varepsilon$

$F \to (E) ∣ i d$

在这里插入图片描述

构造预测分析表：

在这里插入图片描述

紧急方式的错误恢复

发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止。

同步记号选择的一些提示（略）

自下而上分析（移进-归约分析）

自下而上分析

编译器常用的移进-归约分析：LR分析（L：从左向右扫描；R：构造最右推导的逆）

在这里插入图片描述

注意：推导箭头下面的rm在最右推导时必须要写。

最右（左）推导的逆过程是最左（右）归约；最左归约也称规范归约。

句柄：如果一个句型由最右推导得到，则句型的句柄是和某产生式右部匹配的子串。

在这里插入图片描述

上述例子中，绿色标出的就是“句柄”。

句柄的右边仅含终结符。

移进-归约分析器

分析器基本动作：

移进：把下一个输入符号移进栈
归约：把栈顶的句柄归约为非终结符
接受：宣告分析成功
报错：发现错误，调用错误恢复例程

用栈实现移进-归约分析：

$E \to E + E ∣ E * E ∣ (E) ∣ i d$

在这里插入图片描述

“归约”只在栈中进行。

移进-归约冲突&归约-归约冲突

移进-归约冲突举例：

stmt → if expr then stmt | if expr then stmt else stmt | other

栈	输入
… if expr then stmt	else … $

无法确定此时应当移进还是归约，故产生移进-归约冲突。（无法确定 if expr then stmt 是否为句柄）

归约-归约冲突举例：

在这里插入图片描述

不知道应该归约成过程调用还是数组，所以产生了归约-归约冲突。

⭐有关YACC处理移进归约冲突和归约归约冲突：

YACC在处理语法冲突的时候，默认情况下，对于移进归约冲突，优先于移进。
YACC在处理语法冲突的时候，默认情况下，对于归约归约冲突，优先于先出现的产生式。

（往年考过）合并同心项目集有可能产生新的归约归约冲突。

Yacc解决分析动作冲突时，如果定义了终结符的优先级和结合性，则如果产生移进归约冲突时：

如果归约的产生式的优先级和移进的终结符的优先级相同，且产生式左结合，则进行归约。
Yacc中产生式的优先级与产生式中处在最右端的终结符的优先级相同。
如果归约的产生式的优先级高于移进的终结符的优先级，则进行归约。

LR分析器

⭐包含关系：

在这里插入图片描述

简单的LR方法（简称SLR）
规范的LR方法
向前看的LR方法（简称LALR）

所有能够用LL分析法（预测分析法）分析的文法，都能够用LR分析法分析。

它们的差别在于构造action-goto表的方法不同

在这里插入图片描述

输入缓冲区；状态栈

LR分析算法：根据当前的输入和当前的栈顶的状态来查action表（移进/归约/出错/接受）：移进-把当前输入放入栈中，再把si中的i（状态）放进去；出错/接受-结束分析或错误处理；归约-按照（ri中的）第i条产生式归约，把产生式右部的所有符号以及它们上面的状态都出栈，把产生式左部的非终结符移到栈里，根据这个非终结符以及它下面的状态查转移表，把状态值压入栈中。

在这里插入图片描述

活前缀：右句型的前缀，该前缀不超过最右句柄的右端。

在这里插入图片描述

构造SLR分析表⭐

构造识别活前缀的DFA

文法的**LR(0)**项目：在右部的某个地方加点的产生式：

在这里插入图片描述

加点的目的是用来表示分析过程中的状态。

点前面的相当于已经有了的，点后面相当于期望得到的。

核心项目和非核心项目：

核心项目：包括初始项目 $S^{'} \to S$ 和所有那些点不在左端的项目。
非核心项目：除了 $S^{'} \to S$ 以外，所有点在左端的项目。

闭包函数closure：

如果I是文法G的一个项目集，那么 $c l os u re (I)$ 是用下面两条规则从I构造的项目集：

初始时，I的每个项目都加入 $c l os u re (I)$ 。
如果 $A→\alpha ·B\beta$ 在 $c l os u re (I)$ 中，且 $B→\gamma$ 是产生式，那么如果项目 $B→·\gamma$ 还不在 $c l os u re (I)$ 中的话，则把它加入。运用这条规则，直到没有更多的项目可以加入 $c l os u re (I)$ 为止。【点后面是非终结符的需要进行此操作】

e.g. 【构造SLR分析表】考虑下述文法：

$E \to E + T ∣ T$

$T \to T * F ∣ F$

$F \to (E) ∣ i d$

拓广文法：添加 $E^{'} \to E$

$I_0$ ：在上面的所有产生式箭头右边的头部加点：

$E^{'} \to \cdot E$

$E \to \cdot E + T$

$E \to \cdot T$

$T \to \cdot T * F$

$T \to \cdot F$

$F \to \cdot (E)$

$F \to \cdot i d$

$I_1=goto(I_0, E)$ , $I_2=goto(I_0, T)$ , $I_3=goto(I_0, F)$ , $I_4=goto(I_0, ()$ , … …

特别需要注意的是 $I_4$ 的求法：

先有 $F \to (\cdot E)$

⭐⭐⭐【求闭包】点后面是E，要**【根据产生式】**把E产生什么什么的放进来：

$E \to \cdot E + T$

$E \to \cdot T$

点后面是T，要把T产生什么什么的放进来：

$T \to \cdot T * F$

$T \to \cdot F$

点后面是F，要把F产生什么什么的放进来：

$F \to \cdot (E)$

$F \to \cdot i d$

所以 $I_4$ 中有7条产生式。

对于 $I_6=goto(I_1, +)$ ：（ $I_1$ ： $E^{'} \to \cdot E$ , $E \to E \cdot + T$ ）

先有： $E \to E + \cdot T$

因为产生式中有T产生什么什么的，所以要补充：

$T \to \cdot T * F$

$T \to \cdot F$

点后面是F，要把F产生什么什么的放进来：

$F \to \cdot (E)$

$F \to \cdot i d$

所以 $I_6$ 有5条产生式。

参考过程：（较为潦草，但条理是清晰的）

在这里插入图片描述

上图是接受活前缀的DFA的转换图

根据LR(0)项目集规范族和识别活前缀的DFA构造action-goto表

项目集规范族：可理解为上面例子里求的那些 $I_i$ 。

⭐⭐⭐项目集中的项目分四类：（前面的序号是做题时的推荐顺序）

①接受项目**（开始符号’→开始符号·）**：[ $S^{'} \to S \cdot$ ] $action[i, $] = acc$
③移进项目**（点后为终结符）**：[ $A→\alpha ·a\beta$ ] $a c t i o n [i, a] = s j$
④归约项目**（点后为空）：[ $A→\alpha ·$ ] $a c t i o n [i, b] = r j$ , $b\in FOLLOW(A)$ ⭐（这里的“j”表示：按哪条产生式归约）**
②待归约项目**（点后为非终结符，或者说goto(I…, E)中的E为非终结符）**：[ $A→\alpha ·B\beta$ ] $g o t o [i, B] = j$ （仅根据这一条规则写转移表）

构造action-goto表时，要分析每个状态中的每一条产生式。

状态	动作	动作	动作	动作	动作	动作	转移	转移	转移
	id	+	*	(	)	$	E	T	F
0	A		B				C	D	E
1		F				G
2		H	I		J	K
3
…

在这里插入图片描述

对于 $I_0$ ：

$E^{'} \to \cdot E$
$E \to \cdot E + T$
$E \to \cdot T$
$T \to \cdot T * F$
$T \to \cdot F$
$F \to \cdot (E)$
$F \to \cdot i d$

其中的第一、第二条产生式符合“待归约项目”的要求，输入E后转移至状态1（ $I_1$ ），所以在转移表0-E处写1。

其中的第三、第四条产生式符合“待归约项目”的要求，输入T后转移至状态2（ $I_2$ ），所以在转移表0-T处写2。

其中的第五条产生式符合“待归约项目”的要求，输入F后转移至状态3（ $I_3$ ），所以在转移表0-F处写3。

第六条 $F \to \cdot (E)$ 点后是左括号，是终结符，符合移进项目的定义，所以动作表中0-(处写s4。

同理，第七条 $F \to \cdot i d$ 点后是id，是终结符，符合移进项目的定义，所以动作表中0-id处写s5。

对于状态1， $E^{'} \to E \cdot$ 符合接受项目的定义，在1-$处写acc。

$I_1$ 中的 $E \to E \cdot + T$ 点后为终结符，符合移进项目的定义，在1-+处写s6。

对于状态2， $E \to T \cdot$ 符合归约项目（点后为空）的定义，因为$FOLLOW(E)={+, ), $}$，所以2-+, 2-), 2-$三个位置都应该填r2。

（其余填表过程略）

使用SLR分析表的LR分析是SLR分析，能够构造出无冲突的SLR分析表的文法是SLR文法。
SLR分析表中如果出现动作冲突（移进-归约冲突，归约-归约冲突），则文法就不是SLR的。
SLR文法都不是二义的，但是它描述能力有限，有些非二义的文法不能用SLR分析。

解决方法：规范LR分析（LR(1)分析）

构造规范的LR分析表（LR(1)）

LR(1)项目：重新定义项目，让它带上搜索符：

$[A→\alpha ·\beta, a]$

搜索符是在字串 $\alpha \beta$ 所在的右句型中直接跟在 $\beta$ 后面的终结符。
搜索符在 $\beta$ 不为 $\varepsilon$ 的情况下是没什么用处的，但当 $\beta$ 为 $\varepsilon$ 时，它决定了何时将 $\alpha \beta$ 归约为A。
LR(1)中的1实际上指搜索符的长度。

构造规范LR分析表步骤：

拓广文法并为产生式编号
构造LR(1)项目集规范族（顺便计算所有goto函数）
构造识别活前缀的DFA
根据LR(1)项目集规范族和识别活前缀的DFA构造action-goto表

e.g.

在这里插入图片描述

先拓广文法并编号：

$S^{'} \to S$
$S \to BB$
$B \to b B$
$B \to a$

构造项目集规范族：

初始项目集：${[S’→·S, $]}$
⭐计算$closure({[S’→·S, $]}) $得到第一个项目集$ I_0 $。（闭包函数定义第二条：如果$ A→\alpha ·B\beta $在$ closure(I) $中，且$ B→\gamma $是 * * 产生式 * * ，那么如果项目$ B→·\gamma $还不在$ closure(I) $中的话，则把它加入。运用这条规则，直到没有更多的项目可以加入$ closure(I)$为止。【点后面是非终结符的需要进行此操作】）
计算 $goto(I_0, X)$ 得到其他项目集（状态）
同理，可以用 $goto(I_i, X)$ 计算从任意状态 $I_i$ 开始，向栈中压入一个文法符号X所得到的状态（项目集），直到没有新的状态（项目集）产生为止。

在这里插入图片描述

画出识别活前缀的DFA：

在这里插入图片描述

构造action-goto表：

项目集中的项目分四类：

接受项目$[S’→S·, $] $：$ action[i, $]=acc$
移进项目 $A→\alpha·a\beta, b$ ： $a c t i o n [i, a] = s j$
归约项目 $A→\alpha·, b$ ： $a c t i o n [i, b] = r j$
待归约项目 $A→\alpha·B\beta$ ： $g o t o [i, B] = j$

在这里插入图片描述

规范LR分析法的问题：状态数庞大，构造难度大。

缓解的办法：LALR分析法

构造LALR分析表

LALR: LookAhead LR

LALR的分析能力介于SLR和规范LR之间。

实际的编译器经常使用LALR分析法。

LALR分析就是在LR(1)的基础上合并同心项目集，合并同心项目集后的项目集族叫做LALR(1)项目集族。

在这里插入图片描述

其中， $I_4$ 与 $I_7$ 仅搜索符不同，可以将它们视为同心项目集。 $I_3$ 和 $I_6$ 、 $I_8$ 和 $I_9$ 同理，均为同心项目集。

合并同心项目集后的结果：

在这里插入图片描述

合并同心项目集可能会引起冲突，不会引起新的移进归约冲突，但可能产生新的归约归约冲突。

第四章语法制导的翻译

语法制导定义

一个语法制导定义包括：基础文法（上下文无关文法）、产生式对应的语义规则、文法符号的属性。（不包含属性依赖图）

语法制导定义：上下文无关文法的扩展，每个文法符号多了一组属性，每个产生式多了一组语义规则。（语法制导的定义是带属性和语义规则的上下文无关文法；每个文法符号都有一组属性，无论终结符还是非终结符）

在语法制导定义中，每个文法符号有一组属性，每个文法产生式 $A→\alpha$ 有一组形式为 $b=f(c_1, c_2, \dots, c_k)$ 的语义规则，其中f是函数，b和 $c_1, \dots, c_k$ 是该产生式的文法符号的属性：

综合属性：如果b是A（产生式左部）的属性， $c_1, \dots, c_k$ 是产生式右部文法符号的属性或A的其他属性，那么b称为A的综合属性。
继承属性：如果b是产生式右部某个文法符号X的属性， $c_1, \dots, c_k$ 是A的属性或右部文法符号的属性，那么b称为X的继承属性。

注：综合属性和继承属性没有重合。

综合属性是计算 $A→\alpha$ 中A的属性；继承属性是计算 $A→\alpha$ 右部α里的属性。

e.g. 简单计算器的语法制导定义：

产生式	语义规则
$L \to E$ n	$p r in t (E . v a l)$
$E→E_1+T$	$E.val=E_1.val+T.val$
$E \to T$	$E . v a l = T . v a l$
$T→T_1*F$	$T.val=T_1.val×F.val$
$T \to F$	$T . v a l = F . v a l$
$F \to (E)$	$F . v a l = E . v a l$
$F \to$ digit	$F . v a l =$ digit $. l e xv a l$

综合属性

如果把上述表格的第一行的语义规则改写为： $L . d u mm y = p r in t (E . v a l)$ （L的虚拟综合属性dummy），则这里面只有综合属性，符合S属性定义。（S属性定义：仅仅使用综合属性的语法制导定义称为S属性定义）

注释分析树：结点的属性值都标注出来的分析树。

计算结点属性值的过程叫做注释（加注）或修饰。

e.g. $8 + 5 * 2 n$ .

在这里插入图片描述

注释后：

在这里插入图片描述

分析树各结点属性的计算可以自下而上地完成。

继承属性

编程语言的一些构造的属性依赖于它们所在的上下文，此时使用继承属性比较方便。

e.g.

在这里插入图片描述

属性依赖图

对上述注释分析树构造属性依赖图：

在这里插入图片描述

拓扑排序：有向无环图结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。（不能出现逆着箭头走的情况）

下面图中的1-10是一种情况，有的结点的编号可以变顺序。

在这里插入图片描述

属性计算次序

如何确定属性计算次序：

构造输入的分析树
构造属性依赖图
对结点进行拓扑排序
按拓扑排序的次序计算属性

以上是一种语法制导翻译概念上的实现方法；这种方法叫做分析树方法。

S属性定义的自下而上计算

抽象语法树是分析树的浓缩表示：算符和关键字是作为内部结点，单非产生式**（右部只有一个非终结符的产生式）**链可能消失。

抽象语法树是一种中间表示，允许把翻译从分析中分离，形成先分析后翻译的方式。

e.g. （红框中均为“算符作为内部结点”）

在这里插入图片描述

抽象语法树的数据结构：

算符结点：算符域（结点标记），2个运算对象域（存放指向运算对象的指针）
基本运算对象结点：运算对象类别域，运算对象的值

语义规则中的函数：（它们都返回结点指针）

$mk L e a f (i d, e n t ry)$ ：建立标记为id的标识符结点；entry：符号表中该标识符条目的指针。
$mk L e a f (n u m, v a l)$ ：建立标记为num的整数结点；结点另有一个域，其值为val，它是该整数的值。
$mk L e a f (o p, l e f t, r i g h t)$ ：算符结点，其余两个指针是该结点的左右子树的指针。

e.g.

在这里插入图片描述

上图中体现出了三种不同的"make leaf"结点。

在这里插入图片描述

可以通过修改LR分析器的栈使之在分析的同时计算属性。

将LR分析器增加一个域来保存综合属性值：

在这里插入图片描述

翻译器面临 $8 + 5 * 2 n$ 时的动作：

在这里插入图片描述

L属性定义的自上而下计算

L属性定义

L属性定义：如果每个产生式 $A→X_1X_2\dots X_n$ 的每条语义规则计算的属性要么是A的综合属性；或者计算的是 $X_j$ 的继承属性（ $1\le j\le n$ ），它仅依赖：

该产生式中 $X_j$ 左边符号 $X_1, X_2, \dots ,X_{j-1}$ 的属性
A的继承属性

S属性定义属于L属性定义。

翻译方案⭐

语法制导翻译方案和语法制导定义的不同之处：语义动作放在括号{}里。

e.g. A→α {action} β

可以把语义动作想象成一个文法符号，在分析过程中对该符号进行推导或归约的时候，就是该语义动作执行的时候。

A→α M β

e.g. 把有加和减的中缀表达式翻译成后缀表达式：如果输入是8 + 5 - 2，则输出是8 5 + 2 -。

翻译方案：

在这里插入图片描述

只有综合属性时，只要将动作放在对应产生式右部末端即可得到翻译方案。

如果有继承属性，则对于L属性定义，总能构造满足下述三条限制的翻译方案：

产生式右部符号的继承属性必须在先于这个符号的动作中计算。
一个动作不能引用该动作右边符号的综合属性。
左部非终结符的综合属性只能在它所引用的所有属性都计算完成后才能计算。计算该属性的动作通常放在产生式右部的末端。

e.g. 数学排版语言EQN

在这里插入图片描述

上述L属性定义定义编排单元大小和高度。
继承属性B.ps表示点的大小，它会影响公式高度。
综合属性text.h，B.ht和S.ht表示高度。

（粗略理解综合属性&继承属性）表达式左边的对应综合属性，右边的对应继承属性。

在这里插入图片描述

抽象语法树：

在这里插入图片描述

第五章类型检查

执行错误和安全语言

执行错误：程序运行时出现的错误。

程序运行时的执行错误分成两类：

会被捕获的错误(trapped error)
不会被捕获的错误(untrapped error)

良行为的程序：一个程序的运行不可能引起不会被捕获的错误，则称它是良行为的。

安全语言：所有合法程序都是良行为的语言。

禁止错误：

全部不会被捕获的错误
一部分会被捕获的错误

为语言设计类型系统的目标是排除禁止错误。

C语言不是类型可靠的语言。（Java语言是类型可靠的）

类型化语言和类型系统

变量的类型：变量在程序执行期间的取值范围。

类型化的语言：若语言的规范为其每种运算都定义了各运算对象和运算结果所允许的类型，则该语言称为类型化语言。

显式类型化语言：在一种语言中，若函数和变量的类型必须显式声明，则该语言为显式类型化语言。（e.g. Java, C++）
隐式类型化语言：类型声明不是必不可少的语言。

在类型化语言中，类型系统由一组定型规则构成。

类型检查：

根据定型规则来确定程序中各语法构造的类型。
类型检查的目的是拒绝那些有类型错误的程序。

能够通过类型检查的程序称为良类型的程序。

如果良类型程序一定是良行为的，则称该语言是类型可靠的。类型可靠的语言一定是安全语言。

类型系统主要用来说明程序设计语言的定型规则，它独立于类型检查算法。

e.g. 有关自然数的逻辑系统：

自然数表达式： $a + b$ , 3
合式公式： $a + b = 3$ , $KaTeX parse error: Undefined control sequence: \and at position 6: (d=3)\̲a̲n̲d̲ ̲(c<10)$
推理规则： $\frac{a<b, b<c}{a<c}$

e.g. 类型系统：（可能考小题）

类型表达式：int→int
（在逻辑学中，“⊢”表示推导出、推理出）断言： ${x:int\}⊢x+3:int$
定型规则： $\frac{\Tau ⊢ M:int, \Tau ⊢ N:int}{\Tau ⊢ M+N:int}$

断言有三种具体形式：

环境断言： $\Tau ⊢ \Diamond$
语法断言： $\Tau ⊢ nat$
定型断言： $\Tau ⊢ M:T$

推理规则：

在这里插入图片描述

类型检查和类型推断：

类型检查：用语法制导的方式，根据上下文有关的定型规则来判定程序构造是否为良类型的过程。
类型判断：类型信息不完全的情况下的定型判定问题。

类型系统：

在这里插入图片描述

下面三条分别是指针、数组和函数调用。（函数调用曾在考试中出现过）

在这里插入图片描述

类型表达式的等价

结构等价&名字等价

（常考概念辨析、分析大题）

【理解】

结构等价：把名字换成具体的类型，如果类型一样，则满足结构等价。
名字等价：名字不一样就不符合名字等价。

C语言对除记录（结构体）以外的所有类型采用结构等价，而对记录（结构体）类型采用名字等价，以避免类型表示中的环。（考试考过）

e.g. 分别在名字等价和结构等价下，下面的哪些变量具有相同的类型？

type link = ↑cell;
var next : link;last : link;p : ↑cell;q, r : ↑cell;

对于next和p：它们的名字不同，不符合名字等价，但由于link=↑cell，所以它们结构等价。

其余略。

e.g. 分别在名字等价和结构等价下，下面的哪些变量具有相同的类型？

type link = ↑cell;np = ↑cell;nqr = ↑cell;
var next : link;last : link;p : np;q : nqr;r : nqr;

对于p和q：它们的名字不同，不符合名字等价，但由于np=↑cell且nqr=↑cell，所以它们结构等价。

其余略。

记录类型

记录类型从某种意义上来说是它各域类型的积。

在这里插入图片描述

考察方向：写类型表达式

e.g. C的程序段：

typedef struct {int address;char lexeme[15];
}row;

定义类型名row代表类型表达式：

record(address: int, lexeme: array(15, char))

e.g. 假如有下列C的声明：

typedef struct {int a, b;
} CELL, *PCELL;
CELL foo[100];
PCELL bar(x, y) int x; CELL y; {...}

为变量foo和函数bar的类型写出类型表达式。

答：

foo: array(100, record(a: integer, b: integer))

bar: integer×record(a: integer, b: integer) → pointer(record(a: integer, b: integer))

类型表示中的环

在这里插入图片描述

第六章运行时存储空间的组织和管理

局部存储分配

过程

过程定义是一个声明，它的最简单形式是将一个名字和一个语句联系起来。

形式参数（形参）：出现在过程定义中的某些名字
实在参数（实参）：出现在过程调用语句中

e.g. （用于理解形参和实参，程序中主函数为max_val()传入的参数a和b是实参，max_val()定义中的参数x和y是形参）

#include <iostream>
using namespace std;int max_val(int x, int y) { // 形参if (x > y) return x;return y;
}int main() {int a = 3;int b = 2;int res = max_val(a, b); // 实参cout << res << endl;return 0;
}

名字的作用域和绑定

名字的作用域：一个声明起作用的程序部分称为该声明的作用域。（可参考“程序块”处的例子理解）

从名字到值的两步映射：

环境把名字映射到左值（存储空间），而状态把左值映射到右值（实际的值）
赋值改变状态，但不改变环境；过程调用改变环境。
如果环境将名字x映射到存储单元s，我们就说x被绑定（binding）到s

在这里插入图片描述

【补充知识】左值和右值：

左值是可寻址的变量，有持久性。
右值一般是不可寻址的常量，或在表达式求值过程中创建的无名临时变量，不具备持久性。

静态和动态概念的对应：

静态概念	动态对应
过程的定义	过程的活动
名字的声明	名字的绑定
声明的作用域	绑定的生存期

活动记录

一般的活动记录布局：

在这里插入图片描述

代码、全局变量、常量不存在活动记录中。

局部数据的布局

数据对象的存储安排有一个对齐的问题。（因对齐而引起的无用空间称为衬垫区）

按照定义的顺序存储。

e.g. 在SPARC/Solaris工作站上：（double占8字节，char占1字节，long占4字节）

在这里插入图片描述

在X86/Linux机器上：（double类型要求按照4字节对齐，并非8字节对齐）

在这里插入图片描述

程序块

程序块特点：可以嵌套，不能重叠。

程序块结构的声明作用域由最接近的嵌套作用域规则给出。

在这里插入图片描述

全局栈式存储分配

在这里插入图片描述

活动树和运行栈

e.g.

int a[11]; 
void readArray() { /∗ Reads 9 integers into a[1], …, a[9]. ∗/ int i; . . . 
}
int partition(int m, int n) { // **找到一个数i，让a[i]左边都小于a[i]，右边都大于a[i]。**/∗ Picks a separator value v, and partitions a[m..n] so that a[m..p-1] are less than v, a[p]=v, and a[p+1..n] are equal to or greatthan v. Returns p. ∗/ 
} 
void quickSort(int m, int n) { int i; if (n > m) { i = partition(m, n); quickSort(m, i-1); quickSort(i+1,n); } 
}
main() { readarray(); a[0] = -9999; a[10] = 9999; quickSort(1, 9); 
}

活动树：（程序对应活动树的深度优先遍历-DFS）

在这里插入图片描述

控制栈：当前活跃着的过程活动可以保存在一个栈中。

控制栈中当前存在的过程活动都是处在生存期内的活动。

e.g.

在这里插入图片描述

运行栈：把控制栈中的信息拓广到包括过程活动的活动记录。（活动记录栈）

在这里插入图片描述

树每向下一层，运行栈就多一层（实线分割为一层）。

调用序列⭐

过程调用和过程返回：（考过概念辨析）

过程调用序列：过程调用时执行的分配活动记录、把信息填入它的域中的代码。
过程返回序列：过程返回时执行的恢复机器状态、释放活动记录、使调用过程能够继续执行的代码。
调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中。（也就是说，过程调用序列和过程返回序列每个都是有两段代码。错误描述：“过程调用序列通常处于调用过程中，而过程返回序列通常处于被调用过程中”）

在这里插入图片描述

栈上可变长度数据

【非重点】

局部数组的大小要等到过程激活时才能确定。

悬空引用

悬空引用：引用某个已经被释放的存储单元

e.g.

int * dangle() {int j = 20;return &j; // j的存储单元在函数结束后被释放了
}int main() {int *q;q = dangle();
}

非局部名字的访问

无过程嵌套的静态作用域（C语言）
有过程嵌套的静态作用域（Pascal语言）

C语言属于无过程嵌套的语言，不需要访问链。

参数传递

值调用：传右值（对形参的任何操作不会影响调用者的实参的值）
e.g.

void process(int a, int b) {a = a + 2;b = b + 3;
}
int main() {int x = 5;int y = 8;process(x, y);printf("%d %d\n", x, y); /* 此时x和y的打印结果应为5和8，因为C语言采用值调用，被调用函数中的操作对此处的结果没有影响。*/return 0;
}

引用调用（地址调用）：传递实参的左值（对形参的任何赋值都会影响调用者的实参）
在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。
数组常采用引用调用。
换名调用
e.g.
```
procedure swap(var x, y: integer);var temp: integer;begintemp := x;x := y;y := tempend
```
当调用swap(i, a[i])时，直接“换名”（用文字替代）：
```
temp := i;
i := a[i];
a[i] := temp
```
从这里可以看出换名调用和其他方式的重要区别。第2行引用的a[i]和第3行被赋值的a[i]可能是不同的数据单元，因为i的值在第2行可能被改变了。

习题

假定使用：（a）值调用、（b）引用调用、（c）换名调用，下面的程序打印的结果是什么？

program main(input, output);
var a, b: integer;
procedure p(x, y, z: integer);beginy := y + 1;z := z + x;end;
begina := 2;b := 3;p(a + b, a, a);print a;
end.

答：

值调用时，传入函数p中的为值，因此a原来的值不改变，打印结果为a=2；

引用调用时，传入的是地址，a和b会随函数体内容改变，因此结果为：y=3, z=z+x=5+3=8, a=8；（执行p时对y和z的操作都相当于对a的操作）（把x: a+b看作一个整体）

换名调用时，y=a“=”a+1=3, z=z+x=a+a+b=3+3+3=9。

C语言函数f的定义如下：

int f(int x, int * py, int * * ppz) {* * ppz += 1; // 语句1* py += 2; // 语句2x += 3; // 语句3return x + * py + * * ppz;
}

变量a是指向b的指针，变量b是指向c的指针，c是整型变量并且当前值是4。那么执行f(c, b, a)的返回值是多少？

答：

执行语句1后，c=*b=**a=5；执行语句2后，c=*b=**a=7；执行语句3后，x=7，而c=*b=**a=7。最终返回的是7+7+7=21。

（⭐往年考过）下面的C语言程序中，函数printf的调用仅含格式控制字符串一个参数，该程序在x86/Linux系统上，经某编译器编译后，运行时输出三个整数。试从运行环境和printf的实现来分析，为什么此程序会有三个整数输出。

int main() {printf("%d, %d, %d\n");return 0;
}

答：

C语言编译器不做实参、形参个数、类型一致性检查，因此printf函数并不知道究竟调用者提供了多少个参数，它只根据第一个参数格式控制串的要求取参数，而C语言编译器的实现保证了被调用函数能准确取到第一个实参。需要取其他参数的时候编译器会按第一个参数的要求在栈上按顺序取得，而不管该位置是否是真正的参数。

在这里插入图片描述

【附往年考试真题】下面这段C语言程序，在gcc下编译运行的结果是什么？

#include <stdio.h>
void main() {printf("%d,%d,%d,%d\n");
}

答案：输出由逗号分隔的4个十进制数和换行。

第七章中间代码生成

核心考点：给定程序，写出翻译方案（三地址码）。

中间语言

后缀表示

如果E是形式为 $E_1 op E_2$ 的表达式，那么E的后缀表示是 $E_1' E_2' op$ ，其中 $E_1'$ 和 $E_2'$ 分别是 $E_1$ 和 $E_2$ 的后缀表示。

e.g.

$8 - 4 + 2$ 的后缀表示是 $8\ 4-2+$ ，而 $8 - (4 + 2)$ 的后缀表示是 $8\ 4\ 2 + -$ .

对于单目运算符： $op\ E$ →后缀表达式→ $E_{后缀表示}\ op$ .

后缀表示不需要括号。后缀表示便于计算机处理。

图形表示（语法树、有向无环图DAG）

e.g. a=(-b+c*d)+c*d的图形表示：

在这里插入图片描述

只需后序遍历抽象语法树，即可得到后缀表示。

构造赋值语句语法树的语法制导定义：

在这里插入图片描述

第一行构建的是树中的根节点：assign。

uminus: 取相反数。

三地址代码

一般形式： $x=y\ op\ z$ .

x, y, z表示名字、常数或临时变量。
op表示运算符。

一条三地址码只有一个运算符。

e.g. 表达式 $x + y * z$ 翻译成的三地址语句序列是：

$t_1=y*z$

$t_2=x+t_1$

（使用临时变量 $t_1$ 等保存中间结果）

在这里插入图片描述

常用的三地址语句：（要记，考试会考，但卷面上不给）

在这里插入图片描述

三地址指令是中间代码的抽象表示。在编译器中，三地址指令可以用记录实现。

【习题】写出下列程序的三地址代码：

while (a < b) {if (c < d) x = y + z;
}

答：

在这里插入图片描述

（上面的分析图考试时可以不画）

在这里插入图片描述

最好将其中的S.begin, B.true, B1.true, S.next替换成L1, L2, L3, Lnext。

静态单赋值形式(SSA)

两个特点：

SSA中所有复制指令都是对不同变量的赋值。
Φ函数：用于解决分支语句。（对于if语句来说，程序走“then”分支和走“else”分支时，变量名不同→用Φ函数解决）

第一个特点：

在这里插入图片描述

第二个特点：

e.g.

if (flag) x1 = -1; else x2 = 1;
x3 = Φ(x1, x2);

如果控制流通过条件为真的部分，则 $\Phi (x_1, x_2)$ 的值是 $x_1$ ，如果控制流通过条件为假的部分，则 $\Phi (x_1, x_2)$ 的值是 $x_2$ 。

$\Phi (x_1, x_2)$ 返回它某个变元的值，取决于到达 $\Phi (x_1, x_2)$ 时所通过的控制流路径。

【习题】把算术表达式 $- (a + b) * (c + d) + (a + b + c)$ 翻译成：

语法树：

在这里插入图片描述

有向无环图：

在这里插入图片描述

后缀表示：a b + uminus c d + * a b + c + +
三地址代码：（两种写法，分别根据语法树和有向无环图写）

①

t1=a+b

t2=-t1

t3=c+d

t4=t2*t3

t5=a+b

t6=t5+c

t7=t4+t6

②

t1=a+b

t2=-t1

t3=c+d

t4=t2*t3

t5=t1+c

t6=t4+t5

声明语句

在分析过程或程序块的声明序列时，为局部名字建立符号表条目，并为它分配存储单元。（分配一个“偏移量”）

这样，符号表包含各名字的类型和分配给它们的存储单元的相对地址等信息。（相对地址是对静态数据区基址的偏移或是对活动记录中某个基址的偏移）

这部分的讨论中忽略数据对象的对齐等问题。

过程中的声明

offset的初值可能不为0。

在这里插入图片描述

S: 可执行语句

P → D S: 语言的程序→声明+语句

花括号中涉及的对象：

offset
X.type
X.width
enter(name, type, offset)
array()
pointer()

赋值语句

符号表中的名字

介绍中间语言时，为直观，让名字直接出现在三地址码中，实际上应该把名字理解为它们在符号表中位置的指针。

编译器在处理名字时，需要在符号表中查找其定义，获得其属性，然后在生成的三地址码中使用它在符号表中位置的指针。

为赋值语句产生三地址代码的翻译方案：

在这里插入图片描述

类型转换

e.g. 假定x和y的类型是real，i和j的类型是integer，对于输入：

$x = y + i * j$

输出的三地址指令序列是：

在这里插入图片描述

产生式 $E→E_1+E_2$ 的完整语义动作：

E.place=newTemp();
if(E1.type==integer)&&(E2.type==integer)beginemit(E.place,'=',E1.place,'int+',E2.place);E.type=integer;
end
else if(E1.type==real)&&(E2.type==real)beginemit(E.place,'=',E1.place,'real+',E2.place);E.type=real;
end
else if(E1.type==integer)&&(E2.type==real)beginu=newTemp();emit(u,'=','inttoreal',E1.place);emit(E.place,'=',u,'real+',u);E.type=real;
end
else if(E1.type==real)&&(E2.type==integer)beginu=newTemp();emit(u,'=','inttoreal',E2.place);emit(E.place,'=',E1.place,'real+',u);E.type=real;
end
elseE.type=type_error