《《編譯原理》期末考試復習重點劃分_20120314》由會員分享，可在線閱讀，更多相關《《編譯原理》期末考試復習重點劃分_20120314（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,編譯原理,期末總復習,2,選擇、填空,3,計算機執(zhí)行高級語言的方式有編譯和解釋方式。,對于編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結果是目標程序,。,程序語言主要由語法和語義兩方面定義。,4,上下文無關文法,G,是一個四元式（,V,T,，,V,N,，,S,，,P,），其中,V,N,代表非終結符號集。,詞法分析階段的主要任務是掃描源程序，識別出一個個的單詞符號,自上而下分析方法會遇到的主要問題有左遞歸和回溯,。,設,G,是一個給定的文法，,S,是文法的開始符號，如果,S x,，則稱,x,是文法,G,的一個句型,。
2、,5,已知文法,G,：,E,i|EAE,，,A,+|*,，其中的終結符號集包括,i,，,+,，,*,編譯程序是將高級語言程序翻譯成匯編語言或機器語言程序。,文法,G,所產(chǎn)生的句子的全體是該文法所描述的語言。,6,喬姆斯基定義的四種文法分別為,0,，,1,，,2,，,3,四種類型或者（短語文法、上下文有關文法、上下文無關文法、正規(guī)文法）。,自上而下語法分析方法的基本思想是：從開始符號（根節(jié)點）出發(fā)，自上而下的為輸入串建立一棵語法樹。,常見的中間語言形式有后綴式和三地址代碼、,DAG,圖等。,五元式不屬于常用的中間語言形式。,7,只含有綜合屬性的屬性文法稱,S-,屬性文法。,算符優(yōu)先分析方法每次都
3、是對最左素短語進行規(guī)約。,LL,（,1,）文法中第一個,L,的含義是從左到右掃描輸入串。,用高級語言書寫的程序經(jīng)編譯后產(chǎn)生的程序叫目標程序,.,上下文無關文法,G,是一個四元式（,V,T,，,V,N,，,S,，,P,），其中,S,代表開始符號,。,8,匯編程序是將匯編語言翻譯成機器語言。,DMA,的五元式定義中,S,的含義是狀態(tài)的集合。,文法,G,所產(chǎn)生的句子的全體是該文法所描述的語言,。,優(yōu)化階段的主要任務是對于前段產(chǎn)生的中間代碼進行加工變換，以期在最后產(chǎn)生高效的目標代碼。,9,算符優(yōu)先分析方法每次都是對最左素短語進行規(guī)約。,LL,（,1,）文法中第二個,L,的含義是最左推導。,10,簡答題
4、,11,編譯程序的工作過程主要包括,5,個階段，分別為詞法分析、語法分析、語義分析與中間代碼產(chǎn)生、優(yōu)化和目標代碼生成等。,12,有限自動機中,DFA,的定義,：,DFA M,是一個五元式,M=,（,S,，,，,S0,，,F,），,1.S,有限集，其中的每個元素稱為一個狀態(tài),2.,有窮字母表，其中的每個元素稱為一個輸入字符,3.,：,S,S,（即,狀態(tài),s,S,，,a,，,（,S,，,a,）唯一的確定下一狀態(tài)）,4.s0,S,，唯一的初態(tài),5.FS,，是一個終態(tài)集（可空）,13,LL(1),文法滿足的基本條件,:,（,1,）文法不含左遞歸；,（,2,）對于文法中每一個非終結符號,A,的各個產(chǎn)生式
5、的候選首符集兩兩不相交。,14,屬性文法以及屬性的兩個類別,:,在上下文無關文法的基礎上為每個文法符號引入一組屬性并配備屬性的計算規(guī)則，這樣的文法就是屬性文法。屬性分綜合和繼承屬性。,15,高級語言執(zhí)行有解釋方式和編譯方式，本質區(qū)別是編譯方式會產(chǎn)生目標代碼。,自上而下語法分析方法的基本思想,是,對于任何輸入串，試圖用一切可能的辦法從文法的開始符號出發(fā)，自上而下的為輸入串建立一棵語法樹,一個上下文無關文法的定義包含,4,部分即,V,T,，代表終結符號集；,V,N,非終結符號集；,S,文法的開始符號；,P,一組產(chǎn)生式。,16,設計題,17,構造正規(guī)式,1(0|1),*,101,相應的,DFA,。,
6、解析：,（,1,）構造,NFA,：,18,（,2,）確定化：,19,令文法,GS,為：,S,T|S+T|S-T,T,F|T*F|T/F,F,(S)|k,給出,k*(k+k),的最左推導和最右推導。,解析：,（,1,）最左推導,S=T=T*F=F*F=k*F=k*(S)=k*(S+T)=k*(T+T)=k*(F+T)=k*(k+T)=k*(k+F)=k*(k+k),20,最右推導：,S=T=T*F=T*(S)=T*(S+T)=T*(S+F)=T*(S+k)=T*(T+k)=T*(F+k)=T*(k+k)=F*(k+k)=k*(k+k),21,試寫出表達式,a*(b+c),的逆波蘭式（要求寫出詳細分析過程）。,解析：,先考慮,b+c,的后綴式為,bc+,然后將,a,加入，最終的后綴式為,abc+*,22,一個簡單臺式計算器的屬性文法如下表所示，請按照該屬性文法，構造表達式（,3*7+2,）,*,5,的附注語法樹。,23,解析：,24,試寫出表達式,(A+B)*(C+D),的逆波蘭式（要求寫出詳細分析過程）。,解析：,(A+B)*(C+D),的逆波蘭式,先分析,A+B,的后綴式：,AB+,C+D,的后綴式為：,C D+,然后綜合：,AB+C D+*,
《編譯原理》期末考試復習重點劃分_20120314
