编译原理课程设计报告

南京航空航天大学

编译原理课程设计

题目一个PASCAL语言子集（PL/0）编译器的设计与实现

专业

班 号

学号

姓名

指导老师

答辩日期2014年1月

1设计的题目

一个PASCAL语言子集（PL/0）编译器的设计与实现 2课程设计的要求

PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。

PL/0的编译程序和目标程序的解释执行程序都是用C语言书写的，因此PL/0语言可在配备C语言编译器的任何机器上实现。

其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。

用表格管理程序建立变量、常量和过程标示符的说明与引用之间的信息联系。

用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。

当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。

3设计任务:

PL/0语言文法的EBNF（巴克斯-瑙尔范式）表示 〈表达式〉::=[+|-]〈项〉{〈加法运算符〉〈项〉} 〈项〉::=〈因子〉{〈乘法运算符〉〈因子〉}

〈因子〉::=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’ 〈加法运算符〉::=+|-

〈乘法运算符〉::=*|/

〈关系运算符〉::==|#||>=

〈条件语句〉::=IF〈条件〉THEN〈语句〉

〈过程调用语句〉::=CALL〈标识符〉

〈当型循环语句〉::=WHILE〈条件〉DO〈语句〉

〈读语句〉::=READ‘（’〈标识符〉{，〈标识符〉}‘）’ 〈写语句〉::=WRITE‘（’〈表达式〉{，〈表达式〉}‘）’ 〈字母〉::=a|b|…|X|Y|Z

〈数字〉::=0|1|…|8|9

PL/0语言可以看成PASCAL语言的子集，它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言，与具体计算机无关。

PL/0的编译程序和目标程序的解释执行程序都是用PASCAL语言书写的，因此PL/0语言可在配备PASCAL语言的任何机器上实现。

其编译过程采用一趟扫描方式，以语法分析程序为核心，词法分析和代码生成程序都作为一个独立的过程，当语法分析需要读单词时就调用词法分析程序，而当语法分析正确需要生成相应的目标代码时，则调用代码生成程序。

用表格管理程序建立变量、常量和过程表示符的说明与引用之间的信息联系。

用出错处理程序对词法和语法分析遇到的错误给出在源程序中出错的位置和错位性质。

当源程序编译正确时，PL/0编译程序自动调用解释执行程序，对目标代码进行解释执行，并按用户程序的要求输入数据和输出运行结果。

4原理与框图

(1).PL/0编译程序功能的框图

PL/0的编译程序包括了对PL/0语言源程序进行分析处理、编译生成类PCODE代码，并在虚拟机上解释运行生成的类PCODE代码的功能。

输入 输出

（2）. PL/0编译程序的总体设计

PL/0语言编译程序采用以语法分析为核心、一遍扫描的编译方法。词法分析和代码生成作为独立的子程序供语法分析程序调用。当语法

分析需要读单词时就调用词法分析程序，而当语法、语义分析正确，需要生成相应的目标代码时，则调用代码生成程序。语法分析的同时，提供了出错报告和出错恢复的功能。在源程序没有错误编译通过的情况下，调用类PCODE解释程序解释执行生成的类PCODE代码

（3）词法分析子程序分析：

词法分析子程序名为getsym，功能是从源程序中读出一个单词符号（token），把它的信息放入全局变量sym、id和num中，语法分析器需要单词时，直接从这三个变量中获得。（语法分析器每次用完这三个变量的值就立即调用getsym子程序获取新的单词供下一次使用。而不是在需要新单词时才调用getsym过程。）getsym过程通过反复调用getch子过程从源程序过获取字符，并把它们拼成单词。getch过程中使用了行缓冲区技术以提高程序运行效率。

词法分析器的分析过程：调用getsym时，它通过getch过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把sym变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把sym置为ident，把这个单词存入id变量。查保留字表时使用了二分法查找以提高效率。如果getch获得的字符是数字，则继续用getch获取数字，并把它们拼成一个整数，然后把sym置为number，并把拼成的数值放入num变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等），则把sym则成相应的类型。如果遇到不合法的字符，把sym置成nul。

（4）语法分析子程序

语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语意生成相应的代码，并提供了出错处理的机制。语法分析主要由分程序分析过程（block）、常量定义分析过程（constdeclaration）、变量定义分析过程（vardeclaration）、语句分析过程（statement）、表达式处理过程（expression）、项处理过程（term）、因子处理过程（factor）和条件处理过程（condition）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出

错报告过程（error）、代码生成过程（gen）、测试单词合法性及出错恢复过程（test）、登录名字表过程（enter）、查询名字表函数（position）以及列出类PCODE代码过程（listcode）作过语法分析的辅助过程。

