北航编译原理课件 12.编译程序生成方法和工具.ppt.ppt

1、北京航空航天大学计算机学院北京航空航天大学计算机学院1第十二章第十二章 编译程序生成方法和工具编译程序生成方法和工具 编译程序的书写语言编译程序的书写语言 自编译性自编译性 自展自展 编译程序的移植编译程序的移植 编译程序的自动生成编译程序的自动生成北京航空航天大学计算机学院北京航空航天大学计算机学院212.1 编译程序的书写语言编译程序的书写语言机器语言或汇编语言机器语言或汇编语言 主要优点：编出来的程序效率高。主要优点：编出来的程序效率高。 主要缺点：编程效率低，可读性差，不便于修改和移植。主要缺点：编程效率低，可读性差，不便于修改和移植。高级程序设计语言已基本取代汇编语言高级程序设计语言

2、已基本取代汇编语言 优点：编程效率高，可读性好，利于移植。优点：编程效率高，可读性好，利于移植。 缺点：编译程运行效率较低。缺点：编译程运行效率较低。北京航空航天大学计算机学院北京航空航天大学计算机学院312.2 自编译性自编译性自编译性：自编译性：如果一个高级语言能用来书写自己的编译程序，则如果一个高级语言能用来书写自己的编译程序，则该语言具有自编译性，并称该语言为自编译语言。该语言具有自编译性，并称该语言为自编译语言。两点说明：两点说明：1. 通常用自编译语言除可编写本语言的编译程序以外，也可用通常用自编译语言除可编写本语言的编译程序以外，也可用来编写别的语言的编译程序。来编写别的语言的编

3、译程序。 如果某台机器上已配备有某种自编译语言，则可利用这种如果某台机器上已配备有某种自编译语言，则可利用这种语言为本台机器配置其它的高级语言。语言为本台机器配置其它的高级语言。北京航空航天大学计算机学院北京航空航天大学计算机学院4例：例：A机上有自编译语言机上有自编译语言L1的编译程序的编译程序 L1 . AO L1语言语言L1的编译程序的编译程序 AO以以A机的机器指令形式给出机的机器指令形式给出 利用语言利用语言L1可为可为A机生成语言机生成语言L2的编译程序的编译程序 L2. L1 L1.AO L2.AOL1源程序源程序 A机机L2可执行的编译程序可执行的编译程序L2源程序源程序 L2

4、.AOL2目标程序目标程序A机机可在可在A机上运行机上运行北京航空航天大学计算机学院北京航空航天大学计算机学院5(b)解释程序(c)计算机(d)程序(a)编译程序源语言目标语言书写语言北京航空航天大学计算机学院北京航空航天大学计算机学院6L2L1 AoL1AoAoAoAoAoL2AoAoL2AoL2Aoff用用L1写写的的L2语言语言的编译器的编译器L2.L1用用Ao描述的描述的L1语语言的编译器言的编译器L1.Ao用用Ao描述的描述的L2语语言的编译器言的编译器L2.Ao运行运行Ao的的计算机计算机北京航空航天大学计算机学院北京航空航天大学计算机学院72.自编译性不是绝对的，只是强弱不同自编

5、译性不是绝对的，只是强弱不同 数据类型丰富的语言数据类型丰富的语言 控制结构丰富的语言控制结构丰富的语言自编译性强自编译性强数据类型：数据类型：除一般的外还有字符串类型，数组，结构，枚举，指除一般的外还有字符串类型，数组，结构，枚举，指 针等类型。针等类型。控制结构：控制结构：应适于进行多分支的程序设计，如有应适于进行多分支的程序设计，如有CASE语句等语句等 FORTRAN , ALGOL自编译性差自编译性差 PASCAL , C , ADA，C，JAVA自编译性强自编译性强实践示例：实践示例：用用PASCAL语言编写一个简单的编译程序，就是利用语言编写一个简单的编译程序，就是利用 PASC

6、AL的自编译性。的自编译性。北京航空航天大学计算机学院北京航空航天大学计算机学院812.3 自展自展 利用高级语言的自编译性，还可以通过自展方式生成语言的利用高级语言的自编译性，还可以通过自展方式生成语言的编译程序。编译程序。 设设L为自编译语言，自展生成为自编译语言，自展生成 L. Ao（A机目标形式的语言机目标形式的语言L的编译器，可在的编译器，可在A机上运行）机上运行）步骤：步骤：1.首先，将语言划分为首先，将语言划分为N个部分：个部分： L = L1+ L2+ Ln L1 核心部分核心部分 L2 Ln扩充部分扩充部分北京航空航天大学计算机学院北京航空航天大学计算机学院92.先用先用A机

