詞法分析及詞法分析程序

詞法分析及詞法分析程序第1頁(yè)，共54頁(yè)，2023年，2月20日，星期四設(shè)計(jì)掃描器應(yīng)注意的問(wèn)題詞法分析（3型）語(yǔ)法分析（2型）單詞的(Class,Value)二元組表示標(biāo)識(shí)符的長(zhǎng)度限制和按“盡可能長(zhǎng)”的識(shí)別策略超前搜索與回退<,<=,<<,<<=程序3-1輸入緩沖注釋與空白的刪除第2頁(yè)，共54頁(yè)，2023年，2月20日，星期四狀態(tài)轉(zhuǎn)換圖有向圖結(jié)點(diǎn)表示狀態(tài)一個(gè)初態(tài)，箭頭指示若干個(gè)終態(tài)，雙圓圈指示邊表示轉(zhuǎn)移邊上的字符表示轉(zhuǎn)移時(shí)應(yīng)滿足的條件字符串的識(shí)別0132abcdd第3頁(yè)，共54頁(yè)，2023年，2月20日，星期四右線性文法=>狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一右線性文法,令|VN|=K，1)則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài).2)VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài)

2.1)G的開(kāi)始符S為初態(tài)狀態(tài)3)終止?fàn)顟B(tài),用F(VN)標(biāo)記F是新加(狀態(tài)）節(jié)點(diǎn)第4頁(yè)，共54頁(yè)，2023年，2月20日，星期四右線性文法=>狀態(tài)轉(zhuǎn)換圖aA->aBABA->aAFaA->ε消除ε，重用上述規(guī)則AF[other]A若A為起始符（G[A]）A第5頁(yè)，共54頁(yè)，2023年，2月20日，星期四產(chǎn)生式的消除SAXFabc[other]YeSAXFabcYeS->aAA->b|bX

X->c|eYS->aAA->bXX->c|ε|eY第6頁(yè)，共54頁(yè)，2023年，2月20日，星期四狀態(tài)圖=>右線性文法文法G[0]0->a1S->aA1->d1A->dA1->bA->b0->cS->c0->c2S->cB，2有出弧2->dB->d0132abcdd第7頁(yè)，共54頁(yè)，2023年，2月20日，星期四左線性文法=>狀態(tài)轉(zhuǎn)換圖設(shè)G=(VN,VT,P,S)是一左線性文法,令|VN|=K，1)則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài).2)VN中的每個(gè)符號(hào)分別表示K個(gè)狀態(tài)

2.1)G的開(kāi)始符S為終止?fàn)顟B(tài)3)起始狀態(tài),用R(VN)標(biāo)記R是新加(狀態(tài)）節(jié)點(diǎn)第8頁(yè)，共54頁(yè)，2023年，2月20日，星期四左線性文法=>狀態(tài)轉(zhuǎn)換圖aA->BaBAA->ε的消除消除ε，重用上述規(guī)則RA[other]若A為起始符（G[A]）AA->aRAa不存在這種轉(zhuǎn)換第9頁(yè)，共54頁(yè)，2023年，2月20日，星期四狀態(tài)圖=>左線性文法文法G[3]1->aAa1->1dAAd3->1bSAb2->cBc3->2dSBd0132abcdd第10頁(yè)，共54頁(yè)，2023年，2月20日，星期四狀態(tài)矩陣狀態(tài)矩陣Bij=B[Si,aj]=Sk當(dāng)前狀態(tài)，掃視字符，語(yǔ)義動(dòng)作，后續(xù)狀態(tài)程序3-2第11頁(yè)，共54頁(yè)，2023年，2月20日，星期四識(shí)別無(wú)符號(hào)數(shù)的狀態(tài)矩陣第12頁(yè)，共54頁(yè)，2023年，2月20日，星期四語(yǔ)義動(dòng)作中的返回值ICON、FCON分別為整型數(shù)、浮點(diǎn)型數(shù)的值；一般說(shuō)來(lái)，無(wú)符號(hào)數(shù)具有形式dmdm-1…d0.d-1…d-nEdd

即dmdm-1…d0d-1…d-n*10^(dd-n);程序3-3關(guān)于狀態(tài)無(wú)符號(hào)數(shù)識(shí)別矩陣第13頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA的形式定義DFA:DeterministicFiniteAutomata一個(gè)DFAM定義為M=(K,,f,S0,Z)，其中1)K={狀態(tài)i}2)=字母表，即{輸入字符i}3)f:K×->K，f為函數(shù)，表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)，如：f(p,a)=q,p,qK,a4)S0K，S0為初態(tài)5)ZK，且Z，Z為終態(tài)集合第14頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA例子0132abcdd左側(cè)的狀態(tài)圖，在數(shù)學(xué)上稱作DFA，其形式化定義為M=(K,,f,S0,Z)K={0,1,2,3}={a,b,c,d}

