编译原理课程设计报告

1、课程设计(论文)任务书软件学院学 院软件工程专 业07-1班一、课程设计(论文)题目LL(1)分析过程模拟二、课程设计(论文)工作自2010年6月 2日起至2010年6月28日 止。三、课程设计(论文)地点:四、课程设计(论文)内容要求：本课程设计的目的 使学生掌握LL (1)模块的基本工作原理；一培养学生基本掌握LL (1)分析的基本思路和方法；使学生掌握LL (1)的调试； 培养学生分析、解决问题的能力；一提高学生的科技论文写作能力。课程设计的任务及要求基本要求：分析LL (1)模块的工作原理;提出程序的设计方案；对所设计程序进行调试。创新要求：在基本要求达到后，可进行创新设计，如改算法效

2、率。课程设计论文编写要求要按照书稿的规格打印誉写课程设计论文论文包括目录、绪论、正文、小结、参考文献、附录等课程设计论文装订按学校的统一要求完成答辩与评分标准：完成原理分析：20分；完成设计过程(含翻译)：40分；完成调试：20分；（4）回答问题：20分。5）参考文献:（1）张素琴，吕映芝，蒋维杜，戴桂兰编译原理（第2版）.清华大学出版社（2）丁振凡.Java语言实用教程北京邮电大学出版社6）课程设计进度安排内容天数地点构思及收集资料2图书馆编程与调试4实验室撰写论文1图书馆、实验室学生签名：2009年6月22 日课程设计（论文）评审意见（1）完成原理分析（20分）：优（）、良（）、中（）、一

3、般（）、差（）；（2）设计分析（20 分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20 分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20 分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20 分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：职称：编译原理课程设计报告、课设题目问题描述设计一个给定LL （1）分析表，输入一个句子，能由依据 LL （1）分析表输出与句子对应的语法树。能对语法树生成过程 进行模拟。基本要求动态模拟算法的基本功能是：（1）输入LL（1）分析表和一个句子；（2

4、）输出LL（1）总控程序；（3）输出依据句子构成的对应语法树的过程；测试数据输入句子：i*i+i输入LL（1）分析表i+*()#EtTAtTAAt+TAT 8T8TtFBtFBBT 8t*FBT 8T8FTit(E)二、需求分析问题理解用数据库存储多行文法，用LIST控件显示算法，用GRID类依 据算法进行作图。并实现算法与生成过程的关联。问题分析求出First集和Follow集，是求出Select集的基础，因此本程 序也做了些完善，功能扩展发面，在出First集和Follow集的基 础上求Select集，判断是否为LL1文法，构造预测分析表。判断 是在LL1分析文法中通过Select集判断是

5、否是LL1文法，求出预 测分析表之后，实现了字符串，依据LL1分析表单步输出字符串 的分析过程。问题的解决其实要知道一串符号是不是该文法的一个句子，只要判断是否 能从文法的开始符号出发推导出这个输入串。语法分析可以分为 两类，一类是自上而下的分析法，一类是自下而上的分析法。自 上而下的主旨是，对任何输入串，试图用一切可能的办法，从文 法开始符号出发，自上而下的为输入串建立一棵语法树。或者说， 为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过 程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上 而下的过程。解决步骤总体步骤在自上而下的分析法中，主要是研究LL(1)分析法。它的解 决

6、步骤是首先接收到用户输入的一个文法，对文法进行检测和处 理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义 性，无左递归，无左公因子。当文法满足条件后，再分别构造文 法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL(1)分析表，最后利用分析表，根据LL(1) 语法分析构造一个分析器。LL(1)的语法分析程序包含了三个 部分，总控程序，预测分析表函数，先进先出的语法分析栈。FIRST集的确定FIRST集使用以下四个步骤判定：若 XeVTD，贝U FIRST(X)=X若 XeVN，且有产生式 Xa.，aVT。则把a加入到FIRST(X)中，艮口

