編譯原理：第4章 詞法分析（1、2、3）

1、第4章 詞法分析本章重點(diǎn)詞法分析器的設(shè)計(jì)技術(shù)，即有窮狀態(tài)自動(dòng)機(jī)技術(shù)和正則式技術(shù)正則文法、正則式、非確定的有窮狀態(tài)自動(dòng)機(jī)（NFA）、確定的有窮狀態(tài)自動(dòng)機(jī)（DFA）之間的等價(jià)性及相互變換的方法。4.1 詞法分析程序的設(shè)計(jì) 1 詞法分析程序的功能 源程序 單詞序列 2 單詞的詞類和屬性 （詞類符號(hào)，單詞的屬性值） 3 把詞法分析設(shè)計(jì)成一個(gè)獨(dú)立程序 (1) 語(yǔ)法分析程序的子程序； （2）組織成一遍掃描。詞法分析器=80;eniLLine=80;=;輸入031字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字=；4562001字母1字母1字母200=5000=53數(shù)字3數(shù)字3數(shù)字3數(shù)字44；6輸出1字母1字母 id , Line =

2、 , num, 80 ;, 有限控制器分析結(jié)束While ij do if ij then i:i-j else j:=j-i while ， i ， ， j ， do ， if ， i ， ， j , then , i , := , i, - , j ,else, j , := , j , - , i 詞法分析器1 詞法分析程序的功能程序語(yǔ)言單詞的分類： 1關(guān)鍵字(保留字或基本字)：begin, end 2標(biāo)識(shí)符：用來(lái)表示各種名字 3字面常數(shù)：256，3 .14，true, abc 4 運(yùn)算符：如，、*、/ 等等 5分界符：如逗號(hào)，分號(hào)，冒號(hào)等2 單詞的詞類和屬性詞法分析器的輸出： （詞類編

3、碼，單詞自身的屬性值）* 詞類編碼提供給語(yǔ)法分析程序使用；* 單詞自身的屬性值提供給語(yǔ)義分析程序使用。具體的分類設(shè)計(jì)以方便語(yǔ)法分析程序使用為原則。關(guān)鍵字可分成一類，也可以一個(gè)關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型( 整型、實(shí)型、布爾型等)，每個(gè)類型的常數(shù)劃分成一類。單詞自身的屬性值提供的內(nèi)容，是由詞法分析和語(yǔ)義分析的任務(wù)劃分決定的。2 單詞的詞類和屬性例如：圖3.1的源程序經(jīng)詞法分析器的輸出while， id，指向i的符號(hào)表入口的指針relop ， NE id，指向j的符號(hào)表入口的指針do， if， id，指向i的符號(hào)表入口的指針 id，指向j的符號(hào)表入口的指針3 把詞法分析設(shè)計(jì)成一個(gè)獨(dú)立

4、程序 （1）組織成一遍掃描；（2）作為語(yǔ)法分析和語(yǔ)義分析的子程序詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼生成源程序中間代碼 符 號(hào) 表 管 理 錯(cuò) 誤 的 診 查 處 理（1）詞法分析程序的主要任務(wù)掃描源程序，產(chǎn)生單詞符號(hào)（2）詞法分析程序的其他任務(wù)濾掉空格，跳過(guò)注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開(kāi)，（3）就詞法分析工作從語(yǔ)法分析工作獨(dú)立出來(lái)的原因簡(jiǎn)化設(shè)計(jì)改進(jìn)編譯效率增加編譯系統(tǒng)的可移植性 詞法分析程序的工作實(shí)例 PL/0編譯程序的結(jié)構(gòu)圖掃描器分析器代碼生成器表格管理出錯(cuò)管理目標(biāo)程序（中間代碼）以PL/0（2.2節(jié)，P16）為例=數(shù)據(jù)流，調(diào)用關(guān)系PL/0編譯器等用一趟（pass）掃描方式

5、 以語(yǔ)法分析器為核心，掃描器和代碼生成器都作為一個(gè)獨(dú)立過(guò)程，由分析器調(diào)用。（當(dāng)語(yǔ)法分析正確，調(diào)用代碼生成器）圖1（a）PL/0編譯程序的結(jié)構(gòu)圖實(shí)例 PL/0編譯程序的結(jié)構(gòu)圖掃描器分析器代碼生成器表格管理出錯(cuò)管理目標(biāo)程序（中間代碼）PL/0語(yǔ)言目標(biāo)程序PL/0語(yǔ)言解釋執(zhí)行程序輸入數(shù)據(jù)輸出數(shù)據(jù)圖1(a) PL/0編譯程序的結(jié)構(gòu)圖圖1(b) PL/0解釋執(zhí)行結(jié)構(gòu)圖 4 掃描器的接口設(shè)計(jì)掃描器以兩種方式與語(yǔ)法分析器連接： （1）詞法分析可作為單獨(dú)一遍來(lái)實(shí)現(xiàn)詞法分析器處理字符串源程序，輸出是關(guān)于單詞符號(hào)序列的中間文件，供語(yǔ)法分析使用。 字符串源程序 詞法分析 單詞符號(hào)串源程序 圖詞法分析單獨(dú)作為一遍 （

