東北大學秦皇島分校編譯原理課件 第四章.ppt

1、本章將討論詞法分析程序的設計原則，單詞的描述技術(shù)，識別機制及詞法分析程序的自動構(gòu)造原理。 4.1 詞法分析程序 4.2 正規(guī)表達式與正規(guī)集（正規(guī)語言） 4.3 有窮自動機 4.4 詞法分析程序的自動構(gòu)造,第四章 詞法分析,本章重點,單詞的描述工具 單詞的識別系統(tǒng) 設計和實現(xiàn)詞法分析程序 首先需要描述和刻畫程序設計語言中的原子單位單詞，其次需要識別單詞和執(zhí)行某些相關(guān)的動作。 描述程序設計語言的詞法的機制是正則表達式，識別機制是有窮狀態(tài)自動機。,回顧 什麼是詞法分析程序,實現(xiàn)詞法分析（lexical analysis）的程序 逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。 單詞是語言中具有獨立

2、意義的最小單位，包括保留字、標識符、運算符、標點符號和常量等。 詞法分析是編譯過程中的一個階段，在語法分析前進行 。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當前單詞供語法分析使用。,詞法分析程序的任務,詞法分析是編譯的第一個階段。 詞法分析所做的工作也叫“掃描處理”，因此，詞法分析程序也常被叫做“掃描器”。 詞法分析的任務是識別單詞，為語法分析提供語法單位序列。 單詞的形式一般為： 詞法分析程序的輸入是源程序，輸出是一定形式的單詞序列。,詞法分析程序和語法分析程序的關(guān)系,源程序,詞法分析程序,語法分析程序,Token,get token,.,詞法分析程序的主要任

3、務： 讀源程序，產(chǎn)生單詞符號 詞法分析程序的其他任務： 濾掉空格，跳過注釋、換行符 追蹤換行標志，復制出錯源程序， 宏展開，,詞法分析程序的要求,詞法分析程序必須按照一定的分類標準將源程序中的單詞進行識別并進行預加工處理。 常見的單詞分類形式有兩種： 1、一字一類型 2、按下列方式將單詞分為5種類型 關(guān)鍵字：也叫保留字、基本字，是由程序語言定義的具有固定意義的標識符。 標識符：開發(fā)人員自己定義的用來表示變量、數(shù)組等名稱的。 常數(shù)：包括整型、實型、布爾型、字符及字符串型等。 運算符：包括+、*、/、 以及布爾運算等。 界符：逗號、分號、括號、回車、換行等將語法單位分隔開的符號。,詞法分析程序的工

4、作階段,詞法分析工作可以分成兩個工作階段： 1、輸入、預處理階段：預處理子程序。 2、識別單詞符號：超前搜索法。所謂超前搜索法，是指想要識別出某個字符串是否是一個單詞，必須超前掃描一個或多個字符，直到能夠肯定某個字符序列是一個單詞為止。,編譯程序的“遍數(shù)”影響詞法分析的設計。 詞法分析工作從語法分析工作獨立出來的原因： 簡化設計 改進編譯效率 增加編譯系統(tǒng)的可移植性,正規(guī)文法和正規(guī)式,多數(shù)程序設計語言的單詞的詞法規(guī)則都能用正規(guī)文法來描述。 正規(guī)文法所描述的式文法的字符表Vt*上的正規(guī)集。 正規(guī)式也稱正則表達式，也是表示正規(guī)集的工具 正規(guī)式服從的代數(shù)規(guī)律： r|s=s|r r|(s|t)=(r|

5、s)|t (rs)t=r(st) r(s|t)=rs|rt (s|t)r=sr|tr r=r r=r,正規(guī)式,正規(guī)式也稱正則表達式,正規(guī)表達式（regular expression）是說明單詞的模式(pattern)的一種重要的表示法（記號），是定義正規(guī)集的數(shù)學工具。我們用以描述單詞符號。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。,定義（正規(guī)式和它所表示的正規(guī)集）： 設字母表為，輔助字母表=，。 1。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ；,2。任何a ，a是上的一個正規(guī)式，它所表示的正規(guī)集為a； 3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么

