编译器前端回顾(下)

编译器前端的程序主干是字符串的匹配,可真正的目的是翻译,将源代码转换为目标码。若将匹配流程比作骨架,那么翻译方法就是血肉。设计翻译方法,在于解决三个问题:如何表示源代码中的语义?如何表示目标码?如何将源代码到目标代码的翻译步骤添加到程序的主干流程当中?

语义是藏在文字符号本身之上的一种可被解释与理解的特性。比方说,符号>,符号本身只是个开口向左的V,而藏在符号之上的特性是大于,用于体现符号左右两侧的量的大小关系;如果两个连在一起,还表示右移。源代码中藏有的语义可分两类,一类体现了目标码的计算特性,另一类体现了源代码的控制复杂特性。第一类在翻译中会通过不同的形式表示,最终翻译为目标码。第二类在翻译中辅助程序做安全检查和组织目标码结构。体现目标码的计算特性的语句类型有算术表达式、逻辑表达式、比较表达式、函数调用和控制流。体现源代码的控制复杂特性的语句类型主要是类型声明,以及一些附加的限定规则。

在上下文无关文法的框架下,一篇源代码中的字符流,会被转换为文法符号流,语义特性可以作为文法符号的某个属性。语法制导定义中,依据属性对其他符号属性的依赖的不同,将属性分作了两类,继承属性和综合属性。继承属性值的计算依赖于产生式中当前符号左侧的其他文法符号的属性值。综合属性值的计算依赖于产生式中右侧的文法符号的属性值。上下文无关文法通过产生式将源代码映射为了一棵语法分析树,分析树上的结点是文法符号。继承属性值的计算依赖于父结点和兄弟结点的属性值。如果是L属性的语法制导定义,那么规定只依赖于左侧的兄弟结点。综合属性值的计算依赖于孩子结点的属性值。目标码是语法分析树文法结点的主属性,可以表示为综合属性,或者直接依照分析过程生成到文件中或者数组、字符串中。

目标码要运行在解释器上,而解释器的类型是多样的,可能是物理机器,也可能是软件虚拟机,一种语言若要兼容多种运行环境,那么设计一种中间代码能够让前端的程序得以复用。特别是当有M种语言要运行在N种解释器上时,可以让编写编译器的数量从M*N降低到M+N。

中间代码要尽可能地接近解释器上运行的指令。一条指令通常包含一个指令名,可以理解为操作符,以及不超过两个的操作数。如果一条指令有两个操作符,那么一定能够拆成两条指令。如果一条指令有多于两个操作数,那么也一定能够拆成两条以上的指令。比如,函数的调用就是个很好的例子。每个参数都能单独拆成一条单操作数指令,函数调用本身也是一条单操作数指令。这种一个操作符和两个操作数的表示方法称作三地址代码,再考虑到指令本身相对其他指令的序列编号,即地址,也就有了中间代码的四元表示。

三地址码的另一种等价形式是语法树,中间结点是操作符,叶子结点是操作数。如果考虑子表达式的复用,更一般的形式是有向无环图。语法树不同于语法分析树,语法树与三地址码等价,而语法分析树同语法推导的分析过程等价。

在语法制导定义中添加构造语法树的语义动作,伴随符号的匹配和产生式的规约,执行属性求值、语法树的构造与翻译。在产生式中引入表记的技术能够被用来回填无条件跳转指令中缺失的地址信息。设计语义动作可以依据以下的步骤进行:一、找出关联的几个属性;二、找出哪些是综合属性,哪些是继承属性;三、写出该有哪些语义动作;四、确定语义动作的顺序;五、校验。

发布人

jeremy1990

现居北京,就职于亚马逊中国,软件工程师。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注