由PL/0的语法图可知：一个完整的PL/0程序是由分程序和句号构成的。因此，本编译程序在运行的时候，通过主程序中调用分程序处理过程block来分析分程序部分（分程序分析过程中还可能会递归调用block过程），然后，判断最后读入的符号是否为句号。如果是句号且分程序分析中未出错，则是一个合法的PL/0程序，可以运行生成的代码，否则就说明源PL/0程序是不合法的，输出出错提示即可。

（5）下面按各语法单元分析PL/0编译程序的运行机制：

分程序处理过程：

语法分析开始后，首先调用分程序处理过程（block）处理分程序。过程入口参数置为：0层、符号表位置0、出错恢复单词集合为句号、声明符或语句开始符。进入block过程后，首先把局部数据段分配指针设为3，准备分配3个单元供运行期存放静态链SL、动态链DL和返回地址RA。然后用tx0记录下当前符号表位置并产生一条jmp指令，准备跳转到主程序的开始位置，由于当前还没有知道主程序究竟在何处开始，所以jmp的目标暂时填为0，稍后再改。同时在符号表的当前位置记录下这个jmp指令在代码段中的位置。在判断了嵌套层数没有超过规定的层数后，开始分析源程序。首先判断是否遇到了常量声明，如果遇到则开始常量定义，把常量存入符号表。接下去用同样的方法分析变量声明，变量定义过程中会用dx变量记

录下局部数据段分配的空间个数。然后如果遇到procedure保留字则进行过程声明和定义，声明的方法是把过程的名字和所在的层次记入符号表，过程定义的方法就是通过递归调用block过程，因为每个过程都是一个分程序。由于这是分程序中的分程序，因此调用block时需把当前的层次号lev加一传递给block过程。分程序声明部分完成后，即将进入语句的处理，这时的代码分配指针cx的值正好指向语句的开始位置，这个位置正是前面的jmp指令需要跳转到的位置。于是通过前面记录下来的地址值，把这个jmp指令的跳转位置改成当前cx的位置。并在符号表中记录下当前的代码段分配地址和局部数据段要分配的大小（dx的值）。生成一条int指令，分配dx个空间，作为这个分程序段的第一条指令。下面就调用语句处理过程statement分析语句。分析完成后，生成操作数为0的opr指令，用于从分程序返回（对于0层的主程序来说，就是程序运行完成，退出）。

常量定义过程：

通过循环，反复获得标识符和对应的值，存入符号表。符号表中记录下标识符的名字和它对应的值。

变量定义过程：

与常量定义类似，通过循环，反复获得标识符，存入符号表。符号表中记录下标识符的名字、以及它所在的层与它所在层的偏移地址。

语句处理过程：

语句处理过程是一个嵌套子程序，通过调用表达式处理、项处理、因子处理等过程及递归调用自己来实现对语句的分析。语句处理过程可以识别的语句包括赋值语句、read语句、write语句、call语句、if语句、while语句。当遇到begin/end语句时，就递归调用自己来分析，分析的同时生成相应的类PCODE指令。

赋值语句的处理：

首先获取赋值号左边的标识符，从符号表中找到它的信息，并确认这个标识符确为变量名。然后通过调用表达式处理过程算得赋值号右部的表达式的值并生成相应的指令保证这个值放在运行期的数据栈顶。最后通过前面查到的左部变量的位置信息，生成相应的sto指令，把栈顶值移入指定的地址空间，实现了赋值操作。

read语句的处理：

确定read语句语法合理的前提下（否则报错），生成相应的指令：

第一条是16号操作的opr指令，实现从标准输入设备上读一个整数值，放在数据栈顶。第二条是sto指令，把栈顶的值存入read语句括号中的变量所在的单元。

write语句的处理：

与read语句相似。在语法正确的前提下，生成指令：通过循环

调用表达式处理过程分析write语句括号中的每一个表达式，生成相应指令保证把表达式的值算出并放到数据栈顶并生成14号操作的opr指令，输出表达式的值。最后生成15号操作的opr指令输出一个换行。

call语句的处理：

从符号表中找到call语句右部的标识符，获得其所在层次和偏移地址。然后生成相应的cal指令。至于调用子过程所需的保护现场等工作是由类PCODE解释程序在解释执行cal指令时自动完成的。

if语句的处理：

按if语句的语法，首先调用逻辑表达式处理过程处理if语句的条件，把相应的真假值放到数据栈顶。接下去记录下代码段分配位置（即下面生成的jpc指令的位置），然后生成条件转移jpc指令（遇0或遇假转移），转移地址未知暂时填0。然后调用语句处理过程处理then语句后面的语句或语句块。then后的语句处理完后，当前代码段分配指针的位置就应该是上面的jpc指令的转移位置。通过前面记录下的jpc指令的位置，把它的跳转位置改成当前的代码段指针位置。

begin/end语句的处理：

