[科普中国]-通用编译程序

简介

顾名思义, 编译程序是一种具有编撰与翻译功能的程序。一个完整的编译程序, 再小也包括三个方面的内容: 词法分析、语法分析和语义翻译。

人类要用计算机来解决问题, 首先面临的一个问题, 就是要告诉计算机解决什么问题, 或许还要告诉计算机如何解决这个问题。这就牵涉到用什么样的语言来描述的问题。人所习惯的语言与计算机的基本语言( 机器指令) 有很大的差别, 用机器指令来描述人想解决的问题十分不便。因而, 计算机科学家设计一些比较习惯的语言来描述要解决的问题。这种语言, 因为面向与接近人的自然语言, 表达力强, 易于使用, 易于为人理解与接受, 称为高级程序语言。相反, 能被计算机直接理解与执行的语言, 即机器指令, 却不易被人们理解与接受, 因而被称为低级机器语言。不管用什么语言来表达的对问题的描述, 通常都称为程序。例如, FORTRAN 语言, ALGOL 60 语言, PASCAL 语言, C语言, ADA语言, C++ 语言等都是高级程序设计语言。

各种机器的机器语言及其相应的汇编语言, 都是低级程序设计语言. 用高级语言写的程序, 不能直接被计算机理解与执行, 必须经过等价的转换, 变成机器能理解与执行的机器语言的程序。进行这种等价转换的工作, 就是编译程序的任务。一般地说, 编译程序就是这样一种程序, 它将用一种语言写的程序, 等价地转换为另一种语言写的程序。因此,它也叫翻译程序。前一个程序, 即被翻译的程序, 叫源程序; 后一个程序, 即翻译成的程序,叫目的程序或目标程序。

因此, 翻译程序与编译程序这两个名词并无大的区别。但是, 通常把从高级语言写的源程序到机器语言表示的目标程序的转换程序称为编译程序。而把从一种语言写的源程序到另一种语言写的目标程序的转换程序称作翻译程序。例如, 从ADA 语言到C 语言的转换, 从ADA 语言到PASCAL 语言的转换, 从C 语言到ADA 语言的转换都是翻译程序。1

通用结构编译程序的内部结构及组织方式虽是五花八门, 变化多端。但是, 万变不离其宗, 其主要工作有两大部分: 分析与综合。所谓分析, 即对被编译的源程序进行分析; 所谓综合, 是在分析正确无误之后, 综合出可以执行的机器语言程序, 执行的结果应正确无误, 同源程序应达到的目的完全一致。

现代编译程序都是语法制导的, 也就是说, 编译的过程由源程序的语法结构来控制,而语法结构通常由语法分析器( 程序) 来识别。语法分析器读入词法分析器输出的单词流,并由此建立源程序的语法结构。词法分析器逐一读入源程序的字符, 分析字符流的词法结构, 组成一个个的单词, 如标识符、数、运算符等。语法结构的识别是分析部分的主要内容。根据程序的语法结构, 语义分析器分析程序的语义( 意义) 。语义分析器包含许多语义子程序, 在识别一种语法结构时, 就调用与此结构相关的语义子程序, 对附于该语法结构上的短语作语义检查, 如一致性检查与作用域分析, 确定其意义, 综合出各程序部分的中间语言表示( IR) 或目标代码。如果产生了IR, 它作为代码生成器的输入, 由此生成所需的机器语言程序。在语义分析器与代码生成器之间, 可以夹一层优化, 它改变IR 序列, 使其可以由此产生高效的代码, 又与源程序的执行结果一致。一个编辑程序基本上就由这些部件组成。1

词法分析源程序可以简单地被看成是一个多行的字符串。词法分析器逐一从前到后( 从左到右) 读入字符, 按照源语言规定的词法规则, 拼写出一个一个的单词( TOKEN) 。此后, 编译程序就把单词当作源语言的最小单位。

语法分析源语言的语法由以产生式为主体的上下文无关文法描述, 据此, 语法分析器读入单词, 将它们组合成按产生式规定的词组( 短语) 。例如, 根据赋值语句的产生式：

〈赋值语句〉→〈变量〉∶ =〈表达式〉

及〈表达式〉的产生式：

〈表达式〉→〈表达式〉+〈项〉

