第4部分詞法分析ppt課件

1、編譯原理編譯原理第第4 4章章 詞法分析詞法分析 詞法分析程序的設(shè)計 單詞的描畫工具 有限自動機 正規(guī)式和有窮自動機的等價性 正規(guī)文法和有窮自動機間的轉(zhuǎn)換 詞法分析程序的自動構(gòu)造工具編譯原理編譯原理 逐個讀入源程序字符并按照構(gòu)詞規(guī)那么切分成一逐個讀入源程序字符并按照構(gòu)詞規(guī)那么切分成一系列單詞。系列單詞。4.1 4.1 詞法分析程序的設(shè)計詞法分析程序的設(shè)計 詞法分析詞法分析lexical analysis 單詞是言語中具有獨立意義的最小單位，包括保管字、標(biāo)識符、運算符、標(biāo)點符號和常量等。詞法分析是編譯過程中的一個階段，在語法分析前進展。也可以和語法分析結(jié)合在一同作為一遍，由語法分析程序調(diào)用詞法分

2、析程序來獲得當(dāng)前單詞供語法分析運用。編譯原理編譯原理詞法分析程序詞法分析程序源程序源程序詞法分析程序詞法分析程序語法分析程序語法分析程序Tokenget token. 主要義務(wù)： 讀源程序，產(chǎn)生單詞符號。濾掉空格，跳過注釋、換行符。 追蹤換行標(biāo)志，復(fù)制出錯源程序。 宏展開， 其他義務(wù)：編譯原理編譯原理單詞符號單詞符號 單詞符號普通可分為以下五種： 根本字關(guān)鍵字：begin, end, if, while, var等。 標(biāo)識符：各種稱號，如常量名、變量名、過程名等。 常數(shù)量：25, 3.1415, TRUE, “ABC等 運算符：如 + - * / =等。 界符：逗號，分號，括號等。編譯原理編譯

3、原理 輸出表示單詞種別，單詞本身的值。輸出表示單詞種別，單詞本身的值。 單詞的種別可以用整數(shù)編碼表示，假設(shè)標(biāo)識符編碼為1，常數(shù)為2，保管字為3，運算符為4，界符為5。如：程序段 if i=5 then x=y；在經(jīng)詞法分析器掃描后輸出的單詞符號和它們的表示如下：編譯原理編譯原理 程序段 if i=5 then x=y - 保管字if(3，if)- 標(biāo)識符i(1，指向i的符號表入口)- 等號=(4，=)- 常數(shù)5(2，5)- 保管字then(3，then)- 標(biāo)識符x(1，指向x的符號表入口)- 賦值號=(4，=) - 標(biāo)識符 y(1，指向y的符號表入口)- 分號；(5，；) 編譯原理編譯原理詞

4、法分析任務(wù)獨立的緣由：詞法分析任務(wù)獨立的緣由： 簡化設(shè)計 改良編譯效率 添加編譯系統(tǒng)的可移植性 編譯原理編譯原理單詞的描畫工具單詞的描畫工具 文法文法G=VN，VT，P，S，P中每一產(chǎn)生式的方中每一產(chǎn)生式的方式都為：式都為：AaB或或Aa，其中，其中AVN ，BVN ，aVT。幾類單詞的描畫幾類單詞的描畫4.2 4.2 正那么表達式和正規(guī)集正那么表達式和正規(guī)集正規(guī)文法正規(guī)文法編譯原理編譯原理編譯原理編譯原理編譯原理編譯原理正規(guī)式正規(guī)式(regular expression)(regular expression)v 1。 和都是上的正規(guī)式，它們所表示的正規(guī)集分別為和；v2。任何a ，a是上的一

5、個正規(guī)式，它所表示的正規(guī)集為a；v3。假定e1和e2都是上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1e2, e1e2, e1也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。編譯原理編譯原理v 4。僅由有限次運用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是上的正規(guī)集。闡明：闡明：其中的其中的“讀為讀為“或也有運用或也有運用“+“+替代替代 “ 的；的；“ 讀為讀為“銜接；銜接；“讀為讀為“閉包即，恣意有限次的自反復(fù)銜接。在不閉包即，恣意有限次的自反復(fù)銜接。在不致混淆時，

6、括號可省去，但規(guī)定算符的優(yōu)先順序為致混淆時，括號可省去，但規(guī)定算符的優(yōu)先順序為“、“ 、“ 。銜接符。銜接符“ 普通可普通可省略不寫。省略不寫。“、“ 和和“ 都是左結(jié)合都是左結(jié)合的。的。編譯原理編譯原理 例4.2 令=a，b， 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有： 正規(guī)式 正規(guī)集 a a aba,b ab ab (ab)(ab)aa,ab,ba,bba ,a,a, 恣意個a的串(ab) ,a,b,aa,ab 一切由a和b組成的串(ab)(aabb)(ab)上一切含有兩個相繼的a或兩個相繼的b組成的串編譯原理編譯原理 例 =l，d，r=l(l d) 定義的正規(guī)集: l,ll,ld,ldd,，其中

