編譯原理典型例題

《編譯原理典型例題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、被5整除且不以0開頭的無符號整數(shù)集合（如{5，10，15}）解答能被5整除的數(shù)從形式上看，是以0，5結(jié)尾的數(shù)字串。題目要求不以0開頭，注意0不是該語言的句子。句子的結(jié)構(gòu)分為三種：5BACB…CA一位數(shù)兩位數(shù)多位數(shù)其中，A代表可以出現(xiàn)在個(gè)位上的數(shù)字，只能是0或5；B代表可以出現(xiàn)在開始位上的數(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寫文法時(shí)，先描述一位數(shù)結(jié)構(gòu)，于是有產(chǎn)生式S→5。對于兩位數(shù)和多位數(shù)，都是以B開頭和以A結(jié)尾，于是有產(chǎn)生式S→DA。用非

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

25、在中間位上的數(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寫文法時(shí)，先描述一位數(shù)結(jié)構(gòu)，于是有產(chǎn)生式S→A。對于兩位數(shù)和多位數(shù)，都是以C開頭和以B結(jié)尾，于是有產(chǎn)生式S→CE。用非終結(jié)符E推導(dǎo)出兩位數(shù)和多位數(shù)中除個(gè)位數(shù)字以外的數(shù)字。對與多位數(shù)，由于中間位可以是許多位，必須使用遞歸技術(shù)來描述其結(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.考慮下面的程序：????…?procedureP(x,y,z);b

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

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

50、是每個(gè)形式參數(shù)對應(yīng)兩個(gè)單元，第一個(gè)單元存放實(shí)參的地址，第二個(gè)單元存放實(shí)參的值。在過程體中對形參