第四章詞法分析

第四章詞法分析第1頁，共81頁，2023年，2月20日，星期三4.1詞法分析程序的設計回顧

什麼是詞法分析（lexicalanalysis）程序又稱詞法分析器或掃描器，主要功能是逐個讀入源程序字符并按照構詞規(guī)則切分成一系列單詞。單詞是語言中具有獨立意義的最小單位，包括保留字、標識符、運算符、標點符號和常量等。詞法分析是編譯過程中的一個階段，在語法分析前進行。也可以和語法分析結合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當前單詞供語法分析使用。第2頁，共81頁，2023年，2月20日，星期三詞法分析程序和語法分析程序的關系字符串源程序詞法分析

符號串源程序圖4.1a詞法分析單獨作為一遍

字符串源程序詞法分析器

語法分析器取符號送符號圖4.1b詞法分析作為語法分析子程序第3頁，共81頁，2023年，2月20日，星期三詞法分析程序的任務詞法分析程序的主要任務：掃描源程序，識別出具有獨立意義的單詞詞法分析程序的其他任務：濾掉空格，跳過注釋、換行符追蹤換行標志，將行號與出錯信息相聯(lián)系起來。宏展開，……第4頁，共81頁，2023年，2月20日，星期三詞法分析程序的輸出格式詞法分析的輸出常采用二元式：

（單詞類別，單詞自身的值）單詞類別通常用一個整數(shù)類碼或單詞記號表示，單詞記號比整數(shù)碼含義明確。若還需記錄單詞的一些其它屬性值:如標識符的類別、層次等，可將這些屬性統(tǒng)一放到符號表中，并將單詞的二元式表示為：（標識符，指向該標識符所在符號表中位置的指針）第5頁，共81頁，2023年，2月20日，星期三詞法分析程序的結構將詞法分析從語法分析部分獨立出來的原因使整個編譯程序的結構更簡潔、清晰、條例化改進編譯效率增加編譯系統(tǒng)的可移植性第6頁，共81頁，2023年，2月20日，星期三手工構造首先確定出能夠識別程序中單詞的確定的有窮自動機（DFA），然后可以采用直接編程的方法或者表驅動的方法來構造詞法分析器。借助相關工具的自動構造如：Lex編譯系統(tǒng)詞法分析程序的常用設計方法第7頁，共81頁，2023年，2月20日，星期三

多數(shù)程序設計語言的單詞的語法均可用正規(guī)文法來表示。回顧：正規(guī)文法(3型文法)：任一產(chǎn)生式的形式都為A→aB或A→a，其中A∈VN

，B∈VN

，a∈VT*正規(guī)文法描述的是VT上的正規(guī)集。例：程序設計語言中幾類單詞的描述規(guī)則：標識符、無符號整數(shù)、運算符…。（參見課本P52）4.2單詞的描述工具-正規(guī)式第8頁，共81頁，2023年，2月20日，星期三4.2單詞的描述工具-正規(guī)式正規(guī)式（regularexpression也叫正則表達式）正規(guī)式是定義正規(guī)集的數(shù)學工具，是說明單詞的模式(pattern)的一種表示法，用它描述單詞符號時一般比正規(guī)文法更簡潔。正規(guī)式和正規(guī)集(即其描述的語言）的定義可以用遞歸的形式給出。第9頁，共81頁，2023年，2月20日，星期三4.2單詞的描述工具-正規(guī)式正規(guī)式設∑是有窮字母表，并定義輔助字母表∑’={Φ,ε,|,.,*,(,)}1.ε,Φ都是∑上的正規(guī)式，它們所表示的正規(guī)集為{ε},Φ;2.任何a是一個正規(guī)式，若a∈∑，它所表示的正規(guī)集為{a}；3.如果R1和R2是正規(guī)式，其表示的正規(guī)集分別為L1和L2，則

1)正規(guī)式R1|R2或R1+R2表示的正規(guī)集為L1∪L2

2)正規(guī)式R1.R2或R1R2表示的正規(guī)集為L1L2

3)正規(guī)式{R1}或R1*表示的正規(guī)集為L1*

