詞法分析程序詞法分析程序

1、第四章第四章 詞法分析詞法分析 詞法分析程序的設計詞法分析程序的設計 單詞的描述工具單詞的描述工具 有限自動機有限自動機 正規(guī)式和有窮自動機的等價性正規(guī)式和有窮自動機的等價性 正規(guī)文法和有窮自動機間的轉換正規(guī)文法和有窮自動機間的轉換 詞法分析程序的自動構造工具詞法分析程序的自動構造工具4.1 詞法分析程序的設計詞法分析程序的設計 詞法分析（詞法分析（lexical analysis）源程序字符并按照構詞規(guī)則切分成源程序字符并按照構詞規(guī)則切分成一系列單詞。一系列單詞。單詞單詞是語言中具有獨立意義的是語言中具有獨立意義的最小單位最小單位，包，包括保留字、標識符、運算符、標點符號和常括保留字、標識符

2、、運算符、標點符號和常量等。量等。詞法分析是編譯過程中的一個階段，在語法詞法分析是編譯過程中的一個階段，在語法分析前進行。也可以和語法分析結合在一起分析前進行。也可以和語法分析結合在一起作為一遍，由語法分析程序調用詞法分析程作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。序來獲得當前單詞供語法分析使用。詞法分析程序詞法分析程序源程序源程序詞法分析程序詞法分析程序語法分析程序語法分析程序Tokenget token.主要任務：主要任務：讀源程序，產生單詞符號讀源程序，產生單詞符號其他任務：其他任務：濾掉空格，跳過注釋、換行符濾掉空格，跳過注釋、換行符追蹤換行標志，復制出錯源