〈表达式〉→〈项〉

〈项〉→〈项〉*〈因式〉

〈项〉→〈因式〉

〈因式〉→标识符

〈因式〉→数

每个产生式都有形式: 左部→右部。左部只有一个符号, 叫非终结符, 表示一个语法单位。右部是由非终结符与终结符组成的串。只在右部出现的符号叫终结符。非终结符即可在左部又可在右部中出现。

在语法分析中, 如果源程序没有语法错, 就能正确地画出其分析树, 否则, 就指出语法错, 给出相应的诊断信息。

语义分析语义分析阶段主要检查源程序是否包含语义错误, 并收集类型信息供后面的代码生成阶段使用。只有语法、语义正确的源程序才可被翻译成正确的目标代码。语义分析的一个重要内容是类型检查。定义一种类型一般包含两个方面的内容, 类型的载体及其上的操作。例如, 整型是容纳整数的空间及定义在存于此空间上的整数的操作的统一体。这个空间是32 位或64 位的字, 操作是+ 、- 、* 、/ 等32 位或64 位整数操作。因此, 每个操作符( 运算符) 的操作数都必须符合源语言的规定。例如, 有的程序语言要求整数加法只施用于两个整数, 有的程序语言允许将实数自动转换为整数并进行整数加。有的程序语言把做数组下标用的实数视为一个错误并作出错报告。对表达式及语句中的对象作类型检查与分析, 是语义分析的重要内容。

在确认源程序的语法与语义( 类型一致性) 之后, 就可以对其进行翻译, 改变源程序的内部表示, 使其逐步变成可在目标机上运行的目标代码。

经过类型一致性检查之后, 有的编译程序把源程序转换为明显的中间语言表示。不妨把这种中间语言表示看成是一种抽象机的程序。一般地说, 这种中间表示应有两个重要的性质: 易于产生; 易于译成目标程序。产生中间语言表示的工作也可以看成是一个独立的编译阶段, 也可以看成是语义分析阶段的一部分工作, 即把类型一致性检查看成静态语义分析, 产生中间语言表示看成是动态语义分析。

中间语言表示有多种形式，它很像是一台机器的汇编语言, 机器的内存单元的作用同寄存器一样。1

符号表管理在编译过程中, 源程序中的标识符及其各种属性都要记录在符号表中。这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等等。对于过程标识符, 还有参数信息, 包括参数的个数及类型, 实形参结合的方式等等。

符号表是一种含记录的数据结构, 通常一个标识符在符号表中占一个记录, 记录中除了标识符的名字域之外, 还有记录该标识符的属性的域。符号表在编译过程中使用频繁,是影响编译速度的主要因素。因此, 对符号表的组织的要求是存储与查找的效率。在词法分析阶段就可识别出标识符, 因而就可将其填入符号表。但是, 标识符的属性在词法分析时一般不能确定。例如, 在PASCAL 语言程序的声明中:VAR X, Y: REAL标识符在前, 类型在后, 且标识符后不直接跟类型, 因此, 在词法分析看到一个标识符时,其类型还看不到。

在语义分析阶段及其以后, 都要使用标识符的属性, 因此, 都要涉及查询与填表的问题。1

出错处理编译的每个阶段都会发现源程序中的错误。在发现错误之后, 一般要对其有一定的处理措施, 因而编译还可继续进行, 不会一有错误就停止编译工作。

在语法与语义分析阶段, 一般都处理编译中可发现的大部分错误。词法分析中可能发现字符拼写错误, 但单词串违反语言的结构规则( 语法) 的错误要由语法分析阶段来查。在语义分析中, 编译程序进一步查出语法上虽正确但含有无意义的操作的成分, 如两个标识符相加, 一个是数组名, 一个是过程名, 虽然语法上允许, 但语义上不允许。诸如此类的各种错误, 都在相应的阶段进行处理。1

代码优化代码优化的阶段力图提高中间代码的质量, 使之运行速度提高, 经语义分析之后, 对于树表示中的每一内部节点都生成一条指令的直接代码生成算法。

代码优化阶段的设计随编译程序不同而异。进行了大量优化工作的编译程序通常称作“优化编译程序”, 这种编译程序的大部分编译时间都花在这个阶段。但是, 在实用上仍有许多简单有效的优化算法, 能够显著地提高目标程序的运行速度而不明显地降低编译速度。