4)正規(guī)式(R)表示的正規(guī)集仍是L1，但調(diào)整優(yōu)先權，使括號內(nèi)的運算符優(yōu)先權高于括號外的。第10頁，共81頁，2023年，2月20日，星期三4.僅有有限次使用上述三步驟而定義的表達式才是∑上的正規(guī)式，僅有這些正規(guī)式表示的字集才是∑上的正規(guī)集。4.2單詞的描述工具-正規(guī)式注意：不要混淆Φ和ε，正則表達式ε描述的語言只含一個空字符串ε，而Φ表示的語言不含有任何字符串。

第11頁，共81頁，2023年，2月20日，星期三例4.2.1:令={a,b},則上的正規(guī)式和相應正規(guī)集為(1)a(2)ab(3)ab(4)(ab)(ab) (5)a

(6)(ab)(7)(ab)(aabb)(ab)(1){a}(2){a,b}(3){ab}(4){aa,ab,ba,bb}(5){,a,aa,……任意個a的串}(6){,a,b,aa,ab,bb……所有由a和b組成的串}(7)上所有含有兩個相繼的a或兩個相繼的b組成的串}第12頁，共81頁，2023年，2月20日，星期三例4.2.2:令={l，d},則上的正規(guī)式r=l(ld)定義的正規(guī)集為程序設計語言的單詞都能用正規(guī)式來定義。若兩個正規(guī)式e1,e2表示的正規(guī)集相同，則稱它們等價。記作:e1=e2