7、aEFIRST(X)若XeVN，且有产生式X$，则把$也加到FIRST(X)中，昭EFIRST(X)若 XeVN, Y1，Y2，Yi 都 eVN，且有产生式 XY1Y2.Yn。当 Y1，.Yi-1=$ (1i $，则把$加到FIRST(X)中，即： FIRST(Yi) eFIRST(X)FOLLOW集的确定FOLLOW集使用以下三个步骤判定：如果X是开始符那么把#加入到FOLLOW(X)若A =aBp是一个产生式，则把FIRST(P) - $加至 FOLLOW(B )中若A =aB是一个产生式，或A =aBp是一个产生式而 P*=$(即 $ e FIRST(P)，贝U 把 FOLLOW(A)加

8、至 FOLLOW(B )中FOLLOW集的求法与FIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生 式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。 FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属 于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫 描就可以把相应的FIRST集加入到FOLLOW集中，设置 FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队 列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。 碰到死循环使用FIRS

9、T集一样的方法处理就可以。SELLECT集的确定FIRST集& FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：Aa AEVN, a EV*,若a是终结符，那么SELLECT(Aa)=a若a 是$,则 SELECT(Aa)=FOLLOW(A)若a是非终结符那么若 a*=$，贝U SELECT(Aa)=(FIRST(a)-$) UFOLLOW(A) 若 aq*=$ 则 SELECT(Aa)=FIRST(a)LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是 LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同

10、 元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相 同元素则返回TRUE。句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判 定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的 方法是使用哈希表来表示，把每一个产生式左部依次和这个产生 式SELLECT集中的每一个终结符组成关键字，其值即为这个产 生式，送入哈希表。这样在进行句子的分析时就可以很容易判断 是否使用某一个产生式来进行规约。在实际分析时设置两个栈， 把#压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右 向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依 次从两个栈中取出两个元素进

11、行比较，假如一样就匹配，假如可 以规约就规约，否则就不是该文法的句子。三、概要设计1、设计原理、LL (1)文法的定义LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是: 第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表 明分析过程中将使用最左推导，1表明只需向右看一个符号便可 决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和 SELLECT集，然后判断是否为LL(1)文法，最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1)分析法中， 每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右 部

12、去替换该非终极符；当出现终结符时，判断其与剩余输入串的 第一个字符是否匹配，如果匹配，则继续分析，否则报错LL(1) 分析方法要求文法满足如下条件：对于任一非终极符A的两个不 同产生式Aa,Ap，都要满足下面条件：SELECT(Aa) n SELECT(Ap)=0、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该 选择用哪个产生式进行推导。它的行对应文法的非终极符，列对 应终极符，表中的值有两种：一是产生式的右部的字符串，一是 null。若用M表示LL(1)分析表，则M可表示如下：M: VNxVTPUErrorM(A, t) = A分a，当 teselect(Aa)，否则

13、UM(A, t) = Error其中P表示所有产生式的集合。、语法分析程序构造LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E 为给定测试数据的开始符号，#为句子括号即输入串的括号。分析 表用一个二位数组M表示，数组元素MA，a中的下标A表示 非终结符，a为终结符或句子括号#，二维数组中存放的是一 条关于A的产生式，表明当非终结符A向下推导时，面临输入 符a时，所采用的候选产生式，当元素内容无产生式时，则表明用A的左部向下推导时出现了不该出现的符号，因此元素内容转 向出错处理的信息。LL(1)分析过程主要包括以下四个动作：替换：当XeVN时选相应产生式的右部0去替换X。此时X 出栈，

