編譯原理例題與習題解答.ppt

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

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

3、位,故需另引入一 非終結符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)的最左推導和最右推導。,解：此處僅以 i*(i+i) 為例給出答案,最左推導 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),最右推導 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 的語法樹,注意：樹枝和符號均不可隨意增減！,18,9、證明文法: S iSeS | iS | i 是二義的。,二義性的含義:,如果文法存在某個句子對應兩棵以上 不同的語法樹，或者兩種以上不同的最 左/右推導，則稱這個文法是二義的。,

5、首先：找到此文法對應的一個句子 iiiei,其次：構造與之對應的兩棵語法樹,結論：因為該文法存在句子iiiei對應兩棵 不同的語法樹，因而該文法是二義的。,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、給出下面語言的相應文法,21,L4=1n 0m 1m 0n| n,m0,可以看成是兩部分：,剩下兩邊的部分就是：,S 1S0,中間部分是

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

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

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

9、能到達終態(tài)，或者反之，那么對于字a ， s1讀出a后到達終態(tài)，而s2讀出a不能到達終態(tài)，或者反之，所以s1和s2不等價。,s1,t1,a,s2,t2,a,i,j,30,例題3.1,給出下面描述的正規(guī)表達式 以01結尾的二進制數(shù)串 能被5正除的十進制整數(shù) 包含奇數(shù)個1或者奇數(shù)個0的二進制數(shù)串,31,例題3.2,構造下面正規(guī)式相應的DFA 1(0|1)*101,步驟:,.根據(jù)正規(guī)式畫出對應的狀態(tài)轉換圖;,.根據(jù)狀態(tài)轉換圖畫出對應的狀態(tài)轉換矩陣;,.根據(jù)狀態(tài)轉換矩陣得到重命名后的狀態(tài)轉換矩陣;,.根據(jù)重命名后的狀態(tài)轉換矩陣得出最后的DFA.,32,1(0|1)*101,.狀態(tài)轉換圖,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)轉換矩陣,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)轉換矩陣,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,設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 請構造對應的確定有限自動機。,36,【解答】 對照自動機的定義，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動機。 先畫出NFA M相應的狀態(tài)圖，,37,用子集法構造狀態(tài)轉換矩陣,38,重命名后的狀態(tài)轉換矩陣,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)轉換圖,P64-7. 構造下列正規(guī)式相應的DFA。,41,.狀態(tài)轉換矩陣,42,.重命名后的狀態(tài)轉換矩陣,.D

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

13、0,1,1,0,.重命名后的狀態(tài)轉換矩陣,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),這道題實質上已經(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等價,2，4a=0，1 2，4b=3，5,所以2，4等價,3，5a=3，5 3，5b=2，4,所以3，5等價,所以分為 0，1 2，4 3，5,47,P64-14. 構造一個DFA，它接受0,1上所有

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

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

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

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

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

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

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

21、個非終結符，則查看分析表M。 若MX，a中存放著關于X的一個產(chǎn)生式，把X逐出STACK棧頂，把產(chǎn)生式的右部符號串按反序一一推進STACK棧(若右部符號為，則意味不推什么東西進棧)。 若MX，a中存放著“出錯標志”，則調用出錯診察程序ERROR。,如：MX，a=XUVW,就用WVU（U在頂）替換棧頂?shù)腦作為輸出； 如：MX，a=error，則調用error程序。,68,1.考慮下面文法G1: Sa|(T) TT，S|S (1) 消去G1的左遞歸。然后對每個非終結符,寫出不帶回溯的遞歸子程序。,解(1) 消左后的文法G1: Sa|(T) TST T ,ST|,練習解答,解(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)的? 給出它的預測分析表。 消左后的文法G1 : Sa|(T) TST T ,ST|,因為G1 : 文法不含左遞歸; 對 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,構造G1的預測分析表: 對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）計算這個文法的每個非終結符的FIRST集和FOLLOW集。 （2）證明這個文法是LL（1）的。 （3）構造它的預測分析表。 （4）構造它的遞歸下降分析程序。,74,解：（1）計算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）證明這個文法是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）構造預測分析表。,78,（1）設置過程advance為讀下一個單詞送全程變量 （2）設置過程error為錯誤處理程序,1. 主程序 Begin advance; E; End 2. E過程 Procedure E Begin T;E; end,（4）構造遞歸下降分析程序。,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;