1、編譯原理練習1,王金偉 計算機與信息工程學院 天津師范大學,練習1.1基本概念,編譯程序的結構 上下文無關文法的一些概念 詞法分析 語法分析 自上而下 自下而上,1.填充下面編譯程序總框圖,源程序,目標程序,( 字符串),詞法分析器,語法分析器,語義分析和中間代碼生成器,代碼優(yōu)化器,目標代碼生成器,表 格 管 理,出 錯 處 理,對于上的每一個正規(guī)式V，存在一個上的DFA M，使得L(M) = L(V) 問題：如何由一個正規(guī)式V，構造一個DFA M 思路：分兩步走 1.根據V，構造一個NFA M，使得L(M) = L(V) 2.將M確定化，變?yōu)镈FA M 第一步，在上構造一個NFA M (1)

2、構造一個拓廣的轉換圖,練習1.2 詞法分析,(2)使用分裂規(guī)則對V進行分裂，加進新結點，直到把圖轉換成每條弧上標識為上的一個字符或 最后得到一個NFA M 且L(M) = L(V),第二步，把M確定化 (1)兩個概念 定義1：假定I是M的狀態(tài)集的子集，定義I的閉包_CLOSURE(I)為： (a)若qI，則q_CLOSURE(I) (b)若qI，那么從q出發(fā)經任意條弧而能到達的任何狀態(tài)q都屬于_CLOSURE(I) ； 定義2：假定I是M的狀態(tài)集的子集，定義 Ia =_CLOSURE(J) 其中，J是所有那些可從I中的某一狀態(tài)結點出發(fā)經過一條a弧而到達的狀態(tài)結點的全體,例：有如下一個狀態(tài)轉換圖

3、 假定 I=1, 2，求Ia = ？ 解： Ia =_CLOSURE(J) J = _CLOSURE(J) = Ia=5, 6, 2, 4, 7, 3, 8,1,a,5,4,3,8,2,6,7,a,a,4,5,3,5,6,2,4,7,3,8,(2)用子集法把M確定化 設 = a，b 構造一張表,集合1,集合1,集合1,集合2,集合2,集合2,集合3,集合3,集合3,集合4,集合4,集合4,_CLOSURE(X),把得到的每個集合看成一個狀態(tài)，得到一張狀態(tài)轉換表，該表的初態(tài)就是_CLOSURE(X)，它的終態(tài)是那些含有終態(tài)Y的子集，這樣就得到一個DFA M 且L(M) = L(M),1.構造下列

4、正規(guī)式相應的DFA。 (1) 1(0|1)*101 (2) 0*10*10*10*, ,(1)1(0|1)*101,得到一個NFA M 且 L(M) = L(V),用子集法對M進行確定化 構造一張表,-,J=1,X,1, 2, 3,-,2, 3,2, 3,2, 3, 4,1, 2, 3,2, 3,2, 3, 4,2, 3, 5,2, 3, 4,2, 3, 4,J=2,J=2, 4,J=2,J=2, 4,J=2, 5,J=2, 4,2, 3, 5,2, 3,2, 3, 4,Y,2, 3, 4, Y,2, 3, 5,2, 3, 4,J=2,J=2, 4, Y,J=2, 5,J=2, 4,把每個子集

5、看成一個狀態(tài)，得到一個DFA M， 且L(M) = L(M),0,1,2,3,2,3,3,2,4,3,4,5,1,5,3,2,4,把DFA M進行化簡 解: 把M狀態(tài)集分為兩組: 終態(tài)結點5 非終態(tài)結點0，1，2，3，4 考察0，1，2，3，4 因為， 0，1，2，3，40 = 0，1，2，3，41 = 所以， 0，1，2，3，4可再分，分成0,1,2,3和4 考察0，1，2, 3 因為， 0,1,2,30 = 所以， 0,1,2,3必可再分 看圖，把0,1,2,3分割為0,1,2和3,2,4,1,3,5,0,1,2,3,4,0,1,2,3,4,J=2,4,J=1,3,5,2，4,0，1，2，

