编译原理课程设计-PLO.docx

课 程 设 计 课程名称_编译原理 _ _题目名称_编译原理课程设计 _ 学生学院_计算机学院 _ 专业班级_计算机科学与技术_ 学 号_ _学生姓名_ _ _指导教师_ _ _201 年 1 月 7 日一、 实验目的与要求课内实验（考试前交报告）对PL/0作以下修改扩充：（1）增加单词：保留字 ELSE，FOR，STEP，UNTIL，RETURN运算符 +=，-=，+，-，（2）修改单词：不等号# 改为 （3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。课程设计基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：+= 和 -=（2）扩充语句（Pascal的FOR语句）:FOR := STEP UNTIL DO （3）增加运算：+ 和 -。选做内容（成绩评定范围扩大到：“优”和“良”）（1）增加类型： 字符类型； 实数类型。（2）扩充函数： 有返回值和返回语句； 有参数函数。（3）增加一维数组类型（可增加指令）。（4）其他典型语言设施。二、 实验环境与工具（1）计算机及操作系统：PC机，Windows 7（2）程序设计语言： C语言（3）教学型编译程序：PL/0 三、 设计方案（1） 概述课程设计的目标是做一个编译器,用的是PL/0语言,该语言功能简单、结构清晰、可读性强、又具备了一般高级语言的必须部分. PL/0语言的语句类型丰富,能适应各种可能性的程序结构.最基本的语句是赋值语句.组合结构语句有语句串、条件语句和循环语句.数据类型只有整数类型一种.PL/0允许在一个过程范围内说明常数、变量和过程.也允许递归调用,既可以间接递归,也可以直接递归.因而PL/0语言编译器是一个非常合适的小型编译程序的教学模型 PL/0的目标程序为假想栈式的计算机的汇编语言,与具体计算机无关,可称为类PCODE指令代码,其指令集极为简单,指令格式也很单纯.本PL/0编译器是在C+Builder集成环境下,用C语言实现,在Window 7平台下运行通过的.（2） 编译和解释执行的结构图：语法语义分析程序表格管理程序出错处理程序PL/0源程序目标程序代码生成程序程序词法分析程序程序PL/0语言编译过程采用一趟扫描方式,以语法分析程序为核心,词法分析程序和代码生成程序都作为一个独立的过程,当语法分析需要读单词时就调用词法分析程序,而当语法分析正确需生成相应的目标代码时,则调用代码生成程序.此外,用表格管理程序建立变量、常量和过程标识符的说明与引用之间的信息联系.用出错处理程序对词法和语法分析研究遇到的错误给出在源程序中出错的位置和错误性质.当源程序编译正确时,PL/0编译程序自动调用解释执行,并按用户程序要求输入数据和输出运行结果.（3） 各功能模块描述程序总体流程图1、 词法分析子程序分析：GetSym（）函数实现词法分析的功能，它的作用是从文件中读取一个单词。在GetSym（）函数中调用了GetCh（）。其中，GetCh（）函数实现了从文件中读取一个字符的功能，同时在读取过程中忽略了空格，和回车，和制表符。其主要操作见流程图。2、 语法分析子程序分析：语法分析子程序采用了自顶向下的递归子程序法，语法分析同时也根据程序的语义生成相应三元代码，并提供了出错处理的机制。语法分析主要由：分程序分析过程BLOCK常量定义分析过程ConstDeclaration(int LEV,int &TX,int &DX)变量定义分析过程VarDeclaration(int LEV,int &TX,int &DX)语句分析程STATEMENT(SYMSET FSYS,int LEV,int &TX)表达式处理过程EXPRESSION(SYMSET FSYS, int LEV, int &TX)项处理过程TERM(SYMSET FSYS, int LEV, int &TX)因子处理过程FACTOR(SYMSET FSYS, int LEV, int &TX)条件处理过程CONDITION(SYMSET FSYS,int LEV,int &TX)构成。这些过程在结构上构成一个嵌套的层次结构。除此之外，还有:出错报告过程Error(int n)代码生成过程Gen测试单词合法性及出错恢复过程TEST(SYMSET S1, SYMSET S2, int N)登录名字表过程ENTER(OBJECTS K, int LEV, int &TX, int &DX)查询名字表函数POSITION(ALFA ID, int TX)列出类 PCODE代码过程ListCode(int CX0)作过语法分析的辅助过程。 语法分析开始后，首先调用分程序处理过程（Block）处理分程序。过程入口参数置为：0层、符号表位置0、出错恢复单词集合为句号、声明符或语句开始符。进入Block过程后，首先把局部数据段分配指针设为3，准备分配3个单元供运行期存放静态链SL、动态链DL 和返回地址RA。然后用Tx0记录下当前符号表位置并产生一条Jmp指令，准备跳转到主程序的开始位置，由于当前还没有知到主程序究竟在何处开始，所以Jmp的目标暂时填为0，稍后再改。同时在符号表的当前位置记录下这个Jmp指令在代码段中的位置。在判断了嵌套层数没有超过规定的层数后，开始分析源程序。首先判断是否遇到了常量声明，如果遇到则开始常量定义，把常量存入符号表。分析完成后，生成操作数为0的OPR指令，用于从分程序返回（对于0层的主程序来说，就是程序运行完成，退出）。常量定义过程：逐个字母读取单词，反复获得标识符和对应的值，存入符号表。符号表中记录下标识符的名字和它对应的值。变量定义过程：逐个字母读取单词，存入符号表。符号表中记录下标识符的名字、它所在的层及它在所在层中的偏移地址。语句处理过程：在语句处理过程中，可以处理包括+=语句、-=语句、if-else-then语句、while语句、For语句等的语句。在编译过程中，如果有begin和end语句时，就会递归调用子程序，然后通过子程序进行处理。赋值语句的处理：赋值语句首先查找赋值符号左边的标志符，查找符号表，看看这个标志符是否为变量名。然后查找赋值符号后面的数字，然后通过堆栈完成赋值操作。read语句的处理：确定read语句语法合理的前提下（否则报错），由变量的类型生成相应的指令： 对于整型，第一条是16号操作的opr指令，实现从标准输入设备上读一个整数值，放在数据栈顶。如果读入是实数就报错，第二条是sto指令，把栈顶的值存入read语句括号中的变量所在的单元。对于实型，第一条是15号操作的opr指令，实现从标准输入设备上读一个实数值，放在数据栈顶。第二条是sto指令，把栈顶的值存入read语句括号中的变量所在的单元。对于字符型，第一条是20号操作的opr指令，实现从标准输入设备上读一个字符值，第二条是sto指令，把栈顶的值存入read语句括号中的变量所在的单元。write语句的处理：与read语句相似。在语法正确的前提下，生成指令：通过循环调用表达式处理过程分析write语句括号中的每一个表达式，生成相应指令保证把表达式的值算出并放到数据栈顶并生成指令，输出表达式的值，如果是数字类型则生成14号操作的opr指令，如果是字符类型则生成19号操作的opr指令。if-then-else语句的处理：按if语句的语法，首先调用逻辑表达式处理过程处理if语句的条件，把相应的真假值放到数据栈顶。接下去记录下代码段分配位置（即下面生成的jpc指令的位置），然后生成条件转移jpc指令（遇0或遇假转移），转移地址未知暂时填0。然后调用语句处理过程处理 then语句后面的语句或语句块。then后的语句处理完后，如果遇到else，就调用语句处理过程处理else语句后面的语句或语句块，这时当前代码段分配指针的位置就应该是上面的jpc指令的转移位置。通过前面记录下的jpc指令的位置，把它的跳转位置改成当前的代码段指针位置，否则没遇到else，那么此时的当前代码段分配指针的位置也是上面jpc指令的转移位置，也是通过前面记录下的jpc位置指令的位置，把它的跳转到当前的代码段指针位置。begin/end语句的处理：通过循环遍历begin/end语句块中的每一个语句，通过递归调用语句分析过程分析并生成相应代码。while语句的处理：首先用cx1变量记下当前代码段分配位置，作为循环的开始位置。然后处理while语句中的条件表达式生成相应代码把结果放在数据栈顶，再用cx2变量记下当前位置，生成条件转移指令，转移位置未知，填0。通过递归调用语句分析过程分析do语句后的语句或语句块并生成相应代码。最后生成一条无条件跳转指令jmp，跳转到cx1所指位置，并把cx2所指的条件跳转指令的跳转位置改成当前代码段分配位置。For语句的处理：按For语句的语法，首先对For后面的一个标识符进行初值的赋值过程（类似赋值语句处理），生成相应的代码。之后遇到TO或DOWNTO保留字，如果未对应则出错。用CX1变量记下当前代码段分配的位置，作为以后JMP循环的开始位置。对上面识别的标识符变量进行存取（值在栈顶），让TO或DOWNTO后面的表达式（值在次栈顶）与之比较，生成比较指令（TO为11、DOWNTO为13），再用CX2变量记下当前代码段分配的位置，生成JPC指令，跳转地址未知，之后可用CX2记录下的位置进行回填。然后处理DO保留字后的循环体，第一步递归调用语句分析过程，第二步将原先For后的标识符变量进行自加处理，生成相应代码，然后生成无条件跳转语句JMP跳转代码为CX1。最后将此时的代码段位置回填到JPC跳转指令上.4、 代码生成PL/0 处理机的指令集根据PL/0 语言的要求而设计，它包括以下的指令：（1）LIT /* 将常数置于栈顶 */（2）LOD /* 将变量值置于栈顶 */（3）STO /* 将栈顶的值赋与某变量 */（4）CAL /* 用于过程调用的指令 */（5）INT /* 在数据栈中分配存储空间 */（6）OPR /* 一组算术或逻辑运算指令 */（7）JMP, JPC /* 用于if, while 语句的条件或无条件控制转移指令 */5、 代码执行相关过程：base()，interpret()。其中base()的功能是根据层次差并从当前数据区沿着静态链查找，以便获取变量实际所在的数据区其地址；interpret()则完成各种指令的执行工作。6、错误诊断处理一个编译程序，在多数情况下，所接受的源程序正文都是有错误的。发现错误，并给出合适的诊断信息且继续编译下去从而发现更多的错误，对于编译程序而言是完全必要的。相关过程：test(), inset(), createset, uniteset(), error()。7、符号表管理为了组成一条指令，编译程序必须知道其操作码及其参数（数或地址）。这些值是由编译程序本身联系到相应标识符上去的。这种联系是在处理常数、变量和过程说明完成的。为此，标识符表应包含每一标识符所联系的属性；如果标识符被说明为常数，其属性值为常数值；若被说明成变量，其属性就是由层次和偏移量组成的地址；若被说明为过程，其属性就是过程的入口地址及层次。常数的值由程序正文提供，编译的任务就是确定存放该值的地址。我们选择顺序分配变量和代码的方法；每遇到一个变量说明，就将数据单元的下标加一（PL/0 机中，每个变量占一个存贮单元）。开始编译一个过程时，要对数据单元的下标dx 赋初值，表示新开辟一个数据区。dx 的初值为3，因为每个数据区包含三个内部变量RA，DL 和SL。相关过程：enter()，该函数用于向符号表添加新的符号，并确定标识符的有关属性。四、 主要成分描述：符号表：符号表实现了收集符号属性，上下文语义的合法性检查的依据，作为目标代码生成阶段地址分配的依据等功能。 符号表是全程量一维数组TABLE。TX为索引表的指针，表中的每个元素为记录型数据。表中的LEV表示层次，DX表示给本层局部变量分配的相对存贮位置，没说明完一个变量后DX加1。TABLE表中的NAME表示元素名；KIND表示元素的类型(常量、变量、过程)；VAL/LEVEL在元素为常量时表示常量的值，在元素为变量或过程时表示层次；ADR在元素为变量时为变量的存贮位置，在元素为过程时为过程体的目标代码生成时反填过程体的入口地址；SIZE是记录过程所需的数据空间。运行时存储组织和管理：该编译程序使用的是栈式存储分配的存储组织管理方法。当编译结束后，存储区只需以数组CODE存放的只读程序和运行式的数据区S(由解释程序定义的一维整形数组)。解释执行时的数据空间S为栈式计算机的存储空间。遵循后进先出规则，对每个过程(包括主程序)当被调用时，才分配数据空间，退出过程时，所分配的数据空间被释放。解释程序定义了4个寄存器：I 指令寄存器存放当前正在解释的一条目标指令P 程序地址寄存器指向下一条要执行的目标程序的地址T 栈顶寄存器指向当前栈中最新分配的单元B 基址寄存器指向每个过程被调用时，在数据区S中给该过程分配的数据断起始地址为了实现过程被调用时给它分配数据段，过程运行结束后释放数据段以及嵌套过程之间对标识符引用的寻址问题，当过程被调用时，在栈顶分配三个联系单元，这三个单元存放的内容分别如下：SL静态链：指向定义该过程的直接外过程(主程序)运行时最新数据断的基地址DL动态链：指向调用该过程前正在运行过程的数据段基地址RA返回地址：记录调用该过程时目标程序的断点，即当时的程序地址寄存器P的值语法分析方法：自顶向下递归子程序方法：从读入第一个单词开始，由非终结符（即开始符）出发，沿语法描述图箭头所指出的方向进行分析。当遇到非终结符时，则调用相应的处理过程，从语法描述图看，也就进入了一个语法单元，再沿当前所进入的语法单元所指箭头方向继续进行分析。当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。中间代码表示： PL/0编译程序中间代码称为类PCODE指令代码，其指令格式如下：其中f代表功能码，l表示层次差(引用变量或过程的分程序与说明该变量或过程的分程序之间的层次差)。a的含义对不同的指令有所区别。五、 完成的情况完成的功能如下：1 课内实验（考试前交报告）对PL/0作以下修改扩充：（1）增加单词：保留字 ELSE，FOR，STEP，UNTIL，RETURN运算符 +=，-=，+，-，（2）修改单词：不等号# 改为 （3）增加条件语句的ELSE子句，要求：写出相关文法，语法图，语义规则。2 课程设计基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：+= 和 -=（2）扩充语句（Pascal的FOR语句）:FOR := STEP UNTIL DO （3）增加运算：+ 和 -。选做内容（成绩评定范围扩大到：“优”和“良”）（1）增加类型： 字符类型； 实数类型。（2）扩充函数： 有返回值和返回语句； 有参数函数。（3）增加一维数组类型（可增加指令）。（4）其他典型语言设施。（1） 增加单词：保留字 ELSE，FOR，TO, STEP，UNTIL,RETURN.（2） 运算符 +=，-=，+,-,先在SYMBOL中增加ELSESYM, FORSYM, TOSYM, TOSYM,UNTILSYM,RETURNSYM,INC,DEC,PLUSEQL, MINUSEQL；然后在保留字表中增加ELSE,FOR,TO,STEP,UNTIL,RETURN. 在词法分析程序里增加下面的程序段：else if (CH=+) GetCh();if (CH=) SYM=PLUSEQL; GetCh(); else if(CH=+) SYM=INC; GetCh(); else SYM=PLUS; else if (CH=-) GetCh();if (CH=) SYM=MINUSEQL; GetCh(); else if(CH=-) SYM=DEC; GetCh(); else SYM=MINUS; else if (CH=&) GetCh();if (CH=&) SYM=YU; GetCh(); else SYM=NUL; else if (CH=|) GetCh();if (CH=|) SYM=HUO; GetCh(); else SYM=NUL; else if (CH=:) GetCh();if (CH=) SYM=BECOMES; GetCh(); else SYM=NUL; else /* THE FOLLOWING TWO CHECK WERE ADDED BECAUSE ASCII DOES NOT HAVE A SINGLE CHARACTER FOR = */ if (CH=) SYM=NEQ; GetCh(); else SYM=LSS;else if (CH=) GetCh();if (CH=) SYM=GEQ; GetCh(); else SYM=GTR; else SYM=SSYMCH; GetCh(); （2）增加条件语句的ELSE子句,此功能扩充只需在语句分析里面进行增加如下代码：case IFSYM: GetSym();CONDITION(SymSetUnion(SymSetNew(THENSYM,DOSYM,ELSESYM),FSYS),LEV,TX);if (SYM=THENSYM) GetSym();else Error(16);CX1=CX; GEN(JPC,0,0);STATEMENT(SymSetUnion(SymSetNew(IDENT,ELSESYM,SEMICOLON),FSYS),LEV,TX); if(SYM!=SEMICOLON) Form1-printls(错误IF,300); else GetSym(); if(SYM=ELSESYM) GetSym(); CX2=CX; GEN(JMP,0,0); STATEMENT(FSYS,LEV,TX); CODECX1.A=CX2+1; CODECX2.A=CX; else i=1; CODECX1.A=CX; return; break;（3）扩充赋值运算:+=,- =.此功能扩充只需在语句分析里面进行增加如下代码： if(SYM=BECOMES|SYM=PLUSEQL|SYM=MINUSEQL) if (SYM=BECOMES) GetSym(); EXPRESSION(FSYS,LEV,TX); else if(SYM=PLUSEQL|SYM=MINUSEQL) GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); if(SYM=PLUSEQL) GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,2); else if(SYM=MINUSEQL) GetSym(); FACTOR(FSYS,LEV,TX); GEN(OPR,0,3); if (i!=0) GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); （4）扩充FOR TO和FOR DOWNTO语句,此功能的关键是如何判断条件是否成立,并如何进行程序跳转.在这里用到了几条指令,和地址回填技术.扩充代码如下: case FORSYM: GetSym(); if(SYM!=IDENT)Error(31); /FOR后面要标识符 i=POSITION(ID,TX);if (i=0) Error(11);else if (TABLEi.KIND!=VARIABLE) /*ASSIGNMENT TO NON-VARIABLE*/ Error(12); /变量 GetSym(); if(SYM!=BECOMES) Error(13); GetSym(); EXPRESSION(SymSetUnion(SymSetNew(TOSYM,DOWNTOSYM,DOSYM),FSYS),LEV,TX);/表达式 if(SYM=DOWNTOSYM) CX1=CX; GetSym(); GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/保存结果至变量单元 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/重新调入栈顶 EXPRESSION(SymSetAdd(DOSYM,FSYS),LEV,TX);/表达式 GEN(OPR,0,11);/判断运算 CX2=CX; GEN(JPC,0,0);/如果栈顶非真跳转 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR);/重新调入栈顶 GEN(LIT,0,1) ;/送1到栈顶 GEN(OPR,0,3); /减运算 if(SYM=DOSYM) GetSym(); STATEMENT(FSYS,LEV,TX); GEN(JMP,0,CX1); CODECX2.A=CX; else if(SYM=TOSYM) CX1=CX;GetSym(); GEN(STO,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); /保存结果至变量单元 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); /重新调入栈顶 EXPRESSION(SymSetAdd(DOSYM,FSYS),LEV,TX);/表达式分析 GEN(OPR,0,13);/判断运算 CX2=CX; GEN(JPC,0,0);/如果栈顶非真跳转 GEN(LOD,LEV-TABLEi.vp.LEVEL,TABLEi.vp.ADR); GEN(LIT,0,1); GEN(OPR,0,2); if(SYM=DOSYM) GetSym(); STATEMENT(FSYS,LEV,TX); GEN(JMP,0,CX1); CODECX2.A=CX;/回填地址 else Error(35); break;（5）增加运算:+,-.这两个运算又分为前加,后加,前减,后减.可以单独做为一个语句,也可以放在因子里,所以必须对语句分析程序和因子进行扩充.为了实现在因子里+,-运算特别写了两个函数OPDOUBLE和DOUBLEOP对因子进行操作:void DOUBLEOP()/前加int i,TX; SYMBOL DOP; DOP=SYM; GetSym(); if (SYM=IDENT) i=POSITION(ID,TX); if (i=0) Error(11); else if (TABLEi.KIND=VARIABLE) GEN(LOD,TABLEi.vp.LEVEL,TABLEi.vp.ADR);/将变量放到栈顶 else Error(25); /运算符后必须是变量 GEN(LIT,0,1); /将1取到运行栈顶 if(DOP=INC) GEN(OPR,0,2); else GEN(OPR,0,3); GEN(STO,TABLEi.vp.LEVEL,TABLEi.vp.ADR);/存结果 GEN(LOD,TABLEi.vp.LEVEL,TABLEi.vp.ADR);/将变量放到栈顶 GetSym();void OPDOUBLE(int i) /后加 if(i=0) Error(11); else if (TABLEi.KIND=VARIABLE) GEN(LOD,TABLEi.vp.LEVEL,TABLEi.vp.ADR); else Error(25); GEN(LIT,0,1); if(SYM=INC) GEN(OPR,0,2); else GEN(OPR,0,3); GEN(STO,TABLEi.vp.LEVEL,TABLEi.vp.ADR); GetSym();六、 测试用例1、后加测试用例：= COMPILE PL0 = 0 PROGRAM AA; 0 VAR I,J; 1 BEGIN 2 I:=1; 4 J:=100; 6 I:=J+; 12 WRITE(I); 15 WRITE(J); 18 END. 0 JMP 0 1 1 INI 0 5 2 LIT 0 1 3 STO 0 3 4 LIT 0 100 5 STO 0 4 6 LOD 0 4 7 LOD 0 4 8 LIT 0 1 9 OPR 0 2 10 STO 0 4 11 STO 0 3 12 LOD 0 3 13 OPR 0 14 14 OPR 0 15 15 LOD 0 4 16 OPR 0 14 17 OPR 0 15 18 OPR 0 0* RUN PL0 *100101*END PL0*2、前加测试用例：= COMPILE PL0 = 0 PROGRAM MM; 0 VAR A,B,C; 1 BEGIN 2 A:=10; 4 B:=10; 6 +A; 10 -B; 14 WRITE(A); 17 WRITE(B); 20 END. 0 JMP 0 1 1 INI 0 6 2 LIT 0 10 3 STO 0 3 4 LIT 0 10 5 STO 0 4 6 LOD 0 3 7 LIT 0 1 8 OPR 0 2 9 STO 0 3 10 LOD 0 4 11 LIT 0 1 12 OPR 0 3 13 STO 0 4 14 LOD 0 3 15 OPR 0 14 16 OPR 0 15 17 LOD 0 4 18 OPR 0 14 19 OPR 0 15 20 OPR 0 0* RUN PL0 *119*END PL0*3、ELSE语句测试用例= COMPILE PL0 = 0 PROGRAM EX01; 0 VAR A,B,C; 1 BEGIN 2 A:=1; 4 B:=2; 6 IF AB THEN 9 WRITE(A) 12 ELSE 14 WRITE(B); 17 IF AB THEN 20 WRITE(A) 23 ELSE 25 WRITE(B); 28 END. 0 JMP 0 1 1 INI 0 6 2 LIT 0 1 3 STO 0 3 4 LIT 0 2 5 STO 0 4 6 LOD 0 3 7 LOD 0 4 8 OPR 0 12 9 JPC 0 14 10 LOD 0 3 11 OPR 0 14 12 OPR 0 15 13 JMP 0 17 14 LOD 0 4 15 OPR 0 14 16 OPR 0 15 17 LOD 0 3 18 LOD 0 4 19 OPR 0 10 20 JPC 0 25 21 LOD 0 3 22 OPR 0 14 23 OPR 0 15 24 JMP 0 28 25 LOD 0 4 26 OPR 0 14 27 OPR 0 15 28 OPR 0 0* RUN PL0 *21*END PL0*4、FORTO语句测试用例= COMPILE PL0 = 0 PROGRAM EX01; 0 VAR A; 1 BEGIN 2 FOR A:=0 TO 5 6 DO 11 WRITE(A);