第1章 編譯程序概論

編譯原理主講:艾菊梅聯(lián)系電話公室:信工樓310教材：張素琴呂映芝等清華大學(xué)出版學(xué)時(shí)：理論36學(xué)時(shí),實(shí)驗(yàn)10學(xué)時(shí)成績(jī)比例:平時(shí)10%

實(shí)驗(yàn)20%

期末70%第1章引論1.1什么是編譯程序1.2編譯過程概述1.3編譯程序的結(jié)構(gòu)1.4編譯階段的組合1.5編譯技術(shù)和軟件工具編譯程序高級(jí)語言程序（源程序）低級(jí)語言程序（目標(biāo)程序）解釋程序源程序輸入數(shù)據(jù)計(jì)算結(jié)果編譯程序運(yùn)行系統(tǒng)目標(biāo)程序輸入數(shù)據(jù)計(jì)算結(jié)果源程序需預(yù)處理的源程序預(yù)處理程序源程序編譯程序匯編程序裝配/連接編輯程序目標(biāo)匯編程序可再裝配的機(jī)器代碼絕對(duì)機(jī)器代碼可再裝配目標(biāo)文件高級(jí)語言程序的處理過程表格管理詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成出錯(cuò)處理源程序目標(biāo)程序編譯的各個(gè)階段詞法分析從左到右讀入源程序的每個(gè)字符，對(duì)構(gòu)成源程序的字符流進(jìn)行掃描和分解，從而識(shí)別出一個(gè)個(gè)單詞（也叫單詞符號(hào)或符號(hào)）。單詞：邏輯上緊密相連的一組字符，這些字符具有集體含義。如：標(biāo)識(shí)符、保留字（關(guān)鍵字或基本字）、算符、界符等。例.某源程序片斷如下：beginvarsum,first,count:real;sum:=first+count*10end.保留字 begin保留字 var標(biāo)識(shí)符 sum逗號(hào) ,標(biāo)識(shí)符 first逗號(hào) ,標(biāo)識(shí)符 count冒號(hào) :保留字 real分號(hào) ;標(biāo)識(shí)符 sum賦值號(hào) :=標(biāo)識(shí)符 first加號(hào) +標(biāo)識(shí)符 count乘號(hào) *整數(shù) 10保留字 end界符 .語法分析將單詞序列分解成各類語法短語（也叫語法單位），如“程序”、“語句”、“表達(dá)式”等。依據(jù)：語言的語法規(guī)則。通過語法分析確定整個(gè)輸入串是否構(gòu)成一個(gè)語法上正確的程序。賦值語句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符:=表達(dá)式*id1:=id2+id3*10的語法樹id1sumid2

firstid3

count10id1:=id2+id3*10的語法樹的另一種形式:=id1+id2*id310程序結(jié)構(gòu)的遞歸表示表達(dá)式的表示：任何標(biāo)識(shí)符是表達(dá)式。任何常數(shù)（整常數(shù)、實(shí)常數(shù)）是表達(dá)式。若表達(dá)式1和表達(dá)式2都是表達(dá)式，那么表達(dá)式1+表達(dá)式2表達(dá)式1*表達(dá)式2（表達(dá)式1）都是表達(dá)式。語句的表示：

標(biāo)識(shí)符:=表達(dá)式是語句。

while(表達(dá)式)do語句和

if(表達(dá)式)then語句else語句

都是語句。語義分析如：類型檢查。:=id1+id2*id310inttorealsum:=first+count*10中間代碼生成中間代碼：一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng)。原則：容易生成；容易將它翻譯成目標(biāo)代碼。四元式：（運(yùn)算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果）如：源程序sum:=first+count*10生成的四元式可以是：(inttoreal 10 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1):=id1+id2*id310inttoreal代碼優(yōu)化(inttoreal 10 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1)(* id3 10.0 t2)(+ id2 t2 id1)(* id3 10.0 t1)(+ id2 t1 id1)目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。特點(diǎn)：與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)，涉及到硬件系統(tǒng)功能部件的運(yùn)用、機(jī)器指令的選擇、各種數(shù)據(jù)類型變量的存儲(chǔ)空間分配以及寄存器和后緩寄存器的調(diào)度等。(* id3 10.0 t1)(+ id2 t1 id1)sum:=first+count*10MOVF id3, R2MULF #10.0, R2MOVF id2, R1ADDF R1, R2MOV R1, id1表格管理程序詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標(biāo)代碼生成程序出錯(cuò)處理程序源程序目標(biāo)程序編譯程序的結(jié)構(gòu)有關(guān)名詞：前端（frontend）：主要依賴于源語言而與目標(biāo)機(jī)器無關(guān)的編譯階段。如：詞法分析、語法分析、語義分析、中間代碼生成、部分優(yōu)化工作、與前端有關(guān)的出錯(cuò)處理工作和符號(hào)表管理工作。后端（backend）：依賴于目標(biāo)機(jī)而一般不依賴于源語言，只與中間代碼有關(guān)的編譯階段。如：目標(biāo)代碼生成，以及相關(guān)出錯(cuò)處理和符號(hào)表操作。遍（趟）：對(duì)源程序或其等價(jià)的中間語言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。每一遍掃視可完成上述一個(gè)階段或多個(gè)階段的工作。解釋程序和一些工具軟件解釋程序源程序初始數(shù)據(jù)計(jì)算結(jié)果……b:=2;a:=b+2;writea編譯程序解釋程序Mov