1、1. 實驗目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的構(gòu)造方法，掌握LL(1) 驅(qū)動程序的構(gòu)造方法。2.實驗要求：實現(xiàn)LR分析法（P147,例4.6）或預測分析法（P121,例4.3）。3.實驗環(huán)境：一臺配置為1G的XP操作系統(tǒng)的PC機;Visual C+6.0.4.實驗原理：編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語 法規(guī)則的語法單位，如表達式、賦值、循環(huán)等，最后看是否構(gòu)成一個符合要求的程序，按該語言使用的語法規(guī)則分析檢查每條語句是否有正確的邏輯結(jié)構(gòu)，程序是最終的一個語法單位。編譯程序的語法規(guī)則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而

2、下分析法和自下而上分析法。自上而下就是從文法的開始符號出發(fā)，向下推導，推出句子。而自下而上分析法采用的是移進歸約法，基本思想是：用一個寄存符號的先進后出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產(chǎn)生式的一個候選式時，即把棧頂?shù)倪@一部分歸約成該產(chǎn)生式的左鄰符號。自頂向下帶遞歸語法分析：1、首先對所以的生成式消除左遞歸、提取公共左因子2、在源程序里建立一個字符串數(shù)組，將所有的生成式都存在這個數(shù)組中。3、給每個非終結(jié)符寫一個帶遞歸的匹配函數(shù)，其中起始符的函數(shù)寫在main函數(shù)里。 這些函數(shù)對生成式右邊從左向右掃描，若是終結(jié)符直接進行匹配，匹配失敗，則調(diào)用出錯函數(shù)。如果是非終結(jié)符則調(diào)用相應的非終結(jié)

3、符函數(shù)。4、對輸入的符號串進行掃描，從起始符的生成式開始。如果匹配成功某個非終結(jié)符生成式右邊的首個終結(jié)符，則將這個生成式輸出。匹配過程中，應該出現(xiàn)的非終結(jié)符沒有出現(xiàn)，則出錯處理。 5.軟件設計與編程：對應源程序代碼： #include #include #include using namespace std;struct Node1 char vn; char vt; char s10;MAP20; /存儲分析預測表每個位置對應的終結(jié)符，非終結(jié)符，產(chǎn)生式 int k; /用R代表E,W代表T,e代表空char start=E;int len=8;charG1010=E-TR,R-+TR,R-

4、e,T-FW,W-*FW,W-e,F-(E),F-i;/存儲文法中的產(chǎn)生式 char VN6=E,R,T,W,F; /存儲非終結(jié)符 char VT6=i,+,*,(,),#; /存儲終結(jié)符 char SELECT1010=(,i,+,),#,(,i,*,+,),#,(,i;/存儲文法中每個產(chǎn)生式對應的SELECT集 char Right108=-TR,-+TR,-e,-FW,-*FW,-e,-(E),-i;stack stak;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;ila;i+)for(

5、j=0;jlb;j+) if(ai=bj)return 1; return 0;char *Find(char vn,char vt) int i; for(i=0;ik;i+) if(MAPi.vn=vn & MAPi.vt=vt)return MAPi.s; return error;char * Analyse(char * word) char p,action10,output10; int i=1,j,l=strlen(word),k=0,l_act,m; while(!stak.empty() stak.pop(); stak.push(#);stak.push(start);

6、printf(_n); printf(n 對符號串%s的分析過程n,word);printf( -n); printf(n); printf( 步驟 棧頂元素 剩余輸入串 動作n);printf( -n); p=stak.top(); while(p!=#) printf(%7d ,i+); p=stak.top(); stak.pop(); printf(%6c ,p); for(j=k,m=0;j1;j-)stak.push(actionj); if(strcmp(output,#)!=0)return ERROR; int main () freopen(in.txt,r,stdin);

7、 char source100; int i,j,flag,l,m; printf(n*為了方便編寫程序，用R代表E,W代表T,e代表空*nn); printf(該文法的產(chǎn)生式如下：n); for(i=0;ilen;i+)printf( %sn,Gi); printf(_n); printf(n該文法的SELECT集如下：n); for(i=0;ilen;i+) printf( SELECT(%s) = %s n,Gi,SELECTi); printf(_n); /判斷是否是LL(1)文法 flag=1; for(i=0;i8;i+) for(j=i+1;j8;j+) if(Gi0=Gj0)

8、if(compare(SELECTi,SELECTj) flag=0;break; if(j!=8)break; if(flag)printf(n有相同左部產(chǎn)生式的SELECT集合的交集為空，所以文法是LL（1）文法。n); else printf(n有相同左部產(chǎn)生式的SELECT集合的交集不為空，所以文法不是LL（1）文法。n); printf(_n); /預測分析表 for(i=0,k=0;i8;i+) l=strlen(SELECTi); for(j=0;jl;j+=2) MAPk.vn=Gi0; MAPk.vt=SELECTij; strcpy(MAPk.s,Righti); k+; printf(n表達式文法的預測分析表如下：nn); printf( ); for(i=0;i6;i+)printf(%10c,VTi); printf(n); fo