《編譯原理課件詞法分析.ppt》由會員分享，可在線閱讀，更多相關《編譯原理課件詞法分析.ppt（124頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、編譯程序的結構,,表 格 管 理,詞法分析器,語法分析器,語義分析與中間代碼產(chǎn)生,優(yōu)化器,目標代碼生成器,源程序,單詞符號,語法單位,中間代碼,中間代碼,目標代碼,,出 錯 處 理,,,,,,,,,,,,,,,,,第三章 詞法分析,詞法分析的任務是：從左至右逐個字符地對源程序進行掃描，產(chǎn)生一個個單詞符號，把作為字符串的源程序改造成為單詞符號串的中間程序。 詞法分析是編譯的基礎。 執(zhí)行詞法分析的程序稱為詞法分析器。,3.1 對詞法分析器的要求,3.1.1 詞法分析器功能和輸出形式 功能：輸入源程序，輸出單詞符號（單詞記號文件） 單詞符號（token）:具有完整語義的最小的單位，不可分割。 輸出形

2、式：根據(jù)單詞符號的不同，構造表示單詞符號的機內(nèi)表示token,以二元組形式表示，存放在文件中（形成源程序的內(nèi)碼文件）。 二元組形式:(單詞種別編碼，單詞的屬性值）,內(nèi)碼文件的形式,for (i=0;i<=10,i--) (for ,-)((,-)(i，符號表入口)(=,-)(整形常數(shù),常數(shù)表入口)(;-).,單詞種別編碼與單詞符號屬性值,考慮下述C++代碼段： while (i=j) i- -; 經(jīng)詞法分析器處理后，它將轉換為如下的單詞符號序列： = , - ,3.1.2 詞法分析器的構造方式-詞法分析器作為獨立子程序,詞法分析器安排成語法分析的子程序。 好處在于：編譯器結構清

3、晰。,源程序,詞法分析,語法分析,,,,,call,read,token,char,3.1.2 詞法分析器作為獨立子程序,詞法分析器作為獨立的遍 工作方式：不是任何程序的子程序，獨立的完成一遍任務。 缺點：需要保存單詞符號文件，占用內(nèi)存,源程序,詞法分析,單詞記號 文件,,,,read,token,char,3.2 詞法分析器的設計,3.2.1 輸入、預處理,,預處理 空白符，制表符、回車符，注釋語句等 構造預處理程序,詞法分析器的工作,分析器對掃描緩沖區(qū)進行掃描一進行單詞的識別。 掃描時一般使用兩個指示器 掃描緩沖區(qū)最好使用如下一分為二的區(qū)域：（循環(huán)隊列的形式）。,詞法分析器的結構,,,,3

4、.2.2 單詞符號的識別：超前搜索,超前搜索技術 在單詞識別的過程中，通過向前多讀幾個符號的形式，準確的進行單詞的識別 一旦確定識別到的單詞之后，需要進行掃描指針的回退，保證單詞識別工作的順利進行 DO99K=1,10 IF(5.EQ.M)I=10 DO99K=1.10 IF(5)=55,關鍵字的識別,像FORTRAN這樣的語言，關鍵字不加保護（只要不引起矛盾，用戶可以用它們作為普通標識符） 借助于超前搜索技術實現(xiàn)。 保留字（關鍵字不能用作標識符）的識別可以借助于保留字i表進行。 1 DO99K=1,10 2 IF(5.EQ.M)I=10 3 DO99K=1.10 4

5、IF(5)=55,標識符的識別,標識符的定義：字母開頭，字母和數(shù)字的組合 標識符后通常有界符,常數(shù)的識別,算術常數(shù)有時需要超前搜索 5.EQ. M 邏輯常數(shù)：.T. , .F., 有界符，容易識別,算符、界符的識別,+，-，*，/，++，-- 所以需要超前搜索,詞法分析器的構造基礎小結,構造預處理器，刪除非執(zhí)行代碼 注釋語句，多余的分隔符，等等 構造掃描器，對預處理結果進行掃描 對常數(shù)、標識符、關鍵字、運算符的識別都要采用超前搜索技術 掃描指針要及時地回退到適當?shù)奈恢?3.2.3 狀態(tài)轉換圖,狀態(tài)轉換圖：有限、有向圖。用來描述單詞規(guī)則的一種工具。,在轉換圖中，結點代表狀態(tài)（單詞識別過程中的狀態(tài)

6、），用園圈表示。 狀態(tài)之間用箭弧連結。箭弧上的標記（字符）代表在射出結點（即箭弧始結點）狀態(tài)下可能出現(xiàn)的輸入字符或字符類。,一張轉換圖只包含有限個狀態(tài)（即有限個結點），其中有一個被認為是初態(tài)（用=表示） ，而且實際上至少要有一個終態(tài)（用雙圈表示）。,圖3.2狀態(tài)轉換圖,=,,,,狀態(tài)圖的作用,一個狀態(tài)轉換圖可用于識別一定的字符串（描述詞法規(guī)則）。 終態(tài)上打個*號，表示多讀進了一個不屬于標識符部分的字符，應把它退還給輸入串，如果在狀態(tài)0時輸入字符不為“字母”，則意味著這個轉換圖不工作。 可以使用狀態(tài)圖進行詞法分析器的開發(fā),=,3.2.4 狀態(tài)轉換圖的實現(xiàn),利用轉換圖容易編寫詞法分析器 讓每個狀態(tài)

7、結點對應一小段程序。 在編制程序的過程中引進一組全局變量和過程。將它們作為實現(xiàn)轉換圖的基本成分。例如： Key:記錄單詞識別過程中已識別到的字符串 掃描指針回退函數(shù) 判斷讀到的符號的類型 等等,對不包含回路的節(jié)點,狀態(tài)i對應的代碼： i() Ch=Getchar() If (isletter(ch)) j Else if (isdigit(ch)) k Else if(ch=“/”) l Else 出錯處理 ,i,j,k,l,,,,字母,數(shù)字,/,對包含回路的節(jié)點,i() ch=getchar(); while (isletter(ch) or isdigit(ch)) getchar();

8、狀態(tài)K所對應的程序段； ,i,k,,,其他,字母或數(shù)字,對終態(tài)節(jié)點,K() Return token; ,i,k,,,其他,字母或數(shù)字,,,,example:file_operation,標識符,無符號整數(shù),單字符分界符,雙字符分界符,,S,,標,,非字母數(shù)字,字母,,字母、數(shù)字,,,數(shù),,非數(shù)字,數(shù)字,,數(shù)字,,單界,,+ ， （ ）,,出口,星號,*,乘冪,,*,,,,其他,,,出錯,,其他,,讀字符,查保留字表,*,3.3 正規(guī)表達式與有限自動機,為了更好地使用狀態(tài)轉換圖構造詞法分析器，為了討論詞法分析器的自動生成，還需要將轉換圖的概念形式化。 為此我們引入：正規(guī)式，正規(guī)集，自動機等概

9、念。,3.3.1 正規(guī)式與正規(guī)集,和都是 上的正規(guī)式，他們所表示的正規(guī)集分別為 和； 任何a , a是上的一個正規(guī)式，它所表示的正規(guī)集為a； 假定U和V都是上的正規(guī)式，他們所表示的正規(guī)集分別記為L(U)和L(V),并且，(U|V), UV和（U)*也都是正規(guī)式，它們所表示的正規(guī)集分別為L(U)L(V), L(U)L(V)(連接積）和（L(U))*（閉包） 僅由有限次使用上述三步驟而得到的表達式才是上的正規(guī)式。僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。,幾個例子,3.1 令=a, b其正規(guī)式和正規(guī)集如下： 正規(guī)式 a|b ba* a(a|b)* (a|b)*(aa|bb)(a|b)*,,正規(guī)

