編譯原理實驗報告材料FIRST集和FOLLOW集

實用標準文案編譯原理實驗報告實驗名稱 計算first集合和follow 集合實驗時間院系 計算機科學與技術班級 軟件工程1班學號姓名精彩文檔實用標準文案實驗目的輸入：任意的上下文無關文法。輸出：所輸入的上下文無關文法一切非終結符的 first集合和follow 集合。實驗原理設文法G[S]＝（VN，VT，P，S），則首字符集為：*FIRST（α）＝{a|α aβ，a∈VT，α,β∈V*}。*若α ε，ε∈FIRST（α）。由定義可以看出，F(xiàn)IRST（α）是指符號串α能夠推導出的所有符號串中處于串首的終結符號組成的集合。所以 FIRST集也稱為首符號集。設α＝x1x2?xn，F(xiàn)IRST（α）可按下列方法求得：令FIRST（α）＝Φ，i＝1；（1） 若xi∈VT，則xi∈FIRST（α）；（2） 若xi∈VN；若εFIRST（xi），則FIRST（xi）∈FIRST（α）；若ε∈FIRST（xi），則FIRST（xi）－{ε}∈FIRST（α）；（3） i＝i+1，重復（1）、（2），直到xi∈VT，（i＝2，3，?，n）或xi∈VN且若εFIRST（xi）或i>n為止。當一個文法中存在ε產生式時，例如，存在 A→ε，只有知道哪些符號可以合法地出現(xiàn)在非終結符 A之后，才能知道是否選擇 A→ε產生式。這些合法地出現(xiàn)在非終結符A之后的符號組成的集合被稱為 FOLLOW集合。下面我們給出文法的FOLLOW集的定義。設文法G[S]＝（VN，VT，P，S），則精彩文檔實用標準文案FOLLOW（A）＝{a|S ?Aa?，a∈VT}。*若S?A，#∈FOLLOW（A）。由定義可以看出，F(xiàn)OLLOW（A）是指在文法 G[S]的所有句型中，緊跟在非終結符A后的終結符號的集合。FOLLOW集可按下列方法求得：（1） 對于文法G[S]的開始符號S，有#∈FOLLOW（S）；（2） 若文法G[S]中有形如B→xAy的規(guī)則，其中x，y∈V*，則FIRSTy）－{ε}∈FOLLOW（A）；（3） 若文法G[S]中有形如B→xA的規(guī)則，或形如 B→xAy的規(guī)則且ε∈FIRST（y），其中x，y∈V*，則FOLLOW（B）∈FOLLOW（A）；精彩文檔實用標準文案實驗內容計算first集合和follow 集合實驗心得通過上機實驗我對文法符號的FIRST集和FOLLOW集有了更深刻的理解，已經(jīng)熟練的掌握了求解的思想和方法，同時也鍛煉了自己的動手解決問題的能力，對編程能力也有所提高。實驗代碼與結果#include<iostream>#include<string>#include<algorithm>usingnamespacestd;#defineMAXS50intNONE[MAXS]={0};stringstrings;// 產生式stringVn;//非終結符stringVt;//終結符stringfirst[MAXS];//用于存放每個終結符的first集stringFirst[MAXS];//用于存放每個非終結符的first集stringFollow[MAXS];//用于存放每個非終結符的follow集intN;//產生式個數(shù)精彩文檔實用標準文案structSTR{stringleft;stringright;};求VN和VTvoidVNVT(STR*p){inti,j;for(i=0;i<N;i++){for(j=0;j<(int)p[i].left.length();j++){if((p[i].left[j]>='A'&&p[i].left[j]<='Z')){if(Vn.find(p[i].left[ j])>100)Vn+=p[i].left[ j];}else精彩文檔實用標準文案{if(Vt.find(p[i].left[ j])>100)Vt+=p[i].left[j];}}for(j=0;j<(int)p[i].right.length();j++){if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z')){if(Vt.find(p[i].right[j])>100)Vt+=p