【文章內(nèi)容簡(jiǎn)介】 _, _, (1))D:=ACE:=A*CF:=D*EM:=F+207. 最左推導(dǎo)S=(T)=(T,S)=(S,S)=(a,S)=(a,(T))=(a,(T,S))=(a,(S,S))=(a,(a,S))=(a,(a,a))短語(yǔ) ((T,S),a) (T,S),a (T,S) T,S a直接短語(yǔ) T,S a句柄 T,S8.(1)S→do M1 S1 while M2 EM→ε (2)M→ε {=nestquad。}S→do M1 S1 while M2 E {backpatch(, )。 backpatch(, )。 =。 }9.(1) S=aAcBe=AAbcBe=abbcBe=abbcde(2) 短語(yǔ): aAbcde, Ab, d 素短語(yǔ): Ab, d10.(1) S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε} FIRST(L)={a, (} FIRST(L’)={, ε}FOLLOW(S)={, ), } FOLLOW(S’)={, ), }FOLLOW(L)={ )} FOLLOW(L’)={ )}(3) ( ) a , SS →(L)S → aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’ L’L’→ε11.(1) (j, X, 0, (5))(2) (j, _, _, (3))(3) (j, Y, 0, (5))(4) (j, _, _, (11))(5) (j0, X, 0, (7))(6) (j, _, _, (7))(7) (*, A, 3, T1)(8) (:=, T1, _, N)(9) (j, _, _, (5))(10) (j, _, _, (13))(11) (+, B, 3, T2)(12) (:=, T2, _, Y)12.(1) E=E+T=T+T=T*F+T=F*F+T=(E)*F+T=(E+T)*F+T=(T+T)*F+T =(F+T)*F+T=(i+T)*F+T=(i+F)*F+T=(i+i)*F+T=(i+i)*i+T =(i+i)*i+F=(i+i)*i+i (2) 短語(yǔ) i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短語(yǔ) i, E+T最左素短語(yǔ) E+T13.(1) FIRSTVT(S)={∨, ∧, i, } FIRSTVT(T)={∧, i, } FIRSTVT(U)={i, } LASTVT(S)={∨, ∧, i, }LASTVT(T)={∧, i, } LASTVT(U)={i, }(2) i ∨ ∧ S . .∨ . . . .∧ . . . . . . . .描述由正規(guī)式b*(abb*)*(a| e)定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。證明文法E 174。 E + id | id是SLR(1)文法。下面是表達(dá)式和賦值語(yǔ)句的文法，其中and的類(lèi)型是bool 180。 bool 174。 bool，+的類(lèi)型是int 180。 int 174。 int，=的類(lèi)型是int 180。 int 174。 bool，:= 要求id 和E的類(lèi)型都是int或者都是bool。為該文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案，它完成類(lèi)型檢查。S 174。 id := EE 174。 E and E | E + E | E = E |id f1(int x) { long x。 x = 1。 } f2(int x) { { long x。 x = 1。 } }某編譯器編譯時(shí)報(bào)錯(cuò)如下： : In function ‘f1’: :3: warning: declaration of ‘x’ shadows a parameter請(qǐng)回答，對(duì)函數(shù)f2為什么沒(méi)有類(lèi)似的警告錯(cuò)誤。 下面C語(yǔ)言程序經(jīng)非優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是 area=, addr=1073743076經(jīng)優(yōu)化編譯后，若運(yùn)行時(shí)輸入2，則結(jié)果是 area=, addr=1073743068請(qǐng)解釋為什么輸出結(jié)果有區(qū)別。main(){ float s, pi, r。 pi=。 scanf(%f, amp。r)。 printf(area=%f, addr=%d\n, s=pi*r*r, amp。r)。}描述由正規(guī)式b*a(bb*a) *b*定義的語(yǔ)言，并畫(huà)出接受該語(yǔ)言的最簡(jiǎn)DFA。下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集： B 174。 B 0 | B 1 | 1 下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值： B 174。 B1 0 { := 180。 2 } | B1 1 { := 180。 2 +1} | 1 { := 1 } 請(qǐng)消除該基礎(chǔ)文法的左遞歸，再重寫(xiě)一個(gè)翻譯方案，它仍然計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值。 在C語(yǔ)言中，如果變量i和j都是long類(lèi)型，請(qǐng)寫(xiě)出表達(dá)式amp。i和表達(dá)式amp。iamp。j的類(lèi)型表達(dá)式。為幫助你回答問(wèn)題，下面給出一個(gè)程序作為提示，它運(yùn)行時(shí)輸出1。 main() { long i, j。 printf(“%d\n”, amp。iamp。j)。 }一個(gè)C語(yǔ)言的函數(shù)如下： func(i) long i。 { long j。 j = i – 1。 func(j)。 }下面左右兩邊的匯編代碼是兩個(gè)不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對(duì)參數(shù)傳遞的處理方式?jīng)]有實(shí)質(zhì)區(qū)別。請(qǐng)敘述右邊代碼對(duì)參數(shù)傳遞的處理方式并推測(cè)它帶來(lái)的優(yōu)點(diǎn)。 func: | func: pushl %ebp | pushl %ebp movl %esp, %ebp | movl %esp, %ebp subl $4, %esp | subl $8, %esp movl 8(%ebp), %edx | movl 8(%ebp), %eax decl %edx | decl %eax movl %edx, 4(%ebp) | movl %eax, 4(%ebp) movl 4(%ebp), %eax | movl 4(%ebp), %eax pushl %eax | movl %eax, (%esp) call func | call func addl $4, %esp | leave leave | ret ret |編譯原理試卷八答案start1abb2由正規(guī)式b*(abb*)*(a| e)定義的語(yǔ)言是字母表{a, b}上不含子串a(chǎn)a的所有串的集合。最簡(jiǎn)DFA如下：先給出接受該文法活前綴的DFA如下：E162。 174。EE 174。E + idE 174。idI0E162。 174。 EE 174。 E+ idI1E 174。 idI2Eid+E 174。 E +idI3E 174。 E + idI4idI0和I3都只有移進(jìn)項(xiàng)目，肯定不會(huì)引起沖突；I2和I4都無(wú)移進(jìn)項(xiàng)目并僅含一個(gè)歸約項(xiàng)目，也肯定不會(huì)引起沖突；在I1中，E162。的后繼符號(hào)只有$，同第2個(gè)項(xiàng)目的展望符號(hào)“+”不一樣，因此I1也肯定不會(huì)引起沖突。由此可以斷定該文法是SLR(1)的。語(yǔ)法制導(dǎo)定義如下。S 174。 id := E { := if ( = bool and = bool) or ( = int and = int)then type_ok else type_error }E 174。 E1 and E2 { := if = bool and = bool then bool else type_error }E 174。 E1 + E2 { := if = int and = int then int else type_error }E 174。 E1 = E2 { := if = int and = int then bool else type_error }E 174。 id { := lookup() }對(duì)于函數(shù)f1，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪(fǎng)問(wèn)形式參數(shù)x。由于這是一個(gè)合法的C語(yǔ)言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會(huì)出現(xiàn)上述問(wèn)題，因而編譯器不報(bào)錯(cuò)。使用非優(yōu)化編譯時(shí)，變量s, pi, r在局部數(shù)據(jù)區(qū)都分配4個(gè)字節(jié)的空間。使用優(yōu)化編譯時(shí)，由于復(fù)寫(xiě)傳播，pi*r*r *r*r，pi=，函數(shù)中不再有pi的引用，因此不必為pi分配空間。類(lèi)似地，s=*r*r也是一個(gè)無(wú)用賦值（表達(dá)式要計(jì)算，但賦值是無(wú)用的），也不必為s分配空間。這樣，和非優(yōu)化情況相比，局部數(shù)據(jù)區(qū)少了8個(gè)字節(jié)， 因此r的地址向高地址方向移動(dòng)了8個(gè)字節(jié)。正規(guī)式b*a(bb*a) *b*體現(xiàn)的特點(diǎn)是，每個(gè)a的左邊都有若干b，除非a是第一個(gè)字母。該正規(guī)式定義的語(yǔ)言是：至少含一個(gè)a，但不含子串a(chǎn)a的所有a和b的串集。最簡(jiǎn)DFA如下：start2abb10ab 消除左遞歸后的文法： B 174。 1 B162。 B162。 174。 0 B162。 | 1 B162。 | e 相應(yīng)的翻譯方案如下： B 174。 1 {B162。.i := 1 }B162。{ := B162。.val} B162。 174。 0 {B162。 := B162。.i 180。 2 } B162。1 {B162。.val := B162。} | 1 {B162。 := B162。.i 180。 2 +1} B162。1 {B162。.val := B162。} | e {B162。.val := B162。.i}表達(dá)式amp。i的類(lèi)型表達(dá)式是pointer(long)，表達(dá)式amp。iamp。j的類(lèi)型表達(dá)式是long。按照C語(yǔ)言的規(guī)定，指向同一個(gè)類(lèi)型的兩個(gè)指針可以相加減，它們值的差是它們之間的元素個(gè)數(shù)。左邊的編譯器版本：一般只為局部變量分配空間。調(diào)用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返回后用addl $n, %esp一次將所有參數(shù)退棧（常數(shù)n根據(jù)調(diào)用前做了多少次pushl來(lái)決定）。 右邊的編譯器版本：除了為局部變量分配空間外，同時(shí)還為本函數(shù)中出現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間靠近棧頂。調(diào)用函數(shù)前，用movl指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無(wú)需參數(shù)退棧指令。 優(yōu)點(diǎn)是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行addl $n, %esp指令，另外增加優(yōu)化的可能性。《編譯原理》期末試題（三） 從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類(lèi)？對(duì)循環(huán)的優(yōu)化可以有哪三種？ 答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化兩類(lèi)；對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。寫(xiě)出表達(dá)式a=b*c+b*d對(duì)應(yīng)的逆波蘭式、四元式序列和三元式序列。 答：逆波蘭式： abc*bd*+:= 四元式序列： 三元式序列: OP ARG1 ARG2(1) (*， b， c， t1) (1) (* b， c )(2) (*， b， d， t2) (2) (* b， d )(3) (+， t1， t2，t3) (3) (+ (1)， (2))(4) (:=， t3， /， a) (4) (:= (3)， a)對(duì)于文法G(S): SbM(TMabL)答：1） 2） 短語(yǔ): Ma