6、，(e1), e1 e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。 4。僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。,正規(guī)式中的符號,其中的“”讀為“或”（也有使用“+”代替 “” 的）；“ ”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“”、“ ”、“” 。連接符“ ”一般可省略不寫?！啊?、“ ”和“” 都是左結(jié)合的。,例子,令=a，b， 上的正規(guī)式和相應的正規(guī)集的例子有： 正規(guī)式 正規(guī)

7、集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,a, 任意個a的 串,正規(guī)式 正規(guī)集 (ab) ,a,b,aa,ab 所有由a 和b組成的串 (ab)(aabb)(ab) 上所有含有兩個相繼 的a或兩個相繼的b組成 的串,討論下面兩個例子 例 令=l，d，則上的正規(guī)式 r=l(l d) 定義的正規(guī)集為: l,ll,ld,ldd,其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式 即是 字母(字母|數(shù)字) ,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和 多數(shù)程序設計語言允許的的標識符的詞法規(guī)則. 例 =d，e，+，-, 則上的正規(guī)式 d

8、(dd )(e(+- )dd )表示的是無符號數(shù)的集合。其中d為09的數(shù)字。 程序設計語言的單詞都能用正規(guī)式 來定義.,若兩個正規(guī)式e1和e2所表示的正規(guī)集相同,則說e1和e2等價,寫作e1=e2。 例如： e1= (ab)， e2 = ba 又如： e1= b(ab) , e2 =(ba)b e1= (ab) , e2 =(ab),設r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有： 1。rs=sr “或”服從交換律 2。r(st)=(rs)t “或”的可結(jié)合律 3。(rs)t=r(st) “連接”的可結(jié)合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r 是“連接

9、”的恒等元素零一律 6。 rr=r r=rrr “或”的抽取律,正規(guī)文法和正規(guī)式 對上的正規(guī)式r ,存在一個G=(VN,VT,P,S)：L(G)=L(r),初始， VT= ,S VN ，生成正規(guī)產(chǎn)生式 Sr (R1) 對形如 Ar1r2的正規(guī)產(chǎn)生式： Ar1B Br2 BVN (R2)對形如Arr1的正規(guī)產(chǎn)生式： ArB Ar1 BrB Br1 BVN (R3)對形如Ar1r2的正規(guī)產(chǎn)生式:Ar1 A r2 不斷應用R做變換，直到每個產(chǎn)生式右端至多有一個VN,例 r=a(ad),Sa(ad) SaA A(ad) A(ad)B A B(ad)B B Gs: SaA A VT=a,d AaBVN=

10、S,A,B AdB BaB BdB B,正規(guī)文法和正規(guī)式 對G=(VN,VT,P,S),存在一個 =VT上的正規(guī)式r : L(r)=L(G),AxB, By A=xy AxAy A=xy Axy A=xy,正規(guī)文法和正規(guī)式,Gs:SaA|a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a=a(ad)(ad)=a(ad) R=a(ad),正規(guī)表達式與正規(guī)集（正規(guī)語言）,程序設計語言中的單詞是基本語法成分.單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，實現(xiàn)詞法分析程序的自動構(gòu)造.,3型文法產(chǎn)生的語言是有窮自動機（FA）所接受的集合。,定理 設G=

