計算機編譯原理

1、計算機編譯原理 王海文 wanghaiwen 2005本書結構第一章 語言程序概述第二章 文法與語言第三章 詞法分析第四章 語法分析第五章 編譯程序的數據結構和符號表第六章 語法制導翻譯第七章 編譯程序課程要求基礎理論：熟悉基于形式語言理論的編譯程序構造原理和高級語言的實現原理?；A知識：全面掌握詞法分析、語法分析和語法制導翻譯方法等計算機處理技術，了解高級語言中各種語言成分的實現方法?；炯寄埽赫莆沼嬎銠C語言處理系統(tǒng)中各種通用的分析和翻譯技術，以及自動生成系統(tǒng)的運用。本課程的目的構造編譯器基本知識編譯的階段和相關的活動相關數據結構和算法計算機科學中相關的基礎理論形式語言與自動機進一步加深對軟

2、件開發(fā)的認識第一章 概述【課前思考】 什么是編譯程序？ 編譯過程和編譯程序的結構？【學習目標】介紹語言翻譯的基本概念程序和語言翻譯和解釋介紹翻譯的步驟和相關的活動介紹編譯器的開發(fā)方法知 識 結 構課前說明基于形式語言理論中的有關概念來討論編譯實現問題。即 編譯原理=形式語言理論+編譯技術本書主要內容涉及：高級程序設計語言形式語言理論的基本概念構造編譯程序的基本概念、原理和技術基本觀念程序、語言計算機、程序、語言計算機接受指令，然后執(zhí)行指令指令組成的序列，稱為程序符合一定規(guī)則（文法）的程序的集合，稱為語言語法（形式）語義（意義） /形式與意義之間的對應關系？討論：C語言與C語言程序之間的關系基本

3、觀念語言與程序語言的作用設計程序(選出特定的程序構造程序)程序的作用由計算機執(zhí)行在人之間的交流想法，由于程序沒有歧義如何定義語言本課程要學習的內容以有限的規(guī)則，定義無限多的程序 ?；居^念語言的多樣性語言的多樣性方便在特定領域的應用交流障礙解決方案統(tǒng)一語言，一個夢想沒有個性的語言語言的不斷發(fā)展翻譯基本觀念語言之間的翻譯對翻譯的要求保持程序的意義，即功能不變。翻譯的可能性Church猜想與通用計算機（語言的等價性）+、-、JNZ翻譯的策略軟件開發(fā)過程的策略編譯（整體翻譯）解釋（逐句的翻譯、執(zhí)行）程序的執(zhí)行方式高級語言程序通常采用兩種方式執(zhí)行：解釋方式和翻譯方式解釋方式：逐個語句地分析和執(zhí)行，如B

4、asic，Prolog優(yōu)點：易于查錯缺點：效率低，運行速度慢翻譯方式：對整個程序進行分析，翻譯成等價機器語言程序后執(zhí)行，如Pascal，Fortran，C優(yōu)點：只需分析和翻譯一次，缺點：在運行中發(fā)現的錯誤必須在源程序中查找什么是編譯程序？定義：是一種語言轉換系統(tǒng)編譯程序高級語言書寫的程序（源程序）低級語言程序（目標程序）C+編譯器C+CJavaBytecodeJava編譯器編譯程序運行系統(tǒng)目標程序輸入數據計算結果源程序需預處理的源程序預處理程序源程序編譯程序匯編程序裝配/連接編輯程序目標匯編程序可再裝配的機器代碼絕對機器代碼可再裝配目標文件高級語言程序的處理過程編譯程序的功能從功能上看，一個編

5、譯程序就是一個語言翻譯程序。源語言通常是一個高級語言，如FORTRAN，C 或Pascal。目標語言通常是一個低級語言,如匯編或機器語言。 編譯程序源語言程序目標語言程序出錯和警告信息 T形圖常用T形圖來表示編譯程序涉及的三個語言：S OI 其中：S:源語言(程序)，Source language(program)O:目標語言(程序), target/object language(program)I:實現語言, implementation language編譯程序在計算機系統(tǒng)中的作用編譯系統(tǒng)是一種軟件，一種系統(tǒng)軟件。軟件：計算機系統(tǒng)中的程序及其文檔。系統(tǒng)軟件：居于計算機系統(tǒng)中最靠近硬件的一

