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

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

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

源程序

目標匯編程序

可重定位機器代碼

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

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

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

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

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

c60a語義分析

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

類型檢查，審查每個運算符是否具有語言規范允許的運算對象賦值語句經語義分析生成語法樹:=a+b*cinttoreal60特點：結構簡單，含義明確的記號系統。設計原則：一容易生成，二被翻譯成目標代碼。常見的是近似“三地址指令”的“四元式”中間代碼例如中間代碼生成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]代碼優化

代碼優化的任務是對前階段產生的中間代碼進行等價變換或改造，以期獲得更為高效即省時間和空間的目標代碼。優化主要包括局部優化和循環優化等，例如上述四元式經局部優化后得：temp1:=c*60.0a:=b+temp1(*c60temp1)(+btemp1a)目標代碼生成

特點：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。該工作與硬件系統結構和指令含義有關。

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

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

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

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

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

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

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

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

functionn(