編譯原理例題與習(xí)題解答.ppt

1、1,例題與習(xí)題解答第二章,2,回顧,程序語言的定義 一個(gè)程序語言是一個(gè)記號(hào)系統(tǒng),它主要由以下方面定義： 語法 語義,語法,語義,3,語法=詞法規(guī)則+語法規(guī)則,詞法規(guī)則：單詞符號(hào)的形成規(guī)則。 單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。 描述工具：正規(guī)式和有限自動(dòng)機(jī)理論 語法規(guī)則：語法單位的形成規(guī)則。 語法單位通常包括：表達(dá)式、語句、子程序、過程、函數(shù)、程序等; 描述工具：上下文無關(guān)文法,回顧,4,標(biāo)識(shí)符與名字,標(biāo)識(shí)符：以字母開頭的，由字母數(shù)字組成的字符串。 標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別： 標(biāo)識(shí)符是語法概念 名字有確切的意義和屬性,回顧,5,上下文無關(guān)文

2、法的定義：一個(gè)上下文無關(guān)文法G是一個(gè)四元式G=(VT，VN，S，P)，其中 VT：終結(jié)符集合(非空) VN：非終結(jié)符集合(非空)，且VT VN= S：文法的開始符號(hào)，SVN P：產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式形式為 P， PVN， (VT VN)* 開始符S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。,回顧,6,假定G是一個(gè)文法，S是它的開始符號(hào)。如果S ，則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。 文法G所產(chǎn)生的句子的全體是一個(gè)語言，將它記為L(G) L(G) = | S 中間部分可出現(xiàn)任意多位數(shù)字09, 每一位用非終結(jié)符D表示; 最低位只出現(xiàn)1,3,5,7,9, 用A表示。 由于中間部分可任意

3、位,故需另引入一 非終結(jié)符M,它包括最高位和中間部分。,14,15,解: 奇數(shù)集文法GN為: G=(0,1,9,N,A,M,B,D,N,) : NA | MA MB | MD A1 | 3 | 5 | 7 | 9 B1|2|3|4|5|6|7|8|9 D0 | B,8. 令文法為 E T|E+T|E-T T F|T*F|T/F F (E)|i,(1) 給出 i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo)。,解：此處僅以 i*(i+i) 為例給出答案,最左推導(dǎo) E T T*F F*F i*F i*(E) i*(E+T) i*(T+T) i*(F+T) i*(i+T) i*(i+F ) i*(i+

4、i),最右推導(dǎo) E T T*F T*(E) T*(E+T) T*(E+F) T*(E+i) T*(T+i) T*(F+i) T*(i+i) F*(i+i) i*(i+i),8. 令文法為 E T|E+T|E-T T F|T*F|T/F F (E)|i,i-i-i 的語法樹,(2) 給出 i+i+i、i+i*i和i-i-i的語法樹。,i+i+i 的語法樹,i+i*i 的語法樹,注意：樹枝和符號(hào)均不可隨意增減！,18,9、證明文法: S iSeS | iS | i 是二義的。,二義性的含義:,如果文法存在某個(gè)句子對應(yīng)兩棵以上 不同的語法樹，或者兩種以上不同的最 左/右推導(dǎo)，則稱這個(gè)文法是二義的。,

5、首先：找到此文法對應(yīng)的一個(gè)句子 iiiei,其次：構(gòu)造與之對應(yīng)的兩棵語法樹,結(jié)論：因?yàn)樵撐姆ù嬖诰渥觟iiei對應(yīng)兩棵 不同的語法樹，因而該文法是二義的。,19,10. 把下面文法改寫成無二義性的文法 S-SS | (S) | ( ) 解答： S- TS | T T-(S) | ( ),20,L2=aibncn| n1,i0,G2(S): SAB AaA| BbBc|bc,L3=anbnambm| m,n0,G3(S): SAB AaAb| BaBb|,11、給出下面語言的相應(yīng)文法,21,L4=1n 0m 1m 0n| n,m0,可以看成是兩部分：,剩下兩邊的部分就是：,S 1S0,中間部分是

