編譯原理-復(fù)習(xí)重難點(diǎn).doc

《編譯原理-復(fù)習(xí)重難點(diǎn).doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、from成都信息工程大學(xué)軟件工程學(xué)院第一章從本質(zhì)上來說，程序設(shè)計(jì)語言是按一定規(guī)則排列的符號集合，而編譯程序就是把這些符號集合變成機(jī)器指令的轉(zhuǎn)換器，編譯程序又稱為編譯器。程序設(shè)計(jì)語言【高級語言，低級語言（機(jī)器語言和匯編語言）】編譯過程：詞法分析，語法分析，中間代碼生成，優(yōu)化，目標(biāo)代碼產(chǎn)生。三元式定義為如下形式：（op,a1,a2)其中op為操作碼或運(yùn)算符，a1和a2為操作數(shù)或運(yùn)算分量。編譯:將高級語言程序翻譯成另一種語言的等價(jià)程序。解釋：翻譯一句執(zhí)行一句，邊翻譯邊執(zhí)行，直到程序結(jié)束。與編譯的區(qū)別：不生成等價(jià)的目標(biāo)代碼程序。優(yōu)點(diǎn)：解釋方式便于程序的調(diào)

2、試。（編譯方式只需翻譯一次，且目標(biāo)程序的執(zhí)行速度快）（1）詞法分析主要任務(wù)：從左到右掃描源程序，逐一讀入構(gòu)成源程序的字符流，識別出其中的一個(gè)個(gè)單詞，識別出的單詞稱單詞符號，也簡稱符號。單詞是高級語言程序中有實(shí)際意義的最小語法單位。（2）語法分析任務(wù)“組詞成句”，根據(jù)單詞分析出組成源程序的各類語法單位，并指出其中的語法錯誤。語法單位——由源程序的單詞構(gòu)成（如表達(dá)式、語句、……乃至整個(gè)程序。）語法單位的構(gòu)成規(guī)則——語法規(guī)則。一個(gè)語言的詞法規(guī)則和語法規(guī)則定義了一個(gè)程序的形式結(jié)構(gòu)。語法單位的表示——語法樹（3）語義分析和中間代碼生成任務(wù)：分析出語法單位具

3、體的動作意義，進(jìn)行初步翻譯，生成與源程序等價(jià)的中間代碼程序。from成都信息工程大學(xué)軟件工程學(xué)院語義:定義一個(gè)程序所表示的意義,用語義規(guī)則描述。中間代碼：指令應(yīng)結(jié)構(gòu)簡單、含義明確，易于實(shí)現(xiàn)源程序——中間代碼——目標(biāo)代碼三者之間的轉(zhuǎn)換。中間代碼常用形式：逆波蘭式、三元式、四元式等。四元式：（運(yùn)算符，對象1，對象2，結(jié)果）例：z=x+a%3*y(1)（%a3t1）（2）（*t1yt2）(3)（3）（+xt2t3）（4）（=t3_z）（1）代碼優(yōu)化任務(wù)：對中間代碼進(jìn)行等價(jià)的加工變換，以便生成更有效更節(jié)省時(shí)間和空間的目標(biāo)代碼。例：z=x+a%3*y的四元

4、式序列：(1)%a3t1）（2）（*t1yt2）(3)（+xt2z）（5）目標(biāo)代碼生成任務(wù)：將中間代碼程序變換成目標(biāo)代碼程序。2．按“遍”組合方式“遍”：對源程序或等價(jià)的中間語言程序從頭到尾掃描，完成規(guī)定的任務(wù)，并生成新的中間結(jié)果或目標(biāo)程序，稱一“遍”。編譯程序的構(gòu)造與三個(gè)方面有關(guān):源語言，目標(biāo)語言，編譯方法。第二章形式語言與自動機(jī)理論基礎(chǔ)主要內(nèi)容：語言和文法、有限自動機(jī)、正則表達(dá)式。語言：符號串的集合。元素——符號串——該語言的一個(gè)句子。字母表——符號串中符號的來源?！纠?-1】Σ={a，b，c，……，z}，x=“l(fā)augh”，則

5、x

6、=5Σ=

7、{I，you，he，am，is，are，a，student}，y=“Iamastudent”，空格不計(jì)算長度，則

8、y

9、=4。空符號串：無任何符號的串，簡稱空串，用ε表示，

10、ε

11、=0【例2-4】若U={a，b}，V={c，d}則UV={ac，ad，bc，bd}閉包：若指定字母表Σ，則Σ*表示Σ上的所有有窮長的串的集合。Σ*=Σ0∪Σ1∪Σ2∪……∪Σn∪……Σ*稱為集合Σ的閉包。Σ+=Σ1∪Σ2∪……∪Σn∪……Σ+稱為集合Σ的正閉包。成立的等式：Σ*=Σ0∪Σ+，Σ+=ΣΣ*=Σ*Σ若符號串x是Σ*的元素,則表示為x∈Σ*,否則x?Σ*。【例2-

12、5】Σ={0,1}Σ*={ε,0,1,00,10,11,000,001,100,………}文法的形式定義：1：終結(jié)符用VT表示、2：非終結(jié)符用VN表示、3：規(guī)則α→β、4：文法定義：一個(gè)文法是一個(gè)四元組G（VN，VT，S，P）VN：非終結(jié)符集（非空）；VT：終結(jié)符集（非VN∩VT＝?；from成都信息工程大學(xué)軟件工程學(xué)院S：識別符號或開始符號，S∈VN，且至少在一條規(guī)則中作為左部出現(xiàn)；P：規(guī)則（產(chǎn)生式）的集合。用V表示VN∪VT，稱G的字母表或詞匯表?！纠?-7】有一文法G（VN，VT，S，P）其中:VN={S}VT={0，1}開始符號是SP={S

13、→0S1，S→01}2.擴(kuò)展的BNF表示法（1）“{}”表示符號串t的多次重復(fù)，n為重復(fù)的最小次數(shù)，m為重復(fù)的最大次數(shù)，省略n、m表示t可以重復(fù)0到任意多次?！纠?-9】文法規(guī)則S→0S1

14、01簡化為S→0(S1

15、1)或S→(0S

16、0)1或S→0(S

17、ε)1（3）“[]”：[t]表示符號串t可選（即可有可無）?！纠?-11】C語言條件語句的語法圖：文法相關(guān)概念：定義1：如α→β是文法G（VN，VT，S，P）的一條規(guī)則，γ、δ∈V*，若有符號串v、w滿足v=γαδ，w=γβδ則稱v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w，或稱w是v的直接推導(dǎo)，反過來稱w直接歸

18、約到v，記作v?w?！纠?-13】對文法G：S→0S1S→01有直接推導(dǎo)序列：S?0S1?00S11?定義2：如果存在直接推導(dǎo)序列：v=