編譯原理第一章

編譯原理編譯原理這門課程主要介紹程序設(shè)計(jì)語(yǔ)言編譯程序構(gòu)造的一般原理、基本設(shè)計(jì)方法、主要實(shí)現(xiàn)技術(shù)和一些自動(dòng)構(gòu)造工具?；A(chǔ)知識(shí)：計(jì)算機(jī)工作原理一門高級(jí)語(yǔ)言（C，C++，Java等）匯編語(yǔ)言思考：為什么要學(xué)習(xí)編譯原理匯編語(yǔ)言簡(jiǎn)介匯編執(zhí)行指令是機(jī)器指令的符號(hào)化表示，其操作碼用記憶符表示，地址碼直接用標(biāo)號(hào)、變量名字、常數(shù)等表示。匯編執(zhí)行指令經(jīng)匯編程序翻譯為機(jī)器指令，二者之間基本上保持一一對(duì)應(yīng)的關(guān)系。匯編語(yǔ)言編寫程序雖不如高級(jí)程序設(shè)計(jì)語(yǔ)言簡(jiǎn)便、直觀，但是匯編出的目標(biāo)程序占用內(nèi)存較少、運(yùn)行效率較高，且能直接引用計(jì)算機(jī)的各種設(shè)備資源。它通常用于編寫系統(tǒng)的核心部分程序，或編寫需要耗費(fèi)大量運(yùn)行時(shí)間和實(shí)時(shí)性要求較高的程序段。第一章引論什么是編譯程序編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯過(guò)程概述編譯程序的結(jié)構(gòu)編譯階段的組合解釋程序和一些軟件工具程序設(shè)計(jì)語(yǔ)言泛型1.1什么是編譯程序編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分。1.1什么是編譯程序編譯程序是一個(gè)語(yǔ)言翻譯程序。翻譯程序把一種語(yǔ)言（源語(yǔ)言）書寫的程序翻譯成另一種語(yǔ)言（目標(biāo)語(yǔ)言）的等價(jià)程序。編譯程序把高級(jí)語(yǔ)言所寫的源程序翻譯成等價(jià)的機(jī)器語(yǔ)言或匯編語(yǔ)言的目標(biāo)程序。高級(jí)語(yǔ)言程序（源程序）機(jī)器（匯編）語(yǔ)言程序（目標(biāo)程序）編譯程序采用編譯方式在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言編寫的程序，需分階段進(jìn)行。第一種情況源程序編譯程序機(jī)器語(yǔ)言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段1.1什么是編譯程序第二種情況1.1什么是編譯程序源程序編譯程序機(jī)器語(yǔ)言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段匯編程序匯編語(yǔ)言目標(biāo)程序匯編階段把匯編語(yǔ)言書寫的程序翻譯成與之等價(jià)的機(jī)器語(yǔ)言程序的翻譯程序。語(yǔ)言處理過(guò)程

C程序#include<stdio.h>#include<stdlib.h>#defineMAX_LINES75Enumbooleans(FALSE,TRUE);Main(intargc,char*argv[]*)…

預(yù)處理器編譯器匯編器裝配連接編輯骨架程序

源程序

目標(biāo)匯編程序

可重定位機(jī)器代碼

絕對(duì)機(jī)器碼可重定位目標(biāo)文件庫(kù)語(yǔ)言處理過(guò)程第一章引論什么是編譯程序編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯過(guò)程概述編譯程序的結(jié)構(gòu)編譯階段的組合解釋程序和一些軟件工具程序設(shè)計(jì)語(yǔ)言泛型1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)將英文句子“Iwishyousuccess”翻譯成中文句子的大致過(guò)程是：分析一個(gè)個(gè)單詞分析語(yǔ)法結(jié)構(gòu)分析語(yǔ)義簡(jiǎn)單調(diào)整翻譯成文1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯程序的工作過(guò)程：詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成1.2編譯過(guò)程和編譯程序的結(jié)構(gòu)源程序：PROGRAMm;VARa,b,c:real;BEGINread(b,c);a:=b+c*60;write(a)END.

