LL(1)文法分析资料报告

《LL(1)文法分析资料报告》由会员分享，可在线阅读，更多相关《LL(1)文法分析资料报告（20页珍藏版）》请在装配图网上搜索。

1、word编译原理课程设计报告选题名称:LL(1)语法分析 系（院）:计算机工程系专 业:计算机科学与技术学年学期: 2010 2011学年 第 1 学期2010年 12月 30 日设计任务书课题名称LL(1)语法分析设计目的LL(1)分析法的基本思想是：自顶向下分析时从左向右扫描输入串，分析过程中将采用最左推导，并且只需向右看一个符号就可决定如何推导。通过对给定的文法构造预测分析表和实现某个符号串的分析，掌握LL(1)分析法的基本思想和实现过程。实验环境1. 微型电子计算机（PC）任务要求1.录入合法的LL(1)文法工作进度计划序号起止日期工 作 容1选定题目，明确题目要求2课题深入调研、细化

2、工作，系统方案设计3程序录入、调试、整合4上机演示，课程设计分组答辩，完成课程设计报告指导教师（签章）：年月日 摘要：语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定的文法的正确句子。目前语法分析常用的方法右自顶向下分析和自底向上分析两大类。确定的自顶向下方法，是从文法的开始符号，考虑如何根据当前的输入符号（单词）唯一的确定选用哪个产生式替换相应非终结符往下推导。 LL(1)文法是一种确定的自顶向下的分析方法。LL(1)分析法的功能是利用LL(1)控制程序根据显示栈顶容、向前看符号以及LL(1)分析表，对输入符号串自上而下的分析过程。可通过消除左递归、提

3、取左因子把非LL(1)文法改造成LL(1)文法。当文法满足条件后，分别构造出文法的每个非终结符的FIRST、FOLLOW集合和SELECT集，根据SELECT集合判断是否是LL(1)文法。在LL(1)预测分析程序设计过程中，最重要的两个问题是预测分析表的构造和相关数据结构的设计。而预测分析表的构造首先必须计算文法每个非终结符的FIRST集和FOLLOW集。要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下

4、的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。关键词：语法分析；LL(1)分析；FIRST集合；FOLLOW集合；自上而下分析目录1 课题综述11112 系统分析11LL(1)文法.1确定的自顶向下分析思想.2.2.1.3 左递归的消除.32.1.4消除回溯、提左因子42.1.5 计算FIRST集合、FOLLOW集合和SELECT集合.42.2 解决问题的基本思路.52.3 功能模块框图.53系统设计5 LL(1)文法输入设计6 LL(1)语法分析详细流程图6算法描述73.3.1 消

5、除左递归的算法.7.84 代码编写.94.1 相关代码.912总结14致15参考文献1616 / 201 课题综述编译原理的设计一般都是从文法和语言的基础知识开始，沿着词法分析、语法分析、语义分析、语法翻译、中间代码生成及符号表组织序列进行。本课题的总体设计完全依据编译原理的教学容，即上下文无关文法基础及词法分析、语法分析技术研究、语法推导的语义翻译、代码优化及目标代码生成。但是在本课题中只涉及到了关于文法分析的相关知识。课题来源和意义LL（1）文法是一种简单易行的，自顶向下的，且较易实现的文法。它的原理在编译原理的书上已有详细叙述，本文着重于介绍其实现过程中的一些细节及思考。LL(1)表明自

6、顶向下分析技术是从左向右扫描输入串，分析过程中将用最左推导，以及只需向右看一个符号便可决定如何推导的一种文法。首先必须判断所给文法是否是LL(1)文法，然后编写构造LL(1)语法分析程序。因而对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。设计中实现语法分析使用的语言是C+，使程序能达到上述目标。熟练掌握运用VC+建立工程，并用VC+语言进行程序编写，掌握编程思想和算法。熟练掌握LL(1) 文法的分析方法，利用FIRST集合、FOLLOW集合以及SELECT集合得到预测分析表，并且各集合的计算方法也是设计的目标。问题(1)对于一个输入文法，消除文法

7、的左递归；(2)理解计算FIRST、FOLLOW集合和SELECT集合的方法；(3)理解文法分析表的构造。2 系统分析2.1.1 LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。一个用来描述语言语法结构的文法G2可形式地定义如下：一个文法GS可表示成形如(VN，VT，P，S)的四元式。其中VN，VT，P均为非空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说：VN，一系列需要定义的语法畴。VT，若干基本符号，不需要进一步定义。P，用“-“连接起来的有序对(A,)的集合，称为规则，也叫产生式。其中A是一个非终结符，是一个由终结符或非终结符组成的符号串，即(VNV

8、T)*。S， 是文法的开始符号。SVN此外 ，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。显然：V=VNVT；VNVT =。更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A时，并不考虑A所处的环境，即与A的上下文无关。除非另做说明，我们以后所说的文法均指上下文无关文法。LL(1)的含义：l 第一个L表示从左至右扫描输入符号串l 第二个L表示生成输入串的一个最左推导l 1表示在决定分析程序的每步动作时，向前看一个符号LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号

