编译原理 - Max Wang's blog

考试说明：

chapter 7.7-7.9、chapter 8、chapter 9.5的display表部分、chapter 9.6、chapter 10、chapter 11.3-11.5均不考，其他部分都有机会考，特别是标注了重点难点的部分。

考试题型就是选择、判断、填空、简答、分析计算等等

引论

程序设计语言

机器语言：0、1代码构成
汇编语言：助记符

上二者更接近计算机硬件指令系统的工作

高级语言：在表示方法上更接近待解问题的表示方法
- 如定义数据、描述运算、控制流程、传输数据
- C、Fortran, Pascal, Java, SQL，etc。
命令语言：控制系统的工作——以功能封装为特征
- 如UNIX上的shell

练习：

高级语言和汇编语言有什么差别？
命令语言是什么，举一个例子？
命令语言是高级语言的一种吗？

程序设计语言的翻译

翻译程序（Translator）
将源程序翻译为等价的目标程序
解释程序（Interpreter）
一边解释一边执行的翻译程序
以上的区别就是笔译translator与口译interpreter。
编译程序（Compiler）
将源程序完整转换成机器语言/汇编语言程序

编译系统 = 编译程序 + 运行系统

编译程序总体结构（重点）

每个模块的功能：（回忆一下实验课干了啥）

词法分析器：从左到右扫描源程序的字符串，生成单词符号串（Token）。并且将发现的标识符identifier登记到符号表中。检查组词方面的错误并处理。
语法分析器：组词成句，识别出语法成分，分层给出程序的组成结构，指出语法错误，制导语义翻译。
语义分析与中间代码生成器：语法分析器识别出语法成分之后，3完成对其的语义分析。并以中间代码的形式实现对分析结果的表示。
代码优化器：对中间代码进行优化处理，一是节省存储空间，更有效利用机器资源；二是节省时间，使程序运行速度更快，效率更高。
目标代码生成器：将中间代码转化为目标机器上的机器指令代码或者汇编代码。
表格管理：按照编译过程当中的信息需求，以不同类型组织符号表，进行增查的维护表格操作，提供信息服务，辅助实现编译任务。
出错处理器：对各种错误进行检查、报告、纠正，以及相应的续编译处理。

练习：

词法分析有检查错误的功能吗？
目标代码生成器只能生成机器指令吗？
符号表格管理需要删/改吗？
出错处理器只能处理错误吗？

编译程序的组织

需要多遍扫描，在每次扫描中完成不同的任务

如：1st构造语法树，2nd处理中间表示，增加信息etc。

为了提高可移植性，编译程序可以分成前端、后端：

前端：与源语言有关，与目标机无关的部分
- 词法分析、语法分析、语义分析与中代生成、与机器无关的代码优化
后端：与目标机有关的部分
- 与机器有关的代码优化、目标代码生成

编译程序的生成（重点）

T形图：

T形图拼接的性质：

要求拼接处（蓝色框）相同。

T形图翻译生成：

在一个机器上实验C语言编译器：C语言–>机器语言，via机器语言。
你可以以C语言为实现语言，任意地生成T形图。

练习：在在

高级语言与方法

语言结构

语言是由字和组合规则构成的统一体。

对于程序设计语言来说，

程序设计语言：组成程序的所有语句的集合
程序：满足语法规则的语句序列
语句：满足语法规则的单词序列
单词：满足词法规则的字符串

语言的描述形式——文法：

语法——语句
词法——单词

研究语言的角度：

Chomsky从产生语言的角度
Kleene从识别语言的角度（自动机）
Chomsky证明了文法与自动机的等价性

描述语言的基本定义

字母表 $\Sigma$：非空有穷的集合，其中的元素称为字母，或者字符。

字母表的正闭包$\Sigma^+$：字母表内所有字母的任意组合。

字母表的克林闭包$\Sigma^*=\Sigma^+\cup\varepsilon$。即多加了一个空字符。

前缀：句子的前部分，包括空和本身

真前缀：不包括本身

后缀：句子的后部分，包括空和本身

真后缀：不包括本身

语言：克林闭包的一个子集（某些句子的组合）

句子：语言的一个元素

文法的定义

方法G是一个四元组:

$$
G = (V, T, P, S)
$$

其中，

V是非终结符集，表示语法变量/成分——某个语言的各种子结构，以大写字母表示。
T是终结符集，表示语言的句子中出现的字符，以小写字母表示。$V\cap T=\emptyset$
S是开始符号，至少在产生式左侧出现一次。$S\in V$
P是产生式集合，产生式定义各个语法成分的结构/组成规则，如$A\rightarrow bB$