詞法分析階段的任務(wù)是對(duì)構(gòu)成源程序的字符串從左到右進(jìn)行掃描和分解，根據(jù)語(yǔ)言的詞法規(guī)則，識(shí)別出一個(gè)一個(gè)具有獨(dú)立意義的單詞(也稱單詞符號(hào),簡(jiǎn)稱符號(hào))。詞法分析

詞法規(guī)則是單詞符號(hào)的形成規(guī)則,它規(guī)定了哪樣的字符串構(gòu)成一個(gè)單詞符號(hào)。詞法規(guī)則<保留字，PROGRAM><標(biāo)識(shí)符，m><分隔符,;><保留字,VAR><標(biāo)識(shí)符,a><標(biāo)識(shí)符,b><標(biāo)識(shí)符,c><分隔符,:><標(biāo)識(shí)符,real><分隔符,;><保留字,BEGIN>…...<標(biāo)識(shí)符,a><算符,:=><標(biāo)識(shí)符,b><算符,+><標(biāo)識(shí)符,c><算符,*><常數(shù),60>……<保留字,END><分隔符,.>語(yǔ)法分析

語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上,根據(jù)語(yǔ)言的語(yǔ)法規(guī)則從單詞符號(hào)串中識(shí)別出各種語(yǔ)法單位(如表達(dá)式、說(shuō)明、語(yǔ)句等),并進(jìn)行語(yǔ)法檢查,即檢查各種語(yǔ)法單位在語(yǔ)法結(jié)構(gòu)上的正確性。語(yǔ)法規(guī)則

語(yǔ)言的語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成語(yǔ)法單位。表達(dá)式規(guī)則任何標(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á)式語(yǔ)法規(guī)則語(yǔ)句規(guī)則標(biāo)識(shí)符:=表達(dá)式是語(yǔ)句While(表達(dá)式)do語(yǔ)句是語(yǔ)句If(表達(dá)式)then語(yǔ)句else語(yǔ)句是語(yǔ)句賦值語(yǔ)句經(jīng)語(yǔ)法分析生成分析樹賦值語(yǔ)句變量:=表達(dá)式表達(dá)式+項(xiàng)項(xiàng)因子b項(xiàng)*因子因子

c60a語(yǔ)義分析

語(yǔ)義分析的任務(wù)是首先對(duì)每種語(yǔ)法單位進(jìn)行靜態(tài)的語(yǔ)義審查，然后分析其含義。例如：

類型檢查，審查每個(gè)運(yùn)算符是否具有語(yǔ)言規(guī)范允許的運(yùn)算對(duì)象賦值語(yǔ)句經(jīng)語(yǔ)義分析生成語(yǔ)法樹:=a+b*cinttoreal60特點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，含義明確的記號(hào)系統(tǒng)。設(shè)計(jì)原則：一容易生成，二被翻譯成目標(biāo)代碼。常見的是近似“三地址指令”的“四元式”中間代碼例如中間代碼生成temp1:=inttoreal(60);temp2:=c*temp1;temp3:=b+temp2;a:=temp3;(:=60—temp1)(*ctemp1temp2)(+btemp2temp3)(:=temp3—a)不同層次的中間代碼源語(yǔ)言（高級(jí)語(yǔ)言）中間代碼（高級(jí)）中間代碼（中級(jí)）中間代碼（低級(jí)）floata[10][20];a[i][j+2];t1=a[i,j+2]t1=j+2t2=i*20t3=t1+t2t4=4*t3t5=addrat6=t5+t4t7=*t6r1=[fp-4]r2=[r1+2]r3=[fp-8]r4=r3*20r5=r4+r2r6=4*r5r7=fp–216f1=[r7+r6]代碼優(yōu)化

代碼優(yōu)化的任務(wù)是對(duì)前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效即省時(shí)間和空間的目標(biāo)代碼。優(yōu)化主要包括局部?jī)?yōu)化和循環(huán)優(yōu)化等，例如上述四元式經(jīng)局部?jī)?yōu)化后得：temp1:=c*60.0a:=b+temp1(*c60temp1)(+btemp1a)目標(biāo)代碼生成