10、集 a,b ban|n=0,1,2,.. 以a開頭的所有字符串 由a、b組成的、包含aa或bb的字符串,,3.2 令=A,B,0,1 ,則： 正規(guī)式 正規(guī)集 (A|B)(A|B|0|1)* 由A、B、0、1組成的以A、B開頭的字符串的全體 （0|1）（0|1）* 由0、1組成的所有符號串,,例 3：令=d,.,e,+,-，則上的無符號數(shù)的正則式,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*,,解：,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)(e(+|-|

11、)dd*|),dd* .dd*,,,,,dd*(.dd*|)e+dd*,dd*(.dd*|)(e(+|-|)dd*|),dd*(.dd*|)e-dd*,dd*(.dd*|)edd*,無符號數(shù)的組成 整數(shù)部分.小數(shù)部分 指數(shù)部分（e+指數(shù)的符號+整數(shù)）,正規(guī)式的等價性,若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者等價。 兩個等價的正規(guī)式U和V記為U=V。 例如：b(ab)*=(ba)*b等,正規(guī)式的運算規(guī)律,U|V=V|U 或的交換律 U|(V|W)=(U|V)|W 或的可結合律 U(VW)=(UV)W 連接的可結合律 (V|W)U=VU|WU 分配律 U=U=U U**=U*,3.3.

