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

1、编译原理课程设计学 院 计算机学院 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 20 年 月 日一、课程设计要求基本内容（成绩范围：“中”、“及格”或“不及格”）（1）扩充赋值运算：*= 和 /=扩充语句（Pascal的FOR语句）:FOR <变量>:=<表达式> TO <表达式> DO <语句>FOR <变量>:=<表达式> DOWNTO <表达式> DO <语句> 其中，语句的循环变量的步长为2，语句的循环变量的步长为-2。（3）增加运算：+ 和 -。选做内容（成绩评定范围扩大到

2、：“优”和“良”）（1）增加类型： 字符类型； 实数类型。（2）扩充函数： 有返回值和返回语句； 有参数函数。（3）增加一维数组类型（可增加指令）。（4）其他典型语言设施。二、概述目标：实现PL0某些特定语句实现语言：C语言实现工具平台：VS201运行平台：WIN7三、 结构设计说明与功能块描述PL/0编译程序的结构图PL/0编译程序的过程或函数的功能表过程或函数名简要功能说明pl0主程序error出错处理，打印出错位置和错误编码getsym词法分析，读取一个单词getch漏掉空格，读取一个字符gen生成目标代码，并送入目标程序区test测试当前单词符号是否合法block分程序分析处理过程en

3、ter登录名字表position(函数)查找标识符在名字表中的位置constdeclaration常量定义处理vardeclaration变量说明处理listode列出目标代码清单statement语句处理expression表达式处理term项处理factor因子处理condition条件处理interpret对目标代码的解释执行程序base(函数)通过静态链求出数据区的基地址PL/0编译程序的总体流程图启动置初值调用getsym取单词调用block过程是否为源程序结束符源程序是否有错误调用解释过程interpret解释执行目标执行目标程序结束出错打印错误NNYY四、 主要成分描述1、 符号

4、表编译程序里用了一个枚举类型enum symbol，然后定义了enum symbol sym来存放当前的符号，前面讲过，主程序定义了一个以字符为元素的一维数组word，称保留字表，这个保留字表也存放在符号表里，为了识别当前的符号是属于哪些保留字；还有标识符，拼数，拼符合词等的符号名都存放在符号表里，当sym存放当前的符号时，我们可以判断它是属于哪类的符号，然后加以处理。在运行的过程中，主程序中又定义了一个名字表，也就是符号表，来专门存放变量、常量和过程名的各个属性，里面的属性包括name，kind，val/level，adr，size，我们来举一个PL/0语言过程说明部分的片段：Const a

5、=35,b=49;Var c,d,e;Procedure p;Var g;nameKindVal/levelAdrsizeabcdepconstconstvariablevariablevariableprocedure3549LevLevLevlevdxdx+1dx+24gvariablelev+1dx当遇到标识符的引用时就调用position函数，根据当前sym的符号类型来查table表，看是否有过正确的定义，若已有，则从表中取相应的有关信息，供代码的生成用。若无定义则调用出错处理程序。2、 运行时存储组织和管理对于源程序的每一个过程（包括主程序），在被调用时，首先在数据段中开辟三个空间，

6、存放静态链SL、动态链DL和返回地址RA。静态链记录了定义该过程的直接外过程（或主程序）运行时最新数据段的基地址。动态链记录调用该过程前正在运行的过程的数据段基址。返回地址记录了调用该过程时程序运行的断点位置。对于主程序来说，SL、DL和RA的值均置为0。静态链的功能是在一个子过程要引用它的直接或间接父过程（这里的父过程是按定义过程时的嵌套情况来定的，而不是按执行时的调用顺序定的）的变量时，可以通过静态链，跳过个数为层差的数据段，找到包含要引用的变量所在的数据段基址，然后通过偏移地址访问它。在过程返回时，解释程序通过返回地址恢复指令指针的值到调用前的地址，通过当前段基址恢复数据段分配指针，通过

7、动态链恢复局部段基址指针。实现子过程的返回。对于主程序来说，解释程序会遇到返回地址为0的情况，这时就认为程序运行结束。解释程序过程中的base函数的功能，就是用于沿着静态链，向前查找相差指定层数的局部数据段基址。这在使用sto、lod、stoArr、lodArr等访问局部变量的指令中会经常用。类PCODE代码解释执行的部分通过循环和简单的case判断不同的指令，做出相应的动作。当遇到主程序中的返回指令时，指令指针会指到0位置，把这样一个条件作为终至循环的条件，保证程序运行可以正常的结束。3、 语法分析方法语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则.PL/0编

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

