第3章第3章詞法分析程正規(guī)表達(dá)式與正規(guī)集（正規(guī)語(yǔ)言有窮詞法分析程序的自動(dòng)構(gòu)本章重單詞的識(shí)別系設(shè) 詞法分析程描述程序設(shè)計(jì)語(yǔ)言的詞法的機(jī)制是正則表，識(shí)別機(jī)制是有窮狀態(tài) 回顧什么是詞法分析程實(shí)現(xiàn)詞法分析 ysis）的程分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在一詞法分析程序和語(yǔ)法分析程序的關(guān)gettoken

語(yǔ)法分析程序詞法分析程序的主要任務(wù)讀源程序，產(chǎn)生單詞符詞法分析程序的其他任務(wù)濾掉空格，跳過(guò)注釋、換追蹤換行標(biāo)志 出錯(cuò)源程序宏展開(kāi)常常遇到的術(shù) 單詞,詞標(biāo)，符 詞素，詞 模式，式幫助理解術(shù)Ingeneral，thereisasetofstringsintheinputforwhichthesametokenisproducedasoutput. Thissetofstringsisdescribedbyarulecalledapatternassociatedwiththetoken.Thepatternissaidtomatcheachstringintheset.Alexemeisasequenceofcharactersinthesourceprogramthatismatchedbythepatternforatoken.Constpi=3.14159；中的pi是token“identifier”的lexeme，其pattern為letterfollowedbylettersand/ordigit.改進(jìn)編譯效增加編譯系統(tǒng)的可移植正規(guī)表達(dá)式與正規(guī)集（正規(guī)語(yǔ)言首先表述一些基本術(shù)語(yǔ)和概念符號(hào)一個(gè)抽象實(shí)體,我們不再形式地定義它(就象幾何中字母 字母表是元素的非空有窮集合，我們把字母表的元素稱為符號(hào)，因此字母表也稱為符號(hào)集不同的語(yǔ)言可以有不同的字母表，例如漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號(hào)等L語(yǔ)言的字母表是由字母、數(shù)字、若干 符號(hào)BE、I之類的保留字組成。符號(hào)串由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串，例如001110是字母表=｛0，1｝上的符號(hào)串.字母表=｛a,b,｝上的一些符號(hào)串有：a,b,,ab,aaa。b就不同于ba,aba和aab也不同。可以使用字母表示符號(hào)串，如x=STR表示“x是由符S、T和R，并按此順序組成的符號(hào)串的長(zhǎng)度如果某符號(hào)串x中有m個(gè)符號(hào)，則稱其度為m，表示為｜x｜=m，如001110的長(zhǎng)度是6空符號(hào)串，即不包含任何符號(hào)的符號(hào)串，用ε度為，即｜ε｜。介紹有關(guān)符號(hào)串的一些運(yùn)算符號(hào)串的頭,：如果=xy是一符號(hào)串，那么是的頭，是的尾，如果是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。舉個(gè)例子設(shè)=abc那么的頭是ε,a,ab,a除abc外，其它都是固有頭；的尾是ε,,b,ab,的固有尾是ε,,b。 如果只是為了強(qiáng)調(diào)x在符號(hào)串中的某處出現(xiàn)，則可表示為：；符號(hào)是符號(hào)串的第一個(gè)符號(hào)，則表示為=…。是把y的符號(hào)寫在x的符號(hào)之后得到的符號(hào)串由于ε含義，顯然有εx=xε=x。例如x=ST，y=abu，則它們的連接xy=STabu，看符號(hào)串 ：符號(hào)串自身連接n次得到的符號(hào)an定義為aa…aan個(gè) a1=a,a2=aa且例；若x=AB則x0=x1x2=x3=xn=xxn-1=xn-1 符號(hào)串集合：若集合A中所有元素都是某字上的符號(hào)串，則稱A為字母表上的符號(hào)串集。兩個(gè)符號(hào)串集合A和B的乘定義為AB=xy|xA且若集合 集合B=AB使用*表示上的一切符號(hào)串（包括ε）組成的 上的除ε外的所有符號(hào)串組成的集合記為+Σ+稱為Σ的正閉包*{}

2

3

......*{}2......例正規(guī)regularexpression）是說(shuō)明單詞的模式定義（正規(guī)式和它所表示的正規(guī)集設(shè)字母表為，輔助字母表，，}1和都是上的正規(guī)式，它們所表示的正規(guī)集分別為{}和{}；2。任何a，a是上的一個(gè)正規(guī)式，它所表1e1e2e1e2e也都是正規(guī)式,它們所表示1正規(guī)集分別為L(zhǎng)(e1L(e1)L(e2和(L(e1))正規(guī)式中的符“”的）；“”讀為“連接”；“”讀為“閉包”（即，任意有限次的自重復(fù)）。在不致時(shí)，括號(hào)可省去，但規(guī)定算符的優(yōu)先順序?yàn)椤啊薄ⅰ啊?、“”。連接符“”一般可省略不寫?！啊?、“”和“是左結(jié)合的。例令={a，b}上的正規(guī)式和相應(yīng)的正規(guī)集的例正規(guī) 正規(guī) a {,a,a,任意個(gè)a的正規(guī) 正規(guī) {,a,b,aa,ab……所有由 {上所有含有兩個(gè)相的a或兩個(gè)相繼的組 的串令={l，d}，則上的正規(guī)式r=l(ld)定義的正規(guī)集為{l,ll,ld,ldd,……},其中l(wèi)代表字母,d代表數(shù)字,正規(guī)式即是字母(字母|數(shù)字),它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,就是Pascal和多數(shù)程序 例={d，，e，+，-則上的正規(guī)式 d(dd)(e(+-)dd)表示的是程序設(shè)計(jì)語(yǔ)言的單詞都能用正規(guī)式來(lái)定若兩個(gè)正規(guī)式1和2所表示的正規(guī)集相同,則說(shuō)1和e2等價(jià)寫作1=2。例如e1ab)e2=又如e1b(ab),e2e1= ,e21。 “或”服從交換2。 “或”的可結(jié)合 分配5。r=r, 是“連接”的恒等元零一6 “或”的抽取有窮有窮自(也稱有限自)作為一種識(shí)別裝所定義的語(yǔ)言和正規(guī)式所表示的集合，引入有窮自動(dòng)構(gòu)造尋找特殊的方法和工具。 (DeterministicFiniteAutomata)和不確定的有 (NondeterministicFiniteAutomata)。關(guān)于有窮 討論如下題 DFA的最小確定的有窮 DFA定義 DFA定f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上 ，， ）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱作的一個(gè)后繼狀態(tài)S∈K是唯一的一個(gè)初態(tài)ZK是一個(gè)終態(tài)集，終態(tài)也稱可接受狀態(tài)一個(gè)DFA的例子 {Q}）其中f定義為 圖)。假定DFAM含有m個(gè)狀態(tài)，n個(gè)輸入字符 標(biāo)以“+”，若f(ki,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到QbbDFA的狀態(tài)QbbaUSaUSVaa新?tīng)顟B(tài)，即k行a列為f(k,a)的值。箭DFA的矩陣表狀 字 0001 0001 ∑*上的符號(hào)串t在DFAM上運(yùn)其中T∈∑，t1∈∑*）在DFA f（Q，Tt1）=f（f（Q，T），t1）其中Q∈K擴(kuò)充轉(zhuǎn)換函數(shù)f為K×Σ*→K上的 f（ki，）=∑*上的符號(hào)串t被DFAM接若t∑*，f(S，t)=P，其中S為M的開(kāi)始狀，PZ，Z為終態(tài)集則稱t為DFAM所接受（識(shí)別例：證明t=baab被下圖的DFA所接受=f（V，aab）=Q屬于終態(tài)得證

b,QDFAM所能接受的符號(hào)串的全體記為 結(jié)論 ，若字母表Σ含有n個(gè)輸入字符，那末DFA的行為很容易用程序來(lái)模擬DFAM=（K，Σ，f，S，Z）的行為的模擬程序whilec<>eofifKisinZthenreturnelsereturnRegularexpressionsonthealphabetaredefinedbythefollowingrecursiverules:Everysymbolofisaregularεandisaregularifr1andr2areregularexpressions,soare(r1) r1r2 r1|r2 r1*Nothingelseisaregular=(1|2|3|4|5|6|7|8|9|0)*isaregular(1|2|3|4|...8|9|0)(1|2|3...|8|9|0)*isregularDFA Afinitesetofstates,oneofwhichisdesignatedtheinitialstateorstartstate,andsomeofwhicharedesignatedasfinalstates.phabetofpossibleinput Afinitesetoftransitionsthatspecifiesforeachstateandforeachsymboloftheinputalphabet,whichstatetogotonext. ?={digit,notDFAM所能接受的符號(hào)串的全體記為 結(jié)論 FA等不確定的有窮 定NFAM=K，，f，S，Z，其中K為狀態(tài)的有窮非空集為有窮輸入字母表，f為K*到K的子集（2K）的一種 初始狀態(tài)集，ZK為終止?fàn)顟B(tài)集.例NFAM=（{S，P，Z}，{0，1}，f，{S，P}，{Z}）狀態(tài)圖表111SZ0P1矩陣表矩陣表01S01S0P0Z101SP0P.Z0ZPP1f為K*到K的子集（2K）的一具有轉(zhuǎn)移的不確定的有窮 有如下定理 Ｍ，使得L(M)=L(N)。與上例等價(jià)的一個(gè)b b c bc類似DFA,對(duì)NFAM=K，，f，S，Z也有如∑*上的符號(hào)串t在NFAM上運(yùn)行一個(gè)輸入符號(hào)串 它表示成Tt1的形式，中T∈∑，t1∑*）在NFAM上運(yùn)行的定義為f（Q，Tt1）=f（f（Q，T），t1）其中∑*上的符號(hào)串t被NFAM接若t∑*，f(S0，t)=P，其中S0∈S，PZ，則稱t為NFAM所接受（識(shí)別）∑*上的符號(hào)串t被NFAM接受也可以這樣理 稱t可為NFAM所識(shí)別(讀出或接受)。若NFAM所能接受的符號(hào)串的全體記為結(jié)論 Ｍ，使得L(M)=L(N)。對(duì)每個(gè)NFAN存在著與之等價(jià)的DFAM。有一種算法，將NFA轉(zhuǎn)換成接受同樣語(yǔ)言DFA.這種算法稱為子集法與某一NFA等價(jià)的DFA不惟一從的矩陣表示中可以看出，表項(xiàng)通常是一狀態(tài)的集合，而在的矩陣表示中，表項(xiàng)是一個(gè)狀態(tài)，到相應(yīng)的的構(gòu)造的基本思路是：DFA的每一個(gè)狀態(tài)對(duì)應(yīng)NFA的一組狀態(tài). 使用它的狀態(tài)去記錄在讀入一個(gè)輸入符號(hào)后可能達(dá)到的所有狀態(tài).NFA確定化算法假設(shè)NFAN=(K,f,K0,Kt)按如下辦法構(gòu)造一個(gè)DFAM=(S,,d,S0,St)，使得1.M的狀態(tài)集S由K的一些子集組成。用[S1S2...Sj]表示S的元素，其中S1,S2,,...Sj是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...Sj是按某種規(guī)則排列的，即對(duì)于子集{S1S2}={S2,S1,}來(lái)說(shuō)，S的狀態(tài)就是[S1S2]；M和N的輸入字母表是相同的，即是轉(zhuǎn)換函數(shù)是這樣定義d([S1S2,Sj],aR1R2Rt]其{R1,R2,...,Rt} -closure(move({S1,S0=-closure(K0)為M的開(kāi)始狀態(tài)St={[SiSk...Se]，其中[Si Sk...Se]S且{Si,Sk,,...Se}Kt}定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算 狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)狀態(tài)集合I的弧轉(zhuǎn)換，表示為ov(I,a定義為狀態(tài)集合，其中是所有那些可從I中的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。狀態(tài)集合I的有關(guān)運(yùn)算的I={1},-I={5},--a5a512a638a47構(gòu)造NFAN的狀態(tài)K的子集的算法假定所構(gòu)造的子集族為C，即C=(T1,T2,,...其中T1,T2,,...TI為狀態(tài)K的子集 while（C中存在尚未被標(biāo)記的子集{標(biāo)記for每個(gè)輸入字母 {U:=-ifU不在C中將U作為未標(biāo)記的子集加在C}}NFA的確定例aaa3aai1256fbb4bbaaaa3aai1256fbb4bbSABA{1,2,3,5,6,f}BBA{1,2,4,5,6,f}{1,2,3,5,6,f}{1,2,3,5,6,f}E{1,2,4,5,6,f}F{1,2,4,5,6,f}EF{1,2,4,5,6,f}F{1,2,3,5,6,f}E等價(jià)的aaAaAaCbEaSbaabbBbDaFb確定有窮 的化說(shuō)一個(gè)有窮自是化簡(jiǎn)了的，即是說(shuō)，它沒(méi)價(jià)的。一個(gè)有窮自可以通過(guò)消除多余狀態(tài)的有窮自。所謂有窮自的多余狀態(tài)，是指這樣的狀：從自的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不DFA的最小化就是尋求最小狀態(tài)最小狀態(tài)DFA的含義沒(méi)有多余狀態(tài)(沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別兩個(gè)狀態(tài)s和t可區(qū)別：不滿兼容性——同是終態(tài)或同是非性——從s出發(fā)讀入某個(gè)aa和t出發(fā)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)C和D同是終態(tài),讀入a到達(dá)C和F,C和F同是態(tài),C和F讀入a都到達(dá)C,讀入b都到達(dá)E.C和D aAaAaCbEaSbaabbBbDaFb最小狀態(tài)對(duì)于一個(gè)DFAM（K,∑,fk0,,kt)，存在一個(gè)最小狀態(tài)DFAM’=（K’,∑,f’,結(jié) “分割法DFA的最小化算法DFA的最小化算DFAM（K,∑,fk0,kt),最小狀態(tài)DFA構(gòu)造狀態(tài)的一初始劃分終態(tài)kt和非終態(tài)Kkt對(duì)∏施用過(guò)程PP構(gòu)造新劃如 ==∏,則令∏final=∏并繼步驟4，否則∏:=∏new重復(fù)2為∏fial中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若是一代表且f(k,a)=t,令r是t組的代表，則M中有一轉(zhuǎn)換(k,a)=r 的開(kāi)始狀態(tài)是含有S0的那組的代表的終態(tài)是含有F的那組的代去掉M’中的死狀過(guò)程PPConstructionofForeachgroupGof∏PartitonGintosubgroupssuchthattwostatessandtofGareinthesamesubgroupsifandonlyifforallinputsymbolsa,statessandthavetransitionsonatostatesinthesamegroupof∏;/*atworst,astatewillbeinasubgroupbyitself*/replaceGin∏newbythesetofallsubgroupsDFA的最小化—例

a

baAaSbabBbaAaSbabBbDa3.4詞法分析程序的自動(dòng)對(duì)有窮自和正規(guī)表達(dá)式進(jìn)行了上述討論之后,我們介有窮自和正規(guī)表達(dá)式的等價(jià)性,即：對(duì)于∑上的一個(gè)NFAM，可以構(gòu)造一個(gè)∑上的的NFAM，使的L(M)=L(R)。.“對(duì)于∑上的一個(gè)正規(guī)式R,可以構(gòu)造一個(gè)∑上的NFA，，使得 說(shuō)明一種構(gòu)造方法R=,構(gòu)造任一具有空終態(tài)集的NFA(2）R=，構(gòu)造的NFAM=({k0},∑,f,k0.{k0}):f（k0,a)有a∑都沒(méi)定義。(3）R=a,構(gòu)造的NFAf(k0,a)=R=R1|R2,將步驟（1）（2）（3）分別應(yīng)用 產(chǎn)生M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.構(gòu)造NFAM=(K1K2{k},∑,f,k,F)k是新增加的狀態(tài)f包含f1和f2,且若k1F1且k2F2F=F1F2，否則F=F1將步驟（1）（2）（3）分別應(yīng)用到 產(chǎn)M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相.構(gòu)造的NFAM=(K1K2,∑,f,k1,F2) f包含f1f2,f(k,a)=f1(k,a),當(dāng)kF1時(shí)f(k,a)=f2(k,a),當(dāng)k∈K2時(shí)f(k1,將步驟（1）（2）（3）分別應(yīng)用到R1,產(chǎn)生構(gòu)造的NFAM=(K1{k0,F0},∑,f,k0,F0)其中k0,F0 f(k,a)=f1(k,a),當(dāng)kF1時(shí)f(k0,)=f(F1,)={k1,,F0},再用狀態(tài)圖說(shuō)明可用方對(duì)于正規(guī)式x,x∑構(gòu)造的種XSFF對(duì)于正規(guī)式,構(gòu)造的NFA（三種SFF對(duì)于正規(guī)式R=,構(gòu)造的SSFF對(duì)于正規(guī)式r,r=R1|R2構(gòu)造的對(duì)于正規(guī)式r,r=R1R2構(gòu)造的對(duì)于正規(guī)式r,r=R1*構(gòu)造的R=(a|ab)*b詞法分析程序的設(shè)計(jì)技術(shù)可應(yīng)用于其它領(lǐng)域，比如查詢語(yǔ)言以及信息檢系等這應(yīng)領(lǐng)的序計(jì)特點(diǎn)是，通過(guò)字符串模式的匹配來(lái) 動(dòng)作，回想LE，說(shuō)明詞法分析程序的語(yǔ)言，可以看成是一個(gè)模式動(dòng)作語(yǔ)言。詞法分析程序的自動(dòng)構(gòu)造工具也廣泛應(yīng)用于許多方面，如用以生成一個(gè)程序，可識(shí)別印刷電路板中的缺陷，又如開(kāi)關(guān)線路設(shè)計(jì)和文本編輯的自動(dòng)生成等。習(xí)4練1345本章小讀入字符流的源程序，按照 則識(shí)別單，交由語(yǔ)法分析程序接下去和有窮。在此基礎(chǔ)上給出了詞法分析程序識(shí)別Pascal單詞的NFA的確定MoreDFA的最小化算法—英文描Constructaninitialpartition∏thesetofstateswithtwogroups:theacceptingstatesFandthenonacceptingstatesS-F.ApplytheprocedurePP.to∏toconstructane rtition∏new.If∏new=∏,l