1、編譯原理（4）,山東師范大學信息科學與工程學院,本章將討論與詞法分析程序有關的問題，包括單詞的描述、識別機制及詞法分析程序的自動構造原理。 4.1 詞法分析程序的設計 4.2 單詞的描述工具 4.3 有窮自動機 4.4 正規(guī)式與有窮自動機的等價 4.5正規(guī)文法與有窮自動機的等價 4.6 詞法分析程序的自動構造,第4章 詞 法 分 析,4.1 詞法分析程序的設計4.1.1 詞法分析程序與語法分析程序的接口,詞法分析程序讀源文件，生成中間文件，語法分析程序讀中間文件。 詞法分析程序作為語法分析的一個子程序。 詞法分析程序的主要任務： 讀源程序，產生單詞符號 詞法分析程序的其他任務： 濾掉空格，跳過

2、注釋、換行符 追蹤換行標志，復制出錯源程序， 宏展開，,4.1.2 詞法分析程序的輸出,單詞串,識別的單詞： （類別，值） 1 保留字：如：BEGIN、 END、 IF、 THEN等 2 標識符： 用戶定義的變量名、常數(shù)名、過程名 3 常數(shù)： 如：10、25、100、3.12等整數(shù) 4 運算符： 如：+、-、*、/、：=、#、=、=等 5 界符： 如：,、. 、; 、( 、)等 單詞的值？,例如： if i=5 then x:=y經(jīng)詞法分析后所獲得單詞為： if (1,if) I (2, I在標識符表地址） = (5,=) 5 (3, 5) Then (1, then) X (2, x在標識符

3、表地址） := (5, :=) y (2, y在標識符表地址）,是編譯程序結構簡單、清晰、條理化 改進編譯程序效率 增加編譯系統(tǒng)的可移植性 （p48),4.1.3 將詞法分析工作分離的考慮,4.2 單詞的描述工具,4.2.1 正規(guī)文法 任一產生式的形式都為AaB或Aa，其中 AVN ，BVN ，aVT 例： l | l l|d|l|d d|d +|-|*|/|=,例4.1 無符號數(shù)文法 d | . |e d | . |e| d e | d | d|s d d|,4.2.2 正規(guī)式,正規(guī)式也稱正則表達式,正規(guī)表達式。下面是正規(guī)式和它所表示的正規(guī)集的遞歸定義。,定義（正規(guī)式和它所表示的正規(guī)集）:

4、設字母表為，輔助字母表=， ，。 1. 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和 ； 2. 任何a ，則a是上的一個正規(guī)式，它所表示的正規(guī)集為a； 3. 假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。 4.僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的集合才是上的正規(guī)集。,正規(guī)式中的符號,“”讀為“或”（也有使用“+”代替 “” 的）； “ ”讀為“連接”；在不致混淆時，

5、括號可省去. “”讀為“閉包”（即，任意有限次的自重復連接）。 但規(guī)定算符的優(yōu)先順序為“”、“ ”、“” 。連接符“ ”一般可省略不寫。 “”、“ ”和“” 都是左結合的。,例子4.2,令=a，b， 上的正規(guī)式和相應的正規(guī)集的例子有： 正規(guī)式 正規(guī)集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,a, 任意個a的串 (ab) ,a,b,aa,ab 所有由a和b組成的串 (ab)(aabb)(ab) 上所有含有兩個相繼 的a或兩個相繼的b組成的串,例4.3 令=l，d，則上的正規(guī)式 r=l(l d) 定義的正規(guī)集為: l,ll,ld,ldd,其中l(wèi)代表字母

