文法存储及输出

实验报告学号专业计算机班级姓名课程名称编译原理课程类型必修课实验名称实验一、文法存储及输出实验目的：1.掌握文法在计算机内的存储表示；2.输入任意的上下文无关文法；3.以四元组的形式输出Chomsky文实验内容：叙述本次实验的实现方法、分析、实现了哪些功能、给出一个或多个测试用例及其预期运行结果，要求能够反映本次实验的成果。1.本次实验的实现方法为：采用数组的形式实现文法在机内的存储表示。2.本次试验的问题分析为：一是文法的输入形式；二是文法在计算机内的存储表示形式。3.本次试验应实现以下功能：输入一个文法的识别符号与重写规则，输出文法的四要素VN，VT，P，Z。4.测试实例：实例：输入文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i实验代码如下：#includestdio.hcharGName[10];typedefcharSymbolT;SymbolTStartSymbol;typedefstruct{SymbolTLeftSym;SymbolTRightpart[20];intRightLength;}RuleTC;RuleTCGrammarC[20];SymbolTVT[20];SymbolTVN[20];intNVN=0,NVT=0;typedefstruct{intLeftSymNum;intRightpartNum[20];intRightLength;}RuleT;RuleTGrammar[20];intRuleN;charStartSym;charInput[][20]={E::=E+T|T,T::=T*F|F,F::=(E)|i,\0};intLineNumofG=3;voidGetGrammar(){charLeftS,Sym;intk,j,m;StartSym=GrammarC[1].LeftSym;for(k=1;k=RuleN;k++){LeftS=GrammarC[k].LeftSym;for(j=1;j=NVN;j++)if(LeftS==VN[j]){Grammar[k].LeftSymNum=j+100;break;}for(j=1;j=GrammarC[k].RightLength;j++){Sym=GrammarC[k].Rightpart[j];for(m=1;m=NVN;m++)if(Sym==VN[m]){Grammar[k].RightpartNum[j]=m+100;break;}if(m=NVN)continue;for(m=1;m=NVT;m++)if(Sym==VT[m]){Grammar[k].RightpartNum[j]=m;break;}}Grammar[k].RightLength=GrammarC[k].RightLength;}}voidstoreG(){introw,colum,k,j,m;charsym,U;RuleN=0;row=0;NVN=NVT=0;while(rowLineNumofG){colum=0;sym=Input[row][colum];for(k=1;k=NVN;k++)if(sym==VN[k])break;if(kNVN)VN[++NVN]=sym;GrammarC[++RuleN].LeftSym=sym;colum=colum+4;j=0;while(Input[row][colum]!='\0'){sym=Input[row][colum++];if(sym=='|'){GrammarC[RuleN].RightLength=j;U=GrammarC[RuleN].LeftSym;RuleN=RuleN+1;GrammarC[RuleN].LeftSym=U;j=0;continue;}j=j+1;GrammarC[RuleN].Rightpart[j]=sym;for(k=1;k=NVT;k++)if(sym==VT[k])break;if(kNVT)VT[++NVT]=sym;}GrammarC[RuleN].RightLength=j;row=row+1;}for(m=1;m=NVT;m++){for(k=1;k=NVN;k++)if(VT[m]==VN[k]){VT[m]='';break;}}for(m=1;m=NVT;m++)if(VT[m]==''){for(j=m+1;j=NVT;j++)VT[j-1]=VT[j];NVT=NVT-1;if(VT[m]=='')m=m-1;continue;}GetGrammar();}DispG(){intk,j,m;printf(\n文法的识别符号Z为:%c\n,StartSym);printf(重写规则集P为:\n);for(k=1;k=RuleN;k++){printf(%8c%c::=,'',VN[Grammar[k].LeftSymNum-100]);for(j=1;j=Grammar[k].RightLength;j++){m=Grammar[k].RightpartNum[j];if(m100)printf(%c,VT[m]);elseprintf(%c,VN[m-100]);}printf(\n);}printf(文法的非终结符号集为：VN={);for(k=1;k=NVN-1;k++){printf(%c,VN[k]);printf(,);}printf(%c}\n,VN[NVN]);printf(文法的终结符号集为：VT={);for(k=1;k=NVT-1;k++){printf(%c,VT[k]);printf(,);}printf(%c}\n,VT[NVT]);}voidmain(){charc='Y';intj;printf(\n文法重写规则:\n);for(j=0;jLineNumofG;j++)printf(%s\n,Input[j]);printf(重新输入文法的重写规则?(Y/N):);scanf(%c,&c);if(c=='Y'||c=='y'){printf(输入行数(一个规则一行):);scanf(%d,&LineNumofG);for(j=0;jLineNumofG;j++)scanf(%s,Input[j]);}storeG();DispG();}实验结果：实例一：输入文法G[E]:E::=E+T|TT::=T*F|FF::=(E)|i实例二：输入文法G2[Z]:Z::=aZb|abZ::=CSdS::=CSd|Cd实例三：输入文法G3[E]:E::=T|E+T|E-TT::=F|T*F|T/FF::=(E)|i实例四：输入文法：G4[Z]:Z::=Ab|cA::=Aab|ab::=cbD|dd::=bDd|D实验总结：通过本次实验，掌握了文法在计算机内以数组的方式进行存储，文法的输入形式，以及如何输入一个文法的识别符号与重写规则，如何输出文法的四要素VN，VT，P，Z。在本次实验还是遇到许多困难，通过上网查看以及查看许多书籍，最终完成了本次试验，并有很大的收获。实验评语：实验成绩教师签名