编译原理课程设计--正规文法G转换为有穷自动机FA的程序设计

《编译原理课程设计--正规文法G转换为有穷自动机FA的程序设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉理工大学《编译原理》课程设计说明书学号：0120910680405课程设计题目正规文法G转换为有穷自动机FA的程序设计学院计算机学院专业软件工程班级0904班姓名杨杰指导教师何九周2011年12月30日29武汉理工大学《编译原理》课程设计说明书课程设计任务书学生姓名：杨杰专业班级：软件0904指导教师：何九周工作单位：计算机学院题目:正规文法G转换为有穷自动机FA的程序设计初始条件：程序设计语言:主要使用C语言的开发工具，或者采用LEX、YACC等工具，也可利用其他熟悉的开发工具。算法：可以根据《编译原理》课

2、程所讲授的算法进行设计。要求完成的主要任务:（包括课程设计工作量及其技术要求，说明书撰写等具体要求）1.明确课程设计的目的和重要性，认真领会课程设计的题目，读懂课程设计指导书的要求，学会设计的基本方法与步骤，学会如何运用前修知识与收集、归纳相关资料解决具体问题的方法。严格要求自己，要独立思考，按时、独立完成课程设计任务。2.主要功能包括：输入先行正规文法，根据输入文法判断是否为正规文法，判断产生的是确定型文法还是非确定型文法。判断出终结符号，非终结符号，输出自动机标准形式。3.进行总体设计，详细设计：包括算法的设

3、计和数据结构设计。系统实施、调试，合理使用出错处理程序。4.设计报告：要求层次清楚、整洁规范、不得相互抄袭。正文字数不少于0.3万字。包含内容：①课程设计的题目。②目录。③正文：包括引言、需求分析、总体设计及开发工具的选择，29武汉理工大学《编译原理》课程设计说明书设计原则（给出语法分析方法及中间代码形式的描述、文法和属性文法的设计），数据结构与模块说明（功能与流程图）、详细的算法设计、软件调试、软件的测试方法和结果、有关技术的讨论、收获与体会等。④结束语。⑤参考文献。⑥附录：软件清单（或者附盘）。时间安排：消化

4、资料、系统调查、形式描述1天系统分析、总体设计、实施计划3天撰写课程设计报告书1天指导教师签名：2011年12月30日系主任（或责任教师）签名：2011年12月30日29武汉理工大学《编译原理》课程设计说明书摘要4一、引言5二、设计原理6三、设计方案131、总体设计132、详细设计14四、程序调试与体会24五、运行结果24五、结论26六、参考文献2629武汉理工大学《编译原理》课程设计说明书摘要如果我们把一个程序设计语言的每类单词都视为一种语言，那么，一般说来，各类单词的词法都能用相应的正规文法(左线性文法或右线

5、性方法)来描述。正规文法是左线性文法和右线性文法的统称。它们都是Chomsky分类下的3型文法。由正规文法产生的语言称为正规集。一般的高级语言转化成机器语言都要经过词法分析、语法分析、语义分析、中间代码的生成与目标代码的生成。其中，在词法分析环节中可以用LEX等语言来自动进行词法分析，在其分析过程中，要用到正规式、DFA与NFA之间的互相转化的过程。本课程设计从理论和实践上分析和实现正规式到NFA转化的方法及其C程序实现。关键词：正规文法、确定化有限自动状态机、非确定的有限自动状态机、自动机类型判定、29武汉理工

6、大学《编译原理》课程设计说明书《编译原理》课程设计——正规式G转化成有穷自动机FA一、引言编程语言是由一个个句子构成的，而句子是由一个个单词构成的，因此单词是构成程序语言的基本单位。词法就是单词的构成法则，用这些法则来检查程序的单词构成是否合乎词法规则。进行词法分析的形式化工具目前主要有正规式、DFA与NFA，而且正规式、DFA、NFA在表现能力上是等价的，可以互相转化。正规式是一种形式化表达，而DFA和NFA是一种图形化的表达。二、设计原理1、文法形式如果我们把一个程序设计语言的每类单词都视为一种语言，那么，一

7、般说来，各类单词的词法都能用相应的正规文法(左线性文法或右线性方法)来描述。例如，某种语言中的标识符可定义为：〈标识符〉→〈标识符〉字母〈标识符〉→〈标识符〉数字〈标识符〉→字母如果我们把“字母”和“数字”视为终结符号，则上述产生式均为左线性文法中的产生式。又如，把C语言中〈无符号数〉的定义稍加改写，我们可得到如下的产生式(请注意，在下列产生式中，d是一个“字符类”记号，它代表0至9中的任一数字)：〈无符号数〉→d〈余留无符号数〉〈无符号数〉→·〈小数部分〉〈无符号数〉→d29武汉理工大学《编译原理》课程设计说明

8、书〈余留无符号数〉→d〈余留无符号数〉〈余留无符号数〉→·〈十进小数〉〈余留无符号数〉→E〈指数部分〉〈余留无符号数〉→·〈余留无符号数〉→d〈十进小数〉→E〈指数部分〉〈十进小数〉→d〈十进小数〉〈十进小数〉→d〈小数部分〉→d〈十进小数〉〈小数部分〉→d〈指数部分〉→d〈余留整指数〉〈指数部分〉→+〈整指数〉〈指数部分〉→-〈整指数〉〈指数部分〉→d〈整指数〉→d〈余