{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,即:字母(字母|數(shù)字),它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,即Pascal和多數(shù)程序設計語言允許的的標識符的詞法規(guī)則.第13頁，共81頁，2023年，2月20日，星期三正規(guī)式服從的代數(shù)運算規(guī)律：設r,s,t為正規(guī)式，則它們滿足如下運算規(guī)律：r|s=s|rr|(s|t)=(r|s)|t(rs)t=r(st)r(s|t)=rs|rt;(s|t)r=sr|tr:或的分配律r=r;r=r:是“連接”的恒等元素r|r=r:“或”的抽取律第14頁，共81頁，2023年，2月20日，星期三一個正規(guī)語言可用正規(guī)文法表示也可用正規(guī)式表示，兩者具有等價性。一般而言正規(guī)式在描述語言時比正規(guī)文法更為簡潔。正規(guī)文法和正規(guī)式的等價性例如，用正規(guī)文法表示標識符的文法規(guī)則如下：＜標識符＞

a|b|…|z|＜標識符＞a|＜標識符＞b|…|＜標識符＞z|＜標識符＞0|＜標識符＞1|…|＜標識符＞9而采用正規(guī)表達式則為：＜標識符＞=

(a|b|c|…|z){a|b|…|z|0|1|…|9}或簡寫成＜標識符＞=字母{字母|數(shù)字}第15頁，共81頁，2023年，2月20日，星期三將上的正規(guī)式r轉換成正規(guī)文法G=(VN,VT,S,P).

令VT=，產(chǎn)生式和VN按如下方法確定：選擇一非終結符S生成類似產(chǎn)生式的形式Sr，并將S定為文法G的識別符。若x,y是正規(guī)式，對形如Axy的正規(guī)式產(chǎn)生式，重寫成：AxB,By，B為新選的非終結符。對形如Ax*y的正規(guī)式，重寫成:AxB,Ay,BxB,By，B為新選的非終結符。對形如Ax|y的正規(guī)式，重寫成:Ax,Ay。不斷利用上述規(guī)則做變換，直到每個產(chǎn)生式都符合正規(guī)文法的形式即可。正規(guī)文法和正規(guī)式的等價性第16頁，共81頁，2023年，2月20日，星期三例4.2.3：將r=a(a|d)*轉換成相應的正規(guī)文法正規(guī)文法和正規(guī)式的等價性第17頁，共81頁，2023年，2月20日，星期三將正規(guī)文法轉換為正規(guī)式基本上是正規(guī)式到正規(guī)文法轉換過程的逆過程。可反復采用以下三條規(guī)則，直到只剩下一個開始符號定義的正規(guī)式為止。產(chǎn)生式AxB,By對應正規(guī)式A=xy;產(chǎn)生式AxA|y對應正規(guī)式A=x*y;產(chǎn)生式Ax,Ay對應正規(guī)式A=x|y;正規(guī)文法和正規(guī)式的等價性第18頁，共81頁，2023年，2月20日，星期三例4.2.4:

將G[S]轉換為正規(guī)式SaASaAaAAdAAaAd正規(guī)文法和正規(guī)式的等價性解：由文法G[S]得S=aA|aA=(aA|dA)|(a|d)則S=a(a|d)*(a|d)|a=a((a|d)*(a|d)|)=a(a|d)*第19頁，共81頁，2023年，2月20日，星期三4.3有窮自動機

有窮自動機(有限自動機)作為一種識別裝置，它能準確地識別正規(guī)集(即正規(guī)式所表示的集合)。有窮自動機為詞法分析程序的自動構造提供了有效的方法和工具。

有窮自動機分為兩類：確定的有窮自動機(DeterministicFiniteAutomata:DFA)

不確定的有窮自動機(NondeterministicFiniteAutomata:NFA)第20頁，共81頁，2023年，2月20日，星期三4.3關于有窮自動機將主要討論如下問題確定的有窮自動機DFA不確定的有窮自動機NFANFA的確定化DFA的最小化第21頁，共81頁，2023年，2月20日，星期三一、確定的有窮自動機DFADFA定義:一個確定的有窮自動機（DFA）M是一個五元組:M=(K,Σ,f,S,Z),其中1.K是一個有窮集，它的每個元素稱為一個狀態(tài)；2.Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以Σ也稱為輸入符號表；第22頁，共81頁，2023年，2月20日，星期三DFA定義(續(xù)):3.f是轉換函數(shù)，是在K×Σ→K上的單值映射，即如存在f(ki,a)=kj,(ki∈K,kj∈K)，則當前狀態(tài)為ki且輸入符為a時，將轉換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4.S∈K是唯一的一個初態(tài)；5.ZK是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。一、確定的有窮自動機DFA第23頁，共81頁，2023年，2月20日，星期三一、確定的有窮自動機DFA例4.3.1:DFAM=（{S，U，V，Q}，{a，b}，f，S，{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q第24頁，共81頁，2023年，2月20日，星期三上例中DFA的狀態(tài)圖表示bSUVQaaaba，bb一、確定的有窮自動機DFA第25頁，共81頁，2023年，2月20日，星期三上例中DFA的矩陣表示字符狀態(tài)0001一、確定的有窮自動機DFA第26頁，共81頁，2023年，2月20日，星期三概念：∑*上的符號串t被DFAM接受一、確定的有窮自動機DFA定義1:對∑*中的任何符號串t，若存在一條從初態(tài)結點某一終態(tài)結點的道路，且這條道路上所有弧連接成的符號串等于t，則稱t可為DFAM所接受，若M的初態(tài)同時又是終態(tài)結點，則空字可為M所接受。定義2:若t∈∑*,f(S,t)=P，其中S為DFAM的開始狀態(tài),P∈Z,Z為終態(tài)集,則稱t可為M所接受(識別)。DFAM所能接受的符號串的全體記為L(M)。DFA的確定性表現(xiàn)在f:K×K是一個單值函數(shù)。第27頁，共81頁，2023年，2月20日，星期三一個輸入符號串t(表示為t1tx),其中t1∈∑,tx∈∑*,則t在DFAM上運行的定義為:f(Q,t1tx)=f(f(Q,t1),tx)

其中Q∈K,f(Q,)=Q。一、確定的有窮自動機DFA

概念：∑*上的符號串t被DFAM上運行上一個符號串集V是正規(guī)的，當且僅當存在一個上的DFAM

，使得V=L(M)。第28頁，共81頁，2023年，2月20日，星期三一、確定的有窮自動機DFA例4.3.2:證明t=baab被下圖的DFA所接受bSUVQabba,baaf（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)。得證。第29頁，共81頁，2023年，2月20日，星期三DFA行為的程序模擬.DFAM=（K，Σ，f，S，Z）的行為的模擬程序K:=S；c:=getchar;whilec<>eofdo{K:=f(K,c);c:=getchar;};ifKisinZthenreturn(‘yes’)elsereturn(‘no’)一、確定的有窮自動機DFA第30頁，共81頁，2023年，2月20日，星期三二、不確定的有窮自動機NFA

NFA定義:NFAN=(K,,f,S,Z)，其中K為有窮狀態(tài)集，為有窮輸入字母表，f為K

到K的子集的映射，SK是一個非空初態(tài)集，ZK為終態(tài)集。NFA與DFA的區(qū)別主要有:NFA中狀態(tài)轉換函數(shù)為多值函數(shù)。NFA中起始狀態(tài)可以有多個，但從正規(guī)文法出發(fā)構造的NFA起始狀態(tài)是唯一的。第31頁，共81頁，2023年，2月20日，星期三二、不確定的有窮自動機NFA例4.3.3:NFAN=({S,P,Z},{0,1},f,{S,P},{Z})其中f（S，0）={P}f（S，1）={S，Z}f（P，1）={Z}f（Z，0）={P}f（Z，1）={P}SPZ00,1111狀態(tài)圖表示第32頁，共81頁，2023年，2月20日，星期三矩陣表示簡化為二、不確定的有窮自動機NFA第33頁，共81頁，2023年，2月20日，星期三

類似DFA,NFAN=(K，，f，S，Z)也有如下定義：符號串t在NFAN上運行一個輸入符號串t(將它表示成Tt1的形式,其中T∈∑,t1∈∑*)在NFAN上運行的定義為：

f(Q,Tt1)=f(f(Q,T),t1)其中Q∈K.符號串t被NFAN接受若f(S0,t)=P,其中t∑*,S0∈S,PZ,則稱t為NFAN所接受(識別)二、不確定的有窮自動機NFA第34頁，共81頁，2023年，2月20日，星期三

符號串t被NFAN接受也可以這樣理解對于任何一個符號串t(t∈∑*)，若存在一條從某一初態(tài)到某一終態(tài)的道路，且這條道路上所有弧的標記字依序連接成的串(不計ε弧)等于t，則稱t為NFAN所接受。二、不確定的有窮自動機NFA

有了上述定義后，實際上也就是對NFA的轉換函數(shù)

f進行了如下擴充:

f:KK的子集

f:K*K的子集第35頁，共81頁，2023年，2月20日，星期三二、不確定的有窮自動機NFA例4.3.4:下列符號串哪些可以被圖中NFA所接受？11110100010001100第36頁，共81頁，2023年，2月20日，星期三二、不確定的有窮自動機NFA例4.3.4:下列符號串哪些可以被圖中NFA所接受？11110100010001100第37頁，共81頁，2023年，2月20日，星期三

若將NFAN所能接受的符號串的全體記為L(N)，則有如下結論：對每個NFAN存在著與之等價的DFAM，使得L(M)=L(N)。并且最小的DFAM是唯一的。將NFA轉換成等價的DFA的算法---子集法。二、不確定的有窮自動機NFA第38頁，共81頁，2023年，2月20日，星期三有關狀態(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)都屬于ε-closure(I)。2.狀態(tài)集合I的a弧轉換，記為move(I,a)，是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。三、NFA的確定化

第39頁，共81頁，2023年，2月20日，星期三12534687aaa三、NFA的確定化

有關狀態(tài)集合I的運算實例計算下列各式的值1)move({1,2},a)2)-closure({5,3,4})運算結果：1)={5,3,4};2)={2,3,4,5,6,7,8};例4.3.5:若I1={1},則-closure(I1)={1,2};move(I1,a)={4,5};-closure(move({1,2},a))第40頁，共81頁，2023年，2月20日，星期三三、NFA的確定化

