编译原理修改后的PL0报告

一、上机实践要求

“编译原理与技术”的上机实验要求你对PL/0语言及其编译器进行扩充和修改。每个扩充或修改方式可得到不同的分数，满分为100分。 完成上机作业后，必须提交下列文档： （1） 修改后的PL/0语言文本。包含词法分析（正规式），语法分析（BNF）。 （2） 有关修改后的PL/0编译/解释器的说明。详细说明你的编译器是如何编译新的PL/0语言程序的。指出你的程序中最精彩的部分，以及你为什么这样做，你是如何控制和恢复语义错误的。 （3） 给出你所改动后的编译器源程序清单，并标记出你所修改的部分。比较你的编译器和原来的编译器之间的差别。 （4） 说明你的编译器中可能存在的错误。 （5） 总结经验与教训，如果重做一遍，你会有哪些新的改进？ 对现存的PL/0编译程序可做如下修改或扩充，其中（1）、（2）、（11）和（12）必须完成，剩余的均可任意选择，但总分必须超过70分。 （1） 注释（5分）

注释由(*和*)包含，不允许嵌套。 （2） 布尔类型的数据（10分） 布尔类型的BNF为：

var_option → ε| var var_decl_list

var_decl_list → var_decl | var_decl_list var_decl var_decl → ident_list : data_type data_type → integer | boolean 这种修改包括： （i） 区别整型与布尔型变量、常量和表达式。 （ii） 增加按严格计算的布尔类型运算符and、or和not。这些算符以及己有的运算符的优先级与Pascal语言相同。 （iii） 能够使用布尔常量true和false。 （iv） 把PL/0语言中的“条件”概念一般化为Pascal语言那样。 （v） 布尔表达式可以比较大小：false < true （3） 布尔表达式的短路计算（5分） 增加布尔类型（见（2），除（2）的（ii）外），但对and和or采取短路计算。 （4） 数组（10分）

增加由任何数据类型构造的一维数组。数组的下标限于纯量类型。

注意：数组可以由其它的数组来构造，因而必须考虑多维数组的情况。数组的上下界可为任意的纯量常数。

数组的定义如下：

data_type → integer | boolean | array [const..const] of data_type const → ident | number

语言中允许有数组说明，对数组元素赋值，在表达式中引用数组元素。为了便于解释执行，可能要增加新的PL/0机器操作指令。 （5） 参数（10分） 语法同Pascal，采用值-结果方式传递（不用var声明）。 （6） 函数（10分）语法同Pascal。 （7） else子句和repeat语句（5分） （8） for语句，语法参照Pascal或C语言（5分）

第 1 页 共 22 页

（9） exit语句（退出当前执行过程）和break语句（跳出包含它的最内层循环），（5分） （10） 记录（结构）,语法同Pascal语言（10分）。 （11） 更有力的语法错误恢复机制（20分） （12） 分离解释和编译器（5分）

注意：上面的这些要求有时会互相影响：例如实现布尔类型数据，则数组和参数就应该能处理其相互组合的情况，如布尔型数组（包括多维数组）、布尔型作为下标的数组、布尔型作为参数传递。甚至能够实现数组作为参数传递等。

另外，为了实现以上功能，你可任意增加PL/0处理机的指令。但要注意指令的简单与合理。 选做题：此题不计入总分，仅做为学生在有余力的情况下的进一步练习。

实现PL/0语言的输入、输出语句。其语法、语义定义和Pascal语言相同。可以仅仅实现一次输入或输出一个值的语句——语句参数固定；也可以实现完全和Pascal语言一样，能够接受任意个数参数的输入或输出语句。 二、实验原理：

就像一个翻译要把汉语翻译成英语，必须对汉语和英语的单词、语法结构都很精通，才有可能翻译得准确无误。另外，编译程序既然是为了完成这种功能的一个程序，就存在用什么语言来编写这个程序的问题。这些问题在本节将逐步介绍。

现对PL/0语言编译程序的功能用“T”型图表示，并用图形概括描述PL/0编译程序的结构框架。 用语法图描述语法规则的优点是直观、易读。在图1.1的语法图中用椭圆和圆圈中的英文字表示终结符，用长方形内的中文字表示非终结符。所谓终结符，是构成语言文法的单词，是语法成分的最小单位，而每个非终结符也是一个语法成分。

但非终结符可由其它文法符号定义，终结符不能由其它文法符号定义。例如，程序是由非终结符'分程序'和终结符\组成的串定义的。由于对某些非终结符可以递归定义，如图1.1(b)、2.1 (c)、2.1 (e)中：分程序、表达式和语句。第一个非终结符 '程序'为文法的开始符号。 程序 . 分程序 1.1（a） 语句序列 语句 ; 1.1(c) 条件 表达式 odd 表达式 = <> < > <= >= 表达式 1.1(e) 第 2 页 共 22 页

分程序

1.1(b) 语句 1.1(d)

const , ; var , ident = number ident ; procedure ident ; ; 程序体 语句 ident := 表达式 call ident begin 语句序列 end if 条件 then 语句 while 条件 do 语句 第 3 页 共 22 页

表达式 + 项 - 1.1(f) 项 项 因子