9、一个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为过程地址,

10、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.

11、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 从命令行读入一个输入置于栈顶（后续增加的指令后面介

12、绍）五、 测试用例1、 基本内容PL0代码：for.txtvar a,b; begin a:=3; b:=8; a*=b; b/=2; write(a); write(b); repeat a:=a+b; until a>50; write(a); write(b); for(a:=0;a<5;a+)b-; write(a); write(b); for a:=1 to 6 do b+=2; for b:=9 downto 4 do a+=2; write(a); write(b);end.结果截图：2、 选做内容1） 字符实型PL0：charreal.txtchar x;char

13、 y;real r;real s;beginx:='a'y:='b'read(r);read(s);write(x);write(y);write(r);write(s);s:=s-r;write(s);read(x);read(y);write(x);write(y);s:=7.344;r:=4.511;s:=s-r;write(s);end.结果截图：2） 数组PL0：shuzu.txtvar a4;var r1,r2,r3,r4;begina0:=55;a1:=66;a2:=77;a3:=88;r1:=11;r2:=22;r3:=33;r4:=44;a3:

14、=a0+a1;a2:=a1-r1;r1:=a0+a1;r2:=a1+r3;write(a0);write(a1);write(a2);write(a3);write(r1);write(r2);write(r3);write(r4);read(a0);read(a1);read(a2);read(a3);write(a0);write(a1);write(a2);write(a3);r1:=0;r2:=1;r3:=2;r4:=3;ar1:=55;ar2:=66;ar3:=77;ar4:=88;write(ar1);write(ar2);write(ar3); write(ar4);read(a

15、r1);read(ar2);read(ar3);read(ar4);write(ar1);write(ar2);write(ar3);write(ar4);end.结果截图：六、 开发过程1、 实现+，-，*=，/=比较简单，过程大致如下：1） 头文件中symbol枚举类型中得加上4个运算的保留字，修改symnum常量的大小以及保留字大小norw（都是+4）。2） Init()函数里增加4个运算保留字单词（得按照字母顺序）。3） Getsym()函数中增加对这4个运算符的分析，较简单就不列举了。4） Statement()函数中增加对运算符的解释生成代码，如下所示：switch(sym)cas

16、e becomes: /如果的确为赋值号 getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式break; case incsym: /如果为+ gendo(lod,lev-tablei.level,tablei.adr);gendo(lit,0,1);gendo(opr,0,2); getsymdo;break;case decsym: /如果为- gendo(lod,lev-tablei.level,tablei.adr);ge

17、ndo(lit,0,1); gendo(opr,0,3); getsymdo;break;case muleqlsym: /如果为*= gendo(lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,4); break;case diveqlsym: /如果是/= gendo(lod,lev-tablei.level,tablei.adr);g

18、etsymdo;memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev);gendo(opr,0,5); break;case inesym:/+=gendo(lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,2);break;case deesym:/-=ge

19、ndo(lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,3);break;default:error(8);printf("程序体内语句部分的后跟符不正确n");break;5)factor()因子函数也得添加+，-的分析，如下while(sym=incsym|sym=decsym)if(sym = incsym) ge

20、ndo(lit,0,1);gendo(opr,0,2);elsegendo(lit,0,1);gendo(opr,0,3);getsymdo;2、 实现forto.do. 和for.downto.do.语句1） 增加保留字和增加运算符类似，不再说明。2） 主要修改的是statement()函数中for单词的解释生成代码，如下所示if(sym=forsym) /如果遇到for语句getsymdo;if(sym=ident)i=position(id,*ptx);if(i=0) error(11);elseif(tablei.kind!=variable) /赋值语句中，赋值号左部标识符属性应是变

21、量error(12);i=0;elsegetsymdo;if(sym!=becomes) error(13); /赋值语句左部标识符后应是赋值号:=else getsymdo;memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlevtosym=true; /后跟符to和downtonxtlevdowntosym=true;expressiondo(nxtlev,ptx,lev); /处理赋值语句右部的表达式E1gendo(sto,lev-tablei.level,tablei.adr); /保存初值switch(sym)case tosym: /步长为的向

22、上增加getsymdo;cx1=cx; /保存循环开始点/将循环判断变量取出放到栈顶gendo(lod,lev-tablei.level,tablei.adr); memcpy(nxtlev,fsys,sizeof(bool)*symnum); /处理表达式E2nxtlevdosym=true; /后跟符doexpressiondo(nxtlev,ptx,lev);/*判断循环变量条件，比如for i:=E1 to E2 do S中，判断i是否小于E2，如小于等于，继续循环，大于的话，跳出循环*/gendo(opr,0,13); /生成比较指令，i是否小于等于E2的值cx2=cx; /保存循环