特點(diǎn)：將中間代碼變換成特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼。該工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。

movfc,r2;mulf#60.0,r2;movfb,r1;addfr2,r1;movfr1,a;編譯程序結(jié)構(gòu)(components)出錯(cuò)處理程序語(yǔ)法分析程序語(yǔ)義分析程序目標(biāo)代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理程序表格管理程序編譯程序在工作過(guò)程中需要建立一些表格，以登記源程序中所提供的或在編譯過(guò)程中所產(chǎn)生的一些信息，編譯各個(gè)階段的工作都涉及到構(gòu)造、查找、修改或存取有關(guān)表格中的信息，因此，在編譯程序中必須有一組管理各種表格的程序。出錯(cuò)處理程序編譯程序在各個(gè)階段應(yīng)診斷和報(bào)告源程序中的錯(cuò)誤，包括詞法錯(cuò)誤，語(yǔ)法錯(cuò)誤，語(yǔ)義錯(cuò)誤。編譯程序應(yīng)報(bào)告出錯(cuò)地點(diǎn)，并給出簡(jiǎn)明準(zhǔn)確的提示信息。編譯階段的組合分析(analysis)和綜合(synthesis)源程序的分析線性分析、層次分析、語(yǔ)義分析目標(biāo)程序的綜合編譯階段的劃分前端（frontend）和后端（backend）－—編譯的前端與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成—編譯的后端與目標(biāo)機(jī)有關(guān)的那些部分組成編譯階段的組合遍（趟）：對(duì)輸入文件（源程序或其等價(jià)的中間形式）從頭到尾掃視，完成預(yù)定的處理。

遍輸入文件輸出文件把前端組織成一遍掃描詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼生成源程序中間代碼符號(hào)表管理錯(cuò)誤的診查處理設(shè)計(jì)編譯程序應(yīng)首先研究的問(wèn)題首先研究源程序的語(yǔ)法和語(yǔ)義及運(yùn)行模型，源是設(shè)計(jì)編譯程序的出發(fā)點(diǎn)。研究目標(biāo)計(jì)算機(jī)，設(shè)計(jì)目標(biāo)代碼的指令系統(tǒng)，它是由目標(biāo)計(jì)算機(jī)擴(kuò)充而成，擴(kuò)充后的計(jì)算機(jī)稱作抽象計(jì)算機(jī)。目前的通用計(jì)算機(jī)往往和源語(yǔ)言執(zhí)行模型不一致。。編譯程序源程序目標(biāo)程序抽象目標(biāo)第一章引論什么是編譯程序編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯過(guò)程概述編譯程序的結(jié)構(gòu)編譯階段的組合解釋程序和一些軟件工具程序設(shè)計(jì)語(yǔ)言泛型

