北航編譯原理課件 12編譯程序生成方法和工具

第十二章編譯程序生成方法和工具編譯程序的書寫語言自編譯性自展編譯程序的移植編譯程序的自動生成第十二章編譯程序生成方法和工具編譯程序的書寫語言12.1編譯程序的書寫語言機器語言或匯編語言主要優(yōu)點：編出來的程序效率高。主要缺點：編程效率低，可讀性差，不便于修改和移植。高級程序設計語言已基本取代匯編語言優(yōu)點：編程效率高，可讀性好，利于移植。缺點：編譯程運行效率較低。12.1編譯程序的書寫語言機器語言或匯編語言12.2自編譯性自編譯性：如果一個高級語言能用來書寫自己的編譯程序，則該語言具有自編譯性，并稱該語言為自編譯語言。兩點說明：通常用自編譯語言除可編寫本語言的編譯程序以外，也可用來編寫別的語言的編譯程序?！嗳绻撑_機器上已配備有某種自編譯語言，則可利用這種語言為本臺機器配置其它的高級語言。12.2自編譯性自編譯性：如果一個高級語言能用來書寫自己的例：A機上有自編譯語言L1的編譯程序L1.AOL1——語言L1的編譯程序AO——以A機的機器指令形式給出利用語言L1可為A機生成語言L2的編譯程序L2.L1L1.AOL2.AOL1源程序A機L2可執(zhí)行的編譯程序L2源程序L2.AOL2目標程序A機可在A機上運行例：A機上有自編譯語言L1的編譯程序L2.L1L1.A(b)解釋程序(c)計算機(d)程序(a)編譯程序源語言目標語言書寫語言(b)解釋程序(c)計算機(d)程序(a)編譯程序源語言目標L2L1AoL1AoAoAoAoAoL2AoAoL2AoL2Aoff用L1寫的L2語言的編譯器L2.L1用Ao描述的L1語言的編譯器L1.Ao用Ao描述的L2語言的編譯器L2.Ao運行Ao的計算機L2L1AoL1AoAoAoAoAoL2AoAoL2AoL2.自編譯性不是絕對的，只是強弱不同數據類型豐富的語言控制結構豐富的語言自編譯性強數據類型：除一般的外還有字符串類型，數組，結構，枚舉，指針等類型。控制結構：應適于進行多分支的程序設計，如有CASE語句等FORTRAN,ALGOL——自編譯性差PASCAL,C,ADA，C＋＋，JAVA——自編譯性強實踐示例：用PASCAL語言編寫一個簡單的編譯程序，就是利用PASCAL的自編譯性。2.自編譯性不是絕對的，只是強弱不同自編譯性強數據類型：除一12.3自展

利用高級語言的自編譯性，還可以通過自展方式生成語言的編譯程序。設L為自編譯語言，自展生成L.Ao（A機目標形式的語言L的編譯器，可在A機上運行）步驟：1.首先，將語言劃分為N個部分：L=L1+L2+…+LnL1——核心部分L2～Ln——擴充部分12.3自展利用高級語言的自編譯性，還可以通2.先用A機上的匯編編寫L1的編譯程序，L1.AaL1.Aa→Assember→L1.Ao3.用L1編寫L1+L2的編譯程序

(L1+L2).L1L1.Ao(L1+L2).Ao4.用(L1+L2)編寫L1+L2+L3的編譯程序…5.L.(L1+L2…+Ln-1)(L1+L2…+Ln-1).AoL.Ao2.先用A機上的匯編編寫L1的編譯程序，L1.Aa3.用L1

(L1+L2).AoL.AoL1.Ao滾雪球式用自展方式進行編譯，可提高生產率。因核心語言小，可用匯編實現。其余部分高級語言編寫。比全用低級語言效率高?！?L.AoL1.Ao滾雪球式用自展方式進行編譯，可提高生產率12.4編譯程序的移植移植：將某臺機上的成熟軟件移植到另一臺機器上，也就是將宿主機上的軟件移植到目標機上。如果使用具有自編譯性的高級語言來書寫程序，則移植是方便的。宿主機AL.LL.Ao移植目標機BL.Bo通過移植，在B機上可得到語言L的編譯程序，具B機目標形式，可在B機上運行。12.4編譯程序的移植移植：將某臺機上的成熟軟件移植到另一移植步驟：將L.L分為兩部分：

一部分與機器無關F.L一部分與機器有關A.L∴L.L=F.L+A.L根據目標機用語言L改寫與具體機器有關的部分：A.LB.L

∴交叉編譯器：I.L=F.L+B.L用A機上的L語言所寫的能生成B機目標代碼的語言L的編譯程序。L產生A機代碼產生B機代碼移植步驟：將L.L分為兩部分：根據目標機用語言L改寫與具體3.第一次編譯