23、结束点/生成条件跳转指令，跳出循环，跳出的地址未知gendo(jpc,0,0);if(sym=dosym) /处理循环体Sgetsymdo;statement(fsys,ptx,lev); /循环体处理/增加循环变量步长为/将循环变量取出放在栈顶gendo(lod,lev-tablei.level,tablei.adr); gendo(lit,0,2); /将步长取到栈顶gendo(opr,0,2); /循环变量加步长/将栈顶的值存入循环变量gendo(sto,lev-tablei.level,tablei.adr); gendo(jmp,0,cx1); /无条件跳转到循环开始点/*回填循环结

24、束点的地址，cx为else后语句执行完的位置，它正是前面未定的跳转地址*/codecx2.a=cx;elseerror(29); /for语句中少了dobreak;case downtosym: /步长为的向下减少getsymdo;cx1=cx; /保存循环开始点/将循环判断变量取出放到栈顶gendo(lod,lev-tablei.level,tablei.adr); memcpy(nxtlev,fsys,sizeof(bool)*symnum); /处理表达式E2nxtlevdosym=true; /后跟符doexpressiondo(nxtlev,ptx,lev);/*判断循环变量条件，比

25、如for i:=E1 downto E2 do S中，判断i是否大于等于E2，如大于等于，继续循环， 小于的话，跳出循环*/gendo(opr,0,11); /生成比较指令，i是否大于等于E2的值cx2=cx; /保存循环结束点/生成条件跳转指令，跳出循环，跳出的地址未知gendo(jpc,0,0); if(sym=dosym) /处理循环体Sgetsymdo;statement(fsys,ptx,lev); /循环体处理/增加循环变量步长为/将循环变量取出放在栈顶gendo(lod,lev-tablei.level,tablei.adr); gendo(lit,0,2); /将步长取到栈顶g

26、endo(opr,0,3); /循环变量加步长/将栈顶的值存入循环变量gendo(sto,lev-tablei.level,tablei.adr); gendo(jmp,0,cx1); /无条件跳转到循环开始点/*回填循环结束点的地址，cx为else后语句执行完的位置，它正是前面未定的跳转地址*/codecx2.a=cx;else error(29);/for语句中少了dobreak;3、 增加一维数组1） 首先增加单字符和，symbol类型增加2个单词，枚举类型数量symnum加2，init()函数中单字符数组ssym增加2个单字符。2） 变量声明部分vardeclaration()函数需要

27、增加数组声明，如下所示：int vardeclaration(int *ptx,int lev,int *pdx) / 变量声明处理int num1,k,m;if (sym=ident) enter(variable,ptx,lev,pdx); getsymdo; else error(4);if(sym=lsquare) /标识符为''，数组变量说明处理 getsymdo;if(sym=number) num1=(int)num; /长度为数字*pdx=*pdx+num1-1; / 计算数组的长度并留出空间，移动指针getsymdo;else /长度为标识符m=positio

28、n(id,*ptx); /查找标识符的位置if(m=0) error(11);else if(tablem.kind=constant) /为常量 num1=tablem.val; /把其值赋给num1else error(41);m=0; *pdx=*pdx+num1-1;getsymdo;if(sym=rsquare) /标识符为数组的符号''，则取下一个单词getsymdo;else error(61); /漏掉括号''return 0;3） 语句处理statement()函数中需要处理很多，首先确认标识符后需要辨认是否为数组，然后在read和write等