1.3解釋程序和一些軟件工具主要的途徑有兩個(gè)：通過(guò)編譯程序和解釋程序有些語(yǔ)言基本通過(guò)解釋程序Java的Bytecode有些環(huán)境同時(shí)提供編譯程序和解釋系統(tǒng)Lisp編譯程序低級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序解釋程序計(jì)算結(jié)果編譯程序和解釋程序編譯程序和解釋程序區(qū)別執(zhí)行過(guò)程：編譯方式把源程序的執(zhí)行過(guò)程嚴(yán)格地分成兩大步：編譯和運(yùn)行。即先把源程序全部翻譯成目標(biāo)代碼，然后再運(yùn)行此目標(biāo)代碼，獲執(zhí)行結(jié)果。解釋方式則不然。它是按照源程序中語(yǔ)句的動(dòng)態(tài)順序，直接地逐句進(jìn)行分析解釋，并立即執(zhí)行。代碼獨(dú)立性：在編譯方式下，機(jī)器上運(yùn)行的是與源程序等價(jià)的目標(biāo)程序，源程序和編譯程序都不再參與目標(biāo)程序的執(zhí)行過(guò)程，而在解釋方式下，解釋程序和源程序(或某種等價(jià)表示)要參與到程序的運(yùn)行過(guò)程中，運(yùn)行程序的控制權(quán)在解釋程序。編譯程序和解釋程序區(qū)別存儲(chǔ)方式編譯程序處理時(shí),在源語(yǔ)言程序被編譯階段,存儲(chǔ)區(qū)中要為源程序(中間形式)和目標(biāo)代碼開辟空間,要存放編譯用的各種各樣表格,比如符號(hào)表.在目標(biāo)代碼運(yùn)行階段,存儲(chǔ)區(qū)中主要是目標(biāo)代碼和數(shù)據(jù),編譯所用的任何信息都不再需要.解釋程序一般是把源程序一個(gè)語(yǔ)句一個(gè)語(yǔ)句的進(jìn)行語(yǔ)法分析,轉(zhuǎn)換為一種內(nèi)部表示形式,存放在源程序區(qū),因?yàn)榻忉尦绦蛟试S在執(zhí)行用戶程序時(shí)修改用戶程序,這就要求源程序,符號(hào)表等內(nèi)容始終存放在存儲(chǔ)區(qū)中,并且存放格式要設(shè)計(jì)的易于使用和修改.編譯階段和運(yùn)行階段存儲(chǔ)結(jié)構(gòu)編譯時(shí)運(yùn)行時(shí)名字表目標(biāo)代碼緩沖區(qū)編譯用源程序中間表示各種表格目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)源程序緩沖區(qū)解釋系統(tǒng)存儲(chǔ)結(jié)構(gòu)解釋系統(tǒng)源程序臨時(shí)工作單元名字表標(biāo)號(hào)表緩沖區(qū)(輸入輸出)棧區(qū)Java語(yǔ)言環(huán)境1.3處理源程序的軟件工具1.語(yǔ)言的結(jié)構(gòu)化編輯器2.語(yǔ)言程序的調(diào)試工具3.程序格式化工具

4.語(yǔ)言程序測(cè)試工具5.程序理解工具

6.高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具第一章引論什么是編譯程序編譯過(guò)程和編譯程序的結(jié)構(gòu)編譯過(guò)程概述編譯程序的結(jié)構(gòu)編譯階段的組合解釋程序和一些軟件工具程序設(shè)計(jì)語(yǔ)言泛型4程序設(shè)計(jì)語(yǔ)言范型不同的應(yīng)用側(cè)重:數(shù)值計(jì)算--Fortran系統(tǒng)程序設(shè)計(jì)---C事務(wù)處理--Cobol人工智能---LISP自然語(yǔ)言處理---Prolog大型嵌入式實(shí)時(shí)處理---Ada其它---支持的計(jì)算模式:強(qiáng)制(命令)式語(yǔ)言---C,Fortran,Pascal應(yīng)用(函數(shù))式語(yǔ)言---ML，Lisp基于規(guī)則(邏輯）的語(yǔ)言---Prolog,Yacc面向?qū)ο笳Z(yǔ)言---Ada,C++,Java

強(qiáng)制式語(yǔ)言(ImperativeLanguage)特點(diǎn)：過(guò)程式語(yǔ)言，語(yǔ)言面向動(dòng)作，即一個(gè)計(jì)算過(guò)程看做是一系列動(dòng)作。其特點(diǎn)是命令驅(qū)動(dòng)，以語(yǔ)句形式表示，每個(gè)語(yǔ)句的執(zhí)行引起若干存儲(chǔ)單元中的值的改變語(yǔ)法形式；

語(yǔ)句1；語(yǔ)句2；語(yǔ)句3；

特點(diǎn)：應(yīng)用式語(yǔ)言，更注重程序所表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)句地執(zhí)行。程序執(zhí)行過(guò)程是執(zhí)行一個(gè)個(gè)函數(shù)施用在數(shù)據(jù)上的變換最終得到的結(jié)果語(yǔ)法形式:

functionn(