LL(1)文法分析参考模板

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

2、Windows XP 操作系统，Visual C+6.0 开发工具任务任务要求要求1. 录入合法的 LL(1)文法2. 构造并输出预测分析表3. 对输入的符号串进行语法分析工作进度计划工作进度计划序号序号起止日期起止日期工工 作作 内内 容容110.12.27-10.12.27选定题目，明确题目要求210.12.28-10.12.28课题深入调研、细化工作，系统方案设计310.12.29-10.12.29程序录入、调试、整合410.12.30-10.12.31上机演示，课程设计分组答辩，完成课程设计报告指导教师（签章）：指导教师（签章）： 年年 月月 日日 摘要： 语法分析是编译程序的核心部分

3、。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定的文法的正确句子。目前语法分析常用的方法右自顶向下分析和自底向上分析两大类。确定的自顶向下方法，是从文法的开始符号，考虑如何根据当前的输入符号（单词）唯一的确定选用哪个产生式替换相应非终结符往下推导。 LL(1)文法是一种确定的自顶向下的分析方法。LL(1)分析法的功能是利用 LL(1)控制程序根据显示栈顶内容、向前看符号以及 LL(1)分析表，对输入符号串自上而下的分析过程。可通过消除左递归、提取左因子把非 LL(1)文法改造成 LL(1)文法。当文法满足条件后，分别构造出文法的每个非终结符的 FIRST、FOLLOW 集合和 SE

4、LECT 集，根据 SELECT 集合判断是否是 LL(1)文法。在 LL(1)预测分析程序设计过程中，最重要的两个问题是预测分析表的构造和相关数据结构的设计。而预测分析表的构造首先必须计算文法每个非终结符的 FIRST 集和 FOLLOW 集。要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生

5、式谋求匹配输入串的过程我主要是自上而下的过程。关键词：语法分析；LL(1)分析；FIRST 集合；FOLLOW 集合；自上而下分析 目录目录1 课题综述课题综述.11.1 课题来源和意义.11.2 预期目标.11.3 解决问题.12 系统分析系统分析.12.1 涉及的知识基础.12.1.1 LL(1)文法.12.1.2 确定的自顶向下分析思想.2.2.1.3 左递归的消除.32.1.4 消除回溯、提左因子42.1.5 计算FIRST集合、FOLLOW集合和SELECT集合.42.2 解决问题的基本思路.52.3 功能模块框图.53 系统设计系统设计.53.1 LL(1)文法输入设计.63.2

6、LL(1)语法分析详细流程图.63.3 算法描述73.3.1 消除左递归的算法.73.4 系统流程图.84 代码编写.9 4.1 相关代码.94.4 运行结果.12总总 结结 .14致致 谢谢 .15参参 考考 文文 献献.161 课题综述课题综述编译原理的设计一般都是从文法和语言的基础知识开始，沿着词法分析、语法分析、语义分析、语法翻译、中间代码生成及符号表组织序列进行。本课题的总体设计完全依据编译原理的教学内容，即上下文无关文法基础及词法分析、语法分析技术研究、语法推导的语义翻译、代码优化及目标代码生成。但是在本课题中只涉及到了关于文法分析的相关知识。1.1 课题来源课题来源和意义和意义L

7、L（1）文法是一种简单易行的，自顶向下的，且较易实现的文法。它的原理在编译原理的书上已有详细叙述，本文着重于介绍其实现过程中的一些细节及思考。LL(1)表明自顶向下分析技术是从左向右扫描输入串，分析过程中将用最左推导，以及只需向右看一个符号便可决定如何推导的一种文法。首先必须判断所给文法是否是 LL(1)文法，然后编写构造 LL(1)语法分析程序。因而对任给文法需计算FIRST、FOLLOW、SELECT 集合，进而判别文法是否为 LL(1)文法。设计中实现语法分析使用的语言是 C+，使程序能达到上述目标。1.2 预期目标预期目标熟练掌握运用 VC+建立工程，并用 VC+语言进行程序编写，掌握

8、编程思想和算法。熟练掌握 LL(1) 文法的分析方法，利用 FIRST 集合、FOLLOW 集合以及SELECT 集合得到预测分析表，并且各集合的计算方法也是设计的目标。1.3 解决解决问题问题(1)对于一个输入文法，消除文法的左递归；(2)理解计算 FIRST、FOLLOW 集合和 SELECT 集合的方法；(3)理解文法分析表的构造。2 2 系统分析系统分析 2.1 涉及的知识基础涉及的知识基础2.1.1 LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。一个用来描述语言语法结构的文法G2可形式地定义如下：一个文法GS可表示成形如(VN，VT，P，S)的四元式。其中V

