有穷自动机在词法分析中的应用

1、有穷自动机在词法分析中的应用郝亮1|北京林业大学，北京100083（heroleo ）the application of finite automaton in lexical analysis of compiling principleliang hao"1 (beijing forestry university , beijing 100083)abstractlexical analysis is a sequence of chiiracters in the computer science convert word sequence process, lexical

2、 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 constitution character stream source or document scanning and decomposition, thereby identifying words and sent a granimar program. lexi

3、cal 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 wo rd symbols). the finite automata (fa) is divided into a deterministic finite automaton (dfa) and non-deterministic finite automata (nf a), which is used

4、 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 analysi s of finite automata finite state mac

5、hine diagram indicates also simplifies our lexical analysis of state transitions of understanding. finit e automata lexical analysis is widely used.key words lexical analysis; finite automata; dfa; nfa; regular expression摘要 词法分析是计算机科学中将字符序列转换为单词序列的过程，词法分析是编译过程的第一个阶段，它的 任务是从左到右一个字符，一个字符地读入源程序或文档，对构成源

6、程序或文档的字符流进行扫描和分解，从 而识别出一个个单词并发送给语法程序。词法分析器所输出的但系符号常常表示成二元式的形式，如（单词种 别,单词符号的属性值）。而有穷自动机（fa ）分为确定型有穷自动机（dfa ）和非确定型有穷自动机（nfa ）, 它是用来描述特定类型算法的数学方法。特别地，有穷自动机可用作描述在输入串中识别的过程，用有穷自动 机的分析方法可以更加直观的理解词法分析的过程。有穷状态机图的表示也可以简化我们对词法分析中的状态 转换的理解。有穷自动机在词法分析中的应用非常广泛。关键词词法分析；有穷自动机；dfa ; nfao中图法分类号tp391阶类号伍号1. 词法分析与有穷自动

7、机词法分析（英语：lexical analysis）是计算机科 学中将字符序列转换为单词（token）序列的过程。 进行词法分析的程序或者两数叫作词法分析 （lexical analyzer,简称 lexer）,也叫扫描器1.1词法分析概念（scanner）o词法分析器一般以函数的形式存在, 供语法分析器调用。完成词法分析任务的程序称为 词法分析程序或词法分析器扫描器。从编译的允度来看词法分析是编译过程的第一个阶 段，它的任务是从左到右一个字符，一个字符地读入 或文档，对构成源程序或文档的字符流进行扫描和 分解，从而识别出一个个单词并发送给语法程序。 词法分析任务：(1) 分析和识别单词及属性

8、，包括识别语言的关键 字、标识符、常数、运算符等；(2) 跳过各种分隔符，如空格，回车，制表符等;(3) 删除注释；(4) 进行词法检杏，报告所发现的错课；(5) 建立符号表。词法分析器所输出的但系符号常常表示成二元式的 形式，如(单词种别，单词符号的属性值)。词法分析前源程序：jmain()z*add*/ i int x=10,y=20,sum; jsum=x+y;经过词法分析驴果：main. (、)、int、 x、 =、 10.八 y、=、 20、八 sum> 卜 sum.=、x、+、y、；、1.2有穷自动机概念有穷白动机，或有穷状态的机器，是描述(或“机 器”)特定类型算法的数学方

9、法。特别地，有穷白 动机可用作描述在输入串屮识别模式的过程，因此 也能用作构造打描程序。当然有穷口动机与正则表 达式z间有着很密切的关系，在下一节中大家将会 看到如何从匸则表达式小构造有穷口动机。但在硏 究有穷自动机z前，先看一个说明的示例。通过下面的正则表达式可在程序设计语言中给出标 识符模式的一般定义(假设己定义了 letter和 digit):ide nt 辻 ier = letter ( letter | digit ) *它代 表以一个字母开头且其后为任意字母和/或数字序 列的串。通过标明数字1和2的圆圈农示的是状态(state),它们表示其中记录已被发现的模式的数 量在识别过程11

