下载文档原格式
词法分析器的作用词法分析是编译的第一阶段。
词法分析器的主要任务是读入源程序的输入字符，将它们组成词素，生成并输出一个词法单元序列，这个词法单元序列被输出到语法分析器进行语法分析。
另外，由于词法分析器在编译器中负责读取源程序，因此除了识别词素之外，它还会完成一些其他任务，比如过滤掉源程序中的注释和空白，将编译器生成的错误消息与源程序的位置关联起来等。
总而言之，词法分析器的作用如下：1.读入源程序的输入字符，将它们组成词素，生成并输出一个词法单元序列；2.过滤掉源程序中的注释和空白；3.将编译器生成的错误消息与源程序的位置关联起来；4.其它。
词法分析过程首先，对某个正则语言L，构造能够描述其的正则表达式r；然后，需要将r 转换成一个有穷自动机。
这里有三种方法，一是直接转换成NFA，而是直接转换成DFA，三是先转换成NFA，再把NFA 转换成DFA；最后，如果将r 转换成了一个DFA，需要将此DFA 的状态数最小化。
正则表达式正则表达式可以用来描述词素的模式，一个正则表达式可以由较小的正则表达式递归的构建。
对于符号集合∑={a，b}，有：-正则表达式a 表示语言{a}；-正则表达式a|b 表示语言{a，b}；-正则表达式(a|b)(a|b)表示语言{aa，ab，ba，bb}；-正则表达式a*表示语言{ε，a，aa，aaa，…}；-正则表达式(a|b)*表示语言{ε，a，b，aa，ab，ba，bb，aaa，…}；-正则表达式a|a*b 表示语言{a，b，ab，aab，aaab，…}。
上面通过基本的并、连接和闭包运算递归定义了正则表达式有穷自动机一个有穷自动机可以把一个描述词素的模式变成一个词法分析器，从本质上来讲，有穷自动机是与状态转换图相类似的图，它有以下特点：有穷自动机是一个识别器，它只能对每个输入符号串简单的输出“yes”或“no”，表示是否能够识别此符号串；有穷自动机和状态转换图类似，它具有有限个数的结点，每个结点表示一个状态，并且这些状态中有一个初始状态和若干个终止状态。
第3章词法分析和有限自动机1．词法分析器和语法分析器的相互作用见教科书屠3。
12．单词符号、词法记号单词符号是程序设计语言的基本语法符号，它由该程序设计语言的字母表上的字符，按照该语言的词法规则组成的。
3．单词符号的表示单词符号的输出通常用二元组表示：(单词种别，单词自身的值)单词种别说明单词所属的类别，单词的值则是单词在类中的属性值，是为了正确区分同一类别中的不同单词所必须的。
4．Token单词种别又称为token。
5．模式构成单词的规则称为模式，它用于刻画token。
6．词素词素是与关于token的模式所匹配的源程序中的一个字符串。
7．词法规则隶属于语法规则，8．把词法分析分离出来作为一个独立的阶段来考虑，有如下好处：∨使整个编译程序的结构更简洁、更清晰和更有条理化；∨提高了编译程序的效率；∨增加了编译程序的可移植性；9．正则表达式由一些运算对象（符号串）和一些运算符号按照一定的规则组成，类似于算术表达式，它是描述正则集的工具。
10．正规集正规式表示简单的语言，叫做正规集11．正则式和正则集的定义设∑是一字母表，∑上的正则式和正则集定义如下：1.ε和φ是∑上的正则表达式，所表示的正则集分别为{ε}和φ。
2.任何a∈∑，a是∑上的正则表达式，所表示的正则集为{a}。
3.设e1和e2都是∑上的正则表达式，所表示的正则集分别为L(e1)和L(e2)，那么，(1) (e1)是∑上的正则表达式，所表示的正则集为L(e1);(2) e1|e2是∑上的正则表达式，所表示的正则集为L(e1)∪L(e2)；(3) e1∙e2是∑上的正则表达式，所表示的正则集为L(e1) L(e2)；(4) e1*是∑上的正则表达式，所表示的正则集为(L(e1))*。
4.仅由有限次使用上述三步骤而定义的表达式才是∑上的正则表达式，仅由这些正则式所表示的集合才是∑上的正则集。
12．正则式的等价若e1和e2都是∑上的正则表达式，它们所表示的正则集分别为L(e1)和L(e2)，且有L(e1)＝L(e2)，则称e1和e2等价。
有穷自动机在词法分析中的应用郝亮11北京林业大学，北京100083(heroleo@)The application of finite automaton in lexical analysis of compiling principleLiang Hao11(Beijing Forestry University , Beijing 100083)AbstractLexical analysis is a sequence of characters in the computer science convert word sequence process, lexical analysis is the first stage of t he compilation process, and its task is left to right, a character, a character read into the source code or documentation of the constitutioncharacter stream source or document scanning and decomposition, thereby identifying words and sent a grammar program. Lexical anal yzer output but the system is often expressed as a binary notation style forms, such as (the word species do not, the property value of word symbols). The finite automata (FA) is divided into a deterministic finite automaton (DFA) and non-deterministic finite automata (NF A), which is used to describe a specific type of algorithm of mathematical methods. In particular, a finite automaton can be used as descr ibed in the identification process in the input string, using analytical methods can process more intuitive understanding of lexical analysis of finite automata. Finite state machine diagram indicates also simplifies our lexical analysis of state transitions of understanding. Finite Automata Lexical analysis is widely used.Key words Lexical analysis; finite automata; DFA; NFA; regular expression摘要词法分析是计算机科学中将字符序列转换为单词序列的过程，词法分析是编译过程的第一个阶段，它的任务是从左到右一个字符,一个字符地读入源程序或文档，对构成源程序或文档的字符流进行扫描和分解，从而识别出一个个单词并发送给语法程序。
