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

1、有窮自動機(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ī)科學(xué)中將字符序列轉(zhuǎn)換為單詞序列的過程，詞法分析是編譯過程的第一個階段，它的 任務(wù)是從左到右一個字符，一個字符地讀入源程序或文檔，對構(gòu)成源

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

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

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

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

10、啲位置。帶有箭頭的線代表由記錄源程序 一個狀態(tài)向另一個狀態(tài)的轉(zhuǎn)換(transition),該轉(zhuǎn) 換依賴于所標(biāo)字符的匹配。letterdigit冇窮自動機(jī)乂分為確定型的冇窮自動機(jī)(dfa)與 非確定型的冇窮自動機(jī)(nfa)兩種。2.正規(guī)式2.1正規(guī)式的概念正規(guī)式是一種表示正規(guī)集的工具，正規(guī)式是描 述程序語言單詞的表達(dá)式，對于字母表其上的 正規(guī)式及其表示的正規(guī)集可以遞歸定義如下。 £是一個正規(guī)式，它表示集合 l( e ) = £ <> 若a是刀上的字符，則a是一個正規(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僅由有限次地使用上述三個步驟定義的表達(dá) 式才是e上的正規(guī)式。運算符“丨”、“”、“*”分別稱為“或”、 “連接”和“閉包”。在正規(guī)式的書寫中，連接運 算符“ ”可省略。運算符的優(yōu)先級從高到低順序 排列為：“*”、“ ”、“i”。運算符“丨”表示“或”、并集?！?”表示* 之前括號里的內(nèi)容出現(xiàn)0次或多次。若兩個正規(guī)式表示的正規(guī)集相同，則認(rèn)為二者 等價。兩個等價的正規(guī)集u和v記作u二v。正規(guī)式可以用來描述符號串所

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

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

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

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