2.3 语义分析
PL/0的语义分析主要进行以下检查：
（1） 是否存在标识符先引用未声明的情况； （2） 是否存在己声明的标识符的错误引用； （3） 是否存在一般标识符的多重声明。
2.4 代码生成
PL/0编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。最终我们要“运行”该目标码。为了使我们的编译程序保持适当简单的水平，不致陷入与本课程无关的实际机器的特有性质的考虑中去，我们假想有台适合PL/0程序运行的计算机，我们称之为PL/0处理机。PL/0处理机顺序解释生成的目标代码，我们称之为解释程序。注意：这里的假设与我们的编译概念并不矛盾，在本课程中我们写的只是一个示范性的编译程序，它的后端无法完整地实现，因而只能在一个解释性的环境下予以模拟。从另一个角度上讲，把解释程序就看成是PL/0机硬件，把解释执行看成是PL/0的硬件执行，那么我们所做的工作：由PL/0源语言程序到PL/0机器指令的变换，就是一个完整的编译程序。
PL/0处理机有两类存贮，目标代码放在一个固定的存贮数组code中，而所需数据组织成一个栈形式存放。
PL/0处理机的指令集根据PL/0语言的要求而设计，它包括以下的指令： （1）LIT /* 将常数置于栈顶 */ （2）LOD /* 将变量值置于栈顶 */ （3）STO /* 将栈顶的值赋与某变量 */ （4）CAL /* 用于过程调用的指令 */
（5）INT /* 在数据栈中分配存贮空间 */ （6）JMP, JPC /* 用于if, while语句的条件或无条件控制转移指令 */ （7）OPR /* 一组算术或逻辑运算指令 */
上述指令的格式由三部分组成：
F L A 其中，f, l, a的含义见下表：
F INT LIT LOD STO CAL JMP JPC
L ——— ——— 层次差 层次差 层次差 ——— ——— 10
a 常 量 常 量 数据地址 数据地址 程序地址 程序地址 程序地址 OPR ——— 运算类别
表2-1 PL/0 处理机指令
上表中，层次差为变量名或过程名引用和声明之间的静态层次差别，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址。
PL/0的编译程序为每一条PL/0源程序的可执行语句生成后缀式目标代码。这种代码生成方式对于表达式、赋值语句、过程调用等的翻译较简单。 如赋值语句X := Y op Z（op为某个运算符），将被翻译成下面的目标代码序列：（设指令计数从第100号开始）
No. F L a 100 101 102 103 LOD LOD OPR STO Level_diff_Y Level_diff_Z —————— Level_diff_X Addr_Y Addr_Z op Addr_X
而对if和while语句稍繁琐一点，因为此时要生成一些跳转指令，而跳转的目标地址大都是未知的。为解决这一问题，我们在PL/0编译程序中采用了回填技术，即产生跳转目标地址不明确的指令时，先保留这些指令的地址（code数组的下标），等到目标地址明确后再回过来将该跳转指令的目标地址补上，使其成为完整的指令。下表是if、while语句目标代码生成的模式。（L1，L2是代码地址）
if C then S While C do S 条件C的目标代码 L1: 条件C的目标代码 JPC -- L1 JPC – L2 语句S的目标代码 语句S的目标代码 L1: ... JMP L1 L2: ... 表2-2 if-while语句目标代码生成模式
相关过程（函数）有：gen()，其任务是把三个参数f、l、a组装成一条目标指令并存放于code数组中，增加CX的值，CX表示下一条即将生成的目标指令的地址。
2.5 代码执行
为了简单起见，我们假设有一个PL/0处理机，它能够解释执行PL/0编译程序所生成的目标代码。这个PL/0处理机有两类存贮、一个指令寄存器和三个地址寄存器组成。程序（目标代码）存贮称为code，由编译程序装入，在目标代码执行过程中保持不变，因此它可被看成是“只读”存贮器。数据存贮S组织成为一个栈，所有的算术运算均对栈顶元和次栈顶元进行（一元运算仅作用于栈顶
11
元），并用结果值代替原来的运算对象。栈顶元的地址（下标）记在栈顶寄存器T中，指令寄存器I包含着当前正在解释执行的指令，程序地址寄存器P指向下一条将取出的指令。
PL/0的每一个过程可能包含着局部变量，因为这些过程可以被递归地调用，故在实际调用前，无法为这些局部变量分配存贮地址。各个过程的数据区在存贮栈S内顺序叠起来，每个过程，除用户定义的变量外，还应当有它自己的内部信息，即调用它的程序段地址（返回地址）和它的调用者的数据区地址。在过程终止后，为了恢复原来程序的执行，这两个地址都是必须的。我们可将这两个内部值作为位于该过程数据区的内部式隐式局部变量。我们把它们分别称为返回地址（return address）RA和动态链（dynamic link）DL。动态链的头，即最新分配的数据区的地址，保存在某地址寄存器B内。
因为实际的存贮分配是运行（解释）时进行的，编译程序不能为其生成的代码提供绝对地址，它只能确定变量在数据区内的位置，因此它只能提供相对地址。为了正确地存取数据，解释程序需将某个修正量加到相应的数据区的基地址上去。若变量是局部于当前正在解释的过程，则此基地址由寄存器B给出，否则，就需要顺着数据区的链逐层上去找。然而遗憾的是，编译程序只能知道存取路线的表的长度，同时动态链保存的则是过程活动的动态历史，而这两条存取路线并不总是一样。
例如，假定有过程A，B，C，其中过程C的说明局部于过程B，而过程B的说明局部于过程A，程序运行时，过程A调用过程B，过程B则调用过程C，过程C又调用过程B，如下图所示：
A
A
B
BA
C B
C
图2-1 过程说明嵌套图 过程调用图 表示A调用B
从静态的角度我们可以说A是在第一层说明的，B是在第二层说明的，C则是在第三层说明的。若在B中存取A中说明的变量a，由于编译程序只知道A，B间的静态层差为1，如果这时沿着动态链下降一步，将导致对C的局部变量的操作。为防止这种情况发生，有必要设置第二条链，它以编译程序能明了的方式将各个数据区连接起来。我们称之为静态链（static link）SL。这样，编译程序所生成的代码地址是一对数，指示着静态层差和数据区的相对修正量。下面我们给出的是过程A、B和C运行时刻的数据区图示：
DL RA SL
12 A的变量 B的变量 C的变量 B的变量
有了以上认识，我们就不难明白PL/0源程序的目标代码是如何被解释执行的。以语句X ：= Y op Z为例，（该语句的目标代码序列我们己在2.4节给出），PL/0处理机解释该指令的“步骤”如下： step 1,
S[++T] ← S[base(level_diff_Y) + addr_Y]; // 将变量Y的值放在栈顶 step 2,
S[++T] ← S[base(level_diff_Z) + addr_Z];
// 将变量Z的值放在栈顶，此栈顶元为变量Y的值 step 3, T--;
// 栈顶指针指向次栈顶元，即存放结果的单元 step 4,
S[T] ← S[T] op S[T + 1];
// 变量Y和变量Z之间进行“op”操作 step 5,
S[base(level_diff_X) + addr_X] ← S[T]; // 将栈顶的值存放到变量X所在的单元 step 6, T--;
// 栈顶指针减一
相关过程：base()，interpret()。其中base()的功能是根据层次差并从当前数据区沿着静态链查找，以便获取变量实际所在的数据区其地址；interpret()则完成各种指令的执行工作。
13
2.6 错误诊断处理
一个编译程序，在多数情况下，所接受的源程序正文都是有错误的。发现错误，并给出合适的诊断信息且继续编译下去从而发现更多的错误，对于编译程序而言是完全必要的。一个好的编译器，其特征在于： ? 任何输入序列都不会引起编译程序的崩溃。
? 一切按语言定义为非法的结构，都能被发现和标志出来。 ? 经常出现的错误，程序员的粗心或误解造成的错误能被正确地诊断出来，而不致引起进一步的株连错误。
根据这样的要求，我们为PL/0编译程序制定了以下两条规则：
（1） 关键字规则；程序员在写程序时，可能会因为粗心而漏掉语句的分隔
符——“;”，但他决不会漏掉算术运算符“+”，对于编译程序而言，不论是分隔符号类的符号还是关键字符号类的符号，它们都具有同等重要的地位。基于这样的特点，我们可以采用不易出错的部分来作为恢复正常步调的标记。每当遇到错误时，分析程序跳过后面的某些部分，直到出现所期望的符号为止。对于程序设计语言来说，这种符号（称为同步符号）的最好选择就是关键字。PL/0的每一种构造语句以begin、if或while开头；每种说明则以var、const或procedure开头。每遇到错误时，编译程序便可跳过一段程序，直到遇到这类符号为止，而继续编译。
（2） 镇定规则；自顶向下分析的特点在于目标对分成一些子目标，分程序
则用别的分析程序来处理其子目标。镇定规则是说一个分析程序发现了错误，它不应该消极地停止前进，仅仅向调用它的程序报告发生的错误；而应该自己继续向前扫描，找到似乎可以使正常的分析得以恢复的地方。这一规则在程序设计上的含义就是任一分析程序除了正常终止外，没有其它出口。
对于镇定规则，一个可能的严格解释为：一旦发现非法结构，即跳过后面的输入正文，直到下一个可以正确地跟随当前正在分析的句子结构的符号为止。这意味着每一分析程序需知道其当前活动结点的后继符号集合。
为了找到这个后继符号集合，我们给对应语法图的每一个分析过程提供一个显式参数，set，它指明可能的后继集合。不过在任何条件下，如果都跳到输入正文中下一个这种后继符号出现的地方，未免太短视了。程序中所含的错误可能只不过是漏掉了一个符号（如“;”）而己，由此而忽略去源程序的符号集合中，再凑加一些关键字，它们用于标记那些不容忽略的结构的开始符，因此，作为参数传递给分析过程的那些符号就不仅是后继符号了。 对于这样的符号集，我们采用这样的计算策略：先用一些明显的关键符号给它赋初值，然后随着分析子目标的层次深入，逐步补充别的合法符号。为了灵活起见，我们引入test子程序来实现所说的验证工作。 test过程有三个参数：
（1） 可允许的下一个符号集合S1，如果当前符号不在此集合中，当即
得到一个错误号；
（2） 另加的停止符号集合S2，有些符号的出现，虽然无疑是错的，但
它们绝对不应被忽略而跳过；
14