3、程序，追蹤換行標志，復制出錯源程序，宏展開，宏展開，單詞符號單詞符號 單詞符號一般可分為下列五種：單詞符號一般可分為下列五種：（）：）：begin, end, if, while, var等等：各種名稱，如常量名、變量名、過：各種名稱，如常量名、變量名、過程名等程名等（量）：（量）：25, 3.1415, TRUE, “ABC”等等：如：如 + - * / =等等：逗號，分號，括號等：逗號，分號，括號等 輸出表示輸出表示（單詞種別，單詞自身的值）（單詞種別，單詞自身的值）。 A:=B+2 (Id,指向指向A的符號表的入口指針）的符號表的入口指針）(Becomes,) (Id,指向指向B的符號表

4、的入口指針的符號表的入口指針) (Num, 2) 詞法分析工作獨立的原因：詞法分析工作獨立的原因： 簡化設計簡化設計 改進編譯效率改進編譯效率 增加編譯系統(tǒng)的可移植性增加編譯系統(tǒng)的可移植性 單詞的描述工具單詞的描述工具 正規(guī)文法：正規(guī)文法：文法文法G=（VN，VT，P，S），），P中每一產生中每一產生式的式的形式都為：形式都為：或或，其中其中AVAVN N ，BVBVN N ，aVaVT T幾類單詞的描述幾類單詞的描述：標識符標識符l | l字母數字字母數字字母數字字母數字l | d | l字母數字字母數字| d 字母數字字母數字：無符號整數無符號整數d | d無符號整數無符號整數：運算符運算

5、符 + | - | * | / | = | 等號等號等號等號 =：界符界符 , | ; | ( | ) |：無符號實數無符號實數 d 余留無符號數余留無符號數| . 十進小數十進小數| e指數部分指數部分余留無符號數余留無符號數 d 余留無符號數余留無符號數| . 十進小數十進小數| e指數部分指數部分|十進小數十進小數 d 余留十進小數余留十進小數余留十進小數余留十進小數 e指數部分指數部分| d 余留十進小數余留十進小數| 指數部分指數部分 d 余留整指數余留整指數| s整指數整指數整指數整指數 d 余留整指數余留整指數余留整指數余留整指數 d 余留整指數余留整指數 |其中其中s表示正或負

6、號。表示正或負號。如如 25.55e+5 和和 2.1正規(guī)式正規(guī)式(regular expression) 定義（定義（正規(guī)式正規(guī)式和它所表示的和它所表示的正規(guī)集正規(guī)集）：）：設字母標為設字母標為 ，輔助字母表，輔助字母表 = ， ， ， ， ， ， 。v1。 和和 都是都是 上的正規(guī)式，它們所表示的正規(guī)集分別上的正規(guī)式，它們所表示的正規(guī)集分別為為 和和 ；v2。任何。任何a ，a是是 上的一個正規(guī)式，它所表示的正規(guī)上的一個正規(guī)式，它所表示的正規(guī)集為集為a；v3。假定假定e1和和e2都是都是 上的正規(guī)式，它們所表示的正規(guī)集上的正規(guī)式，它們所表示的正規(guī)集分別為分別為L(e1)和和L(e2)，那么

7、，那么，(e1), e1 e2, e1 e2, e1 也都是正也都是正規(guī)式規(guī)式,它們所表示的正規(guī)集分別為它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和和(L(e1) 。v4。僅由有限次使用上述三步驟而定義的表達式才是。僅由有限次使用上述三步驟而定義的表達式才是 上上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是的正規(guī)式，僅由這些正規(guī)式所表示的字集才是 上的正上的正規(guī)集。規(guī)集。 (e1), e1 e2, e1 e2, e1 L(e1), L(e1)L(e2), L(e1)L(e2)和和(L(e1) 。 其中的其中的“ ”讀為讀為“或或”（也有使用（也有使用“+”代

8、替代替 “ ” 的）；的）；“ ”讀為讀為“連接連接”；“ ”讀為讀為“閉包閉包”（即，任意有限次（即，任意有限次的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的自重復連接）。在不致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為的優(yōu)先順序為“ ”、“ ”、“ ” 。連接符。連接符“ ”一般可一般可省略不寫。省略不寫?！?”、“ ”和和“ ” 都是左結合的。都是左結合的。 例例4.2 令令 =a，b， 上的正規(guī)式和相應的正上的正規(guī)式和相應的正規(guī)集的例子有：規(guī)集的例子有：正規(guī)式正規(guī)式 正規(guī)集正規(guī)集a aa ba,bab ab(a b)(a b)aa,ab,ba,bba ,a,a, 任意個任意個a

9、的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a b) (aa bb)(a b) 上所有含有兩個相繼上所有含有兩個相繼 的的a或兩個相繼的或兩個相繼的b組成組成 的串的串 例例 =l，d，r=l(l d) 定義的正規(guī)集定義的正規(guī)集: l,ll,ld,ldd,（標識符）標識符） 例例4.3 =d，.，e，+，-,則則 上的正規(guī)上的正規(guī)式式 表示的是表示的是無符號數的集合。其中無符號數的集合。其中d為為09的數字。的數字。兩個正規(guī)式兩個正規(guī)式等價等價 若兩個正規(guī)式若兩個正規(guī)式e1和和e2所表示的所表示的,則說則說e1和和e2等價等價,寫作寫作e1=e2。 例如：

10、例如： e1= (a b)， e2 = b a 又如：又如： b(ab) = (ba) b(a b) = (a b ) 正規(guī)式的運算律正規(guī)式的運算律 設設r,s,t為正規(guī)式，正規(guī)式服從的代數規(guī)律有：為正規(guī)式，正規(guī)式服從的代數規(guī)律有： 1。r s=s r“或或”服從交換律服從交換律 2。r (s t)=(r s) t“或或”的可結合律的可結合律 3。(rs)t=r(st)“連接連接”的可結合律的可結合律 4。r(s t)=rs rt (s t)r=sr tr分配律分配律 5。 r=r, r =r 是是“連接連接”的恒等元素的恒等元素 6。 r r=r r = r rr “或或”的抽取律的抽取律

11、正規(guī)文法到正規(guī)式正規(guī)文法到正規(guī)式 對對 上的正規(guī)式上的正規(guī)式r ,存在一個存在一個G=(VN,VT,P,S)使得使得L(G)=L(r) ，反之亦然。反之亦然。 VT= ,S VN ，生成正規(guī)產生式生成正規(guī)產生式 Sr (1) 對形如對形如 Axy的的正規(guī)產生式：正規(guī)產生式：AxB By B VN(2)對形如對形如Ax y的的正規(guī)產生式：正規(guī)產生式： AxB Ay BxB By B VN (3)對形如對形如Ax y的的正規(guī)產生式正規(guī)產生式: A x A y 不斷應用上述規(guī)則做變換，直到每個產生式右端只不斷應用上述規(guī)則做變換，直到每個產生式右端只含一個含一個VN 例例 r = a(a d) VT=

12、a,d Sa(a d) SaAA(a d) A(a d)B A B(a d)B BGs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B（1）AxB, ByA=xy （2）AxAyA=xy（3）AxyA=xy S=aAa A =aAdA a d =(ad)A(ad) =(ad)(ad) S=a(ad)(ad)a =a(ad)(ad) =a(ad) R=a(ad)Gs:SaAAaAAdASaAaAd4.3有窮自動機 確定的有窮自動機（確定的有窮自動機（DFA） 不確定的有窮自動機（不確定的有窮自動機（NFA） NFA DFA 的轉換的轉換 DFA的化簡的化簡： 一個

13、確定的有窮自動機（DFA）M是一個五元組：M=（K，f，S，Z）其中1。 是一個有窮集，它稱一個；2。一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為；3。，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味著，當前狀態(tài)為ki，輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4。 K的一個；5。 K一個，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。DFA 例：例：DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定定義為：義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b

14、）=Vf（Q，b）=QDFA 的狀態(tài)圖表示的狀態(tài)圖表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bbDFA 的矩陣表示的矩陣表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符狀態(tài)0100 一個輸入符一個輸入符號號串串t，（，（我們將它表示成我們將它表示成Tt1的形的形式，其中式，其中T，t1 *）在）在DFA M上上的的定義為：定義為： 其中其中QK 擴充轉換函數擴充轉換函數

15、f f，是是K*K上的映射，且：上的映射，且： f（Q， ）= Q*上的符上的符號號串串 t 被被 M 接受接受 對于對于*中的任何字符串中的任何字符串t，若存在一條從初態(tài)若存在一條從初態(tài)結到某一終態(tài)結的道路，且這條路上所有弧的結到某一終態(tài)結的道路，且這條路上所有弧的的標記符連接成的字符串等于的標記符連接成的字符串等于t，則稱則稱t可為可為DFA M所接受，若所接受，若M的初態(tài)結同時又是終態(tài)的初態(tài)結同時又是終態(tài)結，則空字可為結，則空字可為M所所（）。）。 若若t *，f(S，t)=P，其中其中S為為DFA M的開始的開始狀態(tài)，狀態(tài)，P Z，Z為終態(tài)集。為終態(tài)集。則稱則稱t為為DFA M所所（）

16、。）。例：證明例：證明t=baab被如下的被如下的DFA所接受。所接受。DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定義為：定義為：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（v，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb證明：證明： 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）=QQ屬于終態(tài)。得證。屬于終態(tài)。得證。 DFA M所能接受的符所能接受的符號號串的全體記為串的全體記為L(M) 結論

17、：結論： 上一個字符串集上一個字符串集V 是正規(guī)的，當且僅當存是正規(guī)的，當且僅當存在一個在一個 上的確定有窮自動機上的確定有窮自動機M，使得使得 V=L(M)。不確定的有窮自動機不確定的有窮自動機NFA 定義定義 N= K， ，f，S，Z ，其中其中的有窮非的有窮非空空， 有窮輸入有窮輸入，K * 到到K的子集的的子集的， K始狀始狀， K止狀止狀。例子例子NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=PSPZ00,1111狀態(tài)圖表示狀態(tài)圖表示表格表示表格表示01SPS,Z0PZ0ZPP1簡化為01

18、SPS,Z0P.Z0ZPP1NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 f（S，0）=Pf（S，1）=S，Zf（P，1）=Zf（Z，0）=Pf（Z，1）=P *上的符上的符號號串串t在在NFA N上運行上運行 *上的符上的符號號串串t被被NFA N接受（讀出、識別）接受（讀出、識別） 具有具有 轉移的不確定的有窮自動機轉移的不確定的有窮自動機NFAf為為 K （ ）到）到K的子集的映像的子集的映像 對任何一個具有對任何一個具有 轉移的不確定的有窮自動轉移的不確定的有窮自動機機NFA N，一定存在一個不具有一定存在一個不具有 轉移的轉移的不確定的有窮自動機不確定的有窮自動機NFA

19、 ，使得，使得L(M)=L(N)。DFA M=（K，f，S，Z）的行為的模擬的行為的模擬程序程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes) else return (no) DFA是是NFA的特例的特例.對每個對每個NFA M一定存在一定存在一個一個DFA ，使得，使得 L(M)=L(M )。 對每個對每個NFA M存在著與之存在著與之的的DFA M 。與某一與某一NFA等價的等價的DFA不唯一。不唯一。定義對狀態(tài)集合定義對狀態(tài)集合I的幾個有關運算：的幾個有關運算： 1

20、 狀態(tài)集合狀態(tài)集合I的的 -閉包，表示為閉包，表示為，定義為一狀態(tài)集，是狀態(tài)集定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)S經任意條經任意條 弧而能到達的狀態(tài)的集合?；《艿竭_的狀態(tài)的集合。狀狀態(tài)集合態(tài)集合I的任何狀態(tài)的任何狀態(tài)S都屬于都屬于 -closure(I)。 2 狀態(tài)集合狀態(tài)集合I的的a弧轉換，表示為弧轉換，表示為定義為狀態(tài)集合定義為狀態(tài)集合J，其中其中J是所有那些可從是所有那些可從I的某一狀態(tài)經過一條的某一狀態(tài)經過一條a弧而到達的狀態(tài)的全弧而到達的狀態(tài)的全體。體。 定義定義Ia = -closure(J)例例I=1, -closure(I)=1,2；I=5, -closure