9、N，VT，P均为非空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说：VN，一系列需要定义的语法范畴。VT，若干基本符号，不需要进一步定义。P，用“-“连接起来的有序对(A,)的集合，称为规则，也叫产生式。其中A是一个非终结符，是一个由终结符或非终结符组成的符号串，即(VNVT)*。S， 是文法的开始符号。SVN此外 ，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。显然：V=VNVT；VNVT =。更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A时，并不考虑A所处的环境，即与A的上下文无关。除非另做说明，我们以后所说的文法均指上下文无关文法。

10、LL(1)的含义：第一个 L 表示从左至右扫描输入符号串第二个 L 表示生成输入串的一个最左推导1 表示在决定分析程序的每步动作时，向前看一个符号2.1.2 确定的自顶向下分析思想LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号(单词符号)惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。若有文法：S-cAdA-ab|a输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W的第一个符号c。然后用S的第一个产生式

11、来扩展该树，得到的树如图2.1所示：ScAdScAdSabScAda(a)(b)(c)图2.1.1语法分析树最左边的叶子标记为c，匹配W的第一个符号。于是，推进输入指针到W的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d，把它和下一个标记为b的叶子比较。因为b和d不匹配，报告失败，回到A，看它是否还有别的选择尚未尝试。在回到A时，必须重置指针于第二个符号，即第一次进入A的位置。现在尝试A的第二个选择，得到图(c)的分析树。叶子a匹配W的第二个符号，叶子d匹配W的第三个符号。这样，产生了W的分析树，从而宣告分析

12、完全成功。2.1.3 左递归的消除直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为P-Pa|b其中，P是开头。那么我们可以把P的规则改写为如下的非直接左递归形式：P-bRR-aR| (为空字)这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。一般而言，假定P关于的全部产生式是P-P1|P2|Pm|1| 2|n其中，每个i(1im)都不等于，1n都不以P开头，那么消除P的直接左递归就是把这些规则改写成： P-1R| 2R| nR R-1R|2R|mR|使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。对于间接左递归

13、的消除需先通过产生式非终结符置换，把间接左递归变成直接左递归。例如有文法：S-A| (1) A-S (2)因为S=A=S，所以S是一个间接递归的非终结符。为了消除这种间接左递归将(2)式代人(1)式，即可得到与原方法等价的方法: S-S| (3)(3)式是直接左递归的，可以采用消除直接左递归的方法对文法进行改写，可的文法：S-S S-S|由此可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然后对以这些非终结符为左部的产生式，通过逐步置换有关产生式的方法将它们化为直接左递归的产生式。最后在消除其中的全部直接左递归。2.1.4 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任

14、何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假定现在轮到非终结符 A 去执行匹配任务，A 共有 n 个侯选 1，2，n,即 A-1|2|n。A 能够根据不同的输入符号指派相应的 i 作为全权代表去执行任务，那就肯定无需回溯了。在这里 A 已不再是让某个侯选去试探地执行任务，而是根据所面临的输入符号 准确地指派唯一的一个侯选。其次，被指派侯选的工作成败也完全代表了 A。2.1.52.1.

15、5 计算计算FIRSTFIRST集合、集合、FOLLOWFOLLOW集合和集合和SELECTSELECT集合集合FIRST集合：令GS=(VT,VN,S,P),则 FIRST()= a | * a,aVT ,、V*、若 * ，则FIRST()对每以文法符号X，计算FIRST(X)过程如下： (a)若XVT ,则FIRST(X)=X；(b)若XVN,且有产生式Xa,aVT,则把a加入到FIRST(X)中；(c)若XVN ,若X也是一条产生式,则把也加到FIRST(X)中；(d)若XVN,有产生式XY1Y2Yn,Y1,Yi都是非终结符，对于任何j，1ji-1，FIRST(Yj)都含有，则把FIRS