7、上的汇编编写机上的汇编编写L1的编译程序，的编译程序，L1.Aa L1.AaAssemberL1.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.Ao北京航空航天大学计算机学院北京航空航天大学计算机学院10 (L1+L2).AoL.AoL1.Ao滚雪球式滚雪球式用自展方式进行编译，可提高生产率。因核心语言小，可用汇用自展方式进行编译，可提高生产率。因核心语言小，可用汇编实现。其余部分高级语言编写。比全

8、用低级语言效率高。编实现。其余部分高级语言编写。比全用低级语言效率高。.北京航空航天大学计算机学院北京航空航天大学计算机学院1112.4 编译程序的移植编译程序的移植移植：移植：将某台机上的成熟软件移植到另一台机器上，也就是将将某台机上的成熟软件移植到另一台机器上，也就是将宿主机上的软件移植到目标机上。如果使用具有自编译性的高宿主机上的软件移植到目标机上。如果使用具有自编译性的高级语言来书写程序，则移植是方便的。级语言来书写程序，则移植是方便的。宿主机宿主机AL. LL.Ao移植移植目标机目标机BL.Bo通过移植，在通过移植，在B机上可得到语言机上可得到语言L的编译程序，具的编译程序，具B机目

9、标形式，可机目标形式，可在在B机上运行。机上运行。北京航空航天大学计算机学院北京航空航天大学计算机学院12移植步骤：移植步骤：1. 将将L. L分为两部分：分为两部分： 一部分与机器无关一部分与机器无关 F.L 一部分与机器有关一部分与机器有关 A.L L. L = F.L+ A.L2. 根据目标机用语言根据目标机用语言L改写与具体机器有关的部分：改写与具体机器有关的部分： A.L B.L 交叉编译器：交叉编译器： I.L= F.L+ B.L 用用A机上的机上的L语言所写的能生成语言所写的能生成B机目标代码的语言机目标代码的语言L的编译程序。的编译程序。L产生产生A机代码机代码产生产生B机代码

10、机代码北京航空航天大学计算机学院北京航空航天大学计算机学院133. 第一次编译第一次编译 将将I.L在宿主机在宿主机A上用上用L的编译程序进行编译，生成能在宿主机的编译程序进行编译，生成能在宿主机A上上运行的语言运行的语言L的交叉编译器，它能生成目标机的交叉编译器，它能生成目标机B的代码。的代码。I.LL.AoI. Ao用用L所写的生所写的生成目标机成目标机B代码的代码的L语言语言交叉编译器源交叉编译器源程序程序宿主机宿主机A的的L编译编译程序程序语言语言L的交的交叉编译器，叉编译器，能在宿主机能在宿主机A上运行，生上运行，生成目标机成目标机B的的代码代码北京航空航天大学计算机学院北京航空航天

11、大学计算机学院144. 第二次编译（交叉编译）第二次编译（交叉编译）I.LI. AoL.BoA机机可在目标机可在目标机B上运行并生上运行并生成目标机成目标机B代代码的码的L编译编译程序程序交叉编译程序：交叉编译程序：在宿主机在宿主机A上运行，上运行，但所生成的目标只能在目标机但所生成的目标只能在目标机B（另一台机器）上运行。（另一台机器）上运行。北京航空航天大学计算机学院北京航空航天大学计算机学院15AoAoLBoAoBoLLLAoL语言描述语言描述的交叉编译的交叉编译器器I.LAo语言描述语言描述的交叉编译的交叉编译器器I.AoAoAoBoBoBoBoLLLL可在可在B机上运机上运行的行的L

12、语言编语言编译器译器L.BoL语言描述语言描述的交叉编译的交叉编译器器I.LAo语言描述语言描述的交叉编译的交叉编译器器I.Ao北京航空航天大学计算机学院北京航空航天大学计算机学院16 可以设想，只要在某台机器上为某目标机配置一个可以设想，只要在某台机器上为某目标机配置一个L语言的语言的交叉编译程序，就能将宿主机上的交叉编译程序，就能将宿主机上的L语言所写的所有软件移植到语言所写的所有软件移植到其他目标机上。其他目标机上。 采用软件移植的办法来开发软件，可提高软件生产率，并提采用软件移植的办法来开发软件，可提高软件生产率，并提高软件的可靠性。由于上述优点，所以软件的可移植性是软件开高软件的可靠