子集法:

假設NFAN=(K,,f,K0,Kt)，按如下方法可構造一個DFAM=(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]；第41頁，共81頁，2023年，2月20日，星期三2M和N的輸入字母表是相同的，即是；3轉換函數(shù)是這樣定義的： d([S1,S2,...

Sj],a)=[R1,R2,...

,Rt]

其中[R1,R2,...

,Rt]=

-closure(

move([S1,S2,...

Sj],a))

4S0=-closure(K0)為M的開始狀態(tài)；5St={[Si,Sk,...,

Se],其中[Si,Sk,...,

Se]S

且{Si,Sk,,...,

Se}Kt}三、NFA的確定化第42頁，共81頁，2023年，2月20日，星期三構造NFAN中狀態(tài)K的子集的算法：

假定所構造的子集族為CS，即CS=(T1,T2,,...

Ti)，其中T1,T2,...,Ti為狀態(tài)K的子集，則其構造步驟如下：

1.令-closure(K0)為CS中唯一成員，且它是未被標記的。2.while(CS中存在尚未被標記的子集T)do{標記T；

for每個輸入字母ado {U:=-closure(move(T,a))；

ifU不在CS中then

將U作為未標記的子集加在CS中

} }三、NFA的確定化

第43頁，共81頁，2023年，2月20日，星期三例4.3.6:將下圖NFAN=(K,,f,K0,Kt)轉換為等價的DFAM其中M=(S,,d,S0,St)。4f35621iaaaabbbb三、NFA的確定化第44頁，共81頁，2023年，2月20日，星期三表1NFA狀態(tài)子集的構造結果4f35621iaaaabbbb第45頁，共81頁，2023年，2月20日，星期三aDECBFFAbaaaaabbbbbabG三、NFA的確定化轉換為DFA后的狀態(tài)圖第46頁，共81頁，2023年，2月20日，星期三四、DFA的化簡結論：對于任何給定的DFA，都存在一個與之等價的最少狀態(tài)DFA，并且該最少狀態(tài)DFA是唯一的。最少狀態(tài)DFA應滿足：