产生式可以简写，

$$
\alpha\rightarrow\beta_1, \alpha\rightarrow\beta_n \implies a\to\beta_1|\beta_n
$$

其中，$\beta_1, \beta_n$叫做候选式，Candidate。

句子的派生/推导（产生语言）

简单来说，句子的推导就是从一个起始的产生式，依据产生式的规则，逐步变成一个具体的句子的过程。

例如：

左句型对应最左推导，每次对最左边的变量下刀。右变量同理。普通的句型则是随机动手。

可以看到，左句型、右句型是唯一的，但是普通句型可以有多个过程。

句子的识别/归约（识别语言）

是推导的逆过程，由一个具体的句子回溯到一个原始的产生式。

最右归约表示从具体句子的最右下手，最左同理。

可以看到，最右归约和最左推导的过程是一样的。

CFG的语法树

上下文无关方法：箭头左侧只有一个变量且不产生空。

CFG下的句子可以写成一颗语法树。

短语、直接短语、句柄

参考上面的语法树，

短语：对于一棵子树，其所有叶子结点从左到右排列，有几个子树就有几个短语。如id+id*id, id
直接短语：考虑所有叶子结点，如果这个叶子他的直系兄弟都是叶子（他没有侄子），那就是直接短语。下图中，b1, b2, a2是直接短语，但是a3不是，他有一个侄子a2。
句柄：最左直接短语。在上图中是b1。

这ppt讲的真的跟shit一样。

练习：

上下文有关文法可以用语法树表示吗？
上下文有关文法有短语吗？

词法分析

这章比较抽象，考的比较少。

词法分析器的功能

功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成“等价的”单词(记号)序列。

单词被表示成（种别，属性值）的二元组的形式。

为了提高效率，词法分析器采用了缓冲技术，当字符流读入缓冲区时，是经过剔除注释、空白符等预处理之后的结果。

词法分析阶段的错误处理：

1．非法字符检查

2．关键字拼写错误检查

3．不封闭错误检查

4．重复说明检查

5．错误恢复与续编译

紧急方式恢复：反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的单词为止。

单词的描述与正则文法（重点）

单词的识别本质上是正则语言的识别。（自动机！）

正则表达式：

| 表示或
* 表示Kleene闭包
+ 表示正闭包
? 表示0个或1个
ab 并列表示两者的连接

根据正则文法构造正则表达式：

构造方程式
- 形如$A\to a_1|a_2|…|a_mB$, 写成$A=(a_1|a_2|…|a_m)B$, where $B\ne A$.
- For $A\to a_1|a_2|…|a_mA$, convert it as $A=(a_1|a_2|…|a_m)*A$.
解联立方程组，求等价的正则表达式 r
- 用代入消元法
- 以带*的等式为轴操作
- 从末往前消

根据正则表达式构造正则文法：

从 $A\to r$ 开始，逐步进行分解：

if $r=r_1r_2$, then $A\to r_1B, B\to r_2$
if $r=r_1^*r_2$, then $A\to r_1A, A\to r_2$
if $r=r_1|r_2$, then $A\to r_1|r_2$

自动机

主要是《形式语言与自动机》课程的内容，感觉不是重点，懒的复习这个了。

还有一个Lex，赌他也不考这个。

自顶向下语法分析

文法改造

自顶向下分析会遇到二义性问题、回溯问题、左递归引起的无穷推导问题，需对文法进行改造：消除二义性、消除左递归、提取公共左因子。

消除左递归：即改造$A\to A\alpha|\beta$：翻转、拼接
$$
\implies A’\to\alpha A’, \quad A\to\beta A’|\varepsilon
$$
提取左因子：
$$
A\to\alpha\beta_1|\alpha\beta_2 \implies A\to\alpha A’,\quad A’\to \beta_1|\beta_2
$$

FIRST集和FOLLOW集

求FIRST集：FIRST(x)本v质上是在问，x可能以哪些字母开头？
- 若x是终结符，FIRST(x)={x} // 显然此时x只能以x开头
- 若X是非终结符：
  - $X\to aA \implies a\in FIRST(X)$ // 此时X可能以a开头
  - $X\to \varepsilon \implies \varepsilon\in FIRST(X)$ // 也可以以e开头
  - $X\to Y_1Y_2…Y_k$：
    + 把$FIRST(Y_1)-\varepsilon$加入到$FIRST(X)$
    + 如果$\varepsilon\in FIRST(Y_1)$, 则考虑$Y_2$，往下类推
    + 只有空属于每个Y的时候，才可能加入到FIRST(X)。