13、性。由于上述优点，所以软件的可移植性是软件开发所追求的目标之一。发所追求的目标之一。 目前有许多编译程序都考虑到可移植性的要求。目前有许多编译程序都考虑到可移植性的要求。 例如有：可移植的例如有：可移植的PASCAL编译程序。编译程序。 P.J.Brown , Software Portablility. 朱关铭等译，朱关铭等译，1982.12北京航空航天大学计算机学院北京航空航天大学计算机学院1712.5 编译程序的自动生成编译程序的自动生成理想的编译程序自动生成工具：理想的编译程序自动生成工具：L语言规格说明语言规格说明L语义描述和机器规格说明语义描述和机器规格说明编译程序编译程序生成工具

14、生成工具该语言（该语言（L）的编译程序的编译程序目标代码目标代码L源程序源程序北京航空航天大学计算机学院北京航空航天大学计算机学院18目前还没有一个系统能自动生成整个编译系统。目前还没有一个系统能自动生成整个编译系统。早期的工作集中在分析部分，即针对语法规则的形式化描述。早期的工作集中在分析部分，即针对语法规则的形式化描述。对编译程序后端，即与目标机有关的代码生成与代码优化部分，对编译程序后端，即与目标机有关的代码生成与代码优化部分，由于对语义和目标机进行形式化描述方面所存在的困难，最近由于对语义和目标机进行形式化描述方面所存在的困难，最近有所突破，但未见到流行的产品。（样机有所突破，但未见到

15、流行的产品。（样机未形成真正产品）未形成真正产品） 有词法分析器的自动生成器和语法分析器的自动生成器。有词法分析器的自动生成器和语法分析器的自动生成器。 词法分析器生成器词法分析器生成器（在第三章已作介绍）（在第三章已作介绍） LEX: LEX源文件（源文件（. l 文件）文件） (正则表达式表示的单词符号）正则表达式表示的单词符号）LEX（构造识别单词符（构造识别单词符号的自动机）号的自动机）词法分析器词法分析器（ lex.yy.c 文件）文件）（自动机）（自动机）北京航空航天大学计算机学院北京航空航天大学计算机学院19语法分析器生成器：语法分析器生成器： YACC ( YET ANOTHE

16、R COMPILER - COMPILER ) .y 文件文件（BNF表示的语表示的语法描述可插入语法描述可插入语义动作）义动作）YACC构造分析表和构造分析表和控制执行程序控制执行程序 语法分析器语法分析器（ y.tab. c文件文件）（LALR(1)分析器）分析器）Bison: 美国美国GNU开发的语法分析器生成器开发的语法分析器生成器)和和YACC一样都在一样都在 UNIX系统下运行。（已有系统下运行。（已有PC版版)北京航空航天大学计算机学院北京航空航天大学计算机学院20用用yacc建立翻译程序建立翻译程序yacc源程序：源程序：translate.y1. 键入命令：键入命令： yac

17、c translate.y2. 生成进行生成进行LALR分析的翻译分析的翻译程序：程序： y.tab.c 3. 对生成的分析器进行编译：对生成的分析器进行编译： cc y.tab.c -ly (ly为使用为使用LR分析器的库）分析器的库）生成可执行的生成可执行的 翻译程序翻译程序 a.out北京航空航天大学计算机学院北京航空航天大学计算机学院21函数定义部分函数定义部分声明部分声明部分%翻译规则部分翻译规则部分函数定义部分函数定义部分（拷贝）（拷贝）Yacc编译程序编译程序y.outputy.tab.hyacc源程序源程序( *. y )y.tab.c头文件头文件处理记录处理记录语法分析表语法

18、分析表yyparse() 语法分析函数语法分析函数北京航空航天大学计算机学院北京航空航天大学计算机学院221./* 表达式计算表达式计算 */2.% token NUM3.%4.line : expr n printf (n, $1);5. ;6.expr : expr + term $ = $1 + $3; 7. | expr - term $ = $1 - $3; 8. | term/* $ = $1 */9. ;10.term : term * factor $ = $1 * $3; 11. | term / factor $ = $1 / $3; 12. | factor /* $ = $1 */13. ;14.factor: ( espr ) $ = $2; 15. | NUM /* $ = $1 */16. ;%#includeyylex( ) int c; while ( c = getchar( ) = ); if ( isdigit ( c ) ) yylval = c 0; while ( isdigit( c = getchar ( ) ) ) yylval = yylval*10 + ( c-0 ); ungetc ( c, stdin ); retun NUM; else return c;