6、 0m 1m ：,A 0A1 | ,所以G4S可以寫為：,S 1S0 | A A 0A1 |,| A,22,例題與習(xí)題解答第三章,23,1. 假定NFA M=，我們對M的狀態(tài)轉(zhuǎn)換圖進(jìn)行以下改造： 1) 引進(jìn)新的初態(tài)結(jié)點(diǎn)X和終態(tài)結(jié)點(diǎn)Y，X,YS， 從X到S0中任意狀態(tài)結(jié)點(diǎn)連一條箭弧， 從F中任意狀態(tài)結(jié)點(diǎn)連一條箭弧到Y(jié)。 2) 對M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行替換，其中k是新引入的狀態(tài)。,非確定有限自動(dòng)機(jī)狀態(tài)圖的改造,24,代之為,代之為,代之為,按下面的三條規(guī)則對V進(jìn)行分裂:,逐步把這個(gè)圖轉(zhuǎn)變?yōu)槊織l弧只標(biāo)記為上的一個(gè)字符或，最后得到一個(gè)NFA M，顯然L(M)=L(M),25,確定有限自動(dòng)機(jī)的確定化

7、采用子集法,設(shè)I是M的狀態(tài)集的一個(gè)子集，定義I的-閉包-closure(I)為: i) 若sI，則s-closure(I)； ii) 若sI，則從s出發(fā)經(jīng)過任意條弧而能到達(dá)的任何狀態(tài)s都屬于-closure(I) 即： -closure(I)=Is|從某個(gè)sI出發(fā)經(jīng)過任意條弧能到達(dá)s,26,設(shè)a是中的一個(gè)字符，定義 Ia= -closure(J) 其中，J為I中的某個(gè)狀態(tài)出發(fā)經(jīng)過一條a弧而到達(dá)的狀態(tài)集合。,把確定化的過程: 不失一般性，設(shè)字母表只包含兩個(gè)a和b，我們構(gòu)造一張表:,27,對一個(gè)DFA M最少化的基本思想: 把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個(gè)不同子集的狀態(tài)是可區(qū)別的，

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

9、能到達(dá)終態(tài)，或者反之，那么對于字a ， s1讀出a后到達(dá)終態(tài)，而s2讀出a不能到達(dá)終態(tài)，或者反之，所以s1和s2不等價(jià)。,s1,t1,a,s2,t2,a,i,j,30,例題3.1,給出下面描述的正規(guī)表達(dá)式 以01結(jié)尾的二進(jìn)制數(shù)串 能被5正除的十進(jìn)制整數(shù) 包含奇數(shù)個(gè)1或者奇數(shù)個(gè)0的二進(jìn)制數(shù)串,31,例題3.2,構(gòu)造下面正規(guī)式相應(yīng)的DFA 1(0|1)*101,步驟:,.根據(jù)正規(guī)式畫出對應(yīng)的狀態(tài)轉(zhuǎn)換圖;,.根據(jù)狀態(tài)轉(zhuǎn)換圖畫出對應(yīng)的狀態(tài)轉(zhuǎn)換矩陣;,.根據(jù)狀態(tài)轉(zhuǎn)換矩陣得到重命名后的狀態(tài)轉(zhuǎn)換矩陣;,.根據(jù)重命名后的狀態(tài)轉(zhuǎn)換矩陣得出最后的DFA.,32,1(0|1)*101,.狀態(tài)轉(zhuǎn)換圖,a,b,a,d,

10、b,1(0|1)*101,a,1,(0|1)*,101,d,c,e,f,1,0,1,1,0,1,33,.狀態(tài)轉(zhuǎn)換矩陣,I,I0,I1,a,b,c,d,b,c,d,c,d,c,d,e,c,d,c,d,c,d,e,c,d,e,c,d,f,c,d,e,c,d,f,c,d,c,d,e,g,c,d,e,g,c,d,f,c,d,e,34,.重命名后的狀態(tài)轉(zhuǎn)換矩陣,S,0,1,A(始態(tài)),B,B,C,D,C,C,D,D,E,D,E,C,F(終態(tài)),F(終態(tài)),E,D,A,B,1,0,C,1,D,0,1,0,E,1,0,1,0,1,.DFA,35,例題3.3,設(shè)M=(x,y, a,b, f, x, y)，其中

