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

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

2、什么是編譯，并懂得怎樣從語(yǔ)言的定義出發(fā)，系統(tǒng)地去開(kāi)發(fā)一個(gè)語(yǔ)言的編譯程序介紹Lex（詞法分析程序的生成系統(tǒng)） & Yacc（語(yǔ)法分析程序的生成系統(tǒng)）PL/0PL/0編譯器給出一個(gè)簡(jiǎn)單的類Pascal語(yǔ)言，其編譯程序用高級(jí)語(yǔ)言（C/Pascal）實(shí)現(xiàn)。通過(guò)剖析該高級(jí)語(yǔ)言程序以理解各編譯成分的功能及手工實(shí)現(xiàn)方法。PL/0編譯編譯程序程序源語(yǔ)言源語(yǔ)言(PL/0)目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言(類類p-code)實(shí)現(xiàn)語(yǔ)言（實(shí)現(xiàn)語(yǔ)言（pascal/C) PL/0 類類 p-code pascal/C PL/0 語(yǔ)言程序語(yǔ)言程序 類類 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語(yǔ)言的詞法和語(yǔ)法規(guī)則，要求實(shí)現(xiàn)smallC語(yǔ)言編譯程序，包括詞法分析、語(yǔ)法分析、出錯(cuò)處理、代碼生成和解釋程序用smallC語(yǔ)言編若干個(gè)程序，用自己開(kāi)發(fā)的編譯程序?qū)λ幾g，在編譯過(guò)程中要求能連續(xù)指出語(yǔ)法錯(cuò)誤不中斷，能生成代碼程序，能解釋執(zhí)行代碼程序，最后輸出正確結(jié)果可以用自己熟悉的程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)優(yōu)秀學(xué)生作品演示詳細(xì)要求和評(píng)分規(guī)則見(jiàn)編譯原理實(shí)踐作業(yè)要求 為了避免檢查沖突，將把大家分成若干組，每組完成對(duì)smallC的不同擴(kuò)展。按

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

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

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

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

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

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

10、0 由語(yǔ)法分析識(shí)別出為賦值語(yǔ)句，語(yǔ)義分析首先要分析語(yǔ)義上的正確性，例如要檢查表達(dá)式中和賦值號(hào)兩邊的類型是否一致 根據(jù)賦值語(yǔ)句的語(yǔ)義，生成中間代碼。即用一種語(yǔ)言形式來(lái)代替另一種語(yǔ)言形式，這是翻譯的關(guān)鍵步驟。4.代碼優(yōu)化經(jīng)過(guò)語(yǔ)義分析后，編譯程序?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í)語(yǔ)言代碼。這部分與機(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)提供的庫(kù)模塊）連接在一起，確定程序中的變量在內(nèi)存中的位置，裝入內(nèi)存中指定起始地址，使之成為一個(gè)可以運(yùn)行的絕對(duì)指令代碼程序。 注意！注意！上述編譯過(guò)程的5個(gè)階段是一種典型的分發(fā)，并非所有的編譯程序都分成5個(gè)階段本書(shū)中PL/0語(yǔ)言的

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

13、 6.符號(hào)表管理 編譯過(guò)程中要記錄源程序中出現(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ù)奶幚?，從而使編譯能繼續(xù)進(jìn)行。詞法分析可以檢測(cè)出源程序中的非法符號(hào)，就好比自然語(yǔ)言語(yǔ)句中的出現(xiàn)的錯(cuò)字、錯(cuò)詞。語(yǔ)法分析能夠發(fā)現(xiàn)程序語(yǔ)句中的各種語(yǔ)法錯(cuò)誤，如括號(hào)不匹配等等。語(yǔ)義分析能判斷運(yùn)算對(duì)象的類型是否匹配、變量是否重復(fù)聲明或

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

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

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