編譯原理 第十三章 編譯程序實現(xiàn)的途徑

1、第十三章 編譯程序實現(xiàn)的途徑課前索引【課前思考】在第2章我們已經(jīng)用T型圖表示PL/0語言編譯程序的功能，用T型圖表示一個編譯程序的實現(xiàn)功能，容易弄清源語言、目標語言和書寫語言3者之間的關系。本章將介紹基于LALR(1的語法分析程序的生成器YACC和基于有限自動機理論的詞法分析程序的生成器LEX。因此，建議學員學習本章前復習第3章和第7章的內(nèi)容。【學習目標】 掌握編譯程序的書寫語言與T型圖 學會用編譯程序的自展技術實現(xiàn)一個編譯程序 了解什么是編譯程序的移植 弄清什么是交叉編譯 初步學會使用編譯程序的構造工具即：基于LALR(1的語法分析程序的生成器YACC和基于有限自動機理論的詞法分析程序的生成

2、器LEX構造編譯程序的思想和步驟。 【學習指南】本章的學習內(nèi)容主要是對編譯程序構造的幾種不同途徑，到底采用那種途徑，要根據(jù)實現(xiàn)的具體環(huán)境決定，學員學習時要掌握如何更好地利用已經(jīng)有的軟件資源，能高質量的完成一個編譯程序的開發(fā)?！倦y 重 點】重點： 學會用T型圖描述實現(xiàn)編譯程序的自展技術 弄清交叉編譯與編譯程序移植的概念 理解編譯程序的構造工具YACC和LEX的實現(xiàn)原理 初步學會YACC和LEX的使用方法難點：用T型圖描述實現(xiàn)編譯程序的自展技術時，往往對多層T型圖的結構理解不清，其原因是沒有把一個單層T型圖看做是一個程序，而這個程序的功能把一種語言翻譯成另一種語言?！局?識 點】 由于一個編譯程序

3、的設計與實現(xiàn)，不僅要考慮源語言與目標語言，還要考慮實現(xiàn)該編譯程序的書寫語言，在60年代初，幾乎所有的編譯程序都是用機器語言或匯編語言書寫，而這種低級語言書寫的編譯程序多為手工構造，可以加工細致，目標程序的效率高，但開發(fā)時間長，可讀性差，不易調試，不易移植，可維護性和可擴充性更差，可靠性也不高，可以說是效率極低。70年代開始逐步有不少編譯程序是用高級語言編寫，進而又不斷推出編譯程序的構造工具，這些技術的發(fā)展對編譯程序的實現(xiàn)帶來極大的方便，不僅縮短了開發(fā)周期，提高了開發(fā)效率，而且大大增加了可靠性、可移植性、可維護性和可擴充性。本章將介紹編譯程序的自展技術、交叉編譯、移植和一些編譯程序開發(fā)工具的應用

4、。13.1 編譯程序的書寫語言與T型圖一個編譯程序涉及到三個方面的語言，即源語言、目標語言和編譯程序的書寫語言。為了描述方便通常用T型圖來表示這三個方面的語言。T型圖的左上角表示源語言，右上角表示目標語言，底部表示書寫語言(實現(xiàn)語言，如圖13.1。圖 13.1 編譯程序的T型圖如果一個編譯程序的源語言是X，目標語言是Y，書寫語言是Z，我們把該編譯程序記作，那么用T型圖表示如圖13.2。 圖 13.2 的T型圖設計一個編譯程序時必須考慮上述三個方面語言的性質，因為它們對編譯程序的結構和具體實現(xiàn)途徑都有很大影響，源語言的設計和定義往往影響到編譯程序的結構。目標語言和目標機的性質決定著源語言到目標語

5、言的映射和代碼生成的策略，而實現(xiàn)語言的性質和實現(xiàn)環(huán)境及開發(fā)工具的應用對編譯程序的可讀性，可移植性和可維護性及可擴充性等有很重要的關系。如果一個編譯程序是用高級語言或編譯程序的構造工具開發(fā)的，那么它的可讀性、可移植性和可維護性等將會大大提高。而用匯編語言實現(xiàn)，這些性能都會得到相反的結論。13.2 編譯程序的自展技術由于一個編譯程序的功能是把某種高級程序設計語言的源程序翻譯成目標機的機器語言(或匯編語言，目標機只能執(zhí)行它自己的機器語言，因此最早的第一個高級程序設計語言的編譯程序必須用目標機的匯編語言或機器語言書寫，而一個結構較復雜龐大的高級語言的編譯程序，若完全用匯編語言或機器語言書寫(如上所述會

6、有種種不便之處，但用自展技術則可以很好地解決這個問題。結合T型圖的原則是： 下面的T型圖的左右上角兩個語言分別與上面左右兩個T型圖的底部語言相同。 上面左右兩個T型圖的左右上角的語言必須分別相同。自展的思想是先用目標機的匯編語言或機器語言書寫源語言的一個子集的編譯程序，然后再用這個子集作為書寫語言，實現(xiàn)源語言的編譯程序，如果把這個過程根據(jù)情況分成若干步，像滾雪球一樣直到生成預計源語言的編譯程序為止，我們把這樣的實現(xiàn)方式稱為自展技術。例如，在目標機A上要實現(xiàn)L語言的編譯程序，我們可以把L劃分成核心部分為L1。第1步： 我們先用A機器的匯編語言或機器語言A書寫L1的編譯程序，表示為，其T型圖如圖1

7、3.3。圖 13.3 的T型圖這就相當于在A機器上已有了一個L1語言的編譯程序。L1已屬高級程序設計語言。第2步： 我們可以再用L1書寫L語言的編譯程序為，其T型圖如圖13.4所示。 圖 13.4 的T型圖第3步： 由于我們最終要求得到，目前我們已經(jīng)有了第1步和第2步所得到的兩個編譯程序，而對來說只不過是L1語言的源程序，所以只要把經(jīng)過編譯即可得到。我們可用圖13.5的雙層結合T型圖表示。 圖 13.5 的雙層結合T型圖如果我們把L不只分出一個核心L1，而是分出L1,L2，即L2為L1的擴充，那么實現(xiàn)的步驟可以是先由A書寫L1得，再由L1書寫L2表示為，將L1L2A經(jīng)過編譯得，最后用L2書寫L

8、為，再用對進行編譯最終得到我們所需要的。這個過程用三層結合的T型圖表示如圖13.6。 圖 13.6 的三層結合T型圖依此類推，L可以分成核心L1,L2,Ln都為L1的逐步擴充，使得L=Ln,其自展的示意圖如圖13.7所示。圖 13.7 編譯程序的自展示意圖思考問題 如何用T型圖 表示一個編譯程序的實現(xiàn)？ 如何用自展方式在PC機上實現(xiàn)C語言的編譯程序？（請用T型圖表示）13.3 交叉編譯與編譯程序的移植在13.2節(jié)中我們介紹了編譯程序的自展技術，但是一個高級語言往往需要在不同的目標機上實現(xiàn)，這就提出了如何把已在某機器上實現(xiàn)的一個高級語言的編譯程序能否移植到另一個目標機上。如在13.2節(jié)中我們用自

9、展技術已經(jīng)在A機器上實現(xiàn)了L語言的編譯程序，現(xiàn)在我們想在B機器上也實現(xiàn)L語言的編譯程序，當然毫無疑問用自展技術是可以實現(xiàn)的，問題是我們希望能利用A機器上已有的L語言的編譯程序，實現(xiàn)B機器上的編譯程序以縮短開發(fā)時間。通常把某個機器(稱為宿主機上已有的軟件移植到另一臺機器(稱為目標機上的過程稱為移植。在移植過程中也常會用到交叉編譯的技術。所謂交叉編譯是指把一個源語言在宿主機上經(jīng)過編譯產(chǎn)生目標機的匯編語言或機器語言。交叉編譯所產(chǎn)生目標機的匯編語言或機器語言在宿主機上是不能運行，只能在目標機上運行，因此，程序調試比較麻煩?，F(xiàn)在我們利用A機器上已有的L語言的編譯程序使其在B機器上也能實現(xiàn)。第1步： 我們

10、用L語言書寫L語言的編譯程序產(chǎn)生B機器上的匯編語言或機器語言為，其T型圖表示為圖13.8。 圖 13.8 的T型圖通常也把這種用某語言自己書寫自己的編譯程序稱做自編譯程序。第2步： 把經(jīng)過編譯得到，其T型圖如圖13.9。圖 13.9 的雙層結合T型圖這樣在A機器上得到一個用A機器語言書寫生成B機器目標語言的L語言編譯程序，我們把它稱為交叉編譯程序。第3步： 把在A機器上經(jīng)過編譯得到，其T型圖如圖13.10所示。 圖 13.10 的雙層結合T型圖經(jīng)過以上3步我們最終在B機器上實現(xiàn)了L語言的編譯程序。此外還可以用已有的高級語言書寫其它高級語言的編譯程序，例如在A機器上已有C語言，希望實現(xiàn)PASCA

11、L語言的編譯程序。用圖13.11(a,(b,(c表示實現(xiàn)的方法。圖 13.11 實現(xiàn)的T型圖組在圖13.11中，圖(a為已有的編譯程序，圖(b為需要得到的編譯程序，圖(c為需要書寫的編譯程序，只要我們把(c在(a上編譯就可得到(b，其結合T型圖如圖13.12所示。圖 13.12 實現(xiàn)的T型圖思考問題： 什么叫做軟件移植？ 什么叫做交叉編譯？13.4 編譯程序的構造工具70年代隨著諸多種類的高級程序設計語言的出現(xiàn)和軟件開發(fā)自動化技術的提高，編譯程序的構造工具陸續(xù)誕生，如70年代Bell實驗室推出的LEX、YACC至今甚為流行，在各種語言編譯程序的實現(xiàn)中得到廣泛應用。然而，這些早期的工具大都是用于

12、開發(fā)編譯程序的前端，即詞法分析程序和語法分析程序，而對于編譯程序的后端，即與目標機有關的代碼生成和代碼優(yōu)化部分由于對語義和目標機形式化描述方面所存在的困難，雖有不少生成工具被研制，但還沒有廣泛應用。本節(jié)只簡單介紹一種語法分析程序的自動生成工具即基于LALR(1文法的自底向上分析程序的生成工具YACC和詞法分析器的自動生成工具LEX。13.4.1 基于LALR(1的語法分析程序的生成器YACCYACC(Yet Another Compiler-Compiler是1975年由Johnson開發(fā)的一個用于語法分析器的生成器，它接受一個用BNF描述的上下文無關語言的語法規(guī)則，且語法滿足LALR(1文法

13、的要求。它將自動生成相應語法的LALR(1分析表，與它的驅動程序和分析棧結合構成一個LALR(1分析器稱yyparse。它與詞法分析程序的接口稱為yylex。其詞法分析程序不管是手工編寫還是自動生成工具構造，只要程序名為yylex即可與YACC配合工作，即由YACC生成的語法分析器需要單詞符號(終結符時調用yylex，其單詞的屬性值和自身值的存放，也有相應約定。其工作示意圖如圖13.13所示。圖 13.13 YACC工作示意圖在YACC的源程序中，除了BNF描述的語法規(guī)則外，還可以包括當這些語法規(guī)則被識別出來時需要完成的語義動作，其語義動作可以是一段C程序(或RATFOR程序。語義動作的內(nèi)容可

14、以是填寫和查找符號表、做語義檢查或生成語法樹和代碼生成等，若動作加在一條規(guī)則的末尾，則表明用此規(guī)則歸約時所做的動作。動作也可插入在某規(guī)則的文法符號之間，這時需注意偽變量的位置關系。因為LR類分析表只有當歸約時才能調語義處理動作，所以YACC對于在語法規(guī)則的文法符號之間插入的語義動作自動增加規(guī)則和非終結符，使其語義動作都在一條規(guī)則的末尾，即歸約時做。對此的詳細說明請參見附錄C。此外YACC還可以處理某些二義性文法的規(guī)則，我們在第7章中曾介紹過二義性文法在LR分析中的應用，YACC也給出了二義性文法終結符之間的優(yōu)先關系和結合性的書寫規(guī)定。對用戶書寫的二義性文法規(guī)則按其優(yōu)先級和結合性自動生成相應的分

15、析表，對于用優(yōu)先級和結合性能解決的沖突，YACC不報告錯誤。當所給的條件仍不能解決沖突時才報錯。在第7章中曾介紹過二義性文法在LR分析中的應用，當給出了二義性文法終結符之間的優(yōu)先關系和結合性的規(guī)定后，可能會解決LR項目集中的沖突，用二義性文法的LR分析和同樣語言非二義性文法的LR分析相比可提高對輸入串分析的速度，例如：表達式的二義性文法的LR分析速度比非二義性文法的LR分析速度要快的多。13.4.2 詞法分析程序的生成器LEX LEX是一個詞法分析器(掃描器的自動生成系統(tǒng)。它的輸入是描述3型語言的正規(guī)表達式，輸出是一個相應正規(guī)表達式的詞法分析程序。其示意圖如圖13.17。圖 13.17 LEX

16、功能示意圖正像YACC那樣，LEX也可以借助宿主語言C或RATFOR描述動作，LEX自動地把表示輸入串詞法結構的正規(guī)式及相應的動作轉換成一個宿主語言的程序，即詞法分析程序。它有一個固定的名字為yylex，yylex是一個C語言(或RATFOR語言程序。經(jīng)C語言編譯程序編譯后可運行，它的功能就是對輸入串識別出單詞符號，并可做相應的動作。例如，把輸入串的小寫字母轉換成相應的大寫字母，可有如下的LEX源程序。%a-z printf("%c"， yytext0+'A'-'a'；其中%是分界符，表示識別規(guī)則的開始，a-z是識別小寫字母的規(guī)則，print

17、f(是識別出小寫字母時采取的動作，即將小寫字母變換成相應的大寫字母。yytext0是工作單元，是用以存放yylex識別的字符或字符串自身的值。LEX的工作原理是將LEX源程序中的正規(guī)式轉換成相應的確定有限自動機,將其動作插入到y(tǒng)ylex中適當?shù)牡胤??？刂屏魇怯纱_定的有限自動機的解釋器完成，解釋器是LEX的構成部分，像YACC中的驅動程序一樣，它對不同的輸入源程序來說解釋器是相同的。對于LEX的詳細說明，請參閱附錄B?？紤]問題： 編譯程序的實現(xiàn)應考慮的問題有那些？ 編譯程序的實現(xiàn)途徑有那些？本章小結【本章小結】 要求學員掌握一個編譯程序的實現(xiàn)途徑，在所給環(huán)境下能夠提出自己的設計方案。 用編譯程序

18、的構造工具YACC和LEX編寫一個小型編譯程序，和第2章介紹的PL/0編譯程序的實現(xiàn)進行比較，體會用編譯程序的構造工具YACC和LEX編寫編譯程序的優(yōu)點。 目前YACC和LEX被廣泛應用，Ada，C，C+，Java等高級程序設計語言就是用Yacc開發(fā)的前端。Yacc 和 Lex 聯(lián)合應用的示意圖如下：編譯程序的自動生成工具f13-1-1.swf課后習題第13章習題第1題：如何用T型圖 表示一個編譯程序的實現(xiàn)？第2題：如何用自展方式在PC機上實現(xiàn)C語言的編譯程序？請用T型圖 表示。第3題：什么叫做軟件移植？第4題：什么叫做交叉編譯？第5題：編譯程序的實現(xiàn)應考慮的問題有那些？第6題：編譯程序的實現(xiàn)途徑有那些？問答第1題解答：用T型圖 表示編譯程序的實現(xiàn)問答第2題解答：用自展方式在PC機上實現(xiàn)C語言的編譯程序，首先把C