课程设计(论文)任务书
软 件 学 院 学 院 软件测试 专 业 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）设计思路--工作原理、功能规划
（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分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）； （4）回答问题（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
（5）论文撰写（20分）：优（ ）、良（ ）、中（ ）、一般（ ）、差（ ）；
评阅人： 职称： 副教授
2014 年 6 月 26 日
目录
绪论 .............................................................. 错误!未定义书签。 正文 .............................................................. 错误!未定义书签。 设计实现 ...................................................... 错误!未定义书签。 测试数据运行结果分析 ................................ 错误!未定义书签。 课程设计总结 ............................................... 错误!未定义书签。 参考文献 ...................................................... 错误!未定义书签。
绪论
随着计算机科学的飞速发展，形式语言与自动机理论和方法的研究也越来越受到人们的重视，但前者已经成为计算机科学的理论基础。本课程设计主要研究自动机在编译方面的应用，并将讨论重点放在算符优先分析法上，并用此理论完成算数表达式的正确与否的判断。
根据算符优先分析算法，编写一个语法程序，程序具有通用性，即编制的语法缝隙程序能够适用于不同文法以及各种输入的单词串。基本思想描述，语法分析前首先要对输入的文法和句子进行词法分析，去除多余的自负，并将产生式和终结符、非终结符填入有关数组，为语法分析做前期准备。算符优先分析算法的核心算法教材上已给出，因此所要做的事只是将其变成实现。
正文
设计目的
本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。算符优先分析算法是自底向上分析方法的一种。所谓自底向上分析，也称移近——规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。
本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。
问题描述
设计一个给定文法和对应的FIRSTVT和LASTVT集，能依据依据文法和FIRSTVT和LASTVT生成算符优先分析表。可以动态模拟算法的基本功
能，通过输入一个给定文法，及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集的表示可以采取集合的方式，同样也可以采用关系图法进行表示。
总体设计
算符优先分析表的构造原理：通过检查文法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
（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，和一个布尔数组B Procedure
Insert（U，a）
IF NOT B[U,a] THEN BEGIN
B[U,a]::=TRUE;把（U，a）推进STACK栈； END； BEGIN
FOR 每个非终结符号U和终结符号a DO B[U,a]:=FALSE;
FOR 每个形如U::=…a或U::=…aV的规则 DO INSERT(U,a);
WHILE STACK栈非空 DO BEGIN
把STACK栈的栈顶弹出，记为（V,a）; FOR 没条形如U::=…V的规则 DO INSERT(U,a); END OF WHILE; END;
具体算法如下： Begin
For每个终结符P和终结符 a Do F[P,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) ＝ {+，*，↑，），i} LASTVT(T) ＝ {*，↑，），i} LASTVT(F) ＝{↑，），i} LAVSTVT(P)＝{），i}
① 算符优先分析流程图
置初值 k:=1,S[k]:=’#’当前输入符读入aYS[k]∈Vt ?Nj:=kj:=k-1S[j] > aYNS[j] < a ?NY出错NQ := S [j]S[j] = a ?YNk:=k+1S[k] :=aYS[j-1]∈Vt ?NS[j] = ‘#’ ?Nj:= j-1j:= j-2Y检查是否正常借书N出错S[j] < Q ?YY结束S[j+1]...S[k]规约为Nk:=j+1 S[k]:=N图1算符优先分析流程图
设计实现
Ⅰ.主要数据存储结构描述：
本课程设计主要采用栈的数据结构，定义一个栈的类，类中主要成员函数实现栈的一些基本操作，如：push（）为入栈操作，pop（）为出栈操作，empty（）判断栈中是否为空，clear（）用于对栈进行清空处理，核心代码为：
① 建立FirstVT函数集和SetFirstVT（），用来得到相应文法中所对应的非终结符的FirstVT集
void CMyDlg::SetFirstVt(int Ptnum) right[0])!=-1) InsertFirstOrLast(Pt[i].pleft,Pt[i].pright[0],\"First\"); if(Pt[i].()>=2) if(Pt[i].pright[0])!=-1 && (Pt[i].pright[1])!=-1) InsertFirstOrLast(Pt[i].pleft,Pt[i].pright[1],\"First\"); } while(!()) { (Q,a); for(i=0;i② 建立LastVT集函数和SetLastVT函数，用来得到相应文法中所有非终结符的LastVT集void CMyDlg::SetLastVt(int Ptnum) 1)[0]))
InsertFirstOrLast(Pt[i].pleft,Pt[i].(1)[0],\"Last\"); if(Pt[i].()>=2) if(Pt[i].(2)[0])!=-1&&(Pt[i].(2)[1])!=-1) InsertFirstOrLast(Pt[i].pleft,Pt[i].(2)[0],\"Last\");
}
while(!()) { (Q,a); for(i=0;i}}
InsertFirstOrLast(Pt[i].pleft,a,\"Last\");
测试数据运行结果分析
1、 测试数据如下，文法G[S] ①S→# E # ②E→E + T ③E→T ④T→T*F ⑤T→F
⑥F→P-F | P ⑦P→(E)|i
它对性的FirstVT集和LastVT集为： FIRSTVT(S) = { # }
FIRSTVT(E) = {+，*，-，（，i} FIRSTVT(T) = {*，-，（，i} FIRSTVT(F) = {-，（，i} FIRSTVT(P)={（，i} LASTVT(S) = { # }
LASTVT(E) ＝ {+，*，-，），i} LASTVT(T) ＝ {*，-，），i} LASTVT(F) ＝{-，），i} LAVSTVT(P)＝{），i} 2、运行结果截图为：
课程设计总结
经过一个星期的编译原理课程设计的实践，我重新复习了自底向上的分析方法，其中重点复习了算符优先分析算法，对词法、文法的判断有了较深刻的认识，对算符优先分析算法的FirstVT集和LastVT集的构造有了更加感性的认识，对其中数据的流向和数据的输出操作有了很清晰的认识，对数据在该课程设计中的存储和运算有了深刻的理解。
在本课程设计中还存在没有解决的问题，比如在拓广文法中非终结字符“E’”的识别和空产生式的识别都还是悬而未决的问题。
其实在本课程设计的基础上在添加两个优先关系表的函数创建优先关系函数CMyDlg::Create_G_table()和输出优先关系函数CMyDlg::Show_list1()，就可以实现优先关系表的输出。
“示例文法”为： E->E+T|T T->T*F|F F->(E)|i
采用“示例文法”的实验截图如下：
参考文献
1、 张素琴、吕映芝等.编译原理〔M〕（第2版）.清华大学出版社.2005 2、 (美)Alfred ;Monica ;Ravi Sethi;Jeffrey . Compilers: Principles, Techniques,
and Tools (2nd Edition)〔M〕.机械工业出版社. 2008年12月
