08级编译课程设计题目.doc

编译原理课程设计题目
D类题目 1
1、文法的表示 1
2、自动机的表示 2
3、自动机与正规文法间的相互转化 2
4、正规文法与正规式间的相互转化 2
5、符号串的最左推导和最右推导 2
6、基本块的划分 2
7、循环查找 3
C类 3
1、构造语法树 3
2、符号表的线性组织 3
3、符号表的排序组织 3
4、PL/0语言的词法分析程序 4
5、使用逆波兰式方法设计一个计算器 4
6、非LL(1)文法到LL(1)文法的等价变换 4
B类 4
1、自动机的确定化和最小化 4
2、自动机与正规式间的相互转化 5
3、符号表的散列组织 5
4、C语言的词法分析程序 5
5、使用算符优先分析方法设计一个计算器 5
6、使用LR(0)分析方法设计一个计算器 6
7、使用预测分析方法设计一个计算器 6
A类 6
1、预测分析法在PL/0语言编译器中的应用 6
2、PL/0语言编译器改进 6
3、PL/0语言编译器的中间代码生成 7
4、LL(1)文法和预测分析方法 7
5、算符优先分析法研究 7
6、LR(0)分析法研究 8
7、自动机的状态转换图表示 8
8、局部优化的实现 8
课程设计报告的撰写规范及要求 9

13
选题说明
² 学委负责把下列题目分发下去，学生在三个班级中任意组合，3-4人组成一个课题小组，共同完成选定的题目。三个班加在一起每道题目最多可以有两个小组选择。每个题目根据难度具有不同的分类，A类最难，综合能力较强，依次类推。
² 课程设计报告要求字数在2000字以上（不包括程序代码），报告设计格式参看《2008级编译技术课程设计报告模版》。
² 源程序及课程设计报告检查完毕后，于1月5日前一起发送到邮箱：
compiler2011@。
课程设计题目说明
课程设计题目分为4种难度，分别为A类、B类、C类、D类。最高分数依次为100，90，85，75。

【注意】
无论下列哪一个题目，若涉及到输入（文法/自动机/表达式/源程序等等）不能通过键盘手动输入，必须通过文件的方式输入到程序中。
D类题目
1、符号串的最左推导和最右推导
要求：
1. 给定文法和符号串；
2. 给出该符号串的最左推导、最右推导；
3. 文法要求可以用文件方式和直接输入两种方法。
2、基本块的划分
要求：
1. 从文件中读取任意一组四元式；
2. 找出中间代码的入口语句；
3. 划分出程序的基本块。
3、循环查找
要求：
1. 程序流图可以使用二维数组表示出结点间的关系；
2. 求出所有结点的必经结点集；
3. 找出流出中的回边；
4. 给出每一个回边所对应的循环。
4、使用逆波兰式方法设计一个计算器
1. 计算器必须能够完成加、减、乘、除、幂、括号（）等运算符号；
2. 将一个中缀表达式转化为逆波兰式；
3. 根据逆波兰式的计算方法计算出表达式的值；
5、符号表的线性组织
要求：
1. 确定符号表的单表结构的总体组织方式，即所有的标识符都在一个符号表内；
2. 设计符号表的顺序为线性组织方式。
3. 设计符号表的属性，需要包括：符号名、数据类型、层次、在内存单元中的位置（假设数据从该过程活动记录的第3个字节开始，前3个空间保存了返回地址、存取链等信息）
4. 当读入的源程序为C语言程序/或PL/0语言 时，设置一个断点，获得到达断点时的符号表的内容；