7、l代表字母，d代表數(shù)字，正規(guī)式，即是字母(字母|數(shù)字)*，它表示的正規(guī)集中的每個元素的方式是“字母打頭的字母數(shù)字串，就是Pascal和多數(shù)程序設(shè)計言語允許的的標(biāo)識符的詞法規(guī)那么。 例4.3 =d，.，e，+，-,那么上的正規(guī)式 d(.dd )(e(+- )dd )表示的是無符號數(shù)的集合，其中d為09的數(shù)字。編譯原理編譯原理兩個正規(guī)式等價兩個正規(guī)式等價 假設(shè)兩個正規(guī)式e1和e2所表示的正規(guī)集一樣,那么說e1和e2等價,寫作e1=e2。例如： e1= (ab)， e2 = ba又如： b(ab) = (ba)b(ab) = (ab)編譯原理編譯原理正規(guī)式的運算律正規(guī)式的運算律 設(shè)r,s,t為正規(guī)式

8、，正規(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是“銜接的恒等元素 6。 rr=r r=rrr “或的抽取律 編譯原理編譯原理 對于上的正規(guī)式r ,存在一個G=(VN,VT,P,S) 使得L(G)=L(r) ，反之亦然。正規(guī)文法到正規(guī)式正規(guī)文法到正規(guī)式(1) 對形如 Axy的正規(guī)產(chǎn)生式： AxB By BVN編譯原理編譯原理 (2)對形如Axy的正規(guī)產(chǎn)生式：AxB Ay BxB By BVN (3)對形如Axy的正規(guī)產(chǎn)生式

9、: A x A y 不斷運用上述規(guī)那么做變換，直到每個產(chǎn)生式不斷運用上述規(guī)那么做變換，直到每個產(chǎn)生式右端只含一個右端只含一個VN。編譯原理編譯原理 例 r = a(ad) VT=a,d Sa(ad)Gs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB BSaAA(ad) A(ad)BAB(ad)BB規(guī)那么一規(guī)那么二編譯原理編譯原理 S=aAa例Gs:SaA AaA AdA Sa Aa Ad A =aAdA a d =(ad)A(ad) =(ad)(ad) S=a(ad)(ad)a =a(ad)(ad) =a(ad) R=a(ad)1AxB, ByA=xy 2AxA

10、y A=x y3Ax yA=x y編譯原理編譯原理4.34.3有窮自動機有窮自動機 確定的有窮自動機DFA 不確定的有窮自動機NFA NFA DFA 的轉(zhuǎn)換 DFA的化簡編譯原理編譯原理編譯原理編譯原理DFA 例：DFA M=S,U,V,Q, a,b, f, S, Q其中 f 定義為：fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=Q編譯原理編譯原理DFA DFA 的形狀圖表示的形狀圖表示fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QbSUVQaaaba，bb編譯原理編譯原理DFA DFA 的矩陣表

11、示的矩陣表示fS，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QabSUVUQVVUQQQQ字符形狀0100編譯原理編譯原理DFA確實定性表如今：確實定性表如今：轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)f:KK是一個單值函數(shù)，也就是一個單值函數(shù)，也就是說，對任何形狀是說，對任何形狀kK，和輸入符號，和輸入符號a，f(k,a)獨一地確定了下一個形狀。獨一地確定了下一個形狀。從形狀轉(zhuǎn)換圖來看，假設(shè)字母表從形狀轉(zhuǎn)換圖來看，假設(shè)字母表含有含有n個輸個輸入字符，那末任何一個形狀結(jié)點最多有入字符，那末任何一個形狀結(jié)點最多有n條條弧射出，而且每條弧以一個不同的輸入字弧射出，而且每條弧以一

12、個不同的輸入字符標(biāo)志。符標(biāo)志。編譯原理編譯原理編譯原理編譯原理* *上的符號串上的符號串 t t 被被 M M 接受接受對于*中的任何字符串t，假設(shè)存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上一切弧的的標(biāo)志符銜接成的字符串等于t，那么稱t可為DFA M所接受，假設(shè)M的初態(tài)結(jié)同時又是終態(tài)結(jié)，那么空字可為M所接受識別。假設(shè)t *，f(S，t)=P，其中S為DFA M的開場形狀，P Z，Z為終態(tài)集。那么稱t為DFA M所接受識別。編譯原理編譯原理例：證明例：證明t=baab被如下的被如下的DFA所接受。所接受。DFA M=S,U,V,Q, a,b, f, S, Q其中其中 f 定義為：定義為：fS

