FirstVT集和LastVT集生成算法模拟(编译原理课设)

华东交通大学1课程设计(论文)任务书软件学院学院软件测试专业4班一、课程设计(论文)题目FIRSTVT集和LASTVT集生成算法模拟二、课程设计(论文)工作自2014年6月16日起至2014年6月21日止。三、课程设计(论文)地点:软件学院实训中心四、课程设计(论文)内容要求：1．本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识,熟悉使用开发工具VC/JAVA/C#/.NET。2．课程设计的任务及要求1）课程设计任务：设计一个由正规文法生成FIRSTVT集和LASTVT集的算法动态模拟。(算法参见教材)动态模拟算法的基本功能是：(1)输入一个文法G；(2)输出由文法G构造FIRSTVT集的算法；(3)输出FIRSTVT集；(4)输出由文法G构造LASTVT集的算法；(5)输出LASTVT集。2）创新要求：用界面的形式来展现这个结果集，这样显得更加的美观。3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路--工作原理、功能规划华东交通大学2（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，要求装订平整，否则要求返工；（7）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录(代码及相关图片)（8）严禁抄袭，如有发现，按不及格处理。4）课程设计评分标准：（1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。5）参考文献：（1）张素琴，吕映芝.编译原理[M].,清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）[M]，西安：西北工业大学出版社6）课程设计进度安排1．准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料2．程序模块设计分析阶段（4学时）：程序总体设计、详细设计3．代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4．撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名：2014年6月21日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；华东交通大学3（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）；评阅人：职称：副教授2014年6月26日华东交通大学4目录绪论..................................................................................................5正文..................................................................................................5设计实现........................................................................................11测试数据运行结果分析...............................................................13课程设计总结...............................................................................14参考文献........................................................................................15华东交通大学5绪论随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前者已经成为计算机科学的理论基础。本课程设计主要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完成算数表达式的正确与否的判断。根据算符优先分析算法，编写一个语法程序，程序具有通用性，即编制的语法缝隙程序能够适用于不同文法以及各种输入的单词串。基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。算符优先分析算法的核心算法教材上已给出，因此所要做的事只是将其变成实现。正文设计目的本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算符优先分析算法是自底向上分析方法的一种。所谓自底向上分析，也称移近——规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。问题描述设计一个给定文法和对应的FIRSTVT和LASTVT集，能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。可以动态模拟算法的基本功华东交通大学6能，通过输入一个给定文法，及FIRSTVT和LASTVT集，本题目以文法G[E]为测试数据:文法G[E]:E-TE’E’-+TE’|εT-FT’T’-*FT’|εF-(E)|i该文法有对应的FIRSTVT(E)={+,*,(,i}LASTVT(E)={+，*，),i}FIRSTVT(E')={+}LASTVT(E')={+，*，),i}FIRSTVT(T)={*,(,i}LASTVT(T)={*，),i}FIRSTVT(T')={*}LASTVT(T')={*，),i}FIRSTVT(F)={(,i}LASTVT(F)={),i}通过算符优先关系表构造算法：给定文法中任何二个终结符对(a,b)之间的优先关系有三种优先关系计算为：①＝关系：可以直接查看产生式的右部，对如下形式的产生式：A→．．．ab．．．或A→．．．aBb．．．则有a=b成立。②＜关系：求出每个非终结符B的FIRSTVT(B)，观察如下形式的产生式：A→．．．aB．．．对每一b∈FIRSTVT(B)，有a＜b成立。③＞关系：计算每个非终结符B的LASTVT(B)，观察如下形式的产生式：A→．．．Bb．．．对每一a∈LASTVT(B)，有a＞b成立。这样，对于给定的文法和对应的FIRSTVT和LASTVT集，通过二个终结符之间的优先关系表构造算法，可以得到算法优先分析表构造过程的过程和算符优先分析表生成算法。所以，我们的重点应该放在算符优先分析表的生成算法上，解决了这一问题，也就可以得到我们想要的结果，算法优先分析表以及分析过程。其中，对于FIRSTVT集和LASTVT集的表示可以采取集合的方式，同样也可以采用关系图法进行表示。华东交通大学7总体设计算符优先分析表的构造原理：通过检查文法G的每个产生式的每个候选式，可以首先找出满足a＝b的终结符对；为了找出所有满足关系＜和＞的终结符对，我们首先需要对文法G的每个非终结符P构造二个集合FIRSTVT（P）和LASTVT(P)。1.FirstVT集的构造FIRSTVT(P）={a|P=+a．．．或P=+Qa．．．，a∈VT而Q∈VN}若有产生式：P→a．．．或P→Qa．．．,则a∈FIRSTVT(P)；若a∈FIRSTVT(Q)，且有产生式P→Q．．．，则a∈FIRSTVT(P)。2.LastVT集的构造LASTVT(P)={a|P=+．．．a或P=+．．．aQ，a∈VT而Q∈VN}若有产生式：U→．．．a或U→．．．aV,则a∈LASTVT(U)；若a∈LASTVT(V)，且有产生式U→．．．V，则a∈LASTVT(U)。当我们有了这二个集合之后，就可以通过检查每个产生式的候选式确定满足关系的“＜”和“＞”的所有终结符对。我们假定有产生式的一个侯选式形为．．．aP．．．，那么，对任何b∈FIRSTVT(P），a＜b；假定有产生式的一个候选形为．．．Pb．．．，那么，对任何a∈LASTVT(P)，有a＞b。3.构造算符优先关系表在我们有了每个非终结符P的FIRSTVT(P）和LASTVT(P)集合之后，就能够构造文法G的优先表。详细设计首先介绍算符优先文法的几个重要性质：性质1：在算符文法中任何句型都不包含两个相邻的非终结符。性质2：如果Aa（或者bA）出现在算符文法的句型S中，其中A是非终结符，b是终结符，则S中任何含此b的短语必含有A。1.FirstVT集的构造，算法描述①：若有产生式A-a…或A-Ba…，则a属于FirstVT（A），其中A、B为非终结符，a为终结符。②：若a属于FirstVT（B）且有产生式A-B…则有a属于FirstVT华东交通大学8（A）。为了计算方便，建立一个布尔数组F[m,n]（m为非终结字符的个数，n为终结字符的个数）和一个后进先出栈STACK。将所有的非终结符排序，用iA表示非终结符A的序号，再将所有的终结符排序，用ia表示终结符a的序号。算法的目的是要使数组的一个元素最终取值满足：F[iA,ja]的值为真，当且仅当a属于FirstVT（A）。至此，显然所有的非终结符的FirstVT集已完全确定。步骤如下：首先按规则①对每个数组元素附初值。观察这些初值，若F[iA,ia]的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此处理完。然后对栈做如下运算。将栈顶项弹出，则令其变为真，且将（A，a）推进栈，如此重复直到栈弹空为止。若表达式文法为：（0）E'→#E#（1）E→E+T（2）E→T（3）T→T*F（4）T→F（5）F→P↑F|P（6）P→(E)（7）P→i计算每个非终结符的FirstVT集和LastVT集得到如下结果：FIRSTVT(E')={#}FIRSTVT(E)={+，*，↑，（，i}FIRSTVT(T)={*，↑，（，i}FIRSTVT(F)={↑，（，i}FIRSTVT(P)={（，i}2.LastVT集的构造，算法描述：用于构建输入文法的LastVT集①若有规则U::=…a或U::==…aV,则a属于LastVT（U）②若有规则U::=…V,且a属于LastVT（V）则a属于LastVT（U）设一个栈STACK，和一个布尔数组BProcedureInsert（U，a）华东交通大学9IFNOTB[U,a]THENBEGINB[U,a]::=TRUE;把（U，a）推进STACK栈；END；BEGINFOR每个非终结符号U和终结符号aDOB[U,a]:=FALSE;FOR每个形如U::=…a或U::=…aV的规则DOINSERT(U,a);WHILESTACK栈非空DOBEGIN把STACK栈的栈顶弹出，记为（V,a）;FOR没条形如U::=…V的规则DOINSERT(U,a);ENDOFWHILE;END;具体算法如下：BeginFor每个终结符P和终结符aDoF[P,a]=FALSE;For每个形如P-…a或P-…aQ的