*

因子

1.1(g) 因子 ident number ( 表达式 1.1(h) 如：{*}表示*重复任意次，{*}38表示*重复3-8次。 [ ] ：方括号表示其内的成分为任选项。 ( ) ：表示圆括号内的成分优先。 例：用EBNF描述<整数>文法的定义 ： <整数>∷=[+|-]<数字>{<数字>} <数字>∷=0|1|2|3|4|5|6|7|8|9 或更好的写法

<整数>∷=[+|-]<非零数字>{<数字>}|0 <非零数字>∷=1|2|3|4|5|6|7|8|9 <数字>∷=0|<非零数字>

第 4 页 共 22 页

+ - / )

PL/0语言文法的EBNF表示为： 〈程序〉∷=〈分程序〉．

〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉 〈常量说明部分〉∷=CONST〈常量定义〉 {，〈常量定义〉}； 〈常量定义〉∷=〈标识符〉=〈无符号整数〉 〈无符号整数〉∷=〈数字〉{〈数字〉} 〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}； 〈标识符〉∷=〈字母〉{〈字母〉|〈数字〉} 〈过程说明部分〉∷=〈过程首部〉〈分程序〉{；〈过程说明部分〉}； 〈过程首部〉∷=PROCEDURE〈标识符〉；

〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉| 〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉 〈赋值语句〉∷=〈标识符〉∶=〈表达式〉 〈复合语句〉∷=BEGIN〈语句〉{；〈语句〉}END 〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉 〈表达式〉∷=[+|-]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}

〈因子〉∷=〈标识符〉|〈无符号整数〉|'('〈表达式〉')' 〈加法运算符〉∷=+|- 〈乘法运算符〉∷=*|/

〈关系运算符〉∷=#|=|＜|＜=|＞|＞= 〈条件语句〉∷=IF〈条件〉THEN〈语句〉 〈过程调用语句〉∷=CALL〈标识符〉

〈当型循环语句〉∷=WHILE〈条件〉DO〈语句〉 〈读语句〉∷=READ'('〈标识符〉{，〈标识符〉}')' 〈写语句〉∷=WRITE'('〈表达式〉{，〈表达式〉}')' 〈字母〉∷=a|b|?|X|Y|Z 〈数字〉∷=0|1|2|?|8|9 EBNF表示的符号说明。 〈 〉：用左右尖括号括起来的中文字表示语法构造成分，或称语法单位，为非终结符。 ∷= ：该符号的左部由右部定义，可读作'定义为'。 | ：表示'或'，为左部可由多个右部定义。

{ } ：花括号表示其内的语法成分可以重复。在不加上下界时可重复0到任意次数，有上下界时为可重复次数的限制。

用语法图描述语言的语法与EBNF描述相比较： 语法图描述： 直观，易读，易写。 EBNF表示：形式化强，易机器识别。

无论用语法图或EBNF作为描述程序设计语言语法的工具，对描述的语法可以检查哪些符号序列是所给语言的合法程序，一个程序设计语言如C或JAVA，用户可用它写出成千上万个不同的程序，但C或JAVA它们各自的语法只有一个，这就使得无穷的句子集可用有穷的文法（语法）描述。 PL/0编译程序的使用限制

◇ 标识符的有效长度是10 ◇ 数字最多为14位

◇ 过程最多可嵌套三层，可递归调用

第 5 页 共 22 页

◇ 标识符的作用域同PASCAL，内层可引用包围它的外层定义的标识符（如：变量名，过程名，常量名）

目标指令有8条：

① LIT：将常量值取到运行栈顶。a域为常数值。

② LOD：将变量放到栈顶。a域为变量在所说明层中的相对位置,l为调用层 与说明层的层差值。

③ STO：将栈顶的内容送入某变量单元中。a,l域的含意同LOD指令。

④ CAL：调用过程的指令。a为被调用过程的目标程序入口地址，l为层差。

⑤ INT：为被调用的过程(或主程序)在运行栈中开辟数据区。a域为开辟的单元个数。 ⑥ JMP：无条件转移指令，a为转向地址。

⑦ JPC：条件转移指令，当栈顶的布尔值为非真时，转向a域的地址，否则顺序执行。

⑧ OPR：关系运算和算术运算指令。将栈顶和次栈顶的内容进行运算，结果存放在次栈顶，此外还可以是读写等特殊功能的指令，具体操作由a域值给出。（详见解释执行程序）。

类pcode代码指令的详细解释（指令功能表） 认识目标代码类pcode