10、啲位置。带有箭头的线代表由记录源程序 一个状态向另一个状态的转换(transition),该转 换依赖于所标字符的匹配。letterdigit冇穷自动机乂分为确定型的冇穷自动机(dfa)与 非确定型的冇穷自动机(nfa)两种。2.正规式2.1正规式的概念正规式是一种表示正规集的工具，正规式是描 述程序语言单词的表达式，对于字母表其上的 正规式及其表示的正规集可以递归定义如下。 £是一个正规式，它表示集合 l( e ) = £ <> 若a是刀上的字符，则a是一个正规式， 它所表示的正规集l(a) = (ao 若正规式r和s分别表示正规集 l(r)=l(s),贝lj

11、(a) r|s是正规式,表示集合l(r) ul(s)；(b) rs是正规式，表示集合l(r)l(s):(c) r*是正规式,表示集合(l(r)*；(d) (r)是正规式,表示集合l(r)o仅由有限次地使用上述三个步骤定义的表达 式才是e上的正规式。运算符“丨”、“”、“*”分别称为“或”、 “连接”和“闭包”。在正规式的书写中，连接运 算符“ ”可省略。运算符的优先级从高到低顺序 排列为：“*”、“ ”、“i”。运算符“丨”表示“或”、并集。“*”表示* 之前括号里的内容出现0次或多次。若两个正规式表示的正规集相同，则认为二者 等价。两个等价的正规集u和v记作u二v。正规式可以用来描述符号串所

12、遵从的规则，用正规式所描述的规则更适用于被计算机进行高效的 处理。2. 2正规文法与自动机正规文法：s->iaa->ia|da| elwa, b, c,.z, dw 1, 2, 3,. 9词法分析：词法分析是计算机科学中将字符转换为单 词序列的过程，进行词法分析的程序或者函数叫做词 法分析器(lexical analyzer,简称lexer),同样的, 词法分析是编译的第一阶段工作，它把字符流的源程 序变为单词序列，单词序列又可以用正规式表示出 来，有穷白动机就是用来识别这个正规集的装置。有 穷自动机作为一种能够准确地识别正规式的装置，它 能够准确地识别正规集，即识别正规集文法所定

13、义的 语言和正规时所表示的集合，引入有穷自动机这个理 论，止是为词法分析程序的自动构造特殊的方法和工 rto有穷口动机分为两类：确定的有穷口动机 (deterministic finite automata)和不确定的有穷自动 机(non deterministic finite automata)有穷自动机通 过不同的输入进入不同的状态，并以此识别单词序 列。4. nfa 与 dfa4.1 nfa的概念3 词法分析与有穷自动机的关系4. 2 nfa与正规文法的关系(1) nfa的字母表为文法的非终结符号集；(2) nfa的状态集为文法的非终结符号集；(3) nfa的初态对应于文法的开始符号；

14、(4) nfa的转换函数f(a, t)二b,写成一个产生式 a-* tb；(5) 对nfa的终态z,增加一个产生式z- £4. 3 dfa的概念非确定型有穷h动机：(nfa) n是一个五元组：n二(工，q, f, s, z)其中k：有穷非空的状态集合；s：有穷非空的输入符号字母表；f： f是一个多值函数，是从qxz*到q的了集的映射;确定型有穷h动机：(dfa) d是一个五元组：d二(工,q, f, s, z)其中k：有穷非空的状态集合；有穷非空的输入符号字母表；f：转换函数，是在kx s->k±的映像，即，如swq是唯一的一个初态；zu k是非空的终态集合。m(ki

15、,a)=kj, (kiek,kjek)就意味着,当前状态为 ki,输入符为。时，将转换为下一个状态kj,我们若 m: (0, 1,2,3, a, b,f, 0, 3)f (0, a) =1f (1, a) =3f (2, a) =1f (3, a) =3f (0, b) =2f (1, b) =2f (2, b) =3f (3, b) =3得岀nfa图:把kj称作ki的一个后继状态;swq是唯一的一个初态；zu k是非空的终态集合。若 m: (0, 1,2,3, a,b,f, 0, 3)f (0,a) =1f (1, a) =3f (2,a) =1f (0, b) =2f (1, b) =2f

16、 (2, b) =3f (3, a) =3f (3, b) =3得出nfa图:a.b5用有穷自动机识别单词序列的实例 与文法gs等价的nfags:s-aa|bb| ea->ab|bab-*as|ba| £识另lj aaba的过程：(1) 开始进入s；(2) 遇到a进入a状态；(3) 遇到一个a进入b状态；(4) 遇到一个b进入返冋a状态；(5) 遇到一个a进入b状态；(6) 最后遇到一个空进入终止状态z,识別结束。6结束语有穷自动机是我们分析一个正规式最常川方法，它不 仅把符号语言转化为一个可以便于理解的图，简化了 我们对一个正规文法的理解难度，而r冇穷自动机中 无论是dfa述是nfa,我们都可以通过状态跟踪，更 加直观的理解识别单词序列时词法分析程序的状态 转换。有穷自动机能够准确识别正规集，是词法分析 过程中很重要的一个环节。参考文献1 壬丽.词法分析程序的设计实现 电脑対识与技术.2011 (32) 7919-79222 王册，刘剑，基于高级程序设计语言语句的语法分析其设计和实现.硅谷,2012(06) 57-59 廖媛媛，吴晓红，王雨洋基于c/c+的词法分析器的设计与实现.现代计算机(专业版)，2013 (24) 76(4|