13、，a=UfV，a=UfS，b=Vfv，b=QfU，a=QfQ，a=QfU，b=VfQ，b=QbSUVQaaaba，bb證明：證明： fS，baab=ffS，b，aab=fV，aab=ffV，a，ab=fU，ab=ffU，a，b=fQ，b=QQ屬于終態(tài)。得證。屬于終態(tài)。得證。編譯原理編譯原理 DFA M所能接受的符號串的全體記為L(M) 結(jié)論： 上一個字符串集V是正規(guī)的，當(dāng)且僅當(dāng)存在一個上確實定有窮自動機M，使得V=L(M)。編譯原理編譯原理不確定的有窮自動機不確定的有窮自動機NFANFA 定義定義 N=K，f，S，Z，其中，其中K為形狀為形狀的有窮非空集，的有窮非空集， 為有窮輸入字母表，為有

14、窮輸入字母表，f為為K * 到到K的子集的映像，的子集的映像，SK是是初始形狀集，初始形狀集，Z K為終止形狀集。為終止形狀集。由此定義可看出：由此定義可看出：DFA是是NFA的特例的特例DFA與與NFA的區(qū)別：的區(qū)別：DFA的初態(tài)獨一，的初態(tài)獨一，NFA的初態(tài)不獨一。的初態(tài)不獨一。DFA的轉(zhuǎn)換函數(shù)是單值，的轉(zhuǎn)換函數(shù)是單值， NFA的轉(zhuǎn)換函數(shù)是多值。的轉(zhuǎn)換函數(shù)是多值。編譯原理編譯原理例子例子NFA N=S，P，Z，0，1，f，S，P，Z其中 fS，0=PfS，1=S，ZfP，1=ZfZ，0=PfZ，1=PSPZ00,1111形狀圖表示形狀圖表示編譯原理編譯原理矩陣表示矩陣表示01SPS,Z0P

15、Z0ZPP1簡化為01SPS,Z0P.Z0ZPP1NFA N=S，P，Z，0，1，f，S，P，Z其中其中 fS，0=PfS，1=S，ZfP，1=ZfZ，0=PfZ，1=P編譯原理編譯原理 *上的符號串t在NFA N上運轉(zhuǎn) *上的符號串t被NFA N接受讀出、識別 具有轉(zhuǎn)移的不確定的有窮自動機NFAf為 K 到K的子集的映像 對任何一個具有轉(zhuǎn)移的不確定的有窮自動機NFA N，一定存在一個不具有轉(zhuǎn)移的不確定的有窮自動機NFA ，使得L(M)=L(N)。編譯原理編譯原理DFA M=K，f，S，Z的行為的模擬程序K:=S；c:=getchar;while ceof do K:=f(K,c); c:=g

16、etchar; ;if K is in Z then return (yes) else return (no)編譯原理編譯原理NFANFA確實定化確實定化 DFA是NFA的特例.對每個NFA M一定存在一個DFA ，使得 L(M)=L(M )。 對每個NFA M存在著與之等價的DFA M 。與某一NFA等價的DFA不獨一。編譯原理編譯原理定義對形狀集合定義對形狀集合I I的幾個有關(guān)運算：的幾個有關(guān)運算： 1 形狀集合I的-閉包，表示為-closure(I)，定義為一形狀集，是形狀集I中的任何形狀S經(jīng)恣意條弧而能到達的形狀的集合。形狀集合I的任何形狀S都屬于-closure(I)。 2 形狀集

17、合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為形狀集合J，其中J是一切那些可從I的某一形狀經(jīng)過一條a弧而到達的形狀的全體。 定義Ia = -closure(J)編譯原理編譯原理例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；12534687aaa編譯原理編譯原理NFADFANFADFA 假設(shè)NFA N=(K, ,f,K0,Kt)按如下方法構(gòu)造一個DFA M=(S, ,d,S0,St)，使得L(M)=L(N)： 1. M的形狀集S由K的一些子集組成。用S1 S2