6、符号表的排序组织
1. 确定符号表的单表结构的总体组织方式，即所有的标识符都在一个符号表内；
2. 设计符号表的顺序为排序组织方式。
3. 设计符号表的属性，需要包括：符号名、数据类型、层次、在内存单元中的位置（假设数据从该过程活动记录的第3个字节开始，前3个空间保存了返回地址、存取链等信息）
4. 当读入的源程序为C语言程序/或PL/0语言 时，设置一个断点，获得到达断点时的符号表的内容；
5. 设计函数或方法完成线形表的插入和删除操作。
C类
1、构造语法树
要求：
1. 给定文法和符号串；
2. 给出该符号串的语法树；
3. 文法要求可以用文件方式和直接输入两种方法。
2、符号表的散列组织
1. 确定符号表的单表结构的总体组织方式，即所有的标识符都在一个符号表内；
2. 设计符号表的顺序为散列组织方式，查阅资料构造一个好的散列函数。
3. 设计符号表的属性，需要包括：符号名、数据类型、层次、在内存单元中的位置（假设数据从该过程活动记录的第3个字节开始，前3个空间保存了返回地址、存取链等信息）
4. 当读入的源程序为C语言程序/或PL/0语言 时，设置一个断点，获得到达断点时的符号表的内容；
设计函数或方法完成线形表的插入和删除操作。
3、PL/0语言的词法分析程序
要求：
1. 写一个能够完成PL/0语言的词法分析的程序；
2. 将源程序文件中的单词识别出该单词是哪一个保留字、或者哪一个符号、或者是标识符、或者是常数；
3. 将分析的结果以文件的方式输出；
4. 该词法分析程序可以过滤掉多行注释 /* */和单行注释//。
4、非LL(1)文法到LL(1)文法的等价变换
要求：
5. 文法可以只采用产生式的方式进行描述；
6. 查出文法中是否含有左递归或左公因子；
7. 消除左公因子，并给出分析过程；
8. 消除左递归，并给出分析过程。
9.
5、使用LR(0)分析方法设计一个计算器
要求：
1. 计算器必须能够完成加、减、乘、除、幂、括号（）等运算符号；
2. 将算术运算表达式写成LR(0)文法；
3. 给定任意符号串，判断其是否为正确的表达式，若是给出计算结果；
4. 进行语法分析必须采用LR(0)分析方法。
6、使用预测分析方法设计一个计算器
要求：
1. 计算器必须能够完成加、减、乘、除、括号（）等运算符号；
2. 将算术运算表达式写成LL(1)文法；
3. 给定任意符号串，判断其是否为正确的表达式，若是给出计算结果；
4. 进行语法分析必须采用预测分析方法。
7、使用算符优先分析方法设计一个计算器
1. 计算器必须能够完成加、减、乘、除、幂、括号（）等运算符号；
2. 将算术运算表达式写成算符优先文法；
3. 给定任意符号串，判断其是否是正确的表达式，若是给出计算结果；
4. 进行语法分析必须采用算符优先分析方法。
8、C语言的词法分析程序
要求：
1. 写一个能够完成C语言的词法分析的程序；
2. 将源程序文件中的单词识别出该单词是哪一个保留字、或者哪一个符号、或者是标识符、或者是常数；
3. 将分析的结果以文件的方式输出；
4. 该词法分析程序可以过滤掉多行注释 /* */和单行注释//。
B类
1、自动机的确定化和最小化
要求：
1. 自动机以状态转换矩阵的方式在计算机内部进行表示；
2. 根据NFA确定化的方法，将NFA确定化；
3. 判断自动机是否以最小化，若不是将其最小化；
4. 以状态转换矩阵的方法表示出确定化、最小化后的自动机。
2、自动机与正规式间的相互转化
要求：
1. 自动机以状态转换矩阵的方式在计算机内部进行表示；
2. 将给定的任意自动机转化成等价的正规式；
3. 将给定的任意正规式转化成等价的自动机；
4. 自动机要求以文件方式输入；
5. 正规式可以在程序中输入。

3、预测分析法在PL/0语言编译器中的应用
要求
1. 将PL/0语言编译器中的语法分析部分修改，采用预测分析方法；
2. 用机器内码表示出PL/0语言文法的终结符和非终结符；
3. 产生式可以直接用机器内码以二维数组的方法存储到编译器中；
4. 修改PL/0编译器，自己定义一个函数专门用来完成语法分析。

