湖南大學(xué)《編譯原理》考前復(fù)習(xí)資料典型例題.doc

《湖南大學(xué)《編譯原理》考前復(fù)習(xí)資料典型例題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、典型案例1.對(duì)于文法G[S]S→(L)S→aSS→aL→L,SL→S(1)畫(huà)出句型(S,(a))的語(yǔ)法樹(shù)；(2)寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。解答這類題目重點(diǎn)考查語(yǔ)法樹(shù)、推導(dǎo)、短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)等基本概念。在句型中尋找短語(yǔ)、直接短語(yǔ)、句柄的方法：(1)畫(huà)出句型對(duì)應(yīng)的語(yǔ)法樹(shù)。句型(S,(a))的語(yǔ)法樹(shù)如下圖所示S(L)S(L)L,SSa(2)在該語(yǔ)法樹(shù)中尋找短語(yǔ)、直接短語(yǔ)、句柄。首先我們看短語(yǔ)的定義：令G是一個(gè)文法，S是文法的開(kāi)始符，假設(shè)α,β,δ是文法G的句型，如果有S*TαAδ且A+Tβ則稱β是句型αβδ相對(duì)于非終

2、結(jié)符A的短語(yǔ)。如果有ATβ，則稱β是句型αβδ相對(duì)于規(guī)則A→β的直接短語(yǔ)。一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。根據(jù)短語(yǔ)的定義可知，以非終結(jié)符A為根的子樹(shù)的葉結(jié)點(diǎn)從左到右排列就是相對(duì)于非終結(jié)符A的短語(yǔ)；如果子樹(shù)只有兩代，則短語(yǔ)就是直接短語(yǔ)；最左邊的兩代子樹(shù)的所有葉結(jié)點(diǎn)從左到右排列，就是該句型的句柄。素短語(yǔ)是一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符，且除自身外不再包含其他素短語(yǔ)。處于句型最左邊的素短語(yǔ)為最左素短語(yǔ)。從語(yǔ)法樹(shù)中我們可以找到：短語(yǔ)：a，S，(a)，S,(a)，(S,(a))直接短語(yǔ)：a，S16句柄：S素短語(yǔ)：a1.寫(xiě)一個(gè)上下文無(wú)關(guān)文法，使其語(yǔ)

3、言能被5整除且不以0開(kāi)頭的無(wú)符號(hào)整數(shù)集合（如{5，10，15}）解答能被5整除的數(shù)從形式上看，是以0，5結(jié)尾的數(shù)字串。題目要求不以0開(kāi)頭，注意0不是該語(yǔ)言的句子。句子的結(jié)構(gòu)分為三種：5BACB…CA一位數(shù)兩位數(shù)多位數(shù)其中，A代表可以出現(xiàn)在個(gè)位上的數(shù)字，只能是0或5；B代表可以出現(xiàn)在開(kāi)始位上的數(shù)字，除了0以外，其他數(shù)字都可以；C代表可以出現(xiàn)在中間位上的數(shù)字。0-9所有數(shù)字都可以。于是，A→0

4、5B→1

5、2

6、3

7、4

8、5

9、6

10、7

11、8

12、9C→0

13、B寫(xiě)文法時(shí)，先描述一位數(shù)結(jié)構(gòu)，于是有產(chǎn)生式S→5。對(duì)于兩位數(shù)和多位數(shù)，都是以B開(kāi)頭和以A結(jié)尾，于是有產(chǎn)生式S

14、→DA。用非終結(jié)符D推導(dǎo)出兩位數(shù)和多位數(shù)中除個(gè)位數(shù)字以外的數(shù)字。對(duì)與多位數(shù)，由于中間位可以是許多位，必須使用遞歸技術(shù)來(lái)描述其結(jié)構(gòu)。于是有產(chǎn)生式：D→DCD→B因此，所求文法為G[S]：S→5S→DAD→DCD→BA→0

15、5B→1

16、2

17、3

18、4

19、5

20、6

21、7

22、8