源狀態(tài)輸入目的狀態(tài)0a10C21d11b32d3f:

S0=0Z={2,3}

第15頁(yè)，共54頁(yè)，2023年，2月20日，星期四函數(shù)f的推廣定義f^

f^:K×*->K，表示某狀態(tài)接受一個(gè)字母串（而不是一個(gè)字母）所到達(dá)的狀態(tài)，f^的定義依賴于f的定義，f^遞歸定義如下：1）f^(p,)=p,ifpK，即任意一狀態(tài)p接受（串長(zhǎng)為0）的輸入，狀態(tài)不變2）f^(p,aw)=f^(f(p,a),w),ifpK,a,w*第16頁(yè)，共54頁(yè)，2023年，2月20日，星期四函數(shù)f的推廣定義f^:例子對(duì)于x=adb,x*，那么從狀態(tài)0可以遷移到的狀態(tài)p可以這樣求出：P=f^(0,adb)=f^(f(0,a),db)=f^(1,db)=f^(f(1,d),b)=f^(1,b)=f^(f(1,b),)=f^(3,)=30132abcdd因?yàn)閺某鯌B(tài)0接受輸入字母串a(chǎn)db后，遷移到f^(0,adb)=3Z，所以adb為DFA所識(shí)別

第17頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA所識(shí)別的語(yǔ)言令M為一DFA，我們：定義L(M)={x|f(S0,x)Z,x*}L(M)稱為DFAM所識(shí)別的語(yǔ)言有定理：L(M)=L(G)，其中M為一DFA，G為一正規(guī)文法第18頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA關(guān)鍵特征狀態(tài)遷移映射f是入射函數(shù)即f(x)f(y)蘊(yùn)含xy即對(duì)任意狀態(tài)結(jié)點(diǎn)p，其出弧上的字母各不相同且不為從狀態(tài)圖角度，如出現(xiàn)下述情況的狀態(tài)結(jié)點(diǎn)，則不是DFA（而是NFA）PQNaaQNPQPQWhy?第19頁(yè)，共54頁(yè)，2023年，2月20日，星期四NFA的形式定義一個(gè)NFAM定義為M=(K,,f,S0,Z)，除f外其余成員與DFA相同，f定義為

f:K×->(K)，其中(K)為集合K的冪集合，即有|(K)|=2^|K|f表示某狀態(tài)接受某個(gè)字母所到達(dá)的狀態(tài)集合，如：f(p,a)={q,m}p,q,mK,a第20頁(yè)，共54頁(yè)，2023年，2月20日，星期四映射f的推廣定義f^f^:(K)×*->(K)，表示某狀態(tài)集合接受一個(gè)字母串（而不是一個(gè)字母）所到達(dá)的狀態(tài)集合，f^遞歸定義如下(依賴于f)：f^({p},)={p}f^({p},a)={p1,p2,...}iff(p,a)={p1,p2,…}iff(p,a)=f^({p},aw)=f^(f^({p},a),w)其中，p,p1,p2K,a,w*屬于什么？第21頁(yè)，共54頁(yè)，2023年，2月20日，星期四NFA所識(shí)別的語(yǔ)言令N為一NFA，我們：定義L(N)={x|f(S0,x)Z,x*}L(N)稱為NFAN所識(shí)別的語(yǔ)言有定理：L(N)=L(M)=L(G)，其中N為一NFA，M為一DFA，G為一正規(guī)文法第22頁(yè)，共54頁(yè)，2023年，2月20日，星期四NFA例子–寫狀態(tài)遷移表fSABCabaaa,bba為什么是NFA源狀態(tài)輸入目的狀態(tài)集合->Sa{A,C}Aa{A,C}Ab{A,B}BaABbC[C]x對(duì)每狀態(tài)結(jié)點(diǎn)，按出弧上的字母寫出狀態(tài)遷移表C行可以不填f:K×->(K)第23頁(yè)，共54頁(yè)，2023年，2月20日，星期四NFA例子–接受串源狀態(tài)輸入目的狀態(tài)集合->Sa{A,C}Aa{A,C}Ab{A,B}BaABbC[C]xf:K×->(K)當(dāng)前狀態(tài)余留輸入后續(xù)狀態(tài)選擇狀態(tài)SababbA,CAorC?注意，NFA識(shí)別輸入符號(hào)串時(shí)有一個(gè)試探過(guò)程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了NFA的效率。解決辦法？第24頁(yè)，共54頁(yè)，2023年，2月20日，星期四NFA與DFA的等價(jià)性定理3.1

