編譯原理word版.

1、第三章復(fù)習(xí)：程序語言的語法描述 幾個(gè)概念:考慮一個(gè)有窮 字母表 字符集其中每一個(gè)元素稱為一個(gè)字符上的字(也叫字符串) 是指由中的字符所構(gòu)成的一個(gè)有窮序列不包含任何字符的序列稱為空字，記為用*表示上的所有字的全體,包含空字復(fù)習(xí)：程序語言的語法描述 *的子集U和V的連接（積）定義為UV ab | aÎU & bÎV V自身的 n次積記為Vn=VVV規(guī)定V0=e，令 V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。復(fù)習(xí)：程序語言的語法描述 上下文無關(guān)文法的定義： 一個(gè)上下文無關(guān)文法G是一個(gè)四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符

2、集合(非空)VN：非終結(jié)符集合(非空)，且VT Ç VN=ÆS：文法的開始符號(hào)，SÎVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P®a， PÎVN， a Î (VT È VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。復(fù)習(xí)：程序語言的語法描述 定義：稱aAb直接推出agb，即aAbÞagb 僅當(dāng)A ® g是一個(gè)產(chǎn)生式， 且a， bÎ (VT È VN)* 。如果a1 Þ a2 Þ ¼ Þan，則我們稱這個(gè)序列是從a1到an的一個(gè)推導(dǎo)。若存在一

3、個(gè)從a1到an的推導(dǎo)，則稱a1可以推導(dǎo)出an 。復(fù)習(xí)：程序語言的語法描述 最左推導(dǎo)：任何一步a Þ b都是對(duì)a中的最左非終結(jié)符進(jìn)行替換。 最右推導(dǎo)：任何一步a Þ b都是對(duì)a中的最右非終結(jié)符進(jìn)行替換。復(fù)習(xí)：程序語言的語法描述 用一張圖表示一個(gè)句型的推導(dǎo),稱為語法樹。復(fù)習(xí)：程序語言的語法描述 定義：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩顆不同的語法樹，則說這個(gè)文法是二義的。語言的二義性：一個(gè)語言是二義性的，如果對(duì)它不存在無二義性的文法。復(fù)習(xí)：程序語言的語法描述 形式語言鳥瞰¨ 0型(短語文法，圖靈機(jī))： 產(chǎn)生式形如： a ® b 其中：aÎ (VT &#

4、200; VN)*且至少含有一個(gè)非終結(jié)符；bÎ (VT È VN)*¨ 1型(上下文有關(guān)文法，線性界限自動(dòng)機(jī))： 產(chǎn)生式形如： a ® b 其中：|a| £ |b|，僅 S®e 例外。復(fù)習(xí)：程序語言的語法描述 形式語言鳥瞰¨ 2型(上下文無關(guān)文法，非確定下推自動(dòng)機(jī))： 產(chǎn)生式形如： A ® b 其中：AÎ VN；bÎ (VT È VN)*。¨ 3型(正規(guī)文法，有限自動(dòng)機(jī))： 產(chǎn)生式形如： A ® aB 或 A ® a 其中： aÎ VT*；A，B

5、ÎVN 產(chǎn)生式形如： A ® Ba 或 A ® a 其中： aÎ VT*；A，BÎVN第三章 詞法分析詞法分析的任務(wù)：從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)。詞法分析器(Lexical Analyzer) 又稱掃描器(Scanner)：執(zhí)行詞法分析的程序3.1 對(duì)于詞法分析器的要求一、詞法分析器的功能和輸出形式功能:輸入源程序、輸出單詞符號(hào)單詞符號(hào)的種類：基本字：如 begin，repeat，¼標(biāo)識(shí)符表示各種名字：如變量名、數(shù)組名和過程名常數(shù)：各種類型的常數(shù)運(yùn)算符：+，-，*，/，¼界符：逗號(hào)、分號(hào)、括號(hào)和空

6、白輸出的單詞符號(hào)的表示形式:(單詞種別，單詞自身的值)單詞種別通常用整數(shù)編碼表示。若一個(gè)種別只有一個(gè)單詞符號(hào)，則種別編碼就代表該單詞符號(hào)。假定基本字、運(yùn)算符和界符都是一符一種。若一個(gè)種別有多個(gè)單詞符號(hào)，則對(duì)于每個(gè)單詞符號(hào)，給出種別編碼和自身的值。標(biāo)識(shí)符單列一種；常數(shù)按類型分種(整、實(shí)、布爾等）。例 C程序 while (i>=j) i-;輸出單詞符號(hào)：< while, - >< (, - >< id, 指向i的符號(hào)表項(xiàng)的指針 >< >=, - >< id, 指向j的符號(hào)表項(xiàng)的指針 >< ), - >< i

7、d, 指向i的符號(hào)表項(xiàng)的指針 >< -, - >< ;, - >二、詞法分析器作為一個(gè)獨(dú)立子程序詞法分析是作為一個(gè)獨(dú)立的階段，是否應(yīng)當(dāng)將其處理為一遍呢？作為獨(dú)立階段的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)潔、清晰和條理化，有利于集中考慮詞法分析一些枝節(jié)問題。不作為一遍：將其處理為一個(gè)子程序。詞法分析器的結(jié)構(gòu)輸入串放在輸入緩沖區(qū)中。預(yù)處理子程序：剔除無用的空白、跳格、回車和換行等編輯性字符;區(qū)分標(biāo)號(hào)區(qū)、捻接續(xù)行和給出句末符等掃描緩沖區(qū)二、單詞符號(hào)的識(shí)別:超前搜索1 基本字識(shí)別:例如:DO99K=1，10 DO 99 K = 1，10 IF(5.EQ.M)GOTO55 IF (5.EQ.M)