6、,d代表數(shù)字,正規(guī)式 即是 字母(字母|數(shù)字) ,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和 多數(shù)程序設計語言允許的的標識符的詞法規(guī)則. 若令=d，e，+，-, 則上的正規(guī)式 d(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

7、。rs=sr“或”服從交換律 2。r(st)=(rs)t“或”的可結合律 3。(rs)t=r(st)“連接”的可結合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r是“連接”的恒等元素 6。 rr=r,4.2.3 正規(guī)文法到正規(guī)式 正規(guī)文法-正規(guī)式 1.任給上的正規(guī)式r,可構造正規(guī)文法G,使得L(G)=L(r) 構造： 取Vn=S, 增加產生式：S r, 注意：S為文法開始符。 利用下列規(guī)則展開： 若A xy, 則替換為 A xB By 若A x*y, 則替換為 A xB|y BxB|y 若A x|y, 則替換為 A x By,例4.4將r=a(a|d)*轉換

8、成正規(guī)文法。 S a(a|d)* 代換為S aA A (a|d)*,重寫為： S aA A (a|d)B| B (a|d)B| ,2. 根據(jù)正規(guī)文法求出正規(guī)式 轉換規(guī)則： 文法產生式 正規(guī)式 A xB|y A=xy A xA|y A= x*y A x Ay A=x|y,例4.5 已給文法GS,求對應的正規(guī)式 S aA|a A aA|dA|a|d 構造如下： S=aA|a A =aA|dA|a|d 可以變?yōu)椋?A=（a|d)A|a|d 有規(guī)則2知：A=（a|d)+ 從而有：S=a（a|d)+|a,4.3 有窮自動機 有窮自動機(也稱有限自動機)作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文

9、法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構造尋找特殊的方法和工具。 有窮自動機分為兩類：確定的有窮自動機(DFA, Deterministic Finite Automata)和不確定的有窮自動機(NFA, Nondeterministic Finite Automata) 。,關于有窮自動機我們將討論如下題目,確定的有窮自動機DFA 不確定的有窮自動機NFA NFA的確定化 DFA的最小化,4.3.1 確定的有窮自動機DFA,（1）DFA定義： 一個確定的有窮自動機（DFA）M是一個五元組：M=（K，f，S，Z）其中 1.K是一個有窮集，它的每個元

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

11、FA的表示 DFA的狀態(tài)圖表示： 假定DFA M含有m個狀態(tài)，n個輸入字符，那么我們可以用含有m個結點，且每個結點最多有n個弧射出的有向圖表示，整個圖含有唯一一個初態(tài)結點和若干個終態(tài)結點，初態(tài)結點冠以雙箭頭“=”或標以“-”，終態(tài)結點用雙圈表示或標以“+”，若 f(ki,a)=kj，則從狀態(tài)結點ki到狀態(tài)結點kj畫標記為a的弧；,DFA 的狀態(tài)圖表示,DFA的矩陣表示 一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭“=”標明初態(tài)；否則第一行即是初態(tài)，相應終態(tài)行在表的右端標以1，非終態(tài)標以0

12、。,DFA 的矩陣表示,0 0 0 1,（4）*上的符號串t在DFA M上運行 一個輸入符號串t，（將它表示成t1 tx的形式，其中 t1 ，tx *） 在DFA M=（K，f，S，Z）上運行的定義為： f（Q， t1 tx ）=f（f（Q， t1 ），tx） 其中QK 擴充轉換函數(shù)f為 K*K上的映射，且： f（ki，）= ki f（Q， t1 tx ）=f（f（Q， t1 ），tx）,*上的符號串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所接受。

13、 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)。 得證。,b,a,b,a,a,DFA M所能接受的符號串的全體記為L(M),成為DFA所示別的語言。. 對于任何兩個有窮自動機M和M，如果L(M)=L(M)，則稱M與M是等價的. 結論： 上一個符號串集V是正規(guī)的，當且僅當存在一個上的確定有窮自動機M，使得 V=L(M)。,DFA的確定性表現(xiàn)在轉換函數(shù)f:KK是一個單值函數(shù)，也就是說，對任何狀態(tài)kK，和輸入符號a，f(k,a)唯一地確定了下一個狀態(tài)。從狀態(tài)轉換圖來看，若字母

