編譯原理第1章：引論

編譯原理22023/11/30《編譯原理》課程簡介地位計(jì)算機(jī)專業(yè)的一門核心課程編譯程序是計(jì)算機(jī)的重要系統(tǒng)軟件，是高級(jí)程序設(shè)計(jì)語言的支撐基礎(chǔ)課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和方法32023/11/30本門課程的要求了解計(jì)算機(jī)高級(jí)語言源程序被計(jì)算機(jī)接受、掃描、詞法分析、語法分析、語義解釋執(zhí)行的原理與過程；掌握編譯的原理和基本算法、各種概念和語言描述。先導(dǎo)課程：程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、操作系統(tǒng)42023/11/30用途與作用這是本專業(yè)應(yīng)具備的基本知識(shí)，就像其他原理一樣，是基礎(chǔ)。三大系統(tǒng)軟件：

OS、DBMS、CompilingSystem開發(fā)大型系統(tǒng)軟件、工具軟件的需要。看資料、寫論文的需要52023/11/30《編譯原理》前導(dǎo)課程前導(dǎo)課程及涉及內(nèi)容組成原理——計(jì)算機(jī)組成及結(jié)構(gòu)微機(jī)原理——匯編語言與機(jī)器語言離散數(shù)學(xué)——推理知識(shí)及其完備性數(shù)據(jù)結(jié)構(gòu)——樹、表等的表示與實(shí)現(xiàn)操作系統(tǒng)——提供虛擬機(jī)和系統(tǒng)調(diào)用高級(jí)程序設(shè)計(jì)語言——語言定義和編程62023/11/30教學(xué)目的掌握編譯的基本理論、常用的編譯技術(shù)，了解編譯過程及編譯系統(tǒng)的構(gòu)造編譯程序一般由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、目標(biāo)代碼生成程序、代碼優(yōu)化程序、表格管理和出錯(cuò)處理程序等成分構(gòu)成。通過課程的學(xué)習(xí)應(yīng)掌握各個(gè)成分的功能和設(shè)計(jì)原則，以及在編譯階段的邏輯關(guān)系。理解他們?cè)鯓幼鳛橐粋€(gè)整體完成編譯任務(wù)。能運(yùn)用所學(xué)技術(shù)解決實(shí)際問題，能獨(dú)立編寫一個(gè)小型編譯系統(tǒng)72023/11/30意義:學(xué)習(xí)編譯程序構(gòu)造原理，技術(shù)更好地理解高級(jí)語言編譯的原理和方法有助于構(gòu)造一些實(shí)用的工具82023/11/30

課程特點(diǎn):理解性技術(shù)性考核：作業(yè)及上機(jī)實(shí)習(xí)：30%筆試：70%第一章引論1.1基本概念1.2編譯過程1.3編譯程序與程序設(shè)計(jì)環(huán)境1.4高級(jí)語言程序簡介102023/11/30一、發(fā)展機(jī)器語言→匯編語言→高級(jí)語言→工具語言第1代1GL2GL3GL4GL機(jī)器識(shí)別：0|1代碼 相去甚遠(yuǎn)1.1基本概念112023/11/30源語言程序目標(biāo)語言程序翻譯程序翻譯1.1基本概念二、翻譯程序把某一種語言程序(稱為源語言程序)等價(jià)地轉(zhuǎn)換成另一種語言程序(稱為目標(biāo)語言程序)的程序。如：中英互譯系統(tǒng)、DBMS語言(DDL,DCL)122023/11/30高級(jí)語言程序機(jī)器語言程序結(jié)果編譯程序翻譯運(yùn)行三、編譯程序(compiler)