16、T(Yj)中的所有非元素都加到FIRST(X)中； FIRST(Yi)的元素加入到FIRST(X)特别地，若所有的FIRST(Yj , j=1,2,n)均含有,则把 ,FIRST(Yj)中的所有非元素都加到FRIST(X)中。FOLLOW集合：设GS=(VT,VN,S,P)是上下文无关文法, (a)设S为开始符号,则#FOLLOW(S)(b)若有产生式A B， * 则FIRST()FOLLOW(B)(C)若 (可理解为A B)则FIRST()-FOLLOW(A) FOLLOW(B)SELECT集合：A 的可选集SELECT ，则SELECT(A)=FIRST()，则SELECT(A)=(FIR

17、ST()-) FOLLOW(A)2.22.2 解决问题的基本思路解决问题的基本思路首先根据一定的规则输入一个合法的文法，化简成LL(1)文法，利用一定的算法消除文法中的左递归，然后再利用首先预定的规则计算出FIRST和FOLLOW集合，以及算出SELECT集合，然后就是显示出LL(1)文法的分析表。最后一步是输入一串字符串，然后对字符串进行分析，输出分析过程表，这样系统就成形了。2.32.3 功能模块框图功能模块框图初始数据产生式处理计算机 FOLLOW 集合显示预测分析表图 2.3 功能模块框图输入文法3 系统设计系统设计语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础

18、上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试

19、探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。3.13.1 LL(1)LL(1)文法输入设计文法输入设计标准的文法有一定的规则，若在设计过程中，输入的文法不正确，则不能正确的实现程序功能，所以首先在编写程序时，要对输入文法进行限制，规则如下：(1) 大写英文字母表示非终结符，所以产生式左部一定要输入大写字母；(2) e表示空产生式；(3) 除大写字母、#、| 外的单字符表示终结符，所以产生右部不能包括以上几个字符；(4) 不能出现递归文法。(如 S-S或S-A, A-S;)；(5) 不能出现多余文法规则。(如 S-A，A不是非终结符)； (6) 文法产生式长度不超过1

20、0个字符。3.2.2 LL(1)LL(1)语法分析详细流程图语法分析详细流程图我们知道一个文法要能进行 LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的 FIRST和 FOLLOW 集合，然后根据 FIRST 和 FOLLOW 集合构造 LL（1）分析表，最后利用分析表，根据 LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，其结构图如图 3.2。开始操作读源程序字符常数分析程序关键字标识符分析程序其它单词分析程序输

21、出单词内部表示开始结束是字母?有字符?是数字?YYYNNN图 3.2 LL(1)语法分析详细流图3.3 算法描述算法描述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)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结符的产生规则。3.4 系统流程图系统流程图整个程序可分为如下几步：(1) 读入文法；(2) 判断正误；(

22、3) 若无误，判断是否为 LL(1)文法；(4) 若是，构造分析表；(5) 由总控算法判断输入符号串是否为该文法的句型。 开始 读入文法 文法有效？是LL1文法？生成构造分析表报错判断句型接受判断字符Choose=y?结束ynyynn开始得到一非终结符chK=strlen(non_ter)有左递归？Temp=产生式右部(除首符)读取文法rightcount=temprightcountm+1=ch;Temp=产生式右部rightcount=tempLeftcount=原左部Count +结束不含左递归的拆分ny 图 3.4.1 程序主流程图 图 3.4.2 消除左递归流程图4 代码编写代码编写

23、4.1 相关代码相关代码/* 分解含有左递归的产生式*/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) /*如果|后的首符号和左部相同，含直接左递归*/for(j=n+1;j=strlen(point)-1;j+) while(poin

24、tj!=|&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!=|) tempm+=pointj; else leftcount=point0; memcpy(r

25、ightcount,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;n-) Sp+=rightmn; Sq+strlen(rightm)=0; printf(符

26、号栈:%s 剩余字符串:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf( n);4.2 运行结果运行结果编译调试，运行程序。输入文法，如图 4.2.1，按回车键得到分析结果，如图4.2.2，判断其是否为 LL(1)文法，并得到该文法的分析表；输入该文法的句型，回车得到句型的预测分析过程，如图 4.2.3，再次输入不是该文法的句型，如图 4.2.4图 4.2.1图 4.2.2图 4.2.3图 4.2.4 总总结结收获：通过本次课程设计，我收获了很多东西。首先对编译原理这门课有了进一步的深刻理解，对 LL（1）文法分析的原理和过程有了进一步的巩固，也锻炼了我编程的能力，巩固了平时所学的知识，真正做到了学以致用。体会：在做课程设计的过程中，发现自己在编写程序过程中，总是会忽略各种细节，从而导致经常修改一些很小的低级错