代码生成编译的最后一个阶段, 生成目标机代码, 通常是可供装配的机器代码或汇编码。在代码生成过程中, 对源程序中使用的变量要分配寄存器或内存单元, 然后, 为每一条中间语言指令选择合适的机器指令, 包括确定机器指令的操作码或编址模式。

程序设计语言、编译程序及计算机设计的关系这三种设计相互依存, 相互影响。程序语言的设计对编译程序设计的影响是显然的。许多新的程序语言的特征对编译程序的设计提出了新的课题。如并行程序设计语言的特征, 就刺激了并行编译技术的发展。ADA 语言的多任务设施, 要求对运行栈的结构作必要的修改, 运行栈结构的变化又对机器指令提出新的要求。程序设计语言的重载特征, 对编译算法也有影响。程序设计语言的信息隐藏要求, 抽象数据类型, 对编译程序技术都是明显的。编译程序技术的进步也强烈地影响着程序语言的设计。

容易编译实现的程序语言, 往往也易学、易读、易懂。相反, 难于实现的语言特征, 也很难为用户掌握。易于实现的语言, 往往在各种机器上都有编译程序。流行广泛的程序语言与编译程序, 自然又是语言设计成功的标志。

一般地说, 可编译的语言是那些在编译时可确定其结构、对象、作用域、类型的语言。这些静态的程序成分对编译程序是很重要的, 在这个前提下, 才能将其完全翻译成具体的目标机器指令。程序语言及其编译程序的设计对计算机设计的影响, 体现在计算机指令集设计的变化。

在过去, 计算机指令组的设计较为面向汇编级程序设计, 因此, 很难产生高质量的目标代码。主要问题是: ① 指令集不统一, 有的操作要在寄存器中做, 有的要在内存中做。寄存器又往往分几类, 每一类又只适合于某种特定类的操作; ② 高级操作太紧密地结合特定语言, 其作用难以发挥。虽然大多数语言都支持分程序结构及动态存储分配, 但是栈式与堆式存储器仍然很难高效地实现。

微程序技术的广泛使用使许多使用最普遍的操作得以用少量甚至一条指令来实现。这种设计形成了一个机器体系CISC。即所谓复杂指令组计算机。

另一个对立的体系是所谓的RISC 体系, 即精简指令组计算机。其基本思想是指令集的体系应当简单。奇怪的是, 这种设计也考虑到编译程序的要求。持这种观点的人认为,程序都是用高级语言书写的, 并由优化的编译程序来编译的。指令的简单性的目的是使编译的工作更加容易, 减少代码生成中可能选择的个数。

但可以说, 它们都考虑到高级语言的执行, 考虑到如何减轻编译程序人员的负担而影响计算机的设计。1

通用数控代码编译系统数控(NC)代码编译指对NC代码进行词法分析、语法分析及语义分析，查出其中存在的错误，并对错误进行相应处理。NC程序编译水平及效率是影响NC加工效率的一项重要因素。目前存在的NC代码编译器多为专用编译器，虽可显著提高NC代码编译效率，但存在开发工作量大、周期长、改进或修补困难及适用面窄等局限性。并对传统NC代码编译技术加以扩展，将代码转换增加到其中，提出系统定制方法，使NC代码编译系统可适用于多种NC系统的代码，即达到通用性要求，可从理论上建立了一个新的NC代码编译模式，该模式可突破传统NC代码编译的缺陷，显著提高NC代码编译效率。

整个编译系统可分为NC代码编译和NC系统定制两大模块。NC代码编译模块的功能是针对给定NC系统，对代码进行词法分析和语法分析，然后将通过检查无误的代码转换为另一指定NC系统的格式。根据其实现功能，可划分为词法分析、语法分析、出错处理和代码转换4个子模块。NC系统定制则提供足够交互功能，使用户可根据具体要求为编译系统添加NC系统特征，以满足编泽多种类型NC代码的需要。系统定制又可分为前后期2个子模块，前期子模块用于实现系统定制中与用户交互部分的功能，后期子模块则用于建立定制系统与NC代码编译之间的联系。系统实现流程见图。