1、編譯原理,鄒陽(yáng) 計(jì)算機(jī)與信息學(xué)院,2020/6/20,2,個(gè)人聯(lián)系方式 電子郵件: auroras 辦公室: 電學(xué)樓4509,2020/6/20,3,第一章 概論,課程要求 什么是編譯程序 為什么學(xué)習(xí)編譯原理與技術(shù) 編譯過(guò)程概述 編譯程序的結(jié)構(gòu) 編譯程序的生成,2020/6/20,4,0. 課程要求,源語(yǔ)言 目標(biāo)語(yǔ)言 編譯技術(shù),2020/6/20,5,課程的性質(zhì)、地位和任務(wù),本課程是計(jì)算機(jī)專(zhuān)業(yè)的一門(mén)重要的專(zhuān)業(yè)基礎(chǔ)課，既是一門(mén)理論性、實(shí)驗(yàn)性、技術(shù)性很強(qiáng)的課程，又是理論與實(shí)踐緊密結(jié)合的課程。 本課程的主要任務(wù)是介紹程序設(shè)計(jì)語(yǔ)言編譯程序構(gòu)造的基本原理和設(shè)計(jì)方法。通過(guò)本課程的學(xué)習(xí)，使學(xué)生掌握和理解編譯

2、的基本過(guò)程，各個(gè)編譯階段的功能與常用的一些設(shè)計(jì)方法和技巧。,2020/6/20,6,課程定位計(jì)算機(jī)核心課程,操作系統(tǒng),2020/6/20,7,主要內(nèi)容,概述 形式語(yǔ)言與自動(dòng)機(jī) 詞法分析 語(yǔ)法分析 語(yǔ)法制導(dǎo)翻譯及中間代碼 符號(hào)表 代碼優(yōu)化 代碼生成 存儲(chǔ)管理 面向?qū)ο笳Z(yǔ)言的編譯,2020/6/20,8,教材,張素琴，呂映芝等，編譯原理（第二版），清華大學(xué)出版社。,2020/6/20,9,參考書(shū)目,陳火旺，程序設(shè)計(jì)語(yǔ)言編譯原理，國(guó)防工業(yè)出版社 錢(qián)煥延，編譯技術(shù)，第二版，東南大學(xué)出版社 K. C. Louden, 編譯原理及實(shí)踐，馮博琴譯，機(jī)械工業(yè)出版社,2020/6/20,10,成績(jī)?cè)u(píng)定,平時(shí)作業(yè)

3、與課堂表現(xiàn)：20% 期末考試：80% 課程實(shí)踐：1學(xué)分，單獨(dú)算一門(mén)課,2020/6/20,11,1.什么是編譯程序,機(jī)器語(yǔ)言machine language 匯編語(yǔ)言assembly language 高級(jí)語(yǔ)言high-level language 翻譯程序translator 匯編程序assembler 編譯程序compiler 解釋程序interpreter,2020/6/20,12,58 20 1020 (1000) 59 20 1024 (1004) 47 C0 1014 (1008) 50 20 1028 (100C) 47 F0 101C (1010) 58 20 1024 (10

4、14) 50 20 1028 (1018),LD R2, x CP R2, y BNG LESS ST R2, max JMP EXIT LESS: LD R2, y ST R2, max EXIT:,if (xy) max=x; else max=y;,2020/6/20,13,Simply stated, a compiler is a program that reads a program written in one language-the source language-and translates it into an equivalent program in another

5、 language-the target language.(from “Compilers: principles, techniques and tools”, by A.V. Aho, R. Sethi, and J.D. Ullman),2020/6/20,14,從功能上看，一個(gè)編譯程序就是一個(gè)語(yǔ)言翻譯程序,它把一種語(yǔ)言(稱(chēng)作源語(yǔ)言)書(shū)寫(xiě)的程序翻譯成另一種語(yǔ)言(稱(chēng)作目標(biāo)語(yǔ)言)的等價(jià)的程序.,2020/6/20,15,其他與編譯相關(guān)的程序,Linker Loader Preprocessor Editor Debugger Profiler Project manager,2020/6/

6、20,16,2. 為什么學(xué)習(xí)編譯原理與技術(shù),Computer Science 程序設(shè)計(jì)語(yǔ)言 軟件技術(shù) 思維方法,2020/6/20,17,2. 為什么學(xué)習(xí)編譯原理與技術(shù),Various Applications 人工智能-句法模式識(shí)別 機(jī)器人語(yǔ)言 軟件描述/發(fā)布-CORBA IDL XML, SGML, xxML 通信協(xié)議解釋,2020/6/20,18,3. 編譯過(guò)程概述,詞法分析lexical analysis 語(yǔ)法分析syntax analysis 語(yǔ)法樹(shù)syntax tree 語(yǔ)義分析semantic analysis 中間代碼生成intermediate code generation