6、2）詞法分析程序作為語(yǔ)法分析程序的子程序 有些編譯程序?qū)⒃~法分析和語(yǔ)法分析安排在同一遍中，此時(shí)詞法分析作為語(yǔ)法分析程序的一個(gè)子程序。每當(dāng)語(yǔ)法分析需要一個(gè)新的單詞符號(hào)時(shí)，就調(diào)用詞法分析子程序，詞法分析子程序從字符串源程序中識(shí)別出一個(gè)具有獨(dú)立意義的單詞，將其單詞符號(hào)返給語(yǔ)法分析。字符串源程序 詞法分析器 語(yǔ)法分析器 圖詞法分析作為語(yǔ)法分析子程序 取單詞 送單詞掃描器主要操作（1）next-char（輸入模塊: 讀下一字符）返回字符以全局量或參數(shù)形式傳給其他模塊（2）error（錯(cuò)誤處理模塊）發(fā)現(xiàn)非法的單詞符號(hào)（3）識(shí)別單詞（核心任務(wù)）構(gòu)造單詞的內(nèi)部表示-屬性字（語(yǔ)義字）難點(diǎn)：詞法的三種表示：正則文

7、法、正則式、狀態(tài)轉(zhuǎn)換圖（即FA）。三者之間的等價(jià)性及相互變換的方法。4.2 單詞的定義及識(shí)別單詞的描述工具 （1）正則文法（2）正則表達(dá)式（3）有窮狀態(tài)自動(dòng)機(jī)FA正則文法擅長(zhǎng)正則語(yǔ)言的生成。FA 擅長(zhǎng)正則語(yǔ)言的識(shí)別。正則表達(dá)式具有簡(jiǎn)單化和數(shù)學(xué)化的特點(diǎn)，更接近語(yǔ)言的集合表示和語(yǔ)言的計(jì)算機(jī)表示。1 單詞定義(正則文法,3型文法）定義：如：標(biāo)識(shí)符的文法定義I- aA|bA|zAA- aA|bA|zA|A- 0A|1A|9A|或用l代表字母，d代表數(shù)字則I-lAA-lA|dA|識(shí)別單詞的裝置：FA（finite automata） 2 正則語(yǔ)言的識(shí)別裝置-FA 為了構(gòu)造詞法分析器，要研究構(gòu)詞法、每種詞

8、類的結(jié)構(gòu)模式以及識(shí)別它的數(shù)學(xué)模型有窮自動(dòng)機(jī)FA。 FA的模擬程序可以作為詞法分析器的控制程序。(1) 有窮自動(dòng)機(jī)（FA）的三種表示形式(2) 根據(jù)正則文法來(lái)構(gòu)造FA(3) 編寫詞法分析程序（依據(jù)“描述模型”進(jìn)行系統(tǒng)實(shí)現(xiàn)）有窮自動(dòng)機(jī)FAa1a2a3a4ajan#把FA看作由一個(gè)讀頭和一個(gè)有窮狀態(tài)轉(zhuǎn)換器組成。開(kāi)始狀態(tài)后繼符號(hào)有窮狀態(tài)轉(zhuǎn)換讀頭輸入帶有窮自動(dòng)機(jī)FA（1）它可以從左至右從帶上一次讀一個(gè)字符， 每讀一個(gè)字符改變一次狀態(tài)；（2）在開(kāi)始讀字符前，F(xiàn)A處于開(kāi)始狀態(tài)；（3）有一些狀態(tài)指定為終止?fàn)顟B(tài)；（4）當(dāng)FA處于終止?fàn)顟B(tài)又準(zhǔn)備讀帶右邊的字符時(shí)，帶上的字符串就被FA識(shí)別或接受，或者說(shuō)，該串 L(F

9、A)。有窮自動(dòng)機(jī)FAFA 定義了正則語(yǔ)言集合。FA 對(duì)于上的任意串w，能夠判定它是可接受的還是不可接受的。若FA處于狀態(tài)qi，正在讀字符a，而狀態(tài)應(yīng)轉(zhuǎn)換為qj ，則（a） f (qi, a) = qj, f: 狀態(tài)轉(zhuǎn)換函數(shù)或映射（b） 狀態(tài)裝換圖，節(jié)點(diǎn)代表狀態(tài)，弧代表轉(zhuǎn)換，弧上符號(hào)代表輸入字符， ：開(kāi)始狀態(tài)， ：代表終止?fàn)顟B(tài)（c）矩陣方式 M qi, a = qj qiqjaMaqiqj（1）有窮自動(dòng)機(jī)的三種表示形式例： 給出識(shí)別語(yǔ)言 以i為首的i，d串 的FA的三種形式。解： FA Mii,dBA 狀態(tài) idFABBBB1狀態(tài)轉(zhuǎn)換矩陣f (A, i) = Bf (B, i) = Bf (B,

10、 d) = B(B為終止?fàn)顟B(tài))（1）有窮自動(dòng)機(jī)的三種表示形式例：識(shí)別語(yǔ)言 L = 以i為首的i、d串的FA的轉(zhuǎn)換規(guī)則 MidFq1q20q2q2q21q1iq2di FA 正則文法f(q1, i)=q2 q1 iq2f(q2, i)=q2 q2 iq2| dq2|f(q2, d)=q2 （ q2 為終態(tài)）（1）有窮自動(dòng)機(jī)的三種表示形式 圖 標(biāo)識(shí)符及無(wú)符號(hào)數(shù)的狀態(tài)轉(zhuǎn)換圖(a) 標(biāo)識(shí)符；(b) 無(wú)符號(hào)整數(shù)；(c) 無(wú)符號(hào)數(shù)有窮自動(dòng)機(jī)簡(jiǎn)介（*）在線性時(shí)間模型中, 認(rèn)為一次執(zhí)行可完全由狀態(tài)（或系統(tǒng)的事件）建模, 稱為一個(gè)執(zhí)行軌跡 (trace)。系統(tǒng)的行為就是這樣的執(zhí)行序列的集合。 由于序列的集合 是

