西安電子科技大學(xué)編譯原理復(fù)試第一章 引言

1編譯原理西安電子科技大學(xué)計(jì)算理論與技術(shù)研究所王小兵xbwang@2相關(guān)領(lǐng)域程序設(shè)計(jì)語(yǔ)言的應(yīng)用－程序設(shè)計(jì)（PLA）程序設(shè)計(jì)語(yǔ)言的翻譯－編譯器的構(gòu)造（PLT）程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)－語(yǔ)法、語(yǔ)義（PLD）知識(shí)點(diǎn)

中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程(CCC2002)程序設(shè)計(jì)基礎(chǔ)(PF)：程序設(shè)計(jì)基本結(jié)構(gòu)、算法與問(wèn)題求解、基本數(shù)據(jù)結(jié)構(gòu)、遞歸、事件驅(qū)動(dòng)程序設(shè)計(jì)。(PLA)程序設(shè)計(jì)語(yǔ)言(PL)：程序設(shè)計(jì)語(yǔ)言概論、虛擬機(jī)、語(yǔ)言翻譯簡(jiǎn)介、聲明和類(lèi)型、抽象機(jī)制、面向?qū)ο蟪绦蛟O(shè)計(jì)(核心)；函數(shù)程序設(shè)計(jì)、語(yǔ)言翻譯系統(tǒng)、類(lèi)型系統(tǒng)、程序設(shè)計(jì)語(yǔ)言的語(yǔ)義、程序設(shè)計(jì)語(yǔ)言的設(shè)計(jì)(選修)。(PLA、PLT、PLD)課程簡(jiǎn)介3課程簡(jiǎn)介目的了解PL的基本要素、工作原理、語(yǔ)言翻譯的基本方法；用不同的PL進(jìn)行程序設(shè)計(jì)，即自學(xué)計(jì)算機(jī)語(yǔ)言的能力；具備語(yǔ)言翻譯的基本技能；了解計(jì)算機(jī)科學(xué)的基礎(chǔ)理論；課程特點(diǎn)提高自學(xué)能力；理論與實(shí)踐并重；理論的演變是緩慢的、理論基礎(chǔ)是相通的；相同的原理可應(yīng)用于不同的技術(shù)；適應(yīng)飛速變化的技術(shù)的根本是注重基礎(chǔ)理論學(xué)習(xí)；4課程簡(jiǎn)介教材劉堅(jiān)編譯原理基礎(chǔ)西電出版社劉堅(jiān)《編譯原理基礎(chǔ)》習(xí)題與上機(jī)解答西電出版社參考書(shū)目呂映芝等編譯原理清華大學(xué)出版社陳火旺等程序設(shè)計(jì)語(yǔ)言編譯原理國(guó)防工業(yè)出版社Aho等編譯原理技術(shù)與工具人民郵電出版社AndrewW.Appel現(xiàn)代編譯程序?qū)崿F(xiàn)－Java語(yǔ)言高等教育出版社StevenS.Muchnick高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)機(jī)械工業(yè)出版社Hopcroft等自動(dòng)機(jī)理論、語(yǔ)言和計(jì)算機(jī)導(dǎo)論機(jī)械工業(yè)出版社5課程簡(jiǎn)介學(xué)習(xí)方法要作筆記；多思考，勤發(fā)問(wèn)；多實(shí)踐、以用促學(xué)；合理使用參考解答；作業(yè)與上機(jī)提前一星期通知交作業(yè)；驗(yàn)收上機(jī)題，并交上機(jī)報(bào)告；6往屆學(xué)生報(bào)告編譯原理是四大天書(shū)中的天書(shū)，事實(shí)上沒(méi)有那么恐怖。第二、三章只要多看書(shū)，勤做作業(yè)，學(xué)好也不難。第四、五章盡管沒(méi)有涉及算法，但是它與程序的運(yùn)行方面有很大關(guān)系，理解起來(lái)還是比較吃力的。課隨好學(xué)，但是上機(jī)就困難了，由于平時(shí)編程方面的欠缺，對(duì)于程序如何組織，如何編寫(xiě)，總感覺(jué)無(wú)從下手。7往屆學(xué)生報(bào)告函數(shù)繪圖語(yǔ)言采用的分析方法是遞歸子程序，優(yōu)點(diǎn)是分析方法非常簡(jiǎn)單易懂，但涉及到大量棧存儲(chǔ)空間操作，大大降低了分析的效率。實(shí)際中的編譯器和解釋器的構(gòu)造方法通常采用自動(dòng)化工具（Lex/Yacc），其語(yǔ)法分析大部分采用LALR(1)文法，其驅(qū)動(dòng)器具有通用性，與文法無(wú)關(guān)，效率高，但分析表十分復(fù)雜，難于手工構(gòu)造。8第一章引言1.1從面向機(jī)器的語(yǔ)言到面向人類(lèi)的語(yǔ)言面向機(jī)器的語(yǔ)言：機(jī)器指令、匯編語(yǔ)言面向人類(lèi)的語(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言、非過(guò)程式語(yǔ)言計(jì)算機(jī)語(yǔ)言舉例[例1]通用程序設(shè)計(jì)語(yǔ)言與匯編語(yǔ)言（包括機(jī)器指令）

Pascal語(yǔ)句：x:=a+b；

C++語(yǔ)句： x=a+b； 匯編指令： 十六進(jìn)制代碼

匯編指令

A10002 MOVAX,[A] 8B1E0202 MOVBX,[B] 01D8 ADDAX,BX A30402 MOV[X],AX91.1從面向機(jī)器的語(yǔ)言到面向人類(lèi)的語(yǔ)言[例2]SQL：查詢(xún)003號(hào)學(xué)生所選課程與成績(jī)SELECT學(xué)號(hào),姓名,課程名,成績(jī)FROM學(xué)生,選課WHERE學(xué)生.學(xué)號(hào)="003";學(xué)號(hào)姓名性別001張梧男002李煦男003王沁女004劉荔女學(xué)號(hào)課程代碼課程名成績(jī)0010104離散數(shù)學(xué)800010205數(shù)據(jù)結(jié)構(gòu)900030104離散數(shù)學(xué)850030205數(shù)據(jù)結(jié)構(gòu)95學(xué)號(hào)姓名課程名成績(jī)003王沁離散數(shù)學(xué)85003王沁數(shù)據(jù)結(jié)構(gòu)95對(duì)嗎？101.1從面向機(jī)器的語(yǔ)言到面向人類(lèi)的語(yǔ)言[例3]Lex和Yacc

Lex的正規(guī)式：char(char|digit)*returnid Yacc的產(chǎn)生式：E:E'+'E|E'*'E|id[例4]Unix的shell命令

SHELL=/bin/sh #includeenv_precomp.mk CPDIR=/u/pbsrc/chp ORAHOME=/oracle/app/oracle/product/734

111.1從面向機(jī)器的語(yǔ)言到面向人類(lèi)的語(yǔ)言按范型劃分的程序設(shè)計(jì)語(yǔ)言SimpleProceduralLanguages：FORTRANCBlock-StructuredProceduralLanguages：PascalObject-BasedLanguages：AdaC++SmalltalkFunctionalLanguages：LISPMLLogicProgrammingLanguages：PrologCC2002-PL過(guò)程式語(yǔ)言、面向?qū)ο笳Z(yǔ)言：通用程序設(shè)計(jì)語(yǔ)言，如FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等；函數(shù)語(yǔ)言：面向特點(diǎn)領(lǐng)域的、遞歸特性，如Lisp；說(shuō)明性、非算法式語(yǔ)言：濃厚的數(shù)學(xué)特征，如LEX/YACC、SQL等；腳本式語(yǔ)言：僅是一種安排，如shell語(yǔ)言，XML等。121.1從面向機(jī)器的語(yǔ)言到面向人類(lèi)的語(yǔ)言其他面向特定應(yīng)用領(lǐng)域的語(yǔ)言計(jì)算機(jī)輔助設(shè)計(jì)：MATLAB集成電路設(shè)計(jì)：VHDL、Verilog虛擬現(xiàn)實(shí)與人機(jī)交互：VRML……問(wèn)題：如何將形形色色的語(yǔ)言翻譯成可以在計(jì)算機(jī)上運(yùn)行的0、1串？131.2語(yǔ)言之間的翻譯習(xí)慣稱(chēng)法匯編語(yǔ)言－機(jī)器指令：匯編（或交叉匯編）程序設(shè)計(jì)語(yǔ)言－匯編語(yǔ)言或機(jī)器指令：編譯（或解釋?zhuān)└呒?jí)語(yǔ)言之間：轉(zhuǎn)換（或預(yù)編譯）逆向：反匯編、反編譯141.3編譯器與解釋器語(yǔ)言翻譯的兩種基本形態(tài) 先翻譯后執(zhí)行 邊翻譯邊執(zhí)行編譯器源程序目標(biāo)程序目標(biāo)程序輸入數(shù)據(jù)輸出解釋器源程序輸出輸入數(shù)據(jù)[例5]假設(shè)有源程序P：read(x);write("x=",x);

