1、編譯原理典型案例1.對于文法GSS 一 (L)S-aSS 一 aL 一 L,SL - S(1)畫出句型(S,(a)的語法樹；(2)寫出上述句型的所有短語、直接短語、句柄和素短語。解答這類題目重點考查語法樹、推導、短語、直接短語、句柄和素短語等基本概念。在句型 中尋找短語、直接短語、句柄的方法：(1)畫出句型對應的語法樹。句型 (S,(a)的語法樹如下圖所示a(2)在該語法樹中尋找短語、直接短語、句柄。首先我們看短語的定義：令G是一個文法，S是文法的開始符，假設 “，3,8是文法G的句型，如果有S n a A 8 且 A += 3則稱3是句型a 3 8相對于非終結符 A的短語。如果有 A= 3

2、,則稱3是句型a 3 8相對 于規則A- 3的直接短語。一個句型的最左直接短語稱為該句型的句柄。根據短語的定義可知，以非終結符 A為根的子樹的葉結點從左到右排列就是相對于非終結符A的短語；如果子樹只有兩代，則短語就是直接短語； 最左邊的兩代子樹的所有葉結點從左到右排列，就是該句型的句柄。素短語是一個短語，它至少包含一個終結符，且除自身外不再包含其他素短 語。處于句型最左邊的素短語為最左素短語。從語法樹中我們可以找到：短語：a, S, (a), S,(a),(S, (a)直接短語：a, S 句柄：S素短語：a2 .寫一個上下文無關文法，使其語言能被5整除且不以0開頭的無符號整數集合（如 5,10

3、, 15）解答能被5整除的數從形式上看，是以 0, 5結尾的數字串。題目要求不以 0開頭，注意0 不是該語言的句子。句子的結構分為三種：一位數兩位數多位數0或5;0以外，其他數字都可以;0-9所有數字都可以。其中，A代表可以出現在個位上的數字，只能是 B代表可以出現在開始位上的數字，除了 C代表可以出現在中間位上的數字。I于是，A 一0 | 5B一 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C- 0 | B寫文法時，先描述一位數結構，于是有產生式S 一5。對于兩位數和多位數，都是以B開頭和以A結尾，于是有產生式 S-DAo用非終結符D推導出兩位數和多位數中除個位數 字以

4、外的數字。對與多位數，由于中間位可以是許多位，必須使用遞歸技術來描述其結構。于是有產生式：DfDCDfB因此，所求文法為 GS:S 一 5SfDADfDCDfBA- 0 | 5B一 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C- 0 | B3 .寫一個文法G,使其語言為 不以0開頭的偶數集。解答不以0開頭的偶數集數字的結構分為三種：一位數、兩位數和多位數。一位數兩位數多位數其中，A代表可以出現在個位上的數字，可以是 B代表可以出現在開始位上的數字，除了 C代表可以出現在中間位上的數字。I于是，A 一2 | 4 | 6 | 88- 0 | AC一 1 | 3 | 5 |

5、7 | 9 | A2, 4, 6, 8,但不能是0;0以外，其他數字都可以； 0-9所有數字都可以。寫文法時，先描述一位數結構，于是有產生式S -A。對于兩位數和多位數，都是以 CD- 0 | C開頭和以B結尾，于是有產生式 S-CE。用非終結符 E推導出兩位數和多位數中除個位數 字以外的數字。對與多位數，由于中間位可以是許多位，必須使用遞歸技術來描述其結構。于是有產生式：EfCEEfB因此，所求文法為 G(S):ST | CEA一 2 | 4 | 6 | 8B- 0 | AC一 1 | 3 | 5 | 7 | 9 | AD- 0 | C4 .考慮下面的程序： procedure P(x, y

6、, z);beginy:=y+1;z:=z+xend;begina:=2;b:=3;P(a+b, a, a); print aend.試問，若參數傳遞的方式分別采用傳值、傳地址、得結果和傳名時，程序執行后輸出a的值是什么？解答所謂傳值是調用段把實在參數的值計算出來，被調用段把這些值抄進自己的形式參數 中，像使用局部名一樣使用這些形式單元。對形式參數的任何運算不影響實參的值。上面過程P調用的的參數傳遞過程如下圖所示。過程調用前過程調用后a+b=5a=2b=3x=5y=2z=3但過程P無法改變實參a的值。因此，程序執行后輸出a的值是2。所謂傳地址是把實在參數的地址傳遞給相應的形式參數。在過程段中每

7、個形式參數都有一個相應的單元，稱為形式單元。形式單元將用來存放相應實在參數的地址。過程體對形式參數的任何引用或賦值都被處理成對形式單元的間接訪問。過程調用前過程調用后過程調用后，形參x的形式單元指向存a+b值的臨時變量的地址,形參y的形式單元指向變量a的地址，形參z的形式單元指向變量 b的地址。形參通過指針可以間接訪問實參。執行y:=y+1;后，實在參數的變化:執行z:=z+x;后，實參的變化:因此，程序執行后輸出 a的值是8。所謂得結果是每個形式參數對應兩個單元，第一個單元存放實參的地址， 第二個單元存放實參的值。在過程體中對形參的任何引用或賦值都被處理成對第二個形式單元的直接訪 問，但在過

8、程工作完成返回之前必須把第二個單元的內容存放到第一個單元所指的那個實參 單元之中。過程調用前過程調用后執行y:=y+1;后，實參和的形參的變化:執行z:=z+x;后，實參和的形參的變化:過程工作完成返回之前必須把第二個單元的內容存放到第一個單元所指的那個實參單 元之中。實參和的形參的變化：因此，程序執行后輸出a的值是7。(4)所謂傳名是在進入調用段之前不對實在參數預先進行計值，而是過程中每當使用到相應的形參時才對它實行計值。因此，在實現時通常都把實參處理成型個子程(稱為參數子程序),每當過程體中使用到相應形參時就調用這個子程序。因此，過程體執行 y:=y+1;語句，實現時處理成為：a=a+1;

9、過程體執行z:=z+x;語句，實現時處理成為：a=a+(a+b);執行上述兩語句后，a的值是9。因此，程序執行后輸出a的值是9。綜上所述程序執行時 a的輸出：(1)傳值： 2(2)傳地址：8(3)得結果：7(4)傳名： 95 .已知文法GSSfS*aP | aP | *aPP-+aP | +a(1)將文法GS改寫為LL(1)文法G)S;(2)構造文法GWS的預測分析表。解答構造文法的預測分析表，通常應當按下列步驟進行：(1)消除文法的左遞歸(2)對消除左遞歸后的文法，提取左公因子。(3)對經過上述改造后的文法，計算它的每個非終結符的FIRST和FOLLOW 集合。(4)根據FIRST和FOLL

10、OW 集合構造預測分析表。消除直接左遞歸方法：假設關于非終結符P的規則為Pf P a |3其中，3不以P打頭。把P的規則改寫為如下非直接左遞歸形式:P- 3 P ?P- a P ?£文法GS消除直接左遞歸方法后，文法變為GWS:S - aPS? | *aPS?S? 一 *aPS? | SP 一 +aP | +a提公共左因子的方法：假設關于非終結符A的規則為A 一 8 3 1| S3 2|-| 8 3 n| 丫 1| 丫 2|- | 丫 m其中，每個丫不以8開頭。把A的規則改寫為如下形式：A 一 a A?| 1 1| 丫2| | y m A- 3 1|32|-|3 n于是，文法 G?(

11、S)提公共左因子后，文法變為G?SS - aPS? | *aPS?S?f *aPS? |P 一 +aP?P?fP | £ 計算每個非終結符的FIRST和FOLLOW 集合：a.計算非終結符 X的FIRST方法：(1)若有產生式 XTa，則把a加入到FIRST(X)中； (2)若Xtw也是一條產生式，則把他加到FIRST(X)中；(3)若XtY是一個產生式且 YWVN,則把FIRST(Y)中的所有非£元素都加到FIRST(X) 中；若XtY1Y2-YK 是一個產生式，Y1,Y2,Yi-1都是非終結符，而且，對于任何 j, 1<j<i-1,FIRST(Yj)都含有&

12、amp;則把FIRST(Yj)中的所有非元素都加到FIRST(X)中；特別是, 若所有的FIRST(Yj)( j=1,2, ，醺含有&則把 切口到FRIST(X)中。根據計算非終結符的 FIRST方法的第一點，有FIRST(S)=a , * FIRST(S?)=* FIRST(P尸+ FIRST(P?)= 根據計算非終結符的 FIRST方法的第二點，有 FIRST(S)=a , * FIRST(S?)=* , FIRST(P)=+ FIRST(P?)= 根據計算非終結符的 FIRST方法的第三點，有 FIRST(S)=a , * FIRST(S?)=* , FIRST(P)=+ FIR

13、ST(P?)=+ , b.計算非終結符 X的FOLLOW 方法：(1)對于文法的開始符號 S,置#于FOLLOW(S)中；(2) .若A一 a B 3是一個產生式，則把 FIRST( 3)的加至FOLLOW(B)中；(3)若A一 a B是一個產生式，或A一 a B 3是一個產生式而 3=6 (即gFIRST( 3 ),則把 FOLLOW(A),加至 FOLLOW(B)中。根據計算非終結符的 FOLLOW方法的第一點，有FOLLOW(S)=#FOLLOW(S ?)=FOLLOW(P)=FOLLOW(P ?)=根據計算非終結符的 FOLLOW方法的第二點，有FOLLOW(S)=#FOLLOW(S

14、?)=#FOLLOW(P)=* , #FOLLOW(P ?)=*, #根據FIRST和FOLLOW集合構造預測分析表方法：(1)對文法G的每個產生式A一 口執行第二步和第三步；(2)對每個終結符aWFIRST(ot),把A一 口加至MA,a中；若妒FIRST(a),則對任何 bWFOLLOW(A),把A- ct加至MA,b中;(4)把所有無定義的MA,a標上出錯標志構造預測分析表方法如下：*+a#SSf *aPS?Sf a PS?S?S? 一 *aPS?S?一 £PP 一+aP?P?P? 一 £P? 一 PP?一 £6 .設文法G(S):S 一 (T) | aS

15、| aT-T,S | S消除左遞歸和提公共左因子； 構造相應的 FIRST和FOLLOW 集合;構造預測分析表。解答(1)消除左遞歸和提公共左因子，文法變為 G?SS 一(L) | aS?S?一 S | £L-SL?L? 一，SL? |£此文法沒有公共左因子(2)構造相應的 FIRST和FOLLOW 集合FIRST(S)=a , (FIRST(S?)=a , (, eFIRST(L尸a, (FIRST(L?)=, eFOLLOW(S)=, ), #FOLLOW(S?)=, ), #FOLLOW(L)= )FOLLOW(L?)= )(3)構造預測分析表()a,#SS 一 (L

16、)S 一 aS?S?S"SS? sS"SS? SS" sLL fSL?L fSL?L”,SL?L?L?" £7 .設文法GSS >(A)S 1 aA >A+SA -；S(1)構造每個非終結符的FIRSTVT和LASTVT 集合；(2)構造優先關系表；解答對于這類題目，關鍵是準確掌握FIRSTVT和LASTVT集合的定義和構造方法。FIRSTVT(P)=a|P +=a,或 P+=Qa., aVT 而 QWVN即，對于非終結符 P,其往下推導所可能出現的首個算符。LASTVT(P)=a|P += , a 或 P+=.aQ, aVT 而

17、QWVN即，對于非終結符 P,其往下推導所可能出現的最后一個算符。構造FIRSTVT和LASTVT 集合的方法1 1)構造FIRSTV集合若有產生式 PTa,或 Qa,則 aFIRSTVT(P);若有 aFIRSTVT(Q),且有產生式 Q,則 a三 FIRSTVT(P)。2 2)構造LASTVT集合若有產生式Pt, a或J, aQ,則aLASTVT(P);若有 aLASTVT(Q),且有產生式 P-*, Q,則 a= LASTVT(P)。對于文法GS,構造它的每個非終結符的FIRSTVT和LASTVT集合：FIRSTVT(S)=a, ( FIRSTVT(A)=+,a, ( LASTVT(S)

18、=a, )LASTVT(A)=+,a, )構造算符優先關系表方法：,=,關系直接看產生式的右部，若出現了P 一ab或P 一aQb,貝U a=b(2)?<,關系求出每個非終結符 P的FIRSTVT(P)若 P一 aR ，則 vbC FIRSTVT(R) , a<b (3)?>族系求出每個非終結符 P的LASTVT(P)若 P-Rb-.，貝UvaC LASTVT(B) , a>b 對于文法GS,構造它的算符優先關系表如下：a+()a>>+<><>(<<<=)>>8 .設文法G (S):S - T|SVTT-U

19、 |TUU - i |-U(1)計算 FIRSTVT 和 LASTVT ;(2)構造優先關系表。解答(1)對于文法 GS,構造它的每個非終結符的FIRSTVT和LASTVT集合。FIRSTVT(S)= V , A , i, - FIRSTVT(T)= A , i, -FIRSTVT(U)=i, -LASTVT(S)= V , A , i, - LASTVT(T)= A, i, -LASTVT(U)=i, -(2)構造優先關系表。iVA-S.>.>V<.><.<.A<.>.><.-<.>.><.9 .下面映射if

20、語句的文法GS是算符優先文法嗎？如果是，則構造算符優先關系表。如果 不是，則說明理由。GSS >iBtSS >iBtSeSS > aB）b解答對于文法GS,它是一個二義性文法。因為存在句子ibtibtaea有兩個不同的最左推導S ： iBtS= ibtS= ibtiBtSeS= ibtibtSeS ： ibtibtaeS= ibtibtaeaS= iBtSeS= ibtSeS ： ibt iBtSeS= ibtibtSeS= ibtibtaeS= ibtibtaea由于算符優先文法一定不是二義性文法，所以文法GS不是算符優先文法。10 .設有如下的基本塊T1:=A+BT2:=

21、5M:=T2*4T3:=C-DT4:=M+T3L:=T1*T3T4:=A+BN:=T4（1）畫出該基本塊的 DAG圖；（2）假設只有L, M和N在基本塊之后還要引用，寫出優化后的四元式序列。解答在構造基本塊的 DAG圖時，必須注意兩個方面：一是對于已知的常量要進行計算；二是對同一變量進行多次定值時，最后一次定值是基本塊中該變量的最終變量。由于基本塊有語句T2: =5,可知T2是已知量。所以，語句 M: =T2 * 4可計算出M的值來，即，M也轉為常量（M = 20 ）。一方面，變量T4進行了兩次操作，基本塊執行完時，最后一次給T4的定才是T4的最終結果。活躍信息是針對變量而言的。如果一個變量在

22、基本塊之后不再被引用，則稱該變量是非活躍的（或稱為非活躍變量），反之稱之為活躍的（或稱為活躍變量）。 變量的活躍信息對代碼優化和代碼生成都有非常重要的指導意義。當DAG圖構造出來后，根據題目所給的條件從DAG圖中計算出活躍變量的結果即可。本是中只要計算出變量 L、M和N的結果就行了。基本塊對應的DAG圖如下：CAB20D5按照構造其結點的順序，重新寫成四元式序列G?T1=A+BT4=T1N=T4T2=5M=20T3=C-DL=T1*T3T1、T2、T3和T4都不會引用，于是重由于只有L, M和N在基本塊之后還要引用, 新寫出優化后的四元式序列為：N:=A+BM:=20T3:=C-DL:=N*T

23、311 .把語句while a>0 A b>0 doif x>y then b:=b-1else a:=a-1;翻譯為四元式序列。解答對于這類題目，關鍵是準確掌握語句的語動作。while-do語句的語義動作if-then-else語句的語義動作作為條件控制的布爾式的翻譯：把A or B解釋成把A and B解釋成把not A解釋成布爾表達式賦予兩種 出口 ”：一 假設四元式序列從100開始編號。if A then true else Bif A then B else falseif A then false else true 是真”出口； 一是假”出。表達式a>0翻

24、譯為：100 (j>, a, 0, _)101 (j , _, _, _)繼續翻譯表達式 a>0 Ab>0,由于是與運算，100號語句應轉跳到102號語句，102號語 句為“真”出口，101號語句和103號語句為“假”出，四元式序列為：100 (j> a 0 102)101 (j _ _ _)102 (j> b 0 _)103 (j _ _ _)繼續翻譯語句 while a>0 A b>0 doif x>y while語句中的邏輯表達式的“真”出口應轉跳到其循環體的第一個四元式標號，即104號語句。100 (j> , a, 0, 102)101 (j _ _ _)102 (j> , b, 0, 104)103 (j , _, _, _)104 (j> x y_)105 (j， _, _, _)if語句中的邏輯表達式的“真”出口為 104號語句，應轉跳到 then中的第一個四元式 標號，“假”出口為105號語句，應轉跳到else中的第一個四元式標號。then中語句翻譯完， 應轉跳出去。100 (j> , a, 0, 102)101