目标代码类pcode是一种假想栈式计算机的汇编语言。 指令格式： f l a f 功能码 l 层次差 （标识符引用层减去定义层） a 根据不同的指令有所区别 指令功能表 LIT 0 a 将常数值取到栈顶，a为常数值 LOD l a 将变量值取到栈顶，a为偏移量，l为层差 STO l a 将栈顶内容送入某变量单元中，a为偏移量，l为层差 CAL l a 调用过程，a为过程地址，l为层差 INT 0 a 在运行栈中为被调用的过程开辟a个单元的数据区 JMP 0 a 无条件跳转至a地址 JPC 0 a 条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行 OPR 0 0 过程调用结束后,返回调用点并退栈 OPR 0 1 栈顶元素取反 OPR 0 2 次栈顶与栈顶相加，退两个栈元素，结果值进栈 OPR 0 3 次栈顶减去栈顶，退两个栈元素，结果值进栈 OPR 0 4 次栈顶乘以栈顶，退两个栈元素，结果值进栈 OPR 0 5 次栈顶除以栈顶，退两个栈元素，结果值进栈 OPR 0 6 栈顶元素的奇偶判断，结果值在栈顶 OPR 0 7 OPR 0 8 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈 OPR 0 9 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈 OPR 0 10 次栈顶是否小于栈顶，退两个栈元素，结果值进栈 OPR 0 11 次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈 第 6 页 共 22 页

OPR 0 12 次栈顶是否大于栈顶，退两个栈元素，结果值进栈 OPR 0 13 次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈 OPR 0 14 栈顶值输出至屏幕 OPR 0 15 屏幕输出换行 OPR 0 16 从命令行读入一个输入置于栈顶 PL/0语言可看成是PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析程序和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需生成相应的目标代码时，则调用代码生成程序。此外，用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系。用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错误性质。当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序要求输入数据和输出运行结果。

本书所提供的PL/0语言编译器的基本工作流程如图1-1所示： 源程序

词法分析

语法分析

错 符误号 诊表语义分析 断 管处理 理 代码生成

代码执行

执行结果 图1-1 PL/0编译器基本工作流程 由于PL/0编译程序采用一趟扫描方法，所以语法分析过程BLOCK是整个编译过程的核心。下面我们将在图2.4中先给出编译程序的总体流程，以弄清BLOCK过程在整个编译程序中的作用。在流程图2.4中可以看出，主程序置初值后先调用读单词过程GETSYM取一个单词，然后再调用语法分析过程BLOCK，直到遇源程序的结束符\．\为止。

第 7 页 共 22 页

语法分析过程BLOCK是整个编译过程的核心，是指开始由主程序调用GETSYM取一个单词，再调用语法分析过程BLOCK， BLOCK由当前单词根据语法规则再调用其它过程，如说明处理、代码生成或出错处理等过程进行分析，当分析完一个单词后，BLOCK再调用GETSYM取下一个单词，一直重复到当前单词为结束符\．\表明源程序已分析结束。若未取到结束符\．\，而源程序已没有输入符号，这时表明源程序有错误，无法再继续分析。

PL/0的词法分析程序GETSYM(图2.5)是一个独立的过程，其功能是为语法分析提供单词用的，是语法分析的基础，它把输入的字符串形式的源程序分割成一个个单词符号。为此PL/0编译程序设置了三个全程量的公用单元如下：

SYM：存放每个单词的类别，用内部编码形式表示。

ID：存放用户所定义的标识符的值。即标识符字符串的机内表示。 NUM：存放用户定义的数。 单词的种类有五种。

基本字：也可称为保留字或关键字，如BEGIN，END，IF，THEN等。 运算符：如：+、-、*、／、∶=、#、＞=、＜=等。 标识符：用户定义的变量名、常数名、过程名。 常数：如：10，25，100等整数。

界符：如：'，'、'.'、'；'、'('、')'等。

如果我们把基本字、运算符、界符称为语言固有的单词，而对标识符、常数称为用户定义的单词。那么经词法分析程序分出的单词，对语言固有的单词只给出类别存放在SYM中，而对用户定义的单词(标识符或常数)既给类别又给值，其类别放在SYM中，值放在ID或NUM中，全部单词种类由编译程序定义的纯量类型SYMBOL给出，也可称为语法的词汇表。如下面提到的IFSYM，THENSYM，IDENT，NUMBER均属SYMBOL中的元素。

当识别到字母开头的字母数字串时，先查关键字表。若查不到则为标识符，查到则为关键字。PL/0编译程序文本中主程序开始对关键字表置初值如下： 关键字表为：

word[1]:='begin '；word[2]:='call '； ...

word[13]:='write '；

每个数组元素的字符长度为10，不满10个字符时，以空格补满。 查到时找到关键字相应的内部表示为： Wsym[1]:=beginsym; wsym[2]:=callsym； ?

wsym[13]:=writesym；

PL/0编译程序文本中开始对类型的定义中给出单词定义为： type symbol=(nul,ident,number,plus,?,varsym,procsym)； 定义单词是纯量/枚举类型，又定义了3个全程量为： sym:symbol; id:alfa;

num:integer;

因此词法分析程序GETSYM将完成下列任务：

(1) 滤空格：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是无用的，所以必须滤掉。

(2) 识别保留字：设有一张保留字表。对每个字母打头的字母、数字字符串要查此表。若查着则为保留字，将对应的类别放在SYM中。如IF对应值IFSYM，THEN对应值为THENSYM。若查不着，则认为是

第 8 页 共 22 页

用户定义的标识符。

(3) 识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放在ID中。

(4) 拼数：当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值存放在NUM中。 (5) 拼复合词：对两个字符组成的算符

如：＞=、∶=、＜= 等单词，识别后将类别送SYM中。

