編譯原理復(fù)習(xí)-2.

1、典型例題分析典型例題分析1選擇題選擇題1.編譯程序必須完成的工作有編譯程序必須完成的工作有 。詞法分析詞法分析 語法分析語法分析語義分析語義分析中間代碼生成中間代碼生成中間代碼優(yōu)化中間代碼優(yōu)化目標代碼生成目標代碼生成A. B. C. D. 2.下列關(guān)于編譯和解釋的說法，正確的是下列關(guān)于編譯和解釋的說法，正確的是 。解釋方式和編譯方式的區(qū)別在于解釋程序?qū)υ闯绦虿]有進行真正解釋方式和編譯方式的區(qū)別在于解釋程序?qū)υ闯绦虿]有進行真正翻譯。翻譯。編譯方式與解釋方式的根本區(qū)別在于是否生成目標代碼。編譯方式與解釋方式的根本區(qū)別在于是否生成目標代碼。解釋程序和編譯程序都是語言處理程序。解釋程序和編譯程序都

2、是語言處理程序。與編譯系統(tǒng)相比，解釋系統(tǒng)比較簡單，可移植性好，執(zhí)行速度慢。與編譯系統(tǒng)相比，解釋系統(tǒng)比較簡單，可移植性好，執(zhí)行速度慢。編譯程序是將高級語言程序翻譯成匯編語言程序或機器語言程序編譯程序是將高級語言程序翻譯成匯編語言程序或機器語言程序解釋程序是將匯編語言程序翻譯成機器語言程序解釋程序是將匯編語言程序翻譯成機器語言程序A.B. C. D.CD23. 這樣一些語言，它們能被確定有限自動機識別，但不能用正則表達式表示。A存在 B.不存在 C.無法判定是否存在4.已知文法GS：S SaS | SbS | ScS | dSe | f,下列句型中， 是規(guī)范句型。AfafbS B.faSbS C.

3、SaSbf. D.faS BCSaSSSbSffSaSSSbSfSaSSS b SSaSSff35.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) B.句型：句型：( ) ( )(SSS)S(SS)SA(SSS)S(SS)S45.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S) C.句型：句型：ababSSbSaSb

4、SaSSbSaSaSbA55.下列文法中不是二義性文法的是 。AS +SS | -SS | aB. S S(S)S | C. S aSbS | bSaS | D. S a | S + S | SS | S* | (S)D.句型：句型：a+a*S + SS S * a a S *SS + SaaA66.后綴表達式ab+c*de*+ 的中綴形式是 。Aa*(b+c)+d*eB(a+b)*c+d*eCa+b*c*d+eDa+b*c+d*e B7后綴式后綴式(逆波蘭式逆波蘭式 )n例：例：pos(A*B+C*D)=AB*CD*+n逆波蘭式的特點逆波蘭式的特點:逆波蘭式中的變量的次序與中綴式中的變逆波蘭

5、式中的變量的次序與中綴式中的變量的次序完全一致。量的次序完全一致。逆波蘭式中無括號。逆波蘭式中無括號。逆波蘭式中的運算符已按計算順序排列。逆波蘭式中的運算符已按計算順序排列。8二、簡答題1.對于文法對于文法GS：S aAbB A c | AcB d | dB請畫出句型請畫出句型aAcbdd的語法樹，并求出該句的語法樹，并求出該句型的所有短語、簡單短語和句柄。型的所有短語、簡單短語和句柄。9定義定義1 1：由某一結(jié)點及其所有分支組成的部分由某一結(jié)點及其所有分支組成的部分樹稱為原樹的一棵子樹。樹稱為原樹的一棵子樹。定義定義2 2：只有單層分支的子樹稱為簡單子樹。只有單層分支的子樹稱為簡單子樹。定義

6、定義3 3：最左簡單子樹的葉稱為句柄。最左簡單子樹的葉稱為句柄。定理：定理： 1.1.每個句型都有一棵語法樹，每個語法樹每個句型都有一棵語法樹，每個語法樹的葉組成該句型。的葉組成該句型。 2.2.每棵子樹的葉組成短語，每棵簡單子樹每棵子樹的葉組成短語，每棵簡單子樹的葉組成簡單短語。的葉組成簡單短語。 3.3.最左簡單子樹的葉組成句柄。最左簡單子樹的葉組成句柄。10GS：S aAbB A c | AcB d | dB 句型句型aAcbddSaAbBAcdBdaAcbddAcddd短語：短語：簡單短語：簡單短語：Acd 句柄：句柄： Ac11二、3. 請給出下面文法GA的LL(1)分析表。A aA

