編譯原理 語法分析程序設(shè)計(jì)LL分析法

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

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

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

4、',e代表空char start='E'int len=8;charG1010="E->TR","R->+TR","R->e","T->FW","W->*FW","W->e","F->(E)","F->i"/存儲(chǔ)文法中的產(chǎn)生式 char VN6='E','R','T','W','F' /

5、存儲(chǔ)非終結(jié)符 char VT6='i','+','*','(',')','#' /存儲(chǔ)終結(jié)符 char SELECT1010="(,i","+","),#","(,i","*","+,),#","(","i"/存儲(chǔ)文法中每個(gè)產(chǎn)生式對(duì)應(yīng)的SELECT集 char Right108="->TR","->+

6、TR","->e","->FW","->*FW","->e","->(E)","->i"stack <char> stak;bool compare(char *a,char *b) int i,la=strlen(a),j,lb=strlen(b); for(i=0;i<la;i+)for(j=0;j<lb;j+) if(ai=bj)return 1; return 0;char *Find(char v

7、n,char vt) int i; for(i=0;i<k;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); printf("_n");

8、 printf("n 對(duì)符號(hào)串%s的分析過程n",word);printf(" -n"); printf("n"); printf(" 步驟 棧頂元素 剩余輸入串 動(dòng)作n");printf(" -n"); p=stak.top(); while(p!='#') printf("%7d ",i+); p=stak.top(); stak.pop(); printf("%6c ",p); for(j=k,m=0;j<l;j+)output

9、m+=wordj; outputm='0' printf("%10s",output); if(p=wordk) if(p='#') printf(" 分析成功 n"); return "SUCCESS" printf(" 匹配終結(jié)符%cn",p); k+; else strcpy(action,Find(p,wordk); if(strcmp(action,"error")=0) printf(" 沒有可用的產(chǎn)生式n"); return &q

10、uot;ERROR" printf(" 展開非終結(jié)符%c%sn",p,action); int l_act=strlen(action); if(actionl_act-1='e')continue; for(j=l_act-1;j>1;j-)stak.push(actionj); if(strcmp(output,"#")!=0)return "ERROR" int main () freopen("in.txt","r",stdin); char source

11、100; int i,j,flag,l,m; printf("n*為了方便編寫程序，用R代表E',W代表T',e代表空*nn"); printf("該文法的產(chǎn)生式如下：n"); for(i=0;i<len;i+)printf(" %sn",Gi); printf("_n"); printf("n該文法的SELECT集如下：n"); for(i=0;i<len;i+) printf(" SELECT(%s) = %s n",Gi,SELECTi);

12、printf("_n"); /判斷是否是LL(1)文法 flag=1; for(i=0;i<8;i+) for(j=i+1;j<8;j+) 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(&qu

13、ot;_n"); /預(yù)測(cè)分析表 for(i=0,k=0;i<8;i+) l=strlen(SELECTi); for(j=0;j<l;j+=2) MAPk.vn=Gi0; MAPk.vt=SELECTij; strcpy(MAPk.s,Righti); k+; printf("n表達(dá)式文法的預(yù)測(cè)分析表如下：nn"); printf(" "); for(i=0;i<6;i+)printf("%10c",VTi); printf("n"); for(i=0;i<5;i+) printf(" -n"); printf("%10c",VNi); for(j=0;j<6;j+) for(m=0;m<k;m+) if(VNi=MAPm.vn && VTj=MAPm.vt