课程设计任务书3课案.doc

《编译原理》课程设计指导书 一、课程设计的目的 本次课程设计的时间为2周，目的是通过实际的题目如：词法分析、语法分析、代码优化等，使学生了解和掌握编译程序的工作原理，同时培养学生用相关的程序设计语言进行程序设计，实现编译的功能，从而提高学生的综合能力。 二、设计名称：小型语言编译器的设计/编译技术的计算机实现。 三、设计要求 本次课程设计有两种选择：合作完成与独立完成。若选择合作完成，则需自行组合5位学生成为一个小组，小组成员合作完成一个小型编译器（见设计内容题目一）。若选择独立完成，则从设计内容题目二的13个题目中任选一个独立实现。这13个题目，都有一定的工作量，涵盖本课程内容和实际应用相关的主要技术。 四、设计内容 题目一：词法、语法分析器的设计。 通过设计、编制、调试一个对于小型语言词法的词法分析程序，加深对词法分析原理的理解，并实现输出单词序列的词法检查和分析。（建议1名学生完成） 设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解。（建议1名学生完成） 题目二：下列13个题目任选。 选题说明：可以从下列题目中任选一题，每个题目按难度设定不同的参考分数，上机成绩采用100分制。题目指定的参考分数仅适用于上机程序部分，实验报告成绩有自己的标准。 1．文法的计算机表示 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 文法中的空字符串统一使用@表示。 包括各种可能出现的文法描述方法。 使用定义描述文法 只用产生式描述文法 用大写字母和小写字母分别表示非终结符和终结符 用带尖括号的和不带尖括号分别表示非终结符和终结符 产生式可以使用-或::=表示的方法 对给定文法判断是乔姆斯基文法中的哪一种文法 文法要求以文本文件方式输入，不同的文法只要修改文件即可。不允许使用键盘输入文法。 2．自动机的形式定义 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 自动机中的空字符串统一使用@表示。 分别使用定义和状态转换矩阵方法表示自动机，并且两种表示方法可以相互转化。 自动机的状态个数和状态转换函数的个数可以任意指定并随意修改，即可以增加或减少状态或状态转换函数。 判定是确定的自动机还是不确定的自动机。 采用文本文件方式存储自动机，若修改自动机可以仅通过修改该文本文件即可完成。程序可以读取文本文件保存的自动机。 3．自动机的图形表示 设计要求： 可以使用任何语言来完成，例如：Java、C++。 自动机中的空字符串统一使用@表示。 自动机的状态个数和状态转换函数的个数可以任意指定并随意修改，即可以增加或减少状态或状态转换函数。 使用状态转换图表示自动机。 要求设计一个具有简单的绘图功能的程序，在可视化界面上绘制一个状态转换图。 采用文本文件方式存储自动机，若修改自动机可以仅通过修改该文本文件即可完成。程序可以读取文本文件保存的自动机。 附加要求（可以不完成）： 自动机的定义形式、状态转换图和状态转换矩阵三种形式可以相互转化。 4．自动机的确定化和最小化 设计要求： 可以使用任何语言来完成，例如：Java、C++。 文法中的空字符串统一使用@表示。 以文件方式读取自动机。 判断读取的自动机是确定的还是不确定的自动机。 若是不确定的自动机，将自动机确定化。 将确定化后的自动机最小化。 5．有穷自动机与正规文法的相互转换 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 文法和自动机中的空字符串统一使用@表示。 以文件方式读取自动机和正规文法。 判断读取的文法是否是正规文法。 完成有穷自动机与正规文法的相互转换。 6．LL(1)文法的实现 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。 分别求出每一个非终结符FIRST 集FOLLOW集。 画出预测分析表。 判定读入的文法是否是LL(1)文法。 给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。 查出文法中是否含有左递归或左公因子。若有则消除左公因子和左递归，并给出分析过程。 7．算符优先分析法的实现* 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。 分别求出每一个非终结符的FIRSTVT和LASTVT集。 画出算符优先关系表。 判定读入的文法是否是算符优先文法。 给定的任意符号串判定是否是文法中的句子，将分析过程用计算机打印出来。 8．LR(0)分析法的实现 设计要求： 可以使用任何语言来完成，例如：Java、C、C++。 文法采用常用的方式进行描述，例如：S→aA。 以文件方式读取文法。 求出项目集规范族（即所有的状态）。 给出