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

《FirstVT集和LastVT集生成算法模拟编译原理课设》由会员分享，可在线阅读，更多相关《FirstVT集和LastVT集生成算法模拟编译原理课设（20页珍藏版）》请在装配图网上搜索。

1、课程设计(论文)任务书 软 件 学 院 学院 软件测试 专业 4 班 一、课程设计(论文)题目 FIRSTVT集和LASTVT集生成算法模拟 二、课程设计(论文)工作自 年 6 月 16 日起至 年 6 月 21 日止。三、课程设计(论文) 地点: 软 件 学 院 实 训 中 心 四、课程设计(论文)内容规定：1本课程设计的目的进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完毕有一定工作量的程序设计任务，同步，强调好的程序设计风格，并综合使用程序设计语言、数据构造和编译原理的知识, 熟悉使用开发工具VC /JAVA/C#/.NET 。

2、2课程设计的任务及规定1）课程设计任务： 设计一种由正规文法生成FIRSTVT集和LASTVT集的算法动态模拟。(算法参见教材) 动态模拟算法的基本功能是：(1) 输入一种文法G；(2) 输出由文法G构造FIRSTVT集的算法；(3) 输出FIRSTVT集； (4) 输出由文法G构造LASTVT集的算法；(5) 输出LASTVT集。2）创新规定：用界面的形式来呈现这个成果集，这样显得更加的美观。3）课程设计论文编写规定（1）课程设计任务及规定（2）设计思路-工作原理、功能规划（3）具体设计-数据分析、算法思路、功能实现（含程序流程图、重要代码及注释）、界面等。（4）运营调试与分析讨论-给出运营

3、屏幕截图，分析运营成果，有何改善想法等。（5）设计体会与小结-设计遇到的问题及解决措施，通过设计学到了哪些新知识，巩固了哪些知识，有哪些提高。（6）报告按规定排版打印，规定装订平整，否则规定返工；（7）课设报告的装订顺序如下：封面-任务书-中文摘要-目录-正文-附录(代码及有关图片)（8）严禁抄袭，如有发现，按不及格解决。4）课程设计评分原则： （1）学习态度：20分；（2）系统设计：20分；（3）编程调试：20分；（4）回答问题：20分；（5）论文撰写：20分。5）参照文献：（1）张素琴，吕映芝. 编译原理M., 清华大学出版社（2）蒋立源、康慕宁等，编译原理（第2版）M，西安：西北工业大学

4、出版社6）课程设计进度安排1准备阶段（4学时）：选择设计题目、理解设计目的规定、查阅有关资料2程序模块设计分析阶段（4学时）：程序总体设计、具体设计3代码编写调试阶段（8学时）：程序模块代码编写、调试、测试4撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文学生签名： 年 6 月 21 日课程设计(论文)评审意见（1）学习态度（20分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）

5、、差（）；（5）论文撰写（20分）：优（）、良（）、中（）、一般（）、差（）； 评阅人： 职称： 副专家 年 6 月 26 日目录绪论4正文4设计实现10测试数据运营成果分析12课程设计总结13参照文献14绪论随着计算机科学的飞速发展，形式语言与自动机理论和措施的研究也越来越受到人们的注重，但前者已经成为计算机科学的理论基本。本课程设计重要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完毕算数体现式的对的与否的判断。根据算符优先分析算法，编写一种语法程序，程序具有通用性，即编制的语法缝隙程序可以合用于不同文法以及多种输入的单词串。基本思想描述，语法分析前一方面要对输入

6、的文法和句子进行词法分析，清除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。算符优先分析算法的核心算法教材上已给出，因此所要做的事只是将其变成实现。正文设计目的本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的核心。算符优先分析算法是自底向上分析措施的一种。所谓自底向上分析，也称移近规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一种后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符替代相应右部的文法符号串，这称为一部规约。反