4、PL/0语言编译器改进
要求：
1. 可以过滤掉行注释// 和段注释 /* */；
2. 字母不区分大小写
3. 增加数据类型：integer整型和real实型，包括：常数和变量。
4. 变量定义修改为: var a,b:integer；c,d:real;
5. 使用图形界面进行处理
5、LL(1)文法和预测分析方法
要求：
1. 文法使用产生式来定义；
2. 分别求出文法中每一个非终结符的FIRST 集、FOLLOW集和SELECT集；
3. 画出预测分析表；
4. 判定给定的文法是否是LL(1)文法；
5. 给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。
6、算符优先分析法研究
1. 文法使用产生式来定义；
2. 分别给出每一个非终结符的FIRSTVT和LASTVT集。
3. 画出算符优先关系表；
4. 判定给定的文法是否是算符优先文法；
5. 给定符号串判定是否是文法中的句子，分析过程用分析表格的方式打印出来。
A类
1、PL/0语言编译器的中间代码生成
要求：
1. 要求用递归子程序法/或预测分析法实现对表达式、各种说明语句、控制语句进行语法分析。
2. 若语法正确，则用语法制导翻译法进行语义翻译：对说明语句，要求将说明的各符号记录到相应符号表中；对可执行语句，应产生出四元式中间代码并填写到三地址码表中；
3. 若语法错误，要求指出出错性质和出错位置（行号）。出错处理应设计成一个出错处理子程序。
2、LR(0)分析法研究
1. 文法使用产生式来定义；
2. 给出项目集规范族（即所有的状态）。
3. 给出状态间的关系。
4. 给出LR(0)分析表。
5. 给定符号串判定它是否是文法中的句子，分析过程用分析表格的方式打印出来。
3、自动机的状态转换图表示
要求
1. 要求设计一个具有绘图功能的程序，可以手工以状态转换图的方式绘制自动机；
2. 图形化的自动机可以保存，读取；
3. 根据状态转换图得出自动机的状态转换矩阵；
4. 根据状态转换图，自动绘制出状态转换图（可以不完成）。
4、局部优化的实现
要求：
1. 设计出划分基本块的算法；
2. 在每一个基本块中实现：合并已知量、删除多余运算和删除无用赋值三种局部优化；
3. 设计构造基本块的DAG图的算法，以及将DAG图还原实现基本块的优化的算法。
5、C语言文本编辑器
要求：
1. 设计一个类似UltraEdit的工具，将打开或输入的C语言源程序中的代码，以不同的颜色进行显示。例如：关键字，绿色；数字，蓝色等。
2. 文件及文件夹目录结构在窗口的左侧以类似树型目录的方式显示出来，即显示出文件的层次结构关系，并且将不同文件在窗口中不同的标签页分别显示。
3. 需要显示的内容可以进行设置，例如：关键字默认为一种颜色，在“设置”对话框中可以设置关键字的颜色。最好能解决不同颜色的冲突问题，至少应该提示，已经有这种颜色了。

6、帮助自动生成工具
设计一个类似Doc++这样的工具，将源文件中的注释倒出来形成一个帮助文档，可以是html格式的
要求：
1. 提供一个文档编辑窗口，可以在此窗口中打开已有文件或新建文件，文件类型可以为*.c和*.java的源文件；
2. 根据源文件中的注释，导出文件和函数的说明文件并将其形成文本文档或html文件；
3. 可以给出一组包含多级文件夹的所有文件，并给出其文件包含关系的树形目录
4. 在每个单独的帮助文件中，先给出此文件的总体说明及每一个函数的简单总表，然后给出每个函数的具体的帮助信息。
5. 打开的文件及文件夹在左侧以属性结构显示出来，不同的文件分别以不同的标签页显示出来。
7、变量检查工具
实现对C语言中全局变量和共享变量的检查。
要求：
1. 检查全局变量是否是必须的。包括：该全局变量是否被引用过；全局变量是否只在1个函数内被引用。
2. 若某一全局变量从来没有被引用过，则可以将其删除
3. 若某一全局变量只在一个函数内被引用和定值，是否可以将其修改为局部变量
4. 当全局变量仅用于1个文档中，是否可以将其修改为静态全局变量