7、Be 1 | Bc 2B dB 3 | 412三個重要的集合三個重要的集合 First集集 First( ) = a VT | * a. (if * then else ) Follow集集 Follow(A) = a VT | S+ .Aa. (if S*.A then # # else ) Select集集(Select集集)13 Select(A ) First( ) 當當 First( ) = First( )- Follow(A) 當當 First( ) 對每一文法符號對每一文法符號X計算計算First(X)集集(1) 若若X VT ： First(X)=X 若若X VN : 對關(guān)于

8、對關(guān)于X的每一個產(chǎn)生式進行如下處理的每一個產(chǎn)生式進行如下處理:uStep1.形如形如: X , 則則: First(X)uStep2.形如形如:X a , a VT則則 : a First(X)14對每一文法符號對每一文法符號X計算計算First(X)集集(2)uStep3.對對每一個形如下的產(chǎn)生式每一個形如下的產(chǎn)生式: XY1Y2Yi-1YiYn若：若：Y1,Y2, ,Yi VN且且Y1,Y2, ,Yi-1* 則則: First(Y1)- , First(Y2)- , , First(Yi-1)- , First(Yi)都都包含在包含在First(X)中。中。若：若： Yi VN且且Yi *

9、 (i=1,2,n), 則則: First(Y1) , First(Y2), , First(Yn) 都包含在都包含在First(X)中。中。重復(fù)重復(fù)Step3 ，直至對所有，直至對所有A VN，F(xiàn)irst(A)收斂為止。收斂為止。15計算計算First( )集集若符號串若符號串 =X1X2Xn， 當當X1,X2, , Xi-1* ，Xi 不能不能 * ，則則: First( )= 1i-1(First(Xj)- ) First(Xi) 若所有若所有Xi 都能都能* ，則則: First( )= 1n First(Xj)161: 對所有對所有A VN 且且 A非非開始符開始符 : 令令Foll

10、ow(A):= ； 對開始符對開始符 S : 令令Follow(S)= # # ； 2: 若有產(chǎn)生式若有產(chǎn)生式AxBy： 如果如果 First(y) 則：則： Follow(B) = Follow(B) (First(y) Follow(A) 否則：否則： Follow(B)= Follow(B) First(y) 3: 重復(fù)重復(fù)2和和3，直至對所有，直至對所有A VN，F(xiàn)ollow(A)收收 斂為止。斂為止。17計算計算Select集集18lSelect(A ) First( ) ，當，當First( )不含不含 = First( )- Follow(A) ，當，當First( )含含LL(

11、1)分析表的構(gòu)造分析表的構(gòu)造 LL(1)分析表的定義：分析表的定義： T T：V VN N V VT T P P Error Error T(A,t)=AT(A,t)=A 若若t t Select( ASelect( A ) ) T(A,t)=Error T(A,t)=Error 否則否則 其中其中P表示所有產(chǎn)生式的集合。表示所有產(chǎn)生式的集合。19 LL(1)分析表的構(gòu)造方法：分析表的構(gòu)造方法：對文法的每一個產(chǎn)生式求其對文法的每一個產(chǎn)生式求其Select集；集；對文法的每一個產(chǎn)生式對文法的每一個產(chǎn)生式AA 進行如下處進行如下處理：理： Select( ASelect( A )= )=（a a1

12、 1,a,a2 2, ,.,a.,an n);); 則令：則令： T(A,aT(A,ai i)=A)=A ,i=1,2,3 ,i=1,2,3,n,n LL(1)分析表的其它元素為分析表的其它元素為error。20文法GA的LL(1)分析表。A aABe 1 | Bc 2B dB 3 | 4文法符號文法符號First集集Follow集集AB #,d, e,c（1）求每個產(chǎn)生式的）求每個產(chǎn)生式的Select集：集：Select（ A aABe ）= aSelect（ A Bc ）= d,cSelect（ B dB ）= dSelect（ B ）= c,ee a ,d ,d ,c21acde#AB每

13、個產(chǎn)生式的每個產(chǎn)生式的Select集：集：Select（ A aABe 11 ）= aSelect（ A Bc 22 ）= d,cSelect（ B dB 33 ）= dSelect（ B 44 ）= c,eA aABeA BcA BcB dBB B acde#A122B43422q0q1q4q6q2q3q5aaabbb a,b 三、將下圖所示的三、將下圖所示的NFA轉(zhuǎn)換為與其等價的最轉(zhuǎn)換為與其等價的最小小DFA。其中。其中q0狀態(tài)為開始狀態(tài)，狀態(tài)為開始狀態(tài)，q6狀態(tài)為狀態(tài)為終止狀態(tài)。（終止狀態(tài)。（10分）分） 23NFANFA到到DFADFA的轉(zhuǎn)換的轉(zhuǎn)換 有限自動機的等價 對于給定的有限自動