將I.L在宿主機A上用L的編譯程序進行編譯，生成能在宿主機A上運行的語言L的交叉編譯器，它能生成目標機B的代碼。I.LL.AoI.Ao用L所寫的生成目標機B代碼的L語言交叉編譯器源程序宿主機A的L編譯程序語言L的交叉編譯器，能在宿主機A上運行，生成目標機B的代碼3.第一次編譯I.LL.AoI.Ao用L所寫的生宿主機A4.第二次編譯（交叉編譯）I.LI.AoL.BoA機可在目標機B上運行并生成目標機B代碼的L編譯程序交叉編譯程序：在宿主機A上運行，但所生成的目標只能在目標機B（另一臺機器）上運行。4.第二次編譯（交叉編譯）I.LI.AoL.BoA機AoAoLBoAoBoLLLAoL語言描述的交叉編譯器I.LAo語言描述的交叉編譯器I.AoAoAoBoBoBoBoLLLL可在B機上運行的L語言編譯器L.BoL語言描述的交叉編譯器I.LAo語言描述的交叉編譯器I.AoAoAoLBoAoBoLLLAoL語言描述的交叉編譯器I.L

可以設想，只要在某臺機器上為某目標機配置一個L語言的交叉編譯程序，就能將宿主機上的L語言所寫的所有軟件移植到其他目標機上。采用軟件移植的辦法來開發(fā)軟件，可提高軟件生產率，并提高軟件的可靠性。由于上述優(yōu)點，所以軟件的可移植性是軟件開發(fā)所追求的目標之一。目前有許多編譯程序都考慮到可移植性的要求。例如有：可移植的PASCAL編譯程序。P.J.Brown,SoftwarePortablility.朱關銘等譯，1982.12可以設想，只要在某臺機器上為某目標機配置一12.5編譯程序的自動生成理想的編譯程序自動生成工具：L語言規(guī)格說明L語義描述和機器規(guī)格說明編譯程序生成工具該語言（L）的編譯程序目標代碼L源程序12.5編譯程序的自動生成理想的編譯程序自動生成工具：L語目前還沒有一個系統(tǒng)能自動生成整個編譯系統(tǒng)。早期的工作集中在分析部分，即針對語法規(guī)則的形式化描述。對編譯程序后端，即與目標機有關的代碼生成與代碼優(yōu)化部分，由于對語義和目標機進行形式化描述方面所存在的困難，最近有所突破，但未見到流行的產品。（樣機——未形成真正產品）有詞法分析器的自動生成器和語法分析器的自動生成器。

詞法分析器生成器（在第三章已作介紹）LEX:LEX源文件（.l文件）

(正則表達式表示的單詞符號）LEX（構造識別單詞符號的自動機）詞法分析器（lex.yy.c文件）（自動機）目前還沒有一個系統(tǒng)能自動生成整個編譯系統(tǒng)。LEX源文件（.語法分析器生成器：

YACC(YETANOTHERCOMPILER-COMPILER)

.y文件（BNF表示的語法描述可插入語義動作）YACC構造分析表和控制執(zhí)行程序語法分析器（y.tab.c文件）（LALR(1)分析器）Bison:美國GNU開發(fā)的語法分析器生成器)和YACC一樣都在UNIX系統(tǒng)下運行。（已有PC版)語法分析器生成器：.y文件YACC構造分析表和語法用yacc建立翻譯程序yacc源程序：translate.y1.鍵入命令：yacctranslate.y2.生成進行LALR分析的翻譯程序： y.tab.c

3.對生成的分析器進行編譯：

ccy.tab.c-ly(ly為使用LR分析器的庫）生成可執(zhí)行的翻譯程序a.out用yacc建立翻譯程序yacc源程序：translate.y函數定義部分聲明部分%%%%翻譯規(guī)則部分函數定義部分（拷貝）Yacc編譯程序y.outputy.tab.hyacc源程序(*.y)y.tab.c頭文件處理記錄語法分析表yyparse(){語法分析函數｝函數定義部分聲明部分%%%%翻譯規(guī)則部分函數定義部分Yacc/*表達式計算*/%tokenNUM%%line:expr‘\n’ {printf(‘\n’,$1);};expr:expr‘+’term {$$=$1+$3;}|expr‘-’term {$$=$1-$3;}|term /*$$=$1*/;term:term‘*’factor {$$=$1*$3;}|term‘/’factor {$$=$1/$3;}|factor /*$$=$1*/;factor:‘(’espr‘)’ {$$=$2;}|NUM /*$$=$1*/;%%#include <ctype.h>yylex(){int c;whil