編譯器P目標(biāo)程序目標(biāo)程序3x=3解釋器x=3P3151.3編譯器與解釋器編譯器源程序目標(biāo)程序目標(biāo)程序輸入數(shù)據(jù)輸出解釋器源程序輸出輸入數(shù)據(jù)特點(diǎn)編譯器：工作效率高，即時(shí)間快、空間??；交互性與動(dòng)態(tài)特性差、可移植性差。被大多數(shù)PL的翻譯所采用；解釋器：工作效率低，即時(shí)間慢、空間費(fèi)；交互性與動(dòng)態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等?；竟δ埽憾呦嗤?；采用技術(shù)：從翻譯的角度來(lái)講，兩種方式所涉及的原理、方法、技術(shù)相似。161.4編譯器的工作原理與基本組成通用程序設(shè)計(jì)語(yǔ)言的主要成份從語(yǔ)言抽象的演變看： 過(guò)程→抽象數(shù)據(jù)類(lèi)型（ADT，程序包）→類(lèi)共同特點(diǎn)：兩大部分組成，聲明＋操作＝完整定義以過(guò)程式語(yǔ)言為例：聲明性語(yǔ)句：提供操作對(duì)象的性質(zhì)，如數(shù)據(jù)類(lèi)型、值、作用域等；操作性語(yǔ)句：確定操作的計(jì)算次序，完成實(shí)際操作。過(guò)程頭＋過(guò)程體＝過(guò)程定義