8、GOTO 55DO99K=1.10IF(5)=55需要超前搜索才能確定哪些是基本字2 標(biāo)識(shí)符識(shí)別:字母開頭的字母數(shù)字串，后跟界符或算符3 常數(shù)識(shí)別:識(shí)別出算術(shù)常數(shù)并將其轉(zhuǎn)變?yōu)槎M(jìn)制內(nèi)碼表示。有些也要超前搜索。 5.EQ.M 5.E084 算符和界符的識(shí)別把多個(gè)字符符合而成的算符和界符拼合成一個(gè)單一單詞符號(hào)。:=， *， .EQ. ， +，-，>=三、狀態(tài)轉(zhuǎn)換圖1 概念狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別(或接受)一定的字符串。6)IsLetter和 IsDisgital 布爾函數(shù)，判斷ch中字符是否為字母和數(shù)字7) Reserve 整型函數(shù)，對(duì)于 strToken 中的字

9、符串查找保留字表，若它實(shí)保留字則給出它的編碼，否則回送08) Retract 子程序，把搜索指針回調(diào)一個(gè)字符位置9)InsertId 整型函數(shù)，將strToken中的標(biāo)識(shí)符插入符號(hào)表，返回符號(hào)表指針10)InsertConst 整型函數(shù)過程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針。 int code, value;strToken := “ ”;/*置strToken為空串*/GetChar(); GetBC();if (IsLetter()beginwhile (IsLetter() or IsDigit()beginConcat(); GetChar(); endRetrac

10、t();code := Reserve();if (code = 0)beginvalue := InsertId(strToken);return ($ID, value);endelsereturn (code, -);endelse if (IsDigit()beginwhile (IsDigit()beginConcat( ); GetChar( );endRetract();value := InsertConst(strToken);return($INT, value);endelse if (ch =) return ($ASSIGN, -);else if (ch =+) r

11、eturn ($PLUS, -);else if (ch =*)beginGetChar();if (ch =*) return ($POWER, -);Retract(); return ($STAR, -);endelse if (ch =;) return ($SEMICOLON, -);else if (ch =() return ($LPAR, -);else if (ch =) return ($RPAR, -);else ProcError( );/* 錯(cuò)誤處理*/3.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)幾個(gè)概念:考慮一個(gè)有窮 字母表 字符集其中每一個(gè)元素稱為一個(gè)字符上的字(也叫字符串)

12、是指由中的字符所構(gòu)成的一個(gè)有窮序列不包含任何字符的序列稱為空字，記為用*表示上的所有字的全體,包含空字例如: 設(shè) =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.*的子集U和V的連接（積）定義為UV ab | aÎU & bÎV V自身的 n次積記為Vn=VVV規(guī)定V0=e，令 V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。3.3.1 正規(guī)式和正規(guī)集正規(guī)集可以用正規(guī)表達(dá)式（簡(jiǎn)稱正規(guī)式）表示。正規(guī)表達(dá)式是表示正規(guī)集一種方法。一個(gè)字集合是正規(guī)集當(dāng)且僅當(dāng)它能用正規(guī)式表示。正規(guī)式和正規(guī)集的遞歸定義：對(duì)給定的字母表S1)e 和

13、Æ都是S上的正規(guī)式，它們所表示的正規(guī)集為e和Æ2) 任何aÎS ，a是S上的正規(guī)式，它所表示的正規(guī)集為a ;3) 假定e1和e2都是S上的正規(guī)式，它們所表示的正規(guī)集為L(zhǎng)(e1)和L(e2)，則i) (e1|e2)為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)ÈL(e2)，ii) (e1.e2)為正規(guī)式，它所表示的正規(guī)集為L(zhǎng)(e1)L(e2)，iii) (e1)*為正規(guī)式，它所表示的正規(guī)集為(L(e1)*，僅由有限次使用上述三步驟而定義的表達(dá)式才是S上的正規(guī)式，僅由這些正規(guī)式表示的字集才是S上的正規(guī)集。所有詞法結(jié)構(gòu)一般都可以用正規(guī)式描述。若兩個(gè)正規(guī)式所表示的正規(guī)集

14、相同，則稱這兩個(gè)正規(guī)式等價(jià)。如b(ab)*=(ba)*b(a*b*)*=(a|b)* 對(duì)正規(guī)式，下列等價(jià)成立：e1|e2 = e2|e1 交換律e1 |(e2|e3) = (e1|e2)|e3 結(jié)合律e1(e2e3) = (e1e2)e3 結(jié)合律e1(e2|e3) = e1e2|e1e3 分配律(e2|e3)e1 = e2e1|e3 e1分配律ee = e e = e e1e2 <> e2 e1 3.3.2 確定有限自動(dòng)機(jī)(DFA)對(duì)狀態(tài)圖進(jìn)行形式化，則可以下定義：自動(dòng)機(jī)M是一個(gè)五元式M=(S, S, f, S0, F),其中：1. S: 有窮狀態(tài)集，2. S：輸入字母表(有窮)，

15、3. f: 狀態(tài)轉(zhuǎn)換函數(shù)，為S´S®S的單值部分映射，f(s，a)=s表示：當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將狀態(tài)轉(zhuǎn)換到下一狀態(tài)s。我們把s稱為s的一個(gè)后繼狀態(tài)。4. S0ÎS是唯一的一個(gè)初態(tài)； 5 FÍS ：終態(tài)集(可空)。例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3DFA可以表示為狀態(tài)轉(zhuǎn)換圖。假定DFA M含有m個(gè)狀態(tài)和n個(gè)輸入字符，那么，這個(gè)圖含有m個(gè)狀態(tài)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)頂多含有n條箭弧