6、3,J=2,4,考察0,1,2 因為， 0,1,20 = 0,1,21 = 所以， 0,1,2必可再分 看圖，把0,1,2分割為0， 1,2 考察1,2 因為， 1,20 = 1,21 = 所以1,2不可再分,J=2,J=1,3,2,0,1,2,1,3,0,1,2,J=2,J=3,2,1,2,3,3,所以， 最終把M分割為0， 1,2 ， 3 ， 4 ， 5 用狀態(tài)2代替狀態(tài)1，把引向狀態(tài)1的箭弧都引向狀態(tài)2，把1消去，得到一個DFA M, ,(2) 0*10*10*10*,得到一個NFA M 且 L(M) = L(V),J=0,X,0,1,0,1,0,1,3,4,2,3,4,2,3,4,2,

7、3,4,0,1,3,4,3,4,5,6,7,5,6,7,J=3,J=5,J=0,J=8,J=3,J=2,5,6,7,6,7,8,9,Y,6,7,6,7,8,9,Y,J=6,J=5,J=6,J=8,J=2,8,9,Y,J=9,9,Y,9,Y,-,J=9,9,Y,-,X,0,1,0,1,0,1,3,4,2,3,4,2,3,4,2,3,4,0,1,3,4,3,4,5,6,7,5,6,7,5,6,7,6,7,8,9,Y,6,7,6,7,8,9,Y,8,9,Y,9,Y,9,Y,-,9,Y,-,把每個子集看成一個狀態(tài)，得到一個DFA M， 且L(M) = L(M),0,1,2,3,4,5,6,7,1,1,

8、3,3,5,5,7,7,2,2,4,4,6,6,(3) 例:把DFA M進行化簡 解: 把M狀態(tài)集分為兩組: 終態(tài)結點6,7 非終態(tài)結點0,1,2,3,4,5 考察6,7 因為， 6,70 = 6,71 = 所以， 6,7不可再分； 考察0,1,2,3,4,5 因為， 0,1,2,3,4,50 = 0,1,2,3,4,51 = 看圖，把0,1,2,3,4,5分割為0,1,2,3和4,5,7, ,6,7,6,7,J=7,1,3,5,0,1,2,3,4,5,J=1,3,5,2,4,6,0,1,2,3,4,5,J=2,4,6,考察4,5 因為， 4,50 = 4,51 = 所以， 4,5 不可再分

9、考察0,1,2,3 因為， 0,1,2,30 = 0,1,2,31 = 所以0,1,2,3可再分 看圖，把0,1,2,3分割為0,1和2,3,J=5,J=6,5,4,5,6,6,7,J=1,3,J=2,4,1,3,0,1,2,3,2,4,0,1,2,3,4,5,6,7,考察2,3 因為， 2,30 = 2,31 = 所以， 2,3 不可再分 考察0,1 因為， 0,10 = 0,11 = 所以， 0,1 不可再分,J=3,J=4,3,2,3,4,4,5,J=1,J=2,1,0,1,2,2,3,所以， 最終把M分割為0,1， 2,3 ， 4,5 ， 6,7 用狀態(tài)1代替狀態(tài)0，把引向狀態(tài)0的箭弧

10、都引向狀態(tài)1，把0消去；,用狀態(tài)3代替狀態(tài)2，把引向狀態(tài)2的箭弧都引向狀態(tài)3，把2消去；,用狀態(tài)5代替狀態(tài)4，把引向狀態(tài)4的箭弧都引向狀態(tài)5，把4消去；,用狀態(tài)7代替狀態(tài)6，把引向狀態(tài)6的箭弧都引向狀態(tài)7，把6消去；得到一個化簡得DFA M,2.把(a)和(b)分別確定化和最少化,(a),(b),(1)用子集法對M進行確定化 構造一張表,J=0,1,J=1,0,0,1,0,1,0,1,1,1,0,1,-,J=0,J=1,J=0,1,-,把每個子集看成一個狀態(tài)，得到一個DFA M， 且L(M) = L(M),0,1,2,1,2,1,0,2,0,0,1,0,1,0,1,1,1,0,1,-,(2)

