<<编译原理>>
课内实验报告
项目名称 PL/0编译器 学 院____ 计算机学院_______
专 业_ _ 年级班别________ 学 号 _ 学生姓名_______ ___ 辅导教师_______
成 绩_______ _______
目录
1
一、课内实验的内容------------------------------------------4 二、实验修改部分--------------------------------------------4 三、概述-------------------------------------------------11 四、结构设计说明-------------------------------------------11 五、各功能模块描述-----------------------------------------14 六、主要成份描述------------------------------------------14 七、测试用例----------------------------------------------16 八、开发过程和完成情况--------------------------------------21
一、课内实验的内容
对PL/0作以下修改扩充：
（1）增加单词：保留字 ELSE，FOR， STEP，RETURN
运算符 +=，-=，++，--，&，|，~
（2）修改单词：不等号# 改为 <> （3）增加条件语句的ELSE子句
二、实验修改部分：
1、增加四个保留字和七个运算符，共十一个单词。
修改部分：#define symnum 43 //保留字从32增加到43个
2、增加五个保留字：ELSE，FOR，STEP，RETURN 1头文件pl0.h ○
enum symbol { 新增加单词: elsesym, forsym, stepsym,returnsym, pluseq/* += */,plusone/* ++ */,plus/* + */,minuseq/* -= */,minusone/* -- */,minus/* - */,and,or,not}
2头文件pl0.h ○
#define norw 24 //关键字从13增加到24个
3PL0.cpp ○
init();
新增加:（增加后数组的内容要再次根据字母顺序重新排列） strcpy(&(word[0][0]),\"begin\"); strcpy(&(word[1][0]),\"call\"); strcpy(&(word[2][0]),\"const\");
2
strcpy(&(word[3][0]),\"do\");
strcpy(&(word[4][0]),\"else\"); /*增加单词：保留字else*/ strcpy(&(word[5][0]),\"end\");
strcpy(&(word[6][0]),\"for\"); /*增加单词：保留字 for*/ strcpy(&(word[7][0]),\"if\"); strcpy(&(word[8][0]),\"odd\");
strcpy(&(word[9][0]),\"procedure\"); strcpy(&(word[10][0]),\"read\");
strcpy(&(word[11][0]),\"return\");/*增加单词：保留字 return*/ strcpy(&(word[12][0]),\"step\"); /*增加单词：保留字step*/ strcpy(&(word[13][0]),\"then\"); strcpy(&(word[14][0]),\"while\"); strcpy(&(word[15][0]),\"write\"); wsym[0]=beginsym; wsym[1]=callsym; wsym[2]=constsym; wsym[3]=dosym;
wsym[4]=elsesym; /*else*/ wsym[5]=endsym;
wsym[6]=forsym; /*for*/ wsym[7]=ifsym; wsym[8]=oddsym; wsym[9]=procsym; wsym[10]=readsym;
wsym[11]=returnsym; /*return*/ wsym[12]=stepsym; /*step*/ wsym[13]=thensym; wsym[14]=whilesym; wsym[15]=writesym;
3、增加四个运算符 ：+=，-=，++，-- ，∧，∨，┓
PL0.cpp getsym();
增加对+,-,++,--,+=,-=的识别；
Statement();
增加对+，-，++，--，-=的语句的处理；
1Init（）中改动： ○
ssym[‘&’]=and; ssym[‘|’]=or; ssym[‘~’]=not;
facbegsys[plusone]=true; // 添加前自加运算 facbegsys[minusone]=true;// 添加前自减运算
2Getsym（）增加的内容： ○
int getsym()
3
{
int i,j,k; while( ch=='
}
sym=ident;
'||ch==10||ch==9)
{ getchdo;
}
if(ch>='a'&&ch<='z') { k=0; do{ if(k getchdo; }while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9'); a[k]=0; strcpy(id,a); i=0; j=norw-1; do{ k=(i+j)/2; if(strcmp(id,word[k])<=0) { j=k-1; } if(strcmp(id,word[k])>=0) { i=k+1; } }while(i<=j); if(i-1>j) { sym=wsym[k]; } else { } else { if(ch>='0'&&ch<='9') { k=0; num=0; sym=number; do{ num=10*num+ch-'0'; k++; getchdo; }while(ch>='0'&&ch<='9'); /*获取数字的值*/ k--; if(k>nmax) { error(30); } } else { if(ch==':') /*检测赋值符号*/ { getchdo; if(ch=='=') { sym=becomes; getchdo; } else { sym=nul; /*不能识别的符号*/ } } else { 4 if(ch=='<') /*检测小于或小于等于符号*/ { getchdo; if(ch=='=') { sym=leq; getchdo; } else { sym=lss; } } else if(ch=='>') /*检测大于或大于等于符号*/ { getchdo; if(ch=='=') { sym=geq; getchdo; } else { sym=gtr; } } /*这里之间为添加的内容*/ else if(ch=='+'){ /*检测+,+=,++符号*/ getchdo; if(ch=='='){ sym=pluseq; getchdo; }else if(ch=='+'){ sym=plusone; getchdo; }else{ sym=plus; } }else if(ch=='-'){/*检测-,-=,--符号*/ getchdo; if(ch=='=') { sym=minuseq; getchdo; } else if(ch=='-') { sym=minusone; getchdo; } else { sym=minus; } } /*这里之间为添加的内容*/ else{ sym=ssym[ch];/* 当符号不满足上述条件时，全部按照单字符号处理*/ //getchdo; //richard if(sym!=period) { getchdo; } //end richard } } } } 5 return 0; } 3Statement()增加的内容：(将本来“if(sym==becomes)……”部分的内容修○ 改为处理++，+=，--，-=)，并在Statement()中定义变量int sym2; if(sym==becomes||sym==pluseq||sy m==minuseq|| sym==plusone||sym==minusone) { sym2=sym; getsymdo; gendo(lod,lev-table[i].level,tab le[i].adr); } else { error(13); } if(sym2==plusone||sym2==minusone)/* 准备按照a++、a--语句 处理，与read类似*/ { if(i!=0) { if(sym2==plusone) { gendo(lit,0,1); gendo(opr,0,2); gendo(sto,lev-table[i].level,table[i].adr); } if(sym2==minusone) { gendo(lit,0,1); gendo(opr,0,3); gendo(sto,lev-table[i].level,table[i].adr); } } } else { memcpy(nxtlev,fsys,sizeof(bool)* symnum); expressiondo(nxtlev,ptx,lev); if(i!=0) { if(sym2==becomes) gendo(sto,lev-table[i].level,tab le[i].adr); if(sym2==pluseq) { gendo(opr,0,2); gendo(sto,lev-table[i].level,tab le[i].adr); } if(sym2==minuseq) { 6 gendo(opr,0,3); } }//else gendo(sto,lev-table[i].level,tab } } le[i].adr); } } 4、修改单词：不等号# 改为 <> PL0.cpp init(); 移除: ssym['#']=neq; 1在getsym()里增加对<>的识别(在<或<=基础上修改)。 ○ 下面为在<基础上修改，注意在if(ch==’<’)中修改，不包括else if(ch=='>')那部分： if(ch=='<') /*检测小于或小于等于符号*/ { getchdo; if(ch=='=') { } /*在之间添加*/ } else if(ch=='>') //add neq { sym=neq; } /*在之间添加*/ else { } sym=lss; getchdo; sym=leq; getchdo; 5、增加条件语句的ELSE子句 PL0.cpp 1在statement()里的“if...then”语句处理的基础上添加对else子句○ 的处理，使之能处理if……then……else……的语句。 7 else { if(sym==ifsym) ); memcpy(nxtlev,fsys,sizeof(bool)*symnum /*准备按照if语句处理*/ { getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum); nxtlev[thensym]=true; nxtlev[dosym]=true; /*后跟符号为then 或do*/ conditiondo(nxtlev,ptx,lev); /*调用条 件处理（逻辑运算）函数*/ if(sym==thensym) { getsymdo; } else { error(16); /*缺少then*/ } cx1=cx; /*保存当前指令地 址*/ gendo(jpc,0,0); /*生成条件跳转 指 令，跳转地址暂写0*/ /*这里之间开始添加*/ //添加后跟符号 nxtlev[elsesym]=true; statementdo(nxtlev,ptx,lev); /*处理 then后的语句*/ code[cx1].a=cx; /*经statement处 理后 ，cx为then后语句执行完的位置，它正是 前面未定的跳转地址*/ if(sym==elsesym) { cx2=cx; getsymdo; gendo(jmp,0,0); code[cx1].a=cx; statementdo(fsys,ptx,lev); code[cx2].a=cx; } /*这里之间开始添加*/ } else { if(sym==beginsym) /*准备按照复合语句 处理*/ { getsymdo; memcpy(nxtlev,fsys,sizeof(bool)*symnum ); 8 nxtlev[semicolon]=true; else { nxtlev[endsym]=true;/*后跟符号为分号或 end*/ /*循环调用 error(10);/*缺少分号*/ } 语句处理函数，直到下一个符号不 是语句开始符号或收到end*/ statementdo(nxtlev,ptx,lev); } if(sym==endsym) { statementdo(nxtlev,ptx,lev); while(inset(sym,statbegsys)|| sym==semicolon) { getsymdo; } else { if(sym==semicolon) { error(17); /*缺少end或分 号*/ } } getsymdo; } 2写出相关文法: ○ G(S): S→if S else S | if S | a 3Else语法图： ○ 语句ident：=表达式if条件then语句1else语句2 9 三、概述 源语言：PL/0语言 目标语言：假想栈式计算机的汇编语言 实现工具： VC++6.0 运行平台： Windows 7 四、结构设计说明 1、PL/0编译程序的结构图如下： PL0源程序词法分析程序表格管理程序出错处理语法分析程序代码生成程序目标程序 由于PL/0编译程序采用一趟扫描方法，所以语法语义分析过程block是整个编译程序的核心。下面给出编译程序的总体流程图，以弄清block过程在整个编译程序中的作用。在流程图中可以看出，主程序置初值后先调整用读单词过程getsym取一个单词，然后再调用语法分析过程block，直到遇源程序的结束符“.”为止。 10 11 开始置初值调用GETSYM取单词调用BLOCK过程当前单词是否为源程序结束符‘.’N出错YY程序中是否有错误？N调用解释过程INTERPRET解释执行目标程序结束 打印错误 12 五、 各功能模块描述 1GetSym() : 词法分析, 从源文件中读出若干有效字符，组成token串，识别它的类○ 型为保留字/标识符/数字或其它符号。 2GEN() : 目标代码生成过程，本过程用于把生成的目标代码写入目标代码数组，供后○ 面的解释器解释执行. 3TEST() : 测试当前单词是否合法 ○ 4ENTER() : 在名字表中加入一项 ○ 5POSITION () : 查找名字的位置,找到则返回名字表中的位置,否则返回0 ○ 6ConstDeclaration() : 常量声明处理 ○ 7VarDeclaration() : 变量声明处理 ○ 8ListCode() : 输出目标代码清单 ○ 9FACTOR() : 因子处理过程 ○ 10TERM() : 项处理过程 ○ 11EXPRESSION() : 表达式处理过程 ○ 12CONDITION() : 条件处理过程 ○ 13STATEMENT() : 语句处理过程 ○ 14Block() ○: 编译程序主体, 参数：lev:这一次语法分析所在的层次，tx:符号表指针， 15fsys:用于出错恢复的 单词集合 ○ 16BASE() : 通过过程基址求上一层过程的基址 ○ 16Interpret() : 解释程序, PL/0编译器产生的类PCODE目标代码解释运行过程 ○ 六、主要成份描述 1.符号表 在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息,这些信息集中反映了标识符的语义特征属性.符号表的主要功能如下: 1、收集符号属性 ○ 2、上下文语义合法性检查的依据 ○ 3、作为目标代码生成阶段地址分配的依据. ○ 4、符号表的数据结构： ○ struct tablestruct { char name[al]; /*名字*/ enum object kind; /*类型：const，var，array orprocedure*/ int val; /*数值，仅const使用*/ int level; /*所处层，仅const不使用*/ int adr; /*地址，仅const不使用*/ int size; /*需要分配的数据区空间，仅procedure使用*/ }; struct tablestruct table[txmax]; /*名字表*/ 13 2.运行时的存储组织和管理 当源程序经过语法分析,如果未发现错误时,由编译程序调用解释程序,对存放在CODE中的代码CODE[0]开始进行解释执行.当废弃结束后,记录源程序中标识符的TABLE表已没有作用.因此存储区只需以数组CODE存主的只读目标程序和运行机制时的数据区S,S是由解释程序定义的一维整数型数组. 解释执行时的数据空间S为栈式计算机的在座空间,遵循后进先出规则,对每个过程(包括主程序)当调用 时,才分配数据空间,退出过程进, 则所分配原则的数据空间被释放. 解释程序还定义了4个寄存器:1、指令寄存器.存放当前正在解释的一条目标指令2、程序地址寄存器.指向下一条要执行的目标程序的地址3、栈顶寄存器.4、基址寄存器.指向每个过程被调用时,在数据区S中给它分配原则的数据段起始地址,也称基地址. 为了实现过程被调用时给它分配数据段，过程运行结束后释放数据段以及嵌套过程之间结标志符引用的问题，当过程被调用时，在栈顶分配三个联系单元，这三个联系单元存放的内容分别为：SL静态链，动态链DL，RA返回地址。 3.语法分析方法 语法分析的任务是识别由词法分析给出的单词符号序列在结构上是否符合给定的文法规则.PL/0编译程序的语法分析采用了自顶向下的递归子程序法.粗略地说:就是对应每个非终结符语法单元,编一个独立的处理过程(或子程序).语法分析研究从读入第一个单词开始由非终结符’程序即开始符出发,沿语法描述图箭头所指出的方向进行分析.当遇到非终结符时,则调用相应的处理过程,从语法描述图看也就进入了一个语法单元,再沿当前所进入的语法描述图的箭头方向进行分析,当遇到描述图中是终结符时,则判断当前读入的单词是否与图中的终结符相匹配,若匹配,则执行相应的语义程序(就是翻译程序).再读取下一个单词继续分析.遇到分支点时将当前的单词与分支点上的多个终结符逐个相比较,若都不匹配时可能是进入下一非终结符语法单位或是出错. 如果一个PL/0语言程序的单词序列在整修语法分析中,都能逐个得到匹配,直到程序结束’.’,这时就说所输入的程序是正确的.对于正确的语法分析做相应的语义翻译,最终得出目标程序. 4.中间代码表示 14 PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可称为类pcode指令代码，它不依赖任何实际计算机，其指令集极为简单，指令格式如下： f L a lit 0 a Lod l a Sto l a Cal a Int 0 a jmp 0 a Jpc 0 a opr 0 0 opr 0 1 opr 0 2 opr 0 3 opr 0 4 opr 0 5 opr 0 6 opr 0 7 opr 0 8 opr 0 9 opr 0 10 opr 0 11 opr 0 12 opr 0 13 opr 0 14 opr 0 15 opr 0 16 将常数值取到栈顶，a为常数值 将变量值取到栈顶，a为偏移量，l为层差 将栈顶内容送入某变量单元中，a为偏移量，l为层差 调用过程，a为过程地址，l为层差 在运行栈中为被调用的过程开辟a个单元的数据区 无条件跳转至a地址 条件跳转，当栈顶布尔值非真则跳转至a地址，否则顺序执行 过程调用结束后,返回调用点并退栈 栈顶元素取反 次栈顶与栈顶相加，退两个栈元素，结果值进栈 次栈顶减去栈顶，退两个栈元素，结果值进栈 次栈顶乘以栈顶，退两个栈元素，结果值进栈 次栈顶除以栈顶，退两个栈元素，结果值进栈 栈顶元素的奇偶判断，结果值在栈顶 次栈顶与栈顶是否相等，退两个栈元素，结果值进栈 次栈顶与栈顶是否不等，退两个栈元素，结果值进栈 次栈顶是否小于栈顶，退两个栈元素，结果值进栈 次栈顶是否大于等于栈顶，退两个栈元素，结果值进栈 次栈顶是否大于栈顶，退两个栈元素，结果值进栈 次栈顶是否小于等于栈顶，退两个栈元素，结果值进栈 栈顶值输出至屏幕 屏幕输出换行 从命令行读入一个输入置于栈顶 七、测试用例 将需要测试的用例放在与pl0.exe同一个文件夹中 IF ELSE功能的测试,测试文件test3.pl0 15 16 <>替代#的测试，测试文件test5.pl0 17 八、开发过程和完成情况 心得体会： 这个实验开始做时觉得相对来说比较简单，主要是修改保留字数组。只要了解大概的程序运行，剩下的修改工作也就不是特别困难。 比如添加保留字ELSE，FOR， STEP，RETURN和运算符 +=，-=，++，--，&，|，~除了ELSE这个保留字具体实现了功能，其余的只是添加进去，并没有具体的功能，相当于只是声明。当然，由于添加的运算符是双符号的关系，在读取单词函数getsym中需要添加符号的识别判断。 而在把不等号#改为<>的时候，则需要把单符号数组中的#去掉，又因为<>是双符号关系，所以也要符号的判别。不过不等号本身具体功能都已经定义好，我们就不用管，只要能实现把<>判别出是不等号的意思就行了。当然，因为新添加了保留字，所以数组的大小也发生变化，只要适当改一下就行。所以，除了添加ELSE语句的具体功能比较难一点，其余的都相对简单。 比较繁琐的是添加getsym()中识别+=，-=，++，--，因为里面有多层if-else，每添加一步都要格外小心。 同时，对于这次实验比较遗憾的是并没有实现+=，-=，++，--功能，开始修改getsym函数时，我自己觉得程序不管是从逻辑上还是语法上是没问题，但真正输入相关的测试例子时，却经常出错，觉得问题不是出在getsym()函数中，因为时间有限，就只能将它留在编译原理课程设计中解决了。 18 因篇幅问题不能全部显示，请点此查看更多更全内容