29、语句分析部分需要辨认数组，分析主体大致如下 if(sym=ident) /以标识符开头，可能是赋值语句i=position(id,*ptx); /在符号表中查到该标识符所在位置if(i=0) /如果没找到error(11); /抛出11号错误printf("标识符未说明n");else if(tablei.kind!=variable&&tablei.kind!=realcon&&tablei.kind!=charcon) /在符号表中找到该标识符，但该标识符不是变量名error(12); /抛出12号错误printf("赋值语句中

30、，赋值号左部标识符属性应是变量n");i=0; / i置0作为错误标志elsegetsymdo; /获得下一个token，正常应为赋值号/与书本不同的地方，在这里除了赋值号:=/为/= *= + -if(sym=lsquare)getsymdo;if(sym=number) j1=(int)num;getsymdo;else if(sym=ident) j2=position(id,*ptx);j=1;getsymdo;else error(60);if(sym=rsquare) /判断下标后是否为'' getsymdo;tag=1; else error(61);s

31、witch(sym)case becomes: /如果的确为赋值号 getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式break; case incsym: /如果为+ if(j=1)varnumvarn=j2;varn+;gendo(lod2,lev-tablei.level,tablei.adr);elsegendo(lod,lev-tablei.level,tablei.adr);gendo(lit,0,1);gendo(o

32、pr,0,2); getsymdo;break;case decsym: /如果为- if(j=1)varnumvarn=j2;varn+;gendo(lod2,lev-tablei.level,tablei.adr);elsegendo(lod,lev-tablei.level,tablei.adr);gendo(lit,0,1); gendo(opr,0,3); getsymdo;break;case muleqlsym: /如果为*= if(j=1)varnumvarn=j2;varn+;gendo(lod2,lev-tablei.level,tablei.adr);elsegendo(

33、lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,4); break;case diveqlsym: /如果是/= if(j=1)varnumvarn=j2;varn+;gendo(lod2,lev-tablei.level,tablei.adr);elsegendo(lod,lev-tablei.level,tablei.adr);gets

34、ymdo;memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev);gendo(opr,0,5); break;case inesym:/+=if(j=1)varnumvarn=j2;varn+;gendo(lod2,lev-tablei.level,tablei.adr);elsegendo(lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expres

35、siondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,2);break;case deesym:/-=gendo(lod,lev-tablei.level,tablei.adr);getsymdo; /获取下一个token，正常应为一个表达式memcpy(nxtlev,fsys,sizeof(bool)* symnum);expressiondo(nxtlev,ptx,lev); /处理表达式gendo(opr,0,3);break;default:error(8);printf("程序体内语句部分的后跟符不正确n");break;if(i!=

36、0)/如果不曾出错，i将不为0，i所指为当前语句/左部标识符在符号表中的位置 if(j=1)varnumvarn=j2;varn+;gendo(sto2,lev-tablei.level,tablei.adr);elsegendo(sto,lev-tablei.level,tablei.adr+j1); /产生一行把表达式值写往指定内存的sto目标代码 4） Factor()因子处理函数中也需要辨认数组，分析过程如下：int factor(bool*fsys,int *ptx,int lev)int i,j,tag=1,flag=0;bool nxtlevsymnum;testdo(facbe

37、gsys,fsys,24); /开始因子处理前，先检查当前token是否在facbegsys /集合中。如果不是合法的token，抛24号错误，并通 /过fsys集恢复使语法处理可以继续进行while(inset(sym,facbegsys) /循环处理因子if(sym=ident) /如果遇到的是标识符i=position(id,*ptx); /查符号表，找到当前标识符在符号表中位置if(i=0) /如果查符号表返回为0，表示没有找到标识符error(11); /抛出11号错误printf("标识符未说明n");else /如果在符号表中找到了当前标识符的位置，开始生成相

38、应代码 switch(tablei.kind)case constant: /如果这个标识符对应的是常量，值为val，生成lit指令，把val放到栈顶gendo(lit,0,tablei.val);break;case variable: /如果标识符是变量名，生成lod指令 把位于距 /离当前层level的层的偏移地址为adr的变量放到栈顶getsymdo;if(sym=lsquare) /''getsymdo; if(sym=number) fte=num;getsymdo; else if(sym=ident) /把数组的下标赋给j和fte j=position(id,*

39、ptx);varnumvarn=j;varn+;flag=1;getsymdo;else error(60);if(sym=rsquare) getsymdo;tag=0; elseerror(61); /把数组元素放在栈顶if (flag=1)gendo(lod2,lev-tablei.level,tablei.adr); elsegendo(lod,lev-tablei.level,tablei.adr+fte); fte=0;else gendo(lod,lev-tablei.level,tablei.adr);tag=0;break;case procedur: /如果在因子处理中遇到

40、的标识符是过程名，出错了，抛21号错error(21);printf("表达式内标识符属性不能是过程n");break;case charcon: gendo(lod,lev-tablei.level,tablei.adr); break; case realcon: gendo(lod,lev-tablei.level,tablei.adr); break;if(tag=1)getsymdo; /获取下一token，继续循环处理elseif(sym=number|sym=realsym|sym=charsym) /如果因子处理时遇到数字if(num>amax) /数

41、超过允许最大值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=rpare

42、n) /子表达式分析完后，应遇到右括号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