12、2 確定有限自動機（DFA),確定有限自動機(DFA)是一個五元式 M= (S, ,,s0, F) 1. S是一個有限集，它的每個元素稱為一個狀態(tài)。 2. 是一個有窮字母集，它的每個元素稱為一個輸入字符。,3.3.2 確定有限自動機（DFA),確定有限自動機(DFA)是一個五元式 M= (S, ,,s0, F) 是一個從S x 至S的單值部分映射。 (s,a）=S。意味著：當現(xiàn)行狀態(tài)為s、輸入字符為a時，將轉換到下一個狀態(tài)S。我們稱S為s的后繼狀態(tài)。 S0S，是唯一的初態(tài)。 FS，是一個終態(tài)集（可空）,DFA實例,M=(0,1,2,3,a,b,,0,3) 其中： （0

13、,a)=1; （0,b)=2 （1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3; （3,b)=3,DFA的矩陣表示,該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元表示(s,a）的值，該矩陣稱為狀態(tài)轉換矩陣。,DFA的（確定的）狀態(tài)轉換圖表示,假定DFA M 含有m個狀態(tài)n個輸入字符， 那么，這張圖含有m個狀態(tài)結點， 每個結點頂多有n條箭弧射出和別的結點相連接， 每條箭弧用上的一個不同字符作標記， 整張圖含有唯一的初態(tài)和若干個（可以是0個）終態(tài)結點。,DFA對應的狀態(tài)轉換圖,M=(0,1,2,3,a,b,,0,3) 其中： （0,a)=1; （0,b)=2 （

14、1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3; （3,b)=3,=,DFA 所識別（讀出或接受）的字符串,對于*中的任何一個字符串，若存在一條從初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有箭弧的標記符連接成的字等于，則稱為DFA M所識別（讀出或接受）。 若M的初態(tài)結點同時又是終態(tài)結點，則為空字可以為M所識別。DFA M所能識別的字的全體記為L(M).,DFA及其所識別的語言描述,M=(0,1,2,3,a,b,,0,3) 其中： （0,a)=1; （0,b)=2 （1,a)=3; （1,b)=2 （2,a)=1; （2,b)=3 （3,a)=3;

15、 （3,b)=3 問：L(M)=?,L(M)為在上所有含相繼兩個a或相繼兩個b的字,=,3.3.3 非確定有限自動機(NFA),一個非確定有限自動機（NFA)是一個五元式 M= (S, ,,S0, F) (1) S 同DFA （2） 同DFA （3） 是一個從S x *到S的子集的映照，即 ：S x *2s (4) S0S,是一個非空的初態(tài)集； （5）F S，是一個終態(tài)集（可空）,NFA實例,M=(0,1,2,3,4,a,b,,0,2,4) 其中： （0,a)=0,3; （0,b)=0,1 （1,b)=2; （2,a)=2 （2,b)=2; （3,a)=4 （4,a)=4;