1).沒有多余狀態(tài)；2).沒有等價狀態(tài)。多余狀態(tài):從自動機的開始狀態(tài)出發(fā)，任何輸入串也不能到達的狀態(tài)；或者是沒有通路到達終態(tài)的狀態(tài)。兩個狀態(tài)s和t等價是指它們具備以下特性:一致性(兼容性):即兩狀態(tài)同是終態(tài)或同是非終態(tài)蔓延性:對所有輸入符號，狀態(tài)s和t必須轉換到等價的狀態(tài)里?；蛘哒f從兩狀態(tài)出發(fā)所接受的符號串集合相同。第47頁，共81頁，2023年，2月20日，星期三四、DFA的化簡例4.3.7:判斷下圖中那些狀態(tài)是多余狀態(tài)。012345bbbaa0234bba刪除多余狀態(tài)后的狀態(tài)圖

第48頁，共81頁，2023年，2月20日，星期三四、DFA的化簡例4.3.8:判斷下圖中那些狀態(tài)是等價狀態(tài)。解：因為f(1,a)=3，f(2,a)=3，所以狀態(tài)1和狀態(tài)2是等價的02134abaab4第49頁，共81頁，2023年，2月20日，星期三上圖DFA中D、E、F、G為等價狀態(tài)。四、DFA的化簡例4.3.9:判斷下圖中那些狀態(tài)是等價狀態(tài)。aDECBFFAbaaaaabbbbbabG第50頁，共81頁，2023年，2月20日，星期三結論：一個DFA可以通過消除多余狀態(tài)和合并等價狀態(tài)而轉換成一個與之等價的最小DFA。

DFA的最小化算法（分割法）算法的核心思想：把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的。算法具體步驟：以DFAM=(K,∑,f,k0,kt)的最小化為例