求FOLLOW集：FOLLOW(x)本质上是在问，x后面可能跟哪些字母？
- 对于开始符S，$# \in FOLLOW(S)$
- 考虑 $B\to\alpha A\beta$：
  - 将$FIRST(\beta)-\varepsilon$加入到$FOLLOW(A)$
  - 若空还在$FIRST(\beta)$中，将FOLLOW(B)也加到FOLLOW(A)。 // $B\to\alpha A$变换之后，A后面跟的字母就是先前B后面跟的字母。

LL(1)文法

判断LL(1)文法：

已经化简并且没有左递归
对于A每个产生式的candidates, 要求满足：
- $FIRST(c_i)\cap FIRST(c_j) = \emptyset$
- 若存在candidates为$\varepsilon$, 则其他的$FIRST(c_i)\cap FOLLOW(A)=\emptyset$

构造LL(1)分析表：哪些产生式可以让A以a开头？

对于$A\to r_i$

如果$FIRST(r_i)=a$, 则M[A, a]中填入此产生式
如果$FIRST(r_i)=\varepsilon$，则考虑FOLLOW(A)=b，在M[A, b]中填入此产生式
其他空着。

反正就是，出现FIRST(B)=e的时候，就要考虑FOLLOW(A)代替他。

自底向上语法分析

解决LR分析：LR(0) < SLR(1) < LALR(1) < LR(1)

项目与DFA

项目：右部某位置上有·的产生式

如A–>xyz有四个项目：A–>·xyz、A–>x·yz、A–>xy·z、A–>xyz·

项目的分类：

归约项目：$A\to \alpha\cdot$
接受项目：$S\to \alpha\cdot$
移进项目：$A\to\alpha \cdot z\beta$
待约项目：$A\to \alpha\cdot Z\beta$

画项目集活前缀的DFA：

作拓广文法：新增：(0) S’–>S，然后把其他的规则一一标号。
$I_0$中的第一个项目为S’–>·S，接下来，在$I_0$中寻找等价项目。
- A–>XYZ·BCD的等价项目为$B\to\cdot\beta$。也就是把·后面的非终结符展开。
寻找到完整的$I_0$之后，·可以跨越不同的终结符或者非终结符，形成不同的分支，对应不同的新项目集。
在新的项目集内继续寻找等价项目，得到完整的新项目集。
重复3.4.，直到归约。
每个项目集对应DFA的一个状态，最终形成了一个DFA。

例子如下图：（先别管#）

$$
(S\to A,\quad A\to BA|\varepsilon,\quad B\to aB|b)
$$

LR分析表

LR分析表表示状态的转移。需要在表格中填入对应的内容。

LR(0)文法

画出DFA之后，项目集内没有冲突项目：

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

这样的文法称之为LR(0)文法。

对于LR(0)文法分析表，

ACTION:
- sn: 遇到此终结符，shift到n状态。
- rn: 此状态n为归约项目，此行都填rn
- acc：接受项目，#处填acc
GOTO:
- 填n，经过此非终结符到达状态n

SLR(1)文法

满足以下条件：

画出DFA中，项目集内存在冲突项目。
对于$I_n={A_i\to\cdot a_i\beta,\quad B_i=\alpha\cdot}$，（同时有移进和归约），要求${a_1,…,a_m}, FOLLOW(B_1)…FOLLOW(B_n)$两两不相交。也就是·之后的字母只能出现在一个集合内。

对于SLR(1)文法分析表，

ACTION：对于归约项目$A\to\alpha$，求FOLLOW(A)得到的结果处填上rn，即遇到FOLLOW(A)的时候归约
其他和LR(0)一样

LALR(1)文法

两个项目集，如果就向前搜索符不同，其他都相同。则为同心集。

LR(1)文法

判断：构造带有向前搜索符的DFA，没有归约-归约冲突。

DFA构造：

起始项目：S’->·S, #
对于$A\to \alpha\cdot B\beta,a$, 其等价项目$B=\cdot r, b$，其中，$b=FIRST(\beta a)$

对于LR(1)分析表：

ACTION: 归约项目填写到向前搜索符的地方，填上rn
其他和LR(0)一样。

自底向上语法分析过程

看看这个表

在step 1, 由初始状态栈和下一字母，可以查得此时的action为s4。对于sn，其goto项就是n。把goto项压入状态栈，然后把字母压入符号栈。
step 2同理。到达step 3后，此时查表得到action为r5。r5对应的规约是B->b，由于右边长度为1，状态栈弹出1个元素。此时栈顶为4，查询GOTO[4, B] = 7，压入状态栈。修改符号栈。
step 4同理。查询到action为r4，对应规约为B->aB，由于右边长度为2，状态栈弹出2个元素，此时栈顶为0，查询GOTO[0, B] = 3，压入状态栈，修改符号栈。