把某一種高級(jí)語言程序等價(jià)地轉(zhuǎn)換成另一種低級(jí)語言程序(如匯編語言或機(jī)器語言程序)的程序。編譯程序分類診斷編譯程序&優(yōu)化編譯程序交叉編譯程序&可變目標(biāo)編譯程序1.1基本概念132023/11/30四、解釋程序把源語言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身。源程序結(jié)果解釋程序解釋執(zhí)行1.1基本概念142023/11/30編譯程序vs.解釋程序編譯解釋152023/11/30五、執(zhí)行高級(jí)語言程序的步驟把高級(jí)語言程序編譯成低級(jí)語言目標(biāo)程序執(zhí)行目標(biāo)程序1.1基本概念162023/11/30把英文翻譯為中文識(shí)別出句子中的一個(gè)個(gè)單詞；分析句子的語法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對(duì)譯文進(jìn)行修飾；寫出最后的譯文。1.2編譯過程172023/11/30一、程序的編譯過程（見PPT30頁）詞法分析語法分析中間代碼產(chǎn)生優(yōu)化目標(biāo)代碼生成1.2編譯過程作用、實(shí)現(xiàn)者(并非每個(gè)編譯過程均有以上全過程)182023/11/301.詞法分析任務(wù):輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)。依循的原則：構(gòu)詞規(guī)則描述工具：正規(guī)式和有限自動(dòng)機(jī)FORI:=1TO100DO

保留字標(biāo)識(shí)符等符整常數(shù)保留字整常數(shù)保留字192023/11/302.語法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則把單詞符號(hào)串分解成各類語法單位。依循的原則：語法規(guī)則描述工具：上下文無關(guān)文法Z:=X+0.618*Y

算術(shù)表達(dá)式，賦值語句（層次結(jié)構(gòu)分析）202023/11/303.中間代碼產(chǎn)生任務(wù):對(duì)各類不同語法范疇按語言的語義進(jìn)行初步翻譯。依循的原則：語義規(guī)則中間代碼:三元式，四元式，樹形結(jié)構(gòu)等Z:=X+0.618*Y翻譯成四元式為

(1)*0.618YT1 (2)+XT1T2 (3):=T2_Z212023/11/304.優(yōu)化任務(wù)：對(duì)于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價(jià)變換規(guī)則FORK:=1TO100DOBEGINX:=I+1;M:=I+10*K;N:=J+10*K;END222023/11/30中間代碼（一）序號(hào) OPR OPN1 OPN2RESULT注釋 (1) := 1 KK:=1 (2) j< 100 K (10)if(100<K)goto(10)(3) + I 1 X X:=I+1 (4) * 10 K T1 T1:=10*K(5) + I T1 M M:=I+T1 (6) * 10 K T2 T2:=10*K(7) + J T2 N N:=J+T2 (8) + K 1 K K:=K+1 (9) j (2) goto(2)(10) 232023/11/30轉(zhuǎn)換后的等價(jià)代碼（二）序號(hào) OPR OPN1 OPN2 RESULT 注釋 (1) + I 1 X X:=I+1 (2) := I M M:=I (3) := J N N:=J (4) := 1 K K:=1 (5) j< 100 K (10) if(100<K)goto(10)(6) + M 10 M M:=M+10 (7) + N 10 N N:=N+10 (8) + K 1 K K:=K+1 (9) j (5) goto(5) (10) 242023/11/305.目標(biāo)代碼產(chǎn)生任務(wù):把中間代碼變換成特定機(jī)器上的目標(biāo)代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼三種形式:絕對(duì)指令代碼:可直接運(yùn)行可重新定位指令代碼:連接裝配，匯編指令代碼:需要進(jìn)行匯編252023/11/30模塊A…a模塊B…b模塊C…c模塊A…a模塊B…b模塊C…c模塊A…a模塊D…模塊C…c262023/11/305.目標(biāo)代碼產(chǎn)生例:b=a+2 MOVa,R1 ADD#2,R1 MOVR1,b 000101

00

00000000

* 001101

10

00000010

010001

00

00000100

* L=00001111 000101

00

00001111 001101

10

00000010 010001

00

00010011

272023/11/30二、編譯程序的邏輯結(jié)構(gòu)1.2編譯過程282023/11/30三、表格與表格管理常見的表格:符號(hào)名表，常數(shù)表，標(biāo)號(hào)表，入口名表，過程引用表。格式:名字信息1.2編譯過程292023/11/30例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART: K:=M+1; M:=N+4; N:=K;END.302023/11/30312023/11/30322023/11/30四、出錯(cuò)處理出錯(cuò)處理程序：發(fā)現(xiàn)源程序中的錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶語法錯(cuò)誤語義錯(cuò)誤1.2編譯過程332023/11/30五、遍(Pass)所謂“遍”，對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。每遍由從外存上獲得前一遍的工作結(jié)果開始，完成工作后，把結(jié)果存在外存上。每遍工作完成后所占用的存貯空間大部分被釋放。例：IBMPascal：Pass1,Pass2Link？生成可重定位代碼。所以運(yùn)行時(shí)要連接成絕對(duì)指令代碼。1.2編譯過程342023/11/30編譯前端：與源語言有關(guān)，如詞法分析，語法分析，語義分析與中間代碼產(chǎn)生，與機(jī)器無關(guān)的優(yōu)化編譯后端：與目標(biāo)機(jī)有關(guān)，與目標(biāo)機(jī)有關(guān)的優(yōu)化，目標(biāo)代碼產(chǎn)生源語言中間語言目標(biāo)語言前端后端1.2編譯過程

