业务规则引擎词法分析论文.doc

毕业设计(论文）

设计(论文）题目 业务规则引擎词法分析

学生姓名
专业班级
指导老师
系主任(院长）
评 阅 人
5月23日

毕业设计（论文） 第V页

业务规则引擎词法分析

摘 要

编译程序的工作贯穿从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一般来说，整个过程可以划分为五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。
本设计即为词法分析阶段。词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。
词法分析是从输入的源程序中，识别出每个具有独立意义的单词，即基本保留字（关键字）、标识符、常数、运算符、分隔符五大类，剔除空格与转义字符，并依次输出各个单词的内部编码及单词符号自身值。

关键词：词法分析；原词；编译原理；记号
Business rules engine Lexical Analysis

Abstract

Compiler runs through the work started from the source input to output targets procedures of the whole process is very complex. Generally, the whole process can be divided into five phases: lexical analysis, grammar analysis, intermediate code generation, optimization and target code generation.
This is the lexical analysis of the design stage. Lexical analysis stage is to build the first phase of the process. This phase of the mission is scanned from left to right source of the string, in accordance with the rules of morphology (Regular Grammar rules) to identify the correct one word, and converted into the corresponding dual-word (category codes, property values ) To the analysis of the use of grammar. Therefore, the lexical analysis is compiled based. Lexical analysis of the implementation of the procedure known as the lexical analyzer.
Lexical analysis is imported from the source, identify each has an independent significance of the word, namely, the basic reservations about the word (keywords), the identifier, constant, the operator, separators top-five, remove spaces and escape, And the words were out of the internal code words and symbols its own value.

Key Words: Lexical analysis; Vocable; Compilers; Principles; Token
目 录
1. 绪论 1
1.1课题背景及来源 1
1.2课题研究的目标及意义 1
1.3编译器发展历史及前景 2
1.4本论文组织结构 3
2. 项目介绍及方案概述 4
2.1编译器的构造 4
2.1.1编译程序的引进 4
2.1.2编译程序的功能 4
2.1.3编译程序的构造 5
2.2词法分析器构造实践之必要性 5
3. 业务规则引擎词法分析之过程分析 6
3.1扫描处理 6
3.2正则表达式 8
3.3有穷自动机 9
3.4从正则表达式到DFA 10
3.4.1从正则表达式到NFA 11
3.4.2从NFA到DFA 12
3.4.3利用子集构造模拟NFA 13
3.4.5将DFA中的状态数最小化 13
4. 词法分析器的设计与实现 15
4.1词法分析器设计目的 15
4.2词法分析器设计要求 15
4.3算法设计思想 15
4.3.1 Token编码 15
4.3.2函数构成 19
4.3.3注意事项 23
4.4词法分析流程图 23
4.4.1词法分析输入输出总体流程图 23
4.4.2判断标识符和数字的流程图 25
4.4.3函数dealword判别字符串流程图 25
4.5词法分析结果 28
4.5.1正确分析结果 28
4.5.2异常处理结果 28
4.5.3词法分析结果界面显示 29
5. 总结 31
致谢 32
参考文献 33

毕业设计（论文） 第33页
1. 绪论
1.1课题背景及来源
本课题主要是通过一定业务规则进行简单的词法分析，而业务规则引擎来自于企业中一些严格的要求。复杂企业级项目的开发以及其中随外部条件不断变化的业务规则（Business Logic）[1]，迫切需要分离商业决策者的商业决策逻辑和应用开发者的技术决策，并把这些商业决策放在中心数据库或其他统一的地方，让它们能在运行时（即商务时间）可以动态地管理和修改从而提供软件系统的柔性和适应性[2]。规则引擎正是应用于上述动态环境中的一种解决方法。
企业管理者对企业级IT系统[3]的开发有着如下的要求：
1）为提高效率，管理流程必须自动化，即使现代商业规则异常复杂；
2）市场要求业务规则经常变化，IT系统必须依据业务规则的变化快速、低成本的更新；
3）为了快速、低成本的更新，业务人员应能直接管理IT系统中的规则，不需要程序开发人员参与。
而项目开发人员则碰到了以下问题：
1）程序=算法+数据结构，有些复杂的商业规则很难推导出算法和抽象出数据模型；
2）软件工程要求从需求->设计->编码，然而业务规则常常在需求阶段可能还没有明确，在设计和编码后还在变化，业务规则往往嵌在系统各处代码中
3）对程序员来说，系统已经维护，更新困难，更不可能让业务人员来管理[4]。
基于规则的专家系统的出现给开发人员以解决问题的契机。规则引擎由基于规则的专家系统中的推理引擎发展而来[5]。
1.2课题研究的目标及意义
随着计算机语言的结构越来越复杂，为了开发优秀的编译器，人们已经渐渐感到将词法分析独立出来做研究的重要性[5]。不过词法分析器的作用却不限于此。我们有时候建立了比较复杂的配置文件，譬如XML的时候，分析器首先也要对该文件进行词法分析，把整个字符串断成了一个一个比较短小的记号[7]（指的是具有某种属性的字符串），之后才进行结构上的分析。再者，在实现某种控制台应用程序的时候，程序需要分析用户打进屏幕的命令[6]。如果该命令足够复杂的话，我们也首先要对这个命令进行词法分析，之后得到的结果会大大方便进行接下去的工作[13]。
1.3编译器发展历史及前景
从20世纪50年代早期第一个编译器出现至今，我们所掌握的有关编译器的知识已经得到了长足的发展。我们很难说出第一个编译器出现的准确时间，因为最初的很多实验和实现是由不同的工作小组独立完成的。编译器的早期工作主要集中在如何把算术表达式翻译成机器代码[7] [8]。
整个20世纪50年代，编译器的编写一直被认为是一个极难的问题。比如Fortran的第一个编译器花了18人年才得以实现。目前，我们已经系统地掌握了处理编译期间发生的许多重要任务的技术[9]。良好的实现语言、程序设计环境和软件工具也已经被开发出来。借助于这些先进的技术、环境和工具[10]，一个真正的编译器完全可以作为一个课题重点研究，并使其更好地实现[11]。
上个世纪60年代，开始了分析问题（parsing problem，用于上下文无关文法识别的有效算法）[17]的研究。现在它已是编译原理中的一个标准部分。有限状态自动机（Finite Automaton）和正则表达式（Regular Expression）同上下文无关文法紧密相关，并且引出了表示程序设计语言的单词的符号方式[12]。
人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其称为优化技术[10]（Optimization Technique），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（Code Improvement Technique）[10]。
当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器[5]（Parser Generator），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为Unix系统编写的。类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex是这其中的佼佼者。[12]
在20世纪70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化[13]，这其中就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
目前，编译系统软件垄断了绝大部分的软件市场。编译程序作为符号处理的工具，其基本原理和技术有着典型性和广泛性，在软件工程、逆向工程、软件再工程、语言转换及其他领域都有着广泛的应用[12]。例如，语法制导的程序编辑软件、程序结构分析软件、程序调试与测试软件、反汇编软件、符号执行软件的开发也有一定的启发和指导作用。编译程序作为符号处理的工具，只要设计符号处理，就需要采用编译程序实现的基本原理有技术[14]。
1.4本论文组织结构
本论文由5章组成，其中第二、三、四章是核心部分，讲述了项目的设计原理、设计方案、详细分析、功能的具体实现和结果分析。本论文的设计思想是基于结果导向的，按照先整体后具体的思路来组织论文结构。具体的每个章节的主要内容如下：
第一章 绪论。主要介绍论文的课题来源、研究背景、目标、意义和编译器发展历史和背景等。
第二章 项目介绍及方案概述。主要介绍项目的推进的方案。为词法分析的设计与实现提供理论基础。
第三章 业务规则引擎词法分析之过程分析。对编译过程中词法分析过程进行过程分析，是后面的设计与实现做好准备和详细分析。
第四章 词法分析器的设计与实现 该章详细介绍词法分析器设计目的和要求、算法设计思想、主要函数构成、词法分析流程图和词法分析结果等。
第五章 总结。该章对项目完成后在理论和实践上的收获进行了总结和工作上的感悟，并对未来的进一步研究方向进行展望。

2. 项目介绍及方案概述
2.1编译器的构造
2.1.1编译程序的引进
一个高级程序设计语言归根结底是一个基本符号序列[15]，或进一步说是一个字符序列。当我们上机运行时，计算机并不能直接接受、理解与运行该程序。计算机所能直接接受、理解与运行的是机器语言的二进位位串，而现在却是字母与括号等字符。为此我们需要一个软件处理这个字符序列，识别出这是字母还是其他一些特殊字符，进一步把它们翻译成可由计算机执行的等价的目标代码，达到运行且获得所期望效果的目的。这种高级程序设计语言程序翻译成等价的低级语言程序的软件就是编译程序。
编译程序是一种符号处理工具，它把高级程序设计语言源程序翻译成等价的低级语言目标代码。此处低级语言可以是汇编语言，也可以是机器语言[15]。等价是指源程序和目标程序两者效果必须完全一样，也就是说，当源程序正确时运行得到的效果，运行目标代码时同样能得到，若源程序有错误，目标代码也将有相应的反映。
以翻译方式运行的任何一种高级程序设计语言都必须有编译程序。这种编译程序当前都被开发成了集编辑、编译、调试与运行于一体的程序设计语言支持环境[16]，如Turbo PASCAL、Turbo C、Borland C++ Builder与Visual C++等。可视化版本编译程序的引进更为用户设计应用程序界面带来了极大的方便。由于编译程序一般较为庞大，结构复杂，往往称为编译系统。这些编译系统软件往往由著名的公司开发，具有人机接口[16]良好、使用方便、目标代码质量高等优点。
2.1.2编译程序的功能
编译程序的功能是把高级程序设计语言源程序翻译成等价的低级语言目标代码[7]。
鉴于目标代码一般总是机器相关的，也就是说为某种型号计算机产生机器语言目标代码，必须对此种型号计算机的指令系统[8]（包括指令格式、不同操作码和寻址方式等）有详细的了解。这样需要花费大量的时间，而且仅限于一种型号的计算机[14]，有相当的局限性。
编译程序的输入是某种高级程序设计语言源程序[8]字符序列（字符串），以C语言为背景时输入就是C程序字符串，输出是等价的虚拟机目标代码。
一个编译程序输入高级程序设计语言源程序字符串，要识别出一个个具有独立含义的最小语法单位——符号（或称单词），如识别出main、float和if等，并把它们加工处理成内部中间表示——属性字，这就是词法分析。
2.1.3编译程序的构造
一般地，编译程序由两大部分组成，即前端与后端[8]。前端进行分析，即词法分析、语法分析与语义分析；后端进行综合，即目标代码优化与目标代码生成。前端往往涉及一个程序设计语言的定义，而与具体目标机无关。后端在生成目标代码时则一般与目标机有关[11]，必须考虑各个具体细节，如指令系统（包括指令格式、不同的操作码和寻址方式）、寄存器个数与使用约定以及特殊指令的使用等[8]。当目标机是虚拟机时，情况要简单得多。
2.2词法分析器构造实践之必要性
编译原理以形式语言理论相关概念为基础[6]，尤其是实现语义分析的语法制导的翻译，以基于形式定义的属性文法[11]为基础，其本身决定了有较强的理论性，但所讨论的编译程序作为高级程序设计语言支持软件，作为符号处理的工具，它又有很强的实践性，因此要兼顾理论性与实践性两方面。
词法分析是编译程序第一阶段的工作。词法分析程序的输入是源程序字符串，输出是等价的内部中间表示——属性字序列，为以后的语法分析奠定基础[11]。因此词法分析是相当重要的，要做好一个编译器首先就得做好词法分析。词法分析的高效率，才能保证整个编译系统的高效率[15]。
3. 业务规则引擎词法分析之过程分析
编译器的扫描或词法分析（lexical analysis）阶段可将源程序读作字符文件并将其分为若干个记号。记号与自然语言中的单词类似：每一个记号都是表示源程序中信息单元的字符序列。典型的有：关键字（keyword），例如if和while，它们是字母的固定串；标识符（identifier）是由用户定义的串，它们通常由字母和数字组成并由一个字母开头；特殊符号（special symbol）如算术符号+和*、一些多字符符号，如>= 和< >。在各种情况中，记号都表示由扫描程序从剩余的输入字符的开头识别或匹配的某种字符格式。
由于扫描程序的任务是格式匹配的一种特殊情况，所以需要研究在扫描过程中的格式说明和识别方法，其中最主要的是正则表达式（regular expression）和有穷自动机（finite automata）。但是，扫描程序也是处理源代码输入的编译器部分[17]，而且由于这个输入经常需要非常多的额外时间，扫描程序的操作也就必须尽可能地高效了。因此还需十分注意扫描程序结构的实际细节。
扫描程序问题的研究可分为以下几个部分：首先，给出扫描程序操作的一个概貌以及所涉及到的结构和概念。其次是学习正则表达式，它是用于表示构成程序设计语言的词法结构的串格式的标准表示法。接着是有穷状态机器或称有穷自动机，它是对由正则表达式给出的串格式的识别算法。
3.1扫描处理
扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单元。由扫描程序生成的逻辑单元称作记号（token），将字符组合成记号与在一个英语句子中将字母构成单词并确定单词的含义很相像。此时它的任务很像拼写。记号通常定义为枚举类型的逻辑项[9]。例如，记号在C中可被定义为:
typedef enum
{IF, THEN, ELS, EPLUS, MINUS, NUM, ID, ...}
Token Type;
记号有若干种类型，这其中包括了保留字（reserved word），如IF和THEN，它们表示字符串“ i f”和“ t h e n”；第2类是特殊符号（special symbol），如算术符号加（PLUS）和减（MINUS），它们表示字符“+”和“-”。第3类是表示多字符串的记号，如NUM和ID，它们分别表示数字和标识符。
作为逻辑项的记号必须与它们所表示的字符串完全区分开来。例如：保留字记号IF须与它表示的两个字符“i、f”的串相区别。为了使这个区别更明显，由记号表示的字符串有时称作它的串值（string value）或它的词义（lexeme）。某些记号只有一个词义：保留字就具有这个特性。但记号还可能表示无限多个语义。例如标识符全由单个记号ID表示，然而标识符有许多不同的串值来表示它们的单个名字。因为编译器必须掌握它们在符号表中的情况，所以不能忽略这些名字。因此，扫描程序也需用至少一些记号来构造串值。任何与记号相关的值都是记号的属性（attribute），而串值就是属性的示例。记号还可有其他的属性。例如，NUM记号可有一个诸如“32767”的串值属性，它是由5个数字字符组成，但它还会有一个由其值计算所得的真实值32767组成的数字值属性。在诸如PLUS这样的特殊符号记号中，不仅有串值“+”还有与之相关的真实算术操作+。实际上，记号符号本身就可看作是简单的其他属性，而记号就是它所有属性的总和。
为了后面的处理，扫描程序要求至少具有与记号所需相等的属性。例如要计算NUM记号的串值，但由于从它的串值就可计算，因此也就无需立刻计算它的数字值了。另一方面，如果计算它的数字值，就会丢弃掉它的串值。有时扫描程序本身会完成在恰当位置记录属性所需的操作，或直接将属性传到编译器后面的阶段。例如，扫描程序能利用标识符的串值将其输入到符号表中，或在后面传送它。
尽管扫描程序的任务是将整个源程序转换为记号序列，但扫描程序却很少一次性地完成它。实际上，扫描程序是在分析程序的控制下进行操作的，它通过函数从输入中返回有关命令的下一个记号，该函数有与C说明相似的说明：
TokenType getToken(void);
这个方式中声明的get Token函数在调用时从输入中返回下一个记号，并计算诸如记号串值这样的附加属性。输入字符串通常不给这个函数提供参数，但参数却被保存在缓冲区中或由系统输入设备提供。例如，考虑C源代码行：
a [ index ] = 4 + 2
假定将这个代码行放在一个输入缓冲区中，它的下一个输入字符由箭头指出，如下所示：

一个对get Token的调用现在需要跳过下面的4个空格，识别由单个字符a组成的串“a”，并返回记号值ID作为下个记号，此时的输入缓冲区如下所示：

因此，get Token随后的调用将再次从左括号字符开始识别过程。
3.2正则表达式
正则表达式表示字符串的格式。正则表达式r完全由它所匹配的串集来定义。这个集合称为由正则表达式生成的语言（language generated by the regular expression），写作L（r）[7]。正则表达式r还包括字母表中的字符，但这些字符具有不同的含义：在正则表达式中，所有的符号指的都是模式[18]。
最后，正则表达式r还可包括有特殊含义的字符。这样的字符称作元字符（meta character）或元符号（meta symbol）。它们并不是字母表中的正规字符，否则当其作为元字符时就与作为字母表中的字符时很难区分了。但是通常不可能要求这种排斥，而且也必须使用一个惯例来区分元字符的这两种用途。在很多情况下，它是通过使用可“关掉”元字符的特殊意义的转义字符（escape character）做到的。源代码层一般是反斜杠和引号。如果转义字符是字母表中的正规字符，则它们本身也就是元字符了[18]。
程序设计语言记号可分为若干个相当标准的有限种类：
1）数 数可以仅是数字（自然数）、十进制数、或带有指数的数（由e或E表示）的序列。例如：2.71E-2表示数0.0271。可用正则定义将这些数表示如下：
nat = [0-9]+
signedNat = (+|-)? nat
number = signedNat ("." nat ) ? (EsignedNat) ?
此处，在引号中用了一个十进制的点来强调它应直接匹配且不可被解释为一个元字符。
2）保留字和标识符 正则表达式中最简单的就是保留字了，它们由字符的固定序列表示。如果要将所有的保留字收集到一个定义中，就可写成：
reserved = if | while | do | ...
相反地，标识符是不固定的字符串。通常，标识符必须由一个字母开头且只包含字母和数字。可用以下的正则定义表示：
letter = [ a – z A - Z ]
digit = [ 0 - 9 ]
identifier = letter (letter | digit) *
3）注释 注释在扫描过程中一般是被忽略的[18]。然而扫描程序必须识别注释并舍弃它们。因此尽管扫描程序可能没有清晰的常量记号（可将其称为“伪记号pseudo token”），仍需要给注释编写出正则表达式。注释可有若干个不同的格式。通常，它们可以是前后为分隔符的自由，例如：
/* this is a C comment */
4）二义性、空白格和先行 在程序设计语言记号使用正则表达式的描述中，有一些字符串经常可被不同的正则表达式匹配。例如：诸如if和while的串,可以既是标识符又可以是关键字。类似地，串< >可解释为表示两个记号（“小于号”和“大于号”）或单个符号（“不等于”）。程序设计语言定义必须规定出应遵守哪个解释，但正则表达式本身却无法做到它。相反地，语言定义必须给出无二义性规则（disambiguating rules），由其回答每一种情况下的含义。
3.3有穷自动机
有穷自动机，或有穷状态的机器，是描述（或“机器”）特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别模式的过程，因此也能用作构造扫描程序[9]。当然有穷自动机与正则表达式之间有着很密切的关系。
正则表达式可在程序设计语言中给出标识符模式的一般定义：
identifier = letter ( letter | digit) *
它代表以一个字母开头且其后为任意字母和（或）数字序列的串。将真实字符串识别为标识符的过程现在可通过列出在识别过程中所用到的状态和转换的序列来表示。如图3.1所示：

图3.1：标识符的有穷自动机

可以把有穷自动机分为三类：
1）确定有穷自动机（DFA）
自动机的每个状态都有对字母表中所有符号的转移。
2）非确定有穷自动机（NFA）
自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从q0到F中标记（label）著这个输入字的一个状态的路径。如果一个转移是未定义的，自动机因此不知道如何继续读取输入，则拒绝这个字[18]。
3）有ε转移的非确定有穷自动机（FND-ε或ε-NFA）
除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本与符号无关的跳转。就是说，如果一个状态有标记著ε的转移，则NFA可以处在ε-转移可到达的任何状态中，直接或通过其他有ε-转移的状态。从一个状态q通过这种方法可到达的状态的集合叫做q的ε-闭包。
尽管可以证明所有这些自动机都可以接受同样的语言。你总是可以构造接受与给定的NFA M同样语言的某个DFA[18]。
3.4从正则表达式到DFA
将正则表达式翻译成DFA的最简单算法是通过中间构造，在它之中，正则表达式派生出一个NFA，接着就用该NFA构造一个同等的DFA[7]。现在有一些算法可将正则表达式直译为DFA，但是它们很复杂，且对中间构造也有些影响。因此我们只关心两个算法：一个是将正则表达式翻译成NFA，另一个是将NFA翻译成DFA。再与将DFA翻译成前一节中描述的程序的一个算法合并，则构造一个扫描程序的自动过程可分为3步，如图3.2所示：

图3.2：扫描程序的自动过程

3.4.1从正则表达式到NFA
Thompson结构利用ε-转换将正则表达式的机器片段“粘在一起”以构成与整个表达式相对应的机器。它依照了正则表达式定义的结构：为每个基本正则表达式展示一个NFA，接着再显示如何通过连接子表达式的NFA得到每个正则表达式运算。例如，根据Thompson结构将正则表达式ab | a翻译为NFA，如图3.3所示：

图3.3：利用Thompson结构完成的正则表达式ab | a 的NFA

同样利用Thompson结构完成正则表达式letter(letter | digit)*的NFA，如图3.4所示：

图3.4：利用Thompson结构得到正则表达式letter(letter | digit)*的NFA

3.4.2从NFA到DFA
若给定了一个任意的NFA，现在来描述构造等价的DFA（即：可准确接受相同串的DFA）的算法。为了做到它，则需要可从单个输入字符的某个状态中去除ε-转换和多重转换的一些方法。消除ε-转换涉及到了ε-闭包的构造。ε-闭包（ε-closure）是可由ε-转换从某状态或某些状态达到的所有状态集合。消除在单个输入字符上的多重转换涉及跟踪可由匹配单个字符而达到的状态的集合。这两个过程都要求考虑状态的集合而不是单个状态，因此，当看到构建的DFA如同它的状态一样，也有原始NFA的状态集合时，就不会感到意外了。所以就将这个算法称作子集构造（subset construction）。我们首先较详细地讨论一下ε-闭包，然后再描述子集合构造。
1）状态集合的ε-闭包 将单个状态s的ε-闭包定义为可由一系列的零个或多个ε-转换能达到的状态集合。
2）子集构造 从一个给定的NFA-M来构造DFA的算法。考虑图3.4中的NFA（正则表达式letter(letter | digit )*的Thompson结构）如图3.5所示

图3.5：正则表达式letter(letter | digit)*的Thompson结构

令顺序排列的字母来依次表示图3.5状态，其子集构造过程如下：它的初始状态是A= { 1 }，在letter上有到B= {2,3,4,5,7,10}的转换。在letter上还有一个从这个状态到F= {4,5,6,7,9,10}的转换以及在digit上有到H={4,5,7,8,9,10}的转换。最后，所有这些状态都有在letter和digit上的转换，或是到其自身或是到另一个。完整的DFA在如图3.6中给出：

图3.6：正则表达式letter(letter | digit)*的完整的DFA

3.4.3利用子集构造模拟NFA
上一节简要地讨论了编写模拟NFA的程序的可能性，这是一个要求处理机器的非确定性或非算法本质的问题。模拟NFA的一种方法是使用子集构造，但并非是构造与DFA相关的所有状态，而是在由下一个输入字符指出的每个点上只构造一个状态。因此，这样只构造了在给出的输入串上被取用的DFA的路径中真正发生的状态集合。这样做的好处在于有可能就不再需要构造整个DFA了，它的缺点在于如果路径中包含了循环，则有可能会多次构造某个状态。
3.4.5将DFA中的状态数最小化
因为在扫描程序中，效率是很重要的，如果可能的话，在某种意义上构造的DFA应最小。实际上，自动机理论中有一个很重要的结果，即：对于任何给定的DFA，都有一个含有最少量状态的等价的DFA，而且这个最小状态的DFA是唯一的（重命名的状态除外）。考虑下面的DFA，出它与正则表达式(a | ε) b *相对应，如图3.7所示：

图3.7：正则表达式 (a | ε) b *的DFA

在这种情况下，所有的状态（除了错误状态之外）都在接受。现在考虑字符b。每个接受状态都有到其他接受状态的b-转换，因此b不能区分任何状态。另一方面，状态1存在有到一个接受状态的a-转换，但状态2和状态3却没有a-转换（或说成是：在a上到错误的非接受状态的错误转换，更合适一些）。所以，a可将状态1与状态2和3区分开来，我们必须将状态重新分配为集合{1}和{2,3}。然后再重复一遍。集合{1}不能再分隔了，我们也就不再考虑它了。状态2和状态3不能由a或b区分开来。因此，就得到了最小状态的DFA，如图3.8所示：

图3.8：正则表达式 (a | ε) b *简化后的DFA

4. 词法分析器的设计与实现
4.1词法分析器设计目的
从输入的源程序中，识别出每个具有独立意义的单词，即基本保留字（关键字）、标识符、常数、运算符、分隔符五大类，剔除空格与转义字符，并依次输出各个单词的内部编码及单词符号自身值[9]。
4.2词法分析器设计要求
词法分析器的功能和作为一个独立子程序模块的要求进行设计[19]，画出程序流程图；给出一个简单的C语言程序[20]，能识别出其单词符号；采用二元组形式输出[21]。
4.3算法设计思想
本算法主要利用状态转换图生成一个词法分析器，对输入的程序进行词法分析，并生成五个表：关键字表、标识符表、常数表、运算符表、分隔符表[22]。其中关键字表和分隔符表的大小是由高级语言的子集决定的，可以用数组装载[20]；而标识符表和常数表的大小取决于输入的待分析程序中的变量、过程名、常数的个数，所以要用指针组成动态链表来装载[20]。
设计词法分析器的时候，先读出源文件中所有字符串，按照源程序原样输出，把所有的字符串存入一个缓冲区内[19]，然后定义一个Token指针数组对缓冲区内的字符串进行匹配[19]。匹配功能根据字符串的属性[23]由函数进行判定。
4.3.1 Token编码
1）关键字
提取C语言中常用的关键字，如下所示：
auto
break
case
char
const
continue
default
do
double
else
enum
extern
float
for
goto
if
int
long
register
return
short
signed
sizeof
static
struct
switch
typedef
union
unsigned
void
volatile
while
2）运算符
提取语言中C常用的运算符[21]，在dealword函数定义了一些优先级，如下所示：
( 1 左圆括号
) 1 右圆括号
[ 2 左方括号
] 2 右方括号
-> 3 指向
. 4 点运算符
! 5 逻辑非
~ 6 按位取反
++ 7 自增
-- 8 自减
- 9 负
* 10 指针
& 11 取地址
* 12 乘
/ 13 除
% 14 求余
+ 15 加
- 16 减
<< 17 左移
>> 18 右移
< 19 小于
<= 20 小于等于
> 21 大于
>= 22 大于等于
== 23 等于
!= 24 不等于
& 25 按位于
^ 26 按位异或
| 27 按位或
&& 28 逻辑与
|| 29 逻辑或
? 30 双目条件
: 30 双目条件
= 31 赋值
+= 32 加赋值
-= 33 减赋值
*= 34 乘赋值
/= 35 除赋值
%= 36 求余赋值
>>= 37 右移赋值
<<= 38 左移赋值
&= 39 与赋值
^= 40 异或赋值
|= 41 或赋值
, 42 逗号
3）分隔符、标识符、常及其它
分隔定义了2个，分别是{}和;。常数是包括小数在内的数字，标识符是除去关键字和一些C语言中的宏以外的一般字符串[21]。判断处理如下：
单目运算符：( ) [ ] . ? : , ;{}
双目前符：! + - * / % & > < ^ | =
双目运算符： != ++ += -- -= -> *= /= %= &= && >= >> >>= <= << <<= ^= |= || = =
mulitmap<int,char> map0; 单目运算符
mulitmap<int,char> map1; 双目前符
mulitmap<int,char> map2; 双目前符
mulitmap<int,char> map3; 三目
4.3.2函数构成
词法分析器的源程序主要由以下主要的函数构成：
1）outcode函数
用来判断输入文件和输出文件存在与否[23]，并把两个文件的头指针赋给用于输入调用的字符串[20]，并向外文件输出token字。函数定义的代码如表4.1所示：

表4.1：outcode函数的定义
void outcode(char *str)
{
FILE *fp;
char ch='0';
fp=fopen(str,"r");
if( !fp){
cout<<"Can not open the file,Thank you!!!"<<endl;
exit(0);
}
cout<<"**************** source *******************|"<<endl;
while(fp && ch!=-1){
ch=fgetc(fp);
putchar(ch);
}
cout<<"\n********************************************|\n"<<endl;
fclose(fp);
}

2）iskey函数
判断输入的字符串是否为关键字[23]，首先和个数较少的关键字比较匹配，不是关键字（不包含宏