11、一種形式語(yǔ)言, 這自然導(dǎo)致了使用自動(dòng)機(jī)用于系統(tǒng)的規(guī)范（定義）和驗(yàn)證。27狀態(tài)轉(zhuǎn)換圖顯示了一個(gè)由狀態(tài)、轉(zhuǎn)換組成的狀態(tài)機(jī)。 有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖說(shuō)明系統(tǒng)的動(dòng)態(tài)視圖。狀態(tài)圖強(qiáng)調(diào)一個(gè)對(duì)象按事件次序發(fā)生的行為。有窮自動(dòng)機(jī)簡(jiǎn)介（*）28有窮自動(dòng)機(jī)的一個(gè)實(shí)例（2） 根據(jù)正則文法來(lái)構(gòu)造FA已知： G = (VN，VT，P，S )是正則文法，不失一般性，假定規(guī)則是右線性，用文法的非終極符作為狀態(tài)，開(kāi)始符號(hào)作為開(kāi)始狀態(tài)。再增加一個(gè)新的符號(hào)R，作為終止?fàn)顟B(tài)。若文法中有：qiaqj 則 f(qi,a) = qj qj a 則 f(qj,a) = R S 則 S也作為終止?fàn)顟B(tài)例：(a) 文法定義 迭代.e+|-(b)