11、把DFA M進行化簡 解: 把M狀態(tài)集分為兩組: 終態(tài)結點0，1 非終態(tài)結點2 考察0，1 因為， 0，1a = 0，1b = 所以， 0，1不可再分,1,2,0,1,2,J=1,J=2,所以， 最終把M分割為0，1， 2 用狀態(tài)0代替狀態(tài)1，把引向狀態(tài)1的箭弧都引向狀態(tài)0，把1消去，得到一個DFA M,(2)用子集法對M進行確定化 構造一張表,J=1,J=2,0,1,1,1,2,4,2,1,3,J=1,J=4,J=1,J=3,4,3,0,5,3,2,J=0,J=5,J=3,J=2,J=5,J=4,5,5,4,(2) 把DFA M進行化簡 解: 把M狀態(tài)集分為兩組: 終態(tài)結點0，1 非終態(tài)結點

12、2，3，4，5 考察0，1 因為， 0，1a = 0，1b = 所以， 0，1不可再分,1,2，4,0,1,2，3，4，5,J=1,J=2，4,考察2，3，4，5 因為， 2,3,4,5a = 所以， 2,3,4,5可再分 看圖，把2,3,4,5分割為2,4和3,5,0,1,3,5,2,3,4,5,J=0,1,3,5,0,1,考察2，4 因為， 2，4a = 2，4b = 所以， 2，4不可再分 考察3，5 因為， 3，5a = 3，5b = 所以， 3，5不可再分,0,1,3,5,0,1,3,5,J=0,1,J=3,5,3,5,2,4,3,5,2,4,J=3,5,J=2,4,所以，最終把M分

13、割為0，1， 2，4 ， 3，5 用狀態(tài)0代替狀態(tài)1，把引向狀態(tài)1的箭弧都引向狀態(tài)0，把1消去；用狀態(tài)2代替狀態(tài)4，把引向狀態(tài)4的箭弧都引向狀態(tài)2，把4消去；用狀態(tài)5代替狀態(tài)3，把引向狀態(tài)3的箭弧都引向狀態(tài)5，把3消去；得到一個DFA M,3.設計一個DFA，它接受0，1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。 解: (1)根據題意，得到相應的正規(guī)式： (0|10)* (2)由以上正規(guī)式構造相應的NFA為：,(1)用子集法對M進行確定化 構造一張表,J=1,J=2,x,1,y,1,y,1,y,1,y,2,2,2,1,y,-,J=1,J=2,J=1,-,把每個子集看成一個狀態(tài)，得到

14、一個DFA M， 且L(M) = L(M),0,1,2,1,2,1,1,2,x,1,y,1,y,1,y,1,y,2,2,2,1,y,-,(2) 把DFA M進行化簡 解: 把M狀態(tài)集分為兩組: 終態(tài)結點0，1 非終態(tài)結點2 考察0，1 因為， 0，10 = 0，11 = 所以， 0，1不可再分,1,2,0,1,2,J=1,J=2,所以， 最終把M分割為0，1， 2 用狀態(tài)1代替狀態(tài)0，把引向狀態(tài)0的箭弧都引向狀態(tài)1，把0消去，得到一個DFA M,問題一：消除文法直接左遞歸方法： 設有產生式 PP1|P2|Pm|1|2|n 其中每個i不以P開頭，每個i不為 消除P的直接左遞歸性就是把這些規(guī)則改寫

15、成： P1P|2P|nP P1P| 2P|mP| ,練習1.3 自上而下的語法分析,4.消除整個文法的左遞歸的算法 如果文法不含回路（形如 的推導），也不含有以為右部的產生式，則下面算法可以消除左遞歸 (1)把文法G的所有非終結符按任一種順序排列成P1,P2,Pn；按此順序執(zhí)行 (2)for i = 1 to n do for j = 1 to i-1 do 把形如PiPj的規(guī)則改寫成: Pi 1|2|k。 其中Pj1|2|k是關于Pj的所有產生式 Endfor 消除關于Pi的直接左遞歸 Endfor (3)化簡由(2)得到的文法：除去從開始符號無法達到的非終結符的產生式,例子：考慮以下文法，

