摘 要

编译原理是研究如何让计算机理解和执行编程语言的理论，词法分析是编译原理的第一个过程，目的是将源代码中的单词识别为某个具有特定含义的标识，它涉及到自动机理论、正则语言理论，难度较大。且传统的词法分析系统工程性强，难以上手。

本文从需求或目的的角度，结合实例给出了词法分析过程中用到算法的理解与具体实现方法，并基于此通过面向对象设计给出一个可配置的词法分析器的具体实现，并实现相关算法中所有类型自动机及状态转移表的可视化展示。

本文所给出的词法分析系统及算法的实现和数据的可视化都经过单元测试和手工测试，测试的结果可表明论文给出实现的正确性。

关键词：编译原理；词法分析；可配置词法分析器；可视化

ABSTRACT

Compiling principle is the theory of how to make computer understand and execute programming language. Lexical analysis is the first process of compiling principle. The purpose is to recognize words in source code as a sign with specific meaning. It involves automata theory and regular language theory, which is very difficult. And the traditional lexical analysis system is very engineering and difficult to use.

From the point of view of requirement or purpose, this paper gives the understanding and realization method of the algorithm used in the process of lexical analysis with examples, and based on this, a configurable lexical analyzer is realized by object-oriented design, and the visual display of all types of automata and state transition tables in related algorithms is realized.

The implementation of lexical analysis system and algorithm and visualization of data presented in this paper have been tested by unit test and manual test. The test results can show the correctness of the implementation.

KEY WORDS：Compiling principle; Lexical analysis; Configurable lexical analyzer; Visualization

第一章 绪论 6

1.1研究背景与意义 6

1.2研究现状 7

1.3本文研究目标及内容 7

1.4论文结构 7

第二章 算法研究与设计 9

2.1 正则表达式 9

2.1.1 语法与分析 9

2.1.2 正则表达式与状态机的关系 10

2.2正则到NFA 12

2.2.1 状态机的抽象 12

2.2.2单字符转换 13

2.2.3 连接/与操作 14

2.2.4并联/或操作 14

2.2.5 重复 15

2.2.6括号 16

2.3 NFA到DFA 17

2.4最小化DFA 19

2.4.1 去除死状态 19

2.4.2 合并等价状态 19

2.5 算法实现的输出与展示 21

第三章 面向对象设计词法分析器的构建 24

3.1 系统架构与分析 24

3.2面向对象设计 25

3.2.1 状态机相关类设计 27

3.2.2 状态相关类设计 28

3.3 系统测试与展示 28

第四章 算法的可视化 31

4.1 系统运行与状态机图像 31

4.1.1 生成图片的过程分析 31

4.1.2 可视化状态机的数据结构分析 33

4.1.3 广度优先遍历组装状态机 33

4.2 生成状态转移表 38

4.3 最小化DFA 40

第五章 结束语 41

5.1论文工作总结 41

5.2问题和展望 41

参考文献 42

致谢 43

第一章 绪论

1.1研究背景与意义

“编译原理”是链接机器语言和高级编程语言的桥梁^[1]，是计算机专业的一门重要基础课，主要介绍编译器的构造以及算法。其基本流程与每一步的作用如下所示

表1.1 编译原理各部分的作用

要使编译器能够自动且高效地完成任务，需要用到大量比较复杂的算法，这些算法难以理解和实现。同时，一些词法分析器或者词法分析器的生成器体积过大，如lex，flex，JavaCC等，工程性强、不方便作学习和分析使用，本文通过探究正则表达式到NFA（非确定性有限状态自动机）到DFA（确定性有限状态自动机）再到Min-DFA（最小化确定性有限状态自动机）的算法，给出了其在高级编程语言下的具体实现，并在此基础上给出了一个结构简单、面向对象的、易读易修改的可配置的词法分析器的设计思路和具体实现细节，并实现了词法分析每一步生成的状态机图片的可视化展示及状态转移表的展示。

通过论文给出的算法细节的具体实现以及可视化的系统，可以帮助编译原理领域的初学者更好地理解和掌握词法分析过程中用到的算法，同时，本文给出的面向对象可配置词法分析器也可以作为编译器前端或正则表达式引擎^[2]的一部分，其架构与设计细节，也有助于从系统设计的角度分析如何去实现一个低耦合、易维护的词法分析系统。

1.2研究现状

简单来说，现代编译原理的算法与技术发展非常缓慢，自20世纪50年代FORTAIN高级语言编译器开发取得成果以来，编译原理及自编译技术在之后的十年间发展较快，如LEX做自动的词法分析器生成，YACC做自动的语法分析器生成，但之后发展进入缓慢阶段，如在确定性有限状态机的等价状态划分的最好的算法是Hopcroft于1971年提出的，至今仍是工业界的事实标准。有限状态自动机的应用主要是作为正则表达式的匹配，去实现正则引擎^[3]，或者做代码相似度的可视化检测。而在编译原理词法分析的可视化领域有一些论文成果，阐述了如何实现一个词法分析系统及其可视化，但有如下缺点，首先其篇幅较小，以至于没有给出具体的实现细节，而仅仅是从理论和架构的角度给出设计思路，其次其用到的技术较为古老或复杂，如 Java Applet、C 等，以至于无法将重点放在算法的具体实现及可视化上；再次，其研究目标多为给出一个教学系统的设计，系统本身代码并不开源或是自由软件或根本没有实现。

1.3本文研究目标及内容

1. 词法分析器的算法设计实现