提示：可以通过符号表对变量的存储类别的定义，来讨论变量的使用点，从而确定这些变量是否应该为局部变量、静态全局变量或全局变量。
8、C语言过程活动记录的设计
要求：
1. 查阅相关资料，确定C语言的存储管理策略；
2. 设计C语言的过程活动记录，可以设计简单的C语言，可以参考Minus-c来设计。
3. 分析符号表的内容和管理，并通过实例考察。给定几个简单的程序，完成变量的取值和赋值，查看是否能够正确的存取变量。
9、指针检查工具
利用符号表，检查C语言中对指针的使用。需要完成以下的检查，并指出可能出错的位置。假设源程序已经编译通过，即不用对其进行语法的检查了，只检查指针变量的语义是否正确。
要求进行以下的检查：
1. 指针变量是否初始化；
2. 指针类型是否定义正确；
3. 使用前是否已经申请的内存；
4. 引用是否正确，是否引用了释放掉的内存空间

10、数组越界检查工具
检查C语言中对数组的使用。大多数的C语言编译器都不对数组越界进行检查。分析其原因，并想出解决办法。
1. 列出C语言数组产生越界的原因；
2. 设计工具专门检查是否有数组越界问题，并指出其位置。

课程设计报告的撰写规范及要求
一、课程设计的版面
课程设计统一用计算机录入并打印。
纸张规格为A4，版面上、下空2.54cm，左、右空3.17cm、装订线0.5cm，位置为左装订
页数用小五号字下居中标明。
二、结构及要求
课程设计报告的组成及装订顺序：
封面、目录、正文、参考文献、附录（源代码）。
1．封面
包括题目、姓名、班级、指导教师、联系方式
2．目录
目录要求层次清晰，且与正文中标题一致。包括正文主要层次标题、参考文献、附录。
3．正文
（1）正文的内容
正文部分包括：前言、报告主体和结论。要求文章结构严谨，语言流畅，内容正确。
前言作为开场白，要以简短的篇幅，说明课程设计工作的基本原理。
报告主体是核心部分，占主要篇幅，要求文字简练，条理分明，重点突出，概念清楚，论证充分，逻辑性强。分别阐述自己在课程设计过程中是如何实现的，相关的数据结构、分析过程、存在问题等要阐述清楚，报告正文中的使用的源程序代码，除为了阐述数据结构和算法而必须使用的代码外，不能占主要部分，最好不超过10%。
报告中要求有程序运行时的界面，界面直接从计算机屏幕上抓图获得，程序运行示例2个以上（通过示例可以说明程序的功能），及相应的运行结果。
结论是整个课程设计报告的总结，应以简练的文字说明通过课程设计，对编译原理课程的理解和新的认识，在课程设计中实现的功能和取得的成果，以及存在的问题等。
正文中引用文献号用方括号“[ ]”括起来置于引用文字的右上角，按上标书写。
（2） 对正文内容及篇幅的要求
课程设计的汉字的数量要求在1500字以上。
（3）正文的层次划分和编排方法
正文是论文的主要组成部分，题序层次是文章结构的框架。章条序码统一用阿拉伯数字表示，题序层次可以分为若干级，各级号码之间加一小圆点，末尾一级码的后面不加小圆点，层次分级一般不超过4级为宜，各级与上下文间均单倍行距。示例如下：
报告题目：居中放置，并且距下文双倍行距。 （黑体一号字）
正文各层次内容：单倍行距。
（宋体小四号字，英文用Courier New 字体小四）
题序层次的题序和题名：（下面格式不严格要求）
第一级(章) 1. 2. 3. … （黑体小二号字）
第二级 (条) 1.1,1.2,… 2.1,2.2,… 3.1,3.2,… （黑体小三号字）
第三级 (条) 1.1.1,1.1.2,…1.2.1,1.2.2,… （黑体四号字）
第四级 (条) 1.1.1.1,1.1.1.2,…1.2.2.1,1.2.2.2,…… （黑体小四号字）
题序层次编排格式为：章条编号一律左顶格，编号后空一个字距，再写章条题名。题名下面的文字一般另起一行，也可在题名后，但要与题名空一个字距。如在条以下仍需分层，则通常用a，b，…或1),2),…编序，左空2个字距。
4．图表和公式
（1）图表
报告中的选图及制图力求精炼。所有图表均应精心设计并用绘图笔绘制，不得徒手勾画。各类图表的绘制均应符合国家标准。报告中的表一律不画左右端线，表的设计应简单明了。图表中所涉及到的单位一律不加括号，用“,”与量值隔开。图表均应有标题，并按章编号（如图1-1、表2-2等）。图表标题均居中书写，字号比正文小一号。
（2）公式
公式统一用英文斜体书写，公式中有上标、下标、顶标、底标等时，必须层次清楚。公式应居中放置，公式前的“解”、“假设”等文字顶格写，公式末不加标点，公式的序号写在公式右侧的行末顶边线，并加圆括号。序号按章排，如“（1-1）”、“（2-1）”。公式换行书写时与等号对齐。
5．参考文献（不严格要求）
参考文献是报告中引用文献出处的目录表。凡引用本人或他人已公开或未公开发表文献中的学术思想、观点或研究方法、设计方案等，不论借鉴、评论、综述，还是用做立论依据、学术发展基础，都应编入参考文献目录。直接引用的文字应直录原文并用引号括起来。直接、间接引用都不应断章取义。
参考文献的著录方法采用我国国家标准GB7714-87《文后参考文献著录规则》中规定采用的“顺序编码制”，中外文混编。报告中，引用出处按引用先后顺序用阿拉伯数字和方括号[ ]放在引文结束处最后一个字的右上角作为对参考文献表相应条目的呼应。文后参考文献表中，各条文献按在报告中的文献序号顺序排列。各类文献的著录格式如下：
(1) 专著
顺序号 著者.书名.版本.其他责任者.出版地:出版者,出版年,文献数量
示例:1 夏小华,高为柄.非线性系统控制及解耦.第2版.北京:科学出版社,1997
(2) 期刊
顺序号 作者.题名.其他责任者.刊名,年,卷(期):在原文献中的位置
示例:2 高为柄,程勉,夏小华.非线性控制系统的发展.自动化学报,1991,17(4):513～523
(3) 论文集
顺序号 作者.题名.见:编者.文集名.出版地:出版者,出版年. 在原文献中的位置
示例:3 Fox R L, Willmert K D.不等式约束的连杆曲线最优化设计.见:机构学译文集编写组. 机构学译文集.北京:机械工业出版社,1982.232～242
(4) 技术标准
顺序号 标准代号 标准顺序号—发布年 标准名称
示例:4 GB3100～3102—93 量和单位
(5) 学位论文
顺序号 作者.题名:[学位论文].保存地:保存者,年份
示例:5 陈淮金.多机电力系统分散最优励磁控制器的研究:[学位论文].北京:清华大学电机工程系,1988
(6) 会议论文
顺序号 作者.题名.会议名称,会址,会议年份
示例:6 夏小华,高为柄.稳定设计中的分解和参数化方法.全国控制与决策会议,黄山,1993(10)．附录
未尽事宜可将其列在附录中加以说明。原始测定结果、分析报告、图表、测试报告单、译文等，均可列在附录中，附录序号用“附录A、附录B”等字样表示。