编译原理PL0报告(附源码教程)

编译原理课程设计学 院 计算机学院 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 20 年 月 日一、课程设计要求基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：*= 和 /=扩充语句（Pascal的FOR语句）:FOR := TO DO FOR := DOWNTO DO 其中，语句的循环变量的步长为2，语句的循环变量的步长为-2。（3）增加运算：+ 和 -。选做内容（成绩评定范围扩大到：“优”和“良”）（1）增加类型： 字符类型； 实数类型。（2）扩充函数： 有返回值和返回语句； 有参数函数。（3）增加一维数组类型（可增加指令）。（4）其他典型语言设施。二、概述目标：实现PL0某些特定语句实现语言：C语言实现工具平台：VS201运行平台：WIN7三、 结构设计说明与功能块描述PL/0编译程序的结构图PL/0编译程序的过程或函数的功能表过程或函数名简要功能说明pl0主程序error出错处理，打印出错位置和错误编码getsym词法分析，读取一个单词getch漏掉空格，读取一个字符gen生成目标代码，并送入目标程序区test测试当前单词符号是否合法block分程序分析处理过程enter登录名字表position(函数)查找标识符在名字表中的位置constdeclaration常量定义处理vardeclaration变量说明处理listode列出目标代码清单statement语句处理expression表达式处理term项处理factor因子处理condition条件处理interpret对目标代码的解释执行程序base(函数)通过静态链求出数据区的基地址PL/0编译程序的总体流程图启动置初值调用getsym取单词调用block过程是否为源程序结束符源程序是否有错误调用解释过程interpret解释执行目标执行目标程序结束出错打印错误NNYY四、 主要成分描述1、 符号表编译程序里用了一个枚举类型enum symbol，然后定义了enum symbol sym来存放当前的符号，前面讲过，主程序定义了一个以字符为元素的一维数组word，称保留字表，这个保留字表也存放在符号表里，为了识别当前的符号是属于哪些保留字；还有标识符，拼数，拼符合词等的符号名都存放在符号表里，当sym存放当前的符号时，我们可以判断它是属于哪类的符号，然后加以处理。在运行的过程中，主程序中又定义了一个名字表，也就是符号表，来专门存放变量、常量和过程名的各个属性，里面的属性包括name，kind，val/level，adr，size，我们来举一个PL/0语言过程说明部分的片段：Const a=35,b=49;Var c,d,e;Procedure p;Var g;nameKindVal/levelAdrsizeabcdepconstconstvariablevariablevariableprocedure3549LevLevLevlevdxdx+1dx+24gvariablelev+1dx当遇到标识符的引用时就调用position函数，根据当前sym的符号类型来查table表，看是否有过正确的定义，若已有，则从表中取相应的有关信息，供代码的生成用。若无定义则调用出错处理程序。2、 运行时存储组织和管理对于源程序的每一个过程（包括主程序），在被调用时，首先在数据段中开辟三个空间，存放静态链SL、动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL、DL和RA的值均置为0。静态链的功能是在一个子过程要引用它的直接或间接父过程（这里的父过程是按定义过程时的嵌套情况来定的，而不是按执行时的调用顺序定的）的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它。在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址，通过当前段基址恢复数据段分配指针，通过动态链恢复局部段基址指针。实现子过程的返回。对于主程序来说，解释程序会遇到返回地址为0的情况，这时就认为程序运行结束。解释程序过程中的base函数的功能，就是用于沿着静态链，向前查找相差指定层数的局部数据段基址。这在使用sto、lod、stoArr、lodArr等访问局部变量的指令中会经常用。类PCODE代码解释执行的部分通过循环和简单的case判断不同的指令，做出相应的动作。当遇到主程序中的返回指令时，指令指针会指到0位置，把这样一个条件作为终至循环的条件，保证程序运行可以正常的结束。3、 语法分析方法语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则.PL/0编译程序的语法分析采用了自顶向下的递归子程序法.粗略地说:就是对应每个非终结符语法单元,编一个独立的处理过程(或子程序).语法分析研究从读入第一个单词开始由非终结符程序即开始符出发,沿语法描述图箭头所指出的方向进行分析.当遇到非终结符时,则调用相应的处理过程,从语法描述图看也就进入了一个语法单元,再沿当前所进入的语法描述图的箭头方向进行分析,当遇到描述图中是终结符时,则判断当前读入的单词是否与图中的终结符相匹配,若匹配,则执行相应的语义程序(就是翻译程序).再读取下一个单词继续分析.遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较,若都不匹配时可能是进入下一非终结符语法单位或是出错.如果一个PL/0语言程序的单词序列在整修语法分析中,都能逐个得到匹配,直到程序结束.,这时就说所输入的程序是正确的.对于正确的语法分析做相应的语义翻译,最终得出目标程序.4、 中间代码表示中间代码表示格式如下:fLa其中f代表功能码,l表示层次差,也就是变量或过程被引用的分程序与说明该变量或过程 的分程序之间的层次差.a的含意对不同的指令有所区别,见下面对每条指令解释说明.1. LIT 0 A 将常数值取到栈顶,A为常数值2. LOD L A 将变量值取到栈顶,A为偏移量,L为层差3. STO L A 将栈顶内容送入某一变量单元中,A为偏移量,L为层差4. CAL L A 调用过程,A为过程地址,L为层差5. INT 0 A 在运行栈中为被调用的过程开辟A个单元的数据区6. JMP 0 A 无条件跳转到A地址7. JPC 0 A 条件跳转,当栈顶布尔值非真则跳转到A地址,否则顺序执行8. OPR 0 0 过程调用结束后,返回调用点并退栈9. OPR 0 1 栈顶元素取反10. OPR 0 2 次栈顶与栈顶相加,退两个栈元素,结果值进栈11. OPR 0 3 次栈顶减去栈顶,退两个栈元素,结果值进栈12. OPR 0 4 次栈顶乘以栈顶,退两个栈元素,结果值进栈13. OPR 0 5 次栈顶除以栈顶,退两个栈元素,结果值进栈14. OPR 0 6 栈顶元素的奇偶判断,结果值在栈顶15. OPR 0 7 16. OPR 0 8 次栈顶与栈顶是否相等,退两上栈元素,结果值进栈17. OPR 0 9 次栈顶与栈顶是否不等,退两个栈元素,结果值进栈18. OPR 0 10 次栈顶是否小于栈顶,退两个栈元素,结果值进栈19. OPR 0 11 次栈顶是否大于等于栈顶,退两个栈元素,结果值进栈20. OPR 0 12 次栈顶是否大于栈顶,退两个栈元素,结果值进栈21. OPR 0 13 次栈顶是否小于等于栈顶,退两个栈元素,结果值进栈22. OPR 0 14 栈顶值输出到屏幕23. OPR 0 15 屏幕输出换行24. OPR 0 16 从命令行读入一个输入置于栈顶（后续增加的指令后面介绍）五、 测试用例1、 基本内容PL0代码：for.txtvar a,b; begin a:=3; b:=8; a*=b; b/=2; write(a); write(b); repeat a:=a+b; until a50; write(a); write(b); for(a:=0;aamax) /数超过允许最大值amaxerror(31); /抛出31号错printf(数越界n);num=0; /把数字按0值处理gendo(lit,0,num); /生成lit指令，把这个数值常量放到栈顶getsymdo; /获取下一tokenelseif(sym=lparen) /如果遇到的是左括号getsymdo; /获取一个tokenmemcpy(nxtlev,fsys,sizeof(bool)*symnum);nxtlevrparen=true;expressiondo(nxtlev,ptx,lev); /递归调用expression分析一个子表达式if(sym=rparen) /子表达式分析完后，应遇到右括号getsymdo; /若确遇右括号，读取下一个tokenelseerror(22); /否则抛出22号错误printf(表达式中漏了右括号）n); testdo(fsys,facbegsys,23); /*一个因子处理完毕，遇到的token应在fsys集合中。如果不是，抛23号错，并找到下一个因子的开始，使语法分析可以继续运行下去*/return 0;5） interpret()函数里需要增加2个指令的解释，前面头文件那里指令集合也得改一下，这两个指令主要功能是将数组里变量下标寻址取值，然后加上基地址加上偏移地址得出数组元素的位置来赋值。下面给出增加的2个指令：case sto2: /如果是sto指令gendo(sto,lev-tablei.level,tablei.adr+j1);t-; /栈项下移，释放空间sbase(i.l,s,b)+(int)i.a+(int)(sbase(i.l,s,b)+tablevarnumvarnn.adr)=st; /把栈顶的值存入位置在数据区层差l偏移地址a的变量内存varnn+;break;case lod2: /如果是lod指令:将变量放到栈顶gendo(lod2,lev-tablei.level,tablei.adr); st=sbase(i.l,s,b)+(int)i.a+(int)(sbase(i.l,s,b)+tablevarnumvarnn.adr); /通过数据区层差l和偏移地址a找到变量的数据，存入上面开辟的新空间（即栈顶）varnn+;t+; /栈顶上移break;6） 数组的主要难点是数组下标可以为变量，无法在编译阶段得到变量的值然后传偏移地址，只能通过全局数组存储变量的位置，然后在解释执行阶段再得到变量的值来寻址，进而赋值给数组。7） 最后琢磨了一下，当数组下标为变量时，用全局数组存储变量位置很不好，一些运算例如*=之类的会错误，最好采用4参数中间代码指令。4、 增加字符型，实型1） 原有的PL0模板只有变量类型VAR，其实它是默认变量类型VAR为整形，因为存储栈S的类型为整形，所以要想增加字符型和实型两个数据类型，必须增加一个实型栈，而字符型数据仍用整形栈存储，但是这样多个数据栈之间运算很复杂，我们可以取巧一下，将原来的整形栈变成浮点型栈，运算过程都是浮点型数据运算，当需要输入输出时，我们再通过强制转换字符或者整形。2） 增加字符型，实型需要修改的地方很多，在头文件和源文件中，只要出现了var或者variable单词的地方，我们一般都要增加字符型和实型的语句（默认var为整形标识符），如枚举标识符fct结构体中要增加charcon和realcon，增加字符型和实型声明函数，statement()函数中增加字符实型的分析，输入输出指令增加输入输出字符实型等等。3） 下面列举部分增加或者修改了的东西头文件中enum object constant, variable, procedur, charcon, realcon,; /* fct类型分别标识类PCODE的各条指令 */struct instruction enum fct f; int l; double a; /改的;Interptet()函数中double sstacksize; /stacksize常量定义，假想的栈式计算机有500个栈单元, s为栈式计算机的数据内存区int chardeclaration(int *ptx,int lev,int *pdx) /声明if (sym=ident) enter(charcon,ptx,lev,pdx); getsymdo; else