編譯原理練習題

.名詞解釋：前綴2)可歸前綴3)活前綴4)簡單短語5)掃描遍6)句柄7)句型8)句子9)非終結(jié)符10)終結(jié)符11)屬性文法12)語法制導翻譯13)后綴式14)短語15)基本塊二．簡答題：什么是句子？什么是語言?DFA與NFA有何區(qū)別？自頂向下語法分析的思想是什么？一個上下文無關(guān)文法G包括哪四個組成部分？在自底向上的語法分析方法中，分析的關(guān)鍵是什么？在自頂向下的語法分析方法中，分析的關(guān)鍵是什么？編譯程序中語法分析器接收以什么為單位的輸入？若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是可枚舉的嗎？編譯程序生成的目標程序是不是一定是機器語言的程序？詞法分析器是用于識別句型、句子、還是單詞的？“用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標代碼后才能投入運行”這種說法正確嗎？把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由什么完成的？自底向上的語法分析方法的基本思想是什么?圖示運行時存儲空間的劃分(分為哪幾個區(qū))。詞法分析的主要任務是什么？常用的中間語言種類有哪幾種？文法G所描述的語言是什么的集合？喬姆斯基把文法分為四種類型，即 0型、1型、2型、3型。其中2型文法叫什么？編譯程序是一種解釋程序還是什么程序？按邏輯上劃分，編譯程序第二步工作是什么？源程序是用高級語言編寫的，目標程序是機器語言程序或匯編程序，則其翻譯程序稱為什么？編譯方式與解釋方式的根本區(qū)別為什么？常見的兩種動態(tài)存貯分配策略有哪兩種？常用的參數(shù)傳遞方式有哪三種？語法分析的任務是什么？局部優(yōu)化是局限于一個什么范圍內(nèi)的一種優(yōu)化？文法等價的定義是什么？在語法分析處理中， FIRST集合、FOLLOW!合、SELECT集合均是什么集合？通常一個編譯程序中應包括哪七個部分？如果編譯程序生成的目標程序是匯編語言程序， 則源程序的執(zhí)行分為哪三個階段？翻譯程序是這樣一種程序， 它能夠?qū)⒂檬裁崔D(zhuǎn)換成與其等價的用乙語言書寫的程序？在屬性文法中，綜合屬性與繼承屬性是如何傳遞信息的？代碼優(yōu)化的主要目標是什么？

三?應用題消除下列文法G[A]的左遞歸。iE-TITT/FIF1(E)Ii消除下列文法G[A]的左遞歸。A^AaBIBBbCIC3eDIDD^(A)Id3)b其中：開始狀態(tài)：0終止狀態(tài)：2把此自動機轉(zhuǎn)換為確定自動機 DFA給定下列自動機:開始狀態(tài)：S、P終止狀態(tài)：Z把此自動機轉(zhuǎn)換為確定自動機 DFA為正規(guī)R=(ab)*a(ab)*a(ba)*構(gòu)造一個等價的有限自動機。為正規(guī)式(a|b)a(a|b)構(gòu)造一個等價的有限自動機。四.設計題{print:“{print:“0”}{print:“1”}{print:“2”}{print:“3”}1.StS2.StaAAtAbAtd符號串a(chǎn)dbb是不是該文法的一個句子，請證實。若是句子，寫出該句型的所有短語、簡單短語，以及句柄。對于adbb這個輸入符號串，該翻譯方案的輸出是什么？

(2)給定文法:StbTcSta(3)TtR(4)RtR/S(5)RtS符號串ba/ac是不是該文法的一個句子，請證實。若是句子，寫出該句子的所有短語、簡單短語和句柄。為該文法設計翻譯方案，使句型bR/bTc/bSc/ac經(jīng)該翻譯方案翻譯后輸出下列串：0342031320(3)設有基本塊：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-E畫出DAG圖；假設基本塊出口時只有 E，碼序列。(4)設有基本塊：T1:=2T2:=10/T1T3:=S-RT4:=S+RA:=T2*T4B:=AT5:=S+RT6:=T3*T5B:=T6畫出DAG圖；假設基本塊出口時只有 A，F(xiàn)還被引用，請寫出優(yōu)化后的三地址代BF還被引用，請寫出優(yōu)化后的三地址代B還被引用，請寫出優(yōu)化后的三地址代給定文法G[S']:(0)S'tsSteSStfSSte文法G屬于chomsky哪一型文法？符號串effe是不是該文法的一個句子，請證實。若是句子，寫出該句型的所有短語、簡單短語，以及句柄。構(gòu)造識別該文法的活前綴的 DFA判斷該文法是LR(0)還是SLR(1)，并構(gòu)造其分析表。對于effe這個輸入符號串，該翻譯方案的輸出是什么？給定文法G[S']:0.StS1.StaAAtAbAtd文法G屬于chomsky哪一型文法？符號串a(chǎn)dbb是不是該文法的一個句子，請證實。若是句子，寫出該句型的所有短語、簡單短語，以及句柄。構(gòu)造識別該文法的活前綴的 DFA判斷該文法是LR(0)還是SLR(1),并構(gòu)造其分析表。對于adbb這個輸入符號串，該翻譯方案的輸出是什么？五?轉(zhuǎn)換題：給定下列中綴式(運算符優(yōu)先級按常規(guī)理