1.構造自動機的初始劃分:終態(tài)集kt和非終態(tài)集K-kt兩組四、DFA的化簡第51頁，共81頁，2023年，2月20日，星期三2.對各狀態(tài)集按下面方法進行劃分，直到所有狀態(tài)集合不再產(chǎn)生新的劃分為止。設第m次劃分將K分成n個狀態(tài)集合(K=S1∪S2…∪Sn)。對狀態(tài)集合Si中的各狀態(tài)逐一檢查，設q1,q2是狀態(tài)集合Si中的兩個狀態(tài)，對任意輸入符號a，有f(q1,a)=S’,f(q2,a)=S”，若狀態(tài)S’和S”不屬于同一狀態(tài)集，則將q1和q2分為兩個集合。3.重復第2步，直到所有狀態(tài)集合都不能劃分。4.將每個狀態(tài)集中的等價狀態(tài)合并成一個狀態(tài)。5.刪除多余狀態(tài)。四、DFA的化簡第52頁，共81頁，2023年，2月20日，星期三四、DFA的化簡對S1={0,1,2}劃分:因為f(0,a)=1,f(1,a)=3,f(2,a)=1,故1,2不屬于同一狀態(tài)集,所以將S1分成S3={0,2},S4={1}對S3={0,2}劃分:因為f(0,b)=2,f(2,b)=4,故S3應分成S5={0},S6={2}對S2={3,4}劃分:因為f(3,a)=3,f(4,a)=3,f(3,b)=4,f(4,b)=4,故3,4屬于同一狀態(tài)集,所以S2不能劃分,也就是說狀態(tài)3和4等價。至此，不再能繼續(xù)劃分01234bbbaaabaab例4.3.10:對下圖DFA進行化簡。解：首先將狀態(tài)集合分成非終止狀態(tài)集S1和終止狀態(tài)集S2，即S1={0,1,2};S2={3,4}第53頁，共81頁，2023年，2月20日，星期三四、DFA的化簡最終得到不能劃分的狀態(tài)集有:

S2={3,4},S4={1},S5={0},S6={2}每個狀態(tài)集留一個狀態(tài)得:S2={3},S4={1},S5={0},S6={2}所以化簡后的DFA如下圖所示0123bbbaaaab

化簡后的DFA第54頁，共81頁，2023年，2月20日，星期三四、DFA的化簡∏0:{A,B,C},{D,E,F,G}∏1:{A,B,C}

∏2:

a{A,C},{B}{D,E,F,G}b{A},{C}aDCBAaaabbbb例4.3.11:對例4.3.9的DFA進行化簡。至此，不能再進行劃分，所得狀態(tài)集為{A},{S},{B},{C,D,E,F}，每個狀態(tài)集留一個狀態(tài)后得到化簡后的DFA如右圖所示DECBFGAbaaaaaabbbbbba第55頁，共81頁，2023年，2月20日，星期三正規(guī)式和有窮自動機的等價性表現(xiàn)在以下兩個方面：

1.對于∑上的一個正規(guī)式R，可以構造一個∑上的NFAN,使的L(N)=L(R)。2.對于∑上的一個NFAN，可以構造一個∑上的正規(guī)式R,使得L(R)=L(N)。4.4正規(guī)式和有窮自動機的等價性第56頁，共81頁，2023年，2月20日，星期三4.4.1為∑上的正規(guī)式R構造相應的NFAM“語法制導”構造方法首先將正規(guī)式分解成一系列子表達式，然后按下列規(guī)則來構造NFAM：1)基本正規(guī)式Φ,ε,a(a∈∑)對應的NFA為：圖4.4.1Φ,ε,a對應的狀態(tài)轉換圖

SSSaεS1ZS1ZS1Z第57頁，共81頁，2023年，2月20日，星期三2)連接:設R1和R2都是正規(guī)式，則構造與正則表達式R1R2等價的NFA如圖4.4.2：

4.4.1為∑上的正規(guī)式R構造相應的NFAM圖4.4.2R1.R2的狀態(tài)轉換圖3)選擇:設R1和R2都是正規(guī)式，則構造與正則表達式R1|R2等價的NFA如圖4.4.3：

圖4.4.3R1|R2的狀態(tài)轉換圖SS1R1R2

SS1S1R1

R2

S1ZS1ZSS1R1|R2

SS1R1

R2

S1ZS1Z第58頁，共81頁，2023年，2月20日，星期三4.4.1為∑上的正規(guī)式R構造相應的NFAM4)重復:設R是正規(guī)式，則構造與正規(guī)式R*等價的NFA如圖4.4.4

