FirstVT集和LastVT集生成算法模拟.docx

资源描述

FirstVT集和LastVT集生成算法模拟.docx

《FirstVT集和LastVT集生成算法模拟.docx》由会员分享，可在线阅读，更多相关《FirstVT集和LastVT集生成算法模拟.docx（14页珍藏版）》请在冰点文库上搜索。

FirstVT集和LastVT集生成算法模拟.docx

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）课设报告的装订顺序如下：

封面---任务书---中文摘要---目录----正文---附录

（代码及相关图片）

（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集是构造算符优先分析表的基础，而算符优先分析表的构造又是算符优先分析算法的基础。

因此，本程序的实现可以说是算符优先分析算法实现的基础。

目　录

一、课程设计任务及要求

课设目的

进一步培养学生编译器设计的思想，加深对编译原理和应用程序的理解，针对编译过程的重点和难点内容进行编程，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格，并综合使用程序设计语言、数据结构和编译原理的知识，熟悉使用开发工具VC/JAVA/C#/.NET。

总体要求

1.思想的正确性，采用合适的数据存储结构等。

2.程序实现的正确性，程序整体结构合理、编程风格规范等。

3.程序功能的完善程度，包括功能的基本实现、基本完善、完全实现4.工作认真、独立完成课设。

基本要求

设计一个由正规文法生成FirstVT集和LastVT集的算法动态模拟，实现以下功能输入一个文法G；

1.输出由文法G构造FIRSTVT集的算法；

2.输出FirstVT集；

3.输出由文法G构造LastVT集的算法；

4.输出LastVT集。

具体步骤

1、问题理解和分析

充分地分析和理解问题本身，弄清要求做什么。

2、确定解决问题的方法（设计）

主要是找到解决问题的主要思路，是怎么做。

在此阶段可考虑系统的功能和模块划分等。

3、详细设计和编码

确定算法的主要流程，再进行编程。

在此阶段应提醒学生程序可先在纸上写，尽量想清楚了再动手上机，在编程过程中注意程序结构的清晰性，避免出现很多明显的程序逻辑错误和语法错误，提高后面程序调试效率。

4、程序调试和运行

使学生掌握程序调试和排错的基本方法，增加编程的感觉和解决问题的成就感。

5、完成课程设计报告（使用华东交通大学课程设计报告，需学生自己购买）

二、需求分析

本课程设计的题目为“FirstVT集和LastVT集生成算法模拟”，它是算符优先分析算法中判断三种优先关系的关键。

算符优先分析算法是自底向上分析方法的一种。

所谓自底向上分析，也称移近——规约分析，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。

重复这一过程直到规约到栈中只剩文法的开始符号则为分析成功，也就确认输入串是该文法的句子。

而算符优先分析算法的基本思想只是规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。

本课程设计的要求只是构造FirstVT集和LastVT集，在此基础上扩充建造算符优先关系表。

三、设计思路

3.1基本算法

构造集合FIRSTVT（P）的算法

按FIRSTVT（P）的定义，可以用如下两条归则来构造：

（1）若有产生式Pa…或Qa…，则a∈FIRSTVT（P）

（2）若a∈FIRSTVT（Q），且有产生式PQ…，则a∈FIRSTVT（P）

构造算法：

建立一个二维布尔数组F[P,a]，使得F[P,a]为真的条件适当且仅当a∈FIRSTVT（P）;

构造算法

再用一个栈STACK，把所有初值为真的数组元素F[P,a]的符号对（P,a）全都放到栈中；算法如下：

（1）将布尔矩阵各元素置假；栈置空；

（2）按照归则

（1）查看产生式，对于Pa…或PQa..，置相应F[P,a]为真，符号对（P,a）入栈；

（3）按规则

（2），对栈施加如下操作：

弹出栈定符号对记作（Q,a），查看所有产生式是否有形如PQ…产生式，若有，且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集和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有推导关系Pa…；fist[i][j]代表非终结符vn[i]=P与非终结符vt[j]=Q有推导关系或PQa..。