對(duì)于字母表上的任一NFAN，必存在與M等價(jià)的DFAM，使L(N)=L(M)

有了該定理，為提高NFA識(shí)別字符串的效率提供了tips：將NFA轉(zhuǎn)換為DFA，即NFA的確定化基本idea:DFA的f:K×->KNFA的f:K×->(K)，將其改造為

f’:(K)×->(K)，并證明f’是入射函數(shù)且f’^接收的串與f^接收的串相同第25頁(yè)，共54頁(yè)，2023年，2月20日，星期四例子S0S1abba,bq0q2a,babq1b第26頁(yè)，共54頁(yè)，2023年，2月20日，星期四帶有動(dòng)作的NFA例子

abcS0{S0}{S1,S2}S1{S1,S3}S2{S2}{S3}S3

bS0S1S3aS2cb第27頁(yè)，共54頁(yè)，2023年，2月20日，星期四帶有動(dòng)作的NFA-閉包-closure(S0)={S0,S1,S2,S3}……f^(S,)=-closure(S)f^(S,wa)=-closure(f(f^(S,w),a))f(q,)通常不等于f^(q,)f(S0,)f^(S0,)第28頁(yè)，共54頁(yè)，2023年，2月20日，星期四帶有動(dòng)作的NFA的確定化1)令K’={-closure(S0)}(給出M’的初態(tài)q0)2)對(duì)于K’中任一尚未標(biāo)記的狀態(tài)qi={Si1,Si2,…,Sim}，SikK，作2.1)標(biāo)記qi2.2)對(duì)于每個(gè)aΣ，置T=f({Si1,Si2,…,Sim},a)qj=-closure(T)2.3)若qj不在K’中，則將qj作為一個(gè)未加標(biāo)記的狀態(tài)添加到K’中，且把狀態(tài)轉(zhuǎn)移添加到M’。3)重復(fù)進(jìn)行步驟2)，直到K’中不再含有未標(biāo)記的狀態(tài)為止，對(duì)于由此構(gòu)造的K’，我們把那些至少含有一個(gè)Z中的元素的qi作為M’的終態(tài)。第29頁(yè)，共54頁(yè)，2023年，2月20日，星期四S0S1S3aS2cbb第30頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA狀態(tài)數(shù)最小化可區(qū)分狀態(tài)ABa1a2ana1a2狀態(tài)A,B被某一輸入串w=a1a2..an所區(qū)分，指1）從其中一個(gè)狀態(tài)出發(fā)讀入w，到達(dá)終態(tài)，2）而從另一個(gè)狀態(tài)出發(fā)進(jìn)入非終態(tài)第31頁(yè)，共54頁(yè)，2023年，2月20日，星期四可區(qū)分狀態(tài)的遞歸定義在一個(gè)DFA中，狀態(tài)A與狀態(tài)B可區(qū)分：1）A是終止?fàn)顟B(tài)，B是非終止?fàn)顟B(tài) 或B是終止?fàn)顟B(tài)，A是非終止?fàn)顟B(tài)2）對(duì)于字母a，有f(A,a)=C,f(B,a)=D2.1)C與D可區(qū)分2.2)C=NULL且DNULL且D可達(dá)終態(tài)或CNULL且C可達(dá)終態(tài)且D=NULL第32頁(yè)，共54頁(yè)，2023年，2月20日，星期四DFA狀態(tài)數(shù)最小化-例子S0S1S3S2babbaaabS4ab第33頁(yè)，共54頁(yè)，2023年，2月20日，星期四復(fù)習(xí)一個(gè)DFAM=(K,,f,S0,Z)，函數(shù)f:K×->K表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)Kj的轉(zhuǎn)換。一個(gè)NFAM=(K,,f,S0,Z)，函數(shù)f:K×->(K)表示某狀態(tài)Ki接受某字母a后，到達(dá)狀態(tài)集合{K1,…,Kj}的轉(zhuǎn)換。

一個(gè)帶動(dòng)作的NFAM=(K,,f,S0,Z)，函數(shù)

