編譯原理實(shí)踐—課程說明和引論

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

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

3、de解釋解釋程序程序類類 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ī)則，要求實(shí)現(xiàn)smallC語言編譯程序，包括詞法分析、語法分析、出錯(cuò)處理、代碼生成和解釋程序用smallC語言編若干個(gè)程序，用自己開發(fā)的編譯程序?qū)λ幾g，在編譯過程中要求能連續(xù)指出語法錯(cuò)誤不中斷，能生成代碼程序，能解釋執(zhí)行代碼程序，最后輸出正確結(jié)果可以用自己熟悉的程序設(shè)計(jì)語言實(shí)現(xiàn)優(yōu)秀學(xué)生作品演示詳細(xì)要求和評(píng)分規(guī)則見編譯原理實(shí)踐作業(yè)要求 為了避免檢查沖突，將把大家分成若干組，每組完成對(duì)smallC的不同

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

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

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

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

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

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

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

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

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

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

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

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

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