編譯原理實踐—課程說明和引論

1、編譯原理實踐 - 課程說明和引論 序言序言編譯原理的課程實踐一般有兩種可能的安排。其一，為配合編譯課程教學(xué)，而安排多次小型實踐，分別支持編譯程序的各個階段。其二，針對某一規(guī)模適中的語言來設(shè)計和實現(xiàn)一個相對完整、獨立的編譯器。編譯原理實踐作為編譯原理課程的延伸，目的是讓大家動手設(shè)計和實現(xiàn)某一規(guī)模適中的語言的編譯器，該編譯器不僅涉及編譯程序的各個階段，而且也強調(diào)了編譯的總體設(shè)計、各個階段的接口安排等等學(xué)會運用所學(xué)技術(shù)解決實際問題1.課程目標(biāo)課程目標(biāo)回顧編譯相關(guān)的文法和形式語言基本理論以PL/0語言為例，介紹一個編譯程序從語法定義、詞法分析、語法分析、出錯處理、代碼生成到解釋執(zhí)行的全過程。使學(xué)生了解

2、什么是編譯，并懂得怎樣從語言的定義出發(fā)，系統(tǒng)地去開發(fā)一個語言的編譯程序介紹Lex（詞法分析程序的生成系統(tǒng)） & Yacc（語法分析程序的生成系統(tǒng)）PL/0PL/0編譯器給出一個簡單的類Pascal語言，其編譯程序用高級語言（C/Pascal）實現(xiàn)。通過剖析該高級語言程序以理解各編譯成分的功能及手工實現(xiàn)方法。PL/0編譯編譯程序程序源語言源語言(PL/0)目標(biāo)語言目標(biāo)語言(類類p-code)實現(xiàn)語言（實現(xiàn)語言（pascal/C) PL/0 類類 p-code pascal/C PL/0 語言程序語言程序 類類 p-code 代碼代碼PL/0PL/0編譯程序編譯程序類類 p pcodecode解釋

3、解釋程序程序類類 pcode代碼代碼PL/0源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)輸出數(shù)據(jù)輸出數(shù)據(jù)PL/0PL/0編譯系統(tǒng)的結(jié)構(gòu)框架編譯系統(tǒng)的結(jié)構(gòu)框架課程作業(yè)課程作業(yè)給出smallC語言的詞法和語法規(guī)則，要求實現(xiàn)smallC語言編譯程序，包括詞法分析、語法分析、出錯處理、代碼生成和解釋程序用smallC語言編若干個程序，用自己開發(fā)的編譯程序?qū)λ幾g，在編譯過程中要求能連續(xù)指出語法錯誤不中斷，能生成代碼程序，能解釋執(zhí)行代碼程序，最后輸出正確結(jié)果可以用自己熟悉的程序設(shè)計語言實現(xiàn)優(yōu)秀學(xué)生作品演示詳細(xì)要求和評分規(guī)則見編譯原理實踐作業(yè)要求 為了避免檢查沖突，將把大家分成若干組，每組完成對smallC的不同擴展。按

4、照指定時間檢查，無特殊原因不得更換時間。先檢查的同學(xué)將獲得更高的時間分，擴展點的難度也是由簡單到復(fù)雜。2.2.引論引論什么是編譯程序編譯程序的組成編譯程序的結(jié)構(gòu)2.1什么是編譯程序（編譯器）什么是編譯程序（編譯器）編譯器是將一種語言翻譯為另一種語言的計算機程序。編譯器將源程序(source language)編寫的程序作為輸入，而產(chǎn)生用目標(biāo)語言(target language)編寫的等價程序。通常地，源程序為高級語言( high-level language)，如C或C+，而目標(biāo)語言則是目標(biāo)機器的目標(biāo)代碼(object code)，有時也稱作機器代碼(machine code)，也就是寫在計算

