LL(1)文法分析

编译原理课程设计报告编译原理课程设计报告 选题名称选题名称: LL(1)语法分析 系（院）系（院）: 计 算 机 工 程 系 专专 业业: 计算机科学与技术 学年学期学年学期: 2010 2011 学年 第 1 学期 2010年 12 月 30 日 设计任务书设计任务书 课题课题 名称名称 LL(1)语法分析 设计设计 目的目的 LL(1)分析法的基本思想是：自顶向下分析时从左向右扫描输入串，分析 过程中将采用最左推导，并且只需向右看一个符号就可决定如何推导。通过 对给定的文法构造预测分析表和实现某个符号串的分析，掌握 LL(1)分析法 的基本思想和实现过程。 实验实验 环境环境 1. 微型电子计算机（PC） 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上机演示，课程设计分组答辩，完成课程设计报告 指导教师（签章）：指导教师（签章）： 年年 月月 日日 摘要： 语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词 符号序列是否是给定的文法的正确句子。目前语法分析常用的方法右自顶向下分析和 自底向上分析两大类。确定的自顶向下方法，是从文法的开始符号，考虑如何根据当 前的输入符号（单词）唯一的确定选用哪个产生式替换相应非终结符往下推导。 LL(1)文法是一种确定的自顶向下的分析方法。LL(1)分析法的功能是利用 LL(1)控制 程序根据显示栈顶内容、向前看符号以及 LL(1)分析表，对输入符号串自上而下的分 析过程。可通过消除左递归、提取左因子把非 LL(1)文法改造成 LL(1)文法。当文法 满足条件后，分别构造出文法的每个非终结符的 FIRST、FOLLOW 集合和 SELECT 集， 根据 SELECT 集合判断是否是 LL(1)文法。在 LL(1)预测分析程序设计过程中，最重要 的两个问题是预测分析表的构造和相关数据结构的设计。而预测分析表的构造首先必 须计算文法每个非终结符的 FIRST 集和 FOLLOW 集。要知道一串符号是不是该文法的 一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以 分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是， 对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串 建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种 试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。 关键词：语法分析；LL(1)分析；FIRST 集合；FOLLOW 集合；自上而下分析 目录目录 1 课题综述.1 1.1 课题来源和意义.1 1.2 预期目标.1 1.3 解决问题.1 2 系统分析.1 2.1 涉及的知识基础.1 2.1.1 LL(1)文法.1 2.1.2 确定的自顶向下分析思想.2. 2.1.3 左递归的消除.3 2.1.4 消除回溯、提左因子4 2.1.5 计算FIRST集合、FOLLOW集合和SELECT集合.4 2.2 解决问题的基本思路.5 2.3 功能模块框图.5 3 系统设计.5 3.1 LL(1)文法输入设计 .6 3.2 LL(1)语法分析详细流程图 .6 3.3 算法描述7 3.3.1 消除左递归的算法.7 3.4 系统流程 图.8 4 代码编写.9 4.1 相关代码.9 4.4 运行结果.12 总 结.14 致 谢.15 参 考 文 献.16 1 课题综述课题综述 编译原理的设计一般都是从文法和语言的基础知识开始，沿着词法分析、语法分 析、语义分析、语法翻译、中间代码生成及符号表组织序列进行。本课题的总体设计 完全依据编译原理的教学内容，即上下文无关文法基础及词法分析、语法分析技术研 究、语法推导的语义翻译、代码优化及目标代码生成。但是在本课题中只涉及到了关 于文法分析的相关知识。 1.1 课题来源课题来源和意义和意义 LL（1）文法是一种简单易行的，自顶向下的，且较易实现的文法。它的原理在 编译原理的书上已有详细叙述，本文着重于介绍其实现过程中的一些细节及思考。 LL(1)表明自顶向下分析技术是从左向右扫描输入串，分析过程中将用最左推导， 以及只需向右看一个符号便可决定如何推导的一种文法。首先必须判断所给文法是否 是 LL(1)文法，然后编写构造 LL(1)语法分析程序。因而对任给文法需计算 FIRST、FOLLOW、SELECT 集合，进而判别文法是否为 LL(1)文法。设计中实现语 法分析使用的语言是 C+，使程序能达到上述目标。 1.2 预期目标预期目标 熟练掌握运用 VC+建立工程，并用 VC+语言进行程序编写，掌握编程思想和算 法。熟练掌握 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)的四元式。其中VN，VT，P均为非 空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说： VN，一系列需要定义的语法范畴。 VT，若干基本符号，不需要进一步定义。 P，用“-“连接起来的有序对(A,)的集合，称为规则，也叫产生式。其中A是一 个非终结符，是一个由终结符或非终结符组成的符号串，即(VNVT)*。 S， 是文法的开始符号。SVN 此外 ，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。 显然：V=VNVT；VNVT =。 更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A 时，并不考虑A所处的环境，即与A的上下文无关。除非另做说明，我们以后所说的 文法均指上下文无关文法。 LL(1)的含义： 第一个 L 表示从左至右扫描输入符号串 第二个 L 表示生成输入串的一个最左推导 1 表示在决定分析程序的每步动作时，向前看一个符号 2.1.2 确定的自顶向下分析思想 LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法 的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号(单词符号) 惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试 探过程，是反复使用不同产生式匹配输入符号串的过程。 若有文法：S-cAd A-ab|a 输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W 的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图2.1所示： S cAd S cAd S ab S cAd a (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的分析树，从而宣告分析完全成功。 2.1.3 左递归的消除 直接消除产生式中的左递归是比较容易的。假定关于非终结符P的规则为P-Pa|b 其中，P是开头。那么我们可以把P的规则改写为如下的非直接左递归形式：P-bR R-aR| (为空字) 这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。 一般而言，假定P关于的全部产生式是P-P1|P2|Pm|1| 2|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| 由此可见，为了消除间接左递归，可首先查出那些具有左递归的非终结符号，然 后对以这些非终结符为左部的产生式，通过逐步置换有关产生式的方法将它们化为直 接左递归的产生式。最后在消除其中的全部直接左递归。 2.1.4 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能 够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且次侯选的工作 结果是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配不会是虚假 的；若此侯选无法完成任务，则任何其它侯选也肯定也无法完成任务。换句话说，假 定现在轮到非终结符 A 去执行匹配任务，A 共有 n 个侯选 1，2，n,即 A- 1|2|n。A 能够根据不同的输入符号指派相应的 i 作为全权代表去执行 任务，那就肯定无需回溯了。在这里 A 已不再是让某个侯选去试探地执行任务，而是 根据所面临的输入符号 准确地指派唯一的一个侯选。其次，被指派侯选的工作成 败也完全代表了 A。 2.1.52.1.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)都含有，则把FIRST(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)=(FIRST()-) FOLLOW(A) 2.22.2 解决问题的基本思路解决问题的基本思路 首先根据一定的规则输入一个合法的文法，化简成LL(1)文法，利用一定的算法消 除文法中的左递归，然后再利用首先预定的规则计算出FIRST和FOLLOW集合，以及 算出SELECT集合，然后就是显示出LL(1)文法的分析表。最后一步是输入一串字符串， 然后对字符串进行分析，输出分析过程表，这样系统就成形了。 2.32.3 功能模块框图功能模块框图 初始数据 产生式处理 计算机 FOLLOW 集合 显示预测分析表 图 2.3 功能模块框图 输入文法 3 系统设计系统设计 语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础 上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无 关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号 串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的 一个句子，这是这个课程设计所要解决的一个问题。 其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符 号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类 是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法， 从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找 一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹 配输入串的过程我主要是自上而下的过程。 3.13.1 LL(1)LL(1)文法输入设计文法输入设计 标准的文法有一定的规则，若在设计过程中，输入的文法不正确，则不能正确的 实现程序功能，所以首先在编写程序时，要对输入文法进行限制，规则如下： (1) 大写英文字母表示非终结符，所以产生式左部一定要输入大写字母； (2) e表示空产生式； (3) 除大写字母、#、| 外的单字符表示终结符，所以产生右部不能包括以上 几个字符； (4) 不能出现递归文法。(如 S-S或S-A, A-S;)； (5) 不能出现多余文法规则。(如 S-A，A不是非终结符)； (6) 文法产生式长度不超过10个字符。 3.2.2 LL(1)LL(1)语法分析详细流程图语法分析详细流程图 我们知道一个文法要能进行 LL（1）分析，那么这个文法应该满足：无二义性， 无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的 FIRST 和 FOLLOW 集合，然后根据 FIRST 和 FOLLOW 集合构造 LL（1）分析表，最后利 用分析表，根据 LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个 部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样 的方法进行语法分析，其结构图如图 3.2。 开始操作 读源程序字符 常数分 析程序 关键字标识 符分析程序 其它单词 分析程序 输出单词内部表示 开始 结束 是字母? 有字符? 是数字? Y Y Y N N N 图 3.2 LL(1)语法分析详细流图 3.3 算法描述算法描述 3.3.1 消除左递归的算法 (1) 把文法G的所有非终结符按任一种顺序排列成P1，P2,Pn;按此顺序执行； (2) FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi-Pj产生式变为Pj-1|2|k关于Pj的所有规则 消除关于Pi规则的直接左递归性 END (3) 化简由(2)所得的文法。即去除那些从开始符号出发永远也无法到达的非终结 符的产生规则。 3.4 系统流程图系统流程图 整个程序可分为如下几步： (1) 读入文法； (2) 判断正误； (3) 若无误，判断是否为 LL(1)文法； (4) 若是，构造分析表； (5) 由总控算法判断输入符号串是否为该文法的句型。 开始 读入文法 文法有效？ 是LL1文法？ 生成构造分析表报错 判断句型 接受判断字符 Choose=y? 结束 y n y y n n 开始 得到一非终结 符ch K=strlen(non_ter) 有左递归？ Temp=产生式右部( 除首符) 读取文法 rightcount=temp rightcountm+1=ch; Temp=产生式右部 rightcount=temp Leftcount=原左部 Count + 结束 不含左递归的拆分 n y 图 3.4.1 程序主流程图 图 3.4.2 消除左递归流程图 4 代码编写代码编写 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(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(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;n-) Sp+=rightmn; Sq+strlen(rightm)=0; printf(符号栈:%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）文法分析的原理和过程有了进一步的巩固，也锻炼了我编 程的能力，巩固了平时所学的知识，真正做到了学以致用。 体会：在做课程设计的过程中，发现自己在编写程序过程中，总是会忽略各种细 节，从而导致经常修改一些