編譯原理課程設計LL1文法分析器

1、 目 錄引言.1第一章 概述.4 1.1設計內容.4 1.2設計要求.4第二章 設計的基本原理.4 2.1預測分析表的構成原理.4 2.2預測分析程序的生成.5 第三章 程序設計.5 3.1總體方案設計.6 3.2各模塊設計.6 第四章 程序測試.7附錄 程序清單.8課 程 設 計設計題目LL(1)文法分析器學生姓名號 學 號指導教師專業(yè)班級2010 年 12 月 合肥工業(yè)大學課程設計任務書設 計題 目LL(1)文法分析器成績主要內容預測分析表自動構造程序的實現(xiàn)設計內容及要求：對于任意輸入的一個LL(1)文法，構造其預測分析表。要求：首先實現(xiàn)集合FIRST(X)構造算法和集合FOLLOW(A)

2、構造算法，再實現(xiàn)教材P.79給出的預測分析表構造算法。程序顯示輸出預測分析表或輸出到指定文件中。預測分析程序的實現(xiàn)設計內容及要求：對文法 G: EE+T|T 按教材P.76表4.1構造出G的預測分析程序， TT*F|F 程序顯示輸出如P.78那樣的匹配過程。F（E）|i指導教師意見該生能按時完成課程設計任務書所規(guī)定的程序設計，綜合運用所學知識獨立分析和解決問題的能力 。程序設計方案 。論文論述 ，文理 ，格式 。程序運行結果 。程序驗收時回答問題 。 簽名： 第一章 概述1.1 設計內容:1:預測分析表自動構造程序的實現(xiàn)2:預測分析程序的實現(xiàn)1.2 設計要求 1:設計內容及要求：對于任意輸入的

3、一個LL(1)文法，構造其預測分析表。要求：首先實現(xiàn)集合FIRST(X)構造算法和集合FOLLOW(A)構造算法，再實現(xiàn)教材P.79給出的預測分析表構造算法。程序顯示輸出預測分析表或輸出到指定文件中。 2:設計內容及要求：對文法 G: EE+T|T 按教材P.76表4.1構造出G的預測分析程序， TT*F|F 程序顯示輸出如P.78那樣的匹配過程。F（E）|i第二章 設計的基本原理2.1預測分析表的構成原理對于任意給定的LL(1) 文法G,為了構造它的預測分析表M,我們就必須構造與文法G有關的集合First和fellow.首先我們對每一個XVT U Vn ,構造FIRST(X),辦法是,連續(xù)使

4、用下面的規(guī)則,直至每個集合FIRST不再增大為止.(1) 若XVT,則FIRST(X)=X.(2) 若XVn ,且有產生式X->a,則把a加入到FIRST(X)中,若X->,也是一條產生式,則把也加到FIRST(X)中.(3) 若X->Y是一個產生式且YVn,則把FIRST(Y)中所有非-元素都加到FIRST(X)中,若X->Y1Y2YK ,是一個連續(xù)的產生式, Y1Y2Yi-1 都是非終結符,而且,對于任何j,1ji-1,FIRST(Yj) 都含有(即Y1Y2Yi-1=>),則把FIRST(Yi) 中的所有非-元素都加到FIRST(X)中,特別是,若所有的FIR

5、ST(Yj)均含有,j=1,2,k,則把加到FIRST(X)中. 對于文法G中每個非終結符A構造FOLLOW(A)的辦法是,連續(xù)使用下面的規(guī)則,直到每個FOLLOW不在增大為止.(1) 對于文法的開始符號S,置#于FOLLOW(S)中;(2) 若A->aBb是一個產生式,則把FIRST(b) 加至FOLLOW(B)中;(3) 若A->aB是一個產生式,或A->aBb是一個產生式而b=>(即FIRST( b)則把FOLLOW(A)加至FOLLOW(B)中構造分析表M的算法是:(1) 對文法G的每個產生式A->a執(zhí)行第二步和第三步;(2) 對每個終結符aFIRST(a

