编译原理 第十三章 编译程序实现的途径.doc

第13章编译程序的构造第十三章 编译程序实现的途径课前索引【课前思考】在第2章我们已经用T型图表示PL/0语言编译程序的功能，用T型图表示一个编译程序的实现功能，容易弄清源语言、目标语言和书写语言3者之间的关系。本章将介绍基于LALR(1)的语法分析程序的生成器YACC和基于有限自动机理论的词法分析程序的生成器LEX。因此，建议学员学习本章前复习第3章和第7章的内容。【学习目标】 掌握编译程序的书写语言与T型图 学会用编译程序的自展技术实现一个编译程序 了解什么是编译程序的移植 弄清什么是交叉编译 初步学会使用编译程序的构造工具即：基于LALR(1)的语法分析程序的生成器YACC和基于有限自动机理论的词法分析程序的生成器LEX构造编译程序的思想和步骤。 【学习指南】本章的学习内容主要是对编译程序构造的几种不同途径，到底采用那种途径，要根据实现的具体环境决定，学员学习时要掌握如何更好地利用已经有的软件资源，能高质量的完成一个编译程序的开发。【难 重 点】重点： 学会用T型图描述实现编译程序的自展技术 弄清交叉编译与编译程序移植的概念 理解编译程序的构造工具YACC和LEX的实现原理 初步学会YACC和LEX的使用方法难点：用T型图描述实现编译程序的自展技术时，往往对多层T型图的结构理解不清，其原因是没有把一个单层T型图看做是一个程序，而这个程序的功能把一种语言翻译成另一种语言。【知 识 点】 由于一个编译程序的设计与实现，不仅要考虑源语言与目标语言，还要考虑实现该编译程序的书写语言，在60年代初，几乎所有的编译程序都是用机器语言或汇编语言书写，而这种低级语言书写的编译程序多为手工构造，可以加工细致，目标程序的效率高，但开发时间长，可读性差，不易调试，不易移植，可维护性和可扩充性更差，可靠性也不高，可以说是效率极低。70年代开始逐步有不少编译程序是用高级语言编写，进而又不断推出编译程序的构造工具，这些技术的发展对编译程序的实现带来极大的方便，不仅缩短了开发周期，提高了开发效率，而且大大增加了可靠性、可移植性、可维护性和可扩充性。本章将介绍编译程序的自展技术、交叉编译、移植和一些编译程序开发工具的应用。13.1 编译程序的书写语言与T型图一个编译程序涉及到三个方面的语言，即源语言、目标语言和编译程序的书写语言。为了描述方便通常用T型图来表示这三个方面的语言。T型图的左上角表示源语言，右上角表示目标语言，底部表示书写语言(实现语言)，如图13.1。图 13.1 编译程序的T型图如果一个编译程序的源语言是X，目标语言是Y，书写语言是Z，我们把该编译程序记作，那么用T型图表示如图13.2。 图 13.2 的T型图设计一个编译程序时必须考虑上述三个方面语言的性质，因为它们对编译程序的结构和具体实现途径都有很大影响，源语言的设计和定义往往影响到编译程序的结构。目标语言和目标机的性质决定着源语言到目标语言的映射和代码生成的策略，而实现语言的性质和实现环境及开发工具的应用对编译程序的可读性，可移植性和可维护性及可扩充性等有很重要的关系。如果一个编译程序是用高级语言或编译程序的构造工具开发的，那么它的可读性、可移植性和可维护性等将会大大提高。而用汇编语言实现，这些性能都会得到相反的结论。13.2 编译程序的自展技术由于一个编译程序的功能是把某种高级程序设计语言的源程序翻译成目标机的机器语言(或汇编语言)，目标机只能执行它自己的机器语言，因此最早的第一个高级程序设计语言的编译程序必须用目标机的汇编语言或机器语言书写，而一个结构较复杂庞大的高级语言的编译程序，若完全用汇编语言或机器语言书写(如上所述)会有种种不便之处，但用自展技术则可以很好地解决这个问题。结合T型图的原则是： 下面的T型图的左右上角两个语言分别与上面左右两个T型图的底部语言相同。 上面左右两个T型图的左右上角的语言必须分别相同。自展的思想是先用目标机的汇编语言或机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序，如果把这个过程根据情况分成若干步，像滚雪球一样直到生成预计源语言的编译程序为止，我们把这样的实现方式称为自展技术。例如，在目标机A上要实现L语言的编译程序，我们可以把L划分成核心部分为L1。第1步： 我们先用A机器的汇编语言或机器语言A书写L1的编译程序，表示为，其T型图如图13.3。图 13.3 的T型图这就相当于在A机器上已有了一个L1语言的编译程序。L1已属高级程序设计语言。第2步： 我们可以再用L1书写L语言的编译程序为，其T型图如图13.4所示。 图 13.4 的T型图第3步： 由于我们最终要求得到，目前我们已经有了第1步和第2步所得到的两个编译程序，而对来说只不过是L1语言的源程序，所以只要把经过编译即可得到。我们可用图13.5的双层结合T型图表示。 图 13.5 的双层结合T型图如果我们把L不只分出一个核心L1，而是分出L1,L2，即L2为L1的扩充，那么实现的步骤可以是先由A书写L1得，再由L1书写L2表示为，将L1L2A经过编译得，最后用L2书写L为，再用对进行编译最终得到我们所需要的。这个过程用三层结合的T型图表示如图13.6。 图 13.6 的三层结合T型图依此类推，L可以分成核心L1,L2,Ln都为L1的逐步扩充，使得L=Ln,其自展的示意图如图13.7所示。图 13.7 编译程序的自展示意图思考问题 如何用T型图 表示一个编译程序的实现？ 如何用自展方式在PC机上实现C语言的编译程序？（请用T型图表示）13.3 交叉编译与编译程序的移植在13.2节中我们介绍了编译程序的自展技术，但是一个高级语言往往需要在不同的目标机上实现，这就提出了如何把已在某机器上实现的一个高级语言的编译程序能否移植到另一个目标机上。如在13.2节中我们用自展技术已经在A机器上实现了L语言的编译程序，现在我们想在B机器上也实现L语言的编译程序，当然毫无疑问用自展技术是可以实现的，问题是我们希望能利用A机器上已有的L语言的编译程序，实现B机器上的编译程序以缩短开发时间。通常把某个机器(称为宿主机)上已有的软件移植到另一台机器(称为目标机)上的过程称为移植。在移植过程中也常会用到交叉编译的技术。所谓交叉编译是指把一个源语言在宿主机上经过编译产生目标机的汇编语言或机器语言。交叉编译所产生目标机的汇编语言或机器语言在宿主机上是不能运行，只能在目标机上运行，因此，程序调试比较麻烦。现在我们利用A机器上已有的L语言的编译程序使其在B机器上也能实现。第1步： 我们用L语言书写L语言的编译程序产生B机器上的汇编语言或机器语言为，其T型图表示为图13.8。 图 13.8 的T型图通常也把这种用某语言自己书写自己的编译程序称做自编译程序。第2步： 把经过编译得到，其T型图如图13.9。图 13.9 的双层结合T型图这样在A机器上得到一个用A机器语言书写生成B机器目标语言的L语言编译程序，我们把它称为交叉编译程序。第3步： 把在A机器上经过编译得到，其T型图如图13.10所示。 图 13.10 的双层结合T型图经过以上3步我们最终在B机器上实现了L语言的编译程序。此外还可以用已有的高级语言书写其它高级语言的编译程序，例如在A机器上已有C语言，希望实现PASCAL语言的编译程序。用图13.11(a),(b),(c)表示实现的方法。图 13.11 实现的T型图组在图13.11中，图(a)为已有的编译程序，图(b)为需要得到的编译程序，图(c)为需要书写的编译程序，只要我们把(c)在(a)上编译就可得到(b)，其结合T型图如图13.12所示。图 13.12 实现的T型图思考问题： 什么叫做软件移植？ 什么叫做交叉编译？13.4 编译程序的构造工具70年代随着诸多种类的高级程序设计语言的出现和软件开发自动化技术的提高，编译程序的构造工具陆续诞生，如70年代Bell实验室推出的LEX、YACC至今甚为流行，在各种语言编译程序的实现中得到广泛应用。然而，这些早期的工具大都是用于开发编译程序的前端，即词法分析程序和语法分析程序，而对于编译程序的后端，即与目标机有关的代码生成和代码优化部分由于对语义和目标机形式化描述方面所存在的困难，虽有不少生成工具被研制，但还没有广泛应用。本节只简单介绍一种语法分析程序的自动生成工具即基于LALR(1)文法的自底向上分析程序的生成工具YACC和词法分析器的自动生成工具LEX。13.4.1 基于LALR(1)的语法分析程序的生成器YACCYACC(Yet Another Compiler-Compiler)是1975年由Johnson开发的一个用于语法分析器的生成器，它接受一个用BNF描述的上下文无关语言的语法规则，且语法满足LALR(1)文法的要求。它将自动生成相应语法的LALR(1)分析表，与它的驱动程序和分析栈结合构成一个LALR(1)分析器称yyparse。它与词法分析程序的接口称为yylex。其词法分析程序不管是手工编写还是自动生成工具构造，只要程序名为yylex即可与YACC配合工作，即由YACC生成的语法分析器需要单词符号(终结符)时调用yylex，其单词的属性值和自身值的存放，也有相应约定。其工作示意图如图13.13所示。图 13.13 YACC工作示意图在YACC的源程序中，除了BNF描述的语法规则外，还可以包括当这些语法规则被识别出来时需要完成的语义动作，其语义动作可以是一段C程序(或RATFOR程序)。语义动作的内容可以是填写和查找符号表、做语义检查或生成语法树和代码生成等，若动作加在一条规则的末尾，则表明用此规则归约时所做的动作。动作也可插入在某规则的文法符号之间，这时需注意伪变量的位置关系。因为LR类分析表只有当归约时才能调语义处理动作，所以YACC对于在语法规则的文法符号之间插入的语义动作自动增加规则和非终结符，使其语义动作都在一条规则的末尾，即归约时做。对此的详细说明请参见附录C。此外YACC还可以处理某些二义性文法的规则，我们在第7章中曾介绍过二义性文法在LR分析中的应用，YACC也给出了二义性文法终结符之间的优先关系和结合性的书写规定。对用户书写的二义性文法规则按其优先级和结合性自动生成相应的分析表，对于用优先级和结合性能解决的冲突，YACC不报告错误。当所给的条件仍不能解决冲突时才报错。在第7章中曾介绍过二义性文法在LR分析中的应用，当给出了二义性文法终结符之间的优先关系和结合性的规定后，可能会解决LR项目集中的冲突，用二义性文法的LR分析和同样语言非二义性文法的LR分析相比可提高对输入串分析的速度，例如：表达式的二义性文法的LR分析速度比非二义性文法的LR分析速度要快的多。13.4.2 词法分析程序的生成器LEX LEX是一个词法分析器(扫描器)的自动生成系统。它的输入是描述3型语言的正规表达式，输出是一个相应正规表达式的词法分析程序。其示意图如图13.17。图 13.17 LEX功能示意图正像YACC那样，LEX也可以借助宿主语言C或RATFOR描述动作，LEX自动地把表示输入串词法结构的正规式及相应的动作转换成一个宿主语言的程序，即词法分析程序。它有一个固定的名字为yylex，yylex是一个C语言(或RATFOR语言)程序。经C语言编译程序编译后可运行，它的功能就是对输入串识别出单词符号，并可做相应的动作。例如，把输入串的小写字母转换成相应的大写字母，可有如下的LEX源程序。%a-z printf(%c， yytext0+A-a)；其中%是分界符，表示识别规则的开始，a-z是识别小写字母的规则，printf()是识别出小写字母时采取的动作，即将小写字母变换成相应的大写字母。yytext0是工作单元，是用以存放yylex识别的字符或字符串自身的值。LEX的工作原理是将LEX源程序中的正规式转换成相应的确定有限自动机,将其动作插入到yylex中适当的地方。控制流是由确定的有限自动机的解释器完成，解释器是LEX的构成部分，像YACC中的驱动程序一样，它对不同的输入源程序来说解释器是相同的。对于LEX的详细说明，请参阅附录B。考虑问题： 编译程序的实现应考虑的问题有那些？ 编译程序的实现途径有那些？本章小结【本章小结】 要求学员掌握一个编译程序的实现途径，在所给环境下能够提出自己的设计方案。 用编译程序的构造工具YACC和LEX编写一个小型编译程序，和第2章介绍的PL/0编译程序的实现进行比较，体会用编译程序的构造工具YACC和LEX编写编译程序的优点。 目前YACC和LEX被广泛应用，Ada，C，C+，Java等高级程序设计语言就是用Yacc开发的前端。Yacc 和 Lex 联合应用的示意图如下：编译程序的自动生成工具f13-1-1.swf课后习题第13章习题第1题：如何用T型图 表示一个编译程序的实现？第2题：如何用自展方式在PC机上实现C语言的编译程序？请用T型图 表示。第3题：什么叫做软件移植？第4题：什么叫做交叉编译？第5题：编译程序的实现应考虑的问题有那些？第6题：编译程序的实现途径有那些？问答第1题解答：用T型图 表示编译程序的实现问答第2题解答：用自展方式在PC机上实现C语言的编译程序，首先把C划分成