16、射出，且每條箭弧用上的不同的輸入字符來作標(biāo)記。對(duì)于S*中的任何字a，若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧上的標(biāo)記符連接成的字等于a，則稱a為DFA M所識(shí)別(接收)DFA M所識(shí)別的字的全體記為L(zhǎng)(M)?？梢宰C明：S上的字集VÍS*是正規(guī)集，當(dāng)且僅當(dāng)存在上的DFA M，使得VL(M)。3.3.3 非確定有限自動(dòng)機(jī)(NFA) 定義：一個(gè)非確定有限自動(dòng)機(jī)(NFA) M是一個(gè)五元式M=(S, S, f, S0, F)，其中：1 S: 有窮狀態(tài)集；2 S ：輸入字母表(有窮)；3 f: 狀態(tài)轉(zhuǎn)換函數(shù)，為S´S*®2S的部分映射(非單值)；4 S0Í

17、S是非空的初態(tài)集；5 F ÍS ：終態(tài)集(可空)。從狀態(tài)圖中看NFA 和DFA的區(qū)別： 1 弧上的標(biāo)記可以是S*中的一個(gè)字，而不一定是單個(gè)字符； 2 同一個(gè)字可能出現(xiàn)在同狀態(tài)射出的多條弧上。DFA是NFA的特例。定義：對(duì)于任何兩個(gè)有限自動(dòng)機(jī)M和M，如果L(M)=L(M)，則稱M與M等價(jià)。自動(dòng)機(jī)理論中一個(gè)重要的結(jié)論：判定兩個(gè)自動(dòng)機(jī)等價(jià)性的算法是存在的。對(duì)于每個(gè)NFA M存在一個(gè)DFA M，使得 L(M)=L(M)。亦即DFA與NFA描述能力相同。1. 假定NFA M=<S, S, d, S0, F>，我們對(duì)M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造： 1) 引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y，

18、X,YÏS， 從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條e箭弧， 從F中任意狀態(tài)結(jié)點(diǎn)連一條e箭弧到Y(jié)。 2) 對(duì)M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換，其中k是新引入的狀態(tài)。逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為S上的一個(gè)字符或e，最后得到一個(gè)NFA M，顯然L(M)=L(M)識(shí)別所有含相繼兩個(gè)a或相繼兩個(gè)b的字2. 把上述NFA確定化采用子集法.設(shè)a是S中的一個(gè)字符，定義Ia= e-closure(J) 其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)集合。e-closure(1)=1，2=I J=5，4，3 Ia= e-closure(J)= e-closure(5，4，3) =5，4，3，6，2，7，

19、8把確定化的過程: 不失一般性，設(shè)字母表只包含兩個(gè)a和b，我們構(gòu)造一張表:現(xiàn)在把這張表看成一個(gè)狀態(tài)轉(zhuǎn)換矩陣，把其中的每個(gè)子集看成一個(gè)狀態(tài)。這張表唯一刻劃了一個(gè)確定的有限自動(dòng)機(jī)M，它的初態(tài)是e-closure(X) ，它的終態(tài)是含有原終態(tài)Y的子集。不難看出，這個(gè)DFA M與M等價(jià)。3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性對(duì)于正規(guī)文法G和有限自動(dòng)機(jī)M，如果L(G)L(M)，則稱G和M是等價(jià)的。關(guān)于正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性，有以下結(jié)論：3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理： 1.對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA) M，使得L(M)L(G)。 2.對(duì)每

20、一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。證明： 1. 對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都構(gòu)造一個(gè)有限自動(dòng)機(jī)（FA） M，使得L(M)L(G)。(1) 設(shè)右線性正規(guī)文法G=<VT, VN, S, P >。將VN中的每一非終結(jié)符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)新的終結(jié)狀態(tài)符號(hào)f，fÏVN。 令M=<VNf, VT, d, S, f>，其中狀態(tài)轉(zhuǎn)換函數(shù)d由以下規(guī)則定義：(a) 若對(duì)某個(gè)AÎVN及aÎVTe，P中有產(chǎn)生式Aa，則令d(A,a)=f(b) 對(duì)任意的AÎVN及a&

