有窮自動(dòng)機(jī)在詞法分析中的應(yīng)用

1、有窮自動(dòng)機(jī)在詞法分析中的應(yīng)用郝亮1|北京林業(yè)大學(xué)，北京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摘要 詞法分析是計(jì)算機(jī)科學(xué)中將字符序列轉(zhuǎn)換為單詞序列的過(guò)程，詞法分析是編譯過(guò)程的第一個(gè)階段，它的 任務(wù)是從左到右一個(gè)字符，一個(gè)字符地讀入源程序或文檔，對(duì)構(gòu)成源

6、程序或文檔的字符流進(jìn)行掃描和分解，從 而識(shí)別出一個(gè)個(gè)單詞并發(fā)送給語(yǔ)法程序。詞法分析器所輸出的但系符號(hào)常常表示成二元式的形式，如（單詞種 別,單詞符號(hào)的屬性值）。而有窮自動(dòng)機(jī)（fa ）分為確定型有窮自動(dòng)機(jī)（dfa ）和非確定型有窮自動(dòng)機(jī)（nfa ）, 它是用來(lái)描述特定類型算法的數(shù)學(xué)方法。特別地，有窮自動(dòng)機(jī)可用作描述在輸入串中識(shí)別的過(guò)程，用有窮自動(dòng) 機(jī)的分析方法可以更加直觀的理解詞法分析的過(guò)程。有窮狀態(tài)機(jī)圖的表示也可以簡(jiǎn)化我們對(duì)詞法分析中的狀態(tài) 轉(zhuǎn)換的理解。有窮自動(dòng)機(jī)在詞法分析中的應(yīng)用非常廣泛。關(guān)鍵詞詞法分析；有窮自動(dòng)機(jī)；dfa ; nfao中圖法分類號(hào)tp391階類號(hào)伍號(hào)1. 詞法分析與有窮自動(dòng)

7、機(jī)詞法分析（英語(yǔ)：lexical analysis）是計(jì)算機(jī)科 學(xué)中將字符序列轉(zhuǎn)換為單詞（token）序列的過(guò)程。 進(jìn)行詞法分析的程序或者兩數(shù)叫作詞法分析 （lexical analyzer,簡(jiǎn)稱 lexer）,也叫掃描器1.1詞法分析概念（scanner）o詞法分析器一般以函數(shù)的形式存在, 供語(yǔ)法分析器調(diào)用。完成詞法分析任務(wù)的程序稱為 詞法分析程序或詞法分析器掃描器。從編譯的允度來(lái)看詞法分析是編譯過(guò)程的第一個(gè)階 段，它的任務(wù)是從左到右一個(gè)字符，一個(gè)字符地讀入 或文檔，對(duì)構(gòu)成源程序或文檔的字符流進(jìn)行掃描和 分解，從而識(shí)別出一個(gè)個(gè)單詞并發(fā)送給語(yǔ)法程序。 詞法分析任務(wù)：(1) 分析和識(shí)別單詞及屬性

8、，包括識(shí)別語(yǔ)言的關(guān)鍵 字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符等；(2) 跳過(guò)各種分隔符，如空格，回車，制表符等;(3) 刪除注釋；(4) 進(jìn)行詞法檢杏，報(bào)告所發(fā)現(xiàn)的錯(cuò)課；(5) 建立符號(hào)表。詞法分析器所輸出的但系符號(hào)常常表示成二元式的 形式，如(單詞種別，單詞符號(hào)的屬性值)。詞法分析前源程序：jmain()z*add*/ i int x=10,y=20,sum; jsum=x+y;經(jīng)過(guò)詞法分析驢果：main. (、)、int、 x、 =、 10.八 y、=、 20、八 sum> 卜 sum.=、x、+、y、；、1.2有窮自動(dòng)機(jī)概念有窮白動(dòng)機(jī)，或有窮狀態(tài)的機(jī)器，是描述(或“機(jī) 器”)特定類型算法的數(shù)學(xué)方

