编译原理实验+求first集和follow集+代码

/*˵Ã÷£ºÊäÈë¸ñʽ£ºÃ¿ÐÐÊäÈëÒ»¸ö²úÉúʽ£¬×ó²¿ÓÒ²¿ÖмäµÄ¡úÓÿոñ´úÌæ¡£·ÇÖÕ½á·ûµÈ¼ÛÓÚ´óд×Öĸ^±íʾ¿ÕÊäÈëµ½Îļþ½áÊø£¬»òÓÃ00½áβ¡£SampleInput£º(Ï°Ìâ5¡¤3):SMHSaHLSoH^KdMLK^LeHfMKMbLM00*/#includeiostream#includestring#includemap#includeset#includevectorusingnamespacestd;charl;stringr;multimapchar,stringsentence;//´æ´¢²úÉúʽmultimapstring,charsenRever;//²úÉúʽÄæתsetcharter;//·ÇÖÕ½á·û¼¯ºÏmapchar,booltoEmpty;//·ÇÖÕ½á·ûÄÜ·ñÍƳö¿Õboolflag;setcharfir;//±£´æµ¥¸öÔªËصÄfirst¼¯setcharfollow;//±£´æµ¥¸öÔªËصÄfollow¼¯vectorstringrightSide;//ÓÒ²¿charBegin;boolcapL(charc)//×ÖĸÊÇ·ñ´óд{if(c='Z'&&c='A')returntrue;returnfalse;}/*boollowerL(charc)//Сд×Öĸ{if(c='z'&&c='a')returntrue;returnfalse;}*/boolCapLString(strings)//´óд×Ö·û´®{for(inti=0;is.size();i++){if(!capL(s[i])){returnfalse;}}returntrue;}boolisToEmpty(charch)//ÅжÏÖÕ½á·ûÄÜ·ñÍƳö¿Õ{boolflag;//for(setchar::iteratorsIter=ter.begin();sIter!=ter.end();++sIter){flag=false;multimapchar,string::iteratormIter=sentence.find(ch);intcnt=sentence.count(ch);for(inti=0;icnt;++i,++mIter){if(mIter-second==^){returntrue;//toEmpty[ch]=true;}elseif(CapLString(mIter-second)){strings(mIter-second);boolflag2=true;for(intj=0;js.size();j++){if(!isToEmpty(s[j])||s[j]==ch){flag2=false;break;}}if(flag2){//ÓÒ²¿È«ÎªÖÕ½á·û£¬È«ÄÜÍƳö¿Õreturntrue;}}}//}returnfalse;}voidgetFirst(charch,setchar&First)//Ç󵥸öÔªËصÄFIRST¼¯{//if(flag)//return;multimapchar,string::iteratorimul=sentence.find(ch);if(imul==sentence.end())return;intsum=sentence.count(imul-first);//coutimul-firstendl;for(inti=0;isum;++i,++imul){//coutimul-secondendl;strings(imul-second);for(intj=0;js.size();j++){if(!capL(s[j])){//couts[j]endl;First.insert(s[j]);//flag=true;break;}elseif(capL(s[j])){if(s[j]==ch){//ÓÐ×óµÝ¹é,Ìø³öÑ­»·break;;}getFirst(s[j],First);if(toEmpty[s[j]]==false){break;}}}}flag=true;}boolisLast(strings,charch)//chÊÇ·ñÊÇsµÄÖ±½Ó»ò¼ä½ÓµÄ×îºóÒ»¸ö·ÇÖÕ½á·û{if(!capL(ch))returnfalse;for(inti=s.size()-1;i=0;i--){if(ch==s[i])returntrue;if(!capL(s[i])||toEmpty[s[i]]==false){returnfalse;}}returnfalse;}voidgetFollow(charch,setchar&follow)//Ç󵥸öÔªËصÄFOLLOW¼¯{if(!capL(ch))return;for(vectorstring::iteratoriter=rightSide.begin();iter!=rightSide.end();++iter){for(inti=0;i(*iter).size();i++){if(ch==(*iter)[i]&&i!=(*iter).size()-1){if(!capL((*iter)[i+1])){follow.insert((*iter)[i+1]);}else{getFirst((*iter)[i+1],follow);}}if(ch==(*iter)[i]&&i==(*iter).size()-1){//ÅжÏÊÇ·ñÊÇÓÒ²¿µÄ×îºóÒ»¸ö·ÇÖÕ½á·ûfollow+#follow.insert('#');}elseif(ch==(*iter)[i]&&i(*iter).size()-1){//²»ÊÇ×îºóÒ»¸öµ«Ö®ºóÈ«ÊÇ·ÇÖÕ½á·ûÇÒ¶¼ÄÜÍƳö¿Õfollow+#boolflag1=true;for(intj=i+1;j(*iter).size();j++){if(!capL((*iter)[j])||toEmpty[(*iter)[j]]==false){flag1=false;if(!capL((*iter)[j])){follow.insert((*iter)[j]);}break;}}if(flag1==true){follow.insert('#');}}}if(isLast(*iter,ch)){//chÊÇ*iterµÄ×îºóÒ»¸ö·ûºÅ£¨Ö±½Ó»ò¼ä½Ó£©intn=senRever.count(*iter);multimapstring,char::iteratormIter=senRever.find(*iter);for(inti=0;in;i++,++mIter){if(mIter-second!=ch)getFollow(mIter-second,follow);}}}}intmain(){intcnt=0;while(cinlr){if(cnt==0){Begin=l;cnt++;}if(l=='0')break;sentence.insert(make_pair(l,r));//²úÉúʽsenRever.insert(make_pair(r,l));ter.insert(l);//·ÇÖÕ½á·û¼¯ºÏ(×ó²¿)rightSide.push_back(r);//ÓÒ²¿µÄ¼¯ºÏ/*if(r==^){//ÅжÏÊÇ·ñÓзÇÖÕ½á·û-^toEmpty[l]=true;}else{if(toEmpty.find(l)==toEmpty.end()){toEmpty[l]=false;}}*/}for(setchar::iteratorsIter=ter.begin();sIter!=ter.end();++sIter){//ÅжÏÊÇ·ñÓзÇÖÕ½á·û-^if(isToEmpty(*sIter)){toEmpty[*sIter]=true;}else{toEmpty[*sIter]=false;}}for(setchar::iteratoriter=ter.begin();iter!=ter.end();iter++){flag=false;cout*iterFIRST¼¯:;fir.clear();getFirst(*iter,fir);for(setchar::iteratoriterF=fir.begin();iterF!=fir.end();iterF++){cout*iterF;}coutendl;follow.clear();getFollow(*iter,follow);coutFOLLOW¼¯:;if(*iter==Begin){cout#;}for(setchar::iteratoriterF=follow.begin();iterF!=follow.end();++iterF){if(*iterF!='^')cout*iterF;}coutendlendl;}system(pause);return0;}