6、), 把A->a加至MA,a中;(3) 若FIRST(a),則把任何bFOLLOW(A)把A->a加至MA,b中;(4) 把所有無定義的MA,a標上出錯標志.2.2 預測分析程序的生成 預測分析程序的總控程序在任何時候都是按STACK棧頂符號X和當前的輸入符號行事的,對于任何(X,a),總控程序每次都執(zhí)行下述三種可能的動作之一;(1) 若X=a=”#”,則宣布分析成功,停止分析過程.(2) 若X=a”#”,則把X從STACK棧頂逐出,讓a指向下一個輸入符號.(3) 若X是一個非終結符,則查看分析表M,若MA,a中存放著關于X的一個產生式,那么,首先把X逐出STACK棧頂,然后,把產

7、生式的右部符號串按反序一一推進STACK棧(若右部符號為,則意味著不推什么東西進棧).在把產生式的右部符號推進棧的同時應做這個產生式相應得語義動作,若MA,a中存放著”出錯標志”,則調用出錯診察程序ERROR. 第三章 程序設計3.1 總體方案設計 在看到這個題目后,首先想到的就是要分模塊進行設計.(1) 第一模塊:把文本文件中的LL(1)文法讀入到程序中grammer類中的數組成員g中.(2) 第二模塊:通過對已輸入到數組g中的文法,進行掃描,把相應的非終結符和終結符輸入到非終結符數組VN中和終結符數組VT中.(3) 第三模塊:生成所有的非終結符的FIRST集合(4) 第四模塊:生成所有的非

8、終結符的FOLLOW集合(5) 第五模塊:生成文法的預測分析表(6) 第六模塊:生成文法的預測分析程序通過這六模塊的設計,最后可連接成一個預測分析程序.3.2 各模塊程序設計首先要建立兩個類,分別是grammer類和SeqStack類Grammer類中有保存從文本文件讀入的LL(1)文法,用一個二維字符數組g保存,保存非終結符的字符數組VN,保存終結符的字符數組VT,文法開始符號字符變量begin , 元素對應first集合中的有空字符的非終結符數組emptychar,預測分析表為二維整形數組form.SeqStack類主要的作用為在預測分析時作為符號棧.(1) 第一模塊的設計:對于這個模塊的

9、設計,就是用輸入流對文本文件中的文法進行讀入當讀到字符|或/n時意味著一個產生式已結束,那么相應數組中相應的下標變量+1;數組gi0所存放著這個產生式對應的字符的數量.gi1為這個產生式左邊的非終結符.(2) 第二模塊的設計:在已把文法讀入到數組g中后,那么相應的gi0為每個產生式的非終結符,若此非終結符不在數組VN中,那么把此字符加入到VN中對終結符的讀入,則是從每個gi2開始掃描,若此字符不在非終結符數組VN中,也不在VT 中,那么就把此字符加入到VT中.(3) 第三模塊的設計:生成FIRST集合這個算法基本上按照書上的原理,如對每個產生式進行掃描,當掃描到非終結符時,把此字符加入到相應非

10、終結符的FIRST集合中,若遇到非終結符時,需把此非終結符的FIRST集合中除了空字符外全加入到對應的非終結符的first集合中,這就涉及到算法的一個遞歸算法,我是利用在函數的參數表中設置倆個參數,一個是FIRST數組,另外一個是非終結符,在用到遞歸時,我是利用把FIRST數組設為本產生式第一個非終結符的FIRST數組,而非終結符參數則設置為在掃描產生式右部過程中所遇到的非終結符. 然后通過循環(huán)對這個文法中的所有非終結符進行函數的調用,這樣來求到所有非終結符的FIRST集合.(4) 第四模塊的設計: 生成FOLLOW集合這個算法,關鍵就是求某非終結符A的FOLLOW集合,那么就是掃描到A后面的

11、字符,若為終結符,則把此終結符加入到A的FOLLOW集合,那么若為非終結符,則把此非終結符的FIRST集合加入到A的FOLLOW集合中,若A為某個產生式最后一個字符,則把這個產生式的第一個字符的FOLLOW集合加入到A的FOLLOW集合中,在這個算法的過程中葉涉及到運用遞歸,此遞歸的方法同樣與上述求FIRST集合中運用的遞歸方法類似(5) 第五模塊的設計: 求預測分析表的過程同樣是對每個產生式進行掃描,對每個產生式的FIRST集合中的元素,都把相應的產生式的編號寫入到對應的預測分析表中對應的位置(6) 第六模塊的設計: 生成預測分析程序,就是把#和文法開始符號進入到棧中,然后把相應的分析語句中