11、f定義如下： f(x,a)=x, y f(x,b)=y f(y,a)= f(y,b)=x,y 請構(gòu)造對應(yīng)的確定有限自動(dòng)機(jī)。,36,【解答】 對照自動(dòng)機(jī)的定義，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。 先畫出NFA M相應(yīng)的狀態(tài)圖，,37,用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣,38,重命名后的狀態(tài)轉(zhuǎn)換矩陣,39,40,1(1010*|1(010)*1)*0,a,b,d,c,1,0,0,1,0,1,f,g,h,i,0,1,1,1,0,j,k,l,m,n,.狀態(tài)轉(zhuǎn)換圖,P64-7. 構(gòu)造下列正規(guī)式相應(yīng)的DFA。,41,.狀態(tài)轉(zhuǎn)換矩陣,42,.重命名后的狀態(tài)轉(zhuǎn)換矩陣,.D

12、FA,43,8、給出下面正規(guī)表達(dá)式,（4）英文字母組成的所有符號(hào)串，要求符號(hào)串中的 字母按字典序排列。,(A | a)* (B | b)* (C | c)* (Z | z)*,（5）沒有重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串的全體。,令 ri = i | , i=0,1,2,.,9 R0|R1|R2|.|R9記為 P(0,1,2.,9)表示0,1,2.,9的全排列,44,（6）最多有一個(gè)重復(fù)出現(xiàn)的數(shù)字的數(shù)字符號(hào)串全體,(7) 不包含子串a(chǎn)bb 的由a和b組成的符號(hào)串的全體,b*(a|ab)*,45,12、將圖3.18的(a)和(b)分別確定化和最少化。,(a),.狀態(tài)轉(zhuǎn)換矩陣,0,0,1,1,1,0,1,

13、0,1,1,0,.重命名后的狀態(tài)轉(zhuǎn)換矩陣,0,1,2,2,1,1,2,0,a,2,b,a,b,a,.DFA,.最小化,0=(0,1,2),0,1a=1,0,1b=2,因此，不能再分,2,b,a,a,46,(b),這道題實(shí)質(zhì)上已經(jīng)是確定化了的，所以我們只需最小化,：2，3，4，5 0，1,2，3，4，5a=0，1，3，5,分屬兩區(qū)，所以分為2，4 3，5,0，1a=1 0，1b=2，4,所以 0，1等價(jià),2，4a=0，1 2，4b=3，5,所以2，4等價(jià),3，5a=3，5 3，5b=2，4,所以3，5等價(jià),所以分為 0，1 2，4 3，5,47,P64-14. 構(gòu)造一個(gè)DFA，它接受0,1上所有

14、滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。,思路：先寫出滿足條件的正規(guī)式，由正規(guī)式構(gòu)造NFA，再把NFA確定化和最小化。,48,(1)先寫出滿足條件的正規(guī)式正規(guī)式: (10|0)* (2) NFA: 確定化:,DFA:,49,DFA:,DFA:(最簡化),50,例題與習(xí)題解答第四章,51,.,語法分析器在編譯程序中的地位,52,自上而下分析法(Top-down),基本思想：它從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找匹配的推導(dǎo)。 遞歸下降分析法：對每一語法變量(非終結(jié)符)構(gòu)造一個(gè)相應(yīng)的子程序，每個(gè)子程序識(shí)別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實(shí)現(xiàn)對輸入串的識(shí)別。 預(yù)測分析

15、程序 優(yōu)點(diǎn)：直觀、簡單和宜于手工實(shí)現(xiàn)。,53,困難和難點(diǎn): 分析過程中，當(dāng)一個(gè)非終結(jié)符用某一個(gè)候選匹配成功時(shí)，這種匹配可能是暫時(shí)的。 出錯(cuò)時(shí)，不得不“回溯”。 文法左遞歸問題。一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P 含有左遞歸的文法將使自上而下的分析陷入無限循環(huán)。,54,左遞歸的消除,直接消除見諸于產(chǎn)生式中的左遞歸：假定關(guān)于非終結(jié)符P的規(guī)則為 PP | 其中不以P開頭。 我們可以把P的規(guī)則等價(jià)地改寫為如下的非直接左遞歸形式： PP PP|,左遞歸變右遞歸,55,間接左遞歸 例如文法G(S): SQc|c QRb|b RSa|a 雖沒有直接左遞歸，但S、Q、R都是左遞歸的 SQcRbcSab

16、c 潛在左遞歸 即形如：N-N 而 ,56,消除左遞歸的算法: 1. 把文法G的所有非終結(jié)符按任一種順序排列成P1，P2，Pn；按此順序執(zhí)行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 將Pj代入Pi的產(chǎn)生式（若可代入的話） 消除關(guān)于Pi規(guī)則的直接左遞歸性 END 3. 化簡由2所得的文法。去除那些從開始符號(hào)出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生規(guī)則。,57,消除回溯、提左因子,為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無疑的。,58,令G

