編譯原理 語法分析程序設計LL分析法

1、1. 實驗目的：掌握LL(1)分析法的基本原理，掌握LL(1)分析表的構造方法，掌握LL(1) 驅(qū)動程序的構造方法。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)等，最后看是否構成一個符合要求的程序，按該語言使用的語法規(guī)則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。編譯程序的語法規(guī)則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而

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

3、符函數(shù)。4、對輸入的符號串進行掃描，從起始符的生成式開始。如果匹配成功某個非終結符生成式右邊的首個終結符，則將這個生成式輸出。匹配過程中，應該出現(xiàn)的非終結符沒有出現(xiàn)，則出錯處理。 5.軟件設計與編程：對應源程序代碼： #include <iostream.h>#include <stdio.h>#include <stack>using namespace std;struct Node1 char vn; char vt; char s10;MAP20; /存儲分析預測表每個位置對應的終結符，非終結符，產(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ǎn)生式 char VN6='E','R','T','W','F' /

5、存儲非終結符 char VT6='i','+','*','(',')','#' /存儲終結符 char SELECT1010="(,i","+","),#","(,i","*","+,),#","(","i"/存儲文法中每個產(chǎn)生式對應的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 對符號串%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;j<l;j+)output

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

10、uot;ERROR" printf(" 展開非終結符%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"); /預測分析表 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表達式文法的預測分析表如下：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