第四章詞法分析

1、：詞法分析程序的功能，狀態(tài)轉(zhuǎn)換圖，有窮自動(dòng)機(jī)、正規(guī)文法、正規(guī)表達(dá)式的相互轉(zhuǎn)換，詞法分析程序的設(shè)計(jì)方法。：由正規(guī)表達(dá)式構(gòu)造確定化的有窮自動(dòng)機(jī)，確定有窮自動(dòng)機(jī)的最小化，詞法分析程序的設(shè)計(jì)方法。：由正規(guī)表達(dá)式構(gòu)造確定化的有窮自動(dòng)機(jī)。 4.1 詞法分析程序設(shè)計(jì)詞法分析的主要任務(wù)是從左至右從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生產(chǎn)生單詞序列，用以語(yǔ)法分析。單詞符號(hào)是一個(gè)程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法符號(hào)，分為五種。單詞的種類有單詞的種類有五種五種：基本字基本字：也稱保留字，如：也稱保留字，如 IF、END等等運(yùn)算符運(yùn)算符：如：如 +、-、*、/、 = 等等等等標(biāo)識(shí)符標(biāo)識(shí)符：用戶定義的變量名、常數(shù)名、：用戶定義的

2、變量名、常數(shù)名、 過(guò)程名等過(guò)程名等常數(shù)常數(shù)：如：如3.14、100、TRUE 等數(shù)等數(shù)界符界符：如：如，、.、（、； 等等4.2 詞法的描述4.2.1 正規(guī)文法也被稱為也被稱為3型文法。型文法。規(guī)則式限制為下面形式之一：規(guī)則式限制為下面形式之一： AaAa AaB AaB 其中A A、BVBVN N，aVaVT T* * 。正規(guī)正規(guī)文法所描述的是（V VN N V VT T）上的正規(guī)集。上的正規(guī)集。 4.2.2 正規(guī)式是表示正規(guī)集的工具 4.2.2 4.2.2 正規(guī)式正規(guī)式 設(shè)r，s，t 為正規(guī)式，其服從的代數(shù)規(guī)律有：1 r s= s r “或或”滿足交換律滿足交換律2 r （s t）=（r

3、s） t “或或”滿足可結(jié)合律滿足可結(jié)合律3（r s）t=r（st） “連接連接”可結(jié)合律可結(jié)合律4 r（s t）= r s r t 或（或（s t）r =s r t r 分配律分配律5 r = r 或或 r= r 是是“連接連接”的恒等元素的恒等元素4.2.3 正規(guī)文法與正規(guī)式v正規(guī)式到正規(guī)文法的轉(zhuǎn)換正規(guī)式到正規(guī)文法的轉(zhuǎn)換4.2.3 正規(guī)文法與正規(guī)式v正規(guī)文法到正規(guī)式的轉(zhuǎn)換正規(guī)文法到正規(guī)式的轉(zhuǎn)換 4.3 有窮自動(dòng)機(jī)n確定有窮自動(dòng)機(jī)n不確定有窮自動(dòng)機(jī)4.3 有窮自動(dòng)機(jī) 4.3.1確定的有窮自動(dòng)機(jī)（DFA）M = （K，f, S, Z） 五元組K：是一個(gè)有窮集，它的每個(gè)元素是一個(gè)狀態(tài)：有窮字母表

4、，它的每個(gè)元素是一個(gè)輸入字符f：轉(zhuǎn)換函數(shù)，是KK上的映像S：S K是唯一的一個(gè)初態(tài)Z：Z K，是一個(gè)終態(tài)集（即結(jié)束狀態(tài)） 例4.6 DFA的狀態(tài)圖和矩陣表示例：從下圖結(jié)點(diǎn)S出發(fā)，最終到達(dá)結(jié)點(diǎn)Z，請(qǐng)判斷01101 或1001可否為路徑上符號(hào)的連結(jié)？語(yǔ)言和自動(dòng)機(jī)語(yǔ)言和自動(dòng)機(jī)自動(dòng)機(jī)自動(dòng)機(jī): : 12開始開始a 0abb正規(guī)式：正規(guī)式：(a|b)*ab 4.3.2 不確定有窮自動(dòng)機(jī)一個(gè)不確定的有窮自動(dòng)機(jī)（NFA）M也是一個(gè)五元組：M=(K,f,S,Z)其中n K是一個(gè)有窮集，它的每一個(gè)元素稱為一個(gè)狀態(tài)；n 是一個(gè)有窮字母表，它的每一個(gè)元素稱為一個(gè)輸入字符；n f是一個(gè)K*到 K的子集的映像；n S K