17、是一個(gè)不含左遞歸的文法，對G的所有非終結(jié)符的每個(gè)候選定義它的終結(jié)首符集FIRST()為：,特別是，若 ，則規(guī)定FIRST()。,如果非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選 i和 j FIRST(i)FIRST( j) 當(dāng)要求A匹配輸入串時(shí)，A就能根據(jù)它所面臨的第一個(gè)輸入符號(hào)a，準(zhǔn)確地指派某一個(gè)候選前去執(zhí)行任務(wù)。這個(gè)候選就是那個(gè)終結(jié)首符集含a的。,59,如何把一個(gè)文法改造成任何非終結(jié)符的所有侯選式的首符集兩兩不相交？ 提取公共左因子: 假定關(guān)于A的規(guī)則是 A 1 | 2 | | n | 1 | 2 | | m (其中，每個(gè) 不以開頭) 那么，可以把這些規(guī)則改寫成 AA |

18、1 | 2 | | m A 1 | 2 | | n 經(jīng)過反復(fù)提取左因子，就能夠把每個(gè)非終結(jié)符(包括新引進(jìn)者)的所有候選首符集變成為兩兩不相交。,60,構(gòu)造不帶回溯的自上而下分析的文法條件 1. 文法不含左遞歸， 2. 對于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1| 2| n 則 FIRST( i)FIRST( j) (ij) 3. 對文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含，則 FIRST(i)FOLLOW(A)= i=1,2,.,n 如果一個(gè)文法G滿足以上條件，則稱該文法G為LL(1)文法。,LL(1)文法,61,假定S是文法G的開始符號(hào)，對于G的任

19、何非終結(jié)符A，我們定義,特別是，若 ，則規(guī)定 FOLLOW(A),FOLLOW,提醒：要掌握構(gòu)造First和Follow集合的方法,62,遞歸下降分析程序構(gòu)造,在不含左遞歸和每個(gè)非終結(jié)符的所有候選式的終結(jié)首符集都兩兩不相交條件下，構(gòu)造一個(gè)不帶回溯的自上而下分析程序，該分析程序由一組遞歸過程組成，每個(gè)過程對應(yīng)文法的一個(gè)非終結(jié)符。 這樣的一個(gè)分析程序稱為遞歸下降分析器。,63,預(yù)測分析程序,使用一張分析表和一個(gè)棧同樣可實(shí)現(xiàn)遞歸下降分析，用這種方法實(shí)現(xiàn)的語法分析程序叫預(yù)測分析程序, a ,總控程序,預(yù)測分析表M,X #,輸 出,棧,輸入串,64,分析表MA，a的構(gòu)造,構(gòu)造FIRST()和FOLLOW

20、(A) 構(gòu)造分析表MA，a,65,在對文法G的每個(gè)非終結(jié)符A及其任意候選都構(gòu)造出FIRST()和FOLLOW(A)之后，現(xiàn)在可以用它們來構(gòu)造G的分析表MA，a。 1. 對文法G的每個(gè)產(chǎn)生式A執(zhí)行第2步和第3步； 2. 對每個(gè)終結(jié)符a FIRST()，把A加至MA，a中； 3. 若FIRST()，則對任何bFOLLOW(A)把A加至MA，b中。 4. 把所有無定義的MA，a標(biāo)上“出錯(cuò)標(biāo)志”。,66,總控程序根據(jù)現(xiàn)行棧頂符號(hào)X和當(dāng)前輸入符號(hào)a，執(zhí)行下列三種動(dòng)作之一: 1. 若Xa，則宣布分析成功，停止分析。 2. 若Xa ，則把X從STACK棧頂逐出，讓a指向下一個(gè)輸入符號(hào)。,67,3. 若X是一