編譯器對(duì)兩類(lèi)語(yǔ)句的翻譯：聲明：生成相應(yīng)的環(huán)境，一般是配置存儲(chǔ)空間；操作：生成可執(zhí)行的代碼序列。171.4編譯器的工作原理與基本組成[例6]一Pascal的過(guò)程如下：(1)proceduresample(y:integer); {過(guò)程頭}(2)varx:integer; {過(guò)程體（開(kāi)始）}(3)beginx:=y;(4)ifx>100thenx:=0(5)end; {過(guò)程體（結(jié)束）}(1)：聲明，提供調(diào)用信息，如過(guò)程名、參數(shù)、返回值等。（接口）(2)至(5)：過(guò)程體，可含聲明或操作。（實(shí)現(xiàn)）。編譯器對(duì)聲明性語(yǔ)句的處理一般是生成相應(yīng)的環(huán)境（存儲(chǔ)空間），對(duì)操作性語(yǔ)句則是生成此環(huán)境中的可執(zhí)行代碼序列。為便于編譯器的處理，操作性語(yǔ)句中使用的每個(gè)操作對(duì)象，均應(yīng)在使用前聲明，即符合先聲明后引用的原則。181.4編譯器的工作原理與基本組成以階段劃分編譯器自然語(yǔ)言的翻譯過(guò)程： 識(shí)別單詞 識(shí)別句子結(jié)構(gòu) 理解意思 譯成中文并修飾編譯器的工作過(guò)程： 詞法分析 語(yǔ)法分析 語(yǔ)義分析 目標(biāo)代碼生成編譯器的階段（邏輯模塊）中間代碼的重要作用191.4編譯器的工作原理與基本組成編譯器各階段的工作[例7]Pascal源程序語(yǔ)句如下：