18、. Sj表示S的元素，其中S1, S2,. Sj是K的形狀。并且商定，形狀S1, S2,. Sj是按某種規(guī)那么陳列的，即對于子集S1, S2= S2, S1,來說，S的形狀就是S1 S2；編譯原理編譯原理2. M和N的輸入字母表是一樣的，即是；3. 轉(zhuǎn)換函數(shù)是這樣定義的： D(S1 ,S2 ,. , Sj,a)= R1 , R2 ,. , Rt，其中 R1 , R2 ,. , Rt = -closure(move(S1 ,S2 ,. , Sj,a) 4. S0=-closure(K0)為M的開場形狀；5. St=Si ,Sk ,.,Se，其中Si ,Sk ,. ,SeS且Si , Sk,. S

19、eKt編譯原理編譯原理構(gòu)造構(gòu)造NFA NNFA N的形狀的形狀K K的子集的算法：的子集的算法： 假定所構(gòu)造的子集族為C，即C= (T1, T2,. TI),其中T1, T2,. TI為形狀K的子集。 1. 開場，令-closure(K0)為C中獨一成員，并且它是未被標(biāo)志的。編譯原理編譯原理 2.while C中存在尚未被標(biāo)志的子集Tdo 標(biāo)志T； for 每個輸入字母a do U:= -closure(move(T,a)； if U不在C中 then 將U作為未標(biāo)志的子集加在C中編譯原理編譯原理例例4.8 將以下圖的將以下圖的NFA N轉(zhuǎn)換成轉(zhuǎn)換成DFA M023456789101bbbaa

20、NFA N編譯原理編譯原理023456789101bbbaa-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,2,4,5,7,10 加入為T4T4= 1,2,4,

21、5,7,10 1,2,3,4,6,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,2,4,5

22、,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 M編譯原理編譯原理DFADFA的最小化化簡的最小化化簡 最小形狀DFA 沒有多余形狀(死形狀) 沒有兩個形狀是相互等價不可區(qū)別 兩個形狀s和t等價：滿足 一致性同是終態(tài)或同是非終態(tài) 蔓延性從s出發(fā)讀入某個aa和從 t出發(fā)讀入某個a到達的形狀等價。編譯原理編譯原理消除多余形狀消除多余形狀s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s

23、6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s7編譯原理編譯原理 如圖，形狀0和4是可區(qū)別的。 形狀2和3是可區(qū)別的，由于讀入b后分別到達2和4，而2和4不是等價的。b02134abaaaabbbDFA M編譯原理編譯原理 對于一個DFA M =K,f, k0,kt)，存在一個最小形狀DFA M =K,f,k0,kt)，使L(M)=L(M). 算法的中心： 把M的形狀集K分成不相交的

24、子集。使得任何不同兩子集中的形狀都是可區(qū)別的，而同一子集中的任何兩形狀是等價的。 結(jié)論 接受L的最小形狀有窮自動機不計同構(gòu)是 獨一的。編譯原理編譯原理將以下圖中的將以下圖中的DFA MDFA 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 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbba13546aaaabbbbb去處多余形狀，合并去處多余形狀，合并等價形狀等價形狀 編譯原理編譯原理正規(guī)式和有窮自動機的等價性正規(guī)式和有窮自動機的等價性 1. 對于上的NFA M

25、，可以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。 2.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NFA M，使得L(M)=L(R)。編譯原理編譯原理 1. 對于上的NFA M，可以構(gòu)造一個上的正規(guī)式R,使得L(R)=L(M)。 第一步：在M的形狀轉(zhuǎn)換圖上加進兩個結(jié)，一個為x結(jié)點，一個為y結(jié)點。從x結(jié)點用弧銜接到M的一切初態(tài)結(jié)點，從M的一切終態(tài)結(jié)點用弧銜接到y(tǒng)結(jié)點。構(gòu)成一個與M等價的M,M只需一個初態(tài)x和一個終態(tài)y。 第二步：逐漸消去M中的一切結(jié)點，直至只剩下x和y。消去規(guī)那么見下頁 最后x和y結(jié)點間的弧上的標(biāo)志那么為所求的正規(guī)式R。編譯原理編譯原理123R1R213R1 R213R1R213R

26、1| R2123R1R3R213R1 R2* R3消為消為消為消為消為消為編譯原理編譯原理例：例：03124a,baaa,ba,bbb求正規(guī)式求正規(guī)式R編譯原理編譯原理a,b03124a,baaa,bbbxya|b024a|baaa|bbbxy編譯原理編譯原理a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy編譯原理編譯原理0a|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.對于上的一個正規(guī)式R，可以構(gòu)造一個上的NFA M，使得L(M)=L(R)。 由正規(guī)表達式構(gòu)造等價的NFA M的方法如下： (1) 將正規(guī)表達式R表示成如下圖的拓廣轉(zhuǎn)換圖。 (2) 對正規(guī)表達式采用以下圖所示的三條轉(zhuǎn)換規(guī)那么來構(gòu)造NFA M。X2 YR編譯原理編譯原理sisjr1 | r2sisjr1r2sisjr1*123sisjr1r2sisjskr1r2sisjskr1編譯原理編譯原理 對于給定的正規(guī)表達式R，首先將其表示成拓廣轉(zhuǎn)換圖，其中X為初始形狀，Y為終止形狀；然后逐漸將這個拓廣轉(zhuǎn)換圖運用三條轉(zhuǎn)換規(guī)那么不