表达式编译程序上机报告.doc

编译原理上机实验报告计算机科学与技术班-上机一成员： 00813035吴庆周 00813003祝金辉00813015闫海滨 00718100特日格乐00813023王仕华一、 题目编写编译程序实现多行表达式的的文法语言的编译执行二、 设计和主要结构1 词法分析词法分析子程序分析：词法分析子程序名为getsym，功能是从源程序中读出一个单词符号，把它的信息放入全局变量sym、id和num中，语法分析器需要单词时，直接从这三个变量中获得。（注意！语法分析器每次用完这三个变量的值就立即调用getsym子程序获取新的单词供下一次使用。而不是在需要新单词时才调用getsym过程。）getsym过程通过反复调用getch子过程从源程序过获取字符，并把它们拼成单词。getch过程中使用了行缓冲区技术以提高程序运行效率。词法分析器的分析过程：调用getsym时，它通过getch过程从源程序中获得一个字符。如果这个字符是字母，则继续获取字符或数字，最终可以拼成一个单词，查保留字表，如果查到为保留字，则把sym变量赋成相应的保留字类型值；如果没有查到，则这个单词应是一个用户自定义的标识符（可能是变量名、常量名或是过程的名字），把sym置为SYM_IDENTIFIER，把这个单词存入id变量。查保留字表时使用了二分法查找以提高效率。如果getch获得的字符是数字，则继续用getch获取数字，并把它们拼成一个整数，然后把sym置为number，并把拼成的数值放入num变量。如果识别出其它合法的符号（比如：赋值号、大于号、小于等于号等），则把sym赋成相应的类型。如果遇到不合法的字符，把sym置成SYM_NULL。词法分析子程序要完成的工作有:1.识别一般标识符，此标识符值（字符序列）赋给全局量id，而全局量sym赋值为SYM_IDENTIFIER。2.识别数字序列，当前值赋给全局量NUM，sym则置为SYM_NUMBER；3.识别=，回车之类的特殊符号，全局量sym则分别被赋值为SYM_BECOMES，SYM_CONTINUE等。4.在该程序的实现中,我们将标准函数作为保留字使用,即创建四个保留字,分别是sin,cos,tan,exp相关过程（函数）有getsym()，getch()，其中getch()为获取单个字符的过程，除此之外，它还完成：1.识别且跳过行结束符；2.产生一份程序列表，输出相应行号或指令计数器的值。2 语法分析语法分析子程序分析：语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语意生成相应的代码，并提供了出错处理的机制。语法分析主要由表达式处理过程（expression）、项处理过程（term）、因子处理过程（factor）构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有出错报告过程（error）、代码生成过程（gen）、测试单词合法性及出错恢复过程（test）、登录名字表过程（enter）、查询名字表函数（position）以及列出类PCODE代码过程（listcode）作过语法分析的辅助过程。我们采用递归下降的方法来设计编译器。以下我们给出该语言的FIRST和FOLLOW集合。表达式、项、因子处理：根据PL/0语法可知，表达式应该是由正负号或无符号开头、由若干个项以加减号连接而成。而项是由若干个因子以乘除号连接而成，因子则可能是一个标识符或一个数字，或是一个以括号括起来的子表达式。根据这样的结构，构造出相应的过程，递归调用就完成了表达式的处理。把项和因子独立开处理解决了加减号与乘除号的优先级问题。在这几个过程的反复调用中，始终传递fsys变量的值，保证可以在出错的情况下跳过出错的符号，使分析过程得以进行下去。非终结符（S）FIRST(S)FOLLOW(S)表达式+ - ( ident number ) 回车项ident number ( 标准函数 ) + - 因子ident number ( 标准函数 ) + - * / 回车(注:标准函数为sin,cos,tan,exp)表达式序列文法为:- - = +-（+-） - （* | /） - () ( ) - sin | cos | tan | exp以下是我们给出对表达式序列文法的理解，则：1.表达式序列为多个表达式的集合.2.表达式由项组成,或者可以有多个项作加法运算构成3.项是由因子或者因子作乘法运算构成4. 因子是无符号实数,变量,标准函数,亦或递归表达式的定义处理上叙过程的相关函数有:expression(), term(), factor(),expression_list()等。可以得到简单的程序分析图如下:表达式项因子图1-2 语法分析过程依赖关系3 语义分析表达式文法的语义分析主要是：其中的变量无需定义且其作用域为第一次赋值处至最后。4 代码生成表达式序列编译程序不仅完成通常的词法分析、语法分析，而且还产生中间代码和“目标”代码。最终我们要“运行”该目标码。为了使我们的编译程序保持适当简单的水平，不致陷入与本课程无关的实际机器的特有性质的考虑中去，我们假想有台适合表达式序列程序运行的计算机，我们称之为表达式序列处理机。表达式序列处理机顺序解释生成的目标代码，我们称之为解释程序。注意：这里的假设与我们的编译概念并不矛盾，在本课程中我们写的只是一个示范性的编译程序，它的后端无法完整地实现，因而只能在一个解释性的环境下予以模拟。从另一个角度上讲，把解释程序就看成是表达式序列机硬件，把解释执行看成是表达式序列的硬件执行，那么我们所做的工作：由表达式序列源语言程序到表达式序列机器指令的变换，就是一个完整的编译程序。表达式序列处理机有两类存贮，目标代码放在一个固定的存贮数组code中，而所需数据组织成一个栈形式存放。表达式序列处理机的指令集根据表达式序列语言的要求而设计，它包括以下的指令：（1）LIT /* 将常数置于栈顶 */（2）LOD /* 将变量值置于栈顶 */（3）STO /* 将栈顶的值赋与某变量 */（4）INT /* 在数据栈中分配存贮空间 */（5）OPR /* 一组算术运算指令 */（注：对于OPR操作，0表示取反操作，1-4表示算术运算，5-8表示标准函数的操作）上述指令的格式由两部分组成：FA其中，f, a的含义见下表： FaINT常 量LIT常 量LOD数据地址STO数据地址OPR运算类别表2-1 表达式序列 处理机指令上表中，程序地址为目标数组code的下标，数据地址为变量在局部存贮中的相对地址。表达式序列的编译程序为每一条表达式序列源程序的可执行语句生成后缀式目标代码。如赋值语句X = Y op Z（op为某个运算符），将被翻译成下面的目标代码序列：（设指令计数从第100号开始）No.fa100LODAddr_Y101LODAddr_Z102OPRop103STOAddr_X相关过程（函数）有：gen()，其任务是把三个参数f、a组装成一条目标指令并存放于code数组中，增加CX的值，CX表示下一条即将生成的目标指令的地址。5 代码执行为了简单起见，我们假设有一个表达式序列处理机，它能够解释执行表达式序列编译程序所生成的目标代码。这个表达式序列处理机有一个指令寄存器。程序（目标代码）存贮称为code，由编译程序装入，在目标代码执行过程中保持不变，因此它可被看成是“只读”存贮器。数据存贮S组织成为一个栈，所有的算术运算均对栈顶元和次栈顶元进行（一元运算仅作用于栈顶元），并用结果值代替原来的运算对象。栈顶元的地址（下标）记在栈顶寄存器T中，指令寄存器I包含着当前正在解释执行的指令，程序地址寄存器P指向下一条将取出的指令。相关过程： interpret()。interpret()则完成各种指令的执行工作。6 错误诊断处理判断单词合法性与出错恢复过程分析：本过程有三个参数，s1、s2为两个符号集合，n为出错代码。本过程的功能是：测试当前符号（即sym变量中的值）是否在s1集合中，如果不在，就通过调用出错报告过程输出出错代码n，并放弃当前符号，通过词法分析过程获取一下单词，直到这个单词出现在s1或s2集合中为止。这个过程在实际使用中很灵活，主要有两个用法：在进入某个语法单位时，调用本过程，检查当前符号是否属于该语法单位的开始符号集合。若不属于，则滤去开始符号和后继符号集合外的所有符号。在语法单位分析结束时，调用本过程，检查当前符号是否属于调用该语法单位时应有的后继符号集合。若不属于，则滤去后继符号和开始符号集合外的所有符号。通过这样的机制，可以在源程序出现错误时，及时跳过出错的部分，保证语法分析可以继续下去。一个编译程序，在多数情况下，所接受的源程序正文都是有错误的。发现错误，并给出合适的诊断信息且继续编译下去从而发现更多的错误，对于编译程序而言是完全必要的。本程序对错误的处理如下一旦发现非法结构，即跳过后面的输入正文，直到下一个可以正确地跟随当前正在分析的句子结构的符号为止。这意味着每一分析程序需知道其当前活动结点的后继符号集合。为了找到这个后继符号集合，我们给对应语法图的每一个分析过程提供一个显式参数，set，它指明可能的后继集合。不过在任何条件下，如果都跳到输入正文中下一个这种后继符号出现的地方，未免太短视了。程序中所含的错误可能只不过是漏掉了一个符号而己，由此而忽略去源程序的符号集合中，再凑加一些关键字，它们用于标记那些不容忽略的结构的开始符，因此，作为参数传递给分析过程的那些符号就不仅是后继符号了。对于这样的符号集，我们采用这样的计算策略：先用一些明显的关键符号给它赋初值，然后随着分析的深入，逐步补充别的合法符号。为了灵活起见，我们引入test子程序来实现所说的验证工作。test过程有三个参数：1.可允许的下一个符号集合S1，如果当前符号不在此集合中，当即得到一个错误号；2. 另加的停止符号集合S2，有些符号的出现，虽然无疑是错的，但它们绝对不应被忽略而跳过；3. 整数n，表示有关错误的诊断号：7 符号表管理为了组成一条指令，编译程序必须知道其操作码及其参数（数或地址）。这些值是由编译程序本身联系到相应标识符上去的。这种联系是在处理常数、变量和过程说明完成的。为此，标识符表应包含每一标识符所联系的属性；如果标识符被说明为常数，其属性值为常数值；如果标识符被说明成变量，其属性就是由层次和修正量（偏移量）组成的地址；如果标识符被说明为过程，其属性就是过程的入口地址及层次。常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（表达式序列机中，每个变量占一个存贮单元）。开始编译一个过程时，要对数据单元的下标dx赋初值，表示新开辟一个数据区。dx的初值为0。相关过程：enter()，该函数用于向符号表添加新的符号，并确定标识符的有关属性。8 其他本程序所写的表达式序列编译程序包括词法分析、语法分析、错误诊断、代码生成、解释执行等几部分。关于这几个程序，我们做如下说明：（1） 每一个分程序（过程）被编译结束后，将列出该部分表达式序列程序代码。这个工作由过程listcode()完成。（2） 解释程序作为表达式序列编译程序的一个过程，若被编译的源代码没有错误，则编译结束时调用这个过程。表达式序列语言没有输出语句。解释程序按执行次序，每遇到对变量的赋值就输出其值。本程序主要的数据结构为数组和链表，编译技术和程序结构如上所述。关于对剔除本程序不需要的PL/0栈式指令的相关说明剔除的PL/0栈式指令为：CAL，JMP，JPC。CAL：调用过程的指令。 本程序只是关于编译表达式的程序，没有过程，按顺序执行，不需要调用过程的指令。JPC： 条件转移指令JMP： 无条件转移指令 表达式文法是按顺序执行的，不需用到转移指令。简化PL/0运行栈在PL/0程序中在栈顶分配三个联系单元，存贮静态链，动态链，和返回地址。这些用于过程调用，但是因为在本程序中没有过程调用，所以没有这三个单元。三、测试1一个例子1.1表达式序列语言源程序下面我们给出一个表达式序列语言写的一段程序：x=8*2y=cos(x)z=sin(0)sum=x+y+z1.2 生成的代码前面我们给出了PL/0语言写的一段程序，其中乘法过程经过编译程序产生以下代码：0 INT 4 1 LIT 8 2 LIT 2 3 OPR 3 4 STO 0 5 LOD 0 6 OPR 6 7 STO 1 8 LIT 0 9 OPR 5 10 STO 2 11 LOD 0 12 LOD 1 13 OPR 1 14 LOD 2 15 OPR 1 16 STO 3表达式序列语言编译器源程序包括如下C+程序文件，PL0.h、PL0.cpp、set.h和set.cpp。四、遗留的问题及思考大部分程序不可能没有漏洞，本程序也一样，在本程序中，编译部分，程序不能很好的处理无符号小数，在小数超