21、(I)=5,6,2；move(1,2,a)=5,3,4 -closure(5,3,4)=2,3,4,5,6,7,8；12534687aaaNFADFA 假設假設NFA N=(K, ,f,K0,Kt)按如下辦法構造按如下辦法構造一個一個DFA M=(S, ,d,S0,St)，使得使得L(M)=L(N)： 1. M的狀態(tài)集的狀態(tài)集S由由K的一些子集組成。用的一些子集組成。用S1 S2. Sj表示表示S的元素，其中的元素，其中S1, S2,. Sj是是K的狀的狀態(tài)。并且約定，狀態(tài)態(tài)。并且約定，狀態(tài)S1, S2,. Sj是按某種規(guī)則是按某種規(guī)則排列的，即對于子集排列的，即對于子集S1, S2= S2,

22、 S1,來說，來說，S的狀態(tài)就是的狀態(tài)就是S1 S2； 2. M和和N的輸入字母表是相同的，即是的輸入字母表是相同的，即是 ； 3. 轉換函數是這樣定義的：轉換函數是這樣定義的： D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt其中其中 R1 , R2 ,. , Rt = 4. 為為M的開始狀態(tài)；的開始狀態(tài)； 5. St=Si ,Sk ,.,Se，其中，其中Si ,Sk ,. ,Se S且且Si , Sk,. Se Kt構造構造NFA N的狀態(tài)的狀態(tài)K的子集的算法：的子集的算法： 假定所構造的子集族為假定所構造的子集族為C，即即C= (T1, T2,. TI),其中其中