16、消除其左遞歸性 SQc | c QRb | b RSa | a 解：(1)把該文法的非終結符排列為R、Q、S. (2)對于R，不存在直接左遞歸，不用消除 對于Q，把R代入到Q的有關候選式后，把Q的產生式改寫為 QSab| ab | b 現(xiàn)在Q不存在直接左遞歸，不用消除 對于S，把Q代讀到S的有關候選式后，把S的產生式改寫為 SSabc | abc | bc | c S有直接左遞歸，消除S的直接左遞歸為 SabcS | bcS | cS SabcS | ,得到消除左遞歸性的文法為 SabcS | bcS | cS SabcS | QSab| ab | b RSa | a (3)顯然，Q和R的產生

17、式已經是多余的，將它們去掉 化簡后的文法是： SabcS | bcS | cS SabcS | 注意：由于對非終結符排序的不同，最后所得的文法在形式上可能不一樣，但它們都是等價的,例如：考慮剛才的文法，消除其左遞歸性 SQc | c QRb | b RSa | a 解： (1)把該文法的非終結符排列為S、Q、R (2)對于S，不存在直接左遞歸，不用消除 對于Q，不存在直接左遞歸，不用消除 對于R，把S代入到R的有關候選式后，把R的產生式改寫為 RQca| ca | a 把Q代入到R的有關候選式后，把R的產生式改寫為 RRbca| bca | ca | a,RRbca| bca | ca | a

18、 R有直接左遞歸，消除S的直接左遞歸為 RbcaR | caR | aR RbcaR | 得到消除左遞歸性的文法為 SQc | c QRb | b RbcaR | caR | aR RbcaR | ,問題三：證明是LL(1)文法 (1)文法不含左遞歸 (2)對于文法中每一個非終結符A的各個產生式的候選式的FIRST集兩兩不相交。即，若 A1|2|n 則FIRST(i)FIRST(j)= (ij) (3)對于文法中的每個非終結符A，若它的某個候選首符集包含,則 FIRST(A)FOLLOW(A)= 如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法(第1個L代表從左到右掃描輸入串，第2個L

19、代表最左推導，1表示分析時每一步只看1個符號),問題四：預測分析表M(xm ，ai )的構造方法,1. 定義FIRST集 令文法G是不含左遞歸的文法，對G的非終結符的候選，定義它的開始符號（終結首符）集合： 特別地，如果，則FIRST() 如果非終結符A的任意兩個候選式i和j的開始符號集滿足FIRST(i)FIRST(j)=，則A可以根據所面臨的第一個輸入符號，準確地指派一個候選式去執(zhí)行任務，是那個FIRST集含a的候選式，即 a FIRST(),2.對每個文法符號XVNVT構造其FIRST(X) 連續(xù)使用以下規(guī)則，直至每個結合FIRST不再增大為止 (1)若XVT，則FIRST(X)=X.

20、(2)若XVN，且有產生式Xa，則把a加入到FIRST(X)中；若X也是一條產生式，則把也加到FIRST(X)中。 (3)若XY是一個產生式，且YVN，則把FIRST(Y)中所有非元素都加到FIRST(X)中； 若XY1Y2 Yk是一個產生式， Y1Y2 Yi-1都是非終結符，而且，對于任何j，1ji-1， FIRST(Yj)都含有(即Y1Yi-1=)，則把FIRST(Yi)中的所有非元素都加到FIRST(X)； 特別是，若所有的FIRST(Yj)均含有，j=1，2，k，則把加到FIRST(X)中。,3. 對于文法的任意符號串=X1X2 Xn構造集合FIRST() (1)置FIRST()= F

21、IRST(X1) (2)若對任何1ji-1，F(xiàn)IRST(Xj)，則把FIRST(Xi)加至FIRST()中 (3)特別的，若所有的FIRST(Xj)均含有，1jn，則把 也加至FIRST()中,4.定義FOLLOW集 對文法G的任何非終結符A，定義它的后繼符號集合： 特別地，如果SA，則#FOLLOW(A) FOLLOW(A)集合是所有句型中出現(xiàn)在緊接A之后的終結符號或#所組成的集合 當非終結符A面臨輸入符號a，且a不屬于A的任意候選式的FIRST集但A的某個候選式的FIRST集包含時，只有當a FOLLOW(A)，才可能允許A自動匹配,5.對每個文法AVN構造其FOLLOW(A) 連續(xù)使用一