16、（4,b)=4,NFA的表示,矩陣表示：,NFA的表示,狀態(tài)轉換圖表示： 假定NFA 含有m個狀態(tài)n個輸入字符， 那么，這張圖含有m個狀態(tài)結點， 每個結點可以射出若干條箭弧和別的結點相連接，每條箭弧用*上的一個字（不一定要不同的字而且可以是空字）作標記（稱為輸入字）， 整張圖至少含有一個的初態(tài)和若干個（可以是0個）終態(tài)結點。 某結點既可以是初態(tài)也可以是終態(tài)結點。,NFA的狀態(tài)轉換圖,=,NFA所識別或接受的字,對于*中的任何一個字（字符串），若存在一條從初態(tài)結點到某一終態(tài)結點的通路，且這條通路上所有箭弧的標記符連接成的字（忽略那些標記為的?。┑扔冢瑒t稱為NFA M所識別（讀出或接受）。 若

17、M的初態(tài)結點同時又是終態(tài)結點，或者存在一條某初態(tài)結點到某個終態(tài)結點的通路，則為空字可以為M所識別。,=,NFA所識別的語言描述,該NFA識別的語言有什么特點？,L(M)為在上所有含相繼兩個a或相繼兩個b的字,=,NFA到DFA的區(qū)別：,DFA與NFA的等價性,DFA是NFA的特例。 對于每個NFA M存在一個DFA M，使L(M)=L(M)。 第一步，引入新的初態(tài)X和終態(tài)Y(保證初態(tài)的唯一性)，并依照下面的函數(shù)引入新的?。?（X,)=S （F,)=Y 第二步：按照如下替換規(guī)則對NFA進行處理,AB,i,j,,,A,B,i,j,k,,,A|B,i,j,,A*,i,j,,A,B,i,j,,,,,i

18、,j,k,,,A,替換規(guī)則,NFA允許邊出現(xiàn),子集法,第三步，利用子集法將NFA轉化成DFA 狀態(tài)集I的Ia集合： Ia= _CLOSURE(J) J=move(I,a)：所有可以從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體 狀態(tài)集I的_CLOSURE(I)閉包：狀態(tài)集I中的任何狀態(tài)經(jīng)任意條弧而能到達的狀態(tài)的集合,=,子集法的實現(xiàn),構造矩陣（包含K+1列,K為字母集的大?。仃嚨牧袠藶镮a1,Ia2；矩陣的首行首列為_CLOSURE(X) 如果某行第一列的元素已知，記為I, 該行其余各列定義為：Iai(i=1..k) 在構造過程中，如果產(chǎn)生新的狀態(tài)集，則將其寫在下面新行的行首 重復上述過程

19、，直到?jīng)]有新的狀態(tài)集產(chǎn)生 將新構造的矩陣視為狀態(tài)轉換表，構造DFA 表中的第一行為DFA的初態(tài)，含有原終態(tài)的子集為新的終態(tài)。,,例：有NFA M，求DFA M。,a,1,,2,3,,4,start,a,b,a,c,c,,,,,I Ia Ib Ic,1,4,X,Y 2,3 ,2,3 2 4,Y 3,4,Y,2 2 4,Y ,4,Y ,3,4,Y 3,4,Y,,,X,,,,,Y,,,,,,,,,,,,,,,,,,,,,,start,,,I Ia Ib Ic,1,4,X,Y 2,3 ,2,3 2 4,Y 3,4,Y,2

20、 2 4,Y ,4,Y ,3,4,Y 3,4,Y,,,,,,符號,狀態(tài),a,b,c,0,2,3,4,1,2,2,1,_,_,_,_,_,_,_,_,3,3,4,4,,,DFA M狀態(tài)轉換矩陣,將求得的狀態(tài)轉換矩陣重新編號,,0,1,,4,2,,3,,1,4,X,Y,2,3,4,Y,2,a,c,a,b,b,c,3,4,Y,,,,確定有窮自動機的化簡,說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個最小的與之等價的有窮自動機。,DFA的最小化就是尋求最小狀態(tài)DFA,最小狀態(tài)D

21、FA的含義: 1.沒有多余狀態(tài)(死狀態(tài)) 2.沒有兩個狀態(tài)是互相等價（不可區(qū)別）,所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。 兩個狀態(tài)s和t等價：滿足 一致性條件(兼容性)同是終態(tài)或同是非終態(tài) 蔓延性條件（傳播性）從s出發(fā)讀入某個aa和從t出發(fā)讀入某個a到達的狀態(tài)等價。,確定有限自動機的化簡,確定有限狀態(tài)化簡：尋找一個狀態(tài)數(shù)比M少的DFA M，使得L(M)=L(M) 兩個概念： 狀態(tài)s和t等價。 狀態(tài)s和t可區(qū)別。 一般的，終態(tài)和非終態(tài)是可區(qū)別的。 化簡過程：對M的狀態(tài)集進行分割，分割成不相交的子集，使得不

