编译原理课程设计-LL(1)文法分析器

1目录引言...............................................................1第一章概述.....................................................41.1设计内容....................................................41.2设计要求...................................................4第二章设计的基本原理...........................................42.1预测分析表的构成原理.......................................42.2预测分析程序的生成.........................................5第三章程序设计.................................................53.1总体方案设计...............................................63.2各模块设计.................................................6第四章程序测试.................................................7附录程序清单.................................................82课程设计LL(1)文法分析器2010年12月设计题目学号专业班级学生姓名号指导教师合肥工业大学课程设计任务书设计题目LL(1)文法分析器成绩主要内容预测分析表自动构造程序的实现设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。预测分析程序的实现设计内容及要求：对文法G:E→E+T|T按教材P.76表4.1构造出G的预测分析程序，T→T*F|F程序显示输出如P.78那样的匹配过程。F→（E）|i指导教师意见该生能按时完成课程设计任务书所规定的程序设计，综合运用所学知识独立分析和解决问题的能力。程序设计方案。论文论述，文理，格式。程序运行结果。程序验收时回答问题。签名：4第一章概述1.1设计内容:1:预测分析表自动构造程序的实现2:预测分析程序的实现1.2设计要求1:设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。2:设计内容及要求：对文法G:E→E+T|T按教材P.76表4.1构造出G的预测分析程序，T→T*F|F程序显示输出如P.78那样的匹配过程。F→（E）|i第二章设计的基本原理2.1预测分析表的构成原理对于任意给定的LL(1)文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈VTUVn,构造FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止.(1)若X∈VT,,则FIRST(X)={X}.(2)若X∈Vn,且有产生式X-a……,则把a加入到FIRST(X)中,若X-ε,也是一条产生式,则把ε也加到FIRST(X)中.(3)若X-Y……是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到FIRST(X)中,若X-Y1Y2……YK,是一个连续的产生式,Y1Y2……Yi-1都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有ε(即Y1Y2……Yi-1=ε),则把FIRST(Yi)中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(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)中5构造分析表M的算法是:(1)对文法G的每个产生式A-a执行第二步和第三步;(2)对每个终结符a∈FIRST(a),把A-a加至M[A,a]中;(3)若ε∈FIRST(a),则把任何b∈FOLLOW(A)把A-a加至M[A,b]中;(4)把所有无定义的M[A,a]标上出错标志.2.2预测分析程序的生成预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号行事的,对于任何(X,a),总控程序每次都执行下述三种可能的动作之一;(1)若X=a=”#”,则宣布分析成功,停止分析过程.(2)若X=a≠”#”,则把X从STACK栈顶逐出,让a指向下一个输入符号.(3)若X是一个非终结符,则查看分析表M,若M[A,a]中存放着关于X的一个产生式,那么,首先把X逐出STACK栈顶,然后,把产生式的右部符号串按反序一一推进STACK栈(若右部符号为ε,则意味着不推什么东西进栈).在把产生式的右部符号推进栈的同时应做这个产生式相应得语义动作,若M[A,a]中存放着”出错标志”,则调用出错诊察程序ERROR.第三章程序设计3.1总体方案设计在看到这个题目后,首先想到的就是要分模块进行设计.(1)第一模块:把文本文件中的LL(1)文法读入到程序中grammer类中的数组成员g中.(2)第二模块:通过对已输入到数组g中的文法,进行扫描,把相应的非终结符和终结符输入到非终结符数组VN中和终结符数组VT中.(3)第三模块:生成所有的非终结符的FIRST集合(4)第四模块:生成所有的非终结符的FOLLOW集合(5)第五模块:生成文法的预测分析表(6)第六模块:生成文法的预测分析程序通过这六模块的设计,最后可连接成一个预测分析程序.3.2各模块程序设计首先要建立两个类,分别是grammer类和SeqStack类Grammer类中有保存从文本文件读入的LL(1)文法,用一个二维字符数组g保存,保存非终结符的字符数组VN,保存终结符的字符数组VT,文法开始符号字符变量begin,元素对应first集合中的有空字符的非终结符数组emptychar,预测分析表为二维整形数组form.6SeqStack类主要的作用为在预测分析时作为符号栈.(1)第一模块的设计:对于这个模块的设计,就是用输入流对文本文件中的文法进行读入当读到字符’|’或’/n’时意味着一个产生式已结束,那么相应数组中相应的下标变量+1;数组g[i][0]所存放着这个产生式对应的字符的数量.g[i][1]为这个产生式左边的非终结符.(2)第二模块的设计:在已把文法读入到数组g中后,那么相应的g[i][0]为每个产生式的非终结符,若此非终结符不在数组VN中,那么把此字符加入到VN中对终结符的读入,则是从每个g[i][2]开始扫描,若此字符不在非终结符数组VN中,也不在VT中,那么就把此字符加入到VT中.(3)第三模块的设计:生成FIRST集合这个算法基本上按照书上的原理,如对每个产生式进行扫描,当扫描到非终结符时,把此字符加入到相应非终结符的FIRST集合中,若遇到非终结符时,需把此非终结符的FIRST集合中除了空字符外全加入到对应的非终结符的first集合中,这就涉及到算法的一个递归算法,我是利用在函数的参数表中设置俩个参数,一个是FIRST数组,另外一个是非终结符,在用到递归时,我是利用把FIRST数组设为本产生式第一个非终结符的FIRST数组,而非终结符参数则设置为在扫描产生式右部过程中所遇到的非终结符.然后通过循环对这个文法中的所有非终结符进行函数的调用,这样来求到所有非终结符的FIRST集合.(4)第四模块的设计:生成FOLLOW集合这个算法,关键就是求某非终结符A的FOLLOW集合,那么就是扫描到A后面的字符,若为终结符,则把此终结符加入到A的FOLLOW集合,那么若为非终结符,则把此非终结符的FIRST集合加入到A的FOLLOW集合中,若A为某个产生式最后一个字符,则把这个产生式的第一个字符的FOLLOW集合加入到A的FOLLOW集合中,在这个算法的过程中叶涉及到运用递归,此递归的方法同样与上述求FIRST集合中运用的递归方法类似(5)第五模块的设计:求预测分析表的过程同样是对每个产生式进行扫描,对每个产生式的FIRST集合中的元素,都把相应的产生式的编号写入到对应的预测分析表中对应的位置(6)第六模块的设计:生成预测分析程序,就是把’#’和文法开始符号进入到栈中,然后把相应的分析语句中当前的输入符号对应,在每一步过程中按照书上讲到的原理,在预测分析表中找到相应的产生式.7第四章程序测试8附录程序清单classSeqStack;//声明栈类classgrammer//定义grammer类,此类的作用把文本文件中的文法保存,并且产生这个文法的非终结符集合,终结符集合,first集合,fellow集合,预测分析表等{public:grammer();~grammer();voidopenfile(char*);voidprepareform();voidbuildform();voidbuildProcess(SeqStack&ss);private:charbegin;char*vt;char**g;char*vn;char**first;//这时所有非终结符的first集合char**fellow;//这是所有非终结符的fellow集合char*emptychar;//这个集合中的元素为对应first集合中的有空字符的非终结符int**form;//这是对应文法的预测分析表intcount;voidbuildVn();voidbuildVt();voidbuildemptychar();voidbuildfirst();voidbuildfellow();voidfellowzh(char*,char);voidfirstzh(char*,char);intsearch(char*,char);voidprintform();voidoutputblank(int);};constintstackIncreament=20;classSeqStack//定义SeqStack类,这个类的主要作用是在对语句的预测分析过程中作符号栈{public:friendgrammer;SeqStack(intsz=50);~SeqStack();voidPush(charx);boolPop(char&x);9boolgetTop(char&x);boolIsEmpty();boolIsFull();intgetSize();voidMakeEmpty();voidshowPlay();private:char*elements;inttop;intmaxSize;voidoverflowProcess();};#includefstream#includeiostream#includestdio.h#includestdlib.h#includeassert.h#includewindows.h#include编译.husingnamespacestd;grammer::grammer(){count=0;}grammer::~grammer(){inti;for(i=0;icount;