7、 優(yōu)化 optimization 目標(biāo)代碼生成 target code generation,2020/6/20,19,2020/6/20,20,出 錯(cuò) 處 理,表 格 管 理,詞法分析,從左至右讀字符流的源程序、識(shí)別(拼)單詞 例： position := initial + rate * 60;,position := initial + rate * 60;,單詞類(lèi)型 單詞值 標(biāo)識(shí)符1(id1) position 算符(賦值) := 標(biāo)識(shí)符2(id2) initial 算符(加) + 標(biāo)識(shí)符3(id3) rate 算符(乘) * 整數(shù) 60 分號(hào) ；,又如一個(gè)C源程序片斷： int a;

8、 a = a + 2; 詞法分析后可能返回: 單詞類(lèi)型 單詞值 保留字 int 標(biāo)識(shí)符(變量名) a 界符 ; 標(biāo)識(shí)符(變量名) a 算符(賦值) = 標(biāo)識(shí)符(變量名) a 算符(加) + 整數(shù) 2 界符 ；,有關(guān)術(shù)語(yǔ),詞法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens,which are sequences of characters that have a colle

9、ctive meaning. 單詞-token 保留字-reserved word 標(biāo)識(shí)符 -identifier(user-defined name),功能:層次分析.依據(jù)源程序的語(yǔ)法規(guī)則把源程序的單詞序列組成語(yǔ)法短語(yǔ)(表示成語(yǔ)法樹(shù)). position := initial + rate * 60 ; 規(guī)則 :=“:=” :=“+” :=“*” :=“(”“)” := := :=,語(yǔ)法分析,賦值語(yǔ)句,標(biāo)識(shí)符,表達(dá)式,表達(dá)式,+,表達(dá)式,表達(dá)式,標(biāo)識(shí)符,整數(shù),標(biāo)識(shí)符,:=,表達(dá)式,*,id1:=id2+id3*N,術(shù)語(yǔ),語(yǔ)法分析(syntax analysis or parsing) The

10、 purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure. 語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(parse tree or der

11、ivation tree),語(yǔ)義分析,語(yǔ)義審查(靜態(tài)語(yǔ)義) 上下文相關(guān)性 類(lèi)型匹配 類(lèi)型轉(zhuǎn)換,例: Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */; ,又如: int arr 2,abc; abc = arr * 10; ,語(yǔ)義分析,術(shù)語(yǔ),語(yǔ)義分析(semantic analysis) The parsed program is further analyzed to determine whether it

12、conforms to the source languages contextual constraints:scope rules, type rules e.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration.,中間代碼生成,源程序的內(nèi)部(中間)表示 三元式、四元式 ( * id3 t1 t2 ) t2 = id3 * t1,id1:= id2 + id3 * 60 (1) (inttoreal, 60 - t1 ) (2)

13、 (* , id3 t1 t2 ) (3) (+ , id2 t2 t3 ) (4) (:= , t3 - id1 ),中間代碼生成(intermediate code generation),This is where the intermediate representation of the source program is created.We want this representation to be easy to generate,and easy to translate into the target program.The representation can have

14、 a variety of forms, but a common one is called three-address code or 4- tuple code.,代碼優(yōu)化,id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( := t3 - id1 ) 變換 （1） ( * id3 60.0 t1 ) ( 2）（ + id2 t1 id1 ),代碼優(yōu)化,t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1 t3 = b* c

15、 a = t2 t4 = t2 + t3 a = t4,代碼優(yōu)化(code optimization),Intermediate code optimization The optimizer accepts input in the intermediate representation and output a version still in the intermediate representation .In this phase,the compiler attempts to produce the smallest,fastest and most efficient runn

16、ing result by applying various techniques. Object code optimization,目標(biāo)代碼生成,(* , id3 60.0 t1 ) (+ , id2 t1 id1 ),movf id3,R2 mulf #60.0,R2 movf id2,R1 addf R2,R1 movf R1,id1,符號(hào)表管理,記錄源程序中使用的名字 收集每個(gè)名字的各種屬性信息 類(lèi)型、作用域、分配存儲(chǔ)信息,Const1 常量 值：35 Var1 變量 類(lèi)型：實(shí) 層次：2,符號(hào)表(symbol table),Symbol table is a data structu

17、re which is employed to associate identifiers with their attributes . An identifiers attribute consists of information relevant to contextual analysis,and is obtained from the identifiers declaration.,出錯(cuò)處理,檢查錯(cuò)誤、報(bào)告出錯(cuò)信息、排錯(cuò)、恢復(fù)編譯工作,2020/6/20,43,2020/6/20,44,出錯(cuò)處理(error handling)(error reporting and error

18、 recovery),The compiler should report the location of each error,together with some explanation. The major categories of compile-time error: syntax error, scope error, type error. After detecting and reporting an error,the compiler should attempt error recovery,means that the compiler should try to get itself into a state where analysis of the source program can continue as normally as possible.,2020/6/20,46,編譯程序中的主要數(shù)據(jù)結(jié)構(gòu),記號(hào)表token(單詞的內(nèi)部表示) 語(yǔ)法樹(shù)syntax tree 符號(hào)表symbol table 常數(shù)表literal table 中間代碼intermediate code 臨時(shí)文件