编译原理课程设计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)文法分析器学生姓名号 学 号指导教师专业班级2010 年 12 月 合肥工业大学课程设计任务书设 计题 目LL(1)文法分析器成绩主要内容预测分析表自动构造程序的实现设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)

2、构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。预测分析程序的实现设计内容及要求：对文法 G: EE+T|T 按教材P.76表4.1构造出G的预测分析程序， TT*F|F 程序显示输出如P.78那样的匹配过程。F（E）|i指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力 。程序设计方案 。论文论述 ，文理 ，格式 。程序运行结果 。程序验收时回答问题 。 签名： 第一章 概述1.1 设计内容:1:预测分析表自动构造程序的实现2:预测分析程序的实现1.2 设计要求 1:设计内容及要求：对于任意输入的

3、一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材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),办法是,连续使

4、用下面的规则,直至每个集合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 ,是一个连续的产生式, 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)的办法是,连续使用下面的规则,直到每个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执行第二步和第三步;(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),总控程序每次都执行下述三种可能的动作之一;(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数组,而非终结符参数则设置为在扫描产生式右部过程中所遇到的非终结符. 然后通过循环对这个文法中的所有非终结符进行函数的调用,这样来求到所有非终结符的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);/发现要求的非终结符在此产生式的末尾时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);/若发现这个产生式的first集合中的对应的终结符时if(k)if(gij!='')if(formt-1k-1!=-1)cout<<"本终结符错误!"<<endl;exit(1);formt-1k-1=i;flag=false;break;else/若发现对应产生式中的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