编译原理提高型实验报告.doc

黄冈师范学院提高型实验报告实验课题OPG分析程序的设计_（实验类型：综合型设计型应用型） 实验课程 编译原理_ 实验时间 2014年12月16日 学生姓名 专业班级 学号 OPG分析表和分析程序的设计实验目的和要求：通过设计、编写和调试构造优先关系表的程序，了解构造算符优先关系表的步骤以及对文法的要求，并能够从文法G出发自动生成算符优先关系表。实验原理分析（包括算法）：设计一个自动构造优先关系表的程序，该程序的输入是算符文法G，输出的是相应的优先关系表，并指出是否为算符优先文法。（1）例如以下文法： E-T+E|T T-F*T|F F-FP|P P-(E)|i注：I为整型常数后者为标识符表示的整型变量，使用中用*表示。（2）构造优先分析表的算法，构造优先分析表需以下几个步骤： 构造文法G中非终结符号的FIRSTVT集合FIRSTVT集合用一个布尔数组FP,a表示，F是一个m*n的二维数组（m=文法G中非终结符号个数，n=文法G中终结符号个数）。其中PVN，aVT，FP,a=TRUE的条件是当且仅当aFIRSTVTP。对于文法G的所有非终结符号，构造布尔数组FP,a的算法（该算法使用一个数据结构STACK栈，用于存放相应于FP,a=TRUE的符号对（P,a）。 构造文法G中非终结符号的LASTVT集合类似于构造FIRSTVT集合，LASTVT集合用一个布尔数组LP,a表示，F是一个m*n的二维数组（m=文法G中非终结符号个数，n=文法G中终结符号个数）。其中PVN，aVT，LP,a=TRUE的条件是当且仅当 aLASTVTP。对于文法G的所有非终结符号，构造布尔数组LP,a的算法（该算法使用一个数据结构STACK栈，用于存放相应于LP,a=TRUE的符号对（P,a）。 构造文法G的优先关系表使用文法G任何非终结符号的FIRSTVT集合和LASTVT集合，可以构造文法G的优先关系表。优先关系表用一个数组Ra,b表示，R是一个n*n的二维数组（n=文法G中终结符号个数）。其中a,bVT,Ra,b =、或空（可能为多值），表示终结符号对（a,b）之间具有“=”“”优先关系或无优先关系。 判断文法G是否为算符优先文法构造出文法G的算符优先表Ra,b后，判别文法G是否为算符优先文法的算法。实验方案或步骤（流程图、主要数据结构、程序、小结）OPG分析程序的设计实验目的和要求： 通过设计，编写和调试算符优先分析程序，了解算符优先分析器的组成结构以及对文法的要求，掌握实现通用算符优先分析算法的方法。 实验原理分析：程序流程图从键盘读取表达式 NY成功 结束读入字符串 赋给数组str 将#压入数组array 从数组str 中读取一个字符aN a的优先关系大于数组array 中的最后一个终结符Y 将数组array 中优先关系一样的字符规约为MN 将a移近数组array Y sixeof array =0 结束算符优先分析属于自下而上的分析方法，该语法分析程序的输入是终结符号串（即单词符号串，以一个“#”结尾）。如果输入串是句子，则输出“YES”，否则输出“NO”和错误信息。算符优先分析过程与非终结符号无关，当由文法产生了优先关系之后文法就失去了作用。本题目给出文法的目的是为了便于对语法分析结果进行验证。(1) 文法 设算符优先文法G为： EE+T|T TT*F|F FPF|P P（E）|i 说明：i为整形常数或者为表示符表示整形变量；使用中用*表示。(2) 优先关系表设优先关系表如下所示。 + * i ( ) # + * i ( # =实验方案或步骤输出移近规约过程。源代码如下：#include#include#include#define SIZE 128char priority66;/算符优先关系表数组char inputSIZE;/存放输入的要进行分析的句子char remainSIZE;/存放剩余串 char AnalyseStackSIZE; /分析栈void analyse();int testchar(char x);/判断字符X在算符优先关系表中的位置void remainString();/移进时处理剩余字符串，即去掉剩余字符串第一个字符int k;void init()/构造算符优先关系表，并将其存入数组中priority00=;priority01=;priority02=;priority03=;priority05=;priority10=;priority11=;priority12=;priority13=;priority15=;priority20=;priority21=;priority22=$;/无优先关系的用$表示priority23=$;priority24=;priority25=;priority30=;priority31=;priority32=;priority33=;priority41=;priority42=$;priority43=$;priority44=;priority45=;priority50=;priority51=;priority52=;priority53=;priority54=$;priority55=;/*对所输入的句子进行算符优先分析过程的函数*/void analyse()int i,j,f,z,z1,n,n1,z2,n2;int count=0;/操作的步骤数char a;/用于存放正在分析的字符char p,Q,p1,p2;f=strlen(input);/测出数组的长度for(i=0;i) for( ; ; ) Q=AnalyseStackj; if(AnalyseStackj-1=+|AnalyseStackj-1=*|AnalyseStackj-1=i|AnalyseStackj-1=(|AnalyseStackj-1=)|AnalyseStackj-1=#) j=j-1; else j=j-2; z1=testchar(AnalyseStackj); n1=testchar(Q); p1=priorityz1n1; if(p1=)/把AnalyseStackj+1AnalyseStackk归约为N count+; printf(%d) %st%10ct%5c%17st 归约n,count,AnalyseStack,p,a,remain); k=j+1; i-; AnalyseStackk=N; int r,r1; r=strlen(AnalyseStack); for(r1=k+1;r1r;r1+) AnalyseStackr1=0; break; else continue;elseif(p=)/表示移进count+;printf(%d) %st%10ct%5c%17st 移进n,count,AnalyseStack,p,a,remain);k=k+1;AnalyseStackk=a;remainString();elseif(p=)z2=testchar(AnalyseStackj);n2=testchar(#);p2=priorityz2n2;if(p2=)count+;printf(%d) %st%10ct%5c%17st 接受n,count,AnalyseStack,p,a,remain);printf(该句子是该文法的合法句子。n);break;elsecount+;printf(%d) %st%10ct%5c%17st 移进n,count,AnalyseStack,p,a,remain);k=k+1;AnalyseStackk=a;remainString();elseprintf(错误！该句子不是该文法的合法句子！n);break; int testchar(char x)int m;if(x=+)m=0;if(x=*)m=1;if(x=i)m=2;if(x=()m=3;if(x=)m=4;if(x=#)m=5;return m;/*余下的字符串*/void remainString()int i,j;i=strlen(remain);for(j=0;j#E#n);printf(1)E-E+Tn);printf(2)E-T*Fn);printf(3)T-Tn);printf(4)T-Fn);printf(5)F-PFn);printf(6)F-Pn);printf(7)P-(E)n);printf(8)P-in);printf(n-nn);printf(*算符优先关系表*n); printf(t+t*titt(t)t#n); printf( +ttttttn); printf( *ttttttn);printf( ttttttn); printf( itttttttn); printf( (ttttttttttn); printf( #ttttttt=n);printf(=n);printf(请输入要进行分析的句子（以#号结束输入）:n); gets(input);/将输入的字符串存到数组中printf(步骤 栈 优先关系 当前符号 剩余输入串 移进或归约n);k=0;AnalyseStackk=#;AnalyseStackk+1=0;int length,i;/初始化剩余字符串数组为输入串length=strlen(input);/for(i=0;ilen