编译原理

1 导论

参考吉林大学编译原理网课资源

1.1 编译原理思维导图

1.2 编译器的组成及各部分的功能及作用

1. 词法分析 词法分析器根据词法规则识别出源程序中的各个记号（token），每个记号代表一类单词。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器的输入是源程序，输出是识别的记号流。词法分析器的任务是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。 2. 语法分析 语法分析器根据语法规则识别出记号流中的结构（短语、句子），并构造一棵能够正确反映该结构的语法树。 3. 语义分析 语义分析器根据语义规则对语法树中的语法单元进行静态语义检查，如类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的。 4. 中间代码生成 中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式，它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码，它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。 5. 中间代码优化 优化是编译器的一个重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上有很大浪费。当需要生成高效目标代码时，就必须进行优化。 6. 目标代码生成 目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。编译器生成的目标程序代码可以有多种形式：汇编语言、可重定位二进制代码、内存形式。 7 符号表管理 符号表的作用是记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的查找和操作。符号表中的某些内容甚至要保留到程序的运行阶段。 8 出错处理 用户编写的源程序中往往会有一些错误，可分为静态错误和动态错误两类。所谓动态错误，是指源程序中的逻辑错误，它们发生在程序运行的时候，也被称作动态语义错误，如变量取值为零时作为除数，数组元素引用时下标出界等。静态错误又可分为语法错误和静态语义错误。语法错误是指有关语言结构上的错误，如单词拼写错、表达式中缺少操作数、begin和end不匹配等。静态语义错误是指分析源程序时可以发现的语言意义上的错误，如加法的两个操作数中一个是整型变量名，而另一个是数组名等。

2 正则与状态机

正则表达式和状态机的表达能力相同，他们俩之间也是可以互相转换的，一般情况下是NFA与正则相互转换，然后NFA转换为DFA。

正则

正则表达式基于字母表

$$\Sigma$$

里面含有很多字符，通过对符号串进行三种类型的操作（连接，闭包，或）来表达一个符号串集合，如

$$\Sigma1 = \{a,b\}\\ R1 = a*$$

则R1表示只含有a的符号串或空串

除了 R1=a* 描述的很简单的符号串外，正则表达式R还可以描述很多其他有规则的串，如：
标识符
常数
特殊符号
整数

举个栗子：

这个题是比较复杂的了，但是我觉得答案有问题，正确的答案是：

$$((z|yz)*(\epsilon|y)x(z|yz)*(\epsilon|y)x)*(z|yz)*(\epsilon|y)$$

首先，我们要保证有偶数个x，所以就要有这个形式：

$$(AxBx)*C$$

A,B,C中不含有x，且满足没有连续两个y。因此，A，B，C其实具有相同的正则表达式，但是不能保证A，B，C完全相同。

我们可以用状态机的方法求A,B,C的形式。

graph TD;
	id0(0)--y-->id1(1)
	id0(0)--z-->id0(0)
	id1(1)--y-->id2(2)
	id1(1)--z-->id0(0)
	id2(2)--yz-->id2(2)

只有0和1状态是合法状态，因此0状态的正则表达式是:

$$(z|yz)*$$

1状态的正则表达式是:

$$(z|yz)*y$$

因此0和1状态的正则表达式是:

$$(z|yz)*(\epsilon|y)$$

正则与状态机的表达能力

如上图所示，S1集合可以用正则表达，但是S2集合不能用正则表达，原因是：正则不能使a和b的个数相等。但是，当学到了乔姆斯基文法的时候，就可以很轻松地表示S2了，设计一个文法规则，输入一个串，若符合该文法，则是属于S2，若不符合该文法，则不属于S2。

类似地，L1和L3不能用正则来表达

• 正则表达式不能用于描述配对或嵌套结构
• 正则表达式不能用于描述重复串

状态机

状态机M是一个五元组：(有穷状态集，有穷字母表，初始状态集，转换函数，终止状态集)。

状态机分为NFA与DFA，他们俩的区别是：
NFA允许有空边
NFA允许同一个边对应多个状态
NFA的初始状态可以不止一个

DFA怎么用？从初始状态开始接收字符input[0]到A，A接收input1到B…，若最终停留在终止状态，则input是该状态机描述的符号串