23、T1, T2,. TI為狀態(tài)為狀態(tài)K的子集。的子集。 1. 開始，令開始，令 -closure(K0)為為C中唯一成員，并中唯一成員，并且它是未被標記的。且它是未被標記的。 2.while （C中存在尚未被標記的子集中存在尚未被標記的子集T）do 標標記記T； for 每個輸入字母每個輸入字母a do U:= -closure(move(T,a)； if U不不在在C中中 then 將將U作為未標記的子集加在作為未標記的子集加在C中中例例4.8 將下圖的將下圖的NFA N轉換成轉換成DFA M023456789101bbbaaNFA N023456789101bbbaa -closure(mo

24、ve(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入為加入為T11,2,4,5,6,7 加入為加入為T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入為加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,7,10 加入為加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6

25、,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2 -closure(move(Ti,a) -closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入為加入為T11,2,4,5,6,7 加入為加入為T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入為加入為T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,

26、2,4,5,7,10 加入為加入為T4T4= 1,2,4,5,7,10 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2初態(tài)終態(tài)b02134abaaaabbbDFA MDFA的最小化（化簡）的最小化（化簡） 最小狀態(tài)最小狀態(tài)DFA 沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài)) ) 沒有兩個狀態(tài)是互相等價（不可區(qū)別）沒有兩個狀態(tài)是互相等價（不可區(qū)別） 兩個狀態(tài)兩個狀態(tài)s和和t等價：滿足等價：滿足 一致性一致性同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài) 蔓延性蔓延性從從s出發(fā)讀入某個出發(fā)讀入某個a a和從和從 t出發(fā)出發(fā)讀入某個讀入某個a到達的狀態(tài)等價。到達的狀態(tài)等價