14、0逆序入栈。匹配：当XeVT时它与a进行匹配，其结果可能成功，也可 能失败，如果成功则符号栈中将X退栈并将输入流指针向前移动 一位，否则报错。接受：当格局为(#，空#)时报告分析成功。报错：出错后，停止分析。并给出相应的错误提示信息。驱动程序框图如：#， E，进栈，当前终结符号送入2上托栈顶符号送入2若产生式为 A-A1A2“An,按逆序即 AnA2A1入栈Y T结束2、预测分析表具体构造此语法程序的实现采用手工操作输入构造LL(1)分析表。LL(1)分析表用一个二维矩阵表示，其中每个非终极符对应一行， 每个终级符对应一列，一个非终极符和一个终极符可以确定矩阵 中的一个元素，元素的值表示该非终

15、极符和该终极符对应的产生 式。每个矩阵元素都是一个字符串，所有元素初始化为null；构 造LL(1)表时，根据给出的测试数据中相应的分析表LL(1)分析表 的内容。其中输入产生式为空用&表示，产生式不存在则进行出 错处理，在数组中出错用NULL或者null表示。在根据LL(1)分 析表选择产生式进行推导时，若查到的产生式为NULL或者null 表示无相应的产生式可选，不匹配错误；否则根据编号得到相应 的产生式进行推导。预测分析表的模型示意图控制程序是依据分析表和分析栈联合控制输入字符串的识别和分析，它 在任何时候都是依据当前分析栈的栈顶符号和当前输入字符来执行控制功 能。对不同文法，控制程序是

16、相同的。输入缓冲器用来存放被分析的符号串，符号串后跟以标志符事。栈中存放一系列文法符号，符号#存在于栈的底部，分析开始时，栈底 先放好#，然后放进文法开始符号。分析表是一个二维数组MA,a，其中A是非终结符号，a是终结符号 或是符号#，MA,a内容为一条关于A的产生式或出错标志，不同语言使 用内容不同的分析表。e.输出流是在分析中不断产生的输出序列。3、主要算法思想（1）、分析开始时，首先将标志符号#和文法开始符号E 依次压入符号栈；输入流指针指向分析串的第一个输入符号，即 由符号栈和输入流构成的初始格局为：（#E,a1a2.an#）然后，反复执行第2步所列的工作。（2）、设在分析的某一步，符

17、号栈及剩余的输入流处于如 下的格局：（#A12.Am-1Am,aiai+1.an#）其中，A1A2.Am-1Am为分析栈中的文法符号，此时，可视 栈顶符号Xm的不同情况，分别作如下动作：若AmeVN，则以Am及ai组成的符号对（Am，ai）查分析表 M。设M（Am，ai）为一产生式，假设是Am UVW，此时将Am 从分析栈中弹出，并将UVW逆序压入栈中，从而得到新的格局：（#A1A2.Am-1WVU,aiai+1.an#）但若T（Am，ai）=NULL或null，则调用出错处理程序进行处 理；若Am=g#，则表明栈顶符号已经与当前扫描的输入符号得 到匹配，此时应将Am （即ai）从栈中退出，并

18、将输入流指针向 前移动一个位置。若Xm=ai=#，则表明输入串已经完全得到匹配，此时即可宣 告分析成功而结束分析。其它情形，转到错误处理程序。四、详细设计总体思路分析及流程图给定一个正规文法G，在LL（1）预测分析中，必须先求出First 集和Follow集，然后求出Select集，通过Select集判断是否是 LL1文法，如果是的话，构造预测分析表。求出预测分析表之后，再输入一个字符串，依据LL1分析表单步输出字符串的分析过程。功能模块分解图（1）主程序流程图(2)核心算法流程图1.计算非终结符的First集的算法及流程：First集合的构造算法：若 XeVT，贝U First (X) =X

19、。若XeVN，且有产生式Xa.，则把a加入到First(X)中；若Xs也是一条产生式，则把也加到First (X)中。若XY.是一个产生式且YEVN，则把First (Y) 中的所有非-元素都加到First (X)中；若XY1Y2.Yk是一个产生式，Y1,，Yi-1都是非终结符，而且，对于任何j, 1ji-1, First (Yj)都含有 (即 Y1.Yi-1* )，则把 First (Yj)中的所有非 - 元素都加到First (X)中；特别是，若所有的First (Yj)均含有， j=1,2,.，k，则把 加到 First (X)中。连续使用上面的规则，直至每个集合First不再增大为止。

20、2.计算非终结符的Follow集：Follow集合的具体构造算法如下:对于文法的开始符号，置#于Follow(S)中；若 AaB。是一个产生式，则把 First(p)|s)加至 Follow(B) 中；若A一aB是一个产生式，或A一aB。是一个产生式而 。s (即 GFirst(p),则把 Follow(A)加至 Follow(B)中。连续使用上面的规则，直至每个集合Follow不再增大为止。开始取得一个非终结符V查找产生式的右部含有V的产生式V是不是最后一个字符_N添加#到V的Follow集中V是不是最后一个字符_N添加#到V的Follow集中+- V后一个字符V*是1 _ 、否为终结符，L

21、*是否遍历完所有右*部含有V的产生式3.预测分析控制程序的算法流程2、测试数据i*i+i的语法树关键代码(1) 计算非终结符的First集：void first(edge ni,edge *n,int x)/ni 为一个产生式，n 为整 个文法( int i,j;for(j=0;jSUM;j+)( if(ni.getlf()=nj.getlf()(if(NODE.find(nj.getro()NODE.length()/非终结 符的情况( for(i=0;iSUM;i+)if(ni.getlf()=nj.getro() first(ni,n,x);else nx.newfirst(nj.get

22、ro();/终结符的情况 (2)计算非终结符的Follow集：void follow(edge ni,edge *n,int x) /计算 follow( int i,j,k,s;string str;for(i=0;ini.getrlen();i+)( s=NODE.find(ni.getrg()i);if(s-1) /是非终结符if(ini.getrlen()-1) /不在最右 for(j=0;jSUM;j+)if(nj.getlf().find(ni.getrg()i)=0)(if(NODE.find(ni.getrg()i+1)NODE.length()( for(k=0;kSUM;k

23、+)if(nk.getlf().find(ni.getrg()i+1)=0)(nj.newfollow(nk.getfirst();if(nk.getfirst().find(*)nk.getfirst().length() nj.newfollow(ni.getfollow();elsestr.erase();str+=ni.getrg()i+1;nj.newfollow(str);(3)输出预测分析表的主要代码：void outgraph(edge *n,string (*yc)50)( int i,j,k;bool flag;for(i=0;iENODE.length();i+)(if(

24、ENODEi!=*)( outfu(10,);coutENODEi;outfu(10,);cout#endl;int x;for(i=0;iNODE.length();i+)( outfu(4,);coutNODEi;outfu(5,);for(k=0;kENODE.length();k+)( flag=1;for(j=0;jSUM;j+)( if(NODEi=nj.getlf()0)( x=nj.getselect().find(ENODEk);if(x-1)( coutnj.getrg();ycik=nj.getrg();outfu(9-nj.getrlen(), );flag=0;/x=

25、nj.getselect().find(#);if(k=ENODE.length()-1&x-1)( coutnj.getrg();ycij=nj.getrg();if(flag&ENODEk!=*)outfu(11,);coutleftright;/非终结符 产生式右部 coutfilename;ifstream file(filename,ios:in);if(!file) cerrOpen filename error!endl;exit(1);while(!file.eof()/逐 行读入 for (int a=0;a=97 & c=65&c=48&c=2) string tp=;in

26、t q=0;for(int z=1;temp0z!=0;z+) if(temp0z= )continue;q+;tp=tp+temp0z;na.right=tp;na.rightq=0;if(m2) na.right=temp01;na.right1=0;file.close();问题二：将命令行中提示的输入几个产生式数量去除，现实自动统计的 产生式个数。具体实现就是单独使用几行代码就统计行数，实现 代码如下ifstream file1(filename,ios:in);if(!file1)cerrOpen filename error!leftright 来实现，没什么限制，但在文本读入文法

27、产生式时要对空格进行 处理，这样的必须要进行过滤，就要对字符的输入进行限制，设 置条件如下：if(c=97&c=65&c=48&c=57) else if(c=*)可以看出删除了空格的同时也去除了其它符号，只能输入大小写 字母，数字，及空代表符*，对其他如(、)、等无法处理。六、课程设计总结通过这次学课设，我发现有很多东西，很多细节没注意，如经 常漏；大小写问题等很小的问题，真正自己动手做了才发现了自己的 理论知识是如此的不扎实。有时候一个很小的问题卡一下就要处 理很久，细节方面会带来很大的问题等等。我深刻体会到这给我 带来的障碍。不过也因为通过这次的课程设计巩固了我的知识， 查漏补缺，巩固我

28、已有的知识，把那些遗忘掉的知识再重新学习 一遍，使我学到很多，得到很多。本课程设计的思路不难，但要不参考任何资料完全靠自己编确 有不小的难度。在编程之前，我参考了他人的一个程序，在吸收 其精华的基础上，自己做了些改进，最终将程序调出来了。在这次课程设计当中，我感觉自己学到了很多东西，同时也发 现了自己编程的不足之处。编程之前，我也参考了书中关于预测 分析方法的描述研读了书中的例子。通过这次课程设计，使我对LL(1)词法分析原理有了更透彻 的了解，通过将理论付诸实践的过程中，不但对课本知识有了更 深的理解，掌握，同时对编程能力也有很大的巩固，希望为自己 以后的学习打下基础，以便将来自己学得更好、

29、做得更好。七、参考文献MFC程序设计轻松入门欧阳志宏董霖钟俊华人民邮电出版社程序设计语言编译原理陈火旺等.国防工业出版社编译原理吕映芝张素琴蒋维杜主编清华大学出版社编译原理及编译程序构造高仲仪北京航天航空大学出版社八、附录核心算法(词法分析程序)的代码public static void analyse(String Vn, String Vt, String M) /句型分析函数( int i, m, p, q, len, t, step, j; /，记录栈顶指针位 置(s),记录产生式右部的长度(len),记录分析步骤数(step)String a, A; / a用于记录剩余输入串的第一个元素，A记录分 析栈的栈顶元素String str =