14、機M1和M2，如果有 L(M1) = L(M2),則稱有限自動機M1和M2等價。 對于每一個非確定有限自動機M，存在一個確定有限自動機M，使得L(M)=L(M)。由NFA構(gòu)造出與其等價的DFA稱為NFA確定化。 24 狀態(tài)集狀態(tài)集I的的 _閉包閉包設(shè)設(shè)I是是NFA M狀態(tài)集的子集，定義狀態(tài)集的子集，定義I的的 閉包閉包 _CLOSURE(I)為：為： 若若q I ,則則q _CLOSURE(I) 若若q I,那么從那么從q出發(fā)經(jīng)任意條出發(fā)經(jīng)任意條弧而能到達的任弧而能到達的任何狀態(tài)何狀態(tài)q都屬于都屬于 _CLOSURE(I)。 25 例例: _CLOSURE(1)=1，2261524637896

15、79aabbba 狀態(tài)集狀態(tài)集I的的a轉(zhuǎn)換轉(zhuǎn)換若若I=S1, , Sm 是是NFA的的狀態(tài)集的狀態(tài)集的一個一個子集（子集（狀態(tài)子狀態(tài)子集），集），a, 則定義則定義: Ia = _CLOSURE(J )其中其中: J = f (S1,a) f (S2,a) f(Sm,a)27 例例: 1，2a = _CLOSURE(J ) J=f(1,a) f(2,a)=4,5 1，2a = _CLOSURE(4,5 )=4,5,7,6,228152463789679aabbba* NFA A NFA A到到DFA ADFA A的轉(zhuǎn)換過程的轉(zhuǎn)換過程( (確定化確定化):):1.1.令令I(lǐng) I0 0= = _C

16、LOSURE(S_CLOSURE(S0 0 ) )作為作為DFADFA的初始狀態(tài)。其中的初始狀態(tài)。其中S S0 0 為為NFANFA初始狀態(tài)集。初始狀態(tài)集。2.2.若若DFADFA中的每個狀態(tài)都經(jīng)過本步驟處理過中的每個狀態(tài)都經(jīng)過本步驟處理過. .則轉(zhuǎn)步驟則轉(zhuǎn)步驟3 3；否則任選一個未經(jīng)本步驟處理的否則任選一個未經(jīng)本步驟處理的DFADFA狀態(tài)狀態(tài)S Si i，對每一，對每一個個a a, ,進行下述處理：進行下述處理： 計算計算 S Sj j = S = Sia ia 若若S Sj j ，則令，則令f(f(S Si i,a)= ,a)= S Sj j ，若若S Sj j不為當前不為當前DFADFA

17、的狀態(tài)，則將其作為的狀態(tài)，則將其作為DFADFA的一個狀態(tài)。的一個狀態(tài)。轉(zhuǎn)步驟轉(zhuǎn)步驟2 2。3.3.若若S S =S =S1 1, ,S,Sn n 是是A A的一個狀態(tài)的一個狀態(tài), ,且存在一個且存在一個S Si i是是A A的的終止狀態(tài)，則令終止狀態(tài)，則令S S為為A A的終止狀態(tài)。的終止狀態(tài)。 29q0q1q4q6q2q3q5aaabbb a,b 輸入字輸入字 狀態(tài)狀態(tài)a ab bqq0 0 + + q q1 1,q,q3 3 qq1 1,q,q3 3 q q1 1,q,q3 3 q q2 2, ,q q4 4 ,q,q6 6 ,q,q5 5 qq2 2,q,q4 4 ,q,q5 5 ,q

18、,q6 6 q q4 4 , ,q q6 6 ,q,q5 5 q q6 6 , q , q5 5 ,q,q4 4 q q6 6 , q, q5 5 ,q,q4 4 q q6 6 ,q ,q5 5 , , q q4 4 qq4 4 ,q,q5 5 ,q,q6 6 *30 輸入字輸入字 狀態(tài)狀態(tài)A Ab bqq0 0 + +qq1 1,q,q3 3 qq1 1,q,q3 3 qq1 1,q,q3 3 qq2 2,q,q4 4 ,q,q5 5 ,q,q6 6 qq2 2,q,q4 4 ,q,q5 5 ,q,q6 6 qq4 4 ,q,q5 5 ,q,q6 6 qq4 4 ,q,q5 5 ,q,q6