11、（VN，VT，P，S）是3型文法，則存在一個有窮自動機 M=(K, , f, A, Z)，使得L(M)=L(G) 有窮自動機NFA M 這樣構(gòu)造： = VT K= VN N, N為一個新狀態(tài),它不在VN中 A=S Z=N 對G中的形如 DtB的產(chǎn)生式,t為終結(jié)符或,有f(D,t)=B； 對G中形如Dt的產(chǎn)生式， t為終結(jié)符或,有f(D,t)=N; 對VT中的每一個a ,有f(N,a)=,狀態(tài)轉(zhuǎn)換圖（狀態(tài)圖）,狀態(tài)轉(zhuǎn)換圖是為了識別正規(guī)文法而專門設計的有向圖。一個DFA可以表示成一個狀態(tài)圖。 狀態(tài)轉(zhuǎn)換圖包含有窮個狀態(tài)，除開始狀態(tài)不代表任何非終結(jié)符號外，每個狀態(tài)結(jié)點都代表文法的非終結(jié)符號；狀態(tài)圖的轉(zhuǎn)

12、換弧上所標記的符號是文法的終結(jié)符號。 如規(guī)則：U:=Va的狀態(tài)圖為：,V,U,a,正規(guī)文法與狀態(tài)轉(zhuǎn)換圖,左線性文法：其規(guī)則形如： U:=a U:=Wa 右線性文法：其規(guī)則形如： U:=a U:=aW 右線性文法利用狀態(tài)轉(zhuǎn)換圖的識別過程實際上是一種自上而下的推導過程。 左線性文法利用狀態(tài)轉(zhuǎn)換圖的識別過程實際上是一種自下而上的規(guī)約過程。,狀態(tài)轉(zhuǎn)換圖的構(gòu)造法,左線性正規(guī)文法的狀態(tài)轉(zhuǎn)換圖的構(gòu)造步驟： 1、增加結(jié)點S為開始狀態(tài)（假定文法的符號中不存在符號S） 2、以每一個非終結(jié)符號為狀態(tài)結(jié)點 3、對于形如U:=a的每條規(guī)則，引一條從開始狀態(tài)S到狀態(tài)U的弧，弧的標記為a；而對形如U:=Va的規(guī)則，引一條從

13、狀態(tài)V到U的弧，其標記為a。 4、將識別符號作為終止狀態(tài)。 右線性正規(guī)文法的狀態(tài)轉(zhuǎn)換圖的構(gòu)造步驟： 1、增加結(jié)點Z為終止狀態(tài)（假定文法的符號中不存在符號Z） 2、以每一個非終結(jié)符號為狀態(tài)結(jié)點 3、對于形如U:=a的每條規(guī)則，引一條從狀態(tài)U到終止狀態(tài)Z的弧，弧的標記為a；而對形如U:=aV的規(guī)則，引一條從狀態(tài)U 到V的弧，其標記為a。 4、將識別符號作為開始狀態(tài)。,G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,B,A,S,a,a,a,b,b,b,a,b,D,a,b,a,b,定理 已知一有窮自動機M= (K, , f, A, Z),存在有一個3型文法G = （VN，

14、VT，P，S）,使得L(G)=L(M) G 的定義： VT = VN= K S = A 若 f(D,t)=B ，則DtB在P中 若 f(D,t)=B ，且B在Z中，則Dt在P中。,G： SaA|bB AbB|aD|a BaA|bD|b DaD|bD|a|b,B,A,S,a,a,a,b,b,a,b,b,有窮自動機,有窮自動機也稱有限自動機，是一種能準確識別正規(guī)集的識別裝置。 有窮自動機分為確定的有窮自動機（DFA）和非確定的有窮自動機（NFA）兩類。 一個DFA可以表示成一個狀態(tài)圖。 對于任意一個給定的NFA，都存在一個與之等價的DFA。 我們可以用“子集法”將NFA轉(zhuǎn)換成DFA。 不存在兩個或

15、兩個以上的狀態(tài)互相等價的DFA稱為化簡了的DFA。,關(guān)于有窮自動機我們將討論如下題目,確定的有窮自動機DFA 不確定的有窮自動機NFA NFA的確定化 DFA的最小化,確定的有窮自動機DFA,DFA定義： 一個確定的有窮自動機（DFA）M是一個五元組：M=（K，f，S，Z）其中 1.K是一個有窮集，它的每個元素稱為一個狀態(tài)； 2.是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；,DFA定義,3.f是轉(zhuǎn)換函數(shù)，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；