21、#206;VTe，設(shè)P中左端為A，右端第一符號(hào)為a的所有產(chǎn)生式為：AaA1|aAk （不包括Aa）， 則令d(A,a)=A1,Ak。 顯然，上述M是一個(gè)NFA。對(duì)于右線性正規(guī)文法G，在S w的最左推導(dǎo)過程中:· 利用A®aB一次就相當(dāng)于在M中從狀態(tài)A經(jīng)過標(biāo)記為a的箭弧到達(dá)狀態(tài)B（包括a=e的情形）;· 在推導(dǎo)的最后，利用A®a一次則相當(dāng)于在M中從狀態(tài)A經(jīng)過標(biāo)記為a的箭弧到達(dá)終結(jié)狀態(tài)f（包括a=e的情形）。綜上，在正規(guī)文法G中，S w的充要條件是：在M中，從狀態(tài)S到狀態(tài)f有一條通路，其上所有箭弧的標(biāo)記符號(hào)依次連接起來恰好等于w，這就是說，wÎL(

22、G)當(dāng)且僅當(dāng)wÎL(M)，故L(G)L(M)。(2) 設(shè)左線性正規(guī)文法G=<VT, VN, S, P>。將VN中的每一符號(hào)視為狀態(tài)符號(hào)，并增加一個(gè)初始狀態(tài)符號(hào)q0，q0ÏVN。 令M=<VNq0, VT, d, q0, S>，其中狀態(tài)轉(zhuǎn)換函數(shù)d由以下規(guī)則定義：(a) 若對(duì)某個(gè)AÎVN及aÎVTe，若P中有產(chǎn)生式A®a，則令d(q0,a)=A(b) 對(duì)任意的AÎVN及aÎVTe，若P中所有右端第一符號(hào)為A，第二個(gè)符號(hào)為a的產(chǎn)生式為：A1Aa, , AkAa， 則令d(A,a)=A1,Ak。與(1)類似，

23、可以證明L(G)L(M)。例:GR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1D從GR出發(fā)構(gòu)造NFA M = <A, B, C, D, f, 0, 1, d¢, A, f>，M的狀態(tài)轉(zhuǎn)換圖如右圖所示。顯然 L(M) = L(GR)。3.3.4 正規(guī)文法與有限自動(dòng)機(jī)的等價(jià)性定理： 1.對(duì)每一個(gè)右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個(gè)有限自動(dòng)機(jī)(FA) M，使得L(M)L(G)。 2.對(duì)每一個(gè)FA M，都存在一個(gè)右線性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。證明2：對(duì)每一個(gè)DFA M，都存在一個(gè)右線

24、性正規(guī)文法GR和左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。 設(shè)DFA M=<S, S, d, s0, F> (1) 若s0ÏF，我們令GR=<S, S, s0, P>，其中P是由以下規(guī)則定義的產(chǎn)生式集合：對(duì)任何aÎS及A,BÎS，若有d(A,a)=B，則： (a) 當(dāng)BÏF時(shí)，令A(yù)aB， (b) 當(dāng)BÎF時(shí)，令A(yù)a|aB。對(duì)任何wÎS*，不妨設(shè)w=a1ak，其中aiÎS (i=1,k)。若s0 w，則存在一個(gè)最左推導(dǎo)： s0Þa1A1Þa1a2A2ÞÞ

25、;a1aiAiÞa1ai+1Ai+1ÞÞa1ak因而，在M中有一條從s0出發(fā)依次經(jīng)過A1，Ak-1到達(dá)終態(tài)的通路，該通路上所有箭弧的標(biāo)記依次為a1,ak。反之亦然。所以，wÎL(GR)當(dāng)且僅當(dāng)wÎL(M)。q 現(xiàn)在考慮s0ÎF的情形： 因?yàn)閐(s0, e)=s0，所以eÎL(M)。但e不屬于上面構(gòu)造的GR所產(chǎn)生的語言L(GR)。不難發(fā)現(xiàn)，L(GR)=L(M)-e。 所以，我們?cè)谏鲜鯣R中添加新的非終結(jié)符號(hào)s0¢，(s0¢ÏS)和產(chǎn)生式s0¢®s0|e，并用s0¢代替

26、s0作開始符號(hào)。這樣修正GR后得到的文法GR¢仍是右線性正規(guī)文法，并且L(GR¢)=L(M)。 (2) 類似于(1)，從DFA M出發(fā)可構(gòu)造左線性正規(guī)文法GL，使得L(GL)=L(M)。 最后，由DFA和NFA之間的等價(jià)性，結(jié)論2得證。例3.4 設(shè)DFA M = <A, B, C, D, 0, 1, d, A, B>。M的狀態(tài)轉(zhuǎn)換圖如下圖所示。L(M) = 0(10)*GR = <0, 1, A, B, C, D, A, P>，其中P由下列產(chǎn)生式組成：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1DL(GR) = L(

27、M) = 0(10)*例3.4 設(shè)DFA M = <A, B, C, D, 0, 1, d, A, B>。M的狀態(tài)轉(zhuǎn)換圖如圖3.9(a)所示。從NFA M出發(fā)構(gòu)造左線性正規(guī)文法GL = <0, 1, B, C, D, f, f, P¢>，其中P¢由下列產(chǎn)生式組成：f0 | C0CB1B0 | C0D1 | C1 | D0 | D1 | B0易證 L(GL) = L(M)。3.3.5 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性定理： 1. 對(duì)任何FA M，都存在一個(gè)正規(guī)式r，使得L(r)=L(M)。 2. 對(duì)任何正規(guī)式r，都存在一個(gè)FA M，使得L(M)=L(r)。2

