（通信与信息系统专业论文）基于gcc开发c编译器的研究与实践.pdf

! ! ! ! 。： 塑堡查兰堡主兰垡丝兰一 摘要 酽锄5 砧 f编译系统是任何计算机系统中不可缺少的重要部分。但是编译系统的研制冈其技术复 杂、难度较高而需要投入较多的人力、物力和花费较长的研制周期。过去编译系统的研制均 是针对某一种程序设计语言和某一种目标机而专门编写的。随着计算机的飞速发展，这种传 统的方法已经很难满足需要。进入八十年代后期，随着国外各种软件公司的兴起以及各种计 算机芯片不断推陈出新，研制支持多目标机的编译系统越来越显得重要，编泽榉序的开发者 们认识到只有既支持多语种又支持多目标机的编译系统才具有生命力和竞争价值。这种系统 实际上是开发编译程序的基础平台，它采用的技术代表着编译技术的发展方向。， 一一、 ， ， g n u c c 是这种支持多语种、多目标机编译系统中最有代表性的个系统。【它目前已支 持的语言有c 、c + + 、o b j e c t i v ec 、f o r t r a n 、a d a ；已移植的平台有一百多种，涉及二 十多种处理机，六十多种系统。g n uc c 之所以有如此广泛的移植和使用，其原因除了它的 源代码公开之外，更重要的原因应归于其独特的结构。其清晰的前端语法树结构、高度概括 的抽象机中间语言、简洁有力的后端机器描述等三部分为快速实现多语种开发、多平台移植 提供了有力的支持。，一一j f 。 目前，浙江大学信息与通信工程研究所正在进行3 2 位多媒体数字信号处理器( 命名为 m d 3 2 ) 的软硬件开发。由于g n uc c 的这种优点，我们选择它对新目标机进行移植。本 文作为前导性的尝试，提出一个简单的处理器模型s u b d l x ，通过对s u b d l x 目标机重写机 器描述，实现了g c c 的成功移植。为以后实现对m d 3 2 移植o c c 打下来了基础。在实践 过程中我们发现，g c c 看似庞大复杂，其实内部结构清晰，技术成熟，它不仅可用来作为 开发新语言编译程序或移植至新目标机的基础，同时还可以用于进行新编译技术，如面向新 体系结构的优化技术研究与实验。 此外，我们借助g c c 编译过程中产生的中闻代码r t l ( r e g i s t e r t r a n s f e r l a n g u a g e ) 文 件，重写目标代码生成和优化功能程序，为新的目标机器开发c 语言编译器。f 这个方法不 要求程序员精通g c c ，能够快速的进入编译器的开发，缩短项目开发周期，l 眺上可以得 到个更高效的编译器。，= 卜w 一“一 锄：c 淬i 鳓。：，曼。 r 0 ；d o u b l ev a l u ei nr 0 ；a d d r e s s o f a - r i ；a d d r 0 t o r l ：c o n s t a n t6 - a d d r e s sj nr 在以上代码中，为编址模式使用了一个类似c 的协定，因此a 是a 的地址( 也就是数 组的基地址) ，* r i 则意味着间接寄存器地址( 因此最后一条指令将值6 存放在r 】包含的 地址中) 。这个代码还假设机器执行字节编址并且整型数占据存储器的两个字节( 所以在 第2 条指令中用2 作为乘数) 。 ( 6 ) 目标代码优化程序( t a r g e tc o d eo p t i m i z e r ) 在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括选择编 址模式以提高性能、将速度慢的指令更换成速度快的，以及删除多余的操作。 在上面给出的样本目标代码中，还可以做许多更改：在第2 条指令中，利用移位指令替 代乘法( 通常地，乘法很费时间) ，还可以便用更有效的编址模式( 例如用索引地址来执行 数组存储) 。使用了这两种优化后，目标代码就变成： m o vr 0 i n d e x s h lr 0 m o v a r o 】，6 v a l u eo f i n d e x r o d o u b l ev a l u ei nr o c o n s t a n t6 - a d d r e s sa4 - r o 到这里，对编译器阶段的简要描述就结束了，但我们还应特别强调这些讲述仅仅是示意 性的，也无需表示出正在工作中的编译器的实际结构。编译器在其结构细节上确实差别很大， 然而，上面讲到的阶段总会出现在几乎所有的编译器的某个形式上。 我们还谈到了用于维持每一个阶段所需信息的数据结构，例如语法树、中间代码( 假设 它们并不相同) 、文字表和符号表。下一节是编译器中的主要数据结构的概览。 7 塑姿态兰堡! ：兰堡垒茎 1 4 编译器中的主要数据结构n 删 当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强人 的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小 成线性比例的时间内编译器，换言之就是，在0 ( n ) 时间内，n 是程序大小的度量( 通常是字 符数) 。本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并异； 来在阶段 中交流信息。 ( 1 ) 记号( t o k e n ) 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说， 作为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生 出的其他信息( 例如：与标识符记号相关的名字或数字记号值) 。在人多数语言中，扫描程 序一次只需要生成一个记号( 这称为单符号先行( s i n g l es y m b o li o o k a h e a d ) ) 。在这种情况下， 可以用全程变量放置记号信息：而在剐的情况( 最为明显的是f o r t r a n ) f ，则可能会需 要一个记号数组。 ( 2 ) 语法树( s y n t a xt r e e ) 如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时 动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个肯点都 是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。例如，一个表达式 的数据类型可作为表达式的语法树节点中的域。有时为了节省空间，这些域也是动态分配或 存放在诸如符号表的其他数据结构中，这样就可以有选择地进行分配和释放。实际上，根据 它所表示的语言结构的类型( 例如：表达式节点对于语句节点或声明节点都有不同的要求) ， 每一个语法树节点本身都可能要求存储不同的属性。在这种情况下，可由不同的记录表示语 法树中的每个节点，每个节点类型只包含与本身相关的信息。 ( 3 ) 符号表( s y m b o lt a b l e ) 这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与 编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序：语 义分析程序将增加数据类型和其他信息i 优化阶段和代码生成阶段也将利用由符号表提供的 信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比 常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。 有时在一个列表或栈中可使用若干个表格。 ( 4 ) 常数表( 1 i t e r a lt a b l e ) 常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也 十分重要。但是，在其中却无需删除这是因为它的数据全程应用于程序而且常量或字符串 在该表中只出现一次。通过允许重复使用常量和字符串，常数表对于缩小程序在存储器中的 大小显得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入 数据定义的符号地址。 ( 5 ) 中间代码( i n t e r m e d i a t e c o d e ) 根据中间代码的类型( 例如三元式代码和p - 代码) 和优化的类型，该代码可以是文本 8 塑垩查堂堡! ：兰竺笙兰 串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，戍特别注意选 择允许简单重组的表示。 ( 6 ) 临时文件( t e m p o r a r yf i l e ) 计算机过去直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临 时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译( 也就是只保留源程序早期部分 的足够信息用以处理翻译) 解决了。存储器的限制现在也只是个小问题了，现在可以将整 个编译单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要 在某些运行步骤中生成中间文件。其中典型的是代码生成时需要反填( b a c k p a t c h ) 地址。 例如，当翻译如下的条件语句时 i f x = 0 t h e n e l s e 在知道e l s e 部分代码的位置之前必须由文本跳到e l s e 部分： c m p x ，0 j n en e x t ；l o c a t i o no f n e x tn o ty e tk n o w n c o d ef o rt h e n - p a r t n e x t ： 通常，必须为n e x t 的值留出一个空格，一旦知道该值后就会将该空格填上，利用f i 台； 时文件可以很容易地做到这一点。 1 5 编译器结构中的其他问题口1 可从许多不同的角度来观察编译器的结构。1 3 节已讲述了它的阶段用来表示编译 器的逻辑结构。此外，还有其他一些可能的观点：编译器的物理结构、操作的顺序等等。由 于编译器的结构对其可靠性、有效性、可用性以及可维护性都有很大的影响，所以编译器的 编写者应熟悉尽可能多的有关编译器结构的观点。本节将考虑编译器结构的其他方面以及每 一个观点是如何应用的。 ( 1 ) 分析和综合 在这个观点中，已将分析源程序以计算其特性的编泽器操作归为编译器的分析 ( a n a l y s i s ) 部分，而将生成翻译代码时所涉及到的操作称作编译器的综合( s y n t h e s i s ) 部分。 当然，词法分析、语法分析和语义分析均属于分析部分，而代码生成却是综合部分。在优化 步骤中，分析和综合都有。分析正趋向于易懂和更具有数学性，而综合则要求更深的专业技 术。因此，将分析步骤和综合步骤两者区分开来以便发生变化时互不影响是很有用的。 ( 2 ) 前端和后端 本观点认为，将编译器分成了只依赖于源语言( 前端( f r o n te n d ) ) 的操作和只依赖于 目标语言( 后端( b a c ke n d ) ) 的操作两部分。这与将其分成分析和综合两部分是类似的： 扫描程序、分析程序和语义分析程序是前端，代码生成器是后端。但是一些优化分析可以依 赖于目标语言，这样就是属于后端了然而中间代码的综合却经常与目标语言无关，因此也 就属于前端了。在理想情况下，编译器被严格地分成这两部分，而中间表示则作为其间的交 流媒介。 9 塑垩查鲎塑：! 堂竺笙兰 这一结构对于编译器的可移植性( p o r t a b i l i t y ) 十分重要，此时设计的编译器既能改变 源代码( 它涉及到重写前端) ，又能改变目标代码( 它还涉及到重写后端) 。在实际中t 这是 很难做到的，而且称作可移植的编译器仍j 月依赖于源语言平目标语言。其部分原冈是程序设 计语言和机器构造的快速发展以及根本性的变化，但是有效地保持移植一个新的目标语言所 需的信息或使数据结构普遍地适合改变为个新的源语言所需的信息却十分困难。然而人们 不断分离前端和后端的努力会带来更方便的可移植性。 ( 3 ) 遍 编译器发现，在生成代码之前多次处理整个源程序很方便。这些重复就是遍( p a s s ) 。 首遍是从源中构造一个语法树或中间代码，在它之后的遍是由处理中间表示、向它增加信息、 更换结构或生成不同的表示组成。遍可以和阶段相应，也可无关遍中通常含有若干个阶 段。实际上，根据语言的不同，编译器可以是一遍( o n ep a s s ) 所有的阶段由一遍完成， 其结果是编译得很好，但( 通常) 代码却不太有效。p a s c a l 语言和c 语言均允许单遍编译。 ( m o d u l a - 2 语言的结构则要求编译器至少有两遍) 。大多数带有优化的编译器都需要超过一 遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第3 遍用于代码生成和目标层的优化。更深层的优化则可能需要更多的遍：5 遍、6 遍、甚至8 遍都是可能的。 ( 4 ) 语言定义和编译器 我们注意到在1 1 节中。程序设计语言的词法和语法结构通常用形式的术语指定，并使 用正则表达式和上下文无关文法。但是，挫序设计语言的语义通常仍然是由英语( 或其他的 自然语言) 描述的。这些描述( 与形式的词法及语法结构一起) 一般是集中在一个语言参考 手册( 1 a n g u a g er e f e r e n c em a n u a l ) 或语言定义( 1 a n g u a g ed e f i n i t i o n ) 之中。因为编译器的编 写者掌握的技术对于语言的定义有很大的影响，所以在使用了一种新的语言之后，语言的定 义和编译器同时也能够得到开发。类似地。一种语言的定义对于构造编译器所需的技术也有 很大的关系。 编译器的编写者更经常遇到的情况是：正在实现的语言是众所周知的并已有了语言定 义。有时这个语言定义己达到了某个语言标准( 1 a n g u a g es t a n d a r d ) 的层次，语言标准是指 得到诸如美国国家标准协会( a m e r i c a nn a t i o n a ls t a n d a r d si n s t i t u t e ，a n s i ) 或国际标准化 组织( i n t e r n a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n ，i s o ) 的官方标准组织批准的标准。 f o r t r a n 、p a s c a l 和c 语言就具有a n s i 标准，a d a 有一个通过了美国政府批准的标准。 在这种情况下，编译器的编写者必须解释语言的定义并执行符合语言定义的编译器。通常做 到这一点并不容易，但是有时由于有了标准测试程序集( 测试组( t e s ts u i t e ) ) ，就能够测试 编译器( a d a 有这样一个测试组) ，这又变得简单起来了。 有时候，一种语言可从数学术语的形式定义( f o r m a ld e f i n i t i o n ) 中得到它的语义。现在 人们已经使用了许多方法，尽管一个称作表示语义( d e n o t a t i o n a ls e m a n t i c s ) 的方法已经成 为较为常用的方法，在函数编程共同体中尤为如此，但现在仍然没有一种可成为标准的方法。 当语言有一个形式定义时，那么在理论上就有可能给出编译器与该定义一致的数学证明，但 是由于这太难了而几乎从未有人做过。 运行时环境的结构和行为是尤其受到语言定义影响的编译器构造的一个方面。尽管此时 它没有多大用处但程序设计语言所允许的数据结构( 尤其是被许可的函数调用和返回值的 类型) 对于运行时系统的复杂程度具有决定性意义。以下是运行时环境的3 个基本类型( 按 难易程度排列) ： 首先是f o r t r a n 7 7 ，它没有指针或动态分配，也没有递归函数调用，但它允许有一个 1 0 塑坚盔兰堡! ：兰垡笙皇 一 完整的静态运行时环境。在这个环境中，所有存储器的分配都在执行之前进行。冈为无需生 成代码来维护环境，编译器的编写者的分配一1 。作也就容易许多了。其次是p a s c a l 、c 和其他 类似a l g o l 的语言，它们允许有限动态分配以及递归函数的调h j ，并且要求“半动态”或带 有额外的动态结构( 称为堆，由此程序员可安排动态分配) 的基于栈的远行时环境。最后是 面向对象的函数语言，如l i s p 和s m a l l t a l k ，它们要求“完全动态”的环境，在其中所有的 分配都是由编译器的生成代码自动完成的。因为它要求也能够自动释放存储器，而这又相麻 地要求复杂的“垃圾回收”算法，所以它很复杂。 ( 5 ) 编译器的选项和界面 编译器结构的一个重要方面是包含了一种机制与操作系统相连接。并为了满足用户的各 种目的而提供选择。界面机制的例子是提供对目标机器的文件系统的访闯以及输入和输出功 能。用户的选项可包括列表特征( 长度、出错信息和相互对j ! 表) 的说明和代码优化选项( 只 是某个优化的执行) 。选项和界面共称为编译器的语用学( p r a g m a t i c s ) 。有时一种语言的定 义指出必须提供的语用学。例如，p a s c a l 和c 语言均指出一定的输入输出过程( 在p a s c a l 中，它们是语言特性中的一部分：而在c 语言中，它们是标准库说明的一个部分) 。在a d a 中，许多编译器的指示( 称为( p r a g m a s ) ) 则是语言定义的一部分。例如：a d a 语句 p r a g m al i s t ( o n ) p r a g m al i s t ( o f f ) ； 为包含在p r a g m a s 中的程序部分生成了一个编译器列表。在这个文本中，我们发现编译 器指示仅存在于用作编译器调试的生成列表信息的上下文中；另外，也不会在输入输出和 操作系统界面中处理问题，这是因为它们涉及到了大量的细节，而且随操作系统的不同而有 很大差异。 ( 6 ) 出错处理 编译器的一个最为重要的功能是其对源程序中错误的反应。几乎在编译的每一个阶段中 都可以诊察出错误来。这些静态( 或称为编译时( c o m p i l e - t i m e ) ) 的错误( s t a t i ce r r o r ) 必 须由编译器来报告，而编译器能够生成有意义的出错信息并在每一个错误之后恢复编译是非 常重要的。编译器的每一个阶段都需要一个类型略为不同的出错处理，因此错误处理器( e r r o r h a n d l e r ) 必须包括不同的操作，每个操作都给出指定的阶段和结构。因此，读者将在相应的 章节中学到每一个阶段的出错处理技术。 语言定义经常要求编译器不仅能够找到静态错误，而且还能找到执行错误。这就需要编 译器生成额外的代码，该代码将执行恰当的运行时测试。以保证所有这样的错误都将在执行 时引起一个合适的事件。在此类事件中，最简单的就是中止程序的执行。但这经常是不合适 的，而且语言的定义可能要求存在异常处理( e x c e p t i o nh a n d l i n g ) 机制。这将使运行时系 统的管理变得非常复杂，当程序可能由错误发生处继续执行时尤其如此。 1 6 自举与移植口3 前面已经讨论过源语言和目标语言在编译器结构中的决定因素，以及将源语言和目标语 言分为前端和后端的作用，但是却未提到过编译器构造过程中涉及到的另一个语言：编写编 译器本身使用的语言。为了使编译器能立即执行，这个执行( 或宿主( h o s t ) ) 语言只能是机 器语言。当时并没有编译器，因此这确实是蜃初的编译器编写所用的语言。现在更为合理的 浙江大学颂十学位论文 _ - _ _ _ _ 一一 方法是用另一种语言来编写编译器，而使州该种语言的编译器早己存在了。如果现存的编译 器已经在目标机器上运行了，则只需利用现存的编译器编译出新的编译器以得到可运行的稃 序： 当语言b 的现存编译器没有运行在目标机器上时情况会更复杂一些。编译将产生一个交 叉编译器( c r o s sc o m p i l e r ) ，也就是一个为不同于它在运行之上的机器生成目标代码的编泽 器。这种以及其他更为复杂的情况最好通过将编译器画成一个t 型圈( t - d i a g r a m ) ( 以其形 状来命名) 来描述。用语言h ( 代表宿主语言) 编写的编泽器将语言s ( 代表源语言) 翻译 为语言t ( 代表目标语言) 可画成以下的t 型图： 请注意，这与表示编译器是在“机器”h 上运行是等价的( 如果h 不是机器代码，删 可认为其是一个假定机器的可执行代码) 。我们一般都希望h 与t 相同( 也就是编译器为与 之运行之上一样的机器生成代码) ，但是也并不是必须这样做。 可以用两种方法组合t 型图。一种是，如果在一台机器h 上运行有两个编译器，其中 一个编译器将语言a 翻译为语言b ，另一个将语言b 翻译为语言c ，就可按照将第1 个的 输出作为第2 个的输入来组合。其所得结果就是个在机器h 上的由a 到c 的编译。将该 过程表示为： 另一种 执行语言。 在上面 为用b 编写 第2 个假定是，当语言b 的编译器运行在另一台机器上时，就会引出语言a 的交叉编 译器。如下图所示： 1 2 一 塑坚盔堂堡：! ! 堂堡垒兰 以将要编译 ah ： h 器的最终版本 用语言a 自身 编译器的摄终版本 编写的编译器 正运行但效率低的编译嚣 ( b ) 图1 2 自举进程 ( a ) 自举进程中的第一个步骤( b ) 自举进程中的第= 个步骤 口j ! n 3 蒜嚣麓 原始编译器 ( a ) ， 交叉编译器 3 守 堑坚查堂丝! ：兰垡望兰一 广 厂 a k i “【 a ak 一 k l j 一 一 一l j ! 。 j “l 目标重定位为k 目标重定位后的编详器 的编译嚣源代码 交叉编译器 ( b ) 图1 3 移植一个在其i + i 身源代码中编写的编译器 ( a ) 步骤1c b ) 步骤2 但这将表现为一个循环错误：因为如果源语言的编泽器不存在，那么编译器本身也就不 可能被编译了。从这个方法中可以得到很重要的启示。 让我们设想一个问题：如何解决循环。我们可以在汇编语言中编写一个“虽快但不佳” 的编译器，并翻译那些在编译器中真正使用得到的语言特征( 当然，在编写“较好的”编译 器时，会对使用那些特征有所限制) 。这些“虽快但不佳”的编译器也可能产生极为无效的 代码( 它仅需要正确而已! ) 。一旦运行这个“虽快但不佳”的编译器，就可用它来编译那个 “较好的”编译器。接着，对“较好的”编译器进行重编译以得到最终的版本。人们将这个 过程称为自举( b o o t s t r a p p i n g ) 。图l 一2 a 和图1 2 b 描述了这一过程。 自举之后，在源代码和执行代码中就有了一个编译器。这样做的好处在于：通过应用与 前面相同的两步过程，编译器的源代码的任何改进都会立即被白举到一个正在工作着的编译 器中。 除此之外，还有一个好处。现在将编译器移植到一个新的主机，只要求重写源代码的后 端来生成新机器的代码。接着用旧的编译器来编译它以生成一个交叉编译器，该编译器又再 次被交叉编译器重新编译，以得到新机器的工作版本。图1 3 a 和圈1 3 b 描述了这一过程。 4 塑坚查堂堡主堂垡堡兰一 第二章g e c 编译器 2 1g c c 简介1 8 川 2 1 1g n uc 的起源与发展n 1 9 8 5 年，美国杰出的程序设计师r i c h a r ds t a l l m a n 发起并创建了世界上第一个非营利性 计算机软件组织自由软件基金会( f s f ) 。该组织以追求技术上的创新，开发为公众共 享的软件产品为宗旨，制定了雄心勃勃的“g n u 计划”。g n u 是g n u s n o t u n i x 的递门缩 写。该计划的目标是要提供一个与u n i x 兼容的完整系统并免费提供给所有使用它的刚户。 第一个产品用于u n i x 及、，a x ，v m s 上的享有盛名的g n ue m a c 一个可编程的编辑器： 而另一个著名产品就是g c c ( g n ucc o m p i l e r ) 编译器。由于程序设计人员可以彼此共享 这些软件和技术，使得g n u 软件都较同级的商业软件产品更为稳定可靠、性能指标更高， 而且发展极为迅速，每一个季度就有一个功能更强、品质更优的新版本推出。因此，g n u 软件具有很强的生命力，并随着人们对其价值认识的提高，用户也必将迅速地扩大。 g n uc 是a n s ic 的超集。它除了保持c 语言家族的简洁、高级及灵活之外，还增加 了许多新的语言特征，其中某些是从p a s e a | 、c + + 及a d a 语言中汲取来的，因而其描述功能 更为丰富，更易于编写高效、可靠的程序。 g c c 是一个用c 语言实现的优化可移植编译系统。高度的优化和可移植性能是该编译 系统最为突出的两大特点，也是技术上的最为成功和精彩之处。由于优化和可移植性是衡量 现代编译系统的主要标准，加之g c c 的高稳定和免费提供等优点，使许多专门从事c 编译 器的公司难能与之对抗。g n u 声称“要让世界上所有搞编译器的人没有事情可做”。 2 1 2g c c 的步骤n 8 1 g c c 的实现步骤包括：预编译p r e p r o e e s s ( g c c - e ) 、编译c o m p i l e ( g c c ) 、汇编a s s e m b l e ( a s ) 和连接l i n k ( i d ) 。 ( 1 ) 预编译p r e p r o c e s s 源代码中的预编译指示以“# ”为前缀。可以通过在g e c 后加上e 选项来调用预编译器。 预编译过程通过完成三个主要任务给了代码很大的灵活性。 将“i n c l u d e ”的文件拷贝到编译的源文件中 用实际值替代“d e f i n e ”的文本 在调用宏的地方进行宏替换 ( 2 ) 编译c o m p i l e 作为一个中间步骤，g c c 把源代码翻译成汇编语言。这是项极其复杂的工作，包括词 法分析、语法分析、中间代码产生、编译优化和汇编代码生成( 在下面章节会一一详述) 。 人们有时会把这一步误解为整个过程，但是，实际上还有许多工作要g c c 去做昵! 堂堡盔竺丝：! 兰垡丝兰 一 一一 ( 3 ) 汇编a s s e m b l e g c c 通过a s 把汇编语言代码转换为目标代码。事实上，目标代码并不能在c p u 上运 行。编译器选项c 把c 文件转换为以o 为扩展名的目标文件。 ( 4 ) 连接l i n k 连接器i d 使用下丽的命令。接受前面由a s 创建的目标文件并把它转换为可执行文件。 2 2 词法分析和语法分析n 劬 2 2 1g c c 词法分析程序的主要功能 词法分析程序的输入( 即其扫描的源程序文件) 是预处理程序程序的输出，预处理的输 出是放在一个缓冲区内，词法分析程序将从该缓冲区内读取字符作为自己的输入。 词法分析是编译的第一阶段，它的主要任务是从左到右逐个字符地对源程序文件进行扫 描，产生一个个单词序列，用以语法分析。执行词法分析的程序称为词法分析程序或扫描程 序。 词法分析程序可由词法产生器l e x 产生或是人工编写，在g c c 中，词法分析程序是人 工编写的，因此g c c 的词法分析程序具有较好的可读性。它主要包含c - l e x c ，c 1 e x h 文件 以及相关的文件，其主要功能由函数y y l e x 实现。从预处理的输出文件中一个一个地读取字 符，按照尽司能大的原则组成单词( t o k e n ) 组成的单词是放在单词的输出缓冲中。对数字常 量、字符常量等，为其建立节点，并使y y l v a l t t y p e 指向此节点，返回单词的值( v a l u e ) 。其 中单词的属性值是通过结构变量y y l v a l t t y p e ，y y l v a l c o d e ，y y l v a l i t y p e 返回的。 g c c 的词法分析程序将单词分成6 类 ( 1 ) 标识符：包括关键字和自定义标识符由字母( a - z , a z ) 、下划线“一”和“ ”开头， 以及数字组成的单词。组成单词届首先判别该单词是否是关键词，若是则写相应的属性 值。若不是关键词，则该单词是用户自定义的标识符，为其建立一个节点，并添加到链 表中。 ( 2 ) 数字。由数字“0 - - 9 ”组成的单词。其中又可分为】6 ，1 0 ，8 进制，且有浮点和非浮点 之分。 ( 3 ) 字符常量。单引号包含的字符常量。 ( 4 ) 字符串常量。由双引号包含的字符串常量。当由l 开头的字符串常量( l “”) 为宽字 符串( w i d e s t r i n g ) 常量。 ( 5 ) 运算符。包括算术运算符和逻辑运算符以及指针运算符。“+ ”、“”、“& ”、“n “ ”、“+ ”、“”、“”、“ 、“! ，、“一、“+ + ”、“”、“& ”、“i | ，、 ”、“ ”。 ( 6 ) 其它。如：“ ，、“ i 等。 2 2 2 词法分析程序的流程图及其说明 在g c c 中，词法分析程序是一个子程序。每当语法分析程序需要一个单词时，则调用 该子程序。词法分析程序每被调用一次，便从源程序文件读入一些字符，直至识别出个单 词，或说是直至下一个单词的第一个字符为止。g c c 的词法分析程序是通过调用c 的标准 1 6 浙江大学硕士学位论文 库函数g e t e ( f i n p u t ) ，u n g e t c ( c ，f i n p u t ) 来实现从源程序文f l ：读取字符到单词的缓冲区及将字 符放回到输入源程序文件的。 词法分析程序的流程图及其说明：( 见幽2 1 ) 词法分析程序的功能主要由函数y y l e x 来实现，y y l e x 调用标准库函数g e t c 从源程序文 件中逐个读取字符，该源程序文件是g c c 预处理的输出文件，并对该字符进行分析处理。 首先函数y y l e x 判别读入的字符是否为转义字符，如：t 。巾，v ，b 等，若是转 义字符，则跳过转义字符，然后再从源程序文件中读取字符。接着判别该字符是否为n ， ，等，若是则调用函数s k i p _ w h i t e _ s p a c e 取得新字符。将读入的字符暂时放在l 临时变量中， 并对该字符进行分析处理。 在词法分析程序的流程图中，将可能组成单词字的符分成八种情况分析处理，以下分别 对每种情况作简要的说明。 e o f 是源程序文件的结束符号。当词法分析程序读到该字符时，就认为对源程序文件 的扫描工作结束了，也可以说是诃法分析结束了。 l 是宽字符常量或是宽字符串常量的起始标志。如果l 后是 ，则是宽字符常鼍。 如果l 后是“”，则是宽字符串常量。 $ 是美元符号。如果标志位被置1 ，则它作为组成标识符的字符元素，否则返回$ 。 由字符a - z ，a - z ，( $ ) 。开始的单词是标识符。调用函数i sr e s e r v e dw o r d 函数在关键字( 或保留字) 表中查找此标识符是否存在，若找到则该标识符为保留字。否则 为用户自定义的标识符，调用函数g e l i d e n t i f i e r 在h a s ht a b l e 中查找该标识符，如果找到则 返回指向此节点的指针否则调用函数m a k en o d e 建立一个节点，返回此节点的指针。 由数字0 - 9 ，开始的单词构成各种数，包括整数，实数。指数，浮点数，复数等， 有八进制，十进制和十六进制以及由u ，l ，u ，l 修饰的数。 由”开始的单词是字符常量，即由单引号包含的字符是字符常量。 由“”开始的单词是字符串常量，即由双引号包含的单词是字符串常量。 由“十”、“- ”、“”、“l ，、“ ”、“p 、“”、“”、“ ，、“! ”、“= ”构成算术运算符 和逻辑运算符。 经过分析处理的字符将被放入单词的缓冲区内。函数y y l e x 将此单词的值返回给调用它 的语法分析程序，其属性值将通过结构变量y y l v a l t r y 等返回。 7 堑兰查兰丝：! 兰竺丝苎 一一 图2 1词法分析程序的流程图 2 2 3g c c 语法和语义分析程序的主要功能 语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列 分解成各类语法短语，如“程序”，“语句”，“表达式”等等。一般这种语法短语也称为语法 单位，可表示成语法树。 ( 一) 语法分析程序的主要功能 语法分析所依据的是语言的语法规则，即描述程序结构的规则。通过语法分析确定整个 输入串是否构成一个语法上正确的程序a 在g c c 中采用自底向上( b o t t o m u p ) 最右规约的 1 8 塑婆查堂堡! ：堂些堕壅 语法分析方法进行分析的，因为g c c 的语法分析程序是由语法分析程序a 榭( y a c c ) 生成，l r 方法是y a c c 设定的语法分析方法。 语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。例如语义分析的 一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合诰言 规范时，编译程序应报告错误。 词法分析和语法分析本质上都是对源程序的结构进行分析。但词法分析的任务仅对源程 序进行线性扫描即可完成，例如识别标识符，因为标识符的结构是字母打头的字母和数字串， 这只要顺序扫描输入流，遇到既不是字母又不是数字字符时，将前面所发现的所有字母可数 字组合在一起而构成单词标识符。但这种线性扫描不能用于识别的递归定义的语法成分，比 如不能用此办法去匹配表达式中的括号。 ( 二) 语法分析程序自动产生器( y a c c ) 简介 由于g c c 中的语法分析程序是由y a c c 产生的，故在此对y a c c 的工作原理作一简要 的介绍。y a c c 的工作示意图如图2 2 ： y a c c 源程序 图2 2y a c c 的工作示意图 在图中y a c c 源程序是用户用y a c c 提供的一种类似b n f 的语言写的要处理的语言的 语法描述。y a c c 会自动的将这个源程序转换成用l r 方法进行语法分析的语法分析程序 y y p a r s e ，y a c c 的宿主语言是c ，因此y y p a r s e 是一个c 语言的程序，用户在主程序中通过 调用y y p a r s e 进行语法分析。 语法分析必须建立在词法分析的基础之上，所以生成的语法分析程序还要有一个词法 分析程序与它配合工作。y y p a r s e 要求这个词法分析程序的名字为y y l e x 。用户写y y l e x 时可 以借助于l e x ，也可以人工编写。 在y a c c 源程序中除了语法规则外，还要包括当这些语法规则被识别出来时，即用它 们进行归约时要完成的语义动作，语义动作是用c 语言写的程序段。 语法分析的输出可能是一颗语法树，或生成的目标代码，或者就是关于输入串是否符合 语法的信息。需要什么样的输出都是由语义动作和程序部分的程序段来实现的。 ( 三) 语法分析程序的文件构成 语法分析程序尽管是由y a c c 自动产生的，但其语义动作是由用户自己编写的c 代码， 构成语法分析程序的文件有：c p a r s e y ，t r e e h ，t r e e d e f , c - t r e e h ，t r e e c ，c d e c l c c - t y p e c k c ， s t m t c 等。其中c p a r s e y 是根据y a c c 的规范要求对c 语言文法进行的语法描述文件，即 y a c c 源程序，经y a c c 可产生相应的c 文件c p a r s e c 。 相关的文件有c - l e x h ，i n p u t h ，c - i t e r a t e c ，v a r a s m c c c o m m o n c ，c 1 e x c m a c h m o d e h ， m a c h m o d e d e f 。o b s t a c k h ，r e a l h ，r i i h 等。 1 9 塑婆查堂堡! ：兰丝堡皇 2 2 4 语法和语义分析程序的流程图及其说明 ( 一) 语法分析程序的主要工作原理 由y a c c 产生的语法分析程序是由放在栈中的有限状态机构成的，它同时能够读取并 记住下一个输入的单词( t o k e n ) ，有时也叫这样的单词为向前看字符( 1 0 0 k , a h e a dt o k e n ) 。有 限状态机的状态是用一个整数表示的，这与词法、语法分析程序中的单词是相似的。在初始 时，机器处在0 状态，此时仅仅栈中包含了状态0 ，而没有向前看字符被读入。 有限自动机在语法分析程序中可执行相应的动作，以决定下一步的动作。语法分析可执 行的动作( a c t i o n ) 共有4 个，它们分别是：移进( s h i f t ) 、归约( r e d u c e ) 、接受( a c c e p t ) 和错误( e r r o r ) 。语法分析程序的运行如下： 1 )根据当前状态，语法分析程序决定是否需要一个向前看字符以决定将要执行什么动 作。如果需要一个单词但还没有读入时，语法分析程序将调用y y l e x 获得下一个单 词。 2 1用当前状态和向前看字符( 如果需要的话) ，语法分析程序决定它的下一个动作 ( a c t i o n ) ，并且执行这个动作。这样将导致状态被压入或被弹出栈，以及向前看字 符是被处理了还是放在一边待用的不同变化。 以下分别说明4 种语法动作： 移进动作( s h i f ta c t i o n ) 是语法分析程序采用的最平常的动作。根据当前栈的状态和向 前看字符，语法分析程序查动作表( a c t i o n 表) ，以决定将采取什么动作。对于移进动作， 不论何时采用移进动作，都有一个向前看字符，不然移进动作将无法执行对单词的清除处理。 而对应的状态却被压入了状态栈，从而造成错误。 归约( r e d u c ea c t i o n ) 是用语法规则的左边代替其右边的过程。当语法分析程序已经看 到某语法规则的右边，并且确定右边是语法规则的一个实例时，归约动作将被采用。通常语 法分析程序在采用归约动作时是不需要查看向前看字符的。 归约动作能防止栈无限增大，因为大多数情况下归约动作是将状态弹出栈，减少占用 的栈空间。归约动作取决于语法规则左边的符号( 非终结符) 和右边的符号( 终结符和非终 结符) 数。归约动作首先根据语法规则右边的符号数决定将被弹出栈的状态数，然后将状态 从栈中弹出，使栈中的其它的状态被显露出来。事实上，被弹出的状态就是在识别此规则右 边单词时压入栈的状态，规则一旦被识别，这些状态将不再有用。将这些状态弹出之后，在 状态栈中处在栈项的状态是语法分析程序开始处理此规则之前的状态。使用弹出之后的状态 和规则左边的符号，将获得一个新状态( 查状态转换表即g o t o 表得到) 。将此新状态压入栈， 语法分析继续。 处理左边符号和普通的单词移进是有明显的不同的。把对左边符号的移进动作叫做状 态转换动作( g o t oa c t i o n ) ，尤其不同的是，当执行移进时，向前看字符是被清除的，但在执 行状态转换动作时，向前看字符是不受影响的。 ( 事实上，归约动作在语法分析过程中好像是时间倒转，将状态从栈中弹出回到规则 右边刚开始看到时的状态。当一条规则被识别时，语法分析程序好似在那时看n t 规则的左 边。) 如果规则的右边是空的，没有状态被弹出栈，也就是栈中被显露出来的状态就是栈中的 当前状态。 归约在处理用户提供的动作和值时也是重要的。当一条规则被识别并被归约时，在栈 被调整以前，由规则提供的代码( c o d e ) 将被执行。语法分析程序使用两个栈：一个是拥有 状态的栈，即上文提到的栈：另一个是与之并行运行的值栈( v a l u es t a c k ) ，这个栈拥有从词 塑坚盔兰型：兰堂笪堡塞 法分析程序和动作返回的值。当移进时，外部变量y y l a v l 被拷贝到值栈。从川户码( u s e r c o d e ) 返回后，归约被执行。当状态转换动作被执行后，外部变量y y l v a l 被拷贝到值栈。在y a c c 中，用伪变量$ 1 ，$ 2 等来代表值栈的值，而$ s 代表左边非终绢符的值。 另外两个语法动作相对来说比较简单。 接受动作( a c c e p ta c t i o n ) 表明整个输入都已经看到并且匹配语法规则，这个动作只有 当向前看单词是e n d m a r k e r ( 文件结束符，在g c c 中是以e o f 为文件结束符的) 才被采刚， 表明语法分析程序已经成功地完成语法分析工作。 报错动作( e r r o r a c t i o n ) 说明根据规则在某处语法分析程序不能再继续语法分析了。当 输入的单词已经被看到，同时还有向前看字符，但后面不能跟随可导致合法输入的任何东西， 此时语法分析程序报告一个错误，并且试图恢复状况( s i t u a t i o n ) ，试图接着进行语法分析。 ( 二) 语法分析程序y y p a r s e 的主要流程说明，如图2 3 在语法分析过程中，y a c c 语法分析器主要使用两个栈：一个是状态栈，一个是语义值 栈。两套指针：s h o r t + y y s s ，y y s s a ；y y s t y p e + y y v s ，y y v s a 。 1 ) 初始化状态栈的状态和值栈的单词值。y y s t a t e = 0 ：y y e r r s t a t u s = 0 ：y y n e r r s = 0 ： y y c h a r = y y e m p t y ； 初始化栈指针：y y s s p = y y s s - 1 ；y y v s p = y y v s ： 对于其中主要变量的说明：y y c h