六、編譯前端與后端352023/11/30程序設(shè)計(jì)環(huán)境編輯程序編譯程序連接程序調(diào)試工具集成化的程序設(shè)計(jì)環(huán)境1.3編譯程序與程序設(shè)計(jì)環(huán)境362023/11/30編譯程序的生成以匯編語言和機(jī)器語言為工具優(yōu)點(diǎn):可以針對(duì)具體的機(jī)器，充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能。生成的程序效率高。缺點(diǎn):程序難讀、難寫、易出錯(cuò)、難維護(hù)、生產(chǎn)的效率低。1.3編譯程序與程序設(shè)計(jì)環(huán)境372023/11/30高級(jí)語言書寫優(yōu)點(diǎn):程序易讀、易理解、容易維護(hù)、生產(chǎn)的效率高。缺點(diǎn):難以充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能，生成的程序效率低。1.3編譯程序與程序設(shè)計(jì)環(huán)境382023/11/30高級(jí)語言書寫利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語言的編譯程序。L1語言A代碼P1:A代碼L2語言A代碼P2:L1語言L2語言A代碼P2:A代碼1.3編譯程序與程序設(shè)計(jì)環(huán)境392023/11/30

移植方法把一種機(jī)器上的編譯程序移植到另一種機(jī)器上。L語言A代碼P1:A代碼L語言B代碼P2:L語言L語言B代碼P2:A代碼L語言B代碼P2:L語言L語言B代碼P2:B代碼1.3編譯程序與程序設(shè)計(jì)環(huán)境402023/11/30L1+L2+...+Ln…L1+L2自展技術(shù)L11.3編譯程序與程序設(shè)計(jì)環(huán)境412023/11/30編譯程序自動(dòng)產(chǎn)生編譯程序-編譯程序，編譯程序書寫系統(tǒng)LEX詞法分析程序產(chǎn)生器YACC語法分析程序產(chǎn)生器編譯程序自動(dòng)產(chǎn)生器L語言的語法描述語義描述目標(biāo)語言或機(jī)器描述L語言的編譯程序1.3編譯程序與程序設(shè)計(jì)環(huán)境422023/11/30一、參數(shù)傳遞模塊之間進(jìn)行參數(shù)傳遞有三種形式：1、傳地址(callbyreference)：把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)2、傳值(callbyvalue):

調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來并放在被調(diào)用段可以拿到的地方，把值帶入。3、傳名(callbyname)：過程調(diào)用的作用相當(dāng)于把被調(diào)用的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)在參數(shù)(文字替換)。1.4高級(jí)語言程序簡介432023/11/30二、存貯管理1、靜態(tài)存貯分配編譯時(shí)就安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)目的單元地址。2、動(dòng)態(tài)存貯分配如果允許遞歸、可變數(shù)據(jù)結(jié)構(gòu)，則必須動(dòng)態(tài)分配。①棧式：整個(gè)程序數(shù)據(jù)空間安排在一個(gè)棧中②堆式：允許自由地申請(qǐng)和退還空間1.4高級(jí)語言程序簡介442023/11/30

例：對(duì)于下述程序，試分析用傳名、傳值、傳地址方法傳遞參數(shù)時(shí)所得的打印結(jié)果。PROGRAMSS(input,output);VARA,B:integer;PROCEDUREP(x,y,z:integer);beginy:=y+1;z:=z+x;end;BEGINA:=2;b:=3;P(A+B,A,A);writeln(‘A=‘,A);END1.4高級(jí)語言程序簡介452023/11/30解:(1)傳名：相當(dāng)于執(zhí)行A:=2;B:=3;