23、9C→0

24、B2.寫(xiě)一個(gè)文法G,使其語(yǔ)言為不以0開(kāi)頭的偶數(shù)集。解答16不以0開(kāi)頭的偶數(shù)集數(shù)字的結(jié)構(gòu)分為三種：一位數(shù)、兩位數(shù)和多位數(shù)。ACBDC…DB一位數(shù)兩位數(shù)多位數(shù)其中，A代表可以出現(xiàn)在個(gè)位上的數(shù)字，可以是2，4，6，8，但不能是0；B代表可以出現(xiàn)在開(kāi)始位上的數(shù)字，除了0以外，其他數(shù)字都可以

25、；C代表可以出現(xiàn)在中間位上的數(shù)字。0-9所有數(shù)字都可以。于是，A→2

26、4

27、6

28、8B→0

29、AC→1

30、3

31、5

32、7

33、9

34、AD→0

35、C寫(xiě)文法時(shí)，先描述一位數(shù)結(jié)構(gòu)，于是有產(chǎn)生式S→A。對(duì)于兩位數(shù)和多位數(shù)，都是以C開(kāi)頭和以B結(jié)尾，于是有產(chǎn)生式S→CE。用非終結(jié)符E推導(dǎo)出兩位數(shù)和多位數(shù)中除個(gè)位數(shù)字以外的數(shù)字。對(duì)與多位數(shù)，由于中間位可以是許多位，必須使用遞歸技術(shù)來(lái)描述其結(jié)構(gòu)。于是有產(chǎn)生式：E→CEE→B因此，所求文法為G(S)：S→A

36、CEE→CE

37、BA→2

38、4

39、6

40、8B→0

41、AC→1

42、3

43、5

44、7

45、9

46、AD→0

47、C4.考慮下面的程序：????…?procedu

48、reP(x,y,z);beginy:=y+1;z:=z+xend;begina:=2;b:=3;16P(a+b,a,a);printaend.試問(wèn)，若參數(shù)傳遞的方式分別采用傳值、傳地址、得結(jié)果和傳名時(shí)，程序執(zhí)行后輸出a的值是什么?解答所謂傳值是調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來(lái)，被調(diào)用段把這些值抄進(jìn)自己的形式參數(shù)中，像使用局部名一樣使用這些形式單元。對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。上面過(guò)程P調(diào)用的的參數(shù)傳遞過(guò)程如下圖所示。過(guò)程調(diào)用前過(guò)程調(diào)用后a+b=5a=2x=5y=2b=3z=3但過(guò)程P無(wú)法改變實(shí)參a的值。因此，程序執(zhí)行后輸出a的值是2。所謂傳

49、地址是把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。在過(guò)程段中每個(gè)形式參數(shù)都有一個(gè)相應(yīng)的單元，稱為形式單元。形式單元將用來(lái)存放相應(yīng)實(shí)在參數(shù)的地址。過(guò)程體對(duì)形式參數(shù)的任何引用或賦值都被處理成對(duì)形式單元的間接訪問(wèn)。過(guò)程調(diào)用前過(guò)程調(diào)用后a+b=5a=2xyb=3z過(guò)程調(diào)用后，形參x的形式單元指向存a+b值的臨時(shí)變量的地址，形參y的形式單元指向變量a的地址，形參z的形式單元指向變量b的地址。形參通過(guò)指針可以間接訪問(wèn)實(shí)參。執(zhí)行y:=y+1;后，實(shí)在參數(shù)的變化：16a+b=5a=3xyb=3z執(zhí)行z:=z+x;后，實(shí)參的變化：a+b=5a=8xyb=3z因此，程序

50、執(zhí)行后輸出a的值是8。所謂得結(jié)果是每個(gè)形式參數(shù)對(duì)應(yīng)兩個(gè)單元，第一個(gè)單元存放實(shí)參的地址，第二個(gè)單元存放實(shí)參的值。在過(guò)程體中對(duì)形參的任何引用或賦值都被處理