湖南大學《編譯原理》考前復習資料典型例題.doc

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

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

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

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

4、5B→1

5、2

6、3

7、4

8、5

9、6

10、7

11、8

12、9C→0

13、B寫文法時，先描述一位數結構，于是有產生式S→5。對于兩位數和多位數，都是以B開頭和以A結尾，于是有產生式S

14、→DA。用非終結符D推導出兩位數和多位數中除個位數字以外的數字。對與多位數，由于中間位可以是許多位，必須使用遞歸技術來描述其結構。于是有產生式：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.寫一個文法G,使其語言為不以0開頭的偶數集。解答16不以0開頭的偶數集數字的結構分為三種：一位數、兩位數和多位數。ACBDC…DB一位數兩位數多位數其中，A代表可以出現在個位上的數字，可以是2，4，6，8，但不能是0；B代表可以出現在開始位上的數字，除了0以外，其他數字都可以

25、；C代表可以出現在中間位上的數字。0-9所有數字都可以。于是，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寫文法時，先描述一位數結構，于是有產生式S→A。對于兩位數和多位數，都是以C開頭和以B結尾，于是有產生式S→CE。用非終結符E推導出兩位數和多位數中除個位數字以外的數字。對與多位數，由于中間位可以是許多位，必須使用遞歸技術來描述其結構。于是有產生式：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.試問，若參數傳遞的方式分別采用傳值、傳地址、得結果和傳名時，程序執(zhí)行后輸出a的值是什么?解答所謂傳值是調用段把實在參數的值計算出來，被調用段把這些值抄進自己的形式參數中，像使用局部名一樣使用這些形式單元。對形式參數的任何運算不影響實參的值。上面過程P調用的的參數傳遞過程如下圖所示。過程調用前過程調用后a+b=5a=2x=5y=2b=3z=3但過程P無法改變實參a的值。因此，程序執(zhí)行后輸出a的值是2。所謂傳

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

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