通过循环遍历begin/end语句块中的每一个语句，通过递归调用语句分析过程分析并生成相应代码。

while语句的处理：

首先用cx1变量记下当前代码段分配位置，作为循环的开始位置。然后处理while语句中的条件表达式生成相应代码把结果放在数据栈顶，再用cx2变量记下当前位置，生成条件转移指令，转移位置未知，填0。通过递归调用语句分析过程分析do语句后的语句或语句块并生成相应代码。最后生成一条无条件跳转指令jmp，跳转到cx1所指位置，并把cx2所指的条件跳转指令的跳转位置改成当前代码段分配位置。

（5）假想目标机的代码

其中：F段代表伪操作码

L段代表调用层与说明层的层差值

A段代表位移量（相对地址）

进一步说明：

INT：为被调用的过程（包括主过程）在运行栈S中开辟数据区，这

时A段为所需数据单元个数（包括三个连接数据）；L段恒为0。 CAL：调用过程，这时A段为被调用过程的过程体（过程体之前一

条指令）在目标程序区的入口地址。

LIT：将常量送到运行栈S的栈顶，这时A段为常量值。

LOD：将变量送到运行栈S的栈顶，这时A段为变量所在说明层中的相对位置。

STO：将运行栈S的栈顶内容送入某个变量单元中，A段为变量所在

说明层中的相对位置。

JMP：无条件转移，这时A段为转向地址（目标程序）。

JPC：条件转移，当运行栈S的栈顶的布尔值为假（0）时，则转向

A段所指目标程序地址；否则顺序执行。

OPR：关系或算术运算，A段指明具体运算，例如A=2代表算术运

算“＋”；A＝12代表关系运算“>”；A＝16代表“读入”操作等等。运算对象取自运行栈S的栈顶及次栈顶。

(6) 活动记录

RA：返回地址

DL：调用者的活动记录首地址

SL：保存该过程直接外层的活动记录首地址

过程返回可以看成是执行一个特殊的OPR运算

注意：层次差为调用层次与定义层次的差值

（7）目标代码生成

LIT 0 ,a 取常量a放入数据栈栈顶

OPR 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的指令

RED L ,a 读数据并存入变量（相对地址为a，层次差为L）

WRT 0 ,0 将栈顶内容输出

OPR 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 ，8 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈

OPR 0 ，9 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈

OPR 0 ，10次栈顶是否小于栈顶，退两个栈元素，结果值进栈

OPR 0 ，11次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈 OPR 0 ，12次栈顶是否大于栈顶，退两个栈元素，结果值进栈

OPR 0 ，13次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈

5.试验体会

程序测试

源程序:

const a=10;

varb,c;

array h[2];

procedure p(var d);

var e;

begin

e:=d+a;

h[0]:=e;

h[1]:=e+10;

write(h[1]);

h[0]+=h[1];

h[1]-=5;

if b>5 then

return 20;

else

return ++e;

end;

begin

b:='a';

write(b);

read(b);

repeat

begin

c:=call p(b++);

write(h[0]);

write(h[1]);

write(b);

write(--b);

write(c);

read(b);

end

dowhile b0

end.

运行结果：

6.心得体会

经过了不止一周的夜以继日的艰苦奋斗，编译原理课程设计总算告一段落。今年已经大三，编写过不少的程序，但这次是真真切切的感觉到了一个程序复杂令人头疼的程度。要编写一个编译器首先要掌握编译原理的各种原理，编译器的各个部分的工作原理以及各个部分的相互关系。在编写之前要自己先设计好了一个完整的编译器编写比较详细的计划，才能有头绪进展下去，而且编译原理课设要接触很多之前不一样的程序风格，要定义很多符号集，需要更加缜密的思维，总之很难。

之前呢也对具体的编译程序的了解很少，也就是仅仅能做做课本上的题目，了解一点课本上的理论知识，但是这次却是我们自己动手做，查阅了很所资料，也用了很多的时间，最后还是坚持完成了任务，

这也算是期末考试的一个复习吧，让我更深入的了解了编译这门课，

很充实！

这次课程设计我也学到了很多。首先我变得更耐心了，在编写过程中会遇到很多的难题和困难，不过我都努力的让自己冷静不要浮躁然后慢慢的解决或者是请教同学。我觉得每次课程设计都是让我们重新复习一遍C和C++，这次也不例外。不过程序虽然写完了，但它还有不少值得改进的地方，以后继续努力。一周的时间很快过去了，一个学期也就要结束了，感谢老师这一个学期的谆谆教导，让我在计算机的世界里看到了、了解到了更多的好的东西，开阔了我们的视野，增长了我们的知识。

7.参考资料

陈火旺，刘春林，谭庆平，赵克佳，刘越。《程序设计语言编译原理（第三版）》。北京，国防工业出版社，2000：44-46，221-236