举个栗子：设计一个DFA以识别所有能被3整除的二进制数。思路是：可以设计三个状态，分别表示余0状态，余1状态，余2状态。在余0时，接收1就成了余1，接收0，还是余0，在余1时，接收1成了余0，接收0成了余2，在余2时，接收1还是余2，接收0成了余1。
考试应该会出类似这样的题，用这种思路比较好用。

NFA转换为DFA

NFA转换为DFA主要用到了子集法：把NFA中的所有初始状态及其epsilon_closure组成的状态看作是DFA的初始状态，然后由初始状态S中的每个NFA状态经过输入字符a转换的状态集及其epsilon_closure组成新的DFA状态A，这样DFA的状态转换矩阵就有了内容f(S,a)=A。若A包含NFA中的终止状态，则A也是DFA的终止状态

在NFA转换为DFA的过程中，要维护一个状态转换矩阵，上面的f(S,a)=A就是要填充进这个矩阵的，下面是这个矩阵的一个例子。

DFA状态	a	b
+{1,2,3,4}	{2,3,4}	{2,3,4,5}
{2,3,4}	{2,3,4}	{2,3,4,5}
-{2,3,4,5}	{2,3,4}	{2,3,4,5}

有了这个矩阵，画出DFA就不是难事了。

DFA的最小化

DFA化简方法的状态分离法。

思想是：首先将非终止状态放在A组，终止状态放在B组，如果一个组S中的所有状态对每一个在有穷字母表中的元素a都是不可区分的（都转向同一个组内的状态），则不用分割，否则，S分为两个组S1,S2,且S1对a不可区分，S2对a不可区分。

经过状态分离法后，把每一个组作为一个新的状态，然后转换矩阵中的状态也换成这个状态所在的组号。

正则转向NFA

1. 首先构造此NFA的开始状态和S和终止状态Z，由S出发指向Z的有向弧上标记上R（正则表达式）
2. 反复利用下面的规则对R进行分解，直至状态图中的所有有向弧上标记的符号都是单个元素或epsilon为止。

看最外层是属于这三种情况的哪种类型，就运用那个规则来转化

NFA到正则

跟上面一样。

注意：如果在NFA中有一个通过输入a指向自己的弧，则可以转化为a*；NFA中的所有epsilon边都可以不用考虑。

关于“(a*|b*)与(a|b)*是否等价

(a* | b*) 表示只有a或b的串，(a | b)* 表示含有a和b的串，所以这两个正则表达式不一样。

记忆

NFA与正则表达式之间的转换

3 词法分析

一个token的结构是：{类型，内容}，类型表示标识符，常量，保留字和特殊字符；当类型是表示符时，内容就是标识符的内容，否则，内容为空。

词法分析就是利用DFA和输入流来检测输入流中的所有token，然后形成token序列。

4 语法分析

乔姆斯基文法

文法使用非终极符表示一个概念，用终极符表示具体的token，每个文法都由一个最原始的非终极符来推导而成，这个非终极符就是开始符。

我们使用的都是上下文无关文法，这个文法保证产生式左部只有1个非终极符。除了这个文法，还有0型文法，1型文法（上下文有关文法），2型文法（上下文无关文法），3型文法。这些文法的表达能力依次降低。

0型文法

对文法G中的任一产生式$\alpha->\beta$ 不加任何限制

1型文法

如果对文法G中的任一产生式均限制为形如$\alpha A\beta->\alpha\gamma\beta$

2型文法

如果对1型文法的$\alpha, \beta$ 均设为$\epsilon$ ，即任一产生式形如$A->\gamma$ ，则为2型文法

3型文法

又称线性文法，正则文法，正规文法。

如果任一产生式形如：$A->aB$ 或者 $A->a$ ，则为右线性3型文法；如果任一产生式形如：$A->Ba$ 或者 $A->a$ ，则为左线性3型文法。

一般用大写字母如A表示非终极符，用希腊字母如$\alpha$表示句型，用小写字母如a表示终极符

如何根据规则构造上下文无关文法

一般会构造比较对称的规则，比如，下面两个

$$1^n0^m1^m0^n,n,m>=0$$ $$a^{2m-1}b^m, m>0$$

对于第一个规则，答案是：

$$S->1S0\\ S—>\epsilon\\ S->A\\ A->0A1\\ A->\epsilon$$

对于第二个规则，我们可以进行一些改动，比如：

