编译原理课程设计报告-LL(1)分析过程模拟

课程设计(论文)任务书软件学院学院软件工程专业07-1班一、课程设计(论文)题目LL(1)分析过程模拟二、课程设计(论文)工作自2010年6月22日起至2010年6月28日止。三、课程设计(论文)地点:四、课程设计(论文)内容要求：1．本课程设计的目的（1）使学生掌握LL（1）模块的基本工作原理；（2）培养学生基本掌握LL（1）分析的基本思路和方法；（3）使学生掌握LL（1）的调试；（4）培养学生分析、解决问题的能力；（5）提高学生的科技论文写作能力。2．课程设计的任务及要求1）基本要求：（1）分析LL（1）模块的工作原理；（2）提出程序的设计方案；（3）对所设计程序进行调试。2）创新要求：在基本要求达到后，可进行创新设计，如改算法效率。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写课程设计论文（2）论文包括目录、绪论、正文、小结、参考文献、附录等（3）课程设计论文装订按学校的统一要求完成4）答辩与评分标准：（1）完成原理分析：20分；（2）完成设计过程（含翻译）：40分；（3）完成调试：20分；编译原理课程设计报告（4）回答问题：20分。5）参考文献：（1）张素琴，吕映芝，蒋维杜，戴桂兰.编译原理（第2版）.清华大学出版社（2）丁振凡.《Java语言实用教程》北京邮电大学出版社6）课程设计进度安排内容天数地点构思及收集资料2图书馆编程与调试4实验室撰写论文1图书馆、实验室学生签名：2009年6月22日课程设计(论文)评审意见（1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：职称：年月日编译原理课程设计报告目录一、课设题目__________________________________________________51.问题描述_______________________________________52.基本要求_______________________________________53.测试数据_______________________________________5二、需求分析__________________________________________________61.问题理解_______________________________________62.问题分析_______________________________________63.问题的解决_____________________________________64.解决步骤_______________________________________6三、概要设计__________________________________________________91、设计原理______________________________________92、预测分析表具体构造______________________________113、主要算法思想__________________________________12四、详细设计____________________________________________________121.总体思路分析及流程图_____________________________12编译原理课程设计报告2、测试数据i*i+i的语法树___________________________182.关键代码______________________________________183.函数说明______________________________________21五．运行结果____________________________________231.出错处理______________________________________24六、课程设计总结________________________________________________26七、参考文献____________________________________________________27八、附录________________________________________________________27编译原理课程设计报告5一、课设题目1.问题描述设计一个给定LL（1）分析表，输入一个句子，能由依据LL（1）分析表输出与句子对应的语法树。能对语法树生成过程进行模拟。2.基本要求动态模拟算法的基本功能是：（1）输入LL（1）分析表和一个句子；（2）输出LL（1）总控程序；（3）输出依据句子构成的对应语法树的过程；3.测试数据输入句子：i*i+i输入LL（1）分析表((EE))iiFF**FFBBBBFFBBFFBBTT++TTAAAATTAATTAAEE##))((**++ii编译原理课程设计报告6二、需求分析1.问题理解用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。2.问题分析求出First集和Follow集，是求出Select集的基础，因此本程序也做了些完善，功能扩展发面，在出First集和Follow集的基础上求Select集，判断是否为LL1文法，构造预测分析表。判断是在LL1分析文法中通过Select集判断是否是LL1文法，求出预测分析表之后，实现了字符串，依据LL1分析表单步输出字符串的分析过程。3.问题的解决其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。4.解决步骤总体步骤在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和编译原理课程设计报告7FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。FIRST集的确定FIRST集使用以下四个步骤判定：(1)若X∈则FIRST(X)={X}(2)若X∈VN,且有产生式X→a…，a∈VT。则把a加入到FIRST(X)中，即a∈FIRST(X)(3)若X∈VN,且有产生式X→$，则把$也加到FIRST(X)中，即$∈FIRST(X)(4)若X∈VN,Y1，Y2，…，Yi都∈VN，且有产生式X→Y1Y2…Yn。当Y1，..Yi-1=$(1≤i≤n)，则FIRST(Y1)-{$}，…，FIRST(Yi-1)-{$}，FIRST(Yi)都包含在FIRST(X)中，即：FIRST(Yi-1)-{$}∈FIRST(X)所有Y1,…Yn*=$，则把$加到FIRST(X)中,即：FIRST(Yi)∈FIRST(X)FOLLOW集的确定FOLLOW集使用以下三个步骤判定：(1)如果X是开始符那么把#加入到FOLLOW(X)(2)若Ａ=αBβ是一个产生式,则把FIRST(β)－{$}加至FOLLOW(B)中(3)若Ａ=αB是一个产生式，或Ａ=αBβ是一个产生式而β*=$(即$∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中FOLLOW集的求法与FIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。碰到死循环使用FIRST集一样的方法处理就可以。SELLECT集的确定FIRST集＆FOLLOW集都已经求出来后SELLECT集就很好编译原理课程设计报告8求了，扫描每一个产生式，使用以下三个步骤确定：A→αA∈VN，α∈V*，(1)若α是终结符，那么SELLECT(A→α)={α}(2)若α是$，则SELECT(A→α)=FOLLOW(A)(3)若α是非终结符那么若α*=$，则SELECT(A→α)=(FIRST(α)-$)∪FOLLOW(A)若α┐*=$则SELECT(A→α)=FIRST(α)LL(1)文法的判定当SELLECT集求出来后就可以判断是不是一个文法是不是LL(1)文法了，扫描产生式左部相同的SELLCET集是否含有相同元素，一旦发现相同元素立刻返回FALSE，扫描结束没有发现相同元素则返回TRUE。句子的判定当一个文法确定是LL(1)文法时就可以对输入的语句进行判定了。首先要安装SELLECT集生成LL(1)预测分析表，最简单的方法是使用哈希表来表示，把每一个产生式左部依次和这个产生式SELLECT集中的每一个终结符组成关键字，其值即为这个产生式，送入哈希表。这样在进行句子的分析时就可以很容易判断是否使用某一个产生式来进行规约。在实际分析时设置两个栈，把#压入分析栈和剩余栈，把开始符压入分析栈，把输入串从右向左送入剩余栈，然后只要两个栈元素个数同时大于1，那么依次从两个栈中取出两个元素进行比较，假如一样就匹配，假如可以规约就规约，否则就不是该文法的句子。编译原理课程设计报告9三、概要设计1、设计原理（1）、LL（1）文法的定义LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求文法满足如下条件：对于任一非终极符A的两个不同产生式A,A，都要满足下面条件：SELECT(A)∩SELECT(A)=（2）、预测分析表构造LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串，一是null。若用M表示LL(1)分析表，则M可表示如下：M:VN×VTP∪{Error}M(A,t)=Aα，当tselect(Aα)，否则M(A,t)=Error其中P表示所有产生式的集合。（3）、