16、4.SK是唯一的一個初態(tài)； 5.Z K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。,一個DFA 的例子：,DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定義為： f（S，a）=U f（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（Q，a）=Q f（U，b）=Vf（Q，b）=Q,一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFA M含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)圖含有m個結(jié)點，每個結(jié)點最多有n個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=”或標以“-”，終態(tài)結(jié)點用雙圈表示或標以“+”，若 f(ki,a)=kj，則從

17、狀態(tài)結(jié)點ki到狀態(tài)結(jié)點kj畫標記為a的?。?DFA 的狀態(tài)圖表示,b,一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=”標明初態(tài)；否則第一行即是初態(tài)，相應終態(tài)行在表的右端標以1，非終態(tài)標以0。,DFA 的矩陣表示,0 0 0 1,為了說明DFA如何作為一種識別機制,我們還要理解下面的定義,*上的符號串t在DFA M上運行 一個輸入符號串t，（將它表示成Tt1的形式，其中T，t1 *）在DFA M=（K，f，S，Z）上運行的定義為： f（Q， Tt1）=f（f（Q，T），t1） 其中QK

18、擴充轉(zhuǎn)換函數(shù)f為 K*K上的映射，且： f（ki，）= ki,*上的符號串t被DFA M接受 M=（K，f，S，Z） 若t *，f(S，t)=P，其中S為 M的開始狀態(tài)，P Z，Z為終態(tài)集。 則稱t為DFA M所接受（識別）.,例：證明t=baab被下圖的DFA所接受。 f（S，baab）=f（f（S，b），aab） = f（V，aab）= f（f（V，a），ab） =f（U，ab）=f（f（U，a），b） =f（Q，b）=Q Q屬于終態(tài)。 得證。,DFA M所能接受的符號串的全體記為L(M). 對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M與M是等價的. 結(jié)論： 上一個符號串集

19、V是正規(guī)的，當且僅當存在一個上的確定有窮自動機M，使得 V=L(M)。,DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:KK是一個單值函數(shù)，也就是說，對任何狀態(tài)kK，和輸入符號a，f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉(zhuǎn)換圖來看，若字母表含有n個輸入字符，那末任何一個狀態(tài)結(jié)點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。,不確定的有窮自動機NFA,定義 NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種映射，SK是初始狀態(tài)集，Z K為終止狀態(tài)集.,例子 NFA M=（S，P，Z，0，1，f，S，P，Z） 其中 f（S，0）=P f（Z，

20、0）=P f（P，1）=Z f（Z，1）=P f（S，1）=S，Z,狀態(tài)圖表示,矩陣表示,矩陣表示,類似DFA, 對NFA M=K，f，S，Z也有如下定義,*上的符號串t在NFA M上運行. 一個輸入符號串t，（我們將它表示成Tt1的形式，其中T，t1 *）在NFA M上運行的定義為： f（Q， Tt1）=f（f（Q，T），t1） 其中QK. *上的符號串t被NFA M接受 若t *，f(S0，t)=P，其中S0 S，P Z， 則稱t為NFA M所接受（識別）,*上的符號串t被NFA M接受也可以這樣理解,對于中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標記

21、字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的道路,其上所有弧的標記均為，那么空字可為M所接受。,NFA M所能接受的符號串的全體記為 L(M) 結(jié)論： 上一個符號串集V是正規(guī)的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。,(0|1)*(000|111)(0|1),DFA是NFA的特例。對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。對每個NFA N存在著與之等價的DFA M。 有一種算法，將NFA轉(zhuǎn)換成接受同樣語言的DFA.這種算法稱為子集法.

