您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 质量控制/管理 > 编译原理实验报告5-语法分析程序的设计
实验5语法分析程序的设计(2)一、实验目的通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析中算法优先分析方法。二、实验内容设计一个文法的算法优先分析程序,判断特定表达式的正确性。三、实验要求1、给出文法如下:G[E]E-T|E+T;T-F|T*F;F-i|(E);可以构造算符优先表如下:+*()i+*()i2、计算机中表示上述优先关系,优先关系的机内存放方式有两种1)直接存放,2)为优先关系建立优先函数,这里由学生自己选择一种方式;1、给出算符优先分析算法如下:k:=1;S[k]:=‘#’;REPEAT把下一个输入符号读进a中;IFS[k]∈VTTHENj:=kELSEj:=k-1;WHILES[j]aDOBEGINREPEATQ:=S[j];IFS[j-1]∈VTTHENj:=j-1ELSEj:=j-2UNTILS[j]Q把S[j+1]…S[k]归约为某个N;k:=j+1;S[k]:=N;ENDOFWHILE;IFS[j]aORS[j]aTHENBEGINk:=k+1;S[k]:=aENDELSEERRORUNTILa=‘#’1、根据给出算法,利用适当的数据结构实现算符优先分析程序;2、利用算符优先分析程序完成下列功能:1)手工将测试的表达式写入文本文件,每个表达式写一行,用“;”表示结束;2)读入文本文件中的表达式;3)调用实验2中的词法分析程序搜索单词;4)把单词送入算法优先分析程序,判断表达式是否正确(是否是给出文法的语言),若错误,应给出错误信息;5)完成上述功能,有余力的同学可以对正确的表达式计算出结果。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、分析文法中终结符号的优先关系;2、存放优先关系或构造优先函数;3、利用算符优先分析的算法编写分析程序;4、写测试程序,包括表达式的读入和结果的输出;5、程序运行效果,测试数据可以参考下列给出的数据。六、测试数据输入数据:编辑一个文本文文件expression.txt,在文件中输入如下内容:10;1+2;(1+2)*3+(5+6*7);((1+2)*3+4;1+2+3+(*4+5);(a+b)*(c+d);((ab3+de4)**5)+1;正确结果:(1)10;输出:正确(2)1+2;输出:正确(3)(1+2)*3+(5+6*7);输出:正确(4)((1+2)*3+4输出:错误(5)1+2+3+(*4+5)输出:错误(6)(a+b)*(c+d)输出:正确(7)((ab3+de4)**5)+1输出:错误七、实验报告要求实验报告应包括以下几个部分:1、给定文法优先关系和存放方式;+*()i#+*(e1)e2e2ie2e2#e3e4引入“#”,将句型包含起来并填入出错标记。使用二维数组将其存放。2、算符优先分析程序的算法和结构;程序从文本文件中逐行读取表达式,每行以“;”做标记。调用词法分析程序将这行数据分析出由一个个的单词组成的表达式,再逐个分析单词。另外,由于文法中没写入关于标识符和常数的产生式,所以在对单词符号进行语法分析时,会将标识符和常数自动规约为“i”。数据结构:优先关系表R:二维数组,存储了终结符+、*、(、)、i、#的优先关系。符号W:结构体,有四个成员,包括:ch:char类型,非终结符与终结符的字符标记;po:int类型,只对终结符有效,与在R中的位置有关,有词法分析器提供;对于非终结符,其po无效;val:string类型,综合属性;对终结符i,其值由词法分析器提供;对非终结符,其值由规约时对应的产生式的规则计算得到;对界符或运算符,val无效;type:int类型,标记属性值类型,0为标识符,不可计算;1为可计算的数值;由词法分析器提供;注意:程序内部数值的计算和标记一律使用十进制,文本中的表达式必须为十进制整数,即如果在文本中使用八进制或十六进制,词法分析器分析后不会添加至缓冲区,在表达式语法正确且其中不含标志符时,计算得到的结果一律使用十进制。例:对于文本中十进制数字10,其对应的初始结构体成员的值ch=’i’,po=5,val=”10”,type=1。符号栈S:符号结构体的一维数组。算法:说明:G[E]E-T|E+T;T-F|T*F;F-i|(E);算符优先文法并未对非终结符定义优先关系,无法对单非产生式进行规约,所以实际上在规约时,上面的E-T,T-F基本没有使用,而且规约时并不严格按照产生式的右部规约,只要待规约项符合句型#N1a1N2a2…NnanNn+1#(每个ai都是终结符,Ni是可有可无的非终结符),并且相对产生式,在相同位置有相同的非终结符即可规约,这样算符优先文法规约很快,但有些语法错误将无法识别,在本实验中,只要在要规约的地方准确的判断可规约的项,即符合句型,在不严格要求非终结符相同而终结符位置符号相同时,存在可匹配文法的产生式,即可规约,例如:F*F可以匹配T*F继而规约为T。定义用W[ch]表示字符名为ch的符号;实际程序中关于终结符优先关系的比较是利用R获取优先关系标志的,算法中为了可读性,直接将结构体进行比较了。从文本文件读入一行数据,反复调用scanP()得到符号集合,用符号结构体数组E存储;k=1;i=0;S[k]=W[#];Do{A=E[i++];if(S[k]是终结符)j=k;elsej=k–1;while(S[j]A){Do{Q=S[j];If(S[j-1]是终结符)j=j–1;elsej=j–2;}while(S[j]Q);N=Statute(S,j+1,k);k=j+1;S[k]=N;}If(S[j]A||S[j]==A){k++;S[k]=A;}elseerror(S[j].po,A.po);}while(A==W[#]);程序功能说明:程序从文本文件读入表达式,判断语法是否正确,正确则输出结果,其中有标识符的话,结果还是含有标识符的原表达式,语法错误的话,则输出错误信息。源程序:程序中文本文件在桌面文件名为expression.txt#includeiostream#includestring#includestdlib.husingnamespacestd;#defineNULL0#defineMAXSIZE30//单行表达式的符号总数最大值typedefstructgrammar_symbol//文法符号{charch;intpo;stringval;inttype;}W;charpre[6][6]={//优先关系表{'','','','','',''},{'','','','','',''},{'','','','=','','1'},{'','','2','','2',''},{'','','2','','2',''},{'','','','3','','='}};charGetChar(FILE*fp){//读取文件中的一个字符charch;ch=fgetc(fp);returnch;}charGetBC(FILE*fp){//读取文件的字符直至ch不是空白charch;do{ch=GetChar(fp);}while(ch==''||ch=='\t'||ch=='\n');returnch;}voidConcat(charch,charstrToken[]){//将ch中的字符连接到strToken之后charstr[2];intlen=strlen(strToken);strToken[len]=ch;strToken[len+1]='\0';}intIsLetter(charch){//布尔函数,判断ch中的字符是否为字母,是返回1,否则返回0intflag=0;if(ch='a'&&ch='z')flag=1;returnflag;}intIsDigit(charch){//布尔函数,判断ch中的字符是否为数字,是返回1,否则返回0intflag=0;if(ch='0'&&ch='9')flag=1;returnflag;}intReserve(charstrToken[]){//整型函数,对strToken中的字符串查找保留字表,若它是一个保留字则返回它的编码,否则返回0intcode=0,i;charkeyWord[6][6]={if,then,else,while,do};for(i=0;i5;i++){if(strcmp(strToken,keyWord[i])==0){code=i+1;break;}}returncode;}intSearchOP(charch){//整型函数,对strToken中的字符串查找运算符和界符,若它是一个运算符或界符,则返回它的编码,否则返回0intcode=0,i;charOP[10]={'+','*','(',')','-','/','','','=',';'};for(i=0;i10;i++){if(ch==OP[i]){code=i+1;break;}}returncode;}charRetract(FILE*fp,charch){//子函数,将搜索指示器回调一个字符位置,将ch置为空白字符ch='';fseek(fp,-1L,1);returnch;}voidProError(){//错误处理函数printf(输入错误!\n);return;}intscan(FILE*fp,W*E,intnum){Ww;charch;charstrToken[10];strToken[0]='\0';//置strToken为空串ch=GetBC(fp);//先读取一个非空白的字符if(feof(fp))return0;if(ch==';'){printf(;);return0;//判断表达式尾,是则返回调用程序}if(IsLetter(ch)){//判断标识符while(IsLetter(ch)||IsDigit(ch)){Concat(ch,strToken);ch=GetChar(fp);}ch=Retract(fp,ch);if(Reserve(strToken)){//判断关键字printf(%s,-\n,strToken);}else//判断标识符{printf(%s,strToken);w.ch='i';w.po=4;w.val=strToken;w.type=0;E[num]=w;}}elseif(ch='1'&&ch='9'){//判断十进制整数while(IsDigit(ch)){Concat(ch,strToken);ch=GetChar(fp);}ch=Retract(fp,ch);printf(%s,strToken);w.ch='i';w.po=4;w.val=strToken;w.type=1;E[num]=w;}elseif(ch=='0'){ch=GetChar(fp);if(ch='1'&&ch='7'){//判断八进制整数while(ch='0'&&ch='7'){Concat(ch,strToken);ch=GetChar(fp);}ch=Retract(fp,ch);printf(2,%s\n,strToken);}elseif(ch=='x'){//判断十六进制整数ch=GetChar(fp);while(IsDigit(ch)||ch='a'&&ch='f'){Concat(ch,strToken);ch=GetChar(fp);}ch=Retract(fp,ch);printf(3,%s\n,strToken);}else{//判断十进制的0ch=Retract(fp,ch);printf(0);w.ch='i';w.po=4;w.val=0;w.type=0;E[num]=w;}}elseif(Se
本文标题:编译原理实验报告5-语法分析程序的设计
链接地址:https://www.777doc.com/doc-2068912 .html