12、當前的輸入符號對應,在每一步過程中按照書上講到的原理,在預測分析表中找到相應的產生式.第四章 程序測試附錄 程序清單class SeqStack;/聲明棧類class grammer/定義grammer類,此類的作用把文本文件中的文法保存,并且產生這個文法的非終結符集合,終結符集合,first集合,fellow集合,預測分析表等public:grammer();grammer();void openfile(char *);void prepareform();void buildform();void buildProcess(SeqStack& ss); private:char

13、begin; char *vt; char *g; char *vn;char *first;/這時所有非終結符的first集合char *fellow;/這是所有非終結符的fellow集合char *emptychar;/這個集合中的元素為對應first集合中的有空字符的非終結符int *form;/這是對應文法的預測分析表 int count;void buildVn(); void buildVt();void buildemptychar();void buildfirst();void buildfellow();void fellowzh(char *,char);void fir

14、stzh(char *,char); int search(char *,char);void printform();void outputblank(int);const int stackIncreament=20;class SeqStack/定義SeqStack類,這個類的主要作用是在對語句的預測分析過程中作符號棧public:friend grammer;SeqStack(int sz=50);SeqStack();void Push(char x);bool Pop(char& x);bool getTop(char& x);bool IsEmpty();bool

15、 IsFull();int getSize();void MakeEmpty();void showPlay();private:char *elements;int top;int maxSize;void overflowProcess();#include<fstream>#include<iostream>#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<windows.h>#include "編譯.h"using nam

16、espace std;grammer:grammer()count=0;grammer:grammer()int i;for(i=0;i<count;i+)delete gi;delete g;delete vt;delete vn;void grammer:openfile(char *file)/這個函數的主要功能在于對文本文件中的文法進行讀入,并保存在對應的數組中,一并產生對應文法的終結符集合和非終結符集合char ch;int i,j;ifstream infile(file,ios:in);/定義文件流 if(!infile)cout<<"open err

17、or!"<<endl;exit(1);while(ch=infile.get()!=EOF)if(ch='-')if(ch=infile.get()='>')count+;elseinfile.seekg(-1,ios:cur);else if(ch='|')count+;else g=new char *count;for(i=0;i<count;i+)gi=new char 15;gi0=0; infile.clear();/能重新激活文件流infile.seekg(0,ios:beg);/定位i=0;j=1

18、;while(ch=infile.get()!=EOF)if(ch='-')if(infile.get()!='>')gij=ch;gi0+;j+;if(ch=EOF)break;elseinfile.seekg(-1,ios:cur);else if(ch='|')i+;gi1=gi-11;gi0=1;j=2;else if(ch='n')infile.seekg(-3,ios:cur);ch=infile.get();if(ch!='n')i+;j=1;infile.seekg(2,ios:cur);el

19、segij=ch;gi0+;j+;cout<<count<<endl;for(i=0;i<count;i+)for(j=1;j<=gi0;j+)cout<<gij<<" "cout<<endl;buildVn();/建立非終結符集合buildVt();/建立終結符集合void grammer:buildVn()int i=1,j=0;vn=new charcount+1;vni=gj+1;for(;j<count;j+)if(gj1!=gj-11) i+;vni=gj1;vn0=i;begin=v

20、n1;cout<<"本文法開始符為:"<<begin<<endl;cout<<"本文法非終結符為:"<<" "for(i=1;i<=vn0;i+)cout<<vni<<" "cout<<endl;void grammer:buildVt()int i=1,j=0,t;char ch;vt=new char100;vt0=0;for(;j<count;j+)t=2;for(;t<=gj0;t+)ch=gj