28、 對(duì)轉(zhuǎn)換圖概念拓廣，令每條弧可用一個(gè)正規(guī)式作標(biāo)記。(對(duì)一類輸入符號(hào))證明： 1 對(duì)S上任一NFA M，構(gòu)造一個(gè)S上的正規(guī)式r，使得L(r)=L(M)。首先，在M的轉(zhuǎn)換圖上加進(jìn)兩個(gè)狀態(tài)X和Y，從X用e弧連接到M的所有初態(tài)結(jié)點(diǎn)，從M的所有終態(tài)結(jié)點(diǎn)用e弧連接到Y(jié)，從而形成一個(gè)新的NFA，記為M，它只有一個(gè)初態(tài)X和一個(gè)終態(tài)Y，顯然L(M)=L(M)。然后，反復(fù)使用下面的一條規(guī)則，逐步消去的所有結(jié)點(diǎn)，直到只剩下X和Y為止；證明2: 對(duì)于S上的正規(guī)式r，構(gòu)造一個(gè)NFA M，使L(M)=L(r)，并且M只有一個(gè)終態(tài)，而且沒有從該終態(tài)出發(fā)的箭弧。 下面使用關(guān)于r中運(yùn)算符數(shù)目的歸納法證明上述結(jié)論。(1) 若r具

29、有零個(gè)運(yùn)算符，則r=e或r=f或r=a，其中aÎS。此時(shí)下圖所示的三個(gè)有限自動(dòng)機(jī)顯然符合上述要求。(2) 假設(shè)結(jié)論對(duì)于少于k(k³1)個(gè)運(yùn)算符的正規(guī)式成立。 當(dāng)r中含有k個(gè)運(yùn)算符時(shí)，r有三種情形：l 情形1：r=r1|r2，r1,r2中運(yùn)算符個(gè)數(shù)少于k。從而，由歸納假設(shè)，對(duì)ri存在Mi=<Si, Si, di, qi, fi>，使得L(Mi)=L(ri)，并且Mi沒有從終態(tài)出發(fā)的箭?。╥=1,2）。不妨設(shè)S1S2=f，在S1 S2中加入兩個(gè)新狀態(tài)q0，f0。 令M=<S1S2q0,f0, S1S2, d, q0, f0>，其中d定義如下：(a) d(

30、q0, e)=q1,q2(b) d(q,a)= d1(q,a), 當(dāng)qÎS1-f1, aÎS1e(c) d(q,a)= d2(q,a), 當(dāng)qÎS2-f2, aÎS2e(d) d(f1,e)=d(f2,e)=f0。 M的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)l 情形2：r=r1r2, 設(shè)Mi同情形1(i=1,2)。 令M=<S1S2, S1S2, d, q1, f2>，其中d定義如下：(a) d(q,a)= d1(q,a), 當(dāng)qÎS1-f1, aÎS1e(b) d(q,a)

31、= d2(q,a), 當(dāng)qÎS2, aÎS2e(c) d(f1,e)=q2 M的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。l 情形3：r=r1*。設(shè)M1同情形1。令M=<S1q0, f0, S1, d, q0, f0>，其中q0, f0ÏS1，d定義如下：(a) d(q0,e)=d(f1,e)=q1, f0(b) d(q,a)= d1(q, a), 當(dāng)qÎS1-f1, aÎS1e。M的狀態(tài)轉(zhuǎn)換如右圖所示。L(M) = L(M1)* = L(r1)* = L(r)至此，結(jié)論2獲證。1) 構(gòu)

32、造S上的NFA M 使得 L(V)=L(M)首先，把V表示成逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為S上的一個(gè)字符或e，最后得到一個(gè)NFA M，顯然L(M)=L(V)(a|b)*(aa|bb)(a|b)*3.3.6 確定有限自動(dòng)機(jī)的化簡(jiǎn)對(duì)DFA M的化簡(jiǎn):尋找一個(gè)狀態(tài)數(shù)比M少的DFA M，使得L(M)=L(M)假設(shè)s和t為M的兩個(gè)狀態(tài)，稱s和t等價(jià):如果從狀態(tài)s出發(fā)能讀出某個(gè)字a而停止于終態(tài)，那么同樣，從t出發(fā)也能讀出a而停止于終態(tài)；反之亦然。兩個(gè)狀態(tài)不等價(jià)，則稱它們是可區(qū)別的。對(duì)一個(gè)DFA M最少化的基本思想: 把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，而同一子集的任