圖4.4.4R*的狀態(tài)轉換圖

對于任何正規(guī)式,都可根據(jù)上述規(guī)則構造出等價的NFA

SS1R*

SS1S1ε

ε

RS1ZS1Z第59頁，共81頁，2023年，2月20日，星期三4.4.1為∑上的正規(guī)式R構造相應的NFAM例4.4.1構造出與正規(guī)式R=(a)*(ε|b)(a|b)*等價的NFA。解：設初始狀態(tài)為0，目標狀態(tài)為1，將整個正則表達式(a)*(ε|bb)(a|b)*

看成一個整體,則狀態(tài)圖如圖4.4.5所示01(a)*(ε|bb)(a|b)*圖4.4.5正規(guī)式到NFA轉換圖1

因R由(a)*,(ε|bb),(a|b)*連接而成，故展開連接后如圖4.4.6

02(a)*31ε|bb

(a|b)*

圖4.4.6正規(guī)式到NFA轉換圖2第60頁，共81頁，2023年，2月20日，星期三4.4.1為∑上的正規(guī)式R構造相應的NFAM將重復展開后如圖4.4.7所示

02ε31ε|bb

a|b

45εεa

ε圖4.4.7正規(guī)式到NFA轉換圖3將選擇展開后，最終得到的NFA狀態(tài)圖如圖4.4.8所示

圖4.4.8正規(guī)式到NFA轉換圖4

02ε31ε

a45εεa

ε6b

b

b第61頁，共81頁，2023年，2月20日，星期三例4.4.2:構造正規(guī)式(0|1)*(000|111)(0|1)*對應的NFA，并對其進行化簡。第62頁，共81頁，2023年，2月20日，星期三4.4.1將NFAM變?yōu)橄鄳恼?guī)式R由NFAM構造正規(guī)式相對較容易，處理方法與根據(jù)正規(guī)式構造NFAM的方法互逆。具體如下:1

添加兩個新的結點S和T，將S與NFAM上的所有初態(tài)結點相連，將T與所有終態(tài)結點相連，所有連接弧線上均標記為ε，從而使NFAM只有一個初態(tài)S和一個終態(tài)T。2逐步去掉NFAM中的結點，直到只剩下結點S和T。在去掉結點的過程中，逐步用正則表達式來標記弧線。去掉結點的規(guī)則如下:①連接：設R1和R2都是基本正則表達式，去掉結點，用弧線直接連接結點1和3，弧線上標記R1R2，如圖4.4.9所示:

13R1R2

123R1

R2

圖4.4.9由NFA構造正則表達式R1R2

第63頁，共81頁，2023年，2月20日，星期三4.4.1將NFAM變?yōu)橄鄳恼?guī)式R②選擇:設R1和R2都是正規(guī)式，去掉標記為R1和R2的弧線并用一根弧線直接連接結點1和2，弧線上標記R1|R2。③重復:設R是正規(guī)式，則構造與R*等價的NFA如圖4.4.11

圖4.4.10由NFA構造正規(guī)式R1|R2

12R1|R2

12R1

R2

13R*

123ε

ε

R圖4.4.11由NFA構造正規(guī)式R*

例題4.4.1的逆過程即可作為此處實例來學習第64頁，共81頁，2023年，2月20日，星期三4.5

正規(guī)文法和有窮自動機的等價性從正規(guī)文法G直接構造一NFAN取N的字母表和G的終結符集相同。為G的每個非終結符生成N中的一狀態(tài)，G的開始符對應N的開始狀態(tài)。增加一個新狀態(tài)Z作為NFA的終態(tài)。對G中形如AtB的規(guī)則，構造一轉換函數(shù)f(A,t)=B對G中形如At的規(guī)則，構造一轉換函數(shù)f(A,t)=Z反復使用上述規(guī)則對文法G中的規(guī)則進行替換即可得到等價的NFAN。第65頁，共81頁，2023年，2月20日，星期三4.5

