编译原理实验报告5语法分析程序的设计2.docx
- 文档编号:5420056
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:22
- 大小:59.31KB
编译原理实验报告5语法分析程序的设计2.docx
《编译原理实验报告5语法分析程序的设计2.docx》由会员分享,可在线阅读,更多相关《编译原理实验报告5语法分析程序的设计2.docx(22页珍藏版)》请在冰点文库上搜索。
编译原理实验报告5语法分析程序的设计2
实验5语法分析程序的设计
(2)
一、实验目的
通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序
列进行语法检查和结构分析,进一步掌握常用的语法分析中算法优先分析方法。
二、实验内容
设计一个文法的算法优先分析程序,判断特定表达式的正确性。
三、实验要求
1给出文法如下:
G[E]
E->T|E+T;
T->F|T*F;
F->i|(E);
1)直接存放,2)为
可以构造算符优先表如下:
+
*
(
)
+
<<
A
<
*
>
I
><
>
J
<
(
<
<
<
s
<
)
>
>
L
i
>
>
2、计算机中表示上述优先关系,优先关系的机内存放方式有两种优先关系建立优先函数,这里由学生自己选择一种方式;
1、给出算符优先分析算法如下:
k:
=1;S[k]:
='#';
REPEAT
把下一个输入符号读进a中;
IFS[k]€VTTHENj:
=kELSEj:
=k-1;
WHILES[j]>aDO
BEGIN
REPEAT
Q:
=S[j];
IFS[j-1]€VTTHENj:
=j-1ELSEj:
=j-2UNTILS[j] 把S[j+1]…S[归约为某个N; k: =j+1; S[k]: =N; ENDOFWHILE; IFS[j] BEGIN k: =k+1;S[k]: =a END ELSEERROR UNTILa='#' 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、给定文法优先关系和存放方式; + * ( ) # + > < < > > * > >」 > >- ( < < < e1 ) > > e2 > e2 > i > > e2 > e2 _>— # < 一<一 e3 一V一 e4 引入“#”,将句型包含起来并填入出错标记。 使用二维数组将其存放。 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; else j=k-1; while(S[j]>A){ Do{ Q=S[j]; If(S[j-1]是终结符) j=j-1; else j=j-2; }while(S[j] N=Statute(S,j+1,k); k=j+1; S[k]=N; } If(S[j] k++; S[k]=A; } elseerror(S[j].po,A.po); }while(A==W[#]); 程序功能说明: 程序从文本文件读入表达式,判断语法是否正确,正确则输出结果,其中有标识符的话,结果还是含有标识符的原表达式,语法错误的话,则输出错误信息。 源程序: 程序中文本文件在桌面文件名为expression.txt #include #include #include usingnamespacestd; #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){ charch; do{ ch=GetChar(fp); }while(ch==''||ch=='\t'||ch=='\n');returnch; } voidConcat(charch,charstrToken[]){charstr[2]; intlen=strlen(strToken);strToken[len]=ch; strToken[len+1]='\0'; } intIsLetter(charch){ 为字母,是返回1,否则返回0 intflag=0; if(ch>='a'&&ch<='z') flag=1; returnflag; } intIsDigit(charch){是返回1,否则返回0 intflag=0; if(ch>='0'&&ch<='9') flag=1; returnflag; } 〃读取文件的字符直至ch不是空白 //将ch中的字符连接到strToken之后 //布尔函数,判断ch中的字符是否 〃布尔函数,判断ch中的字符是否为数字, intReserve(charstrToken[|){//整型函数,对strToken中的字符串查找保留字表,若它 是一个保留字则返回它的编码,否则返回0 intcode=0,i; charkeyWord[6][6]={"if","then","else","while","do"};for(i=0;i<5;i++){ if(strcmp(strToken,keyWord[i])==0){ code=i+1; break; }returncode; intSearchOP(charch){〃整型函数,对strToken中的字符串查找运算符和界符,若它 是一个运算符或界符,则返回它的编码,否则返回0 intcode=0,i; charOP[10]={'+','*','(',')','-','/','<','>','=',';'}; for(i=0;i<10;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'; 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); //子函数,将搜索指示器回调一个字符位置, //错误处理函数 //置strToken为空串 //先读取一个非空白的字符 是则返回调用程序 //判断标识符 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); boolcheckVt(charch){ boolflag=false; inti; charVt[6]={'+','*','(',')','i','#'}; for(i=0;i<6;i++){ if(ch==Vt[i]){flag=true; } } returnflag; } WStatute(W*S,ints,inte){//规约子函数,将S中j+1到k的符号规约为N WN; if(S[s].ch=='i'&&s==e){ N.ch='F'; N.val=S[s].val; N.type=S[s].type; } elseif(S[s].ch=='('&&! (checkVt(S[s+1].ch))&&S[e].ch==')'){ if(S[s+1].type==1){ N.ch='F'; N.val=S[s+1].val; N.type=S[s+1].type; } else{ N.ch='F'; N.val='('+S[s+1].val+')'; N.type=S[s+1].type; } } elseif(! (checkVt(S[s].ch))&&S[s+1].ch=='+'&&! (checkVt(S[e].ch))){ N.ch='E'; if(S[s].type==1&&S[e].type==1){N.type=1; intv=atoi(S[s].val.data())+atoi(S[e].val.data()); charl[30]; sprintf_s(l,30,"%d",v); N.val=l; } else{ N.type=0; N.val=S[s].val+S[s+1].ch+S[e].val; } } elseif((s! =e)&&! (checkVt(S[s].ch))&&S[s+1].ch=='*'&&! (checkVt(S[e].ch))){N.ch='T'; if(S[s].type==1&&S[e].type==1){N.type=1; intv=atoi(S[s].val.data())*atoi(S[e].val.data()); charl[30]; sprintf_s(l,30,"%d",v); N.val=l; } else{ N.type=0; N.val=S[s].val+S[s+1].ch+S[e].val; } } elseif(S[s].ch=='T'&&s==e){ N.ch='E'; N.val=S[s].val; N.type=S[s].type; }else{ N.ch='#'; } N.po=4;returnN; } voiderror(charerrnum){//错误处理子函数 if(errnum=='1'){ printf("错误,非法左括号\n\n"); } elseif(errnum=='2'){ printf("错误,缺少运算符\n\n"); } elseif(errnum=='3'){ printf("错误,非法右括号\n\n"); } elseif(errnum=='4'){ printf("错误,缺少表达式\n\n"); } } intsyntax(W*E,intnum){//算法对应的主要实现程序 WS[MAXSIZE]; intk=1,i=0,j; Wborder,A,Q;border.ch='#';border.po=5;E[num]=border;S[k]=border;do{ A=E[i++]; if(checkVt(S[k].ch))//判断S[k]是终结符 j=k; else j=k-1; while(pre[S[j].po][A.po]=='>'){do{ Q=S[j]; if(checkVt(S[j-1].ch)) j=j-1; elsej=j-2; }while(pre[S[j].po][Q.po]! ='<'); WN=Statute(S,j+1,k);if(N.ch=='#'){error('4');return0; } k=j+1;S[k]=N; } if(pre[S[j].po][A.po]=='<'||pre[S[j].po][A.po]=='='){ k++; S[k]=A; }else{error(pre[S[j].po][A.po]);return0; } }while(A.ch! ='#');if(A.ch=='#'){ printf("正确,结果为: %s\n\n",S[k-1].val.data());return0; } } intmain(){ FILE*fp; errno_terr; if((err=fopen_s(&fp,"C: \\Users\\Administrator\\Desktop\\expression.txt","r"))! =NULL){//以只读方式打开文件,失败则退出程序 printf("filecannotopen! ");exit(0); } intn=0; printf("语法分析结果如下: \n\n");while(! feof(fp)){//若不是文件尾则执行循环 intnum=0; WE[MAXSIZE];//存储一行表达式 GetBC(fp); if(! feof(fp)){ n++;fseek(fp,-1L,1); printf("(%d)",n); } else{ break; } while (1){//只读一行,行末标志为 intflag=scan(fp,E,num); if(flag==0)break; num++; } printf("\n输出: ");syntax(E,num); } fclose(fp);//关闭文件 fp=NULL;//避免指向非法内存 } 3、程序运行流程; 4、程序的测试结果和问题;实验报告源数据: C: \Windows\system32\cmdnexe 语法分析结果如下: <1>10; 输岀;正确,结果为;10 <251+2; 输岀|正确,结果为;3 <3><1+2^*3+<5+6*7>; 输出*正确,结果为: 56 <4> 输岀: 错误,非法左括号 <5>l*2*-3+C«4«5>; 输岀: 错误,缺少表达式 <6>* 输出: <7; **5>+l: 输岀: 错误,缺少表达式 请按任意键继续…■ 其它数据: expression,txt-记事本 文件(F)窗E〕榕式Q)奩8+; (0; (5*5))+3; 3*x+2y+5*zJ 6+5*((6+5)*2); 1+i+h; valuel+value2+value3; C: fIndows\systeiii32\cmd.exe 语法分析结果如下’ <1>8+; 输岀: 错误,缺少表达式 (2X0; 输出: 错误,缺少表达式 <3><5«5>>+3; 输岀;错误,非法右括号 <"1>3*x+2y+5**z; 输岀|错误,缺少运算符 (5>6+5*<<6+5>*2); 输出1正碣,结異為. <6>l+x+L: 输岀: 正确,结杲为: l*x+h (7>ualuel+ualue2-»valiJie3; 输出;正确’结果为;valuel*ualue2*ua
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验 报告 语法分析 程序 设计