自下而上語法分析習(xí)題

《自下而上語法分析習(xí)題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、自下而上語法分析方法習(xí)題課第五章本章要求1.掌握自下而上分析的基本思想，基本概念2.掌握算符優(yōu)先文法、算符優(yōu)先關(guān)系的判定3.掌握最左素短語、句柄的定義與判定4.掌握求FirstVT集,LastVT集,學(xué)會構(gòu)造算符優(yōu)先關(guān)系表,能用算符優(yōu)先分析法進行表達式分析問題的提出：①在構(gòu)造語法樹的過程中，何時歸約？當(dāng)可歸約串出現(xiàn)在棧頂時就進行歸約。②如何知道在棧頂符號串中已經(jīng)形成可歸約串？如何進行歸約？通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個共同的特點：邊移進邊歸約。規(guī)范歸約：使用句柄來定義可歸約串。算符優(yōu)先：使用最左

2、素短語來定義可歸約串規(guī)范歸約的概念有文法G，開始符號為S,如果有S=>xβy,則xβy是文法G的句型，x,y是任意的符號串如果有S=>xAy,且有A=>β,則β是句型xβy相對于非終結(jié)符A的短語如果有S=>xAy,且有A->β,則β是句型xβy相對于A->β的直接短語位于一個句型最左邊的直接短語稱為句柄.**+*注意:每次歸約的部分必須是句柄(最右推導(dǎo))。關(guān)鍵的問題是如何識別句柄例：考慮如下文法：求句型i1*i2+i3的短語、直接短語和句柄。E?T

3、E+TT?F

4、T*FF?i

5、(E)從語法分析樹來識別：一棵子樹是由樹的某個結(jié)點連同它的所有子孫組成的。子樹

6、的所有端末結(jié)點自左至右排列成一個相對子樹根的短語。直接短語：只有父子兩代結(jié)點形成的短語。句柄：最左子樹的直接短語。EE+TTFi3i2i1T*FF從語法樹可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語直接短語有：i1,i2,i3句柄是：i1E?T

7、E+TT?F

8、T*FF?i

9、(E)句型i1*i2+i3的語法樹如圖：練習(xí)1、令文法G1為：E→E+T

10、TT→T*F

11、FF→(E)

12、i證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。EE+TT*FT*F是句型E+T*F相對于T的短語E+T*F句型E+T*

13、F相對于E的短語T*F是句型E+T*F相對于T的直接短語T*F是句柄2對下述文法，求句型E+T*F+i的短語、直接短語、句柄E?T

14、E+TT?F

15、T*FF?i

16、(E)EE+TFiE+TT*F短語有：i,T*F,E+T*F,E+T*F+i直接短語有：i,T*F句柄是：T*F練習(xí)規(guī)范歸約的定義：假定α是文法G的一個句子，如果序列：αn,αn-1,……,α0(=S)滿足如下條件，則序列αn,αn-1,……,α0是一個規(guī)范歸約:(1)αn=α是給定的句子(2)α0=S是文法的開始符號(3)對任何i,0

17、號而得到的。規(guī)范歸約是最右推導(dǎo)的逆過程，規(guī)范歸約又稱為最左歸約。最右推導(dǎo)又稱規(guī)范推導(dǎo)，由規(guī)范推導(dǎo)所得到的句型稱規(guī)范句型，規(guī)范推導(dǎo)的逆過程是規(guī)范歸約。句型歸約規(guī)則abbcde(2)A?baAbcde(3)A?AbaAcde(4)B?daAcBe(1)S?aAcBeS(1)S?aAcBe(2)A?b(3)A?Ab(4)B?d上述例子中句子abbcde的規(guī)范歸約過程是：abbcde，aAbcde，aAcde，aAcBe，S練習(xí)使用下述文法對句型i1*i2+i3進行規(guī)范規(guī)約:E?T

18、E+TT?F

19、T*FF?i

20、(E)i1*i2+i3,F*i2+i3,T*i

21、2+i3,T*F+i3,T+i3,E+i3,E+F,E+T,EEE+TTFi3i2i1T*FF2、考慮下面的表格結(jié)構(gòu)文法G2：S→a

22、^

23、(T)T→T,S

24、S（1）給出(a,(a,a))和(((a,a),^,(a)),a)的最左和最右推導(dǎo)。(a,(a,a))的最左推導(dǎo)：S?(T)?(T,S)?(S,S)?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a,S))?(a,(a,a))(((a,a),^,(a)),a)的最左推導(dǎo)：S?(T)?(T,S)?(S,S)?((T),S)?((T,S),S)?((T,S,S),S)?((

25、S,S,S),S)?(((T,S),S,S),S)?(((S,S),S,S),S)?(((a,S),S,S),S)?(((a,a),S,S),S)?(((a,a),^,S),S)?(((a,a),^,a),S)?(((a,a),^,a),a)(((a,a),^,(a)),a)的最右推導(dǎo)：S?(T)?(T,S)?(S,S)?(S,a)?((T),a)?((T,S,S),S)?((S,S,S),S)?(((T,S),S,S),S)?(((S,S),S,S),S)?(((a,S),S,S),S)?(((a,a),S,S),S)?(((a,a),^,S),S)?

26、(((a,a),^,a),S)?(((a,a),^,a),a)(a,(a,a))