22、同的兩個子集中的狀態(tài)是可區(qū)別的，而同一子集中的狀態(tài)是等價的,狀態(tài)集劃分步驟,第一步，將終態(tài)和非終態(tài)分開，從而將狀態(tài)集分成兩個子集； 假定到某個時候已經(jīng)將集合劃分成m個子集，并且屬于不同子集中的狀態(tài)是可區(qū)分的 檢查每一個子集中的狀態(tài)是否可以在劃分：對于某一個集合I=q1,q2qk,構造該集合的I(a)，如果 I(a)不包含在現(xiàn)行劃分中的某一個子集中，則將I一分為二,集合劃分方法,如果s1和s2經(jīng)a弧到達t1和t2，而t1和t2分屬于兩個子集，則將I分成兩部分，其中 I(1)=s|s經(jīng)a弧到達t1所在的子集中的某狀態(tài) I(2)=I- I(1) 重復上述過程，直到?jīng)]有新的狀態(tài)子集生成 最后，對劃分中

23、的每一個子集，選取子集中的一個狀態(tài)代表其他的狀態(tài)，并進行相關的處理,例1:最小化,狀態(tài)集的劃分 將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個子集G1,G2; 分別從兩個子集G1,G2中尋找等價狀態(tài)進行化簡。,,解:,(一)區(qū)分終態(tài)與非終態(tài),,1,2,3,4,5,6,6,3,7,3,1,5,4,6,7,3,7,4,1,4,2,,a,b,,,a,b,,,,,,,,,,,,,,,,例：試求與下圖所示NFA等價的化簡了的DFA。,化簡后的DFA:,,,有限自動機化簡實例,有限自動機化簡實例,首先把M的狀態(tài)分為兩組：終態(tài)組3，4，5，6，和非終態(tài)組0，1，2 其次考察終態(tài)組，由于 3，4，5，6a3

24、,4,5,6和 3，4，5，6b3,4,5,6所以不能再劃分,,再考察0，1，2 由于 0，1，2a1，3，它既不屬于0，1，2也不屬于3，4，5，6，因此應將其一分為二，由于1態(tài)經(jīng)a弧到達3態(tài)，而且狀態(tài)0，2經(jīng)a弧到達1態(tài)故應把1態(tài)分出形成1， 0，2。 現(xiàn)在劃分已經(jīng)有3個組：3，4，5，6，1，0，2。 由于0，2b=2,5未包括在上述分組中，故0，2應一分為二0，2。 到此四個分組3，4，5，6，0，1，2。每個組都不可再分。 最后，令狀態(tài)3代表3，4，5，6。把原來到達4，5，6的弧都導入3，并刪除4，5，6狀態(tài)。得到化簡的DFA.,正規(guī)式與有限自動機的等價性,結論： 對于

25、任何FA，都存在一個正規(guī)式r，使得L(r)=l(M) 對于任何正規(guī)式r ，都存在一個FA ，使得l(M) =L(r),由FA 構造正規(guī)式的過程,第一步，引入新的初態(tài)X和終態(tài)Y，并用標記為的有向弧，將X、Y與原來的初態(tài)和終態(tài)連接；,,,,,由FA 構造正規(guī)式的過程,第二步，按照規(guī)則消除M上的弧 重復第二步，直到狀態(tài)圖中只有XY狀態(tài) 此時，X、Y之間的標注即為正規(guī)式,()消除M中的所有結點,a|b,,x,0,,2,4,,y,,,,,,,,,aa,bb,a|b,a|b,,由正規(guī)式構造FA,采用關于正規(guī)式中運算符數(shù)目的歸納方法進行證明。 若r 中具有0個運算符，則r=,r=a或r=,由正規(guī)式構造FA