14、表含有n個輸入字符，那末任何一個狀態(tài)結點最多有n條弧射出，而且每條弧以一個不同的輸入字符標記。,DFA的行為很容易用程序來模擬. 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,DFA = digit,not digit,.2 不確定的有窮自動機NFA,(1)定義 NFA M=K，f，S，Z，其中K為狀態(tài)的有窮非空集， 為有窮輸入字母表，f為K * 到K的子集（2 K）的一種

15、映射，SK是初始狀態(tài)集，Z K為終止狀態(tài)集.,（2）例子 NFA M=（S，P，Z，0，1，f，S，P，Z） 其中 f（S，0）=P f（Z，0）=P f（P，1）=Z f（Z，1）=P f（S，1）=S，Z,狀態(tài)圖表示,矩陣表示,矩陣表示,f為K * 到K的子集（2 K）的一種映射,再如：例4.7 p54 （3）具有轉移的不確定的有窮自動機,1,2,a,b,c,有如下定理:,對任何一個具有轉移的不確定的有窮自動機NFA N，一定存在一個不具有轉移的不確定的有窮自動機NFA ，使得L(M)=L(N)。 與上例等價的一個NFA.,2,a,c,b,b,a,c,a,c,b,b,（4） 對NFA M=

16、K，f，S，Z的擴展,*上的符號串t在NFA M上運行. 一個輸入符號串t，（我們將它表示成at1的形式，其中a，t1 *）在NFA M上運行的定義為： f（Q， at1）=f（f（Q，a），t1） 其中QK. *上的符號串t被NFA M接受 若t *，f(S0，t)=P，其中S0 S，P Z， 則稱t為NFA M所接受（識別）,*上的符號串t被NFA M接受也可以這樣理解,對于中的任何一個串t，若存在一條從某一初態(tài)結到某一終態(tài)結的道路，且這條道路上所有弧的標記字依序連接成的串(不理采那些標記為的弧)等于t，則稱t可為NFA M所識別(讀出或接受)。若M的某些結既是初態(tài)結又是終態(tài)結，或者存在一

17、條從某個初態(tài)結到某個終態(tài)結的道路,其上所有弧的標記均為，那么空字可為M所接受。,例： 000 111 1010001 110000001 00 01100,NFA M所能接受的符號串的全體記為 L(M) 結論： 上一個符號串集V是正規(guī)的，當且僅當存在一個上的不確定的有窮自動機M，使得V=L(M)。,(0|1)*(000|111)(0|1) *,4.3.3 NFA到DFA的轉換 （1）討論問題 DFA是NFA的特例. 結論： 對每個NFA N一定存在一個DFA ，使得 L(M)=L(N)。對每個NFA N存在著與之等價的DFA M。 有一種算法，將NFA轉換成接受同樣語言的DFA.這種算法稱為子

18、集法. 與某一NFA等價的DFA不唯一.,（2） NFA確定化算法:,假設NFA N=(K, ,f,K0,Kt)按如下辦法構造一個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ī)則排列的，即對于子集S1, S2= S2, S1,來說，S的狀態(tài)就是S1 S2；,2 M和N的輸入字母表是相同的，即是； 3 轉換函數(shù)是這樣定義的： d(S1 S2,. Sj,a)= R1R2. Rt 其中 R1,R2,. , Rt = -clos