5、，是一個(gè)非空初態(tài)集非空初態(tài)集；n Z K是一個(gè)終態(tài)集。4.3.3 不確定到確定的轉(zhuǎn)換轉(zhuǎn)換n設(shè)L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存在一個(gè)接受L的確定的有窮自動(dòng)機(jī)。關(guān)于狀態(tài)集合的兩個(gè)運(yùn)算n-Closure(I)運(yùn)算：n該運(yùn)算結(jié)果是一狀態(tài)集，I中任意狀態(tài)經(jīng)任意多條弧轉(zhuǎn)變所能達(dá)到的狀態(tài)的集合。nMove(I,a)運(yùn)算:n該運(yùn)算結(jié)果是一狀態(tài)集，是I中任意狀態(tài)經(jīng)過(guò)一次a弧轉(zhuǎn)變達(dá)到的狀態(tài)的集合。n關(guān)于狀態(tài)集合的兩個(gè)運(yùn)算關(guān)于狀態(tài)集合的兩個(gè)運(yùn)算n有NFA N=(K,f,K0,Kt)存在，設(shè)與之等價(jià)的 DFA M= (S,D,S0,St)則 ：1. S是由K的一些子集組成（即：若ki, kj, klS，則

6、kiK, kjK, klK）。且S中的元素可由以下算法確定： 開始，令-Closure(k0)是C中的唯一成員，且未標(biāo)記； while (C中存在未標(biāo)記的集合時(shí)), do標(biāo)記，未標(biāo)記的集合為T； for 每個(gè)輸入字母a do U= -Closure(Move(T,a); if U不在C中 then 將U作為未標(biāo)記的集合加在C中 U C, U S3. 令容器C中元素為T0,T1,Tk，則轉(zhuǎn)換函數(shù)D定義為: D(Ti,a)=Tj形式, 其中: i,j0，1，k(即I,j介于0-k之間) -Closure(MoveTi,a)=Tj;4. S0=-Closure(K0)為M的開始狀態(tài)；5. St=Tl

7、,TlS且TlKt2. M 和N的輸入字母表相同，即；n子集轉(zhuǎn)化法子集轉(zhuǎn)化法確定有窮自動(dòng)機(jī)的化簡(jiǎn)n 化簡(jiǎn)途徑： 1 去除多余狀態(tài)： 多余狀態(tài)： 從確定有窮自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的狀態(tài)。 2 合并等價(jià)狀態(tài)： 等價(jià)狀態(tài)：在有窮自動(dòng)機(jī)中，兩個(gè)狀態(tài)s,t滿足下列兩個(gè)條件，則s與t狀態(tài)等價(jià)： （1）狀態(tài)s和t必須同時(shí)為可接受狀態(tài)（一致性） （2）對(duì)于所有輸入符號(hào)，狀態(tài)s,t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里（蔓延性） 消除多余狀態(tài)例: 0 10 10 10 1例 4.9P0=(1,2,3,4,5,6,7)4.4 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性n有窮自動(dòng)機(jī)正規(guī)式使L（R）=L（M）n正規(guī)式有窮自動(dòng)機(jī)使

8、L（ M ）=L（R）4.4 正規(guī)式與有窮自動(dòng)機(jī)的等價(jià)性例4.101.（a）對(duì)正規(guī)式對(duì)正規(guī)式 ，所構(gòu)造的，所構(gòu)造的NFA為：為： 正規(guī)式和自動(dòng)機(jī)的等價(jià)性可使它們之間進(jìn)行轉(zhuǎn)換，正規(guī)文法和有窮自動(dòng)機(jī)也可從正規(guī)文法G G直接構(gòu)造一個(gè)有窮自動(dòng)機(jī)NFA MNFA M，使得L L（M M）=L=L（G G）：字母表與G G的終極符集相同；為G G中的每個(gè)非終極符生成M的一個(gè)狀態(tài)，G G的開始符號(hào)S S的開始狀態(tài)S S；增加一個(gè)新狀態(tài)Z Z，做為NFANFA的終態(tài)；對(duì)G G中的形如A t BA t B其中t t為終極符或，A A和B B為非終極符的產(chǎn)生式，構(gòu)造M M的一個(gè)轉(zhuǎn)換函數(shù)f(Af(A，t t）= B

9、= B；對(duì)G G中形如A tA t的產(chǎn)生式，構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f f（A A，t t）= Z= Z。 4 4.5 .5 正規(guī)文法和有窮自動(dòng)機(jī)的轉(zhuǎn)換正規(guī)文法和有窮自動(dòng)機(jī)的轉(zhuǎn)換A aBB bAB aSB bAB 例4.13 給出下圖NFA M等價(jià)的正規(guī)文法: C- D- LEX是由美國(guó)Bell實(shí)驗(yàn)室的M.Lesk和Schmidt于1975年用C語(yǔ)言研制的一個(gè)詞法分析程序的自動(dòng)生成工具。對(duì)任何高級(jí)程序語(yǔ)言，用戶必須用正規(guī)表達(dá)式描述該語(yǔ)言的各個(gè)詞法類（這一描述稱為L(zhǎng)EX的源程序），LEX就可以自動(dòng)生成該語(yǔ)言的詞法分析程序。4.6 詞法分析器的自動(dòng)生成系統(tǒng)4.6 詞法分析器的自動(dòng)生成系統(tǒng)nlex是一個(gè)

10、詞法分析器（掃描器）的自動(dòng)產(chǎn)生系統(tǒng)。它是基于UNIX系統(tǒng)的.nLex編譯程序把Lex源程序轉(zhuǎn)換成一個(gè)C語(yǔ)言的可運(yùn)行程序,這個(gè)程序放在Lex.yy.c文件中(是個(gè)C程序)再經(jīng)由C編譯生成目標(biāo)文件a.out(詞法分析程序)可將輸入字符流變成單詞流.lexlex是用一種面向問(wèn)題的語(yǔ)言寫成的。這個(gè)語(yǔ)言的核心是正規(guī)正規(guī)表達(dá)式表達(dá)式，用它描述輸入串的詞法結(jié)構(gòu)。LexLex不是一個(gè)完整的語(yǔ)言是某種高級(jí)語(yǔ)言的擴(kuò)充。 nLEX源程序詞法分析器 Ln輸入串 單詞符號(hào)串 Lex讀入詞法分析器的規(guī)格說(shuō)明,根據(jù)此說(shuō)明生成一個(gè)用C語(yǔ)言描述的詞法分析器.把描述詞法分析器規(guī)格說(shuō)明的語(yǔ)言描述詞法分析器規(guī)格說(shuō)明的語(yǔ)言稱為詞法分析

11、器設(shè)計(jì)語(yǔ)言或Lex語(yǔ)言.用Lex語(yǔ)言書寫的詞法分析器規(guī)格說(shuō)明稱為L(zhǎng)ex源程序.實(shí)用程序Lex把Lex源程序翻譯成C語(yǔ)言描述的目標(biāo)程序,所以通常也稱為L(zhǎng)ex編譯器.LEX及其編譯系統(tǒng)的作用如下：詞法分析程序詞法分析程序 L LLEX編譯系統(tǒng)編譯系統(tǒng)輔助定義部分% 識(shí)別規(guī)劃部分% 用戶子程序部分 Lex源程序的格式： Lex的實(shí)現(xiàn)： 化簡(jiǎn) 正規(guī)式正規(guī)式 NFA DFA DFA 詞法分析程序詞法分析程序 1將每條規(guī)則變成一個(gè)NFA； 2. Pi action ：0 MiPi3. 將NFA化為DFA 4將DFA根據(jù)控制規(guī)則轉(zhuǎn)化成程序見例XiPi XiXiPiPi Mi Mi nLEX可以用兩種方式來(lái)使用：一種是將LEX作為一個(gè)單獨(dú)的工具，用以生成所需的識(shí)別程序；另一種是將LEX和語(yǔ)法分析器自動(dòng)生成工具（如YACC）結(jié)合起來(lái)使用，以生成一個(gè)編譯程序的掃描器和語(yǔ)法分析器。 小小 結(jié)結(jié)u詞法分析程序的功能是輸入源程序，輸出單詞符號(hào)。u詞法分析程序?qū)⒁罁?jù)語(yǔ)言詞法規(guī)則，分析由字符組成的源程序，把它識(shí)別為一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，即“單詞”，并識(shí)別出與其相關(guān)的屬性(如該單詞是標(biāo)識(shí)符