7、复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。本课程设计的规定只是构造FirstVT集和LastVT集，在此基本上扩大建造算符优先关系表。问题描述设计一种给定文法和相应的FIRSTVT和LASTVT集，能根据根据文法和FIRSTVT和LASTVT生成算符优先分析表。可以动态模拟算法的基本功能，通过输入一种给定文法，及FIRSTVT和LASTVT集，本题目以文法GE为测试数据: 文法GE:E-TEE-+TE|T-FTT-*FT|F-(E)|i该文法有相应的FIRSTV

8、T(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)之间的优先关系有三种优先关系计算为：关系：可以直接查看产生式的右部，对如下形式的产生式：Aab或 AaBb则有a=b成立。 关系：求出每个非终结符B的FIRSTVT(B)，观测如下形式的产生式：A

9、aB对每一bFIRSTVT(B)，有ab成立。 关系：计算每个非终结符B的LASTVT(B)，观测如下形式的产生式： ABb对每一aLASTVT(B)，有ab成立。 这样，对于给定的文法和相应的FIRSTVT和LASTVT集，通过二个终结符之间的优先关系表构造算法，可以得到算法优先分析表构造过程的过程和算符优先分析表生成算法。 因此，我们的重点应当放在算符优先分析表的生成算法上，解决了这一问题，也就可以得到我们想要的成果，算法优先分析表以及分析过程。其中，对于FIRSTVT集和LASTVT集的表达可以采用集合的方式，同样也可以采用关系图法进行表达。总体设计算符优先分析表的构造原理：通过检查文法