26、,2. 假設r中有少于k個運算符時時，上述結論成立 3. 則當r中有k個運算符時：,r的三種情形 r=r1|r2, r=r1.r2 r=r1*,(a)對于正則式R=s|t, NFA(R),(b)對正則式R=st,NFA(R),N(s),,,,(c)對于正則式R=s*, NFA(R),,,,,,,例:為R=(a|b)*abb構造NFA,使得L(N)=L(R),R=(a|b)*abb,例3：試構造與正則式R=(a*|b*)b(ba)*等價的狀態(tài)最少的DFA。,NFA確定為DFA:,注：狀態(tài)從18標注,,最小化的DFA:,,1,,2,,,,例：設計一個最小化的DFA，其輸入字母表是0,1，它能接受以

27、0開始，以1結尾的所有序列。,解：根據(jù)題意，得出相應的正則式：0(0|1)*1 得狀態(tài)轉換圖(NFA)如下：,NFA確定為DFA過程：,,,,,得狀態(tài)轉換圖(DFA)如下：,在DFA中，所有含有NFA的終態(tài)的狀態(tài)作為DFA的終態(tài),DFA M=( S,A,B,C , 0,1 , , S , C ) 其中如上（不可省略）,,,正規(guī)文法與有限自動機的等價性,定義：對于正規(guī)文法G和有限自動機M,如果L(G)=L(M),則稱二者等價 結論： 對每一個右（左）線性正規(guī)文法G，都有一個有限自動機M，使得L(G)=L(M) 對每一個有限自動機M，都有一個右（左）線性正規(guī)文法G ，使得L(G)=L(M),由正

28、規(guī)文法構造有限自動機,M中狀態(tài)轉換函數(shù)的構造： A-a,a Vt,則（A,a）=f A-aA1| aA2 aAk,a Vt,則 （A,a）=A1| A2 Ak,例:求與文法GS等價的NFA GS: SaA|bB| AaB|bA BaS|bA|,G=（A，B，C，D，a，b，P，A）,其中P: A aB A bD|b B bC|b C aA C bD|b D aB D bD|b,,,,,,,,,二者的等價性證明,對于右線性文法G,在S推導出句子w的過程中，利用A-aB相當于： 利用A-a相當于： 也就是說：任給w L(G)，都有w L(M

29、) 即：L(G)是L(M)的子集； 同樣，任給w L(M)，都有w L(G) 即：L(M)是L(G)的子集； 結論： L(M)=L(G)，即M跟G等價,由正規(guī)文法構造有限自動機,M中狀態(tài)轉換函數(shù)的構造： A-a,a Vt,則（q,a）=A A1-Aa, A2-Aa , Ak-Aa a Vt,則 （A,a）=A1, A2 Ak,例:求與文法GS等價的NFA GS: SAa|Bb| ABa|Ab BSa|Ab|,q,B,,,,,S,A,,b,a,,,a,,a,,b,,b,由DFA構造正規(guī)文法（右線性）,關于文法產(chǎn)生式的定義： 對于 （A,a）=B的狀態(tài)轉換函數(shù)， 如果B不屬于F，可以

30、定義A-aB形式的產(chǎn)生式； 如果B屬于F，可以定義A-a|aB形式的產(chǎn)生式;,例:給出如圖DFA等價的正則文法G,G=（A，B，C，D，a，b，P，A）,其中P: A aB A bD|b B bC|b C aA C bD|b D aB D bD|b,,,,,,,,,1.對轉換函數(shù)(A,t)=B， 可寫成一個產(chǎn)生式:AtB,,3.有限自動機的初態(tài)對應于文法的開始符號, 有限自動機的字母表為文法的終結符號集。,由DFA構造正規(guī)文法（左線性）,關于文法產(chǎn)生式的定義： 對每一個S屬于F,定義Q-S 對于 （A,a）=B的狀態(tài)轉換函數(shù)，定義B-Aa形式的產(chǎn)生式