$$aa^{2m-2}b^{m-1}b, m>0$$

这样就明了了，答案是：

$$S->aAb\\ A->aaAb\\ A->\epsilon$$

短语，简单短语，句柄

要分辨出这几个概念，必须画语法分析树。

短语：由语法树上任意一个非终极符推导出来的终极符串就是短语。

简单短语：由语法树上任意一个非终极符经过一步推导得到的终极符串就是简单短语

句柄：由于每个简单短语在句型中都不相交，所以找最左边的那个就是了。

二义性文法

二义性文法不管怎么进行文法变换，都是二义性文法。下面是两个典型的二义性文法

1. E -> i | E+E | E*E | (E)

   对于串 i*i+i 可以画出两个语法分析树

2. 若将1的文法稍作修改

   $$E->E+E|T\\ T->T*T|(E)|a$$

   对于i*i+i已经没有歧义了，但是对于i+i+i仍然有歧义，因为不知道前2个i由第一个E推导出来的，还是前1个i由第一个E推导出来的。

3. $$S -> S(S)S | \epsilon$$

   对于串 ()() 可以画出两个语法分析树

4. 对于一个if-then-else文法

   $$S->iBtSE|a\\ E->eS|\epsilon\\ B->b$$

   对于ibtibtea，最后的else语句ea是和第一个t(then)还是第二个t(then)匹配呢？

文法等价变换

本来学了一大堆，但是真正有用的只有三个。

拓广产生式

按照经验，考试时如果要画LR状态机，大概率用拓广产生式，有以下两种情况很可能用拓广产生式：

1. 某个规则的右部含有开始 符
2. 开始符含有多个规则

例如：

$$S->AB\\ A->aS\\ B->b$$

要用拓广产生式变为：

$$Z->S\\ S->AB\\ A->aS\\ B->b$$ $$S->A\\ S->B\\ A-a\\ B->b$$

要用拓广产生式变为：

$$Z->S\\ S->A\\ S->B\\ A-a\\ B->b$$

消除公共前缀

产生式形如：

$$A -> \alpha \beta1 | \alpha \beta2|...|\alpha \beta_n | \gamma$$

转换结果为：

$$A1 -> \beta1 | \beta2 |...| \beta n \\ A -> \alpha A1 | \gamma$$

消除左递归

一般考虑直接左递归。

例如：

$$A -> A \alpha | \beta$$

这个文法可以理解为，左边有一个\beta，右边跟上0个或多个\alpha
所以转换结果为：

$$A -> \beta A1\\ A1 -> \alpha A1 | \epsilon$$

自顶向下的语法分析

自顶向下的语法分析试图构造文法的最左推导，因为每次都从最左边的非终极符中选择它的一个产生式进行替换。但是选择哪个产生式呢？这就要看当前的输入字符a了，看哪一个产生式的右部有可能“导致“后面的第一个终极符为a。使用”导致“非常不准确，就出现了predict集来描述。

First集合

First集合既相对于一个单个的非终极符，也相对于一个句型（包含终极符和非终极符的串），两者的求法是递归的，比如求一个非终极符的First集合要先求它的右部句型的First集合，同时要求一个句型的First集合，要先求它所有包含的非终极符的First集合。我们先维护一个空的Fisrt集合表，里面保存所有非终极符的First集合，然后让这个表收敛。

非终极符的First集合

对于每个X $\epsilon$ $V_N$ 重复以下步骤，并不断填充First集合表，直到每个非终极符的First集都不再变化为止

求X的First集合First(X):

1. 若 $X \epsilon V_T$，则First(X) = {X}

2. 若$X \epsilon V_N$，则First(X) <= {a | X -> a$\alpha$ $\epsilon$ P}

3. 若$X \epsilon V_N$，且有产生式 X->$\epsilon$，则First(X) <= $\epsilon$

4. 若$X \epsilon V_N$，且有产生式 X->$Y_1$ $Y_n$ … $Y_n$

   当存在一个i<=n，使得每个i，有First($Y_i$ )含有$\epsilon$，则，First(X) <= (First($Y_1$) - {$\epsilon$}) $\cup$ (First($Y_2$) - {$\epsilon$}) $\cup$ … $\cup$ (First($Y_{i-1}$ ) - {$\epsilon$}) $\cup$ First($Y_{i+1}$)

   当对于所有的i<=n，都有$Y_i$的First集合存在$\epsilon$，则First(X) <= {$\epsilon$}