21、t;if(!search(vt,ch)&&!search(vn,ch)vti+=gjt;vt0+;cout<<"本文法終結符為:"<<" "for(i=1;i<=vt0;i+)cout<<vti<<" "cout<<endl;int grammer:search(char *a,char ch)/搜索函數,用于在指定數組中對指定字符進行搜尋,若存在輸出對應的序號,若不在則輸出0for(int i=1;i<=a0;i+)if(ch=ai)return

22、 i;return 0;void grammer:buildemptychar()/建立對應first集合中含有空字符的的非終結符集合int i=0,j=2,t=1;bool flag=true,flag1;emptychar=new charvn0+1; emptychar0=0;for(;i<count;i+)if(gi2=''&&!search(emptychar,gi1)emptychart+=gi1;emptychar0+;while(flag)flag=false;for(i=0;i<count;i+)for(j=2;j<=gi0;

23、j+)if(search(emptychar,gij)flag1=true;elseflag1=false;break;if(flag1=true&&!search(emptychar,gi1)emptychart+=gi1;emptychar0+;flag=true;cout<<"First集中含有空字符的有: "for(i=1;i<=emptychar0;i+)cout<<emptychari<<" "cout<<endl;void grammer:buildfirst()int

24、i;first=new char* vn0;for(i=0;i<vn0;i+)firsti=new charvt0+1;for(i=0;i<vn0;i+)firsti0=0;for(i=1;i<=vn0;i+)firstzh(firsti-1,vni);void grammer:buildfellow()int i,j;fellow=new char* vn0;for(i=0;i<vn0;i+)fellowi=new charvt0+1;for(i=0;i<vn0;i+)fellowi0=0;for(i=1;i<=vn0;i+)fellowzh(fellow

25、i-1,vni);for(i=0;i<vn0;i+)cout<<vni+1<<"的fellow集合為: "for(j=1;j<=fellowi0;j+)cout<<fellowij<<" "cout<<endl;void grammer:firstzh(char *a,char ch)/對指定非終結符建立對應的first集合int i,j,t=1;for(i=0;i<count;i+)for(j=2;j<=gi0;j+)if(gi1=ch)if(!search(vn,gi

26、j)&&gij!='')/找到對應產生式中的終結符時if(!search(a,gij)at+=gij;a0+;break;else if(gij!='')/找到對應的產生式中的非終結符時firstzh(a,gij);/用遞歸的方法算出此非終結符的first集合if(!search(emptychar,gij)/當此非終結符的first集合中無空字符時,對此產生式掃描完畢break;elseelsebreak;void grammer:fellowzh(char *a,char ch)/對指定非終結符建立fellow集合int i,j,k,m,n,

27、t=a0;if(ch=begin)/把#字符放入開始符的fellow集合if(!search(a,'#')a+t='#'a0+;for(i=0;i<count;i+)for(j=2;j<=gi0;j+)if(gij=ch)for(m=j;m<=gi0;m+)if(m=gi0)if(gi1!=ch)fellowzh(a,gi1);/發(fā)現(xiàn)要求的非終結符在此產生式的末尾時else break;elseif(!search(vn,gim+1)/當此非終結符后面的字符為終結字符時,放入對應的fellow集合if(!search(a,gim+1)a+t=g

28、im+1;a0+;break;else k=search(vn,gim+1);/把此非終結符后面的非終結符的first集合中的元素放入對應的fellow集合for(n=1;n<=firstk-10;n+)if(!search(a,firstk-1n)a+t=firstk-1n;a0+;if(!search(emptychar,gim+1)break;void grammer:prepareform()int i,j;buildemptychar();buildfirst();buildfellow();for(i=0;i<vn0;i+)if(search(emptychar,vni

29、+1)j=firsti0;firsti+j=''firsti0+;for(i=0;i<vn0;i+)cout<<vni+1<<"的first集合為: "for(j=1;j<=firsti0;j+)cout<<firstij<<" "cout<<endl;void grammer:buildform()int i,j,k,t,m,n;bool flag;form=new int*vn0;for(i=0;i<vn0;i+)formi=new intvt0;for(i

30、=0;i<vn0;i+)for(j=0;j<vt0;j+)formij=-1;for(i=0;i<count;i+)t=search(vn,gi1);flag=true;for(j=2;j<=gi0;j+)k=search(vt,gij);/若發(fā)現(xiàn)這個產生式的first集合中的對應的終結符時if(k)if(gij!='')if(formt-1k-1!=-1)cout<<"本終結符錯誤!"<<endl;exit(1);formt-1k-1=i;flag=false;break;else/若發(fā)現(xiàn)對應產生式中的fir

31、st集合中含有空字符時for(m=1;m<=fellowt-10;m+)if(fellowt-1m!='#')/可把對應的非終結符的fellow集合中的元素對應的表項中填入該產生式的標號n=search(vt,fellowt-1m);if(formt-1n-1!=-1)cout<<"有終結符本fellow集合中非#錯誤!"<<endl;exit(1);formt-1n-1=i;elseif(formt-1k-1!=-1) cout<<"有終結符本fellow集合中#錯誤!"<<endl

32、; exit(1);formt-1k-1=i;flag=false;break;else/找到該產生式中的非終結符時k=search(vn,gij);for(m=1;m<=firstk-10;m+)if(firstk-1m!='')n=search(vt,firstk-1m);if(formt-1n-1!=-1) cout<<"本first集合中非!"<<endl; exit(1); formt-1n-1=i;elseif(!search(firstk-1,'')/若在此終結符對應的first集合中無空字符時fl

33、ag=false;break;if(flag=true)/說明該產生式對應的first集合中含有空字符for(m=1;m<=fellowt-10;m+)if(fellowt-1m!='#')n=search(vt,fellowt-1m);if(formt-1n-1!=-1)cout<<"本fellow集合中非#錯誤!"<<endl;exit(1);formt-1n-1=i;elsen=search(vt,'');if(formt-1n-1!=-1)cout<<"本fellow集合中#錯誤!&

34、quot;<<endl;exit(1);formt-1n-1=i;printform();void grammer:outputblank(int i)int j;for(j=0;j<i;j+)cout<<" "void grammer:printform()int i,j,k,t,m;cout<<"-預測分析表如下所示-"<<endl;outputblank(6);for(i=1;i<=vt0;i+)if(vti='')cout<<"#"outp

35、utblank(10);elsecout<<vti;outputblank(10);cout<<endl;for(i=0;i<vn0;i+)cout<<" "<<vni+1;outputblank(4);for(j=0;j<vt0;j+)k=formij;if(k=-1)Sleep(500);cout<<"error"outputblank(6);elseSleep(1000);t=9-gk0;cout<<gk1<<"->"for(m

36、=2;m<=gk0;m+)cout<<gkm;outputblank(t);cout<<endl;void grammer:buildProcess(SeqStack& ss)char *dia,ch;int i,j,inlen,m,n,index=0,proc=0;bool flag=true,flag1=false;dia=new char20;cout<<"請輸入待分析的字符串"<<endl;cin>>dia;for(i=0,inlen=0;i<20;i+)if(diai!='0&

37、#39;)inlen+;else break;cout<<"步驟"outputblank(8);cout<<"符號棧"outputblank(15);cout<<"輸入串"outputblank(15);cout<<"所用產生式"<<endl;diainlen+='#' ss.Push('#');ss.Push(begin);while(flag)Sleep(1500); cout<<proc;if(proc&g

38、t;=10)outputblank(11);elseoutputblank(12);+proc;ss.showPlay();outputblank(21-ss.getSize();for(j=index;j<inlen;j+)cout<<diaj; outputblank(21-inlen+index);if(flag1=true)cout<<gformm-1n-11<<"->"for(j=2;j<=gformm-1n-10;j+)cout<<gformm-1n-1j;cout<<endl;els

39、ecout<<endl; ss.getTop(ch);m=search(vn,ch);if(diaindex!='#')n=search(vt,diaindex);else n=search(vt,''); if(search(vt,ch)/當棧頂是終結符if(ch=diaindex)/且此終結符與輸入串此時檢測的終結符符號相同index+;ss.Pop(ch);flag1=false;else cout<<"該字符串不能由該文法推出"<<endl;exit(1);else if(ch='#')if(ch=diaindex)cout<<endl;cout<<"-分析完成-"<<endl;flag=false;else cout<<"該字符串不能由該文法推出"<<endl;exit(1);else if(formm-1n-1!=-1)/當棧頂的非終結符與輸入串對應的終結符在預測分析表中相應的項存在時if(gformm-1n-12!='')ss.Pop(ch);for(i=gformm-1n-10;i>=2;i-)ss.Push(gformm-1n-1i);el