LL(1)文法分析

编译原理课程设计报告选题名称:LL(1)语法分析系（院）:计算机工程系专业:计算机科学与技术学年学期:2010~2011学年第1学期2010年12月30日设计任务书课题名称LL(1)语法分析设计目的LL(1)分析法的基本思想是：自顶向下分析时从左向右扫描输入串，分析过程中将采用最左推导，并且只需向右看一个符号就可决定如何推导。通过对给定的文法构造预测分析表和实现某个符号串的分析，掌握LL(1)分析法的基本思想和实现过程。实验环境1.微型电子计算机（PC）2.WindowsXP操作系统，VisualC++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课题综述.......................................................................................................................................................11.1课题来源和意义.......................................................................................................................................11.2预期目标....................................................................................................................................................11.3解决问题....................................................................................................................................................12系统分析.......................................................................................................................................................12.1涉及的知识基础.......................................................................................................................................12.1.1LL(1)文法……………………………………………………………………………………..12.1.2确定的自顶向下分析思想…………………………………………………………………..2.2.1.3左递归的消除………………………………………………………………………………..32.1.4消除回溯、提左因子…………………………………………………………………………42.1.5计算FIRST集合、FOLLOW集合和SELECT集合……………………………………………….42.2解决问题的基本思路……………………………………………………………………………...52.3功能模块框图……………………………………………………………………………………….53系统设计.................................................................................................................错误!未定义书签。3.1LL(1)文法输入设计............................................................63.2LL(1)语法分析详细流程图......................................................63.3算法描述……………………………………………………………………………………………73.3.1消除左递归的算法…………………………………………………………………………….73.4系统流程图…………………………………………………………………………………………..84代码编写………………………………………………………………………………..94.1相关代码…………………………………………………………………………………………..94.4运行结果..................................................................................................................................................12总结............................................................................................................................................................14致谢............................................................................................................................................................15参考文献..................................................................................................................................................16《编译原理--课程设计报告》11课题综述编译原理的设计一般都是从文法和语言的基础知识开始，沿着词法分析、语法分析、语义分析、语法翻译、中间代码生成及符号表组织序列进行。本课题的总体设计完全依据编译原理的教学内容，即上下文无关文法基础及词法分析、语法分析技术研究、语法推导的语义翻译、代码优化及目标代码生成。但是在本课题中只涉及到了关于文法分析的相关知识。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.1涉及的知识基础2.1.1LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。一个用来描述语言语法结构的文法G[2]可形式地定义如下：《编译原理--课程设计报告》2一个文法G[S]可表示成形如(VN，VT，P，S)的四元式。其中VN，VT，P均为非空的有限集，分别称为非终结符集、终结符集和产生式集。具体来说：VN，一系列需要定义的语法范畴。VT，若干基本符号，不需要进一步定义。P，用“-“连接起来的有序对(A,α)的集合，称为规则，也叫产生式。其中A是一个非终结符，α是一个由终结符或非终结符组成的符号串，即α∈(VN∪VT)*。S，是文法的开始符号。S∈VN此外，我们还将出现在产生式左、右侧的全部符号的集合称为词汇表，记为V。显然：V=VN∪VT；VN∩VT=φ。更确切地说，上面给出的是上下文无关文法的定义。这是因为由符号串a去替换A时，并不考虑A所处的环境，即与A的上下文无关。除非另做说明，我们以后所说的文法均指上下文无关文法。LL(1)的含义：第一个L表示从左至右扫描输入符号串第二个L表示生成输入串的一个最左推导1表示在决定分析程序的每步动作时，向前看一个符号2.1.2确定的自顶向下分析思想LL(1)文法是一类可以进行确定的自顶而下语法分析的文法。而自顶而下分析法的基本思想是从文法的开始符号出发采用最左推导，根据当前的输入符号(单词符号)惟一地确定选用哪个产生式替换相应非终结符以下推导。这种分析过程实质是一种试探过程，是反复使用不同产生式匹配输入符号串的过程。若有文法：S-cAdA-ab|a输入串W=cad。为建立分析树，首先建立只有标记S单个结点树，输入指针指向W的第一个符号c。然后用S的第一个产生式来扩展该树，得到的树如图2.1所示：《编译原理--课程设计报告》3图2.1.1语法分析树最左边的叶子标记为c，匹配W的第一个符号。于是，推进输入指针到W的第二个符号a，并考虑下一个标记为A的叶子。用A的第一个选择来扩展A，得到如图(b)的树。现在匹配第二个输入符号a，再推进输入指针到d