编译原理课程设计报告-预测分析程序的设计

课程设计任务书学生姓名：专业班级：指导教师：工作单位：题目:预测分析程序的设计初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据《编译原理》课程所讲授的算法进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2.课设任务：对教材P94中的上下文无关文法，实现它的预测分析程序，给出符号串i+i*i的分析过程。（参考教材P93～96）3.主要功能：对于这个给的LL（1）文法，假设所有非终结符号P的FIRST集合和FOLLOW集合都是已知的，构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分析，并给出了栈的变化过程。4.进行总体设计，详细设计：包括算法的设计和数据结构设计。系统实施、调试，合理使用出错处理程序。5.设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：①课程设计的题目。②目录。③正文：包括引言、需求分析、总体设计及开发工具的选择，设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。④结束语。⑤参考文献。⑥附录：软件清单（或者附盘）。时间安排：消化资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名：2010年6月11日系主任（或责任教师）签名：2010年6月11日《编译原理》课程设计说明书3目录1引言.............................................52需求分析.........................................52.1问题的提出.....................................52.2问题的解决.....................................52.3解决步骤.......................................63总体设计.........................................63.1概要设计.......................................63.1.1设计原理....................................63.1.2构造LL（1）分析表...........................73.2详细设计......................................103.2.1程序流程图.................................103.2.2设计要求...................................123.2.3设计原理...................................123.2.3.1FIRST(X)(XVNVT)的构造...............123.2.3.2函数getFIRST()(=X1X2X3…Xn)的构造.123.2.3.3FOLLOW(A)(AVN)的构造................133.2.3.4分析表M【A,a】的构造..................133.2.3.5匹配过程的实现.........................133.3程序设计......................................14《编译原理》课程设计说明书43.3.1总体方案设计...............................143.3.2各模块的实现...............................144开发工具的选择..................................235程序测试........................................236有关技术的讨论..................................257收获与体会......................................258参考文献........................................26《编译原理》课程设计说明书51引言一个编译程序在对某个源程序完成了词法分析工作之后，就进入了语法分析阶段，分析检查源程序是否语法上正确的程序，并生成相应的内部中间表供下一阶段使用。程序设计语言是一般形式语言的特例，程序语法正确性的检查时语法句子的识别，语法分析问题也就是句型识别问题。按照识别句子语法树建立的方式，有自顶向下与自底向上两大类分析技术。本课程讨论自顶向下的情况。本次课程设计所做的工作是对已知FIRST集合和FOLLOW集合的LL(1)文法构造其预测分析表，程序显示输出预测分析表，同时用这个预测分析程序对输入串进行分析，并给出了栈的变化过程。2需求分析2.1问题的提出语法分析是编译过程的核心部分。他的任务是在词法分析识别单词符号串的基础上，分析并判断程序的的语法结构是否符合语法规则。语言的语法结构是用上下文无关文法描述的。因此语法分析器的工作的本质上就是按文法的产生式，识别输入符号串是否为一个句子。对于一个文法，当给你一串符号是，如何知道它是不是该文法的一个句子，这是这个课程设计所要解决的一个问题。2.2问题的解决其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。《编译原理》课程设计说明书62.3解决步骤在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。当然本课设只是针对FIRST和FOLLOW集合都以知的任意输入的LL（1）文法。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。3总体设计3.1概要设计3.1.1设计原理所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。我们知道一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，也是采用了C++语言来编写。《编译原理》课程设计说明书7LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X=a=‘#’，则宣布分析成功，停止分析过程。（２）若X=a‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。（３）若X是一个非终结符，则查看预测分析表M。若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK栈顶，然后，把产生式的右部符号串按反序一一弹出STACK栈（若右部符号为ε，则不推什么东西进STACK栈）。若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。3.1.2构造LL（1）分析表在构造LL(1)预测分析表之前，首先要构造该文法的每个非终结符的FIRST和FOLLOW集合，按照下面描述的算法来构造这两个集合。①FIRST集合的构造算法：（1）若X∈VT，则FIRST（X）={X}。（2）若X∈VN，且有产生式X→a……，则把a加入到FIRST(X)中；若X→ε也是一条产生式，则把ε也加到FIRST(X)中。（3）若X→Y……是一个产生式且Y∈VN，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任何j，1≤j≤i-1，FIRST(Yj)都含有ε（即Y1…Yi-1*ε），《编译原理》课程设计说明书8则把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有ε，j=1,2,…，k，则把ε加到FIRST(X)中。连续使用上面的规则，直至每个集合FIRST不再增大为止。②FOLLOW集合的构造算法：（1）对于文法的开始符号S，置#于FOLLOW(S)中；（2）若A→αBβ是一个产生式，则把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一个产生式，或A→αBβ是一个产生式而βε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。连续使用上面的规则，直至每个集合FOLLOW不再增大为止。根据以上描述的算法，可以构造文法G［A］的FIRST和FOLLOW集合如下：非终结符AFIRST(A)FOLLOW(A)A{(，i}{),#}B{+,ε}{),#}C{(，i}{+,),#}D{*,ε}{+,),#}E{(，i}{*,+,),#}构造预测分析表，设计预测分析表的存储结构（构造算法）。i+*()#AACBACB《编译原理》课程设计说明书9BB+CBBεBεCCEDCEDDDεD*EDDεDεEEiE(A)总体的框图：句子分析过程的框图：《编译原理》课程设计说明书103.2详细设计3.2.1程序流程图在对程序各个模块分析之前。先给出整个程序的流程图。以便于在分析过程中更好的对各个模块之间的联系进行了解。程序的流程图如下：《编译原理》课程设计说明书11开始输入文法相关信息LL（1）文法构造FIRST集构造FOLLOW集构造预测分析表输入产生式判断句型Continue=“Y“构造句子的预测分析过程是Y结束《编译原理》课程设计说明书123.2.2设计要求1.实现FIRST(X)(XVNVT)；2.根据FIRST(X)(XVNVT)，实现getFIRST()(=X1X2X3…Xn)；3.实现FOLLOW(A)(AVN)；4.根据getFIRST()以及FOLLOW(A)构造LL(1)分析表M【A,a】；5.根据分析表M【A,a】，对任一输入字符串进行匹配，判断是否合法，并且显示其匹配过程。3.2.3设计原理3.2.3.1FIRST(X)(XVNVT)的构造连续使用下面的规则，直至每个集合FIRST不再增大为止：(1).若XVT，则FIRST