5、機機器指令中的用于運行的代碼。編譯器是一種相當(dāng)復(fù)雜的程序，其代碼長度可從10000到1000000行不等。編寫甚至讀懂這樣的一個程序都非易事，大多數(shù)的計算機科學(xué)家和專業(yè)人員從來也沒有編寫過一個完整的編譯器。但是，幾乎所有形式的計算均要用到編譯器，而且任何一個與計算機打交道的專業(yè)人員都應(yīng)掌握編譯器的基本結(jié)構(gòu)和操作。操作系統(tǒng)編譯系統(tǒng)裸機編譯器歷史回顧本世紀(jì)40年代，開始時程序都是用機器語言（machine language）編寫的。機器語言就是表示機器實際操作的數(shù)字代碼，例如：C7 06 0000 0002表示在IBM PC上使用的Intel 8x86處理器將數(shù)字2移至地址0 0 0 0（1 6進

6、制）的指令。這種代碼形式很快就被匯編語言(assembly language)代替了。在匯編語言中，都是以符號形式給出指令和存儲地址的。例如，匯編語言指令MOV X, 2就與前面的機器指令等價(假設(shè)符號存儲地址X是0 0 0 0)。匯編程序(assembler)將匯編語言的符號代碼和存儲地址翻譯成與機器語言相對應(yīng)的數(shù)字代碼。發(fā)展編程技術(shù)的下一個重要步驟就是以一個更類似于數(shù)學(xué)定義或自然語言的簡潔形式來編寫程序的操作，它應(yīng)與任何機器都無關(guān)，而且也可由一個程序翻譯為可執(zhí)行的代碼。例如，前面的匯編語言代碼可以寫成一個簡潔的與機器無關(guān)的形式x = 2;在1954年至1957年期間，IBM的John Ba

7、ckus帶領(lǐng)的一個研究小組對FORTRAN語言及其編譯器的開發(fā)Noam Chomsky開始了他的自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編譯器結(jié)構(gòu)異常簡單，甚至還帶有了一些自動化。Chomsky的研究導(dǎo)致了根據(jù)語言文法(grammar)的難易程度以及識別它們所需的算法來為語言分類喬姆斯基分類結(jié)構(gòu)( Chomsky hierarchy)-文法的4個層次：0型、1型、2型和3型文法，且其中的每一個都是其前者的專門化。2型(或上下文無關(guān)文法(context-free grammar)被證明是程序設(shè)計語言中最有用的，而且今天它已代表著程序設(shè)計語言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。2.2 編譯程序的組成編譯程序的組成詞法分析

8、語法分析語義分析與中間代碼生成代碼優(yōu)化目標(biāo)代碼生成源程序單詞符號語法單位中間代碼中間代碼目標(biāo)代碼出錯處理符號表管理編譯程序結(jié)構(gòu)框圖編譯過程編譯過程1.詞法分析 輸入源程序，對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個具有獨立意義的最小語法單位“單詞 (token) ” 單詞：是語言的基本語法單位，一般語言有四大類單詞：關(guān)鍵字或保留字(如BEGIN、END、IF)標(biāo)識符常數(shù)分界符(運算符)，如+、-、*、/、；、(、) 舉例：1)a:=10+c*202)while x0 do x:=x-1詞法分析是一種線性分析2.語法分析 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法定義規(guī)則，識別出構(gòu)成單詞符號串的各

9、類語法單位。通過語法分析，確定整個輸入符號串是否構(gòu)成語法上正確的“程序” 舉例： a:=10+c*20 語法分析是一種層次分析3.語義分析與中間代碼產(chǎn)生 對識別出的各種語法成份進行語義分析，并產(chǎn)生相應(yīng)的中間代碼 中間代碼：一種介于源語言和目標(biāo)語言之間的中間語言形式 生成中間代碼的目的：便于做優(yōu)化處理便于編譯程序的移植 中間代碼的形式：編譯程序設(shè)計者可以自己設(shè)計，常見的中間代碼有：三元式、間接三元式、四元式、逆波蘭表示和樹形表示， P-Code、C-Code、U-Code、bytecode等 中間代碼具有易于產(chǎn)生，易于翻譯成目標(biāo)程序的特點，可以看成是一種抽象機的指令代碼舉例： a:=10+c*2