9、(单词符号)惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。若有文法：S-cAdA-ab|a输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图2.1所示：ScAdScAdSabScAda(a)(b)(c)最左边的叶子标记为c，匹配W的第一个符号。于是，推进输入指针到W的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d，把它和下一个标记为b的叶子比较。

10、因为b和d不匹配，报告失败，回到A，看它是否还有别的选择尚未尝试。在回到A时，必须重置指针于第二个符号，即第一次进入A的位置。现在尝试A的第二个选择，得到图(c)的分析树。叶子a匹配W的第二个符号，叶子d匹配W的第三个符号。这样，产生了W的分析树，从而宣告分析完全成功。2.1.3 左递归的消除直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为P-Pa|b其中，P是开头。那么我们可以把P的规则改写为如下的非直接左递归形式：P-bRR-aR| (为空字)这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。一般而言，假定P关于的全部产生式是P-P1|P2|Pm|1| 2|

11、n其中，每个i(1im)都不等于，1n都不以P开头，那么消除P的直接左递归就是把这些规则改写成：P-1R| 2R| nR R-1R|2R|mR|使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。对于间接左递归的消除需先通过产生式非终结符置换，把间接左递归变成直接左递归。例如有文法：S-A| (1) A-S(2)因为S=A=S，所以S是一个间接递归的非终结符。为了消除这种间接左递归将(2)式代人(1)式，即可得到与原方法等价的方法: S-S| (3)(3)式是直接左递归的，可以采用消除直接左递归的方法对文法进行改写，可的文法：S-S S-S|由此

12、可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然后对以这些非终结符为左部的产生式，通过逐步置换有关产生式的方法将它们化为直接左递归的产生式。最后在消除其中的全部直接左递归。2.1.4消除回溯、提左因子 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假定现在轮到非终结符A去执行匹配任务，A共有n个侯选1，2，n,即A-1|2|n。A能够根

13、据不同的输入符号指派相应的i作为全权代表去执行任务，那就肯定无需回溯了。在这里A已不再是让某个侯选去试探地执行任务，而是根据所面临的输入符号准确地指派唯一的一个侯选。其次，被指派侯选的工作成败也完全代表了A。2.1.5 计算FIRST集合、FOLLOW集合和SELECT集合FIRST集合：令GS=(VT,VN,S,P),则 FIRST(a)= a | a * ab,aVT ,a、bV*、若a* ，则FIRST(a)对每以文法符号X，计算FIRST(X)过程如下： (a)若XVT ,则FIRST(X)=X；(b)若XVN,且有产生式Xa,aVT,则把a加入到FIRST(X)中；(c)若XVN ,

14、若Xe也是一条产生式,则把e也加到FIRST(X)中；(d)若XVN,有产生式XY1Y2Yn,Y1,Yi都是非终结符，对于任何j，1ji-1，FIRST(Yj)都含有，则把FIRST(Yj)中的所有非元素都加到FIRST(X)中； FIRST(Yi)的元素加入到FIRST(X)特别地，若所有的FIRST(Yj , j=1,2,n)均含有e,则把e ,FIRST(Yj)中的所有非元素都加到FRIST(X)中。FOLLOW集合：设GS=(VT,VN,S,P)是上下文无关文法, (a)设S为开始符号,则#FOLLOW(S)(b)若有产生式AaBb，b *则FIRST(b)FOLLOW(B)(C)若b

15、(可理解为AaB)则FIRST(b)-FOLLOW(A) FOLLOW(B)SELECT集合：Aa的可选集SELECTa，则SELECT(Aa)=FIRST(a)a，则SELECT(Aa)=(FIRST(a)-) FOLLOW(A)2.2 解决问题的基本思路首先根据一定的规则输入一个合法的文法，化简成LL(1)文法，利用一定的算法消除文法中的左递归，然后再利用首先预定的规则计算出FIRST和FOLLOW集合，以及算出SELECT集合，然后就是显示出LL(1)文法的分析表。最后一步是输入一串字符串，然后对字符串进行分析，输出分析过程表，这样系统就成形了。2.3 功能模块框图初始数据产生式处理计算

16、机FOLLOW集合显示预测分析表图2.3 功能模块框图输入文法3 系统设计语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何

17、输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。3.1 LL(1)文法输入设计标准的文法有一定的规则，若在设计过程中，输入的文法不正确，则不能正确的实现程序功能，所以首先在编写程序时，要对输入文法进行限制，规则如下：(1) 大写英文字母表示非终结符，所以产生式左部一定要输入大写字母；(2) e表示空产生式；(3) 除大写字母、#、| 外的单字符表示终结符，所以产生右部不能包括以上几个字符；(4) 不能出现递归文法。(如 S-S或

