编译原理-实验3-算符优先分析

编译原理实验3算符优先分析一、实验目的通过设计编制调试构造FIRSTVT集、LASTVT集和构造算符优先表、对给定符号串进行分析的程序，了解构造算符优先分析表的步骤，对文法的要求，生成算符优先关系表的算法，对给定的符号串进行分析的方法。二、实验内容1.给定一文法G，输出G的每个非终结符的FIRSTVT集和LASTVT集。2.构造算符优先表。3.对给定的符号串进行分析，包含符号栈，符号栈栈顶符号和输入串当前符号的优先级，最左素短语和使用的产生式和采取的动作。三、程序思路在文法框内输入待判断文法产生式，格式E-a|S,注意左部和右部之间是“-”，每个产生式一行，ENTER键换行。文法结束再输入一行G-#E#1.先做文法判断，即可判断文法情况。2.若是算符优先文法，则在优先表栏显示优先表。3.写入要分析的句子，按回车即可。4.在分析过程栏，可以看到整个归约过程情况四、实验结果FunctorFirst.h#includeafx.h#includeiostream#includefstream#includestringusingnamespacestd;#definerightlength20#defineproduct_num20//产生式最多个数#definenum_noterminal26//非终结符最多个数#definenum_terminal26//终结符最多个数structProduction{charLeft;charRight[rightlength];intnum;};structVT{boolvt[num_noterminal][num_terminal];};structStack{charP;chara;};classCMyDlg{public:CMyDlg();voidInputRule();CStringshowLastVT();CStringshowFirstVT();CStringshownoTerminal(charG[]);CStringshowTerminal(charg[]);CStringshowLeftS(charS[],intj,intk);voidInitAll();CStringshowSentence(CStringsen,intstart);CStringshowStack(charS[],intn);voidInitarry(chararry[],intn);CStringProdtoCStr(Productionprod);intselectProd(inti,intj,charS[]);voidpreFunctor(CStringsen);voidinsertFirstVT(StackS[],int&sp,charP,chara);voidinsertLastVT(StackS[],int&sp,charP,chara);voidShowPreTable();voidcreatePreTable();charpretable[num_terminal][num_terminal];boollike_Q(Productionprod,charQ);voidcreateLastVT();boollikeQ_(Productionprod,charQ);boollikeQa_(Productionprod);boollike_aQ(Productionprod);boollike_a(Productionprod);boollikea_(Productionprod);boolDignose(charc);intfindg(charc);intfindG(charc);voidcreateFirstVT();voidcreateTerminal();voidcreatenoTerminal();voidbuildProduction(CStrings);booltest(CStrings);voidparse();//语法分析CStringgram;//存放文法；Productionproduction[product_num];VTFirstVT;VTLastVT;intlocProduct;//已有产生式个数charG[num_noterminal];charg[num_terminal];inti_G;inti_g;CStringm_sen;};FunctorFirst.cpp#includeFunctorFirst.hCMyDlg::CMyDlg(){}boolCMyDlg::test(CStrings)//测试是否是算符优先文法{boolt=1;for(inti=0;is.GetLength()-1;i++)if(s[i]64&&s[i]91&&s[i+1]64&&s[i+1]91){t=0;break;}returnt;}voidCMyDlg::InputRule(){stringinfile;stringline;cout请输入语法文件的路径：;cininfile;coutendl;ifstreaminput(infile.c_str());if(!input){coutendl###打不开文件，请确认输入的路径有效###endl;cout!!!请再次运行本程序!!!endlendl;exit(0);}while(getline(input,line)){if(test(line.c_str())==0){coutendl这不是算符优先文法！endl;exit(0);}buildProduction(line.c_str());}coutendl这是算符优先文法！endl;input.close();}voidCMyDlg::buildProduction(CStrings){inti=0;intj=0;intk=0;for(k=0;ks.GetLength();k++)//得到左部{if(s[k]!=''){production[locProduct].Left=s[k];break;}}for(i=k+1;is.GetLength();i++){if(s[i-1]=='-'&&s[i]=='')break;}inttemp=i;for(i=temp+1;is.GetLength();i++){if(s[i]!='|'){if(s[i]!=''){production[locProduct].Right[j]=s[i];j++;production[locProduct].num=j;}}else{locProduct++;production[locProduct].Left=production[locProduct-1].Left;j=0;}}locProduct++;}voidCMyDlg::createnoTerminal()//建立非终结符索引{i_G=0;//最后一个位置的下一个下标intj=0;for(inti=0;ilocProduct;i++){for(j=0;ji_G;){if(production[i].Left!=G[j])j++;elsebreak;}if(ji_G-1){G[i_G]=production[i].Left;i_G++;}}}voidCMyDlg::createTerminal()//建立终结符索引{i_g=0;//最后一个位置的下一个下标intj=0;for(inti=0;ilocProduct;i++){for(intk=0;kproduction[i].num;k++){chartemp=production[i].Right[k];if(Dignose(temp)){for(j=0;ji_g;){if(temp!=g[j])j++;elsebreak;}if(ji_g-1){g[i_g]=temp;i_g++;}}}}}voidCMyDlg::createFirstVT()//production已完成，创建FirstVT{inti,j;StackS[100];intsp=0;for(i=0;ii_G;i++)//初始化FirstVTfor(j=0;ji_g;j++)FirstVT.vt[i][j]=false;for(i=0;ilocProduct;i++){if(likea_(production[i]))insertFirstVT(S,sp,production[i].Left,production[i].Right[0]);if(likeQa_(production[i]))insertFirstVT(S,sp,production[i].Left,production[i].Right[1]);}while(sp0){sp--;charQ=S[sp].P;chara=S[sp].a;for(i=0;ilocProduct;i++){if(likeQ_(production[i],Q))insertFirstVT(S,sp,production[i].Left,a);}}}voidCMyDlg::createLastVT()//创建Last集{inti,j;StackS[100];intsp=0;for(i=0;ii_G;i++)//初始化FirstVTfor(j=0;ji_g;j++)LastVT.vt[i][j]=false;for(i=0;ilocProduct;i++){if(like_a(production[i]))insertLastVT(S,sp,production[i].Left,production[i].Right[production[i].num-1]);if(like_aQ(production[i]))insertLastVT(S,sp,production[i].Left,production[i].Right[production[i].num-2]);}while(sp0){sp--;charQ=S[sp].P;chara=S[sp].a;for(i=0;ilocProduct;i++){if(like_Q(production[i],Q))insertLastVT(S,sp,production[i].Left,a);}}}intCMyDlg::findG(charc)//定位c在G中的下标{inti=0;for(i=0;ii_G;i++)if(c==G[i])break;returni;}intCMyDlg::findg(charc)//定位c在g中的下标{inti=0;for(i=0;ii_g;i++)if(c==g[i])break;returni;}boolCMyDlg::Dignose(charc)//判断c是终结符还是非终结符，终结符true，非终结符false{if(c64&&c91)returnfalse;elsereturntrue;}boolCMyDlg::likea_(Productionprod){if(Dignose(prod.Right[0]))returntrue;elsereturnfalse;}boolCMyDlg::like_a(Productionprod)//形如P-…a型产生式{if(Dignose(prod.Right[prod.num-1]))returntrue;elsereturnfalse;}boolCMyDlg::like_aQ(Productionprod)//形如P-…aQ型产生式{if(prod.num1)returnfalse;else{if(Dignose(prod.Right[prod.num-2])&&(!Dignose(prod.Right[prod.num-1])))returntrue;elsereturnfalse;}}boolC