編譯原理-第3章詞法分析

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

語法分析程序詞法分析程序的主要任務(wù)讀源程序，產(chǎn)生單詞符詞法分析程序的其他任務(wù)濾掉空格，跳過注釋、換追蹤換行標(biāo)志 出錯源程序宏展開常常遇到的術(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ī)語言首先表述一些基本術(shù)語和概念符號一個抽象實體,我們不再形式地定義它(就象幾何中字母 字母表是元素的非空有窮集合，我們把字母表的元素稱為符號，因此字母表也稱為符號集不同的語言可以有不同的字母表，例如漢語的字母表中包括漢字、數(shù)字及標(biāo)點符號等L語言的字母表是由字母、數(shù)字、若干 符號BE、I之類的保留字組成。符號串由字母表中的符號組成的任何有窮序列稱為符號串，例如001110是字母表=｛0，1｝上的符號串.字母表=｛a,b,｝上的一些符號串有：a,b,,ab,aaa。b就不同于ba,aba和aab也不同?？梢允褂米帜副硎痉柎鐇=STR表示“x是由符S、T和R，并按此順序組成的符號串的長度如果某符號串x中有m個符號，則稱其度為m，表示為｜x｜=m，如001110的長度是6空符號串，即不包含任何符號的符號串，用ε度為，即｜ε｜。介紹有關(guān)符號串的一些運算符號串的頭,：如果=xy是一符號串，那么是的頭，是的尾，如果是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。舉個例子設(shè)=abc那么的頭是ε,a,ab,a除abc外，其它都是固有頭；的尾是ε,,b,ab,的固有尾是ε,,b。 如果只是為了強調(diào)x在符號串中的某處出現(xiàn)，則可表示為：；符號是符號串的第一個符號，則表示為=…。是把y的符號寫在x的符號之后得到的符號串由于ε含義，顯然有εx=xε=x。例如x=ST，y=abu，則它們的連接xy=STabu，看符號串 ：符號串自身連接n次得到的符號an定義為aa…aan個 a1=a,a2=aa且例；若x=AB則x0=x1x2=x3=xn=xxn-1=xn-1 符號串集合：若集合A中所有元素都是某字上的符號串，則稱A為字母表上的符號串集。兩個符號串集合A和B的乘定義為AB=xy|xA且若集合 集合B=AB使用*表示上的一切符號串（包括ε）組成的 上的除ε外的所有符號串組成的集合記為+Σ+稱為Σ的正閉包*{}

2

3

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

b,QDFAM所能接受的符號串的全體記為 結(jié)論 ，若字母表Σ含有n個輸入字符，那末DFA的行為很容易用程序來模擬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所能接受的符號串的全體記為 結(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)。與上例等價的一個b b c bc類似DFA,對NFAM=K，，f，S，Z也有如∑*上的符號串t在NFAM上運行一個輸入符號串 它表示成Tt1的形式，中T∈∑，t1∑*）在NFAM上運行的定義為f（Q，Tt1）=f（f（Q，T），t1）其中∑*上的符號串t被NFAM接若t∑*，f(S0，t)=P，其中S0∈S，PZ，則稱t為NFAM所接受（識別）∑*上的符號串t被NFAM接受也可以這樣理 稱t可為NFAM所識別(讀出或接受)。若NFAM所能接受的符號串的全體記為結(jié)論 Ｍ，使得L(M)=L(N)。對每個NFAN存在著與之等價的DFAM。有一種算法，將NFA轉(zhuǎn)換成接受同樣語言DFA.這種算法稱為子集法與某一NFA等價的DFA不惟一從的矩陣表示中可以看出，表項通常是一狀態(tài)的集合，而在的矩陣表示中，表項是一個狀態(tài)，到相應(yīng)的的構(gòu)造的基本思路是：DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài). 使用它的狀態(tài)去記錄在讀入一個輸入符號后可能達(dá)到的所有狀態(tài).NFA確定化算法假設(shè)NFAN=(K,f,K0,Kt)按如下辦法構(gòu)造一個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ī)則排列的，即對于子集{S1S2}={S2,S1,}來說，S的狀態(tài)就是[S1S2]；M和N的輸入字母表是相同的，即是轉(zhuǎn)換函數(shù)是這樣定義d([S1S2,Sj],aR1R2Rt]其{R1,R2,...,Rt} -closure(move({S1,S0=-closure(K0)為M的開始狀態(tài)St={[SiSk...Se]，其中[Si Sk...Se]S且{Si,Sk,,...Se}Kt}定義對狀態(tài)集合I的幾個有關(guān)運算 狀態(tài)集合I的任何狀態(tài)S都屬于ε-closure(I)狀態(tài)集合I的弧轉(zhuǎn)換，表示為ov(I,a定義為狀態(tài)集合，其中是所有那些可從I中的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。狀態(tài)集合I的有關(guā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每個輸入字母 {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等價的aaAaAaCbEaSbaabbBbDaFb確定有窮 的化說一個有窮自是化簡了的，即是說，它沒價的。一個有窮自可以通過消除多余狀態(tài)的有窮自。所謂有窮自的多余狀態(tài)，是指這樣的狀：從自的開始狀態(tài)出發(fā)，任何輸入串也不DFA的最小化就是尋求最小狀態(tài)最小狀態(tài)DFA的含義沒有多余狀態(tài)(沒有兩個狀態(tài)是互相等價（不可區(qū)別兩個狀態(tài)s和t可區(qū)別：不滿兼容性——同是終態(tài)或同是非性——從s出發(fā)讀入某個aa和t出發(fā)讀入某個a到達(dá)的狀態(tài)等價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)對于一個DFAM（K,∑,fk0,,kt)，存在一個最小狀態(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對∏施用過程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 的開始狀態(tài)是含有S0的那組的代表的終態(tài)是含有F的那組的代去掉M’中的死狀過程PPConstructionofForeachgroupGof∏PartitonGintosubgroupssuchthattwostatessandtofGareinthesamesubgroupsifandonlyifforallinputsymbolsa,statessandthavetransitionsonatostatesinthesamegroupof∏;/*atworst,astatewillbeinasubgroupbyitself*/replaceGin∏newbythesetofallsubgroupsDFA的最小化—例

a

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