詞法分析及詞法分析程序

詞法分析及詞法分析程序第1頁，課件共60頁，創(chuàng)作于2023年2月設(shè)計(jì)掃描器應(yīng)注意的問題詞法分析（3型）語法分析（2型）單詞的(Class,Value)二元組表示標(biāo)識(shí)符的長度限制和按“盡可能長”的識(shí)別策略超前搜索與回退<,<=,<<,<<=程序3-1輸入緩沖注釋與空白的刪除第2頁，課件共60頁，創(chuàng)作于2023年2月狀態(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頁，課件共60頁，創(chuàng)作于2023年2月右線性文法=>狀態(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的開始符S為初態(tài)狀態(tài)3)終止?fàn)顟B(tài),用F(VN)標(biāo)記F是新加(狀態(tài)）節(jié)點(diǎn)第4頁，課件共60頁，創(chuàng)作于2023年2月右線性文法=>狀態(tài)轉(zhuǎn)換圖aA->aBABA->aAFaA->ε消除ε，重用上述規(guī)則AF[other]A若A為起始符（G[A]）A第5頁，課件共60頁，創(chuàng)作于2023年2月產(chǎn)生式的消除SAXFabc[other]YeSAXFabcYeS->aAA->b|bX

X->c|eYS->aAA->bXX->c|ε|eY第6頁，課件共60頁，創(chuàng)作于2023年2月狀態(tài)圖=>右線性文法文法G[0]0->a1S->aA1->d1A->dA1->bA->b0->cS->c0->c2S->cB，2有出弧2->dB->d0132abcdd第7頁，課件共60頁，創(chuàng)作于2023年2月左線性文法=>狀態(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的開始符S為終止?fàn)顟B(tài)3)起始狀態(tài),用R(VN)標(biāo)記R是新加(狀態(tài)）節(jié)點(diǎn)第8頁，課件共60頁，創(chuàng)作于2023年2月左線性文法=>狀態(tài)轉(zhuǎn)換圖aA->BaBAA->ε的消除消除ε，重用上述規(guī)則RA[other]若A為起始符（G[A]）AA->aRAa不存在這種轉(zhuǎn)換第9頁，課件共60頁，創(chuàng)作于2023年2月狀態(tài)圖=>左線性文法文法G[3]1->aAa1->1dAAd3->1bSAb2->cBc3->2dSBd0132abcdd第10頁，課件共60頁，創(chuàng)作于2023年2月狀態(tài)矩陣狀態(tài)矩陣Bij=B[Si,aj]=Sk當(dāng)前狀態(tài)，掃視字符，語義動(dòng)作，后續(xù)狀態(tài)程序3-2第11頁，課件共60頁，創(chuàng)作于2023年2月識(shí)別無符號(hào)數(shù)的狀態(tài)矩陣第12頁，課件共60頁，創(chuàng)作于2023年2月語義動(dòng)作中的返回值ICON、FCON分別為整型數(shù)、浮點(diǎn)型數(shù)的值；一般說來，無符號(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)無符號(hào)數(shù)識(shí)別矩陣第13頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月函數(shù)f的推廣定義f^

f^:K×*->K，表示某狀態(tài)接受一個(gè)字母串（而不是一個(gè)字母）所到達(dá)的狀態(tài)，f^的定義依賴于f的定義，f^遞歸定義如下：1）f^(p,)=p,ifpK，即任意一狀態(tài)p接受（串長為0）的輸入，狀態(tài)不變2）f^(p,aw)=f^(f(p,a),w),ifpK,a,w*第16頁，課件共60頁，創(chuàng)作于2023年2月函數(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頁，課件共60頁，創(chuàng)作于2023年2月DFA所識(shí)別的語言令M為一DFA，我們：定義L(M)={x|f(S0,x)Z,x*}L(M)稱為DFAM所識(shí)別的語言有定理：L(M)=L(G)，其中M為一DFA，G為一正規(guī)文法第18頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月映射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頁，課件共60頁，創(chuàng)作于2023年2月NFA所識(shí)別的語言令N為一NFA，我們：定義L(N)={x|f(S0,x)Z,x*}L(N)稱為NFAN所識(shí)別的語言有定理：L(N)=L(M)=L(G)，其中N為一NFA，M為一DFA，G為一正規(guī)文法第22頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月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è)試探過程，為了能走到終態(tài)，往往要走許多彎路（帶回溯），這影響了NFA的效率。解決辦法？第24頁，課件共60頁，創(chuàng)作于2023年2月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頁，課件共60頁，創(chuàng)作于2023年2月例子S0S1abba,bq0q2a,babq1b第26頁，課件共60頁，創(chuàng)作于2023年2月帶有動(dòng)作的NFA例子

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

bS0S1S3aS2cb第27頁，課件共60頁，創(chuàng)作于2023年2月帶有動(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頁，課件共60頁，創(chuàng)作于2023年2月帶有動(dòng)作的NFA的確定化步驟：1)求-closure，且將所有狀態(tài)表上（除的列以外）狀態(tài)q用相應(yīng)的-closure(q)替代2)刪除列3)從起始狀態(tài)S0的-closure(S0)開始走3.1)-closure(S0)做行計(jì)算：對(duì)每字母a，求-closure(S0)-a->?3.2)對(duì)-closure(S0)所能到達(dá)的每個(gè)狀態(tài)集做行計(jì)算4)標(biāo)記“起始狀態(tài)”，“終止?fàn)顟B(tài)”，“可達(dá)性”5)用樣本串測(cè)試所得的DFA第29頁，課件共60頁，創(chuàng)作于2023年2月S0S1S3aS2cbb第30頁，課件共60頁，創(chuàng)作于2023年2月abcS0S0S1,S2S1S1,S3S2S2S3S30）畫出狀態(tài)表第31頁，課件共60頁，創(chuàng)作于2023年2月abcS0S1,S2,S3S0,S1,S2,S3S1,S2,S3S1S1,S3S2,S3S2,S3S3S31）求-closure，且將所有狀態(tài)表上（除的列以外）狀態(tài)q用相應(yīng)的-closure(q)替代，如S0和S2第32頁，課件共60頁，創(chuàng)作于2023年2月abcS0S1,S2,S3S0,S1,S2,S3S1,S2,S3S1S1,S3S2,S3S2,S3S3S32)刪除列第33頁，課件共60頁，創(chuàng)作于2023年2月可達(dá)性abc-起始->S0S1,S2,S3S0,S1,S2,S3S1,S3S2,S3S1,S2,S3S1S1,S3->S2,S3S2,S3S3S3->S1,S3S1,S33)從起始狀態(tài)S0的-closure(S0)開始走第34頁，課件共60頁，創(chuàng)作于2023年2月4)標(biāo)記“起始狀態(tài)”，“終止?fàn)顟B(tài)”，“可達(dá)性”可達(dá)性abc-起始->[S0S1,S2,S3]S0,S1,S2,S3S1,S3S2,S3S1,S2,S3S1S1,S3->[S2,S3]S2,S3S3S3->[S1,S3]S1,S3令q0={S0,S1,S2,S3},q1={S1,S3},q2={S2,S3}得下表第35頁，課件共60頁，創(chuàng)作于2023年2月abc->[q0]q0q1q2[q2]q2[q1]q15)用樣本串測(cè)試所得的DFA，如原NFA識(shí)別abb,ac，所得新DFA也識(shí)別，即P68,圖3-12第36頁，課件共60頁，創(chuàng)作于2023年2月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)第37頁，課件共60頁，創(chuàng)作于2023年2月可區(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第38頁，課件共60頁，創(chuàng)作于2023年2月DFA狀態(tài)數(shù)最小化-例子S0S1S3S2babbaaabS4ab第39頁，課件共60頁，創(chuàng)作于2023年2月復(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)換。第40頁，課件共60頁，創(chuàng)作于2023年2月試描述下述文法所產(chǎn)生的語言的特點(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}第41頁，課件共60頁，創(chuàng)作于2023年2月上述正規(guī)文法產(chǎn)生的語言的特點(diǎn)是由字母開頭，后接0個(gè)或多個(gè)字母和(或)數(shù)字的符號(hào)串即標(biāo)識(shí)符的定義如果使用型如字母(字母|數(shù)字)*的式子來表示上述符號(hào)串構(gòu)成的集合，那么這樣的式子就稱為正規(guī)表達(dá)式(正則式，RegularExpression)，相應(yīng)的符號(hào)串集合則稱為該表達(dá)式對(duì)應(yīng)的正規(guī)集。第42頁，課件共60頁，創(chuàng)作于2023年2月正規(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+第43頁，課件共60頁，創(chuàng)作于2023年2月算符優(yōu)先級(jí)與正規(guī)式化簡

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

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

r?s*|r

又因?yàn)檫B接符?通?？墒÷圆粚?，再化簡為rs*|r第44頁，課件共60頁，創(chuàng)作于2023年2月正規(guī)式與正規(guī)集的例子={a,b}第45頁，課件共60頁，創(chuàng)作于2023年2月正規(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)*等等第46頁，課件共60頁，創(chuàng)作于2023年2月正規(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*第47頁，課件共60頁，創(chuàng)作于2023年2月由正規(guī)文法構(gòu)造正規(guī)式1/4使用正規(guī)式描述下述右線性文法產(chǎn)生的語言SaS|b SaS|bS|c(或S(a|b)S|c)SabS|c總結(jié)出規(guī)律:SS|對(duì)應(yīng)的正規(guī)式是*第48頁，課件共60頁，創(chuàng)作于2023年2月由正規(guī)文法構(gòu)造正規(guī)式2/4使用正規(guī)式描述下述左線性文法產(chǎn)生的語言SSa|b SSa|Sb|c(或SS(a|b)|c)SSab|c總結(jié)出規(guī)律:SS|對(duì)應(yīng)的正規(guī)式是*第49頁，課件共60頁，創(chuàng)作于2023年2月由正規(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=*第50頁，課件共60頁，創(chuàng)作于2023年2月由正規(guī)文法構(gòu)造正規(guī)式4/4于是，對(duì)文法G[S]SaS|bA|b AaS……我們可以將所有產(chǎn)生式的運(yùn)算符“|”用“+”替換，“”用“=”替換，再以我們習(xí)摜的線性方程組求解方法來求解S對(duì)應(yīng)的正規(guī)式。第51頁，課件共60頁，創(chuàng)作于2023