(6) 输出源程序：为边读入字符边输出(可输出在文件中)。 GETCH 所用单元说明：

CH： 存放当前读取的字符，初值为空。

LINE： 为一维数组，其数组元素是字符，界对为1∶80。用于读入一行字符的缓冲区。 LL和CC为计数器，初值为0。 GETSYM流程图的工作单元说明：

A：一维数组，数组元素为字符，界对[1∶10]。 ID：同A。

WORD：保留字表，一维数组，数组元素是以字符为元素的一维数组。界对为[1∶13]。查表方式采用二分法。

单个字符对应的单词表的建立是，首先在主程序中定义了下标为字符的数组ssym，数组ssym的元素为单词，主程序开始对下标为字符的所有数组元素置初值为nul，对PL/0语言用到的单个字符为单词的，将其字符作为数组下标的元素置初值为对应的单词。如： ssym['+']:=plus; ssym['-']:=minus; ?

ssym[';']:=semicolon; PL/0编译程序的语法分析

PL/0编译程序语法、语义分析是整个编译程序设计与实现的核心部分,要求学员努力学习掌握实现技术和方法。现分别说明语法分析实现的主要思想方法和语义分析的实现。

语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则。PL/0语言的文法规则已在2.1节中给出。本节将以语法图描述的语法形式为依据，给出语法分析过程的直观思想。

PL/0编译程序的语法分析采用了自顶向下的递归子程序法。 什么是自顶向下的语法分析？

可形象地对该程序自顶向下构造一棵倒挂着的语法分析树，其构造方法是：

（1） 由开始符号非终结符'程序'作为分析树的根结点，由非终结符'程序'规则的右部为子结点。 （2） 对分析树中的每个非终结符结点，选择它规则的一个右部为子结点构造分析树的下一层。 （3） 重复（2）直到分析树中的末端结点只有终结符。

（4） 若分析树中的末端结点从左到右连接的终结符号串刚好是输入的程序终结符号串，则说明所给程序在语法上是正确的。

粗略地说：自顶向下的递归子程序法就是对应每个非终结符语法单元，编一个独立的处理过程(或子程序)。语法分析从读入第一个单词开始由非终结符'程序'即开始符号出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看也就进入了一个语法单元，再沿当前所进入的语法描述图的箭头方向进行分析，当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，则执行相应的语义程序(就是翻译程序)。再读取下一个单词继续分析。遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较，若都不匹配时，可能是进入下一非终结符语法单位或是出错。

如果一个PL/0语言的单词序列在整个语法分析中，都能逐个得到匹配，直到程序结束符'.'，这时就说所输入的程序是正确的。对于正确的语法分析做相应的语义翻译，最终得出目标程序。

第 9 页 共 22 页

以上所说语法分析过程非常直观粗浅，实际上应用递归子程序法构造语法分析程序时，对文法有一定的要求和限制，这个问题我们将在第5章详细讨论。

此外，从PL/0的语法描述图中可以清楚地看到，当对PL/0语言进行语法分析时，各个非终结符语法单元所对应的分析过程之间必须存在相互调用的关系。这种调用关系可用图1-2表示。也可称为PL/0语法的依赖图，在图中箭头所指向的程序单元表示存在调用关系，从图中不难看出这些子程序在语法分析时被直接或间接递归调用。

由图1-2PL/0语法调用关系图可以看出对分程序和语句为直接递归调用，对表达式为间接递归调用。

程序

程序体 语句

条件 表达式

项 因子 图1-2 语法分析过程依赖关系 表达式的EBNF

〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} 〈项〉∷=〈因子〉{（*|/）〈因子〉}

〈因子〉∷=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’ 〈表达式〉的递归子程序实现

procedure expr; begin

if sym in [ plus, minus ] then begin

getsym; term; end

else term;

第 10 页 共 22 页

while sym in [plus, minus] do begin

getsym; term; end end;

〈项〉的递归子程序实现

procedure term; begin

factor;

while sym in [ times, slash ] do begin

getsym; factor; end end;

〈因子〉的递归子程序实现

procedure factor; begin

if sym <> ident then begin

if sym <> number then begin

if sym = ‘(‘ then begin

getsym; expr;

if sym = ‘)’ then getsym else error end

else error end end end;

语法分析程序除总控外主要有两大部分的功能，即对说明部分的处理和对程序体部分的处理，也就是在语法单元中的分程序功能。

PL/0编译程序语法、语义分析的的核心程序是BLOCK过程，在BLOCK过程内又定义了许多嵌套及并列的过程。

在过程BLOCK内对说明部分及程序体部分的分析说明如下： (1) 说明部分的分析

由于PL/0语言允许过程调用语句，且允许过程嵌套定义。因此每个过程应有过程首部以定义局部于它自己过程的常量、变量和过程标识符，也称局部量。每个过程所定义的局部量只能供它自己和它自己定义的内过程引用。对于同一层并列过程的调用关系是先定义的可以被后定义的引用，反之则不行。

第 11 页 共 22 页

