编译技术课程设计B试验报告词法分析器设计 算符优先分析程序设计 基于算符优先分析方法的语法制导翻译程序设计.doc

课程设计报告( 2010 - 2011年度第 1 学期)名 称：编译技术课程设计B 题 目：词法分析器设计 算符优先分析程序设计 基于算符优先分析方法的语法制导翻译程序设计院 系： 计算机系 班 级： 网络0802 学 号： 学生姓名： 指导教师： 设计周数： 1周 成 绩： 日期：2010年12月31一、课程设计的目的与要求1词法分析器设计的目的与要求1.1 词法分析器设计的实验目的本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术设计出词法分析器，了解扫描器的组成结构，不同种类单词的识别方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。1.2 词法分析器设计的实验要求设计一个扫描器，该扫描器是一个子程序，其输入是源程序字符串，每调用一次识别并输出一个单词符号。为了避免超前搜索，提高运行效率，简化扫描器的设计，假设该程序设计语言中，基本字（也称关键词）不能做一般标识符用，如果基本字、标识符和常数之间没有确定的运算符或界符作间隔，则用空白作间隔。单词符号及其内部表示如表1-1所示，单词符号中标识符由一个字母后跟多个字母、数字组成，常数由多个十进制数字组成。单词符号的内部表示，即单词的输出形式为二元式：（种别编码,单词的属性值）。表1-1单词符号及其内部表示单词符号种别编码单词的属性值BEGINIFTHENELSEEND标识符整型常数+*（）123456789101112在名字表中的地址十进制整数2算符优先分析程序设计的目的和要求2.1 算符优先分析程序设计的实验目的本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 设计、编写和调试算符优先分析程序，了解算符优先分析程序的组成结构，掌握实现通用算符优先分析算法的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。2.2 算符优先分析程序设计的实验要求算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入串是句子则输出“YES”，否则输出“NO”和错误信息。算符优先分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用,本题目给出文法的目的是为了便于对语法分析结果进行验证。(1)文法设算符优先文法为： 说明：i为整型常数或者为标识符表示整型变量；使用中用*表示。(2)优先关系表设优先关系表如表1-2所示。表1-2优先关系表+ * i ( ) # + * i ( ) # 3基于算符优先分析方法的语法制导翻译程序设计的目的和要求3.1 基于算符优先分析方法的语法制导翻译程序设计的实验目的本实验是为计算机科学与技术专业的学生在学习编译技术课程后，为加深对课堂教学内容的理解，培养解决实际问题能力而设置的实践环节。通过这个实验，使学生应用编译程序设计的原理和技术, 通过设计、编写和调试语法制导翻译程序，掌握从一种语句的语法和语义出发，构造相应的语义子程序，实现基于算符优先分析方法的语法制导翻译的方法。能使得学生在设计和调试编译程序的能力方面有所提高。为将来设计、分析编译程序打下良好的基础。3.2 基于算符优先分析方法的语法制导翻译程序设计的实验要求算符优先分析方法是通过反复把输入符号移进分析栈，使用优先关系表在分析栈顶寻找最左素短语，将其归约为一个非终结符号而实现的。这个分析过程与非终结符号无关，当由文法产生了优先关系之后文法也就失去了作用（所以本题目无需给出文法）。基于算符优先分析方法的语法制导翻译是在算符优先语法分析的基础上进行翻译工作（即语义分析），每当将一个最左素短语归约为一个非终结符号时，就调用对应产生式的语义子程序，去完成相应的语义翻译工作，这步归约使用的产生式对非终结符号不加区分（即将所有的非终结符号用一个通用的非终结符号表示）。语法制导翻译程序的输入是终结符号串（即单词符号串，以一个“”结尾），如果输入符号串是句子,则按照其语义进行翻译,输出等价的四元式序列（作为练习应显示输出）。二、课程设计正文1 词法分析器设计1.1 以文件流的方式对词法进行输入句子。1.2 标识符和常数的属性值（1）标识符和常数的属性值为该单词在名次表或常数表中登机项的相对地址；（2）当识别出一个标识符或常数时，要查名字表或常数表，若表中有其登记项，则把得到的登记项地址作为其属性值；（3）若表中没有其登记项，则建立一个新登记项，该登记项地址作为其属性值，此处的地址为在表中的下标。1.3 主要数据结构（1）属性类Dog，内含某一单词的显示字符串和类别，类别包括关键字、标识符、常数；（2）输入缓冲区Buffer100，类型为字符型；（3）关键字表Letter，类型为Dog；（4）标识符表Varible，类型为Dog，存储在句子中出现过的标识符；（5）常数表Constant，类型为Dog，存储在句子中出现过的常数；（6）设置全局变量b，v，c，l记录输入缓冲区、标识符表、常数表、关键字表的当前最后一个指针。1.4 词法错误处理：出错则显示错误所在字符位置。2 算符优先分析程序设计2.1 以文件流的方式对词法进行输入句子。2.2 主要数据结构（1）优先关系表XX，全局变量，事先设定；（2）分析栈类Stack，内含数组array存储终结符号、“#”、非终结符N，和数组array的长度size；（3）数组str，用于存放输入字符串。2.3 算法主要使用两个while嵌套循环，外层为当前字符a不为#则继续，内层循环当前字符a与其后一个终结符的相对优先关系为大于时，则进行规约，否则执行移入操作；2.4 当分析栈中进入#，且分析栈中只剩三个字符时，表示分析成功，否则失败。2.5 出错则显示错误所在字符位置。3 基于算符优先分析方法的语法制导翻译程序的设计3.1 该实验算法是在第二个实验的基础上，将规约后产生的N变为临时变量Ei或中间变量Ti，当产生中间变量的四元式时，则输出该四元式。3.2 为实现算法，这里用到词法分析的思想，将输入字符串先通过词法分析，转化为各单词的属性值或地址值。此做法便于实现数组的输出和查看。三、课程设计总结或结论1词法分析器设计在做这个实验以前一直认为编译的词法分析器是计算机内部某个硬件部分。由于该门课程结课较早，有些内容需要重新翻书查找。通过这次实验，我对之前学过的内容有了更深的理解，了解了扫描器的组成结构、不同种类单词的识别方法，掌握了由单词的语法规则触发、画出识别单词的状态转换图、然后再用程序实现的扫描器设计方法。2算符优先分析程序设计该程序的主要难点在于何时规约和何地规约，以及规约前后对几个指针位置的处理。通过本次实验一定程度上提高了软件开发能力，对编译原理这一门课程也有了比较深刻的了解，掌握了算符优先分析方法。最后，由于所学知识不够全面，实验在很多方面还有待完善，在以后的学习过程中，会掌握更多知识，力求做到更好。3基于算符优先分析方法的语法制导翻译程序的设计关于语法制导的内容之前未在课堂上有学过，首先锻炼了我的自学能力，通过学习和实践掌握了从一种语句的语法和语义出发，构造相应的语义子程序，实现语法制导翻译的方法。这个实验有着第二个实验的基础，保持算符优先分析的整体思想，在此基础上利用词法分析器的思想设计了一段模数转换程序，将字符串转换为数字形式。通过自己思考摸索，不断调试，最终使程序得以正常运行。四、参考文献1 陈火旺，刘春林. 程序设计语言编译原理. 北京：国防工业出版社，第三版. 2008，92 宋雨，程晓荣，黄志强. 计算机综合实践指导. 北京：清华大学出版社，第一版. 2004，2附录（设计流程图、程序、运行结果等）（一）流程图1 词法分析器设计开始结束初始化读入需要分析的句子还有单词未分析？否是是字母？是否其他单词分析程序是数字？否输出单词二元式关键字或标识符分析程序读一个字符是常数分析程序2 算符优先分析程序设计开始结束初始化，显示算符优先矩阵打开需要读入的文档a的优先关系大于arry中最后一个终结符？是是Array为空？否是将array中优先关系一样的字符规约为N构造字符串s ，存储需要分析的句子从s 中读取一个字符a将a压入数组array3. 基于算符优先分析方法的语法制导翻译程序的设计开始结束初始化，显示算符优先矩阵打开需要读入的文档da的优先关系大于arry中最后一个终结符？是是Array为空？否是将array中优先关系一样的字符规约为临时变量或中间变量，如有产生四元式则输出构造字符串s ，存储需要分析的句子从digital 中读取一个字符da将da压入数组array对s里的每个字符进行模数转换，存入digital（二）程序代码1 词法分析器设计#include<iostream>#include<stdlib.h>#include <ctype.h>#include<string.h>using namespace std;char strToken20;/存当前构成字符串class Dogchar info20;int race;public:Dog(char cc20,int rr)/构造函数strcpy(info,cc);race=rr;int comp(char ss20)/比较strToken是否为此类别，否返回0if(strcmp(info,ss)=0)return race;return 0;char Buffer100;/输入缓冲区int b;/Buffer指针char ch;/当前读进字符Dog* Varible20;/符号表Dog* Constant20;/常数表Dog* Letter20;/已有单词表int v,c,l;/对应尾指针的后一个int a2;void init0()b=0;v=0;c=0;l=0;Letterl+=new Dog("BEGIN",1);Letterl+=new Dog("IF",2);Letterl+=new Dog("THEN",3);Letterl+=new Dog("ELSE",4);Letterl+=new Dog("END",5);void init()ch=' 'a0=-1;a1=-1;strcpy(strToken,"");void GetChar()/取当前字符ch=Bufferb;b+;void GetBC()/取字符直到不为空格while(ch=' ')GetChar();bool IsLetter()/判断是否为字母if(ch>='A'&&ch<='Z')return 1;else if(ch>='a'&&ch<='z')return 1;return 0;bool IsDigit()/判断是否为数字if(ch>='0'&&ch<='9')return 1;return 0;void Concat()/把字符连接到当前短语后边strcat(strToken,&ch);void Retract()/回退一个字符ch=' 'b-;int Reserve()/*整型函数过程，对strToken则可回送0值中的字符串查找保留字表，若它是一个保留字则返回它的编码;否则返回非保留字信息，譬如若0不是保留字的编码*/int i,x;for(i=0;i<l;i+)x=Letteri->comp(strToken);if(x>0)return x;return 0;int InsertId()/整型函数过程，将strToken中的标识符插入符号表，返回符号表指针Variblev=new Dog(strToken,v+1);v+;int i=v;return i;int InsertConst()/整型函数过程，将strToken中的常数插入常数表，返回常数表指针Constantc=new Dog(strToken,c+1);c+;return c;void ProError()cout<<endl<<"第"<<b<<"个字符""<<Bufferb-1<<""出错"<<endl;/cout<<"errorerror!"<<endl;void f()/词法分析器int code, value;init();/int a2;/作为return（种别，属性）GetChar(); GetBC();if(IsLetter()while (IsLetter()|IsDigit()Concat(); GetChar();Retract();code=Reserve();if (code=0)value=InsertId();a0=6;/该单词为标识符a1=value;return;/return a;elsea0=code;/该单词为保留字a1=-1;return;/return a;else if (IsDigit()while(IsDigit()Concat();GetChar();Retract();value=InsertConst();a0=7;/该单词为常数a1=value;return;/return a;else if (ch='=')a0=8;a1=-1;return;/return a;else if (ch='+')a0=9;a1=-1;return;/return a;else if (ch='*')GetChar();if (ch='*')a0=11;a1=-1;return;/return a;Retract();a0=10;a1=-1;return;/return a;else if (ch=',')a0=12;a1=-1;return;/return a;else if (ch='(')a0=13;a1=-1;return;/return a;else if (ch=')')a0=14;a1=-1;return;/return a;else ProError(); /*错误处理*/a0=-1;a1=-1;return;/return a;void disp()char x;/if(a0=-1)/ProError();if(a1=-1)x='-'cout<<"("<<a0<<","<<x<<")"elsecout<<"("<<a0<<","<<a1<<")"void main()init0();/strcpy(Buffer,"BEGIN IF ELSE abcde 1234");/char in100; /用于接收输入文件名/ char str100;/存句子FILE *fin; /用于指向输入文件的指针cout<<"请输入所需文件名(xxx.txt)："cin>>in;while(fin=fopen(in,"r")=NULL) /判断输入文件名是否正确cout<<endl<<"打开词法分析输入文件出错!"<<endl;cout<<"请重新输入："strcpy(in,"");cin>>in;int m=0;/记录str句子串的长度char ch1='a'while (ch1!='#')/从文件中读入一串字符ch1=getc(fin);Bufferm+=ch1;/cin>>Buffer;int lllong=m-1;/cout<<lllong<<endl;while(b<lllong)init();f();disp();cout<<endl;/return;2 算符优先分析程序设计#include<string.h>#include<stdlib.h>#include <ctype.h>#include<iostream>using namespace std;const int maxsize=100; /为数组str、in分配的最大存储空间const int length=100;/为数组array分配的最大存储空间char XX88=' ','+','*','!','i','(',')','#', '+','>','<','<','<','<','>','>', '*','>','>','<','<','<','>','>', '!','>','>','<','<','<','>','>', 'i','>','>','>',' ',' ','>','>', '(','<','<','<','<','<','=',' ', ')','>','>','>',' ',' ','>','>', '#','<','<','<','<','<',' ','='class Stackprivate:int size;/size为当前数组array的大小char arraylength;/用于存储读入的字符public:Stack()size=0;/数组array的初始长度为0void push(char ch)if(size<length)/如果数组未满，则压入arraysize=ch;size+;else/若数组已满，则给出出错信息cout<<"overflow!"<<endl;int pop(char ch,int len)/弹出字符准备规约if(size-len>=0)for(int i=0;i<len;i+)chi=arraysize-len+i;size-=len;return len;elsecout<<"参数错误!"<<endl;return 0;char judge(int pos)/判断大小是否合法if(pos>=0&&pos<size)return arraypos;return '0'void disp_all()/输出当前数组中的字符for(int i=0;i<size;i+)if(judge(i)='!')cout<<"*"elsecout<<judge(i);if(size>7)cout<<'t'<<'t'elsecout<<'t'<<'t'<<'t'int getsize()/返回当前数组大小return size;char guiyue(char ch)/规约为'N' return 'N'int isnumch(char ch)/判断ch是不是数字或小写字母return (ch>='0'&&ch<='9'|ch>='a'&&ch<='z');int getrank(char ch1,char ch2)/根据算符优先分析矩阵设置读入优先次序 /0表示等于，1表示大于，-1表示小于，2表示没有优先关系int i,j;if(isnumch(ch1)ch1='i'if(isnumch(ch2)ch2='i'switch(ch1)case '+':i=1;break;case '*':i=2;break;case '!':i=3;break;case 'i':i=4;break;case '(':i=5;break;case ')':i=6;break;case '#':i=7;break;switch(ch2)case '+':j=1;break;case '*':j=2;break;case '!':j=3;break;case 'i':j=4;break;case '(':j=5;break;case ')':j=6;break;case '#':j=7;break;if(XXij='>')return 1;else if(XXij='<')return -1;else if(XXij='=')return 0;elsereturn 2;int isvt(char ch)/区别参加规约的资格if(ch>='a'&&ch<='z')return 1;if(ch>='0'&&ch<='9')return 1;for(int i=0;i<8;i+)if(ch=XX0i)return 1;return 0;/*主函数*/void main()cout<<"=该文法的算符优先矩阵如下="<<endl;int i;for(i=0;i<8;i+) /输出算符优先矩阵for(int j=0;j<8;j+)if(XXij='!')cout<<"*"<<'t' elsecout<<XXij<<'t' cout<<endl;char inmaxsize; /用于接收输入文件名 char strmaxsize;/存句子FILE *fin; /用于指向输入文件的指针cout<<"请输入所需文件名(xxx.txt)："cin>>in;while(fin=fopen(in,"r")=NULL) /判断输入文件名是否正确cout<<endl<<"打开词法分析输入文件出错!"<<endl;cout<<"请重新输入："strcpy(in,"");cin>>in;int m=0;/记录str句子串的长度char ch1='a'while (ch1!='#')/从文件中读入一串字符ch1=getc(fin);strm+=ch1;strm='#'/将'#'赋给字符串尾Stack s;/定义Stack类的变量sint len;len=int(strlen(str);/取出输入字符串的长度 s.push('#');/先把'#'压入数组arrayint k=s.getsize()-1;/k为当前数组array读入已读入字符的位置标识,int t=0;/t为输入字符串数组str即将被读的字符位置标识,int j;/j用于记录当前数组array中的最后一个非终结符的位置char a=str0;/a用于传递即将读入的字符char ch10;/存规约串while(a!='#')/如果a不等于'#',则继续读入操作或规约操作a=strt;if(a='*')if(strt+1='*')a='!'t+;if(isvt(s.judge(k) j=k;elsej=k-1;while(isvt(a)&&getrank(s.judge(j),a)=1)/判断是否满足规约的条件 > s.disp_all();/规约后输出当前数组array中的字符int h=j,low=j-1;/h记录要规约的位置，low记录规约后数组array中的最qian一个非终结符的位置if(!isvt(s.judge(low)low-;while(getrank(s.judge(low),s.judge(h)!=-1)/寻找最前一个非终结符的位置用low记录h=low;low-;if(!isvt(s.judge(low)low-;h=s.getsize();/array的长度low+;/规约的起始位置int len=h-low; /len记录要规约的长度for(int p=0;p<10;p+)chp='0's.pop(ch,len);/弹出要规约的字符用字符串ch存储char c=guiyue(ch);/将ch规约为Ns.push(c);/再将规约后的N压入数组中cout<<" 规约: "for(i=0;i<strlen(ch);i+)if(chi='!')cout<<"*"elsecout<<chi;cout<<" -> "<<guiyue(ch)<<endl;j=s.getsize()-1;if(!isvt(s.judge(j)j-;/s.disp_all();if(!(a>='A'&&a<='Z')&&getrank(s.judge(j),a)=2)/当待输入字符不是大写字母且与前一个 /非终结符无优先关系则提示出错并给出提示cout<<"出错!"<<endl;cout<<"错误为第 "<<t+1<<"个字符 :"<<strt<<endl;exit(0);elses.disp_all();if(a='!')cout<<"移进: *"<<endl;elsecout<<"移进: "<<a<<endl;s.push(a);/将a压入数组array/读入后输出当前数组array中的字符t+;k=s.getsize()-1;s.disp_all();char temp10; s.pop(temp,3);if(s.getsize()=0)/如果最后数组array的长度size的值为0，则分析成功cout<<"成功!"<<endl;else/否则，分析失败cout<<"失败!"<<endl;fclose(fin);/关闭输入文件 3 基于算符优先分析方法的语法制导翻译程序的设计#include<string.h>#include<stdlib.h>#include <ctype.h>#include<iostream>using namespace std;typedef class Four *C;char XX88=' ','+','*','!','i','(',')','#', '+','>','<','<','<','<','>','>', '*','>','>','<','<','<','>','>', '!','>','>','<','<','<','>','>', 'i','>','>','>',' ',' ','>','>', '(','<','<','<','<','<','=',' ', ')','>','>','>',' ',' ','>','>', '#','<','<','<','<','<',' ','='const int maxsize=100; /为数组str、in分配的最大存储空间const int length=100;/为数组array分配的最大存储空间int digitalmaxsize;int d_len=0;char B21;/标识符,b0记录最后一个的下标int E21;/临时变量,e0记录最后一个的下标,1xx为标识符地址，2xx为临时变量地址C Gama21;/一个中间变量即一个四元式，gamai记录最后一个下标int a=0,b=0,c=0;/B,E,Gama的最后一个下标 int ATD(char ch);/将单个字符转为为数字int entry(char ch);/查找ch是否在名字表内，返回名字表内的下标+100，如没有则将其加入表中-okint newtemp(int t3);/新建一个临时变量，返回其在临变表中的下标+200void fuzhi(int m,int n);/m.place:=n.placeint guiyue(int ch,int ll);/规约为'N'int getrank(int i,int j);/根据算符优先分析矩阵设置读入优先次序int isword(char ch);/判断是否为字母/gai!void disp_one(int i);/输出单个i代码的字符，标识符或符号void disp_deep_one(int i);/输出单个i代码的字符，标识符或符号typedef class Four/四元式char fuhao;/int s2,s3,s4;/(fuhao,s2,