27、。消除多余狀態(tài)消除多余狀態(tài)s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7 如圖，狀態(tài)如圖，狀態(tài)0和和4是可區(qū)別的。是可區(qū)別的。 狀態(tài)狀態(tài)2和和3是可區(qū)別的，因為讀入是可區(qū)別的，因為讀入b后分別到后分別到達達2和和4，而，而2和和4不是等價的。不

28、是等價的。b02134abaaaabbbDFA M 對于一個對于一個DFA M =DFA M =（K,f,K,f, k k0 0, , ,k kt t) )，存在存在一個一個最小狀態(tài)最小狀態(tài)DFA M = =（K,f,K,f, k k0 0, , ,k kt t) )，,使使L(M)=L(M). 算法的核心：算法的核心：。 結論結論 接受接受L的最小狀態(tài)有窮自動機不計同構是唯一的最小狀態(tài)有窮自動機不計同構是唯一的。的。將下圖中的將下圖中的DFA M最小化最小化 1,2,3,4,5,6,7Ia: 6,7,1,4,7,4,4Ib: 3,3,5,6,3,1,21,2,3,4 5,6,71,2 3,4

29、 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb13546aaaaabbbbb 1. 對于對于上的上的NFA M，可以構造一個，可以構造一個上上的正規(guī)式的正規(guī)式R,R,使得使得L(R)=L(M)。 2 2. .對于對于上的一個正規(guī)式上的一個正規(guī)式R，可以構造一，可以構造一個個上的上的NFA M，使得，使得L(M)=L(R)。 1. 對于對于上的上的NFA M，可以構造一個，可以構造一個上上的正規(guī)式的正規(guī)式R,R,使得使得L(R)=L(M)。 第一步：在第一步：在M的狀態(tài)轉換圖上的狀態(tài)轉換圖上，一，一個為個為x結點，一個為結點，一個為y結點。從結點。從x結點用結點

30、用弧連接弧連接到到M的的，從，從M的的用用弧連接到弧連接到y(tǒng)結點。形成一個與結點。形成一個與M等價的等價的M,M只有只有和和。 第二步：逐步消去第二步：逐步消去M中的所有結點，直至只中的所有結點，直至只剩下剩下x和和y。（。（消去規(guī)則見下頁）消去規(guī)則見下頁） 最后最后x和和y結點間的弧上的標記則為所求的正規(guī)結點間的弧上的標記則為所求的正規(guī)式式R。123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R3例：例：03124a,baaa,ba,bbb求正規(guī)式求正規(guī)式R03124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy024a|baaa|ba|bbbxy0a|baa(a|b)*bb(a|b)*xy0a|baa(a|b)*bb(a|b)*xy0a|bxyaa(a|b)* |bb(a|b)*xy(a|b)* (aa |bb)(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)* 2 2. .對于對于上的一個正規(guī)式上的一個正規(guī)式R，可以構造一個，可以構造一個上上的的NFA M，使得，使得L(M)=L(R)。 (1) R=, 任一具有空終態(tài)集的任一具有空終態(tài)集的NFA M (2) R= ，NFA M=(k0, ,f,k,f,k0 0.k.k0 0):): f f（k k