6、層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用。和具體的應用領域無關，如編譯系統(tǒng)和操作系統(tǒng)等。語言處理系統(tǒng)：把軟件語言書寫的各種程序處理成可在計算機上執(zhí)行的程序，如編譯系統(tǒng)。裸機操作系統(tǒng)語言處理系統(tǒng)應用軟件層編譯程序的組成結構semanticsparserscanneroptimizercode generatorprogram前端front end與源語言有關middle end后端back end與目標機相關翻譯外文資料編譯源程序分析閱讀原文識別單詞分析句子輸入并掃描源程序詞法分析語法分析綜合修辭加工寫出譯文代碼優(yōu)化目標代碼生成編譯程序的結構翻譯外文資料與編譯源程序進行類比翻譯之前的準備必須了解的

7、源語言（翻譯誰輸入）目標語言（翻譯成誰輸出）翻譯方法（如何實現翻譯）如何定義源語言和目標語言程序的基本組成是字符，程序是一個字符串由字符組成程序的方法先定義接口，然后再實現(1) 詞法分析(Lexical analysis)詞法分析程序又稱掃描程序。是編譯過程的第一個階段，其任務是：讀源程序的字符流、識別單詞（如標識符、整數、界限符等），并轉換成內部形式。輸入字符串（即源程序）輸出單詞符號（最基本的語法單位） 。詞法分析舉例一個C源程序片段：int a;a=a+2;詞法分析后返回(如右圖)： 單詞類型 單詞值保留字 int標識符 a界符 ;標識符 a算符(賦值) =標識符 a算符(加) +整數

8、 2界符 ；(2) 語法分析（Syntax analysis）語法分析語法定義如何由單詞符號組成更大的語法單位輸入單詞符號輸出語法單位及其之間的關系，通常是語法樹表達語法規(guī)則的主要工具為上下文無關文法id1:=id2+id3*10 的語法樹id1:=id2+id3*10的語法樹的另一種形式 (3) 語義分析(Semantic analysis)和中間代碼生成語義分析和中間代碼生成分析（檢查和計算）程序中各個語法單位的語義，翻譯為中間代碼形式。輸入語法單位及其之間的關系（語法樹）輸出中間代碼表達語義規(guī)則的主要工具是屬性文法表達中間代碼的主要工具是四元式主要使用語法制導的翻譯方法語義分析舉例錯在哪