18、S-A, A-S;)；(5) 不能出现多余文法规则。(如 S-A，A不是非终结符)； (6) 文法产生式长度不超过10个字符。3.2 LL(1)语法分析详细流程图我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，其结构图如图3.2。开始操作

19、读源程序字符常数分析程序关键字标识符分析程序其它单词分析程序输出单词内部表示开始结束是字母?有字符?是数字?YYYNNN图3.2 LL(1)语法分析详细流图3.3.1 消除左递归的算法(1)把文法G的所有非终结符按任一种顺序排列成P1，P2,Pn;按此顺序执行； (2)FOR i:=1 TO n DOBEGIN FOR j:=1 TO i-1 DO把形如Pi-Pj产生式变为Pj-1|2|k关于Pj的所有规则消除关于Pi规则的直接左递归性 END(3)化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。整个程序可分为如下几步：(1) 读入文法；(2) 判断正误；(

20、3) 若无误，判断是否为LL(1)文法；(4) 若是，构造分析表；(5) 由总控算法判断输入符号串是否为该文法的句型。4 代码编写/* 分解含有左递归的产生式*/void recur(char *point)/*完整的产生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c();/*得到一个非终结符*/k=strlen(non_ter); /*非终结符号长度*/non_terk=ch;/得到最后一个非终结符号non_terk+1=0;for(j=0;j=strlen(point)-1;j+)if(pointn=point0) /*如果|后的首符号和左部相

21、同，含直接左递归*/for(j=n+1;j=strlen(point)-1;j+)while(pointj!=|&pointj!=0) tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(pointj=|)n=j+1;break;else /*如果|后的首符号和左部不同*/leftcount=ch;rightcount0=;rightcount1=0;count+;for(j=n;j=strlen(point)-1;j+) if(pointj!=|)

22、 tempm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1=0;printf( count=%d ,count);m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch;rightcountm+1=0;count+; m=0;/* 分解不含有左递归的产生式*/void non_re(char *point) int m=0,j;char temp20;for(j=3;j=0;

23、n-) Sp+=rightmn; Sq+strlen(rightm)=0; printf(符号栈:%s 剩余字符串:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf( n);总结收获：通过本次课程设计，我收获了很多东西。首先对编译原理这门课有了进一步的深刻理解，对LL（1）文法分析的原理和过程有了进一步的巩固，也锻炼了我编程的能力，巩固了平时所学的知识，真正做到了学以致用。体会：在做课程设计的过程中，发现自己在编写程序过程中，总是会忽略各种细节，从而导致经常修改一些很小的低级错误才能使程序正常运行，不仅浪费时间，还影响对其他地方的修改，

24、深刻体会到了自己在编程方面与别人的差距，在今后的学习中，我会注意改正自己在这方面的缺点，促使自己的编程水平不短进步。编译原理是一门专业学科，对于现阶段的我来说，只能掌握它的一些基本原理和概念，对于一些更深层的知识还是有很多难以理解的地方。但在这次课程设计过程中，是我对编译原理有了更深的理解，同时也锻炼了自己的思考能力，提高了自己的团体合作意识，锻炼了自己的动手编程能力，对于将知识的转化有了很大的帮助。总之，在这次课程设计过程中，我学到了很多东西，在很多方面都得到了提高。致这次的编译原理课程设计能顺利完成，与很多方面有着密切的关系。首先，要感学校,学校为我们学生提供了免费的机房 ,让我们能顺利地

25、进行实习。然后，我要感指导老师，他们为我们解决课程设计过程中出现的各种问题。当然，我还要帮助过我的同学。在这次的课程设计中，我的同学给了我很多帮助，他们让我了解怎样去做好一个完整的程序。他们是我最好的学习对象，从他们那里，我能学习到很多东西。在实习过程中，我在同学和指导老师那里得到了很多的帮助，是他们让我感受到互相学习是一件很开心的事，你可以在发现自己优点的同时，找到自己的不足。比如，在程序运行出错的时候，发现自己耐心不足，很容易情绪化。而同学们的耐心教导使我对自己有了重新的认识，心中不时地提醒自己，向他们学习、靠齐。参 考 文 献1 编译原理 素琴 吕映芝等 著 清华大学 2004年2Visual C+实战演练王宏 玉东 罡 人民邮电 2003年3月3编译原理实践教程胡元义等 电子科技大学 2005年7月4胡伦骏.编译原理.：电子工业，20025 高仲仪.编译原理及编译程序构造.：航空航天大学，19906 编译原理，火旺、春林等编著，国防工业7 涛.C+:面向对象程序设计.:高等教育,20068 慧南数据结构C+语言描述：人民邮电，200503