10、G的每个产生式的每个候选式，可以一方面找出满足ab的终结符对；为了找出所有满足关系和的终结符对，我们一方面需要对文法G的每个非终结符P构造二个集合FIRSTVT（P）和LASTVT(P)。1. FirstVT集的构造FIRSTVT(P）=a|P=+a或P=+Qa，aVT而QVN 若有产生式：Pa或PQa,则aFIRSTVT(P)；若aFIRSTVT(Q)，且有产生式PQ，则aFIRSTVT(P)。2. LastVT集的构造LASTVT(P)= a|P=+a或P=+aQ，aVT而QVN 若有产生式：Ua或UaV, 则aLASTVT(U)；若aLASTVT(V)，且有产生式UV，则aLASTVT(

11、U)。当我们有了这二个集合之后，就可以通过检查每个产生式的候选式拟定满足关系的“”和“”的所有终结符对。我们假定有产生式的一种侯选式形为aP，那么，对任何bFIRSTVT(P），ab；假定有产生式的一种候选形为Pb，那么，对任何aLASTVT(P)，有ab。3. 构造算符优先关系表在我们有了每个非终结符P的FIRSTVT(P）和LASTVT(P)集合之后，就可以构造文法G的优先表。具体设计一方面简介算符优先文法的几种重要性质：性质1：在算符文法中任何句型都不涉及两个相邻的非终结符。性质2：如果Aa（或者bA）出目前算符文法的句型S中，其中A是非终结符，b是终结符，则S中任何含此b的短语必具有A

12、。1. FirstVT集的构造，算法描述：若有产生式A-a或A-Ba，则a属于FirstVT（A），其中A、B为非终结符，a为终结符。 ：若a属于FirstVT（B）且有产生式A-B则有a属于FirstVT（A）。为了计算以便，建立一种布尔数组Fm,n（m为非终结字符的个数，n为终结字符的个数）和一种后进先出栈STACK。将所有的非终结符排序，用iA表达非终结符A的序号，再将所有的终结符排序，用ia表达终结符a的序号。算法的目的是要使数组的一种元素最后取值满足：FiA,ja的值为真，当且仅当a属于FirstVT（A）。至此，显然所有的非终结符的FirstVT集已完全拟定。环节如下：一方面按规则

13、对每个数组元素附初值。观测这些初值，若FiA,ia的值是真，则将（A，a）推入栈中，直至对所有数组的初值都按此解决完。然后对栈做如下运算。将栈顶项弹出，则令其变为真，且将（A，a）推动栈，如此反复直到栈弹空为止。若体现式文法为：（0） E# E #（1） EE + T（2） ET（3） TT*F（4） TF（5） FPF | P（6） P(E)（7） Pi计算每个非终结符的FirstVT集和LastVT集得到如下成果：FIRSTVT(E) = # FIRSTVT(E) = +，*，（，iFIRSTVT(T) = *，（，iFIRSTVT(F) = ，（，iFIRSTVT(P)=（，i2. La

14、stVT集的构造，算法描述：用于构建输入文法的LastVT集若有规则U:=a或U:=aV,则a属于LastVT（U）若有规则U:=V,且a属于LastVT（V）则a属于LastVT（U）设一种栈STACK，和一种布尔数组BProcedureInsert（U，a） IF NOT BU,a THEN BEGIN BU,a:=TRUE;把（U，a）推动STACK栈； END；BEGIN FOR 每个非终结符号U和终结符号a DO BU,a:=FALSE; FOR 每个形如U:=a或U:=aV的规则 DO INSERT(U,a); WHILE STACK栈非空 DO BEGIN 把STACK栈的栈顶弹

15、出，记为（V,a）; FOR 没条形如U:=V的规则 DO INSERT(U,a); END OF WHILE;END; 具体算法如下： Begin For每个终结符P和终结符 a Do FP,a=FALSE; For 每个形如P-a或P-aQ的产生式， Do insert （P，a） While Stack 非空 Do Begin 把Stack 的顶端，记为（Q，a），上托出去； For每条形如P-Q的产生式 Insert（P，a） End of while； END针对上述算法可得到每个非终结符的LastVT集如下：LASTVT(E) = # LASTVT(E) +，*，），iLASTVT

16、(T) *，），iLASTVT(F) ，），iLAVSTVT(P)），i 算符优先分析流程图图1算符优先分析流程图设计实现.重要数据存储构造描述：本课程设计重要采用栈的数据构造，定义一种栈的类，类中重要成员函数实现栈的某些基本操作，如：push（）为入栈操作，pop（）为出栈操作，empty（）判断栈中与否为空，clear（）用于对栈进行清空解决，核心代码为： 建立FirstVT函数集和SetFirstVT（），用来得到相应文法中所相应的非终结符的FirstVT集void CMyDlg:SetFirstVt(int Ptnum) /建立FRISTVT集int i,j; char Q; char

17、 a; for(i=0;i100;i+) for(j=0;j100;j+) Fij=false; for(i=0;i=2)if(Vn.Find(Pti.pright0)!=-1 & Vt.Find(Pti.pright1)!=-1)InsertFirstOrLast(Pti.pleft,Pti.pright1,First); while(!stack.empty() stack.pop(Q,a); for(i=0;iPtnum;i+) if(Pti.pright0=Q) InsertFirstOrLast(Pti.pleft,a,First); 建立LastVT集函数和SetLastVT函数，

18、用来得到相应文法中所有非终结符的LastVT集void CMyDlg:SetLastVt(int Ptnum) /建立LASTVT集 int i,j; char Q; char a; for(i=0;i100;i+) for(j=0;j100;j+) Lij=false; for(i=0;i=2) if(Vt.Find(Pti.pright.Right(2)0)!=-1&Vn.Find(Pti.pright.Right(2)1)!=-1)InsertFirstOrLast(Pti.pleft,Pti.pright.Right(2)0,Last); while(!stack.empty() stack.pop(Q,a); for(i=0;iE+T|TT-T*F|FF-(E)|i采用“示例文法”的实验截图如下：参照文献1、 张素琴、吕映芝等.编译原理M（第2版）.清华大学出版社.2、 (美)Alfred V.Aho;Monica S.Lam;Ravi Sethi;Jeffrey D.Ullman. Compilers: Principles, Techniques, and Tools (2nd Edition)M.机械工业出版社. 12月3、