33、何兩個(gè)狀態(tài)是等價(jià)的。最后，讓每個(gè)子集選出一個(gè)代表，同時(shí)消去其他狀態(tài)。具體做法: 對(duì)M的狀態(tài)集進(jìn)行劃分首先，把S劃分為終態(tài)和非終態(tài)兩個(gè)子集，形成基本劃分P。 假定到某個(gè)時(shí)候，P已含m個(gè)子集，記為P=I(1)，I(2)，¼，I(m)，檢查P中的每個(gè)子集看是否能進(jìn)一步劃分:對(duì)某個(gè)I(i)，令I(lǐng)(i)=s1,s2, ¼,sk，若存在一個(gè)輸入字符a使得Ia(i) 不會(huì)包含在現(xiàn)行P的某個(gè)子集I(j)中，則至少應(yīng)把I(i)分為兩個(gè)部分。例如，假定狀態(tài)s1和s2經(jīng)a弧分別到達(dá)t1和t2，而t1和t2屬于現(xiàn)行P中的兩個(gè)不同子集，說明有一個(gè)字a， t1讀出a后到達(dá)終態(tài)，而t2讀出a后不能到達(dá)終

34、態(tài)，或者反之，那么對(duì)于字aa ， s1讀出aa后到達(dá)終態(tài)，而s2讀出aa不能到達(dá)終態(tài)，或者反之，所以s1和s2不等價(jià)。則將I(i)分成兩半，使得一半含有s1 : I(i1)=s|sÎI(i)且s經(jīng)a弧到達(dá)t, 且t與t1屬于現(xiàn)行P中的同一子集 另一半含有s2 : I(i2)=I(i)-I(i1)一般地，對(duì)某個(gè)a和I(i)，若Ia(i) 落入現(xiàn)行P中 N個(gè)不同子集，則應(yīng)把I(i)劃分成N個(gè)不相交的組，使得每個(gè)組J的Ja都落入的P同一子集。這樣構(gòu)成新的劃分。重復(fù)上述過程，直到P所含子集數(shù)不再增長(zhǎng)。對(duì)于上述最后劃分P中的每個(gè)子集，我們選取每個(gè)子集I中的一個(gè)狀態(tài)代表其他狀態(tài)，則可得到化簡(jiǎn)后的

35、DFA M。若I含有原來的初態(tài)，則其代表為新的初態(tài)，若I含有原來的終態(tài)，則其代表為新的終態(tài)。3.4 詞法分析器的自動(dòng)產(chǎn)生-LEXAUXILIARY DEFINITIONletter®A|B|.|Zdigit ®0|1|.|9RECOGNITION RULES1DIM RETURN (1,-) 2IF RETURN (2,-) 3DO RETURN (3,-) 4STOP RETURN (4,-) 5END RETURN (5,-) 6letter(letter|digit) * RETURN (6, TOKEN) 7digit(digit)* RETURN (7, DTB)

36、 8= RETURN (8, -) 9+ RETURN (9,-) 10* RETURN (10,-) 11* RETURN (11,-) 12, RETURN (12,-) 13( RETURN (13,-) 14) RETURN (14,-) LEX的工作過程：首先，對(duì)每條識(shí)別規(guī)則Pi構(gòu)造一個(gè)相應(yīng)的非確定有限自動(dòng)機(jī)Mi；然后，引進(jìn)一個(gè)新初態(tài)X，通過e弧，將這些自動(dòng)機(jī)連接成一個(gè)新的NFA；最后，把M確定化、最小化，生成該DFA的狀態(tài)轉(zhuǎn)換表和控制執(zhí)行程序作業(yè)P64-7，8，12，14 例: 對(duì)下圖NFA M構(gòu)造其DFA.編譯原理第四章 語法分析自上而下分析第四章 語法分析自上而下分析本章主要介

37、紹語法分析的處理要進(jìn)行語法分析，必須對(duì)語言的語法結(jié)構(gòu)進(jìn)行描述。采用正規(guī)式和有限自動(dòng)機(jī)可以描述和識(shí)別語言的單詞符號(hào)；用上下文無關(guān)文法來描述語法規(guī)則。上下文無關(guān)文法的定義： 一個(gè)上下文無關(guān)文法G是一個(gè)四元式 G=(VT，VN，S，P)，其中VT：終結(jié)符集合(非空)VN：非終結(jié)符集合(非空)，且VT Ç VN=ÆS：文法的開始符號(hào)，SÎVNP：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為P®a， PÎVN， a Î (VT È VN)*開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。例，定義只含+，*的算術(shù)表達(dá)式的文法 G=<i，+，*

38、，(，)，E，E， P>， 其中，P由下列產(chǎn)生式組成：E ® iE ® E+EE ® E*EE ® (E)定義：稱aAb直接推出agb，即aAbÞagb 僅當(dāng)A ® g是一個(gè)產(chǎn)生式， 且a， bÎ (VT È VN)* 。如果a1 Þ a2 Þ ¼ Þan，則我們稱這個(gè)序列是從a1到an的一個(gè)推導(dǎo)。若存在一個(gè)從a1到an的推導(dǎo)，則稱a1可以推導(dǎo)出an 。例：對(duì)文法(1)E Þ (E) Þ (E+E)Þ (i+E)Þ (i+i)4.