说明部分的处理任务就是对每个过程的说明对象造名字表，填写所在层次、标识符的属性和分配的相对位置等。标识符的属性不同时，所需要填写的信息也有所不同。登录信息是调用ENTER过程完成的。 说明部分的处理对主程序看成是第0层过程，主程序定义的过程为第1层，随着嵌套的深度增加而层次数加大。PL/0允许最大层次为3。

所造名字表放在全程量一维数组TABLE表中。TX为索引表的指针，表中的每个元素为记录型数据。LEV给出层次，DX给出每层局部量当前已分配到的相对位置，可称地址指示器，每说明完一个变量后DX指示器加1。

PL/0编译程序文本中对名字表定义有： 说明类型的定义：

type object= (constant, variable, procedur) （定义为纯量/枚举类型） 名字表的定义：

table:array[0..txmax] of record name:alfa;

case kind:object of

constant:(val:integer);

variable:procedur:(level,adr,size:integer); end；

例如：一个过程的说明部分为： CONST A=35,B=49； VAR C，D，E； PROCEDUREP； VAR G, ...

对常量，变量和过程说明分析后，在TABLE表中的信息如表2.2所示。

在说明处理后TABLE表中的信息对于过程名的ADR域，是在过程体的目标代码生成后再反填过程体的入口地址。例中在处理P过程的说明时对LEV就增加1。在P过程中的变量名的层次为LEV+1后的值。对过程还有一项数据SIZE，是记录该过程体运行时所需的数据空间。至于在造表和查表的过程中，如何保证每个过程的局部量不被它的外层引用，请读者阅读完PL/0编译程序后自己总结。 (2) 过程体的分析

程序的主体是由语句构成的。处理完过程的说明后就处理由语句组成的过程体，从语法上要对语句逐句分析。当语法正确时就生成相应语句功能的目标代码。当遇到标识符的引用时就调用POSITION函数查TABLE表，看是否有过正确的定义，若已有，则从表中取相应的有关信息，供代码的生成用。若无定义则出错。

PL/0编译程序的目标代码结构和代码生成

编译程序的目标代码是在分析程序体时生成的，在处理说明部分时并不生成目标代码，而当分析程序体中的每个语句时，当语法正确则调用目标代码生成过程以生成与PL/0语句等价功能的目标代码，直到编译正常结束。

PL/0语言的代码生成是由过程GEN完成的。GEN过程有三个参数，分别代表目标代码的功能码、层差和位移量(对不同的指令含意不同)。生成的代码顺序放在数组CODE中。CODE为一维数组，数组元素为记录型数据。每一个记录就是一条目标指令。CX为指令的指针，由0开始顺序增加。实际上目标代码的顺序是内层过程的排在前边，主程序的目标代码在最后。下面我们给出一个PL/0源程序和对应的目标程序的清单。

PL/0编译程序的目标代码生成是由GEN过程完成的 ，当语法分析正确则调用目标代码生成过程以生成与PL/0语句等价功能的目标代码，直到编译正常结束。 除了过程说明部分外，变量和常量的说明都不

第 12 页 共 22 页

产生目标代码。在block入口处生成一条(jmp,0,0)指令，作为过程体入口指令，该指令的第3区域的'0'需分析到过程体入口时才返填。目标代码生成时所用到的变量地址和层差等信息是由名字表table提供的，而名字表的信息是在说明时填写的。在代码生成时查名字表，这就是表格管理的作用。这些信息之间的连接关系学员必须弄清。下面对一些重要程序段给予扼要的解释。（gen过程的实现很简单不再解释）

对分程序体人口的处理（见程序文本block 的过程体） begin (*block*) dx:=3;

tx0:=tx; （*保留当前table表指针值,实际为过程名在table表中的位置*） table[tx].adr:=cx;（*保留当前code指针值到过程名的adr域*） gen(jmp,0,0);

（*生成转向过程体入口的指令，该指令的地址为cx已保留在过程名的adr域，真正的过程体入口地址，等生成过程体入口的指令时，再由table[tx].adr中取出 cx将过程体入口返填到cx所指目标代码，即:（jmp,0,0）的第3区域，同时填到table[tx].adr 中*) 程体入口时的处理

code[table[tx0].adr].a:=cx;（cx为过程入口地址，填写在code中） with table[tx0] do begin

adr:=cx; （过程的入口填写在table表的过程名中） size:=dx; （过程需要的空间填写在table中） end;

cxo:=cx; （保留过程在code中的入口地址在输出目标代码时用） gen(int,0,dx);（生成过程入口指令）

请特别注意dx、 tx、 cx的作用和如何处理信息之间的连接关系。 PL/0编译程序的语法错误处理

编写一个程序，往往难于一次成功，常常会出现各种类型的错误。一般有语法错、语义错及运行错。出错的原因是多方面的，这就给错误处理带来不少困难。就语法错来说，任何一个编译程序在进行语法分析遇到错误时，总不会就此停止工作，而是希望能准确地指出出错位置和错误性质并尽可能进行校正，以便使编译程序能继续工作。但对所有的错误都做到这样的要求是很困难的，主要困难在校正上，因为编译程序不能完全确定程序人员的意图。例如在一个表达式中，圆括号不配对时，就不能确定应补在何处。有时由于校正得不对反而会影响到后边，导致出现误判错误的情况。因此编译程序只能采取一些措施，对源程序中的错误尽量查出，加以修改，以便提高调试速度。 PL/0编译程序对语法错误的处理采用两种办法：