语法制导翻译与属性文法

这ppt写的是真nm抽象。

语义翻译：语义分析+中间代码生成

如果在语义分析的同时进行语义翻译，这个就called语法制导翻译。

基本思想

表示语义信息：

为CFG中的文法符号设计语义属性，如类型、值、地址

计算语义属性：

通过文法符号所在的产生式，其相关联的语义规则来计算。

如何联系语义规则与语法规则？

语法制导定义：语法规则与语义规则（计算式）之间的映射
语法制导翻译方案：SDD的补充，显式地指明了语义规则的计算顺序

语法制导定义SDD

将每个文法符号与其语义属性集合相关联
将产生式与语义规则相关联

例如：

文法符号的属性：

综合属性：
- 在语法树结点N上，A的综合属性只能由N和N的子结点定义。如
- 对于终结符a，其综合属性是由词法分析器提供的词法值。（所以，为什么token需要二元组？）
继承属性
- 在语法分析树结点N上，A的继承属性只能由N的父结点、兄弟结点、N本身定义。如：（兄弟）
- 终结符没有继承属性。

副作用：过程调用的形式表达的语义规则

注释分析树：每个节点都带有属性值

属性文法：一个没有副作用的SDD

SDD的求值顺序

在语法树中，把综合属性写在右边，继承属性写在左边。

如果一个属性A的求出，需要依赖B，那么画一条B->A的有向边。

完成所有边后，会得到一个有向图，把它变成拓扑排序，就是SDD的求值顺序。

注意：

如果只有综合属性的SDD，一定可以求出一个顺序
如果同时有syn和inh，有可能没有这个顺序（有可能形成环）。

S-属性定义（S-SDD）

只使用综合属性的SDD。可以通过自底向上的方法，得到所有的节点的属性值。

L-属性定义（L-SDD）

在一个产生式所关联的各个属性之间，有向图的边可以从左到右，不能从右到左。

正式定义：好抽象。
反正就是，限制了继承属性，不能依赖右边的兄弟的属性

S-SDD是L-SDD的一种。

语法制导翻译方案SDT

不想看这个了，赌不会考。

SDT是产生式右部嵌入了语义动作（程序片段）的CFG

SDT可以看成是SDD的具体实施方案

例如：

S-SDD生成SDT：把语义动作加到产生式最右就可以。

L-SDD生成SDT：

把计算A的继承属性的动作插入到产生式右部A出现之前的位置
把计算左部的综合属性的动作插入到最右端。

语义分析与中间代码生成

逆波兰表示：ab+，是树的后序遍历。

三地址码：每条指令最多有两个地址，即两个操作数和一个结果。

如x+y*z的三地址码：t1:=y*z, t2:=x+t1
三地址码中还可以使用if, goto之类的
其实就是规则更简单的伪代码

四元式：(op, arg1, arg2, result) –> result = arg1 op arg2

如(*, y, z, t1), (+, x, t1, t2)

翻译为四元式序列

基本语句的转换：

x := y | (:=, y, -, x)
t1 = x+y | (+, x, y, t1)
if A goto p | (jnz, A, -, p)
if A rop B, goto p | (jrop, A, B, p)
goto p | (j, -, -, p)

布尔表达式->四元式序列

从左向右扫描布尔表达式。一旦确定如下的结果就结束：

$A\land B$: A假则假
$A\lor B$: A真则真

写的时候，A真A假的情况要成对相邻出现。

if/while

其实差不多。

存储分配

静态存储分配

分配方法：

顺序分配法
- 依据调用的顺序关系，为每个过程分配相关的存储空间
- 我们注意到，同层的过程是没有互相调用的关系的，不可能同时处于活跃状态。这意味着我们可以使用更少的存储空间。
层次分配法
- 从最下层过程开始，按层次分配存储单元。
- 为过程分配时，一定要超过其调用过程的存储空间位置

不想写这个啦我测剩下的感觉也没什么好考的再看看作业的那个结构体对齐吧。

代码生成

考一个指令的开销。

只有R和*R是0开销。其他（如访问地址、使用常数）都是1。

另外，每一条指令都有1的基本开销。

#编译原理

编译原理

https://max-wzm.github.io/2022/11/19/course/编译原理/

作者

Max Wang

发布于

2022年11月19日

许可协议

密码学基础上一篇

计算机组成原理下一篇