9、法。特別地，有窮白 動(dòng)機(jī)可用作描述在輸入串屮識(shí)別模式的過(guò)程，因此 也能用作構(gòu)造打描程序。當(dāng)然有窮口動(dòng)機(jī)與正則表 達(dá)式z間有著很密切的關(guān)系，在下一節(jié)中大家將會(huì) 看到如何從匸則表達(dá)式小構(gòu)造有窮口動(dòng)機(jī)。但在硏 究有窮自動(dòng)機(jī)z前，先看一個(gè)說(shuō)明的示例。通過(guò)下面的正則表達(dá)式可在程序設(shè)計(jì)語(yǔ)言中給出標(biāo) 識(shí)符模式的一般定義(假設(shè)己定義了 letter和 digit):ide nt 辻 ier = letter ( letter | digit ) *它代 表以一個(gè)字母開(kāi)頭且其后為任意字母和/或數(shù)字序 列的串。通過(guò)標(biāo)明數(shù)字1和2的圓圈農(nóng)示的是狀態(tài)(state),它們表示其中記錄已被發(fā)現(xiàn)的模式的數(shù) 量在識(shí)別過(guò)程11

10、啲位置。帶有箭頭的線代表由記錄源程序 一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)換(transition),該轉(zhuǎn) 換依賴于所標(biāo)字符的匹配。letterdigit冇窮自動(dòng)機(jī)乂分為確定型的冇窮自動(dòng)機(jī)(dfa)與 非確定型的冇窮自動(dòng)機(jī)(nfa)兩種。2.正規(guī)式2.1正規(guī)式的概念正規(guī)式是一種表示正規(guī)集的工具，正規(guī)式是描 述程序語(yǔ)言單詞的表達(dá)式，對(duì)于字母表其上的 正規(guī)式及其表示的正規(guī)集可以遞歸定義如下。 £是一個(gè)正規(guī)式，它表示集合 l( e ) = £ <> 若a是刀上的字符，則a是一個(gè)正規(guī)式， 它所表示的正規(guī)集l(a) = (ao 若正規(guī)式r和s分別表示正規(guī)集 l(r)=l(s),貝lj

11、(a) r|s是正規(guī)式,表示集合l(r) ul(s)；(b) rs是正規(guī)式，表示集合l(r)l(s):(c) r*是正規(guī)式,表示集合(l(r)*；(d) (r)是正規(guī)式,表示集合l(r)o僅由有限次地使用上述三個(gè)步驟定義的表達(dá) 式才是e上的正規(guī)式。運(yùn)算符“丨”、“”、“*”分別稱為“或”、 “連接”和“閉包”。在正規(guī)式的書(shū)寫(xiě)中，連接運(yùn) 算符“ ”可省略。運(yùn)算符的優(yōu)先級(jí)從高到低順序 排列為：“*”、“ ”、“i”。運(yùn)算符“丨”表示“或”、并集?！?”表示* 之前括號(hào)里的內(nèi)容出現(xiàn)0次或多次。若兩個(gè)正規(guī)式表示的正規(guī)集相同，則認(rèn)為二者 等價(jià)。兩個(gè)等價(jià)的正規(guī)集u和v記作u二v。正規(guī)式可以用來(lái)描述符號(hào)串所

12、遵從的規(guī)則，用正規(guī)式所描述的規(guī)則更適用于被計(jì)算機(jī)進(jìn)行高效的 處理。2. 2正規(guī)文法與自動(dòng)機(jī)正規(guī)文法：s->iaa->ia|da| elwa, b, c,.z, dw 1, 2, 3,. 9詞法分析：詞法分析是計(jì)算機(jī)科學(xué)中將字符轉(zhuǎn)換為單 詞序列的過(guò)程，進(jìn)行詞法分析的程序或者函數(shù)叫做詞 法分析器(lexical analyzer,簡(jiǎn)稱lexer),同樣的, 詞法分析是編譯的第一階段工作，它把字符流的源程 序變?yōu)閱卧~序列，單詞序列又可以用正規(guī)式表示出 來(lái)，有窮白動(dòng)機(jī)就是用來(lái)識(shí)別這個(gè)正規(guī)集的裝置。有 窮自動(dòng)機(jī)作為一種能夠準(zhǔn)確地識(shí)別正規(guī)式的裝置，它 能夠準(zhǔn)確地識(shí)別正規(guī)集，即識(shí)別正規(guī)集文法所定

13、義的 語(yǔ)言和正規(guī)時(shí)所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理 論，止是為詞法分析程序的自動(dòng)構(gòu)造特殊的方法和工 rto有窮口動(dòng)機(jī)分為兩類：確定的有窮口動(dòng)機(jī) (deterministic finite automata)和不確定的有窮自動(dòng) 機(jī)(non deterministic finite automata)有窮自動(dòng)機(jī)通 過(guò)不同的輸入進(jìn)入不同的狀態(tài)，并以此識(shí)別單詞序 列。4. nfa 與 dfa4.1 nfa的概念3 詞法分析與有窮自動(dòng)機(jī)的關(guān)系4. 2 nfa與正規(guī)文法的關(guān)系(1) nfa的字母表為文法的非終結(jié)符號(hào)集；(2) nfa的狀態(tài)集為文法的非終結(jié)符號(hào)集；(3) nfa的初態(tài)對(duì)應(yīng)于文法的開(kāi)始符號(hào)；

14、(4) nfa的轉(zhuǎn)換函數(shù)f(a, t)二b,寫(xiě)成一個(gè)產(chǎn)生式 a-* tb；(5) 對(duì)nfa的終態(tài)z,增加一個(gè)產(chǎn)生式z- £4. 3 dfa的概念非確定型有窮h動(dòng)機(jī)：(nfa) n是一個(gè)五元組：n二(工，q, f, s, z)其中k：有窮非空的狀態(tài)集合；s：有窮非空的輸入符號(hào)字母表；f： f是一個(gè)多值函數(shù)，是從qxz*到q的了集的映射;確定型有窮h動(dòng)機(jī)：(dfa) d是一個(gè)五元組：d二(工,q, f, s, z)其中k：有窮非空的狀態(tài)集合；有窮非空的輸入符號(hào)字母表；f：轉(zhuǎn)換函數(shù)，是在kx s->k±的映像，即，如swq是唯一的一個(gè)初態(tài)；zu k是非空的終態(tài)集合。m(ki

15、,a)=kj, (kiek,kjek)就意味著,當(dāng)前狀態(tài)為 ki,輸入符為。時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj,我們?nèi)?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的一個(gè)后繼狀態(tài);swq是唯一的一個(gè)初態(tài)；zu k是非空的終態(tài)集合。若 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用有窮自動(dòng)機(jī)識(shí)別單詞序列的實(shí)例 與文法gs等價(jià)的nfags:s-aa|bb| ea->ab|bab-*as|ba| £識(shí)另lj aaba的過(guò)程：(1) 開(kāi)始進(jìn)入s；(2) 遇到a進(jìn)入a狀態(tài)；(3) 遇到一個(gè)a進(jìn)入b狀態(tài)；(4) 遇到一個(gè)b進(jìn)入返冋a狀態(tài)；(5) 遇到一個(gè)a進(jìn)入b狀態(tài)；(6) 最后遇到一個(gè)空進(jìn)入終止?fàn)顟B(tài)z,識(shí)別結(jié)束。6結(jié)束語(yǔ)有窮自動(dòng)機(jī)是我們分析一個(gè)正規(guī)式最常川方法，它不 僅把符號(hào)語(yǔ)言轉(zhuǎn)化為一個(gè)可以便于理解的圖，簡(jiǎn)化了 我們對(duì)一個(gè)正規(guī)文法的理解難度，而r冇窮自動(dòng)機(jī)中 無(wú)論是dfa述是nfa,我們都可以通過(guò)狀態(tài)跟蹤，更 加直觀的理解識(shí)別單詞序列時(shí)詞法分析程序的狀態(tài) 轉(zhuǎn)換。有窮自動(dòng)機(jī)能夠準(zhǔn)確識(shí)別正規(guī)集，是詞法分析 過(guò)程中很重要的一個(gè)環(huán)節(jié)。參考文獻(xiàn)1 壬麗.詞法分析程序的設(shè)計(jì)實(shí)現(xiàn) 電腦対識(shí)與技術(shù).2011 (32) 7919-79222 王冊(cè)，劉劍，基于高級(jí)程序設(shè)計(jì)語(yǔ)言語(yǔ)句的語(yǔ)法分析其設(shè)計(jì)和實(shí)現(xiàn).硅谷,2012(06) 57-59 廖媛媛，吳曉紅，王雨洋基于c/c+的詞法分析器的設(shè)計(jì)與實(shí)現(xiàn).現(xiàn)代計(jì)算機(jī)(專業(yè)版)，2013 (24) 76(4|