21、個(gè)非終結(jié)符，則查看分析表M。 若MX，a中存放著關(guān)于X的一個(gè)產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號(hào)串按反序一一推進(jìn)STACK棧(若右部符號(hào)為，則意味不推什么東西進(jìn)棧)。 若MX，a中存放著“出錯(cuò)標(biāo)志”，則調(diào)用出錯(cuò)診察程序ERROR。,如：MX，a=XUVW,就用WVU（U在頂）替換棧頂?shù)腦作為輸出； 如：MX，a=error，則調(diào)用error程序。,68,1.考慮下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左遞歸。然后對每個(gè)非終結(jié)符,寫出不帶回溯的遞歸子程序。,解(1) 消左后的文法G1: Sa|(T) TST T ,ST|,練習(xí)解答,解(1) 不帶回溯的遞歸子程

22、序: Sa|(T) Procedure S; Begin if sym=a or sym= then advance else if sym=( then begin advance; T; if sym=) then advance else error end else error End;,解(1) 不帶回溯的遞歸子程序: TST Procedure T; Begin S; T; end;,解(1) 不帶回溯的遞歸子程序: T,ST| procedure T; begin if sym=, then begin advance; S; T; end End;,(2) 經(jīng)改寫后的文法是否是

23、LL(1)的? 給出它的預(yù)測分析表。 消左后的文法G1 : Sa|(T) TST T ,ST|,因?yàn)镚1 : 文法不含左遞歸; 對 Sa|(T) FIRST(a)=a, FIRST()=, FIRST( (T) )= ( , 集合互不相交且不含; 對 T,ST| FIRST( ,ST )= , , FIRST()=, 其交集為空。 但FIRST(T)=FIRST( ,ST ) FIRST()=，, 然而，F(xiàn)OLLOW(T)= ) FIRST(T)=，, ，兩者 不相交。 所以，G1是LL(1)文法。,72,構(gòu)造G1的預(yù)測分析表: 對Sa|(T) 對TST FIRST(a)=a FIRST(ST

24、)=a,( FIRST()= 對 T,ST| FIRST(T)=( FIRST(,ST)=, FOLLOW(T)=),73,2、對下面的文法G： ETE EE TFT TT FPF F*F P(E)ab （1）計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。 （2）證明這個(gè)文法是LL（1）的。 （3）構(gòu)造它的預(yù)測分析表。 （4）構(gòu)造它的遞歸下降分析程序。,74,解：（1）計(jì)算FIRST與FOLLOW集 FIRST(P)= ( , a , b , FIRST(F)= * , FIRST(F)=FIRST(P) = ( , a , b , FIRST(T)=FIRST(T)= ( , a

25、 , b , , FIRST(T)=FIRST(F) = ( , a , b , FIRST(E)= + , FIRST(E)=FIRST(T)= ( , a , b , FOLLOW(E)= ) , # FOLLOW(E)=FOLLOW(E)= ) , # FOLLOW(T)=FIRST(E) FOLLOW(E)=+, ) , # FOLLOW(T)=FOLLOW(T)=+, ) , # FOLLOW(F)=FIRST(T) FOLLOW(T)= (,a,b, , +, ) , # FOLLOW(F)=FOLLOW(F)=(, a , b , , +, ) , # FOLLOW(P)=FIR

26、ST(F) FOLLOW(F)=*,( ,a, b ,+ , ) ,# ,ETE EE TFT TT FPF F*F P(E)ab,75,76,（2）證明這個(gè)文法是LL（1）的。 對產(chǎn)生式P(E)ab，有 FIRST(E)FISRT(a) FIRST(b) FIRST()= 對產(chǎn)生式EE FIRST(+E) FOLLOW(E)= + ) , # = 對產(chǎn)生式TT FIRST(T) FOLLOW(T)= ( , a , b , +, ) , # = 對產(chǎn)生式F*F FIRST（*F) FOLLOW(F)= * (, a , b , , +, ) , # = 文法不含左遞歸。 綜上 i,ii,ii

27、i 可知，文法G是LL（1）的。,ETE EE TFT TT FPF F*F P(E)ab,77,（3）構(gòu)造預(yù)測分析表。,78,（1）設(shè)置過程advance為讀下一個(gè)單詞送全程變量 （2）設(shè)置過程error為錯(cuò)誤處理程序,1. 主程序 Begin advance; E; End 2. E過程 Procedure E Begin T;E; end,（4）構(gòu)造遞歸下降分析程序。,ETE EE TFT TT FPF F*F P(E)ab,79,3. E過程 Procedure E Begin if sym=+ then begin advance; E; end else if sym in #,) return else error,ETE EE TFT TT FPF F*F P(E)ab,80,4. T過程 Procedure T Begin F;T;