10、0 由語法分析識別出為賦值語句，語義分析首先要分析語義上的正確性，例如要檢查表達式中和賦值號兩邊的類型是否一致 根據(jù)賦值語句的語義，生成中間代碼。即用一種語言形式來代替另一種語言形式，這是翻譯的關(guān)鍵步驟。4.代碼優(yōu)化經(jīng)過語義分析后，編譯程序?qū)⒃闯绦蛏芍虚g代碼，這時的中間代碼往往有些重復(fù)和冗余。對代碼進行優(yōu)化的目的是提高目標(biāo)程序的執(zhí)行效率。代碼優(yōu)化首先在中間代碼上進行。在局部范圍可能做的優(yōu)化有常數(shù)表達式的計算或根據(jù)操作符的某些性質(zhì)如可結(jié)合性、可交換性和分配性以及檢測公共子表達式進行優(yōu)化 。5.目標(biāo)代碼生成 編譯的最后一步是將中間代碼生成特定機器上的低級語言代碼。這部分與機器類型有關(guān)，對程序中的

11、每個變量指定存貯單元，把中間代碼的指令翻譯成等價的某種類型機器的機器指令代碼或匯編指令代碼。 目標(biāo)代碼的形式可以是絕對指令代碼、可重定位的機器指令代碼或匯編指令代碼。如果目標(biāo)是絕對指令代碼，則可立即執(zhí)行。如果是匯編指令代碼，還需經(jīng)匯編程序翻譯后才能運行?，F(xiàn)在多數(shù)編譯程序產(chǎn)生的是可重定位的機器指令代碼，這種目標(biāo)代碼在運行前必須借助于一個連接裝配程序把各個目標(biāo)模塊（包括系統(tǒng)提供的庫模塊）連接在一起，確定程序中的變量在內(nèi)存中的位置，裝入內(nèi)存中指定起始地址，使之成為一個可以運行的絕對指令代碼程序。 注意！注意！上述編譯過程的5個階段是一種典型的分發(fā)，并非所有的編譯程序都分成5個階段本書中PL/0語言的

12、編譯程序省略了優(yōu)化階段；同時省去了最后的目標(biāo)代碼生成階段，取而代之的是增加一個解釋程序，由解釋程序來解釋執(zhí)行中間代碼程序，同樣可以得到最終結(jié)果編譯和解釋編譯和解釋解釋程序：在解釋程序的執(zhí)行過程中不產(chǎn)生目標(biāo)代碼。每讀一條源程序代碼，就將它解釋成等價的若干條機器代碼，并執(zhí)行之。一些規(guī)模較小的語言，如BASIC，常采用此方式。通常把編譯和解釋作某種程度的結(jié)合。如Java，先將源程序由java編譯器(javac)編譯生成字節(jié)碼文件，然后由java解釋器(java)執(zhí)行。 注：字節(jié)碼文件是與平臺無關(guān)的二進制碼，執(zhí)行時由解釋器解釋生成本地機器碼，邊解釋邊執(zhí)行。PL/0編譯程序也采用了編譯和解釋相結(jié)合的方式

13、 6.符號表管理 編譯過程中要記錄源程序中出現(xiàn)的標(biāo)識符，并收集每個標(biāo)識符的各種屬性信息。為此需要建立一個符號表記錄有關(guān)標(biāo)識符的各種信息。符號表是由若干記錄組成的數(shù)據(jù)結(jié)構(gòu)，每個標(biāo)識符在表中有一條記錄，每條記錄有多個域，每個域記載標(biāo)識符的一個屬性。7.出錯處理 編譯的各個階段都可能發(fā)現(xiàn)源程序中的錯誤。發(fā)現(xiàn)錯誤后如果立即停止編譯，往往會降低調(diào)試程序的效率，所以應(yīng)對出現(xiàn)的錯誤做適當(dāng)?shù)奶幚?，從而使編譯能繼續(xù)進行。詞法分析可以檢測出源程序中的非法符號，就好比自然語言語句中的出現(xiàn)的錯字、錯詞。語法分析能夠發(fā)現(xiàn)程序語句中的各種語法錯誤，如括號不匹配等等。語義分析能判斷運算對象的類型是否匹配、變量是否重復(fù)聲明或