39、1 語法分析器的功能語法分析的任務(wù)是分析一個(gè)文法的句子結(jié)構(gòu)。語法分析器的功能：按照文法的產(chǎn)生式(語言的語法規(guī)則)，識(shí)別輸入符號(hào)串是否為一個(gè)句子(合式程序)。語法分析的方法：自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進(jìn)行“歸約”，直到文法的開始符號(hào)。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號(hào)。n 算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進(jìn)行語法分析。適合分析表達(dá)式。n LR分析法：規(guī)范歸約G(E)： E ® i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i

40、 E+E En 語法分析的方法：¨ 自下而上分析法(Bottom-up)¨ 自上而下分析法(Top-down)n 基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找"匹配"的推導(dǎo)。n 遞歸下降分析法：對(duì)每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對(duì)輸入串的識(shí)別。n 預(yù)測(cè)分析程序F 優(yōu)點(diǎn)：直觀、簡(jiǎn)單和宜于手工實(shí)現(xiàn)。n 4.2 自上而下分析面臨的問題n 自上而下就是從文法的開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子。¨ 帶“回溯”的¨ 不帶回溯的遞歸子程序(遞歸下降)分析方

41、法。n 自上而下分析的主旨：對(duì)任何輸入串，試圖用一切可能的辦法，從文法開始符號(hào)(根結(jié)點(diǎn))出發(fā)，自上而下地為輸入串建立一棵語法樹?；蛘哒f，為輸入串尋找一個(gè)最左推導(dǎo)。n 例3.4.1 假定有文法G(S): (1) SxAy (2) A*|* 分析輸入串x*y(記為a)。n 當(dāng)某個(gè)非終結(jié)符有多個(gè)產(chǎn)生式候選時(shí)，可能帶來如下問題:1. 分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。出錯(cuò)時(shí)，不得不“回溯”。2. 文法左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符Pn 4.3 LL(1)分析法n 構(gòu)造不帶回溯的自上而下分析算法¨ 要消除文法的左遞歸性¨ 克

42、服回溯n 4.3.1 左遞歸的消除n 直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為PPa | b 其中b不以P開頭。 我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式：PbP¢P¢aP¢|en 一般而言，假定P關(guān)于的全部產(chǎn)生式是PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每個(gè)a都不等于e，每個(gè)b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P¢ | b2P¢ | | bnP¢P¢a1P¢ | a2P¢ | | amP¢ | en

43、例 文法G(E):EET | TTT*F | FF(E) | i經(jīng)消去直接左遞歸后變成： ETE¢ E¢+TE¢ | e TFT¢ T¢*FT¢ | e F(E) | in 例如文法G(S):SQc|cQRb|bRSa|a (4.3)雖沒有直接左遞歸，但S、Q、R都是左遞歸的SÞQcÞRbcÞSabcn 消除左遞歸的算法:1. 把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序執(zhí)行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPjg的

44、規(guī)則改寫成 Pid1g|d2g|dkg ; (其中Pjd1|d2|dk是關(guān)于Pj的所有規(guī)則) 消除關(guān)于Pi規(guī)則的直接左遞歸性 END3. 化簡(jiǎn)由2所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。n 例 考慮文法G(S)SQc|cQRb|bRSa|an 令它的非終結(jié)符的排序?yàn)镽、Q、S。n 對(duì)于R，不存在直接左遞歸。n 把R代入到Q的有關(guān)候選后，把Q的規(guī)則變?yōu)?QSab | ab | bn 例 考慮文法G(S)SQc|cQRb|bRSa|an 令它的非終結(jié)符的排序?yàn)镽、Q、S。n Q的規(guī)則變?yōu)?QSab | ab | bn 現(xiàn)在的Q不含直接左遞歸，把它代入到S的有關(guān)候選后，S

45、變成SSabc | abc | bc | cn 例 考慮文法G(S)SQc|cQRb|bRSa|an S變成SSabc | abc | bc | cn 消除S的直接左遞歸后：SabcS¢ | bcS¢ | cS¢S¢abcS¢ | eQSab |ab | bRSa|an 例 考慮文法G(S)SQc|cQRb|bRSa|an 消除S的直接左遞歸后：SabcS¢ | bcS¢ | cS¢S¢abcS¢ | eQSab |ab | bRSa|an 關(guān)于Q和R的規(guī)則已是多余的，化簡(jiǎn)為：SabcS

46、2; | bcS¢ | cS¢S¢abcS¢ | e (4.4)n 注意，由于對(duì)非終結(jié)符排序的不同，最后所得的文法在形式上可能不一樣。但不難證明，它們都是等價(jià)的。n 例如，若對(duì)文法(4.3)的非終結(jié)符排序選為S、Q、R，那么，最后所得的無左遞歸文法是：SQc | cQRb | bRbcaR¢ | caR¢ |a R¢ (4.5)R¢ bca R¢ | en 文法(4.4)和(4.5)的等價(jià)性是顯然的。n 4.3.2 消除回溯、提左因子n 為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，

47、能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。n Aa 1 | a 2 | | a nn 令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選a定義它的終結(jié)首符集FIRST(a)為：n 提取公共左因子: 假定關(guān)于A的規(guī)則是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每個(gè)g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nn 經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變

