③構(gòu)造LL（1）分析表：+-*/()i#EE→TE'E→TE'TT→FT'T→FT'FF→(E)F→iE'E'→+TE'E'→-TE'E'→εE'→εT'T'→εT'→εT'→*FT'T'→/FT'T'→εT'→ε該文法是LL（1）文法。3.基于上述分析表，仿照教材，寫出符號(hào)串#((i+i)*i-i)/i#的詳細(xì)的分析過程。G=（{E,T,F},{+,-,*,/,(,),i},E,P），其中P由下列產(chǎn)生式組成：E→E+TE→E-TE→TT→T*FT→T/FT→FF→(E)F→i消除左遞歸后的文法：G=（{E,T,F,E',T'},{+,-,*,/,(,),i},E,P），其中P由下列產(chǎn)生式組成：E'→+TE'E'→-TE'E→TE'T'→*FT'T'→/FT'T→FT'F→(E)F→iE'→εT'→ε該文法是一個(gè)LL(1)文法。輸入串#((i+i)*i-i)/i#的預(yù)測(cè)分析過程如下：==============================================================步驟分析棧余留輸入串所用產(chǎn)生式==============================================================1#E((i+i)*i-i)/i#E→TE'2#E'T((i+i)*i-i)/i#T→FT'3#E'T'F((i+i)*i-i)/i#F→(E)4#E'T')E(((i+i)*i-i)/i#(匹配5#E'T')E(i+i)*i-i)/i#E→TE'6#E'T')E'T(i+i)*i-i)/i#T→FT'7#E'T')E'T'F(i+i)*i-i)/i#F→(E)8#E'T')E'T')E((i+i)*i-i)/i#(匹配9#E'T')E'T')Ei+i)*i-i)/i#E→TE'10#E'T')E'T')E'Ti+i)*i-i)/i#T→FT'11#E'T')E'T')E'T'Fi+i)*i-i)/i#F→i12#E'T')E'T')E'T'ii+i)*i-i)/i#i匹配13#E'T')E'T')E'T'+i)*i-i)/i#T'→ε14#E'T')E'T')E'+i)*i-i)/i#E'→+TE'15#E'T')E'T')E'T++i)*i-i)/i#+匹配16#E'T')E'T')E'Ti)*i-i)/i#T→FT'17#E'T')E'T')E'T'Fi)*i-i)/i#F→i18#E'T')E'T')E'T'ii)*i-i)/i#i匹配19#E'T')E'T')E'T')*i-i)/i#T'→ε20#E'T')E'T')E')*i-i)/i#E'→ε21#E'T')E'T'))*i-i)/i#)匹配22#E'T')E'T'*i-i)/i#T'→*FT'23#E'T')E'T'F**i-i)/i#*匹配24#E'T')E'T'Fi-i)/i#F→i25#E'T')E'T'ii-i)/i#i匹配26#E'T')E'T'-i)/i#T'→ε27#E'T')E'-i)/i#E'→-TE'28#E'T')E'T--i)/i#-匹配29#E'T')E'Ti)/i#T→FT'30#E'T')E'T'Fi)/i#F→i31#E'T')E'T'ii)/i#i匹配32#E'T')E'T')/i#T'→ε33#E'T')E')/i#E'→ε34#E'T'))/i#)匹配35#E'T'/i#T'→/FT'36#E'T'F//i#/匹配37#E'T'Fi#F→i38#E'T'ii#i匹配39#E'T'#T'→ε40#E'#E'→ε41##接受!恭喜您，分析成功，這是一個(gè)合法的句子!Pressanykeytocontinue（二）編程實(shí)現(xiàn)下述要求消除左遞歸（可僅考慮直接左遞歸）；//消除直接“左遞歸”：//即消除形如P→Pα|β的產(chǎn)生式voidCLL1Grammar::DelDirectLeftRecursion(){ vector<CreateFormula>::iteratorIter2; //迭代器2 for(inti=0;i<NoEndSign.size();i++) { if(!HaveDirectLeftRecursion(GR_Array,NoEndSign[i])) //若不存在左遞歸，則結(jié)束本次循環(huán) continue; stringc=CreateNewVn(NoEndSign[i]); for(Iter2=GR_Array.begin();Iter2!=GR_Array.end();Iter2++) { stringtemp1=(*Iter2).LeftPart; //左部 if(!pare(NoEndSign[i])) //若左部==NoEndSign[i]， { vector<string>temp2=GetSingleSign((*Iter2).RightPart); //分解右部 //（1）修改產(chǎn)生式：P→β為P→βP'if(pare(temp2[0])) //若左部不等于右部首字符，即為形如P→β， { if(temp2[temp2.size()-1].compare(c)) //如果尚未, (*Iter2).RightPart+=c; //則添加P'，即P→β變?yōu)镻→βP' } //（2）改造：P→Pα為P'→αP'： else { //①左部變?yōu)樾碌姆墙K結(jié)符號(hào)c，即P' (*Iter2).LeftPart=c; //②右部刪除首字符，即“去除”原遞歸字符 (*Iter2).RightPart=(*Iter2).RightPart.substr(temp1.length(), (*Iter2).RightPart.length()-temp1.length()); //③在右部尾端添加c，即P' (*Iter2).RightPart+=c; }}} //（3）增加產(chǎn)生式：P'→ε CreateFormulatemp; temp.LeftPart=c; temp.RightPart="ε"; GR_Array.push_back(temp); //（4）將P'加入非終結(jié)符集： if(!FindSign(c,NoEndSign)) NoEndSign.push_back(c); }}求解文法符號(hào)和各個(gè)候選式的FIRST； //（2）確定所有非終結(jié)符的FIRST： //判斷各個(gè)非終結(jié)符的FIRST是否增大的標(biāo)識(shí) boolFlag; do { Flag=false; for(intj=0;j<NoEndSign.size();j++) { for(intk=0;k<GR_Array.size();k++) { if(NoEndSign[j].compare(GR_Array[k].LeftPart)) continue; //對(duì)于左部為NoEndSign[j]的產(chǎn)生式： intpos2=LocateInFFSet(NoEndSign[j],FIRSTofSingleSign); //（2.1）若形如X→ε，則 if(!(GR_Array[k].RightPpare("ε"))) //若右部為ε，則 { if(!FindSign("ε",FIRSTofSingleSign[pos2])) //若ε尚未加入，則 { FIRSTofSingleSign[pos2].push_back("ε"); //添加進(jìn)去 Flag=true; }} else { //分解右部 vector<string>temp1=GetSingleSign(GR_Array[k].RightPart); //（2.1）若形如X→a...，則 if(FindSign(temp1[0],EndSign)) //若右部首符號(hào)為終結(jié)符，則 { if(!FindSign(temp1[0],FIRSTofSingleSign[pos2])) //若ε尚未加入，則 { FIRSTofSingleSign[pos2].push_back(temp1[0]); //添加進(jìn)去 Flag=true; } } //（2.1）若形如X→Y1Y2...Yn，則 else { for(intp=0;p<temp1.size();p++) { intpos3=LocateInFFSet(temp1[p],FIRSTofSingleSign); if(pos3!=-1) { if(SignWhetherToEmpty(temp1[p])) //若Yp能導(dǎo)出ε { //將FIRST(Yp)-ε加入FIRST(X) Flag=Flag||Merge1(FFSetSubE(FIRSTofSingleSign[pos3]), FIRSTofSingleSign[pos2]);} else { //將FIRST(Yp)加入FIRST(X) Flag=Flag||Merge1(FIRSTofSingleSign[pos3], FIRSTofSingleSign[pos2]); break; }} } if(p==temp1.size()) { //將ε加入FIRST(X) if(!FindSign("ε",FIRSTofSingleSign[pos2])) //若ε尚未加入，則 { FIRSTofSingleSign[pos2].push_back("ε"); //添加進(jìn)去 Flag=true; } }}}}}}while(Flag);//直到FIRST集不再變化為止DisplayAllSingleSignFIRST();}//計(jì)算所有候選式的FIRST：voidCLL1Grammar::FIRSTSetOfAllSignString(){ for(inti=0;i<FIRSTofSignString.size();i++) { vector<string>temp; temp=FIRSTSetOfSTR(FIRSTofSignString[i][0]); for(intj=0;j<temp.size();j++) FIRSTofSignString[i].push_back(temp[j]); } DisplayAllSignStringFIRST();}求解各個(gè)非終結(jié)符的FOLLOW集；//顯示所有非終結(jié)符的FOLLOWvoidCLL1Grammar::DisplayAllVNFOLLOW(){ vector<string>temp; for(inti=0;i<FOLLOWofVN.size();i++) { cout<<"FOLLOW("<<FOLLOWofVN[i][0]<<")={"; temp=FOLLOWofVN[i]; if(temp.size()==2) cout<<temp[1]<<"}"<<endl; elseif(temp.size()>2) { cout<<temp[1]; for(intj=2;j<temp.size();j++) cout<<","<<temp[j]; cout<<"}"<<endl;} else { cout<<"}"<<endl;}}}構(gòu)造LL(1)分析表；//構(gòu)造預(yù)測(cè)分析表M：voidCLL1Grammar::CreateMM(){ //（1）構(gòu)造臨時(shí)終結(jié)符集： tempEndSign.clear(); for(intt=0;t<EndSign.size();t++) tempEndSign.push_back(EndSign[t]); //建立臨時(shí)用的終結(jié)符集 tempEndSign.push_back("#"); //補(bǔ)加一個(gè)符號(hào)“#” //（2）初始化分析表： inti,j; MMTable.clear();vector<string>tempTable;for(i=0;i<NoEndSign.size();i++){for(j=0;j<tempEndSign.size();j++)tempTable.push_back("");MMTable.push_back(tempTable);tempTable.swap(vector<string>());} //（3）構(gòu)造分析表： for(intk=0;k<GR_Array.size();k++)//考查所有產(chǎn)生式A→α， { introw,col; //構(gòu)成產(chǎn)生式A→α： stringtemp1=GR_Array[k].LeftPart+"→"+GR_Array[k].RightPart; //由左部符號(hào)確定分析表的行坐標(biāo)： row=GetSignInVector(GR_Array[k].LeftPart,NoEndSign); //（3.1）對(duì)FIRST(α)中的任一個(gè)a，置M[A,a]=“A→α”： if(GR_Array[k].RightPpare("ε")) //若右部不等于“ε”，則 { //確認(rèn)右部的FIRST集： intpos1=LocateInFFSet(GR_Array[k].RightPart,FIRSTofSignString); vector<string>temp3=FIRSTofSignString[pos1]; //對(duì)于FIRST(α)中的每一個(gè)符號(hào)： for(intP=1;P<temp3.size();P++) //首符號(hào)為標(biāo)志，故從1開始 { //由FIRST(α)中的終結(jié)符確定分析表的列坐標(biāo)： col=GetSignInVector(temp3[P],tempEndSign); //設(shè)置表元素為：A→α if(MMTable[row][col].empty()) MMTable[row][col]=temp1; else { MMTable[row][col]+="\n"; MMTable[row][col]+=temp1;} } } //（3.2）若ε∈FIRST(α)，則對(duì)任何a∈FOLLOW(A)，置M[A,a]=“A→α”： if(StringWhetherToEmpty(GR_Array[k].RightPart)) //若α能導(dǎo)出ε，則 { intpos2=LocateInFFSet(GR_Array[k].LeftPart,FOLLOWofVN); vector<string>temp5=FOLLOWofVN[pos2]; for(intL=1;L<temp5.size();L++) //首符號(hào)為標(biāo)志，故從1開始 { col=GetSignInVector(temp5[L],tempEndSign);//確定分析表的列坐標(biāo)： if(MMTable[row][col].empty()) MMTable[row][col]=temp1; else { MMTable[row][col]+="\n"; MMTable[row][col]+=temp1;}}}}} 判斷文法G’[E]是否為L(zhǎng)L(1)文法；boolCLL1Grammar::CheckLL1Grammar(){ for(inti=0;i<MMTable.size();i++) { vector<string>temp1=MMTable[i]; for(intj=0;j<temp1.size();j++) { intpos=temp1[j].find_first_of("\n"); if(pos!=-1) //若存在多重定義，則表示存在沖突，直接返回： returnfalse;} } returntrue;}判斷符號(hào)串#((23+12)*9-200)/5#是否為G’[E]文法的合法句子。//判斷串signstr是否是合法的句子：//串signstr的格式為：##boolCLL1Grammar::IsSentenceofLL1(stringsignstr){ if(!(pare("ε"))) //不識(shí)別“ε” returnfalse; if(signstr.empty()) //若待分析串為空，則 returnfalse; vector<string>tempstr=GetSingleSign(signstr);//分解signstr if(tempstr[0].compare("#")) //若左首符號(hào)不為“#”，則 returnfalse; //（1）顯示表頭： cout<<endl<<"輸入串"<<signstr<<"的預(yù)測(cè)分析過程如下："<<endl; cout<<"=============================================================="; cout<<endl<<setw(8)<<"步驟"<<setw(20)<<"分析棧"<<right<<setw(20) <<"余留輸入串"<<left<<setw(4)<<""<<setw(12)<<"所用產(chǎn)生式"<<endl; cout<<"=============================================================="<<endl; //（2）初始化： inti=-1; intNumber=0; ClearStack(); //清空棧 sLL1.push(tempstr[0]); //首先將串的左界符“#”壓棧 sLL1.push(StartSign); //再將文法的開始符號(hào)壓棧 tempstr=GetReststring(0,tempstr); //獲得剩余串，并作為下一次的“源串” stringcurInputstr=tempstr[0]; //讀取下一個(gè)符號(hào) //（3）開始識(shí)別： do { //（3.1）顯示過程信息： cout<<right<<setw(2)<<(++Number)<<setw(6)<<left<<"";//顯示序號(hào) cout<<left<<setw(20)<<GetStack(sLL1); //顯示棧內(nèi)容 cout<<right<<setw(20)<<Gouzaostring(tempstr)<<left<<setw(4)<<""; //顯示剩余串tempstr的內(nèi)容 //（3.2）觀察棧頂元素與當(dāng)前符號(hào)（Token）： stringstackTopstr=sLL1.top(); //觀察棧頂元素， //（3.3）如果棧頂元素是終結(jié)符 if(FindSign(stackTopstr,tempEndSign)) { if(!stackTpare(curInputstr)) //若stackTopstr等于curInputstr { if(stackTpare("#")) //，但不等于'#'，即局部匹配，則 { cout<<curInputstr<<"匹配"<<endl; sLL1.pop(); //彈出棧頂元素 //讀取下一個(gè)符號(hào)： tempstr=GetReststring(0,tempstr); //將上次的剩余串設(shè)置為這一次的待識(shí)別串 curInputstr=tempstr[0]; //讀取下一個(gè)符號(hào)， } else //，且均等于'#'，則分析成功! { cout<<"接受!"<<endl; break;}} else//分析進(jìn)行不下去了，出錯(cuò)! { cout<<"錯(cuò)："<<stackTopstr<<"與"<<curInputstr<<"不匹配!"; returnfalse;}} //（3.4）如果棧頂元素為非終結(jié)符，則查看分析表： else { introw=GetSignInVector(stackTopstr,NoEndSign); //看是哪個(gè)非終結(jié)符A if(row!=-1) { intcol=GetSignInVector(curInputstr,tempEndSign); //看當(dāng)前輸入符是哪個(gè)終結(jié)符a if(col!=-1 //若當(dāng)前輸入符是為終結(jié)符, &&!MMTable[row][col].empty()) //，且M[A,a]不為空，則 { cout<<setw(12)<<MMTable[row][col]<<endl; sLL1.pop(); //棧頂元素出棧 //將產(chǎn)生式的右部“反序”壓棧 //（3.4.1）提取產(chǎn)生式的右部： stringsRight=MMTable[row][col]; intpos=sRight.find("→"); if(pos<sRight.size()) sRight=sRight.substr(pos+2,sRight.length()-pos);//"→"是漢字符號(hào)，所以“+2” else { cout<<"存在的產(chǎn)生式格式錯(cuò)誤，無法提取右部符號(hào)串!"; returnfalse; } //（3.4.2）將規(guī)則的右部“反序”壓入棧 if(sRpare("ε")) //若不為A→ε， { vector<string>tempstr2=GetSingleSign(sRight);//分解右部的sRight intt3=tempstr2.size(); for(intk=t3-1;k>=0;k--) //將規(guī)則的右部“反序”壓入棧 sLL1.push(tempstr2[k]);}} else { cout<<"錯(cuò)：分析表元素為空!"; returnfalse;}}}} while(1); returntrue;}實(shí)驗(yàn)運(yùn)行結(jié)果：輸入串#(23+12)*9-200)/5#的預(yù)測(cè)分析過程如下：===========================================================步驟分析棧余留輸入串所用產(chǎn)生式===========================================================1#E(23+12)*9-200)/5#E→TE'2#E'T(23+12)*9-200)/5#T→FT'3#E'T'F(23+12)*9-200)/5#F→(E)4#E'T')E((23+12)*9-200)/5#(匹配5#E'T')E23+12)*9-200)/5#E→TE'6#E'T')E'T23+12)*9-200)/5#T→FT'7#E'T')E'T'F23+12)*9-200)/5#F→i8#E'T')E'T'i23+12)*9-200)/5#23匹配9#E'T')E'T'+12)*9-200)/5#T'→ε10#E'T')E'+12)*9-200)/5#E'→+TE'11#E'T')E'T++12)*9-200)/5#+匹配12#E'T')E'T12)*9-200)/5#T→FT'13#E'T')E'T'F12)*9-200)/5#F→i14#E'T')E'T'i12)*9-200)/5#12匹配15#E'T')E'T')*9-200)/5#T'→ε16#E'T')E')*9-200)/5#E'→ε17#E'T'))*9-200)/5#)匹配18#E'T'*9-200)/5#T'→*FT'19#E'T'F**9-200)/5#*匹配20#E'T'F9-200)/5#F→i21#E'T'i9-200)/5#9匹配22#E'T'-200)/5#T'→ε23#E'-200)/5#E'→-TE'24#E'T--200)/5#-匹配25#E'T200)/5#T→FT'26#E'T'F200)/5#F→i27#E'T'i200)/5#200匹配28#E'T')/5#T'→ε29#E')/5#E'→ε30#)/5#錯(cuò)：#與)不匹配很遺憾，分析失敗!五、思考題 上述實(shí)驗(yàn)中考察的是表達(dá)式的符號(hào)表示式，例如：#i+i*i# 而事實(shí)上，其中的終結(jié)符i是泛指數(shù)值型操作數(shù)，例如5、10、200、3050等。 顯然，由于這些操作數(shù)的位數(shù)變化不一，故不能簡(jiǎn)單地通過符號(hào)串的指針移動(dòng)來實(shí)現(xiàn)字串分離。因此，需要由詞法分析程序來逐一讀取每一個(gè)單詞（參見實(shí)驗(yàn)1的效果），再賦給語(yǔ)法分析程序進(jìn)行分析。 所以，就需要將詞法分析程序與語(yǔ)法分析程序緊密結(jié)合，重點(diǎn)是考查二者的協(xié)調(diào)性能。修改實(shí)驗(yàn)1中的表達(dá)式的狀態(tài)轉(zhuǎn)換圖，使其可以將左界符（“#”）識(shí)別為一個(gè)單詞；修改實(shí)驗(yàn)1的詞法分析程序源碼，以實(shí)現(xiàn)上述第①條的要求。tempEndSign.clear();for(intt=0;t<EndSign.size();t++) tempEndSign.push_back(EndSign[t]);//建立臨時(shí)使用的終結(jié)符集tempEndSign.push_back("#");//補(bǔ)加一個(gè)符號(hào)“#”重點(diǎn)修改語(yǔ)法分析中符號(hào)串的識(shí)別函數(shù)，將輸入符號(hào)讀取改由詞法分析程序來實(shí)現(xiàn)。 CLL1GrammarLLG1; //（1）初始化文法 LLG1.InitGrammar(); //初始化 LLG1.DisplayGrammar(); //顯示文法 LLG1.Pretreatment(); //預(yù)處理：消除左遞歸等 //（2）初始化有關(guān)數(shù)據(jù)結(jié)構(gòu) LLG1.InitSets(); //（3）計(jì)算FIRST集 LLG1.FIRSTSetOfAllSingleSign(); //計(jì)算所有單個(gè)符號(hào)的FIRST LLG1.FIRSTSetOfAllSignString(); //計(jì)算所有右部符號(hào)串的FIRST //（4）計(jì)算FOLLOW集 LLG1.FOLLOWSetOfAllVN(); //計(jì)算所有非終結(jié)符的FOLLOW //（5）構(gòu)造預(yù)測(cè)分析表： LLG1.CreateMM();// LLG1.DisplayMMTable(); //（6）檢查是否為L(zhǎng)L(1)文法： if(LLG1.CheckLL1Grammar()) { cout<<endl<<"本文法是一個(gè)LL(1)文法!"<<endl<<endl;//（7）輸入串分析 stringinputstr("#((23+12)*9-200)/5#");// stringinputstr("#((23+12)*9-200)/5#"); //正確// stringinputstr("#(23+12)*9-200)/5#"); //出錯(cuò)：棧頂終結(jié)符元素與當(dāng)前單詞不匹配// stringinputstr("#((23+12)9-200)/5#"); //出錯(cuò)：表元素為空 boolFlag=LLG1.IsSentenceofLL1(inputstr); if(Flag) cout<<endl<<"恭喜您，分析成功，這是一個(gè)合法的句子!"<<endl<<endl; else cout<<endl<<"很遺憾，分析失敗!"<<endl<<endl;} else cout<<endl<<"警告：該文法不是LL(1)文法!"<<endl<<endl;實(shí)驗(yàn)運(yùn)行結(jié)果：輸入串#((23+12)*9-200)/5#的預(yù)測(cè)分析過程如下：=======================================================步驟分析棧余留輸入串所用產(chǎn)生式=======================================================1#E((23+12)*9-200)/5#E→TE'2#E'T((23+12)*9-200)/5#T→FT'3#E'T'F((23+12)*9-200)/5#F→(E)4#E'T')E(((23+12)*9-200)/5#(匹配5#E'T')E(23+12)*9-200)/5#E→TE'6#E'T')E'T(23+12)*9-200)/5#T→FT'7#E'T')E'T'F(23+12)*9-200)/5#F→(E)8#E'T')E'T')E((23+12)*9-200)/5#(匹配9#E'T')E'T')E23+12)*9-200)/5#E→TE'10#E'T')E'T')E'T23+12)*9-200)/5#T→FT'11#E'T')E'T')E'T'F23+12)*9-200)/5#F→i12#E'T')E'T')E'T'i23+12)*9-200)/5#23匹配13#E'T')E'T')E'T'+12)*9-200)/5#T'→ε14#E'T')E'T')E'+12)*9-200)/5#E'→+TE'15#E'T