31、；如果A為起始符，可以定義B-a,或者定義B-Aa 和A- ; 如果S0屬于F, Q- ,已知NFA，構造等價的右線性文法,A-0B|1D|0 B-1C|0D C-0B|1D|0 D-0D|1D,,,0,1,有下面的右線性文法，構造NFA A-0B|1D|0 B-1C|0D C-0B|1D|0 D-0D|1D,A,1,,0,1,0,有下面的NFA，構造左線性文法 Q-F F-C0|0 B-C0|0 C-B1 D-D0|D1|B0|A1|C1,A,1,,0,1,0,3.4詞法分析器的自動產(chǎn)生,我們用正規(guī)式描述單詞符號，并研究如何從正規(guī)式產(chǎn)生識別這些單詞符號的詞法分析程序。 首先介紹一個描述詞法

32、分析器的語言LEX，討論LEX的實現(xiàn)，從而，用它來描述和自動產(chǎn)生所需的各種詞法分析器。,Lex編譯器,C語言編譯器,,,,Lex文件(文本文件),Lex.yy.c,,可執(zhí)行的詞法分析工具,輸入文件,單詞符號,,,3.4詞法分析器的自動產(chǎn)生,定義部分 規(guī)則部分 用戶子程序部分,3.4.1 LEX的程序結構,定義部分,定義部分 % . %,內(nèi)容 Include、聲明語句等C語句及正則表達式 % #include “ stdio.h” #include”y.tab.h” int lineno % delim tn letter A-Za_z digit 0-9 id letter(letter|

33、digt)*,Lex中的正則表達式規(guī)則,轉義字符： :表示一個集合，可以結合-表示一個范圍，如abc，a-zA-Z ? * + :0或1次，任意次，至少一次 . :任意一個符號 |：二選一 （）:分組，括號內(nèi)的內(nèi)容被看作一個原子，如（ab）,:標記限定符。例如O2(匹配兩個O)， O2， (匹配至少兩個O)， O2，5(匹配兩個O，至多5個) / 向前匹配（超前搜索）。如果在匹配的模版中的“/”后跟有后續(xù)表達式，只匹配模版中“/”前面的部分。如：如果輸入 A01，那么在模版 A0/1 中的 A0 是匹配的。,規(guī)則部分,規(guī)則部分起始于%%，終止于%%，其間是詞法規(guī)則（正則表達式）和相應的動作組成

34、 格式 P1 A1 P2 A2 P3 A3 其中，Pi是一個正規(guī)式（第一部分定義的正規(guī)式的名字） Ai是一個程序段C語句,識別規(guī)則,%% n ++num_line; A-Za-z* ++num_words . ++num_chars %% 注意： 在識別規(guī)則中引用正規(guī)式的名字時，要用分隔。例如：letter(digit|letter)* 超前搜索符號（/）只能在規(guī)則段中使用,用戶子程序部分,包含用c語言編寫的子程序，這些子程序可以用在前面的動作中，這樣可以達到簡化編程的目的。 Lex 編程的第三段，也就是最后一段覆蓋了 C 的函數(shù)聲明（有時是主函數(shù)）。注意這一段必須包括 yywrap() 函數(shù)

35、的定義。,用戶子程序的相關問題,Main(int argc, char * argv) --argc; ++argv /*跳過對第一個文件，即main 函數(shù)多對應的.exe文件*/ if (argc0) yyin= fopen(argv0,r); else yyin=stdin yylex(); yywrap(); /*返回值為零，可對多個文件進行解析*/ ,一個完整的lex程序,% intwordCount=0; % chars A-za-z.“ numbers(0-9)+ delimnt whitespace delim+ wordschars+ %%,words wordCount

36、++; whitespace numbers numcount++ %%,voidmain() yylex();/*starttheanalysis*/ printf(Noofwords:%dn,wordCount); intyywrap() return1; ,3.4.3 LEX的實現(xiàn),Lex編譯過程： 對每條規(guī)則構建一個NFA 引入新的初態(tài)，將這些NFA合并成一個NFA 利用子集法將NFA轉化為大DFA 必要時對DFA進行狀態(tài)的化簡,例題與習題解答,例3.1寫能被5整除的十進制整數(shù)的文法及正則表達式。 解：能被5整除的文法： GZ: ZSAB S +|- B 0|5 ANA|