12、 正則式表示（簡(jiǎn)潔）dd*(.dd*|)(e(+|-|)dd*|)（2） 根據(jù)正則文法來(lái)構(gòu)造FA(C) FA：（識(shí)別）d.dNN1ON2N3N4N5ON6OOOOOOO空格deedd+/-l=:(l/d=dother=標(biāo)識(shí)符超前搜索識(shí)別PL/0 所有單詞的FAd.正則文法（無(wú)符號(hào)數(shù)）： NdN1N1dN1|.N2|eN4| N2dN3 N3dN3|eN4| N4dN5|+N6|-N6N5dN5| N6dN5 根據(jù)畫出的（識(shí)別單詞的）狀態(tài)轉(zhuǎn)換圖構(gòu)造詞法分析程序，每個(gè)狀態(tài)對(duì)應(yīng)一段程序，完成到達(dá)此狀態(tài)的工作；詞法分析程序的控制程序模擬狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換。 在識(shí)別標(biāo)識(shí)符的過(guò)程中，要把標(biāo)識(shí)符拼寫出來(lái)，

13、并和保留字區(qū)別開(kāi)來(lái)；在識(shí)別常數(shù)的過(guò)程中，要把它轉(zhuǎn)換成機(jī)器表示以作為屬性值。（3） 編寫詞法分析程序Start: getch;While (ch= ) do getch ; /*l濾掉無(wú)用的空格*/ case char of a.z: beginWhile letter or digit dobegin concat; getch end; /連接字符串 c:=reserve; /*查保留字表 */ if c=0 then return($ID,val) else return(c，-）end;（3） 編寫詞法分析程序0.9:begin While digit do begin /*concat

14、 連接字符串*/ concat; getch； end; Return($INT, val) end;3 編寫詞法分析程序+: Return($plus, _);-: Return($minus, _);): Return($rpar, _);:begin /*讀取下一個(gè)字符,查看這一字符是否為=,若是即為=,否則為= 0）anbmck| n, m, k = 0， SaS|B BbB|C CcC|四 自動(dòng)機(jī)（帶有空轉(zhuǎn)換的FA）確定化帶有空轉(zhuǎn)換的NFA的確定化算法： 由-NFA構(gòu)造等價(jià)的DFA的算法與不帶有空轉(zhuǎn)換的NFA確定化的算法類似，只是需要引進(jìn)狀態(tài)集的-閉包（-CLOSURE）的概念，并在

15、算法中，凡是涉及到狀態(tài)集時(shí)就用與它相對(duì)應(yīng)的-閉包代替。定義狀態(tài)集I 的空閉包：設(shè)I是一狀態(tài)集，C(I)是其空閉包（-closure(I)）， 1 若PI，則 PC(I)； 2 對(duì)于PI，若 f(P, )=Q，則QC(I)； 即從P出發(fā)，經(jīng)過(guò)任意條弧所能到達(dá)的任何狀態(tài)Q，都屬于C(I)。在確定化算法中，狀態(tài)集由它的閉包代替，即可消除轉(zhuǎn)換四 自動(dòng)機(jī)（帶有空轉(zhuǎn)換的FA）確定化有如下定理：對(duì)任何一個(gè)具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA N，一定存在一個(gè)不具有轉(zhuǎn)移的不確定的有窮自動(dòng)機(jī)NFA ，使得L(M)=L(N)。 NFAMabFSSAAA1 -NFA到DFA的確定化 實(shí)例SaAbDFAM abF SA

16、SAA1AA1122b1ab -NFA到DFA的轉(zhuǎn)化 實(shí)例NFA MabFSA，DABADBCCEDDAE1解： 該NFA M識(shí)別的語(yǔ)言是L（M）=(a|b)*abb ，確定化的DFA M的狀態(tài)轉(zhuǎn)換矩陣及狀態(tài)圖分別如下圖所示。 NFA M的狀態(tài)轉(zhuǎn)換矩陣BabESAbCbDaaDFA MabF 0 SADBADAD1 ABDBADACD2 ADBADAD3 ACDBADAED4 ADEBADAD1轉(zhuǎn)換后的 DFA M的狀態(tài)轉(zhuǎn)換矩陣NFA MabFSA，DABADBCCEDDAE1DFA MabF0 SADBADAD1 ABDBADACD2 ADBADAD3 ACDBADAED4 ADEBADAD

17、1轉(zhuǎn)換后的 DFA M的狀態(tài)圖3bb401aa2babbaa五 FA與正則文法的關(guān)系定理1：對(duì)任意的正則文法G=（ VN, VT, P, S），都存在一個(gè)有窮自動(dòng)機(jī)A，使得L(A)=L(G)定理2：對(duì)任一DFA(或NFA)，都存在一個(gè)正則文法G，使L(G)=L(A)合并：一文法G是正則的，當(dāng)且僅當(dāng)存在一個(gè)FA，使L(G)=L(M) x L(G)x L(M)五 FA與正則文法的關(guān)系（1）正則文法FA (見(jiàn)前述:本課件28頁(yè))（2）FA正則文法（VN，Vt ，P，S） 設(shè)FA M=(Q,q0, F) 對(duì)于 轉(zhuǎn)換函數(shù)(A, t) =B，可寫一產(chǎn)生式 AtB 對(duì)于可接受狀態(tài)z，增加一產(chǎn)生式z 此外：S=q0 VT =（FA的字母表）補(bǔ)充：左線性正則文法G構(gòu)造 FA M具體步驟：（1）對(duì)于 A-a的產(chǎn)生式，按歸約理解，句子中的第1個(gè)字符，都是用A-a的產(chǎn)生式進(jìn)行歸約的.對(duì)應(yīng)到FA中，F(xiàn)A從開(kāi)始狀態(tài)出發(fā)，讀到句子的第一個(gè)字符a,將它歸約為A。此時(shí)引用初態(tài) q, 定義為：f(q,a)=A.（2）對(duì)于 A-Ba的產(chǎn)生式，F(xiàn)A應(yīng)該在狀態(tài)B讀入 a,其狀態(tài)轉(zhuǎn)為A , 即 f(B,a)=A. 也可理解為在狀態(tài)B時(shí)，F(xiàn)A已將當(dāng)前句子處理過(guò)的前綴歸約成了B，此時(shí)它讀入 a時(shí)，要將Ba歸約為A。（3）按