(1) 对于一些易于校正的错误，如丢了逗号、分号等，则指出出错位置，并加以校正。校正的方式就是补上逗号或分号。

(2) 对某些错误编译程序难于确定校正的措施，为了使当前的错误不致影响整个程序的崩溃，把错误尽量局限在一个局部的语法单位中。这样就需跳过一些后面输入的单词符号，直到读入一个能使编译程序恢复正常语法分析工作的单词为止。具体做法是：当语法分析进入以某些关键字(保留字)或终结符集合为开始符的语法单元时，通常在它的入口和出口处，调用一个测试程序TEST(见图2.9)。例如：语句的开始符是begin，if，while，call，read，write；说明的开始符是var，const，procedure；因子的开始符是\，ident，number。当语法分析进入这样的语法单元前，可用测试程序检查当前单词符号是否属于它们开始符号的集合，若不是则出错。

请读者对照图 2.1各语法描述图直观地找出每个非终结符语法单元的开始符号集合，与表2.3进行

第 13 页 共 22 页

比较，验证对开始符号集合理解的正确性。对于一个文法符号的开始符号集合的形式定义将在第5章详细介绍。现给出PL/0文法部分非终结符语法单元的开始符号和后继符号的集合。 另外由于PL/0编译程序采用自顶向下的分析方法，一个语法单元分析程序调用别的语法单元的分析程序时，以参数形式(文本中以FSYS定义为单词符号集合作为形参)给出被调用的语法分析程序出口时合法的后继单词符号集合(如表2.3所给出)，在出口处也调用测试程序。若当前单词符号是属于所给集合，则语法分析正常进行，否则出错。单词符号集合FSYS参数是可传递的，随着调用语法分析程序层次的深入，FSYS的集合逐步补充合法单词符。 非终结符（S） FIRST(S) FOLLOW(S) 程序体 const var procedure ident . ; call if begin while 语句 ident call begin if while . ; end 条件 odd + - ( ident number then do 表达式 + - ( ident number . ; ) R end then do 项 ident number ( . ; ) R + - end then do 因子 ident number ( . ; ) R + - * / end then do *注： 表2.3中' R '表示关系运算符集合,如=，＃，＜，＜=，＞，＞=。

在进入某个语法单位时，调用TEST,检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。 在语法单位分析结束时，调用TEST,检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于，则滤去后继符号和开始符号集合外的所有符号。 TEST测试过程有三个参数，它们的含意是： ① S1：当语法分析进入或退出某一语法单元时当前单词符号应属于的集合，它可能是一个语法单元开始符号的集合或后继符号的集合。 ② S2：在某一出错状态时，可恢复语法分析继续正常工作的补充单词符号集合。因为当语法分析出错时，即当前单词符号不在S1集合中，为了继续编译，需跳过后边输入的一些单词符号，直到当前输入的单词符号是属于S1或S2集合的元素。 ③ n:整型数，出错信息编号。 为了进一步明确S1，S2集合的含意，现以因子(FACTOR)的语法分析程序为例，在过程FACTOR的入口处调用了一次TEST过程，它的实参S1是因子开始符号的集合(文本中的FACBEGSYS)。S2是每个过程的形参FSYS调用时实参的传递值。当编译程序第一次调用BLOCK时，FSYS实参为[·]与说明开始符和语句开始符集合的和。以后随着调用语法分析程序层次的深入逐步增加。如调用语句时增加了[；]和[endsym],在表达式语法分析中调用项时又增加了[+]和[-]，而在项中调用因子时又增加了[*]和[/]，这样在进入因子分析程序时即使当前符号不是因子开始符，出错后只要跳过一定的符号，遇到当时输入的单词符号在FSYS中或在因子开始符号集合中，均可继续正常进行语法分析。而在因子过程的出口处也调用了测试程序，不过这时S1和S2实参恰恰相反。说明当时的FSYS集合的单词符号都是因子正常出口时允许的单词符号，而因子的开始符号为可恢复正常语法分析的补充单词符号。 从PL/0编译程序文本中因子过程的处理片段说明上述问题。

（1）PL/0编译程序文本中给出关于某些语法单位开始符号集合的定义为： symset=set of symbol; （见PL/0文本类型说明部分） declbegsys, statbegsys, facbegsys:symset;

declbegsys:=[constsym,varsym,procsym];（见PL/0文本主程序置初值部分） statbegsys:=[beginsym,callsym,ifsym,whilesym,readsym,writesym]; facbegsys:=[ident,number,lparen];

（2）后继符号集合fsys作为参数传递（见PL/0文本相应过程的说明部分）

第 14 页 共 22 页

procedure test(s1,s2:symset; n:integer);

procedure block(lev,tx:integer; fsys:symset); procedure statement(fsys:symset); procedure expression (fsys:symset); procedure term (fsys:symset); procedure factor (fsys:symset); （3）因子过程的处理片段 test过程有三个参数：

可允许的下一个符号集合S1，如果当前符号不在此集合中，当即得到一个错误号；

另加的停止符号集合S2，有些符号的出现，虽然无疑是错的，但它们绝对不应被忽略而跳过； 整数n，表示有关错误的诊断号：

void test(symset s1, symset s2, int n) {

symset s;

if (! inset(sym, s1)) {

error(n);

s = uniteset(s1, s2); while(! inset(sym, s)) getsym(); destroyset(s); } }

（4）由于后继符号集合fsys作为参数传递，随着调用语法分析程序层次的深入后继符号集合逐步增加，但对调用同一个过程所需增加的后跟符与调用位置有关。例如： 在write语句和factor中调用expression(fsys);所增加的后继符号不完全相同。

· write语句的语法：<写语句> ∷= write({,});

处理在（ ）内调用expression时在fsys中应增加 rparen,comma。 expression([rparen,comma]+fsys);

· factor的语法：<因子>∷=...|'(' exp ')

在处理（ ）内调用expression时在fsys中应增加rparen。 expression([rparen]+fsys);

然而PL/0编译程序对测试程序TEST的调用有一定的灵活性。对语义错误，如标识符未加说明就引用，或虽经说明，但引用与说明的属性不一致。这时只给出错误信息和出错位置，编译工作可继续进行。而对运行错，如溢出，越界等，只能在运行时发现，由于PL/0编译程序的功能限制无法指出运行错在源程序中的错误位置。

出错编号 出错原因 1： 常数说明中的\写成\ 2： 常数说明中的\后应是数字。 3： 常数说明中的标识符后应是\。 4： const ,var, procedure后应为标识符。 5： 漏掉了'，'或'；'。

第 15 页 共 22 页

6： 过程说明后的符号不正确(应是语句开始符，或过程定义符)。 7： 应是语句开始符。 8： 程序体内语句部分的后跟符不正确。 9： 程序结尾丢了句号'.'。 10： 语句之间漏了'；'。 11： 标识符未说明。 12： 赋值语句中，赋值号左部标识符属性应是变量。 13： 赋值语句左部标识符后应是赋值号'∶='。 14： call后应为标识符。 15： call后标识符属性应为过程。 16： 条件语句中丢了'then'。 17： 丢了'end\或'；'。 18： while型循环语句中丢了'do'。 19： 语句后的符号不正确。 20： 应为关系运算符。 21： 表达式内标识符属性不能是过程。 22： 表达式中漏掉右括号')'。 23： 因子后的非法符号。 24： 表达式的开始符不能是此符号。 31： 数越界。 32： read语句括号中的标识符不是变量。

