摘 要

本文借助unity对词法分析自动构造的过程进行了模拟，主要模拟了正规式转化为NFA，NFA转化为DFA以及DFA的最简化的关键算法和过程。

论文主要研究了词法分析自动构造过程的原理和算法，着重论述了正规式的形式化定义，正规式如何表示语言的单词规则，有穷自动机在编译技术中的作用，有穷自动机与DFA、NFA的关系，如何使用递归构造的方法由正规式转化得到相应的NFA，如何使用“子集法”将NFA转化得到相应的DFA，以及如何将DFA最简化的过程。在这些原理的基础之上，选择合适的数据结构，进行相应的封装，采用合适的方法实现了这些算法。

在具体的实现上，将程序的结构分成三层，分别为表示层，控制层和算法层，三个层次之间通过接口关系连接在一起运作，减小了程序的耦合性，同时使得程序更加易读易维护。

关键词：词法分析；自动构造；模拟器；正规式；DFA；NFA

Abstract

This paper uses unity to simulate the automatic construction process of lexical analysis. It mainly simulates the most simplified key algorithms and processes for transforming regular expression to NFA and NFA to DFA and simplifying DFA.

This thesis mainly studies the principle and algorithm of the automatic construction process of lexical analysis. It focuses on the formal definition of the formal, how the regular expression represents the word rules of the language, the role of the finite automata in the compilation technology, finite automata and DFA. The relationship between the NFA and the NFA, how to use the recursive construction method to get the corresponding NFA from the formal conversion, how to use the "subset method" to transform the NFA into the corresponding DFA, and how to simplify the DFA process. Based on these principles, select appropriate data structures, package them accordingly, and implement these algorithms in a suitable way.

In the specific implementation, the structure of the program is divided into three layers: the presentation layer, the control layer, and the algorithm layer. The three layers are connected and operated through the interface relationship, which reduces the coupling of the program and makes the program easier to read and maintain.

Key Words：lexical analysis；automatic construction；simulator； regular expression; DFA; NFA

目 录

第1章 绪论 6

1.1 论文工作的意义 6

1.2 主要工作内容 6

1.3 论文的组织结构 7

1.4 本章总结 7

第2章 词法分析自动构造原理 8

2.1 词法分析 8

2.2 正规式 8

2.3 有穷自动机 9

2.4 确定的有穷自动机DFA 9

2.5 不确定的有穷自动机NFA 10

2.6 NFA转化为等价的DFA 10

2.7 DFA化简 12

2.8 正规式转换为NFA 13

2.9 本章小结 13

第3章 词法分析自动构造模拟器的算法实现 14

3.1 正规式的表示 14

3.2 NFA的表示 14

3.3 正规式转化为NFA 15

3.4 DFA的表示 18

3.5 NFA转化为DFA 19

3.6 DFA的最简化 21

3.7 由最简化的DFA构造词法分析驱动表 21

3.8 词法分析自动构造模拟器的架构 22

3.8.1 表示层 23

3.8.2 算法层 23

3.8.3 控制层 23

3.9 本章小结 24

第4章 总结与展望 25

4.1 总结 25

4.2 展望 26

参考文献 27

致 谢 29

绪论

论文工作的意义

词法分析的主要工作是按照某种语言给定的词法规则从源代码中逐个识别出有意义的单词，把字符串形式的源代码转换成有实际意义的内部表示—也就是单词。这是程序编译的基础，也是程序编译的第一阶段。词法分析技术在信息检索，命令语言的识别，报文格式的识别中也有广泛的应用。然而，当前编译原理的课程中，教师只能以手工构造或者静态的课件来讲解实例。手工计算费时费力，不能给人完整的印象。静态的课件缺乏交互，效果不佳。编译原理书籍中讲解词法分析的部分，大多偏重原理的讲解，没有具体且详尽的实例讲解；比较成熟的测法分析自动生成工具用法复杂，不易在课堂中展示，且使用时只能输出最终的DFA，不能呈现词法分析程序的各个构造过程。词法分析模拟器能够弥补以上的不足，生动的表现出词法分析自动构造的过程。同时，通过词法分析自动构造程序，能够加深对于编译原理技术尤其是词法分析技术的理解，同时还能提升编程的能力。

主要工作内容

本文借助unity对词法分析自动构造的过程进行了模拟，主要模拟了正规式转化为NFA，NFA转化为DFA以及DFA的最简化的关键算法和过程。

论文主要研究了词法分析自动构造过程的原理和算法，着重论述了正规式的形式化定义，正规式如何表示语言的单词规则，有穷自动机在编译技术中的作用，有穷自动机与DFA、NFA的关系，如何使用递归构造的方法由正规式转化得到相应的NFA，如何使用“子集法”将NFA转化得到相应的DFA，以及如何将DFA最简化的过程。在这些原理的基础之上，选择合适的数据结构，进行相应的封装，采用合适的方法实现了这些算法。

在具体的实现上，将程序的结构分成三层，分别为表示层，控制层和算法层，三个层次之间通过接口关系连接在一起运作，减小了程序的耦合性，同时使得程序更加易读易维护。

论文的组织结构

论文第一章是绪论，主要主要介绍论文工作的意义，主要工作内容和论文的组织结构，指出当前在词法分析自动构造模拟器的相关领域存在的一些问题和本毕业设计能够解决的问题，并简要的概括了本毕业设计采用了什么方法进行系统的设计与实现。