正規(guī)文法和有窮自動機的等價性例題1：第66頁，共81頁，2023年，2月20日，星期三從NFAN構造正規(guī)文法G對轉換函數(shù)f(A,t)=B，可寫一產(chǎn)生式AtB對可接受狀態(tài)Z，增加一產(chǎn)生式Zε有窮自動機的初態(tài)對應文法開始符，字母表為文法的終結符集。4.5

正規(guī)文法和有窮自動機的等價性第67頁，共81頁，2023年，2月20日，星期三例題2：4.5

正規(guī)文法和有窮自動機的等價性第68頁，共81頁，2023年，2月20日，星期三4.6

詞法分析程序的構造根據(jù)DFA構造詞法分析程序的方法直接編程的方法表驅動的實現(xiàn)方法借助自動生成器Lex的構造方法第69頁，共81頁，2023年，2月20日，星期三1.

直接編程的詞法分析器直接編程的詞法分析器是將DFA識別過程轉化為程序，即用程序來模擬DFA的行為?？砂聪铝胁襟E將DFA轉換成程序流程圖：1)初始狀態(tài)對應程序的開始；2)

終止狀態(tài)對應程序的結束3)

狀態(tài)轉移對應條件語句或分支選擇語句；4)

狀態(tài)圖的環(huán)對應程序中循環(huán)語句；5)

終態(tài)返回時，應滿足最長匹配原則。4.6.1根據(jù)DFA構造詞法分析程序的方法第70頁，共81頁，2023年，2月20日，星期三4.6.1根據(jù)DFA構造詞法分析程序的方法這種方法適合手工實現(xiàn)，編寫出的詞法分析程序比較精簡，分析速度快。但這種詞法分析程序與要識別的語言單詞密切有關，通過程序的控制流轉移來完成對輸入字符的響應，程序中的每一條語句都與要識別的單詞符號有關，一但語言的單詞符號集發(fā)生變化，則要重新編寫程序。故這種方法僅適合編寫比較簡單的詞法分析程序。

第71頁，共81頁，2023年，2月20日，星期三4.6.1根據(jù)DFA構造詞法分析程序的方法2.表驅動的詞法分析程序

表驅動的詞法分析程序的模型如圖4.6.1所示。它由輸入字符序列、分析表和控制程序組成。分析表就是DFA的狀態(tài)轉換矩陣，如圖4.6.2?？刂瞥绦蛴袃蓚€參數(shù)，一個參數(shù)接受掃描的字符a，另一個參數(shù)為DFA的狀態(tài)i。輸入字符序列分析表控制程序圖4.6.1表驅動的詞法分析程序的模型

Σ狀態(tài)01S*BAACSBSCCAB圖4.6.2分析表

第72頁，共81頁，2023年，2月20日，星期三4.6.1根據(jù)DFA構造詞法分析程序的方法

其控制程序的算法是：1)

在輸入字符序列后面加一個字符‘#’，叫結束符。將掃描指針設在輸入序列的最左端，狀態(tài)參數(shù)i設為開始狀態(tài)。2)

掃描下一字符a，如果是結束符‘#’，則停止；否則，根據(jù)狀態(tài)參數(shù)i和輸入的字符a查分析表，將狀態(tài)參數(shù)i設為查分析表（i，a）后得到的狀態(tài)。3)

如果i是終態(tài)，則表示識別出一個單詞轉到4；否則轉到2。4)處理識別出的單詞，輸出單詞符號。狀態(tài)參數(shù)i設為開始狀態(tài)，轉到2。第73頁，共81頁，2023年，2月20日，星期三4.6.1根據(jù)DFA構造詞法分析程序的方法表驅動的詞法分析程序是根據(jù)分析表的內(nèi)容進行操作，與要識別的單詞符號無關,是一種典型的數(shù)據(jù)與操作分離的工作模式。構造不同的詞法分析程序實質上是構造不同的分析表，而控制程序是不變的。這為詞法分析程序的自動生成提供了極大的方便。表驅動的詞法分析程序相對直接編程方法來說，程序較復雜。由于在工作中需要查表確定分析動作，因此分析速度也慢一些。

第74頁，共81頁，2023年，2