編譯原理-語法分析程序設(shè)計(jì)(LL(1)分析法)(共6頁)

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

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

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

4、E-TR,R-+TR,R-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;/存儲文法中每個(gè)產(chǎn)生式對應(yīng)的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=

5、0;ila;i+)for(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.

6、push(start); 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.

7、txt,r,stdin); 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+)

8、 if(Gi0=Gj0) 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); /預(yù)測分析表 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表達(dá)式文法的預(yù)測分析表如下：nn); printf( ); for(i=0;i6;i+)printf(%10c,VTi); printf(n); for(i=0;i