FirstVT集和LastVT集生成算法模拟

课程设计(论文)任务书软件学院学院软件工程专业3班一、课程设计(论文)题目FirstVT集和LastVT集生成算法模拟二、课程设计(论文)工作自2013年6月17日起至2013年6月21日止。三、课程设计(论文)地点:软件学院实训中心四、课程设计(论文)内容要求：1．本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时，强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识,熟悉使用开发工具VC/JAVA/C#/.NET。2．课程设计的任务及要求1）课程设计任务：设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟2）创新要求：3）课程设计论文编写要求（1）课程设计任务及要求（2）设计思路--工作原理、功能规划（3）详细设计---数据分析、算法思路、功能实现（含程序流程图、主要代码及注释）、界面等。（4）运行调试与分析讨论---给出运行屏幕截图，分析运行结果，有何改进想法等。（5）设计体会与小结---设计遇到的问题及解决办法，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，要求装订平整，否则要求返工；（7）课设报告的装订顺序如下：封面---任务书---中文摘要---目录----正文---附录(代码及相关图片)编译原理课程设计-第2页-（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学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名：2013年6月21日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）；评阅人：职称：副教授2013年6月日司房昭：FirstVT集和LastVT集生成算法模拟-第3页-中文摘要随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前者已经成为计算机科学的理论基础。本课程设计主要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完成算数表达式的正确与否的判断。根据算符优先分析算法，编写一个语法程序，程序具有通用性，即编制的语法缝隙程序能够适用于不同文法以及各种输入的单词串。基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。算符优先分析算法的核心算法教材上已给出，因此所要做的事只是将其变成实现。计算非终结符的FIRSTVT集和LASTVT集是构造算符优先分析表的基础，而算符优先分析表的构造又是算符优先分析算法的基础。因此，本程序的实现可以说是算符优先分析算法实现的基础。编译原理课程设计-第4页-目录一、课程设计任务及要求..................................................................5二、需求分析......................................................................................7三、设计思路......................................................................................8四、详细设计....................................................................................10五、运行调试与分析讨论................................................................14六、设计体会与小结........................................................................14七、参考文献....................................................................................16司房昭：FirstVT集和LastVT集生成算法模拟第5页一、课程设计任务及要求课设目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC/JAVA/C#/.NET。总体要求1.思想的正确性，采用合适的数据存储结构等。2.程序实现的正确性，程序整体结构合理、编程风格规范等。3.程序功能的完善程度，包括功能的基本实现、基本完善、完全实现4.工作认真、独立完成课设。基本要求设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟，实现以下功能输入一个文法G；1.输出由文法G构造FIRSTVT集的算法；2.输出FirstVT集；3.输出由文法G构造LastVT集的算法；4.输出LastVT集。具体步骤1、问题理解和分析充分地分析和理解问题本身，弄清要求做什么。2、确定解决问题的方法（设计）主要是找到解决问题的主要思路，是怎么做。在此阶段可考虑系统的功能和模块划分等。3、详细设计和编码确定算法的主要流程，再进行编程。在此阶段应提醒学生程序可先在纸上写，尽量想清楚了再动手上机，在编程过程中注意程序结构的清晰性，避免出现很多明显的程序逻辑错误和语法错误，提高后面程序调试效率。编译原理课程设计-第6页-4、程序调试和运行使学生掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感。5、完成课程设计报告（使用华东交通大学课程设计报告，需学生自己购买）司房昭：FirstVT集和LastVT集生成算法模拟第7页二、需求分析本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算符优先分析算法是自底向上分析方法的一种。所谓自底向上分析，也称移近——规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。编译原理课程设计-第8页-三、设计思路3.1基本算法构造集合FIRSTVT(P)的算法按FIRSTVT(P)的定义，可以用如下两条归则来构造：(1)若有产生式Pa…或Qa…，则a∈FIRSTVT(P)(2)若a∈FIRSTVT(Q)，且有产生式PQ…，则a∈FIRSTVT(P)构造算法：建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT(P);构造算法再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对(P,a)全都放到栈中；算法如下：(1)将布尔矩阵各元素置假；栈置空；(2)按照归则(1)查看产生式，对于Pa…或PQa..，置相应F[P,a]为真，符号对(P,a)入栈；(3)按规则(2)，对栈施加如下操作：弹出栈定符号对记作(Q,a)，查看所有产生式是否有形如PQ…产生式，若有，且a∈FIRSTVT(P)，则将F[P,a]置为真，并把(P,a)入栈；(4)重复(3)，直到栈空为止。用类似的方法来构造LASTVT(P)可根据LASTVT(P)的定义来构造，两条规则：(1)若有产生式P…a或…aQ，则a∈LASTVT(P)(2)若a∈LASTVT(P)，且有产生式P…Q，则a∈LASTVT(P)构造算法同FIRSTVT(P)的构造算法3.2定义数据结构在程序中，用两个字符数组vn[M]和vt[N]分别用来存储所有的非终结字符集与终结字符集。为了记录非终结符的FIRSTVT集和LASTVT集，为此建立两个布尔数组F[M][N]和L[M][N]，分别记录非终结符的FIRSTVT司房昭：FirstVT集和LastVT集生成算法模拟第9页集和LASTVT集。比如，F[i][j]=true表示vt[j]属于FIRSTVT(vn[i])，L[i][j]=true表示vt[j]属于LASTVT(vn[i])，值为false表示相应的终结符不属于非终结符的FIRSTVT集和LASTVT集。为了简便起见，程序中又构造了两个两维布尔数组first[M][M+N]和last[M][M+N]来表示推导关系。数组第一维的M个字符代表非终结符；数组第二维的前M个字符代表非终结符，后N个字符代表终结符。以first数组为例，fist[i][M+j]代表非终结符vn[i]=P与非终结符vt[j]=a有推导关系Pa…；fist[i][j]代表非终结符vn[i]=P与非终结符vt[j]=Q有推导关系或PQa..。相关的数据结构定义如下：charvn[M],vt[N];//非终结字符与终结字符数组boolfirst[M][M+N],last[M][M+N];//以布尔数组形式定义推导关系charvn[M],vt[N];//非终结字符与终结字符数组intstp;//堆栈栈顶指针符号栈的数据结构：structrelation//结构体用来说明终结符vt与非终结符vn之间的关系，若关系存在说明vt属于FIRSTVT(vn)或LASTVT(vn){intvn;intvt;};编译原理课程设计-第10页-四、详细设计存储firstvt，4个case对FIRSTVT进行存储voidsetFIRSTVT(charX,intT){inti;intt=0;switch(T){case0:for(i=0;iN;i++){if(X==FIRSTVT0[i])break;elseif(FIRSTVT0[i]=='\0'){t=i;break;}}FIRSTVT0[t]=X;break;case1:for(i=0;iN;i++){if(X==FIRSTVT1[i])break;elseif(FIRSTVT1[i]=='\0'){t=i;break;}}FIRSTVT1[t]=X;break;case2:for(i=0;iN;i++)司房昭：FirstVT集和LastVT集生成算法模拟第11页{if(X==FIRSTVT2[i])break;elseif(FIRSTVT2[i]=='\0'){t=i;break;}}FIRSTVT2[t]=X;break;case3:for(i=0;iN;i++){if(X==FIRSTVT3[i])break;elseif(FIRSTVT3[i]=='\0'){t=