48、成為兩兩不相交。n 4.3.3 LL(1)分析條件n ETE¢ E¢+TE¢ | e TFT¢ T¢*FT¢ | e F(E) | in i + in 4.3.3 LL(1)分析條件n 假定S是文法G的開始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義n 對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為Aa 1 | a 2 | | a n1. 若aÎFIRST(a i)，則指派a i執(zhí)行匹配任務(wù)；2. 若a不屬于任何一個(gè)候選首符集，則： (1)

49、 若e屬于某個(gè)FIRST(ai )且 aÎFOLLOW(A)， 則讓A與e自動(dòng)匹配。 (2) 否則，a的出現(xiàn)是一種語法錯(cuò)誤。n 回顧：LL(1)分析法n 構(gòu)造不帶回溯的自上而下分析算法¨ 要消除文法的左遞歸性¨ 克服回溯n 一般而言，假定P關(guān)于的全部產(chǎn)生式是PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每個(gè)a都不等于e，每個(gè)b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P¢ | b2P¢ | | bnP¢P¢a1P¢ | a2P¢ | | amP¢

50、 | en 消除左遞歸的算法:1. 把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序執(zhí)行；2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPjg的規(guī)則改寫成 Pid1g|d2g|dkg ; (其中Pjd1|d2|dk是關(guān)于Pj的所有規(guī)則) 消除關(guān)于Pi規(guī)則的直接左遞歸性 END3. 化簡(jiǎn)由2所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。n 回顧：LL(1)分析法n 構(gòu)造不帶回溯的自上而下分析算法¨ 要消除文法的左遞歸性¨ 克服回溯n 4.3.2 消除回溯、提左因子n 為了消除回溯就必

51、須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。n Aa 1 | a 2 | | a nn 令G是一個(gè)不含左遞歸的文法，對(duì)G的所有非終結(jié)符的每個(gè)候選a定義它的終結(jié)首符集FIRST(a)為：n 提取公共左因子: 假定關(guān)于A的規(guī)則是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm (其中，每個(gè)g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nn 經(jīng)過反復(fù)提取左因子，就

52、能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。n FOLLOW定義n 假定S是文法G的開始符號(hào)，對(duì)于G的任何非終結(jié)符A，我們定義n 對(duì)于一個(gè)滿足上述條件的文法，可以對(duì)其輸入串進(jìn)行有效的無回溯的自上而下分析。假設(shè)要用非終結(jié)符A進(jìn)行匹配，面臨的輸入符號(hào)為a，A的所有產(chǎn)生式為Aa 1 | a 2 | | a n1. 若aÎFIRST(a i)，則指派a i執(zhí)行匹配任務(wù)；2. 若a不屬于任何一個(gè)候選首符集，則： (1) 若e屬于某個(gè)FIRST(ai )且 aÎFOLLOW(A)， 則讓A與e自動(dòng)匹配。 (2) 否則，a的出現(xiàn)是一種語法錯(cuò)誤。構(gòu)造FIRST(a)

53、n 對(duì)每一文法符號(hào)XÎVTVN構(gòu)造FIRST(X) 連續(xù)使用下面的規(guī)則，直至每個(gè)集合FIRST不再增大為止：1. 若XÎVT，則FIRST(X)X。2. 若XÎVN，且有產(chǎn)生式Xa，則把a(bǔ)加入到FIRST(X)中；若Xe也是一條產(chǎn)生式，則把e也加到FIRST(X)中。3. l 若XY是一個(gè)產(chǎn)生式且YÎVN，則把FIRST(Y)中的所有非e-元素都加到FIRST(X)中；l 若XY1Y2Yk是一個(gè)產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對(duì)于任何j，1£j£i-1，F(xiàn)IRST(Yj)都含有e(即Y1Yi-1e)， 則把FIRST(Yi)

54、中的所有非e-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有e，j1，2，k，則把e加到FIRST(X)中。n 對(duì)文法G的任何符號(hào)串a(chǎn)=X1X2Xn構(gòu)造集合FIRST(a)。1. 置FIRST(a)FIRST(X1)e；2. 若對(duì)任何1£j£i-1，eÎFIRST(Xj)，則把FIRST(Xi)e加至FIRST(a)中；特別是，若所有的FIRST(Xj)均含有e，1£j£n，則把e也加至FIRST(a)中。顯然，若ae則FIRST(a)e。構(gòu)造FOLLOW(A)n 對(duì)于文法G的每個(gè)非終結(jié)符A構(gòu)造FOLLOW(A)的辦法是，連續(xù)使用下面的規(guī)則，直至每個(gè)FOLLOW不再增大為止：1. 對(duì)于文法的開始符號(hào)S，置于FOLLOW(S)中；2. 若AaBb是一個(gè)產(chǎn)生式，則把FIRST(b)e加至FOLLOW(B)中；n 例4.6 對(duì)于文法G(E)ETE¢E¢+TE¢ | eTFT¢ T¢*FT¢ | eF(E) | i構(gòu)造每個(gè)非終結(jié)符的FIRST和FOLLOW集合：n 4.4 遞歸下降分析程序構(gòu)造n 構(gòu)造不帶回溯的自上而下分析程序¨ 要消除文法的左遞歸性¨ 克服回溯n 構(gòu)造不帶回溯的自上而下分析器n