PL/0编译程序的目标代码解释执行时的存储分配

当源程序经过语法分析，如果未发现错误时，由编译程序调用解释程序，对存放在CODE中的目标代码CODE[0]开始进行解释执行。当编译结束后，记录源程序中标识符的TABLE表已没有作用。

因为计算每个变量在运行栈中相对本过程基地址的偏移量dx 的值，放在table表中的adr域，生成目标代码时再从adr域中取出基地址的偏移量 ，放在code中的a域。

因此数据空间只需以数组CODE存放的只读目标程序和运行时的数据栈S。S是由解释程序定义的一维整型数组。由于PL/0语言的目标程序是一种假想的栈式计算机的汇编语言，仍用PASCAL语言解释执行。解释执行时的数据空间S为栈式计算机的存储空间。遵循后进先出规则，对每个过程(包括主程序)当被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。 解释程序还定义了4个寄存器。

(1) I：指令寄存器。存放着当前正在解释的一条目标指令。

(2) P：程序地址寄存器。指向下一条要执行的目标程序的地址(相当目标程序CODE数组的下标)。 (3) T：栈顶寄存器。由于每个过程当它被运行时，给它分配的数据空间(下边称数据段)可分成两部分。

静态部分：包括变量存放区和三个联系单元(联系单元的作用见后)。

动态部分：作为临时工作单元和累加器用。需要时随时分配，用完后立即释放。栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。 (4) B：基址寄存器。指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。

为了实现对每个过程调用时给它分配数据段，也就是对即将运行的过程所需数据段进栈；过程运行结束后释放数据段，即该数据段退栈；以及嵌套过程之间对标识符引用的寻址问题。每个过程被调用时，在栈顶分配三个联系单元，这三个单元存放的内容分别为：

(1) SL：静态链：它是指向定义该过程的直接外过程(或主程序)运行时最新数据段的基地址。

第 16 页 共 22 页

(2) DL：动态链：它是指向调用该过程时正在运行过程的数据段基地址。

(3) RA：返回地址：记录调用该过程时目标程序的断点，即当时的程序地址寄存器P的值。也就是调用过程指令的下一条指令的地址。

具体的过程调用和结束，对上述寄存器及三个联系单元的填写和恢复由下列目标指令完成。 (1) INT 0 A

每个过程目标程序的入口都有这样一条指令，用以完成开辟数据段的工作。A域的值指出数据段的大小，即为局部变量个数+3(联系单元个数为3)。由编译程序的代码生成给出。开辟数据段的结果是改变栈顶寄存器T的值，即T∶=T+A；。 (2) OPR 0 0