varx,y,z:real; x:=y+z*60;（源程序）varx,y,z:real;x:=y+z*60;

（記號(hào)流）varid1,id2,id3:real;id1:=id2+id3*60;（語(yǔ)法樹(shù)）詞法分析語(yǔ)法分析201.4編譯器的工作原理與基本組成語(yǔ)義分析中間代碼生成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中間代碼的形式與作用：(序號(hào))(op，arg1,arg2,result)result:=arg1oparg2211.4編譯器的工作原理與基本組成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中間代碼優(yōu)化(1)(*,id3,60.0,T1)(2)(+,id2,T1,id1)MOVF id3,R2MULF #60.0,R2MOVF id2,R1ADDFR2,R1MOVF R1,id1目標(biāo)代碼生成R2:=id3R2:=R2*60.0R1:=id2R1:=R1+R2id1:=R1id1:=id2+id3*60.0x:=y+z*60;221.4編譯器的工作原理與基本組成各階段工作的歸納

詞法分析：識(shí)別單詞，至少分以下幾大類(lèi)：關(guān)鍵字（保留字）、標(biāo)識(shí)符、字面量、特殊符號(hào)；語(yǔ)法分析：得到語(yǔ)言結(jié)構(gòu)并以樹(shù)的形式表示；語(yǔ)義分析：考察結(jié)構(gòu)正確的句子是否語(yǔ)義合法，修改樹(shù)結(jié)構(gòu)；中間代碼生成（可選）：生成一種既接近目標(biāo)語(yǔ)言，又與具體機(jī)器無(wú)關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致）231.4編譯器的工作原理與基本組成中間代碼優(yōu)化（可選）：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實(shí)際上是一個(gè)等價(jià)變換，變換前后的指令序列完成相同功能，但在占用的空間上和程序執(zhí)行的時(shí)間上都更省、更有效。目標(biāo)代碼生成：不同形式的目標(biāo)代碼－匯編、可重定位、內(nèi)存形式（Load-and-Go）;符號(hào)表管理：合理組織符號(hào)，便于各階段查找、填寫(xiě)等；出錯(cuò)處理：錯(cuò)誤的種類(lèi)－詞法錯(cuò)、語(yǔ)法錯(cuò)、靜態(tài)語(yǔ)義錯(cuò)、動(dòng)態(tài)語(yǔ)義錯(cuò)。241.4編譯器的工作原理與基本組成編譯器的分析/綜合模式

前端：語(yǔ)言結(jié)構(gòu)和意義的分析；后端：語(yǔ)言意義處理；中間代碼：前端與后端的分界；251.4編譯器的工作原理與基本組成編譯器基礎(chǔ)架構(gòu)(Infrastructure)：源代碼的中間表示、一組前端、一組后端；261.4編譯器的工作原理與基本組成編譯器掃描的遍數(shù)每個(gè)階段將程序完整分析一遍的工作模式稱(chēng)為一遍掃描。確定掃描遍數(shù)的因素有：軟、硬件條件，如內(nèi)存太小，或全局優(yōu)化語(yǔ)言結(jié)構(gòu)，如規(guī)定標(biāo)識(shí)符的先聲明后引用x:=f(a);…functionf(a:integer):integer;編譯技術(shù)，如拉