f:K×{}->(K)表示某狀態(tài)Ki接受某字母a或空串后，到達(dá)狀態(tài)集合{K1,…,Kj}的轉(zhuǎn)換。第34頁(yè)，共54頁(yè)，2023年，2月20日，星期四試描述下述文法所產(chǎn)生的語(yǔ)言的特點(diǎn)G[S]=(VN={S,<alpha>,<digit>},VT={A…Z,a…z,0…9},P,S),其中P={SS<alpha>，SS<digit>，S<alpha>，<alpha>A，…，<alpha>z，<digit>0，…，<digit>9}第35頁(yè)，共54頁(yè)，2023年，2月20日，星期四上述正規(guī)文法產(chǎn)生的語(yǔ)言的特點(diǎn)是由字母開(kāi)頭，后接0個(gè)或多個(gè)字母和(或)數(shù)字的符號(hào)串即標(biāo)識(shí)符的定義如果使用型如字母(字母|數(shù)字)*的式子來(lái)表示上述符號(hào)串構(gòu)成的集合，那么這樣的式子就稱為正規(guī)表達(dá)式(正則式，RegularExpression)，相應(yīng)的符號(hào)串集合則稱為該表達(dá)式對(duì)應(yīng)的正規(guī)集。第36頁(yè)，共54頁(yè)，2023年，2月20日，星期四正規(guī)表達(dá)式及正規(guī)集的定義正規(guī)式正規(guī)集1.空集2.{}3.a，a{a}4.(r)?(s)Lr?Ls (r)|(s)LrLs (r)*

Lr*

[r]=((r)|())Lr{}(r)+=(r)?((r)*)Lr+第37頁(yè)，共54頁(yè)，2023年，2月20日，星期四算符優(yōu)先級(jí)與正規(guī)式化簡(jiǎn)

算符優(yōu)先級(jí)從高到低依次為(),[],*,+,?,|

如((r)?((s)*))|(r)，可化簡(jiǎn)為

r?s*|r

又因?yàn)檫B接符?通?？墒÷圆粚?，再化簡(jiǎn)為rs*|r第38頁(yè)，共54頁(yè)，2023年，2月20日，星期四正規(guī)式與正規(guī)集的例子={a,b}第39頁(yè)，共54頁(yè)，2023年，2月20日，星期四正規(guī)式與正規(guī)集的多對(duì)一關(guān)系給定一個(gè)正規(guī)式，它唯一確定一個(gè)正規(guī)集；反之不然。即一個(gè)正規(guī)集可由多個(gè)不同的正規(guī)式表示。我們稱兩個(gè)正規(guī)式等價(jià)，當(dāng)且僅當(dāng)它們所描述的正規(guī)集相同。例如a|b與b|a,(a|b)*與(b|a)*等等第40頁(yè)，共54頁(yè)，2023年，2月20日，星期四正規(guī)式的基本等價(jià)公理A1.r|s=s|r A2.r|r=r

A3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st) A6.r(s|t)=rs|rtA7.(s|t)r=sr|tr A8.r=r=A9.r=r=r A10.r*=(|r)*=|rr*第41頁(yè)，共54頁(yè)，2023年，2月20日，星期四由正規(guī)文法構(gòu)造正規(guī)式1/4使用正規(guī)式描述下述右線性文法產(chǎn)生的語(yǔ)言SaS|b SaS|bS|c(或S(a|b)S|c)SabS|c總結(jié)出規(guī)律:SS|對(duì)應(yīng)的正規(guī)式是*第42頁(yè)，共54頁(yè)，2023年，2月20日，星期四由正規(guī)文法構(gòu)造正規(guī)式2/4使用正規(guī)式描述下述左線性文法產(chǎn)生的語(yǔ)言SSa|b SSa|Sb|c(或SS(a|b)|c)SSab|c總結(jié)出規(guī)律:SS|對(duì)應(yīng)的正規(guī)式是*第43頁(yè)，共54頁(yè)，2023年，2月20日，星期四由正規(guī)文法構(gòu)造正規(guī)式3/4如果將“|”用“+”替換，“”用“=”替換，那么可以將產(chǎn)生式轉(zhuǎn)換為方程的形式，于是對(duì)上述兩個(gè)規(guī)律，我們得到論斷：論斷3.1

方程X=X+（對(duì)應(yīng)SS|），有解X=*論斷3.2

方程X=X+（對(duì)應(yīng)SS|），有解X=*第44頁(yè)，共54頁(yè)，2023年，2月20日，星期四由正規(guī)文法構(gòu)造正規(guī)式4/4于是，對(duì)文法G[S]SaS|bA|b AaS……我們可以將所有產(chǎn)生式的運(yùn)算符“|”用“+”替換，“”用“=”替換，再以我們習(xí)摜的線性方程組求解方法來(lái)求解S對(duì)應(yīng)的正規(guī)式。第45頁(yè)，共54頁(yè)，2023年，2月20日，星期四例子1)SaS|bA|b,AaS2)SaA,AbA|aB|b,BaA3)SbS|aA,AaA|bB,BaA|bC|b,Cb