9、里？例1： int arr2, c; c = arr1 * 10; 插入語義處理結點的語法樹 例子1C語言的源程序a = b*c + b*d 的四元式序列（賦值語句形式的四元式）： (1) t1 = b*c (2) t2 = b*d (3) t3 = t1 + t2 (4) a = t3例子2源程序： if (ab If t1 goto l t2=a-c a=t2 l: t3=b*c c=t3翻譯成(4) 代碼優(yōu)化優(yōu)化（在理論上不是必須的）輸入中間代碼輸出優(yōu)化后的中間代碼對中間代碼進行處理，期望得到高效的代碼刪除無用代碼減少冗余目前不要對優(yōu)化寄予過高的期望現在不能優(yōu)化算法將來也許能在一定范圍內

10、自動選擇算法或重構(5) 目標代碼生成目標代碼生成輸入中間代碼輸出目標代碼涉及的知識包括目標機器指令的選取、寄存器的分配、運行時存儲空間組織等可以根據目標機的模型，對目標代碼進一步進行優(yōu)化符號表管理記錄源程序中使用的名字(標識符)收集每個名字的各種屬性信息類型、作用域、分配存儲信息名字信息出錯處理檢查錯誤、報告出錯信息、排錯、恢復編譯工作詞法錯誤和語法錯誤可由編譯程序在編譯時刻查出。語義錯誤常采用下列方式查出：靜態(tài)模擬檢查：動態(tài)調試檢查：編譯程序的結構詞法分析程序語法分析程序語義分析程序中間代碼生成程序代碼優(yōu)化程序目標代碼生成程序符號表管理程序出錯管理程序編譯程序的結構框圖編譯的各個階段概念：

11、趟（遍）一個編譯程序的工作分成若干個階段來完成。每個階段讀入整個輸入并進行處理的過程稱為趟（或遍，pass）。一個編譯系統(tǒng)可以看成是一個變換系統(tǒng)進行一系列的變換，即 (SL,L1),(L1,L2),.(Lk,TL) 其中SL為源語言，TL為目標語言幾趟編譯程序：編譯原理課程的學習內容程序設計語言之間的翻譯方法翻譯的必要性和可能性定義語言的方法翻譯的活動、步驟及相關數據結構、算法和理論詞法分析（重點）語法分析（重點）語義分析和中間代碼生成（重點）優(yōu)化和目標代碼生成編譯技術的發(fā)展第一個編譯程序出現在20世紀50年代早期，多是將算術公式翻譯成機器代碼20世紀50年代末，提出并研制編譯程序的編譯程序，

12、20世紀60年代起，出現自展技術（用被編譯的語言來書寫該語言自身的編譯程序）。編譯實現方式的發(fā)展手工機器語言匯編語言系統(tǒng)程序設計語言自動構造工具lex yacc 編譯技術的應用語言的結構化編輯器語言程序的調試工具預處理程序高級語言之間的轉換工具研究領域并行編譯技術：交叉編譯技術：如嵌入式應用硬件描述語言及其編譯技術：如芯片設計交叉編譯交叉編譯程序產生不同于宿主機的機器代碼的編譯器可變目標編譯器前端與目標機無關的編譯器A(L)=A 求生成B(L)=B的方法構造C = L(L)=B對C = L(L)=B, 用A(L)=A，得到C = A(L)=B, 對C = L(L)=B, 用A(L)=B，得到C

13、 = B(L)=B本章小結高級程序設計語言通常有解釋和翻譯兩種執(zhí)行方式。從功能上說,編譯程序是一個翻譯程序,將高級語言的程序翻譯成低級語言的程序。一個編譯過程可劃分成詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標代碼生成六個階段。編譯技術會應用在很多領域。相關概念源語言目標語言源程序目標程序運行子程序趟 參考書（1）Tomas Pittmn, The art of Compiler Design theory and Practice, Prentice-Hall 1992Charles N. Fischer, Richard J. Leblanc, Crafting A Comp

14、iler, The Benjamin/Cummings Publishing Company 1988ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN, Compilers Principles, Techniques and Tools ADDISSON-WESLEY 1986 參考書（2）Terrence W.Pratt,Marvin V.Zelkowitz Programming Languages Design and Implementation, Prentice-Hall 1996Bennett, J.P.,Introduction to C

15、ompiling techniques: a first course using ANSI C,LEX and YACC.-2nd ed- , The McGRAW-HILL Publishing Company 1996David A. Watt, Programming Language Syntax and Semantics,Prentice Hall 1991Modern Compiler Design, 現代編譯程序設計，人民郵電出版社多級化和多元化的嵌入式系統(tǒng)的發(fā)展為我國自主版權的嵌入式軟件開發(fā)帶來機遇昂貴的國外開發(fā)軟件給我國造成了巨大經濟損失國外開發(fā)環(huán)境產品與國產OS的無縫連接水平有限,制約了我國新一代智能化數字產品的發(fā)展嵌入式軟件開發(fā)環(huán)境的市場增長迅速嵌入式系統(tǒng)的研究意義及其現狀國際市場上已經出現了以VRTX、VxWorks、pSOS和Windows CE為代表的近40個嵌入式操作系統(tǒng)家族，支持不同處理器的200多個產品.應用開發(fā)平臺雖然可支持多種處理器但不能支持我國自行研制的新型處理器，另外，這類產品中存在著各種問題，如將不需要的庫函數鏈接到了嵌入式應用程序中，優(yōu)化后的代碼調試時調試器往往出現各種錯誤.目前國外研究方向主要有以下幾個方面：提高嵌入式系統(tǒng)的實時性；