22、 與某一NFA等價的DFA不唯一.,從NFA的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在DFA的矩陣表示中，表項是一個狀態(tài)，NFA到相應的DFA的構(gòu)造的基本思路是： DFA的每一個狀態(tài)對應NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能達到的所有狀態(tài)。,NFA確定化算法：,假設NFA N=(K, ,f,K0,Kt)按如下辦法構(gòu)造一個DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1. M的狀態(tài)集S由K的一些子集組成。用S1 S2. Sj表示S的元素，其中S1, S2,. Sj是K的狀態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則排列的，即

23、對于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；,2 M和N的輸入字母表是相同的，即是； 3 轉(zhuǎn)換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -closure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)； 5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt,定義對狀態(tài)集合I的幾個有關(guān)運算：,1. 狀態(tài)集合I的-閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達的狀態(tài)的集合。 狀態(tài)集合I的任

24、何狀態(tài)S都屬于-closure(I)。 2. 狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體,狀態(tài)集合I的有關(guān)運算的例子,I=1, -closure(I)=1,2； I=5, -closure(I)=5,6,2； move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；,構(gòu)造NFA N的狀態(tài)K的子集的算法： 假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(tài)K的子集。 1 開始，令-closure(K0)為C中唯一成員，并且它是未被

25、標記的。,2 while （C中存在尚未被標記的子集T）do 標記T； for 每個輸入字母a do U:= -closure(move(T,a)； if U不在C中 then 將U作為未標記的子集加在C中 ,NFA的確定化,例子,等價的DFA,a,a,b,確定有窮自動機的化簡,說一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機。 所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。,DFA的最小

26、化就是尋求最小狀態(tài)DFA,最小狀態(tài)DFA的含義: 沒有多余狀態(tài)(死狀態(tài)) 沒有兩個狀態(tài)是互相等價（不可區(qū)別） 兩個狀態(tài)s和t可區(qū)別：不滿足 兼容性同是終態(tài)或同是非終態(tài) 傳播性從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達的狀態(tài)等價。,C和D同是終態(tài),讀入a到達C和F, C和F同是終態(tài), C和F讀入a都到達C,讀入b都到達E. C和D等價,a,a,b,最小狀態(tài)DFA,對于一個DFA M =（K,f, k0,kt)，存在一個最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結(jié)論 接受L的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的。,“分割法”,DFA的最小化算法的核心 把一個DFA

27、的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的. 算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己。,DFA的最小化算法,DFA M =（K,f, k0, kt),最小狀態(tài)DFA M 1.構(gòu)造狀態(tài)的一初始劃分： 終態(tài)kt 和非終態(tài)K- kt兩組(group) 2.對施用過程PP 構(gòu)造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復2 . 4.為final中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若k

28、是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉(zhuǎn)換f(k,a)=r,M 的開始狀態(tài)是含有S0的那組的代表 M 的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài)。,DFA的最小化例子,0:S,A,B C,D,E,F 1:S,A,B C,D,E,F 2:,a,A,S,B,b,B,S,a,a,后續(xù)內(nèi)容不要求,3.4*詞法分析程序的自動構(gòu)造,對有窮自動機和正規(guī)表達式進行了上述討論之后,我們介紹詞法分析程序的自動構(gòu)造方法,這個方法基于有窮自動機和正規(guī)表達式的等價性,即： 1.對于上的一個NFA M，可以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。 2.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NFA M，使的L(M)=L(R)。,從上的一個正規(guī)式R構(gòu)造上的一個NFA M，使得L(M)=L(R)的方法。 “語法制導”的方法，即按正規(guī)式的語法結(jié)構(gòu)指引構(gòu)造過程，構(gòu)造規(guī)則具體描述如下：,.“對于上的一個正規(guī)式R,可以構(gòu)造一個上的NFA M， ，使得L(M)=L(R).” 說明一種構(gòu)造方法：,(1)R=,構(gòu)造任一具有空終態(tài)集的NFA M (2） R= ，構(gòu)造的NFA M=(k0, ,f,k0.k0): f（k0,a)對于 所有a都沒定義。 (3）R=a,構(gòu)造的NFA M=(k0,k1,f,k0.k