正文：
词法分析器可有两种:一种是把词法分析器作为语法分析的一个子程序,一种是把词法分析器作为编译程序的独立一遍.在前一种情况下,词法分析器不断地被语法分析器调用,每调用一次词法分析器将从源程序的字符序列拼出一个单词,并将其Token值返回给语法分析器.后一种情况则不同,词法分析器不是被语法分析器不断地调用,而是一次扫描全部单词完成编译器的独立一遍任务.
词法分析器的本质：基本任务是进行模式匹配,其关键在于分析过程中的模式说明和模式识别方法,在编译分析中即正规表达式和有限自动机。
构造词法分析器方法：1、手工构造；2、利用自动生成工具LEX。但是无论用那种方法，其内在工作原理都是相同的，都要经过正规式到最小状态DFA的转换。
正规表达式与有限自动机的关系：（1）、字母表Σ上的有限自动机M所接受的语言L（M）是Σ上的一个正规集；（2）、对于Σ上的每一个正规式r，存在一个Σ上的非确定有限自动机M，使得L（M）=L（r）。这就是说，正规式所表示的语言即正规集与有限自动机所识别的语言是完全等价的，只是表示形式不同而已。同一个语言，既可以用FA描述，也可以用正规式描述。而词法分析器则是根据它们的规则构造的。
编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（source language）编写的程序作为输入，而产生用目标语言（target language）编写的等价程序。通常地，源程序为高级语言（high-level language），如C或C++，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code）），也就是写在计算机机器指令中的用于运行的代码。
编译器是一种相当复杂的程序，其代码的长度可从10000行到1000000行不等。编写甚至读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。因此，掌握这一技术具有非常大的实际意义。
一、
编译系统的
发展：
上世纪50年代，IBM的John Backus带领一个研究小组对FORTRAN语言及其编译器进行开发。但由于当时人们对编译理论了解不多，开发工作变得既复杂又艰苦。与此同时， Noam Chomsky开始了他对自然语言结构的研究。他的发现最终使得编译器的结构异常简单，甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言分类。正如现在所称的Chomsky架构（Chomsky Hierarchy），它包括了文法的四个层次：0型文法、1型文法、2型文法和3型文法，且其中的每一个都是其前者的特殊情况。2型文法（或上下文无关文法）被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个问题。现在它已是编译原理中的一个标准部分。
有限状态自动机（Finite Automaton）和正则表达式（Regular Expression）同上下文无关文法紧密相关，它们与Chomsky的3型文法相对应。对它们的研究与Chomsky的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。
人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其称为优化技术（Optimization Technique），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（Code Improvement Technique）。
当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器（Parser Generator），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为Unix系统编写的。类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex（与Yacc同时，由Mike Lesk为Unix系统开发）是这其中的佼佼者。
在70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括：首先，编译器包括了更加复杂算法的应用程序它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法。其次，编译器已越来越成为基于窗口的交互开发环境（Interactive Development Environment，IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的IDE标准并没有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节。
在九十年代，作为GNU项目或其它开放源代码项目的一部分，许多免费编译器和编译器开发工具被开发出来。这些工具可用来编译所有的计算机程序语言。它们中的一些项目被认为是高质量的，而且对现代编译理论感性趣的人可以很容易的得到它们的免费源代码。
大约在1999年，SGI公布了他们的一个工业化的并行化优化编译器Pro64的源代码，后被全世界多个编译器研究小组用来做研究平台，并命名为Open64。Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。
二、与编译器相关的程序：
(1)
解释程序（interpreter）
解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲，任何程序设计语言都可被解释或被编译，但是根据所使用的语言和翻译情况，很可能会选用解释程序而不用编译器。例如，我们经常解释BASIC语言而不是去编译它。类似地，诸如LISP的函数语言也常常是被解释的。解释程序也经常用于教育和软件的开发，此处的程序很有可能被翻译若干次。而另一方面，当执行的速度是最为重要的因素时就使用编译器，这是因为被编译的目标代码比被解释的源代码要快得多，有时要快10倍或更多。但是，解释程序具有许多与编译器共享的操作，而两者之间也有一些混合之处。
(2)
汇编程序（assembler）
汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的，汇编语言是计算机的机器语言的符号形式，它极易翻译。有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。
(3)
连接程序（linker）
编译器和汇编程序都经常依赖于连接程序，它将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下，目标代码，即还未被连接的机器代码，与可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。有趣的是，连接程序现在正在完成编译器最早的一个主要活动（这也是“编译”一词的用法，即通过收集不同的来源来构造）。连接过程对操作系统和处理器有极大的依赖性。
(4)
装入程序（loader）
编译器、汇编程序或连接程序生成的代码经常还不完全适用或不能执行，但是它们的主要存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为是可重定位的（relocatable），而装入程序可处理所有的与指定的基地址或起始地址有关的可重定位的地址。装入程序使得可执行代码更加灵活，但是装入处理通常是在后台（作为操作环境的一部分）或与连接相联合时才发生，装入程序极少会是实际的独立程序。
(5)
预处理器（preprocessor）
预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以删除注释、包含其他文件以及执行宏（宏macro是一段重复文字的简短描写）替代。预处理器可由语言（如C）要求或以后作为提供额外功能（诸如为FORTRAN提供Ratfor预处理器）的附加软件。
(6)
编辑器（editor）
编译器通常接受由任何生成标准文件（例如ASCII文件）的编辑器编写的源程序。最近，编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境——IDE中。此时，尽管编辑器仍然生成标准文件，但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基于结构的（structure based），且它早已包括了编译器的某些操作；因此，程序员就会在程序的编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序，这样程序员无需离开编辑器就可执行程序。
(7)
调试程序（debugger）
调试程序是可在被编译了的程序中判定执行错误的程序，它也经常与编译器一起放在IDE中。运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息（诸如行数、变量名和过程）。它还可以在预先指定的位置（称为断点（breakpoint））暂停执行，并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数，编译器必须为调试程序提供恰当的符号信息，而这有时却相当困难，尤其是在一个要优化目标代码的编译器中。因此，调试又变成了一个编译问题。
(8)
描述器（profiler）
描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目标代码。
(9)
项目管理程序（project manager）
现在的软件项目通常大到需要由一组程序员来完成，这时对那些由不同人员操作的文件进行整理就非常重要了，而这正是项目管理程序的任务。例如，项目管理程序应将由不同的程序员制作的文件的各个独立版本整理在一起，它还应保存一组文件的更改历史，这样就能维持一个正在开发的程序的连贯版本了（这对那些由单个程序员管理的项目也很有用）。项目管理程序的编写可与语言无关，但当其与编译器捆绑在一起时，它就可以保持有关特定的编译器和建立一个完整的可执行程序的链接程序操作的信息。在Unix系统中有两个流行的项目管理程序：sccs（source code control system）和rcs（revision control system）。
词法分析器可有两种:一种是把词法分析器作为语法分析的一个子程序,一种是把词法分析器作为编译程序的独立一遍.在前一种情况下,词法分析器不断地被语法分析器调用,每调用一次词法分析器将从源程序的字符序列拼出一个单词,并将其Token值返回给语法分析器.后一种情况则不同,词法分析器不是被语法分析器不断地调用,而是一次扫描全部单词完成编译器的独立一遍任务.
词法分析器的本质：基本任务是进行模式匹配,其关键在于分析过程中的模式说明和模式识别方法,在编译分析中即正规表达式和有限自动机。
构造词法分析器方法：1、手工构造；2、利用自动生成工具LEX。但是无论用那种方法，其内在工作原理都是相同的，都要经过正规式到最小状态DFA的转换。
正规表达式与有限自动机的关系：（1）、字母表Σ上的有限自动机M所接受的语言L（M）是Σ上的一个正规集；（2）、对于Σ上的每一个正规式r，存在一个Σ上的非确定有限自动机M，使得L（M）=L（r）。这就是说，正规式所表示的语言即正规集与有限自动机所识别的语言是完全等价的，只是表示形式不同而已。同一个语言，既可以用FA描述，也可以用正规式描述。而词法分析器则是根据它们的规则构造的。
编译器是将一种语言翻译为另一种语言的计算机程序。编译器将源程序（source language）编写的程序作为输入，而产生用目标语言（target language）编写的等价程序。通常地，源程序为高级语言（high-level language），如C或C++，而目标语言则是目标机器的目标代码（object code，有时也称作机器代码（machine code）），也就是写在计算机机器指令中的用于运行的代码。
编译器是一种相当复杂的程序，其代码的长度可从10000行到1000000行不等。编写甚至读懂这样的一个程序都非易事，大多数的计算机科学家和专业人员也从来没有编写过一个完整的编译器。但是，几乎所有形式的计算均要用到编译器，而且任何一个与计算机打交道的专业人员都应掌握编译器的基本结构和操作。除此之外，计算机应用程序中经常遇到的一个任务就是命令解释程序和界面程序的开发，这比编译器要小，但使用的却是相同的技术。因此，掌握这一技术具有非常大的实际意义。
一、
编译系统的
发展：
上世纪50年代，IBM的John Backus带领一个研究小组对FORTRAN语言及其编译器进行开发。但由于当时人们对编译理论了解不多，开发工作变得既复杂又艰苦。与此同时， Noam Chomsky开始了他对自然语言结构的研究。他的发现最终使得编译器的结构异常简单，甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言分类。正如现在所称的Chomsky架构（Chomsky Hierarchy），它包括了文法的四个层次：0型文法、1型文法、2型文法和3型文法，且其中的每一个都是其前者的特殊情况。2型文法（或上下文无关文法）被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个问题。现在它已是编译原理中的一个标准部分。
有限状态自动机（Finite Automaton）和正则表达式（Regular Expression）同上下文无关文法紧密相关，它们与Chomsky的3型文法相对应。对它们的研究与Chomsky的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。
人们接着又深化了生成有效目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其称为优化技术（Optimization Technique），但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术（Code Improvement Technique）。
当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器（Parser Generator），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为Unix系统编写的。类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex（与Yacc同时，由Mike Lesk为Unix系统开发）是这其中的佼佼者。
在70年代后期和80年代早期，大量的项目都贯注于编译器其它部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功，这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括：首先，编译器包括了更加复杂算法的应用程序它用于推断或简化程序中的信息；这又与更为复杂的程序设计语言的发展结合在一起。其中典型的有用于函数语言编译的Hindley-Milner类型检查的统一算法。其次，编译器已越来越成为基于窗口的交互开发环境（Interactive Development Environment，IDE）的一部分，它包括了编辑器、连接程序、调试程序以及项目管理程序。这样的IDE标准并没有多少，但是对标准的窗口环境进行开发已成为方向。另一方面，尽管近年来在编译原理领域进行了大量的研究，但是基本的编译器设计原理在近20年中都没有多大的改变，它现在正迅速地成为计算机科学课程中的中心环节。
在九十年代，作为GNU项目或其它开放源代码项目的一部分，许多免费编译器和编译器开发工具被开发出来。这些工具可用来编译所有的计算机程序语言。它们中的一些项目被认为是高质量的，而且对现代编译理论感性趣的人可以很容易的得到它们的免费源代码。
大约在1999年，SGI公布了他们的一个工业化的并行化优化编译器Pro64的源代码，后被全世界多个编译器研究小组用来做研究平台，并命名为Open64。Open64的设计结构好，分析优化全面，是编译器高级研究的理想平台。
二、与编译器相关的程序：
(1)
解释程序（interpreter）
解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲，任何程序设计语言都可被解释或被编译，但是根据所使用的语言和翻译情况，很可能会选用解释程序而不用编译器。例如，我们经常解释BASIC语言而不是去编译它。类似地，诸如LISP的函数语言也常常是被解释的。解释程序也经常用于教育和软件的开发，此处的程序很有可能被翻译若干次。而另一方面，当执行的速度是最为重要的因素时就使用编译器，这是因为被编译的目标代码比被解释的源代码要快得多，有时要快10倍或更多。但是，解释程序具有许多与编译器共享的操作，而两者之间也有一些混合之处。
(2)
汇编程序（assembler）
汇编程序是用于特定计算机上的汇编语言的翻译程序。正如前面所提到的，汇编语言是计算机的机器语言的符号形式，它极易翻译。有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。
(3)
连接程序（linker）
编译器和汇编程序都经常依赖于连接程序，它将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。在这种情况下，目标代码，即还未被连接的机器代码，与可执行的机器代码之间就有了区别。连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。有趣的是，连接程序现在正在完成编译器最早的一个主要活动（这也是“编译”一词的用法，即通过收集不同的来源来构造）。连接过程对操作系统和处理器有极大的依赖性。
(4)
装入程序（loader）
编译器、汇编程序或连接程序生成的代码经常还不完全适用或不能执行，但是它们的主要存储器访问却可以在存储器的任何位置中且与一个不确定的起始位置相关。这样的代码被称为是可重定位的（relocatable），而装入程序可处理所有的与指定的基地址或起始地址有关的可重定位的地址。装入程序使得可执行代码更加灵活，但是装入处理通常是在后台（作为操作环境的一部分）或与连接相联合时才发生，装入程序极少会是实际的独立程序。
(5)
预处理器（preprocessor）
预处理器是在真正的翻译开始之前由编译器调用的独立程序。预处理器可以删除注释、包含其他文件以及执行宏（宏macro是一段重复文字的简短描写）替代。预处理器可由语言（如C）要求或以后作为提供额外功能（诸如为FORTRAN提供Ratfor预处理器）的附加软件。
(6)
编辑器（editor）
编译器通常接受由任何生成标准文件（例如ASCII文件）的编辑器编写的源程序。最近，编译器已与另一个编辑器和其他程序捆绑进一个交互的开发环境——IDE中。此时，尽管编辑器仍然生成标准文件，但会转向正被讨论的程序设计语言的格式或结构。这样的编辑器称为基于结构的（structure based），且它早已包括了编译器的某些操作；因此，程序员就会在程序的编写时而不是在编译时就得知错误了。从编辑器中也可调用编译器以及与它共用的程序，这样程序员无需离开编辑器就可执行程序。
(7)
调试程序（debugger）
调试程序是可在被编译了的程序中判定执行错误的程序，它也经常与编译器一起放在IDE中。运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息（诸如行数、变量名和过程）。它还可以在预先指定的位置（称为断点（breakpoint））暂停执行，并提供有关已调用的函数以及变量的当前值的信息。为了执行这些函数，编译器必须为调试程序提供恰当的符号信息，而这有时却相当困难，尤其是在一个要优化目标代码的编译器中。因此，调试又变成了一个编译问题。
(8)
描述器（profiler）
描述器是在执行中搜集目标程序行为统计的程序。程序员特别感兴趣的统计是每一个过程的调用次数和每一个过程执行时间所占的百分比。这样的统计对于帮助程序员提高程序的执行速度极为有用。有时编译器也甚至无需程序员的干涉就可利用描述器的输出来自动改进目标代码。
(9)
项目管理程序（project manager）
现在的软件项目通常大到需要由一组程序员来完成，这时对那些由不同人员操作的文件进行整理就非常重要了，而这正是项目管理程序的任务。例如，项目管理程序应将由不同的程序员制作的文件的各个独立版本整理在一起，它还应保存一组文件的更改历史，这样就能维持一个正在开发的程序的连贯版本了（这对那些由单个程序员管理的项目也很有用）。项目管理程序的编写可与语言无关，但当其与编译器捆绑在一起时，它就可以保持有关特定的编译器和建立一个完整的可执行程序的链接程序操作的信息。在Unix系统中有两个流行的项目管理程序：sccs（source code control system）和rcs（revision control system）。
编译原理与技术的一整套理论在整个计算机科学领域占有相当重要的地位。学习它，对程序设计人员有很大的帮助。我们考究历史会发现那些人人称颂的程序设计大师都是编译领域的高手，像写出BASIC语言的BILL GATES，SUN的JAVA之父等等，在编译上都有很深的造诣。
我们知道，词法分析在编译器的设计过程中是非常重要的，研究编译原理中的算法可以帮助我们更加深层次的理解程序语言和内部机制，可以用来做简单的命令解释器，比如游戏的脚本引擎。而且，界面开发也需要编译原理的知识。
正则表达式是一种可以用于模式匹配和替换的强有力的工具。例如搜索引擎就用到正则表达式的模式匹配功能。同时我们可以在几乎所有的基于UNIX系统的工具中找到正则表达式的身影，例如，vi编辑器，Perl或PHP脚本语言，以及awk或sed shell程序等。此外，象JavaScript这种客户端的脚本语言也提供了对正则表达式的支持。由此可见，对正则表达式的研究已经超出了某种语言或某个系统的局限。
编译技术几乎是所有计算机高级编程语言（诸如C、C++、JAVA等）所必须的，尽管有些（如BASIC）用解释程序，但解释程序的前端与编译器是相通的，因此研究编译技术是非常必要的。
编译原理的相关技术还可应用于其它许多领域，例如文本编辑器、信息检索系统、模式识别器；排版、绘图系统；程序验证器；集成电路设计；外文翻译等等。
英特尔公司与中国合作项目中最颠峰的技术是中科院计算所与英特尔公司共同合作的IA-64位开放源代码编译系统。编辑器接受以高级程序设计语言(如C、C++和Fortran)编写的程序，并将其转换为处理器能够识别的机器指令。像安腾这样的处理器拥有多个功能部件，能够并行地执行多条指令。因此，要求现代编译器也能够识别源代码中的并行性，对指令流进行高度，以缩短程序的执行时间，提高处理器的性能。随着微处理器体系结构的升级换代，同步提高编译器技术也变得越来越重要。中国科学院计算技术研究所李国杰院士说：“随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量，编译技术成为计算机的核心技术，地位变得越来越重要。我国要发展自己的微处理器事业，必然要有自己的编译技术作为后盾。”“IA-64开放源代码编译系统的研究，有助于掌握先进的处理器和编译器的设计技术以及产品软件开发过程的管理技术和先进的软件工程技术，为研制自有知识产权的微处理器和编译器提供技术储备。”而且，中国的龙芯的成功，应该归功于好的技术路线和编译技术的突破。
3.
程序设计及实现过程
要把正规表达式转换为最小化状态DFA，可以直接通过相关算法转换，但是这将会使得设计过程非常复杂，而且程序的可理解性将会大大降低。所以整个程序通过下列三个步骤实现：
(一)
由正规表达式构造NFA；
(二)
把NFA转化为与其等价的DFA；
(三)
把DFA最小化；
程序设计过程主要是分析各阶段设计过程要用到的相关算法。
(一)
由正规表达式构造NFA：使用Thompson构造法
输入：字母表∑上的一个正规表达式r。
输出：接受L(r)的NFA N。
使用子集构造算法
输入：一个NFA N；
输出：一个接受同样语言的DFA D。
方法：为D构造转换表Dtran，DFA的每个状态是NFA的状态集，D将并行地模拟N对输入串的所有可能的移动。
a
、构造NFA N的状态K的子集的算法：
假定所构造的子集族为C（D的状态集合），即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态S的子集。
开始，令
e
-closure(S0)
为C中唯一成员，并且它是未被标记的。
while
（C中存在尚未被标记的子集T）do begin { 标记T； for 每个输入字母a do begin{
U:=
e
-closure(move(T,a))
；
if U
不在C中 then
将U作为未标记的子集加在C中；
Dtran[T
，a]:=U } }
b
、
e
-closure
的计算
将T中所有的状态压入栈stack中；
将
e
-closure
（T）初始化为T；
While
栈stack不空do begin
将栈顶元素t弹出栈；
for
每个这样的状态u：从t到u有一条标记为
e
的边do
if u
不在
e
-closure
（T）内 do begin
将u添加到
e
-closure
（T）；
将u压入栈stack中
End
End
最小化DFA状态数的算法：
输入：DFA M（其状态集合为S），输入符号为
∑，转换函数为f：S×∑--〉S，开始状态为s0 ，接受状态集为F。
输出：一个DFA M’，它和M接受同样的语言，且状态数最少。
方法：
1、
构造具有两个组的状态集合的初始划分∏：接受状态组F，非接受状态组S-F。
2、
对∏采用下面所述的过程来构造新的划分∏new。
for
∏中的每个组G do begin
当且仅当对任意输入符号a，状态s和t在a上的转换到达∏中的同一组中 的状态时，才把G划分成小组，以便G的两个状态s和t在同一小组中；
/*
最坏情况下，一个状态就可能成为一个组*/
用所有新形成的小组集代替∏new中的G；
end
3、
如果∏new=∏，令∏final=∏，再执行步骤4；否则，令∏:=∏new，重复步骤2。
4、
在划分∏final的每个状态组中选一个状态作为该组的代表，这些代表构成了简化后的DFA M’的状态。令s是一个代表状态，而且假设：在DFA M中，在输入a上有从s到t的转换。令t所在组的代表是r（r可能就是t），那么在M’中有一个从s到r的a上的转换。令包含s0的状态组的代表是M’的开始状态，并令M’的接受状态是那些属于F集的状态所在组的代表。注意，∏final的每个组或者仅含F中的状态，或者不含F中的状态。
5、
如果M’含有死状态（即一个对所有输入符号都有到自身的转换的非接受状态d），即从M’中去掉它；删除从开始状态不可到达的状态；取消从任何其它状态到死状态的转换定义。
词法分析的任务是对输入的字符串形式的源程序按顺序进行扫描，在扫描的同时，根据源语言的词法规则识别具有独立意义的单词（符号），并产生与其等价的属性字流（内部编码）作为输出。通常属性字流即是对识别的单词给出的标记符号的集合。
词法分析程序一般具有如下功能:读入字符串形式的源程序;识别出具有独立意义的最小语法单位:单词。
事实上，由正规表达式到最小化DFA的转换源程序中的测试生成串部分就是对所输入的单词进行判断，看其是否能被生成的DFA接受（也就是这个单词是否符合正规式定义的要求）。这本质上就是一个简单的词法分析。为了更好地说明做这个题目的目的和意义，也为了使本文的主题得到升华，我另外设计了一个用于分析C语言词法的简单的词法分析器，过程如下。
定义某种语言的单词，并给出编号。该语言单词包括：保留字、运算符、标识符、常量、格式符等。根据给定的语言子集构造词法分析器。输出为中间文件。在设计时为了便于理解，不使用内部编码而用中文字符对同类型的单词进行标识。例如所有定义的关键字（保留字）统一用“关键字”对其进行标识，当扫描时遇到关键字就输出该关键字的字符串和“关键字”标识。
词法分析程序的一般设计方法：
1、根据要求写出词法分析的正规文法G；
2、根据正规文法G，写出正则式RE；
3、根据正则式RE，画出NFA；
4、将NFA转化为DFA；
5、将DFA转化为mininum state DFA；
6、mininum state DFA就是词法分析程序的流程图，根据此流程图编写相应的词 法分析程序。