22、下規(guī)則，直至每個集合FOLLOW不再增大為止 (1)對于分發(fā)開始符號S，置#與FOLLOW(S)中； (2)若AB是一個產生式，則把FIRST()加至FOLLOW(B)中； (3)若AB是一個產生式， FOLLOW(A)加至FOLLOW(B)中 或AB是一個產生式而 (即FIRST()，F(xiàn)OLLOW(A)加至FOLLOW(B)中 其中,(VNVT)*，BVN,6.構造分析表M的算法是 (1)對于文法G的每個產生式A，執(zhí)行(2)(3) (2)對每個終結符aFIRST()，把A加至MA,a中； (3)若FIRST()，則對任何b FOLLOW(A)把A加至MA,b中； (4)把所有無定義的MA,a

23、標上”出錯標志”,1. 設有文法G(VT，VN，S，P)，其中 VT=a， ，, ，(，) ；VN=S,T；S = S P: S a | | (T) T T,S | S (1)消除其產生式的左遞歸.然后，對每個非終結符寫出不帶回溯的遞歸子程序； (2)經改寫后的文法是否是LL(1)的？給出它的預測分析表,S a | | (T) T T,S | S (1)消除其產生式的直接左遞歸 解：對于T T,S | S (P=T，=,S ，=S)變成 TST T,ST| 所以 S a | | (T) TST T,ST| 每個非終結符的不帶回溯的遞歸子程序如下：,PP| - PP PP|,S a | | (T

24、) TST T,ST| (2)經改寫后的文法 是否是LL(1)的？ 給出它的預測分析表。 解：FIRST( S )= ; FIRST( T )= ; FIRST( T)= ;,(2)若XVN，且有產生式Xa，則把a加入到FIRST(X)中；若X也是一條產生式，則把也加到FIRST(X)中。 (3)若XY是一個產生式，且YVN，則把FIRST(Y)中所有非元素都加到FIRST(X)中； 若XY1Y2 Yk是一個產生式， Y1Y2 Yi-1都是非終結符，而且，對于任何j，1ji-1， FIRST(Yj)都含有(即Y1Yi-1=)，則把FIRST(Yi)中的所有非元素都加到FIRST(X)； 特別是

