編譯原理分知識(shí)點(diǎn)習(xí)題 自下而上語(yǔ)法分析

《編譯原理分知識(shí)點(diǎn)習(xí)題 自下而上語(yǔ)法分析》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、1．★已知文法G[S]：S→SaA

2、AA→AbB

3、BB→cSd

4、e請(qǐng)證實(shí)AacAbcBaAdbed是文法的一個(gè)句型，并寫(xiě)出該句型的所有短語(yǔ)、素短語(yǔ)以及句柄。解：本題考查“句型”、“短語(yǔ)”、“句柄”、“素短語(yǔ)”等概念。符號(hào)棧S關(guān)系輸入串最左素短語(yǔ)S1S2S3S4S5S6S7R1R2R3R4R5R6＃<(adb)##<(db)#d#<(V)#b#<(V)#VdV#<(V=)##<(=V)>#(V)#V#接受因?yàn)榇嬖趶奈姆ㄩ_(kāi)始符號(hào)S到符號(hào)串AacAbcBaAdbed的推導(dǎo)過(guò)程（如圖

5、6.1中的語(yǔ)法樹(shù)所示），所以符號(hào)串AacAbcBaAdbed是文法的句型。從圖6.1中句型A1a1c1A2b1c2Ba2A3d1b2ed2的語(yǔ)法樹(shù)可知，該句型的短語(yǔ)有：A1、B、Ba2A3、c2Ba2A3d1、A2b1c2Ba2A3d1、e、A2b1c2Ba2A3d1b2e、c1A2b1c2Ba2A3d1b2ed2、A1a1c1A2b1c2Ba2A3d1b2ed2該句型的素短語(yǔ)有：Ba2A3、e該句型的句柄為：B2．★已知文法G[S]：S→*AA→0A1

6、*（1）求文法G的各非終結(jié)符號(hào)的FIRSTVT集和LASTVT集;（2）構(gòu)造文法G的優(yōu)先關(guān)系矩陣，并

7、判斷該文法是否是算符優(yōu)先文法；（3）分析句子*0*1，并寫(xiě)出分析過(guò)程。解：本題考查算符優(yōu)先分析法中的有關(guān)知識(shí)：非終結(jié)符號(hào)的FIRSTVT集和LASTVT集的求法、算符優(yōu)先關(guān)系的構(gòu)造、算符優(yōu)先文法的定義、算符優(yōu)先分析過(guò)程等。（1）求文法G的各非終結(jié)符號(hào)的FIRSTVT集和LASTVT集。根據(jù)非終結(jié)符號(hào)的FIRSTVT集定義得到FIRSTVT（S）＝｛*｝FIRSTVT（S）＝｛0，*｝根據(jù)非終結(jié)符號(hào)的LASTVT集定義得到LASTVT（S）＝｛*，1｝LASTVT（S）＝｛1，*｝SSa1AA1Bc1Sd2AAb2BA2b1Bec2Sd1Sa2A3AB圖6

8、.1句型AacAbcBaAdbed的語(yǔ)法樹(shù)（1）構(gòu)造文法G的優(yōu)先關(guān)系矩陣。根據(jù)（1）中的FIRSTVT集和LASTVT集及算符優(yōu)先關(guān)系構(gòu)造算法對(duì)S→*A，按算法第3種情形有：（*<0），（*<*）對(duì)A→0A1，按算法第1種情形有：（0

9、＝1）按算法第3種情形有：（0

10、<0）,(0

11、<*)按算法第4種情形有：（1

12、>1），(*

13、>1),根據(jù)上述算符優(yōu)先關(guān)系得到算符優(yōu)先關(guān)系矩陣如表6.1所示。表中空白元素表示相應(yīng)終結(jié)符號(hào)對(duì)之間沒(méi)有算符優(yōu)先關(guān)系，即它們不會(huì)在任何句型中相繼出現(xiàn)。表6.1文法的算符優(yōu)先關(guān)系矩陣01*0

14、<

15、=

16、<1

17、>*

18、<

19、>

20、<(3)對(duì)句子“

21、*0*1#”分析過(guò)程如表6.2所示。表6.2分析輸入符號(hào)串“*0*1#”的過(guò)程符號(hào)棧S關(guān)系輸入串最左素短語(yǔ)S1S2S3S4S5S6S7R1R2R3R4R5#<*0*1##<*<0*1##<*<0<*1##<*<0<*>1#*#<*<0V=##<*<0V=1>#0V1#<*V>#*V#V#接受3．試為下列優(yōu)先矩陣構(gòu)造優(yōu)先函數(shù)。（1）S1S2S3S4S1S2±±S3>>S4>>(2)S1S2S3S4S1>>S2>S3<±

22、代：S1S2S3S4f1122g1111第2次迭代：S1S2S3S4f1122g1111第2次迭代沒(méi)有變化，所以第2次迭代結(jié)果便是優(yōu)先函數(shù)。（3）采用Bell有向圖法構(gòu)造優(yōu)先函數(shù)(省略)。因?yàn)閒s1可以到達(dá)的結(jié)點(diǎn)：gs3，gs4，fs4，gs3，gs2fs2可以到達(dá)的結(jié)點(diǎn)：gs3，fs3，gs2，fs4，gs1fs3可以到達(dá)的結(jié)點(diǎn)：gs2，fs3fs4可以到達(dá)的結(jié)點(diǎn)：gs1，gs3，fs3，gs2，fs4gs1可以到達(dá)的結(jié)點(diǎn)：fs3，fs4，gs2，gs1，gs3gs2可以到達(dá)的結(jié)點(diǎn)：fs3，gs2gs3可以到達(dá)的結(jié)點(diǎn)：fs4，fs3，gs1，gs3，g

23、s2gs4可以到達(dá)的結(jié)點(diǎn)：無(wú)于是得到優(yōu)先函數(shù)如表6.3所示。S1S2S3S4f7625g52514.試為文法G[Z]：Z→A()A→(

24、Ai

25、B)B→i構(gòu)造算符優(yōu)先關(guān)系和優(yōu)先函數(shù)。解：本題考查算符優(yōu)先關(guān)系的構(gòu)造方法和優(yōu)先函數(shù)的構(gòu)造方法。（1）構(gòu)造算符優(yōu)先關(guān)系。首先構(gòu)造FIRSTVT集和LASTVT集，根據(jù)定義有：FIRSTVT（Z）＝｛（，i，）｝FIRSTVT（A）＝｛（，i，）｝FIRSTVT（B）＝｛i｝和LASTVT（Z）＝｛｝｝LASTVT（A）＝｛（，），i｝LASTVT（B）＝｛i｝按照構(gòu)造算符優(yōu)先關(guān)系的算法得到如下算符優(yōu)先關(guān)系：“＝”的構(gòu)

26、造∵有產(chǎn)生式Z→A（）∴按算法第1種情形有：（（＝））“<”的構(gòu)造文法沒(méi)有滿足“