37、 N 0|1|2|3|4|5|6|7|8|9| 正則表達式：GZ: Z= (+| - )A*(0|5) A=0|1|2|3|4|5|6|7|8|9,例3.2寫一個正規(guī)式，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。 解：r1=1|3|5|7|9 r2=2|4|6|8 r3=r1|r2 r4=(0|r3)* R=r1|r3r4r1,,例3.3寫出能被3整除十進制整數(shù)的文法和正則表達式： 解： 能被3整除的文法： G=( 0,1,2,3,4,5,6,7,8,9,S, A, B, S, P,) 其中P為： S - (0|3|6|9)S| S - (1|4|7)A|(2|5|8)B A

38、- (0|3|6|9)A|(1|4|7)B|(2|5|8)S B - (0|3|6|9)B|(2|5|8)A|(1|4|7)S,,,例3.4：已知有限自動機如圖,(1)以上狀態(tài)轉換圖表示的語言有什么特征？ (2)寫出其正規(guī)式與正規(guī)文法. (3)構造識別該語言的有限自動機DFA.,,解： （1） L=W |W 0,1,并且W至少有兩個連續(xù)的1 （2） 正則式為（0|1)*11(0|1)* 正則文法G(Z)為： A0A|1A|1B B 1C|1 C 0C|1C|0|1 （3）將圖中有限自動機確定化： 首先從初態(tài)A出發(fā)：,,I I0 I1 (1)A

39、(1)A (2) A,B (2)A,B (1)A (3)A,B,C (3)A,B,C (4)A,C (3)A,B,C (4)A,C (4)A,C (3)A,B,C 其相應的DFA如下圖：,,將這個DFA最小化： 首先分終態(tài)和非終態(tài)兩個集 K1=1,2 和 K2=3,4 由于狀態(tài)1輸入1到達狀態(tài)K1集，而狀態(tài)2輸入1到達K2集故將k1分為 K11=1, K12=2 由于狀態(tài)3，和 4 輸入1，或0 都到達k2集所以狀態(tài)3，4等價。 則可以分割成三個子集： 1，2，3，4,,所以將DFA最小化的狀態(tài)圖如下：,,例3.5請構造與正則式R=(a*b)*ba(a|b)*

40、 等價的狀態(tài)最少的DFA（確定有限自動機） 解： （1）首先構造轉換系統(tǒng)圖： （2）由系統(tǒng)轉換圖構造DFA（NFA確定化） 設初態(tài)為S, A, B, G,F,,NFA確定化為DFA的過程： I Ia Ib (1)S,A,B,G,F (2)G,F (3)A,B,C,G,F (2)G,F (2)G,F (4)A,B,G,F (3) A,B,C,G,F (5)D,F,G,E,Z (3)A,B,C,G,F (4)A,B,G,F (2)G,F (3)A,B,C,G,F (

41、5)D,F,G,E,Z (6)G,F,E,Z (7)A,B,E,Z,G,F (6)G,F,E,Z (6)G,F,E,Z (7)A,B,E,Z,G,F (7)A,B,E,Z,G,F (6)G,F,E,Z (8)A,B,C,E,Z,G,F (8)A,B,C,E,Z,G,F (5)D,F,G,E,Z (8)A,B,C,E,Z,G,F DFA 這狀態(tài)圖如下：,,確定有限自動機圖如下：,,（3）將DFA最小化：先將終態(tài)和非終態(tài)分成兩個集: K1=1,2,3,4 , K2=5,6,7,8 對于K1中的3態(tài)輸入a則進入K2集，而1，2，4態(tài)輸入a仍然在K1中，故K1可一分為二K11=1,2,4和K12=3; 考察K11對于1，4態(tài)輸入b到達3態(tài)而2態(tài)輸入b到達4態(tài)。故K11可一分為二K111=1,4; K112=2最后考察K2輸入a或b都到達K2集。則DFA化簡為1，4，2，3，5，6，7，8四個子集。其狀態(tài)圖如下：,第四章 語法分析自上而下分析（1）,4.1 語法分析器功能 下圖表明了語法分析器在編譯程序中的地位。,詞法分析器,語法分析器,,,單詞符號,取下一個單詞符號,編譯后續(xù),,語法分析樹,符號表,,,,,,,,