自下而上語(yǔ)法分析習(xí)題.ppt

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

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

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

3、。E?T

4、E+TT?F

5、T*FF?i

6、(E)從語(yǔ)法分析樹來(lái)識(shí)別：一棵子樹是由樹的某個(gè)結(jié)點(diǎn)連同它的所有子孫組成的。子樹的所有端末結(jié)點(diǎn)自左至右排列成一個(gè)相對(duì)子樹根的短語(yǔ)。直接短語(yǔ)：只有父子兩代結(jié)點(diǎn)形成的短語(yǔ)。句柄：最左子樹的直接短語(yǔ)。EE+TTFi3i2i1T*FF從語(yǔ)法樹可以看出：i1,i2,i3,i1*i2,i1*i2+i3是句型i1*i2+i3的短語(yǔ)直接短語(yǔ)有：i1,i2,i3句柄是：i1E?T

7、E+TT?F

8、T*FF?i

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

10、

11、TT→T*F

12、FF→(E)

13、i證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。EE+TT*FT*F是句型E+T*F相對(duì)于T的短語(yǔ)E+T*F句型E+T*F相對(duì)于E的短語(yǔ)T*F是句型E+T*F相對(duì)于T的直接短語(yǔ)T*F是句柄2對(duì)下述文法，求句型E+T*F+i的短語(yǔ)、直接短語(yǔ)、句柄E?T

14、E+TT?F

15、T*FF?i

16、(E)EE+TFiE+TT*F短語(yǔ)有：i,T*F,E+T*F,E+T*F+i直接短語(yǔ)有：i,T*F句柄是：T*F練習(xí)規(guī)范歸約的定義：假定α是文法G的一個(gè)句子，如果序列：

17、αn,αn-1,……,α0(=S)滿足如下條件，則序列αn,αn-1,……,α0是一個(gè)規(guī)范歸約:(1)αn=α是給定的句子(2)α0=S是文法的開始符號(hào)(3)對(duì)任何i,0

18、S?aAcBe(2)A?b(3)A?Ab(4)B?d上述例子中句子abbcde的規(guī)范歸約過(guò)程是：abbcde，aAbcde，aAcde，aAcBe，S練習(xí)使用下述文法對(duì)句型i1*i2+i3進(jìn)行規(guī)范規(guī)約:E?T

19、E+TT?F

20、T*FF?i

21、(E)i1*i2+i3,F*i2+i3,T*i2+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),^,(

25、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)?((S,S,S),S)?(((T,S),S,S),S)?(((S,S),S,S),S)?(((a,S),S,S),S)?(((a,a),S,S),S)?(((

26、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)?(((a,a),^,a),S)?(((a,a),^,a),a)(a,(a,a))