編譯原理第一章

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

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

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

源程序

目標匯編程序

可重定位機器代碼

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

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

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

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

語言的語法規(guī)則規(guī)定了如何從單詞符號形成語法單位。表達式規(guī)則任何標識符都是表達式任何常數(shù)（整常數(shù)、實常數(shù)都是表達式）若表達式1和表達式2都是表達式，那么：表達式1+表達式2表達式1*表達式2（表達式1）都是表達式語法規(guī)則語句規(guī)則標識符:=表達式是語句While(表達式)do語句是語句If(表達式)then語句else語句是語句賦值語句經(jīng)語法分析生成分析樹賦值語句變量:=表達式表達式+項項因子b項*因子因子

c60a語義分析

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

類型檢查，審查每個運算符是否具有語言規(guī)范允許的運算對象賦值語句經(jīng)語義分析生成語法樹:=a+b*cinttoreal60特點：結(jié)構(gòu)簡單，含義明確的記號系統(tǒng)。設(shè)計原則：一容易生成，二被翻譯成目標代碼。常見的是近似“三地址指令”的“四元式”中間代碼例如中間代碼生成temp1:=inttoreal(60);temp2:=c*temp1;temp3:=b+temp2;a:=temp3;(:=60—temp1)(*ctemp1temp2)(+btemp2temp3)(:=temp3—a)不同層次的中間代碼源語言（高級語言）中間代碼（高級）中間代碼（中級）中間代碼（低級）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ù)是對前階段產(chǎn)生的中間代碼進行等價變換或改造，以期獲得更為高效即省時間和空間的目標代碼。優(yōu)化主要包括局部優(yōu)化和循環(huán)優(yōu)化等，例如上述四元式經(jīng)局部優(yōu)化后得：temp1:=c*60.0a:=b+temp1(*c60temp1)(+btemp1a)目標代碼生成

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

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

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

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

4.語言程序測試工具5.程序理解工具

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

強制式語言(ImperativeLanguage)特點：過程式語言，語言面向動作，即一個計算過程看做是一系列動作。其特點是命令驅(qū)動，以語句形式表示，每個語句的執(zhí)行引起若干存儲單元中的值的改變語法形式；

語句1；語句2；語句3；

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

functionn(