19、6 qq4 4 ,q,q5 5 ,q,q6 6 qq4 4 ,q,q5 5 ,q,q6 6 qq4 4 ,q,q5 5 ,q,q6 6 *q0q1, q3aba,bq2, q4 , q5 , q6 q4 , q5 , q6aa,bab31q0q1, q3aba,bq2, q4 , q5 , q6 q4 , q5 , q6aa,babS0S1aba,bS2S3aa,bab32 等價狀態(tài)等價狀態(tài) 定義定義1 設(shè)設(shè)DFA M 的兩個狀態(tài)的兩個狀態(tài)q1和和q2 , 如果對任意輸如果對任意輸入的符號串入的符號串x，從，從q1和和q2出發(fā)，總是同時到達接出發(fā)，總是同時到達接受狀態(tài)或拒絕狀態(tài)中，則稱受狀態(tài)或

20、拒絕狀態(tài)中，則稱q1和和q2是等價的。如是等價的。如果果q1和和q2不等價，則稱不等價，則稱q1和和q2是可區(qū)分的。是可區(qū)分的。定義定義1 對對DFADFA中的兩個狀態(tài)中的兩個狀態(tài)q1和和q2 ，如果將它們看，如果將它們看作是初始狀態(tài)，所接受的符號串相同，則定義作是初始狀態(tài)，所接受的符號串相同，則定義q1和和q2是等價的。是等價的。 注意注意: DFA的的終止狀態(tài)和非終止狀態(tài)是不等價的。終止狀態(tài)和非終止狀態(tài)是不等價的。33 無關(guān)狀態(tài)無關(guān)狀態(tài) 從有限自動機的初始狀態(tài)開始，任何輸入從有限自動機的初始狀態(tài)開始，任何輸入序列都不能到達的那些狀態(tài)稱為無關(guān)狀態(tài)。序列都不能到達的那些狀態(tài)稱為無關(guān)狀態(tài)。 最小

21、的最小的DFA(化簡了的化簡了的DFA) 如果如果DFA M 沒有無關(guān)狀態(tài)，也沒有彼此等沒有無關(guān)狀態(tài)，也沒有彼此等價的狀態(tài)，則稱價的狀態(tài)，則稱DFA M 是最小的（或規(guī)約是最小的（或規(guī)約的）。的）。 狀態(tài)分離法狀態(tài)分離法 34狀態(tài)分離法狀態(tài)分離法 狀態(tài)分離法的目標狀態(tài)分離法的目標: : SS = SSSS = SS1 1SSSS2 2SSSSn n 其中其中: SS: SSi i SS SSj j= = (i j (i j時時) ) 狀態(tài)集狀態(tài)集I I對對a(aa(a) )是不可區(qū)分的是不可區(qū)分的: :若若I I中元素對輸入符中元素對輸入符a a都轉(zhuǎn)到相同的狀態(tài)集中都轉(zhuǎn)到相同的狀態(tài)集中. .

22、狀態(tài)集狀態(tài)集I I對對a(aa(a) )是可區(qū)分的是可區(qū)分的: : 若若I I中元素對輸入符中元素對輸入符a a轉(zhuǎn)到不同的狀態(tài)集中轉(zhuǎn)到不同的狀態(tài)集中. . 狀態(tài)集狀態(tài)集I I對對a(aa(a) )進行劃分進行劃分: :若若I I中元素對輸入符中元素對輸入符a a轉(zhuǎn)到不同的狀態(tài)集中轉(zhuǎn)到不同的狀態(tài)集中, ,則分別將轉(zhuǎn)到相則分別將轉(zhuǎn)到相同集合中的狀態(tài)組成一個新的狀態(tài)集同集合中的狀態(tài)組成一個新的狀態(tài)集. .35狀態(tài)分離法算法狀態(tài)分離法算法STEP1.STEP1.求初始劃分求初始劃分: : SS= SS=非終止狀態(tài)集非終止狀態(tài)集終止狀態(tài)集。終止狀態(tài)集。STEP2.STEP2.若若SSSS中的每個子集對中