14、沒聲明就使用等錯誤。任意時刻發(fā)現(xiàn)錯誤，都應(yīng)該報告錯誤信息，包括錯誤出現(xiàn)的位置、錯誤性質(zhì)等，為程序員調(diào)試程序提供方便。由此可見，錯誤檢測和恢復(fù)也是編譯程序中的一項重要工作。2.3 2.3 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu)在設(shè)計和實現(xiàn)編譯程序時，要考慮編譯程序分“遍”的問題。所謂一“遍”是指在編譯時把源程序或者中間形式從頭到尾掃描一遍，并作相關(guān)處理，生成新的中間形式或目標(biāo)代碼采用不同的分遍方式，編譯程序的結(jié)構(gòu)也有所不同單遍編譯程序單遍編譯程序單遍編譯程序只對源程序進行一遍掃描，就完成編譯的各項任務(wù)，產(chǎn)生目標(biāo)代碼。在單遍編譯程序中，往往以語法分析程序為中心，詞法分析和語義分析作為語法分析的子程序。其工作

15、過程如下：當(dāng)語法分析需要讀進一個新單詞時，就調(diào)用詞法分析子程序。詞法分析子程序則從源程序中依次讀入字符，組合成單詞符號，并將單詞符號返回給語法分析程序。當(dāng)語法分析程序識別出一個語法成分時，就調(diào)用語義分析子程序進行語義分析，并生成目標(biāo)程序。當(dāng)源程序處理完后，進行善后處理，優(yōu)化目標(biāo)程序。 詞法分析詞法分析語法分析語法分析語義分析生成語義分析生成目標(biāo)程序目標(biāo)程序S.P.S.P.語法成分語法成分返回分析結(jié)果返回分析結(jié)果整理目標(biāo)程序整理目標(biāo)程序 停機停機O.P.O.P.取單詞取單詞返回單詞返回單詞單遍編譯程序單遍編譯程序多遍編譯程序多遍編譯程序有的編譯程序把編譯程序的五項任務(wù)分幾遍來進行，每遍只完成部分

16、任務(wù)，多遍編譯程序的工作過程如下： 調(diào)用詞法分析程序?qū)⒏呒壵Z言源程序轉(zhuǎn)換成用單詞符號表示的程序，即將字符串程序轉(zhuǎn)換成單詞符號串源程序。 調(diào)用語法分析程序?qū)Ψ柎闯绦蜻M行語法歸類檢查。 調(diào)用語義分析程序進行語義檢查，并生成中間的代碼程序。 調(diào)用代碼優(yōu)化程序?qū)χ虚g代碼程序進行優(yōu)化。 調(diào)用目標(biāo)生成程序?qū)?yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。源程序 詞法分析 語法分析 語義分析 代碼優(yōu)化目標(biāo)代碼生成錯誤處理符號表目標(biāo)程序 多遍編譯程序結(jié)構(gòu) 實際上，根據(jù)語言的不同，編譯器可以是一遍(one pass)所有的階段由一遍完成，其結(jié)果是編譯得很好，但(通常)代碼卻不太有效。大多數(shù)帶有優(yōu)化的編譯器都需要超過一遍：典型的安排是將一遍用于掃描和分析，將另一遍用于語義分析和源代碼層優(yōu)化，第3遍用于代碼生成和目標(biāo)層的優(yōu)化。更深層的優(yōu)化則可能需要更多的遍： 5遍、6遍、甚至8遍都是可能的。試問世界上第一個編譯程序是用什么語言書寫的？用高級語言書寫？*沒有編譯器，如何編譯？因此世界上第一個編譯器只能是用機器語言開發(fā)的編譯程序的自展技術(shù)編譯程序的自展技術(shù)直接用目標(biāo)機器上的機器語言書寫源語言的編譯程序工作量太大用目標(biāo)機器上的機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現(xiàn)源語言的編譯程序。