是每个过程出口处的一条目标指令。用以完成该过程运行结束后释放数据段的工作，即退栈工作。恢复调用该过程前正在运行的过程(或主程序)的数据段基地址寄存器的值，和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。 (3) CAL L A；

为调用过程的目标指令，其中

L： 为层次差，它是寻找静态链的依据。在解释程序中由BASE(L)函数来计算，L为参数，实参为所给层差。

A： 为被调用过程的目标程序入口。

CAL指令还完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。 由于PL/0编译程序是用PASCAL语言编写的(若文件名为PL0.PAS)，所以要对PL/0语言的源程序进行编译，如在PC机上，首先必须对PL0.PAS进行编译、汇编、连接得到PL0.EXE文件。运行PL0.EXE文件才是启动PL/0的编译程序。因此执行命令。

RUN PL0<回车>启动PL/0编译程序，输出一些询问信息，需用户回答。 输出信息 回答信息

INPUT FILE? PL/0源程序文件名<回车> LIST OBJECT CODE? Y或N<回车>

目标程序输出的次序是，最内层的过程体在最前边，主程序体在最后。源程序清单中的序号，是该语句在目标程序中对应的起始位置。但需指出例题中序号为0，1指令的内容为： 0 jmp 0 8 8为主程序入口 1 jmp 0 2 2为过程P的入口 三、实验结果：

测试文件TEXT.TXT： const m=7, n = 85; var x, y, z;

procedure multiply; var a, b; begin

a := x ; b := y ; z := 0; while b > 0 do begin

if odd b then z := z + a; a := 2 * a; b := b / 2; end

第 17 页 共 22 页

end;

begin

x := m; y := n; call multiply; end.

乘法过程经过编译程序产生以下代码：

2 INT 3 LOD 1 4 STO 5 LOD 1 6 STO 7 LIT 8 STO 9 LOD 0 10 LIT 11 OPR 12 JPC 13 LOD 0 14 OPR 15 JPC 16 LOD 1 17 18 19 20

LOD 0 OPR STO LIT

0 3 0 4 0 0 1 4 0 0 0 4 0 0 5 3 0 1 0 3 0 0 4 0 0 0 0 0

5

-- allocate storage

a := x b := y z := 0

-- x

3 -- a -- y 4 0

-- b -- 0

5 -- z -- b 0 -- 0 12 -- >

b > 0

29 -- if b <= 0 then goto 29 -- b

odd(b)

6 -- odd

20 -- if not(odd(b)) goto 20 -- z -- 2 5 2

a

-- + -- z -- 2

z := z + a

while

if

21 LOD 0 22 OPR 23 STO 24 LOD 0 25 LIT 26 OPR 27 STO 28 JMP 29 OPR

-- a

4 -- * 3 -- a -- b

2 -- 2 2 4 9 0

-- / -- b

a := 2 * a

b := b / 2

-- goto 9 -- return

上述代码采用助记符形式，“--”后面是为了便于理解而额外加上的注释，大括号右边为左部代码序列对应的源程序中的语句或表达式。 结果图：

第 18 页 共 22 页

第 19 页 共 22 页

。。。。。。。。。。。。 测试文件EX1.TXT： const m = 7, n = 85; var x, y, z, q, r; procedure multiply; var a, b;

procedure plus; var ss;

第 20 页 共 22 页

procedure plusplus; var s; begin

s := ss; end; begin

ss :=x end; begin

a := x; b := y; z := 0; while b > 0 do begin

if odd b then z := z + a; a := 2 * a; b := b / 2; end end; begin

x := n; y := m; call plusplus; end.

测试文件EXAMPLE.TXT： const m = 7, n = 85; var x, y, z, q, r; procedure multiply; var a, b;

procedure plus; var ss;

procedure plusplus; var s; begin

s := x end; begin

ss :=x end; begin

a := x; b := y; z := 0; while b > 0 do begin

if odd b then z := z + a; a := 2 * a; b := b / 2; end end;

procedure divide; var w;

第 21 页 共 22 页

begin

r := x; q := 0; w := y; while w > y do begin

q := 2 * q; w := w / 2; if w <= r then begin

r := r - w; q := q + 1; end; end end;

procedure gcd; var f, g; begin

f := x; g := y;

while f <> g do begin

if f < g then g := g - f; if g < f then f := f - g; end end; begin

x := m; y := n; call plus;

x := n; y := m; call plusplus; x := 25; y := 3; call divide; x := 34; y := 36; call gcd; end.

四、心得体会

修改了很细节的东西，有老师说的block_dx = dx，block是PL0的核心，他的很多代码都直接关系到说明部分的处理和对程序体部分的处理，他的代码很经典，看PL0真的要很细心，对没行都细嚼慢咽你会恍然大悟—原来是这样。不过我对base还不是很了解，即使老师说了b = stack[b]的意思，在程序中修改的部分我用中文标记了，这是我的改法，出来是对的，跟指导书结果一致。还有很多地方没细看，这是个值得一看的代码，基本上很容易懂，可是综合理解就看自己的水平了。

第 22 页 共 22 页

本文来源：https://www.bwwdw.com/article/gujr.html