23、的每個子集對每一個每一個a(aa(a) )都都是不可區(qū)分的是不可區(qū)分的, ,則轉(zhuǎn)則轉(zhuǎn)STEP3;STEP3;否則對可分的子集否則對可分的子集按相應(yīng)的按相應(yīng)的a(aa(a) )進行劃分。進行劃分。 轉(zhuǎn)轉(zhuǎn)STEP2STEP2。STEP3.STEP3.每個子集中元素合并為一個狀態(tài)，只含每個子集中元素合并為一個狀態(tài)，只含終態(tài)的集合為一個終態(tài)，對邊作相應(yīng)的調(diào)整。終態(tài)的集合為一個終態(tài)，對邊作相應(yīng)的調(diào)整。36S0S1aba,bS2S3aa,babSTEP1.STEP1.求初始劃分求初始劃分: : SS=S SS=S0 0, S, S1 1SS2 2, S, S3 3 STEP2. SS0 0, S, S1

24、1 是否是可區(qū)分的？是否是可區(qū)分的？S S0 0S S1 1S S0 0S S3 3S S2 2S S1 1SS0 0, S, S1 1 對對a是否是可區(qū)分的？是否是可區(qū)分的？S S0 0S S1 1S S0 0S S1 1S S3 3S S2 2SS0 0, S, S1 1 對對b是否是可區(qū)分的？是否是可區(qū)分的？STEP2. SS2 2, S, S3 3 是否是可區(qū)分的？是否是可區(qū)分的？S S2 2S S3 3S S0 0S S1 1S S2 2S S3 3SS2 2, S, S3 3 對對a是否是可區(qū)分的？是否是可區(qū)分的？S S2 2S S3 3S S0 0S S1 1S S2 2 S S

25、3 3SS2 2, S, S3 3 對對b是否是可區(qū)分的？是否是可區(qū)分的？SS=SSS=S0 0SS1 1SS2 2, S, S3 3 SS=SSS=S0 0SS1 1SS2 2, S, S3 3 aS0S1ba,baS2 , S3最終結(jié)果：最終結(jié)果：37四、已知文法四、已知文法GSGS如下：如下：S S aSAb | a aSAb | aA A Aa | b Aa | b請寫出該文法的遞歸下降語法分析程序（程請寫出該文法的遞歸下降語法分析程序（程序中給出必要的注釋）。序中給出必要的注釋）。解：該文法的產(chǎn)生式中存在左公共前綴和左遞歸，解：該文法的產(chǎn)生式中存在左公共前綴和左遞歸，因此不滿足遞歸下

26、降語法分析條件，因此，需要因此不滿足遞歸下降語法分析條件，因此，需要進行文法變換。進行文法變換。38文法等價變換技術(shù)：消除公共前綴文法等價變換技術(shù)：消除公共前綴 公共前綴公共前綴: :A的不同產(chǎn)生式的右部具有相同的前綴。的不同產(chǎn)生式的右部具有相同的前綴。 這種這種情形不滿足自頂向下的語法分析條件。情形不滿足自頂向下的語法分析條件。 可用提取左因子的方法消除產(chǎn)生式的公共前綴。假定關(guān)可用提取左因子的方法消除產(chǎn)生式的公共前綴。假定關(guān)于的規(guī)則是：于的規(guī)則是：A1 | 2 | n | 1| 2 | m (其中每個其中每個 不以不以 開頭開頭)則將這些規(guī)則寫成：則將這些規(guī)則寫成： A A | 1 |2|m

27、 A 1 | 2 | n經(jīng)過反復(fù)提取左因子，就能夠使每個非終極符的不同產(chǎn)經(jīng)過反復(fù)提取左因子，就能夠使每個非終極符的不同產(chǎn)生式的右部具有不同的前綴。生式的右部具有不同的前綴。39S aSAb | aA Aa | b（1）去除左公共前綴）去除左公共前綴:S aS 1S SAb 2 | 3S aS 1S SAb 2 | 3A Aa | b40文法等價變換技術(shù)文法等價變換技術(shù): :消除直接左遞歸消除直接左遞歸v文法的遞歸性：文法的遞歸性： 對文法中的某個非終極符對文法中的某個非終極符A，若有產(chǎn)生式：，若有產(chǎn)生式：AA，則稱則稱A是是直接左遞歸的直接左遞歸的。 對文法中的某個非終極符對文法中的某個非終極符A，若有產(chǎn)生式：，若有產(chǎn)生式：AA，則稱則稱A是是直接右遞歸的直接右遞歸的。 對文法中的某個非終極符對文法中的某個非終極符A，若有產(chǎn)生式：，若有產(chǎn)生式：AA，則稱，則稱A是是直接遞歸的直接遞歸的。 對文法中的某個非終極符對文法中的某個非終極符