例如文法G：

$$E->TE1\\ E1->+TE1|\epsilon\\ T->FT1\\ T1->*FT1|\epsilon\\ F->id|(E)$$

它的First集合表为：

非终极符	First集
E	id (
E1	+ $\epsilon$
T	id (
T1	* $\epsilon$
F	id (

有了每个First集合后，Follow集合和Predict集合好求多了。

句型的First集合

有了非终极符的First集合，我们可以一步到位地求任何句型的First集合。

First($Y_1$ $Y_n$ … $Y_n$ )的求法

1. 当存在一个i<=n，使得每个i，有First($Y_i$ )含有$\epsilon$，则，First(X) <= (First($Y_1$) - {$\epsilon$}) $\cup$ (First($Y_2$) - {$\epsilon$}) $\cup$ … $\cup$ (First($Y_{i-1}$ ) - {$\epsilon$}) $\cup$ First($Y_{i+1}$)
2. 当对于所有的i<=n，都有$Y_i$的First集合存在$\epsilon$，则First(X) <= {$\epsilon$}

Follow集合

1. 初始时若A不是开始符，则Follow(A) = {}，否则，Follow(A) = { # }（#表示终结符）

2. 对于所有的右部包含有A的产生式 $X->\alpha A \beta$

   1. Follow(A) <= First($\beta$) - {$\epsilon$}
3. 若First($\beta$) 包含 $\epsilon$，则Follow(A) <= Follow(X)

对于每个$V_N$ 运行上述步骤，知道对所有的X $\epsilon$ $V_N$ ，Follow(X)收敛

Predict集合

我们基于句型的First集合和每个非终极符的Follow集合 可以一步到位地求出每个产生式的Predict集合。

对于产生式$X-> Y_1 Y_2 … Y_n$ ：

1. Predict($X-> Y_1 Y_2 … Y_n$) <= First($Y_1 Y_2 … Y_n$) - {$\epsilon$}

2. if First($Y_1 Y_2 … Y_n$) 含有 $\epsilon$ then

   1. Predict($X-> Y_1 Y_2 … Y_n$) <= Follow(X)

LL1分析表

大致结构如下（以上面的例子为例）：

产生式	*	id	(	)	+	#
E		1	1
E1				3	2	3
T
T1
F

接下来就是根据求得的Predict集合来填表了(上表没有填完)，表中的元素代表要是用的产生式的下标。

LL1分析方法

计算过程中，维护一个表：

符号栈	输入流	操作(匹配，替换，成功)
S#	abc#

符号栈有两种写法，一种是我上面写的，另一种是这样：$#S$ 。这两种有什么不同呢：若使用第一种，则每次替换时，直接把最左边的非终极符替换成对应产生式的右部，若使用第二种，则每次替换时，把最右边的非终极符替换成对应产生式右部的reverse串。

第一种：$aBCD#$

第二种：$#DCBa$

递归下降分析方法

主要是写递归程序，对每一个非终极符都写一个递归程序：

例如：

void E(){
    if(token == "id" || token == "("){
        T();
        E1();
    }else{
        error();
    }
}

void E1(){
    if(token == "+"){
        Match();
        T();
        E1();
    }else if(token == "(" || token == "#"){
        return;
    }else{
        error();
    }
}

自底向上的语法分析

关键词：

1. 项目集
2. 项目集的投影
3. 项目集的闭包
4. 项目集的转换函数（决定了一个状态经过一个输入字符后，转向的下一个状态是什么样）

LR(0)

这个语法分析 是自底向上语法分析中表达能力最弱的，为什么呢？

1. 它无法处理移入/归约冲突和归约/归约冲突，当一个状态中既存在移入语句：$X1->A.bC$，又存在归约语句如：$X2->a.$，这样它就不知道应该移入还是归约，它没有任何前瞻性，它不会去检查前瞻符号与当前的产生式之间是否匹配，如：前瞻字符是a，但是X2的的Follow集合中并没有a，这样就肯定不能归约了（虽然X2的Follow集合有a，使用归约也不一定是正确的，见LR(1)）。

还有一点需要注意：在填写LR(0)语法分析的action表时，只含有归约产生式的状态对于所有的输入字符，都要填写R（归约），也就是说，当遇到归约状态时，不管前瞻字符是什么，都要归约，这一点与具有前瞻性的LR(1)对action表的填写有区别。

SLR(1)

它使用Follow集合和前瞻字符来避免一些移入/归约冲突和归约/归约冲突。

1. 如果某个状态有如下项目集：$A->\alpha.，D->\beta.d\gamma$

   1. 若前瞻字符在A的Follow集合中，则应用$A->\alpha.$归约
   2. 若前瞻字符为d，则应该移入 （满足移入的条件）
   3. 若前瞻字符在A的Follow集合中，也是d，则无法解决。
2. 如果某个状态有如下项目集：$A->\alpha.，B->\beta.$
   1. 若前瞻字符在A的Follow集中，则使用第一个归约
   2. 若前瞻字符在B的Follow集中，则使用第二个归约
   3. 若前瞻字符在A的Follow集中，也在B的Follow集中，则无法解决

SLR(1)的问题

有产生式：

$$Z->B^1aB^2bB^3c\\ B->d$$

这里的上标，表示同一个B的不同出现位置。B的Follow集是{a, b, c}，但是对于不同出现场景的B，它的Follow集不一样，比如，第一个B的Follow集是{a}，此时我们称{a}是第一个B的展望符集。

若移入了d，前瞻符是c，但是此时B是$B^2$，则此时，只能移入，不能归约，因为$B^2$后面应该是b，而不是c；但是SLR(1)此时不能解决了，因为c属于B的Follow集合，同时也可能符合移入的条件。

LR(1)

使用展望符集解决SLR(1)的问题。

核心是，对于状态中的每个项目（产生式），求它的展望符集，这个要基于这个项目的父项目，例如 ，$B->a.B，B->.aB，B->.b$，第二，三个项目的父项目是第一个项目：

1. 第一个产生式右部的.后面B后面是$\alpha$
2. 这个项目的子项目的展望符集 <= First($\alpha$) - {$\epsilon$}
3. 若First($\alpha$) 包含 $\epsilon$ ，则这个项目的子项目的展望符集 <= 这个项目的展望符集

例子

有文法：

$$Z->BB\\ B->aB\\ B->b$$

它的LR(1)状态机是：

这个状态数比LR(0)的多了，因为5状态和6状态本应该是一个状态的，但是由于展望符集的不同，所以也就分成了不同的状态。

问题

每个句子都一定有最左推导和最右推导吗？每个句型都一定有最左推导和最右推导吗？

每个句子都应该有最左推导和最右推导，因为推导的顺序不影响最终的结论；但是并非所有句型都有最左推导或最右推导，假如一个句型的最右端和最左端都有非终极符，那么无论采用最右推导还是最左推导，都违反了对当前符号串中的最右端（最左端）进行替换的原则。

若一个句型中出现了某一个产生式的右部，则此右部是否一定是该句型的句柄？

句柄是一个句型中最左的简单短语，但是这个产生式的右部不一定是简单短语，也不一定是最左的简单短语。如上图所以，i2不是简单短语，虽然i是B->i的右部，但不是句柄，i3是简单短语，但不是最左的，所以也不是句柄，只有i1才是句柄。

关于三个集合的说明

语法分析的核心是判定给定的token序列是不是文法的句子，自顶向下分析方法的思路是从文法的初始符号出发，看给定的token序列能否根据文法规则推导出来，由于以同一个非终极符为左部的规则可能有多条，所以在推导过程中可能伴随着大量的回溯，具体例子大家可以见我课件第九讲中的例子。由于回溯较多，会严重影响语法分析的效率，所以人们就开始思考怎样可以提高语法分析的效率，语法分析本质是一个搜索过程，最基本的提高搜索效率的方法就是增加启发式。假设文法的初始符号为S，以S为左部的规则有两条，分别是：S→aB和S→bD，当前待判定的串是abcd，串的头符是a，根据S进行推导时，我们一定是希望S把a打头的串推出来，这样才能继续往下推，在上面两条文法规则中使用S→aB推出的串是a打头的，用S→bD推出的串是b打头的，所以我们应使用S→aB这个规则来进行推导，S→bD这条规则可以直接排除。怎样让计算机完成这样的判断呢，一个方法就是为每一条文法规则都构造一个集合，这个集合包含了使用这条文法规则所能推出的所有头符（终极符）的集合，这个集合被称为这条文法规则的predict集，为什么头符一定要是终极符，因为句子只有终极符，不含非终极符。有了predict集之后，再判断上面的例子使用哪条规则就容易多了，因为S→aB这条规则的predict集包含a，S→bD这条规则的predict集不包含a。明确了这个问题之后下面要解决的问题是predict集怎么求，2型文法规则的描述形式为：A→§，这里A表示非终结符，§表示由非终极符和终极符组成的符号串。Predict集要求A→§这条规则最先可以推出什么终极符，显然这个集合应该包含§这个串所能推出的第一个终极符，我们把§这个串所能推出的第一个终极符的集合称为First（§）。求predict集时除了上述情况，我们还需要考虑一种特殊情况，就是§这个串推导出空串的情况。假设推导过程中的某个句型为AdBf,若使用A→§这条规则，§推导出空串时，得到的句型为dBf，此时得到的第一个终极符为d，d不在First（§）中，而是紧跟在A这个非终极符后面的终极符，我们将所有可能紧跟在A这个非终极符后面的终极符集合成为Follow（A）。当§可以推导出空串时，predict（A→§）不仅包含First（§），还包含Follow（A）。这里注意一下三个集合针对的对象是不一样的，predict集面向的是文法规则，First集面向的是符号串，Follow集面向的是一个非终极符。

5 语义分析

三个核心

1. 检查语义错误
2. 抽象地址的分配
3. 符号表局部化，标识符的作用域

语义表示

常量标识符的语义表示

Name	Kind	Type	Value

变量标识符的语义表示

Name	Kind	Type	Access	Level	Off	Value

过函标识符的语义表示

Name	Type	Kind	Level	off	Param	Class	Code	Size	Forward
func	intPtr	routKind	0			actual/formal			true/false

off只对形式过函有效，表示形式过函在所属过函内存块中的偏移

Param：过函的参数表指针，参数表的结构同符号表的结构相同，参数信息可以填入符号表，也可以填入单独的参数表中

Class：=actual表示实在过函，=formal表示形式过函

Code：只对实在过函有效，表示过函定义对应生成的目标代码的起始地址，当目标代码生成时，回填得到，形式过函的code为NULL

Size：只对实在过函有效，表示过函的过程活动记录的大小，这个大小是确定的。调用这个函数时我们会根据这个信息给它分配相应的存储空间。

Forward：前向声明

关于size的更详细的信息：

1. 在什么时候填写size：过函中局部变量的符号表填写完毕之后
2. 在什么时候修改size的内容：在中间代码生成后和中间代码优化后
3. 在什么时候使用size的内容：在过函的过程活动记录创建是使用size

类型的语义表示

子界类型

Size	Kind	Low	Up	ElemType
1	subrangeTy	‘a’	‘z’	charPtr

枚举类型

Size	Kind	ElemList
1	enumTy

ElemList是指向枚举常量表的指针：

Name	Value
red	0
yellow	1
blue	2

数组类型

Size	Kind	Low	Up	ElemType
50	ArrayTy	0	4

ElemType 表示数组成分类型的内部表示指针。

结构体和联合体

Size	Kind	RecBody
3	structTy
2	unionTy

Kind=structTy 表示结构体类型
Kind = unionTy 表示联合体类型
RecBody是指向FieldList（struct）的指针

FieldList的内部表示如下：

Name	Type	Off	link
year	intPtr	0
mont	intPtr	1

符号表的局部化

问题

对于嵌套式语言和并列式语言的处理，有哪些不同

1. 对于符号表的局部化处理。对于嵌套式语言，Scope栈中的Scope[l]通常指向l层符号表起始地址；对于并列语言，若不含分程序结构，可以不使用Scope栈，用两个变量分别存储0层和1层的符号表地址，若有分程序，Scope栈中的Scope[l]通常指向深度为l的分程序对应的局部化区首地址。
2. 分配抽象地址时，并列式语言中并列的分程序可以共用存储空间，嵌套式语言中的分程序必须要连续的向下分配
3. 在抽象地址映射过程中，对于并列式语言，在活动记录中可以不用为变量访问环境分配空间，使用两个寄存器分别存储静态区和当前活动记录的首地址就可以完成抽象地址到物理地址的映射；对于嵌套式语言，必须在过程活动记录中分配变量访问环境，可以用不同的方式：局部display表，静态链方法。

记忆

各种标识符，类型的语义表示

语义错误

6 中间代码生成

过函调用的中间代码生成

f(E1,E2,…, En) 的调用

(VarACT/ValACT, t1, Offset1, Size1)
(VarACT/ValACT, t2, Offset2, Size2)
......
(VarACT/ValACT, tn, Offsetn, Sizen)
(CALL, f, true/false, Result)

VarACT表示传递引用；ValACT表示传递值

true表示静态确定转向地址；false表示动态确定转向地址。

问题

临时变量有哪些特征：

1. 临时变量都是一种类型
2. 临时变量在定值之后只会被使用一次
3. 活动区不相交的两个临时变量可以共用一个存储单元

7 中间代码优化

我们使用三种局部优化：常量表达式节省，公共子表达式节省，循环不变式外提。前两种方法的优化范围是基本块。

常量表达式节省用到的表：常量定值表（ConstDef）

公共子表达式节省用到的表：值编码表（ValueNum），可用表达式代码表（UsableExpr），临时变量等价表（PAIR）

循环不变式外提用到的表：变量信息表（LoopDef）

注意

1. 对局部变量的赋值语句绝不外提，因为有些循环执行0次
2. 除法不外提
3. 非良性循环（循环体中含有函数调用或地址引用型变量的赋值）不做外提优化

例子

设有如下程序段，其中A：Array of [1..10] of Array [1..100] of integer，程序中的所有变量都为整型变量，占1个存储单元。

x:=0;
s:=x+1;
i:=2*s;
while i<10 do
begin
	k:=1;
    while k<100 do
    begin
    	j:=2*k;
        if j<50 then
        begin
        	s:=s+A[3][k]*A[i][k];
        end
		k:=2*k;  
	end
	i:=i+1;
end

该代码的四元式中间代码是：

(:=,0,_,x)
(+,x,1,t0) //常量表达式节省
(:=,t0,_,s) //常量表达式节省
(*,2,s,t1) //常量表达式节省
(:=,t1,_,i) //常量表达式节省
(while,_,_,_)
	(<,i,10,t2)
	(do,t2,_,_)
	(:=,1,_,k)
	(while,_,_,_)
		(<,k,100,t3)
		(do,t3,_,_)
		(*,2,k,t4)
		(:=,t4,_,j)
		(<,j,50,t5)
			(then,t5,_,_)
			(-,3,1,t6) //常量表达式节省，循环不变式外提
			(*,t6,100,t7) //常量表达式节省，循环不变式外提
			(AADD,A,t7,t8) //常量表达式节省，循环不变式外提
			(-,k,1,t9)
			(*,t9,1,t10)
			(AADD,t8,t10,t11)
			(-,i,1,t12) //循环不变式外提
			(*,t12,100,t13) //循环不变式外提
			(AADD,A,t13,t14) //循环不变式外提
			(-,k,1,t15) //公共子表达式节省
			(*,t15,1,t16) //公共子表达式节省
			(AADD,t14,t16,t17)
			(*,t11,t17,t18)
			(+,s,t18,t19)
			(:=,t19,_.s)
		(endif,_,_,_)
		(*,2,k,t20)
		(:=,t20,_,k)
	(endwhile,_,_,_)
	(+,i,1,t21)
	(:=,t21,_,i)
(endwhile,_,_,_)

中间代码优化：

源代码的2-3行（中间代码的2-6行）可以采用常量表达式节省；源代码的12行的A[3]的计算（中间代码的17-19行）可以采用常量表达式节省，循环不变式外提；源代码的12行的A[i][k]的计算（中间代码的23-27行），采用循环不变式外提，公共子表达式节省。

(:=,0,_,x)
(:=,1,_s) //常量表达式节省
(:=,2,_,i) //常量表达式节省
(AADD,A,200,t8) //常量表达式节省，循环不变式外提（外提2层）
(while,_,_,_)
	(<,i,10,t2)
	(do,t2,_,_)
	(:=,1,_,k)
	(-,i,1,t12) //循环不变式外提
	(*,t12,100,t13) //循环不变式外提
	(AADD,A,t13,t14) //循环不变式外提
	(while,_,_,_)
		(<,k,100,t3)
		(do,t3,_,_)
		(*,2,k,t4)
		(:=,t4,_,j)
		(<,j,50,t5)
			(then,t5,_,_)
			(-,k,1,t9)
			(*,t9,1,t10)
			(AADD,t8,t10,t11)
			(AADD,t14,t10,t17) //t10, 公共子表达式节省
			(*,t11,t17,t18)
			(+,s,t18,t19)
			(:=,t19,_.s)
		(endif,_,_,_)
		(*,2,k,t20)
		(:=,t20,_,k)
	(endwhile,_,_,_)
	(+,i,1,t21)
	(:=,t21,_,i)
(endwhile,_,_,_)

问题

为什么中间代码生成和中间代码优化不是编译程序必须完成的工作？

中间代码的生成是为了方便优化和移植，中间代码的优化则是为了提高效率。而源程序在经过词法分析、语法分析、语义分析、目标代码生成之后已经可以转化为目标程序，不需要中间代码生成和优化也能够实现编译程序的最终目的:将源程序转化为目标程序。所以中间代码生成和中间代码优化并不是编译程序必须完成的工作。

8 运行时存储空间管理

过程活动记录

当一个函数被调用时，就在栈区为它分配一片存储空间，用于存储管理信息和静态分配的数据。所以栈区中存储的所有过程活动记录反映了程序的过程调用情况，比如main调用P，P调用Q，就在栈区中依次出现$MAIN ar -> P ar -> Q ar$，这就是动态链，对应调用链：$main->P->Q$。

当一个程序运行到某个函数时，为了程序能够定位到自己的栈区，就设立了sp指针和top指针，这两个指针通常存储在寄存器中，有点类似于OS中的页表基址和页表限长，也存在相应的寄存器中。sp指向栈区的低地址区，top指向栈区的高地址区。

既然函数的调用形成了动态链，就要有动态链指针，不然返回到上一级调用函数时，上一级函数的sp指针怎么知道呢？；返回时，还要知道返回到上一级函数的哪一个语句，就要有返回地址来修改pc指针；返回的时候，还要给特定位置的存储区赋返回值，就有了返回值，表示存储区的地址；过程层数标识目前的函数处于第几层（注意，不是调用的深度，而是声明的深度，如果是main函数，则是0，如果在main函数定义了一个P，然后访问了P，则为1）；寄存器状态保存上一级函数的环境；活动记录大小标识整个AR的大小，这个是编译时就能确定的；如果你是用的是嵌套式语言，变量访问环境是必不可少的，可以根据它来访问上层函数定义的数据，如果一个函数的深度是N，那么它的变量访问环境就是第0层，第1层，…，第N-1层函数的活跃活动记录的sp指针，再加上自己的sp指针，这个变量访问环境完全可以根据调用函数的变量访问环境来计算。形参区，局部变量区，临时变量区，就是这个函数自己的东西了。

LAR(活跃活动记录)

变量访问环境的实现方法

局部Display表，全局Display表，静态链方法

总结

局部Display表的产生需要花费空间，但是返回时不需要为恢复变量访问环境做任何事情。

全局Display表的产生需要花费时间，而且返回时也需要为恢复访问环境而花时间，其主要优点是节省存储单元。

静态链方法是使用链表来表示变量访问环境，它实际上是共享化的局部display表方法，其主要优点同全局display表一样是能够节省存储单元，但产生需要花费时间，返回时不需要为恢复变量访问环境做任何事情。

问题

当发生函数嵌套时如何访问变量逻辑地址（如何进行抽象地址映射）？

以下解答，基于变量访问环境的局部display表法。假如当前活跃过程活动记录的层数是N，若访问的变量的层数是0，则说明它是全局变量，地址是0+off；若访问的变量的层数是i+1（1<=i<=N），则说明访问的变量是声明链中第i个（从0开始）函数内定义的变量，要知道其地址，必须知道对应函数的活跃过程活动记录在栈空间中的位置，答案是ar[i]+off，ar是当前函数的活跃过程记录中的变量访问环境。

记忆

过程活动记录

题目

https://wenku.baidu.com/view/fdd9716b284ac850ad0242ed.html 试题

引用

赏

谢谢你请我吃糖果