25、，若所有的FIRST(Yj)均含有，j=1，2，k，則把加到FIRST(X)中。,a, ,(,a,(,S a | | (T) TST T,ST| 解：FIRST(ST)= ; FIRST(,ST)= ; FIRST(a)= ; FIRST()= ; FIRST(T)= ;,=X1X2 Xn 構造FIRST() (1)置FIRST()= FIRST(X1) (2)若對任何1ji-1，F(xiàn)IRST(Xj)，則把FIRST(Xj)加至FIRST()中 (3)特別的，若所有的FIRST(Xj)均含有，1jn，則把 也加至FIRST()中,，,a, ,(,a,(,S a | | (T) TST T,ST|

26、 解： FOLLOW(T)= ; FOLLOW (T)= ; FOLLOW (S)= ;,(1)對于分發(fā)開始符號S，置#于FOLLOW(S)中； (2)若AB是一個產生式，則把FIRST()加至FOLLOW(B)中； (3)若AB是一個產生式，或AB是一個產生式而FIRST()，F(xiàn)OLLOW(A)加至FOLLOW(B)中。,#,),),),S a | | (T) TST T,ST|,證明： FIRST(a)FIRST() FIRST(T)=a (= FIRST( T)FOLLOW (T)= ，, ) = 所以，該文法是LL(1)文法,S a | | (T) TST T,ST|,2.構造算符優(yōu)先

27、關系表 (1)通過檢查產生式的每一個候選式可以找出滿足a=.b （即Pab或PaQb的產生式） (2)為了滿足.，需對G中每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P)：,(3)構造集合FIRSTVT(P)的算法 按其定義，可用下面兩條規(guī)則來構造集合FIRSTVT(P)： 若有產生式Pa或PQa， 則aFIRSTVT(P)； 若aFIRSTVT(Q)，且有產生式PQ， 則aFIRSTVT(P)。,(4)同理構造構造集合LASTVT(P)的算法 按其定義，可用下面兩條規(guī)則來構造集合LASTVT(P)： 若有產生式P a或P aQ ， 則a LASTVT(P)； 若a LAST

28、VT(Q)，且有產生式P Q ， 則a LASTVT(P)。,(5)有了這兩個集合之后，就可以通過檢查每個產生式的候選式確定滿足關系.的所有終結符對。 (1)假定有個產生式的一個候選形為 aP 那么，對任何bFIRSTVT(P)，有a . b。,例1:考慮下面的文法G： S X | SaX X Y | X%Y Y X！ 構造該文法G的每個非終結符的FIRSTVT和LASTVT集合 解: (1)構造FIRSTVT集合 FIRSTVT(Y)= FIRSTVT(X)= FIRSTVT(S)= , 若有產生式Pa或PQa，則aFIRSTVT(P)； 若aFIRSTVT(Q)，且有產生式PQ，則aFIR

29、STVT(P)。,%,a,%,例1:考慮下面的文法G： S X | SaX X Y | X%Y Y X！ 構造該文法G的每個非終結符的FIRSTVT和LASTVT集合 解: (1)構造LASTVT集合 LASTVT(Y)= LASTVT(X)= LASTVT(S)= ,!, ,%,! , ,a,%,!, , 若有產生式P a或P aQ ，則a LASTVT(P)； 若a LASTVT(P)，且有產生式P Q ，則a LASTVT(P)。,例2:G: S X | SaX X Y | X%Y Y X！ 求出該文法每個終結符號的優(yōu)先關系，并構造優(yōu)先分析表 (1)SSaX，且%, FIRSTVT(X)

30、 aP 所以a 小于 %, (2) SSaX，且a, %, !, LASTVT(S) Pb 所以a, %, !, 大于 a 以下略。,FIRSTVT(S)=a, %, FIRSTVT(X)= %, FIRSTVT(Y)= LASTVT(S)=a, %, !, LASTVT(X)= %, !, LASTVT(Y)= !, ,(1)假定有個產生式的一個候選形為 aP 那么，對任何bFIRSTVT(P)，有a . b。,構造分析表如下： 其中，空白為錯誤,2.優(yōu)先函數(shù)的構造方法 如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構造優(yōu)先函數(shù): (1)對于每個終結符a，令其對應兩個符號fa和ga，畫一張

31、以所有符號fa和ga為結點的方向圖。如果a.=.b，則從fa畫一條弧至gb如果a.=.b，則從gb畫一條弧至fa 。 (2)對每個結點都賦予一個數(shù)，此數(shù)等于從該結點出發(fā)所能到達的結點(包括出發(fā)點自身)。賦給fa的數(shù)作為f(a)賦給ga的數(shù)作為g(a)。 (3)檢查所構造出來的函數(shù)f和g是否與原來的關系矛盾。若沒有矛盾，則f和g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。,gi,fi,f*,g*,g+,f+,f#,g#,例:取前面文法G(E) (1) EE+T | T (2) TT*F | F (3) F (E) | i 的終結符+，*，i，#,7,4,6,6,2,1,5,1,(1) U | V = V | U或的交換律 證明：因為，L(U|V) = L(U)L(V) 又因為，L(V|U) = L(V)L(U) = L(U)L(V) 因為， L(U|V) = L(V|U) 所以，U | V = V | U,(2) U | ( V|W ) = ( U|V ) | W或的結合律 證明： 因為，L(U|(V|W)=L(U)L(V|W) =L(U)L(V)L(W) 又因為，L( U|V ) | W) = L(U|V)L(W) = L(U)L(V)L(W) 因此， L(U|(V|W) = L( U|V ) | W) 所以， U | ( V|W