19、ure(move(S1, S2,. Sj,a) 4 S0=-closure(K0)為M的開始狀態(tài)； 5 St=Si Sk. Se，其中Si Sk. SeS且Si , Sk,. SeKt,（3）定義對狀態(tài)集合I的幾個有關運算：,1. 狀態(tài)集合I的-閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達的狀態(tài)的集合。 狀態(tài)集合I的任何狀態(tài)S都屬于-closure(I)。 2. 狀態(tài)集合I的a弧轉換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。,（4）狀態(tài)集合I的有關運算的例子,I=1, -clo

20、sure(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；,（5）構造NFA N的狀態(tài)K的子集的算法： 假定所構造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為狀態(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中 ,（6）

21、 NFA的確定化例子例,等價的DFA,a,a,b,例4.8（p55圖4.4）,4.3.4 確定有窮自動機的化簡,一個有窮自動機是化簡了的，即是說，它沒有多余狀態(tài)并且它的狀態(tài)中沒有兩個是互相等價的。一個有窮自動機可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個最小的與之等價的有窮自動機。 所謂有窮自動機的多余狀態(tài)，是指這樣的狀態(tài)：從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的那個狀態(tài)；或者從這個狀態(tài)沒有通路到達終態(tài)。,(1) DFA的最小化就是尋求最小狀態(tài)DFA,最小狀態(tài)DFA的含義: 沒有多余狀態(tài)(死狀態(tài)) 沒有兩個狀態(tài)是互相等價（不可區(qū)別） 兩個狀態(tài)s和t可區(qū)別：不滿足 兼容性同是終態(tài)或同是非

22、終態(tài) 傳播性從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達的狀態(tài)等價。 (改為：任意符號串w, f(s,w)Z 當且切僅當f(s,w)Z ),C和D同是終態(tài),讀入a到達C和F, C和F同是終態(tài), C和F讀入a都到達C,讀入b都到達E. C和D等價,a,a,b,(2)最小狀態(tài)DFA,對于一個DFA M =（K,f, k0,kt)，存在一個最小狀態(tài)DFA M =（K,f, k0,kt)，,使L(M)=L(M). 結論 接受L的最小狀態(tài)有窮自動機不計同構是唯一的。,(3)“分割法”,DFA的最小化算法的核心 把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中

23、的任何兩個狀態(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.構造狀態(tài)的一初始劃分：終態(tài)kt 和非終態(tài)K- 兩組(group) 2.對施用過程PP 構造新劃分new 3. 如new =,則令 final= 并繼續(xù)步驟4，否則:=new重復2 . 4.為final中的每一組選一代表，這些代表構成M的狀態(tài)。若k是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉換f(k,a)=r M 的開

24、始狀態(tài)是含有S0的那組的代表， M 的終態(tài)是含有F的那組的代表 5.去掉M中的死狀態(tài).,過程PP : Construction of new,For each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on to states in the same group of ;/*at

25、worst, a state will be in a subgroup by itself*/ 2.replace G in new by the set of all subgroups formed end,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,再如：p58例4.9(自己做）,4.4有窮自動機和正規(guī)表達式的等價性,1.對于上的一個NFA M，可以構造一個上的正規(guī)式R,使得L(R)=L(M)。 2.對于上的一個正規(guī)式R，可以構造一個上的NFA M，使的L(M)=L(R)。,1.對于上的一個NFA M,構

26、造正規(guī)式R，使得L(M)=L(R)的方法。 第一步：增加兩個狀態(tài)X,Y ,構造相應的弧,第二步：利用下列規(guī)則，逐步消去中間節(jié)點，最終只剩下X,Y，節(jié)點X到Y弧上的標記即為所求得正規(guī)式R。,例4.10 p59,2. “對于上的一個正規(guī)式R,可以構造一個上的NFA M，使得L(M)=L(R).”,(1)R=,構造任一具有空終態(tài)集的NFA M (2） R= ，構造的NFA M=(k0, ,f,k0,k0): f（k0,a)對于 所有a都沒定義。 (3）R=a,構造的NFA M=(k0,k1,f,k0,k1): f(k0,a) = k1 (4) R =R1 | R2, 將步驟（1）（2）（3）分別應用到R1,R2 產生M1= (K1,f1,k1,F1), M2=(K2,f2,k2,F2),其中K1,K2不相交. 構造NFA M= (K1K2k,f,k,F) : k是新增加的狀態(tài)符號，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a). 若k1F1且