内容发布更新时间 : 2024/11/16 23:56:07星期一 下面是文章的全部内容请认真阅读。

关于《编译原理》课程设计的有关说明

《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。大家在进行课程设计时，可从所学内容中选择某个主题，抽象成一个模型，可适当进行简化。也可按提供给大家的一些参考选题进行设计。软件开发选择C/C++语言（也可以是你熟悉的任何语言）。最后每位同学都要认真撰写设计报告，格式要规范，内容要详尽，包括：设计题目，设计目的，设计内容，设计要求，问题的描述及解决的方法、原理、思想、算法（流程图），设计的输入和输出形式，测试、模拟的结果（屏幕拷贝、生成结果的打印输出），总结（体会），源程序清单，等等。

大家应把该门课的课程设计当成对自己学习效果的一次检验，当成是为在大四能够顺利完成毕业设计的一次基本功训练。希望每个同学尽可能不要都选择完全一样的题目。大家可以自主选题，或选择我提供的题目，也可以把几个题目合起来做（如开发一个小的编译器）。鼓励选择有一定技术难度、有一定工作量、综合性较强的题目，在评定成绩时将会给予好的成绩。

编译原理课程设计部分参考选题： 1． 题目： FORTRAN语言实型常数识别程序设计

设计内容及要求： 将教材P.41的图3.2(d)识别FORTRAN实型常数的状态

转换图用程序实现。程序能够从用户输入的任意一个字符串中识别出FORTRAN实型常数，显示输出。

2． 题目： 简化的FORTRAN语言词法分析程序设计

设计内容及要求：将教材P.42上的表3.1的词法分析器构造出来，限制

条件如教材所述。保留字的识别按标识符一样识别，通过查找保留字表区分是保留字还是标识符。程序能够从用户输入的源程序中，识别出的单词符号，并用二元式表示，显示输出或输出到文件中。

3． 题目： ε-CLOSURE(I)构造算法的程序实现

设计内容及要求：将ε-CLOSURE(I)构造算法用程序实现。要求：对任意

给定的一个NFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)的某一

个状态子集I，显示输出构造出的ε-CLOSURE(I)。

4． 题目： 从右线性文法构造与之等价的有限自动机的程序实现

设计内容及要求：构造一转换程序，实现将用户任意给定的右线性文法，

转换为与之等价的有限自动机FA M，输出其状态转换矩阵（显示输出或输出到文件中）。

5． 题目： 从有限自动机构造与之等价的右线性文法的程序实现

设计内容及要求：构造一转换程序，实现将用户任意给定的有限自动机FA

M，转换为与之等价的右线性文法，显示输出或输出到文件中。 6． 题目： 有限自动机的状态转换图显示程序的实现

设计内容及要求：构造一程序，实现：将任一给定的有限自动机M(其状态

转换矩阵及初态、终态信息保存在指定文件中)，在屏幕上显示输出M的状态转换图。程序应具有通用性，状态节点在屏幕上的分布应合理、美观。 7． 题目： 从NFA构造与之等价的正规式r的程序实现

设计内容及要求：对给定的任意NFA M(其状态转换矩阵及初态、终态信息

分别保存在指定文件中)。构造一程序，从NFA构造与之等价的正规式r，并显示输出。

8． 题目： 构造正规式r1|r2（或运算）的NFA的程序实现

设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、

M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1|r2（或运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。

9． 题目： 构造正规式r1r2（连接运算）的NFA的程序实现

设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、

M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1r2（连接运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。 10．

题目： 构造正规式r*（闭包运算）的NFA的程序实现

设计内容及要求：对给定的正规式r，已知其NFA为M(其状态转换矩阵及

初态、终态信息保存在指定文件中)。构造一程序，由此程序构造正规式r*（闭包运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。 11．

题目： 基于语法制导构造正规式的NFA

设计内容及要求：首先构造一个语法分析程序，实现对任意正规式的语法

分析。语法分析方法采用自下而上的分析方法（如算符优先分析，或LR分析）。在此语法分析器的基础上，按照语法制导的思想，增加构造NFA的功能。生成的NFA将其状态转换矩阵及初态、终态信息保存在指定文件中。进一步实现把NFA确定化为DFA 的算法(其状态转换矩阵及初态、终态信息保存在指定文件中)。 12．

题目： DFA M状态最少化的程序实现

设计内容及要求：构造一程序，实现：将给定的DFA M(其状态转换矩阵及

初态、终态信息保存在指定文件中)的有限状态集S划分成若干互不相交的子集，使得：任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。 13．

题目： 把NFA确定化为DFA 的算法实现

设计内容及要求：构造一程序，实现：将给定的NFA M(其状态转换矩阵及

初态、终态信息保存在指定文件中)，确定化为DFA M’。（要先实现ε-CLOSURE函数和Ia函数）。输出DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。 14．

题目： 基于贪心算法的DFA 的程序实现

设计内容及要求：采用贪心算法实现教材P.62表3.5的DFA，要求从输入

串中匹配最长的子串。输出所有识别出的符号串及其词形。 15．

题目： 根据句型的推导构造其语法分析树的程序实现

设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的推

导序列，生成该句型的语法分析树并显示输出。程序应具有通用性，语法分析树的节点在屏幕上的分布要合理、美观。 16．

题目： 从语法分析树构造句型所有的推导的程序实现

设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的语

法分析树（其表示存于指定文件中），生成该语法分析树中包含的该句型的所有推导（显示输出）。 17．

题目： 递归下降分析程序的实现 设计内容及要求：

对文法 G: E→E+T|T 构造出G的递归下降分析程序。程序显示输出

T→T*F|F 匹配过程（即自上而下生成语法分析树的步骤，

F→（E）|i 输出各匹配产生式序号即可）。

18．

题目： 集合FIRST(X)构造算法的程序实现

设计内容及要求：构造一程序，实现教材P.78的FIRST(X)集合的构造算