理论教育 操作数翻译基础编译器设计之路

操作数翻译基础编译器设计之路

时间:2023-11-04 理论教育 版权反馈
【摘要】:与表达式翻译类似,操作数翻译同样是基于语法机制实现的。因此,操作数的形式将是设计语义子程序的重要依据。操作数相关的文法形式如下:从文法来说,可以将操作数分为五种基本形式:简单变量操作数:操作数中没有任何界符,也就是直接使用变量名来表示一个操作数,例如a、b等。操作数的类型是语义子程序内部逻辑所关注的元素。

操作数翻译基础编译器设计之路

与表达式翻译类似,操作数翻译同样是基于语法机制实现的。因此,操作数的形式将是设计语义子程序的重要依据。在本小节中,略过类型不谈,而从操作数的形式入手讨论一般化的操作数翻译。操作数相关的文法形式如下:

【文法6-2】

从文法来说,可以将操作数分为五种基本形式:

(1)简单变量操作数:操作数中没有任何界符,也就是直接使用变量名来表示一个操作数,例如a、b等。注意,这里所说的“简单变量操作数”并不一定是简单类型的变量。在进行操作数翻译时,可能更多关注的是操作数的形式,而不是操作数的类型。这是因为语法推导的过程及语义子程序调用的顺序并不是由操作数的类型决定的,而是取决于操作数的形式。当然,这并不意味着操作数的类型没有意义。操作数的类型是语义子程序内部逻辑所关注的元素。简单变量操作数的语义处理比较容易,只需将OpInfo对象的m_iLink属性指向变量信息表中相应的表项,并正确设置其他相关属性即可。

(2)记录字段操作数:操作数中包含界符“.”,也就是使用记录类型变量的某一个字段作为一个操作数,例如,house.address、house.tel等。众所周知,记录字段相对于首地址的偏移是常量。当然,偏移的值可能会因为记录的存储布局而变化,甚至出现一些令人费解的情形。不过,有一点应该是无可争议的,那就是偏移的值必定是一个常量。当然,在处理记录字段操作数时,不能忽略多级字段操作数的形式,例如,house.address.road。根据实际语义,多级字段操作数的地址相对于记录类型变量首地址的偏量同样是一个常量。

(3)数组元素操作数:操作数中包含界符“[],,,也就是使用数组类型变量的某一个元素作为一个操作数,例如,source[i]、class[2]等。传统的数组都是顺序存储的,所以数组元素的地址通常可以被描述成相对于首地址的偏移。不过,与记录字段不同,这个偏移量可能是常量,也可能是变量,这是取决于数组元素的下标形式。数组元素操作数的语义处理比较复杂,由于可能存在变量偏移的情况,所以编译器就需要生成IR来计算相应的偏移。

(4)指针目标操作数:操作数中包含界符“^,’,也就是将指针指向的目标元素作为一个操作数,例如,aa^,aa.bb^等。指针目标操作数本身并不需要处理偏移量。它的语义处理比较简单,实际上,就是一次间接寻址的过程,只需正确设置m_bRef属性即可。不过,在处理指针时,一定不能忽略左值的问题。在任何支持指针的语言中,指针运算的对象通常只能是左值变量。因此,左值判断是非常必要的。

(5)函数返回值操作数:在Pascal、C等语言中,函数返回值也可以直接作为表达式的操作数。值得注意的是:标准Pascal规定,程序员调用过程或函数时,“()”只能在参数列表非空的情况下运用。也就是说,调用无参过程或函数时,只需引用过程或函数名即可。不过,随着“@”运算符的引入,就不得不解决一个二义性的问题。例如:

这是一个合法的Pascal程序。主程序中两个赋值语句的右部都为@a,但它们的语义却是完全不同的。对于语义分析来说,这种情况是非常不利的。显然,表达式“@a”本身的语义并不唯一,它依赖于赋值号左边对象的类型。从语言实现的角度而言,这种机制也将给编译器设计带来不小的麻烦。实践证明,这种得不偿失的做法并没有得到大多数语言设计者的认可。在设计C语言时,Ritchie很好地解决了这一问题。因为C语言的函数调用语句必须加“()”,即使无参函数也是如此。这样,就避免了类似的二义性问题。开源编译器Free Pascal就参考了C语言的实现,提出了类似的修改方案,规定调用过程或函数时必须加“()”。为了避免二义性,便于编译器的实现,Neo Pascal同样采用了这个方案。

以上简单说明了五种操作数形式,这是讨论操作数语义处理及翻译的基础。关于操作数的概念、分类都没有非常明确的定论,所以笔者给出的操作数分类名仅适用于本书。另外,再次强调,在进行操作数语义处理时,区分操作数形式是比较重要的,因为翻译操作数的语义动作与其文法形式是密切相关的。了解了操作数的形式后,就来讨论操作数翻译的一般化过程。

读者已经知道了,操作数翻译与表达式翻译的接口就是Operand栈。前者借助于Operand栈向后者传递信息,而后者则根据表达式的语义生成相应的IR。然而,这里主要关注的是生成OpInfo对象的过程。

在讨论翻译过程之前,有一个概念需要明确:即使语法分析器选用“因子一变量”这个产生式进行后续推导,也并不意味着当前标识符必定是变量名或者函数名。事实上,很多语言都提供了一种符号常量机制,例如Pascal中的“CONST”为首的相关声明。虽然符号常量的形式与简单变量比较类似,但是它的语义处理却与普通的常量无异。如果当前标识符是符号常量名,那么“[]”或“.”运算对于符号常量都是没有任何意义的。处理符号常量操作数的过程比较简单,编译器只需为其生成一个OpInfo对象,将相应的m_iType属性设为OpInfo::Const,并压入Operand栈即可。

下面重点讨论变量操作数的语义处理过程。

处理变量操作数的关键就在于如何计算偏移量。针对不同形式的变量操作数,区别常量偏移、变量偏移是极其重要的。由于变量偏移依赖运行时刻的状态,所以,对于变量偏移来说,编译器只能通过生成相应的目标代码来实现偏移量的计算。至于如何生成更优的IR或目标代码,则完全是代码优化问题。

不过,常量偏移的情况就有些不同了。在语义分析过程中,常量偏移的计算完全是由编译器完成的。当然,生成精简且高效的IR就是编译器设计者关注的。这里,笔者先给出一个简单的例子:

根据先前讨论的结论可知,house.address.road的偏移必定是一个常量偏移。当然,也可以非常容易地得到这个常量偏移的值即为8。当运用相关文法推导“house.address.road”时,就不难发现semantic056将被两次调用,分别用于处理address与road字段。换句话说,如果不考虑效率,编译器可能得到如下的IR序列:(www.daowen.com)

从语义上来说,这样的IR序列是完全正确的,确实也足以精确描述整个寻址的过程。不过,这个结果却是不可接受的。实际上,在本例中,生成计算address字段偏移的IR完全没有意义。本例只需直接计算得到road字段的偏移量8,并生成相应的IR即可。当然,有些读者认为编译器可以借助优化算法将后两句IR合并。虽然笔者也承认优化算法可以解决这个问题,但并不推荐这种实现。理由非常简单,任何优化算法都只能处理某种或某几种代码情况,不可能以不变应万变,应对任意代码情景。由于编译器自动生成IR的随意性较大,设计一个能在任意代码情景中将后两句IR合并的算法可能需要付出较大的代价,所以其可行性较差。然而,在操作数翻译过程中,要实现这个目标就比较容易了。

在前面例子中,生成冗余的IR的主要原因就是没有完成常量偏移的折叠,而是直接生成IR输出。解决这个问题的关键就是如何在语义分析过程中完成常量偏移的折叠。为了便于讲解,笔者暂且将翻译操作数得到的IR序列分成两个部分:偏移计算部分、操作数寻址部分。顾名思义,偏移计算部分就是专门用于计算操作数偏移的IR序列。而操作数寻址部分就是指那些用于获取首地址及计算操作数逻辑地址的IR序列。

所谓的“操作数寻址部分”的IR序列主要指的就是两条指令,即获取首地址的IR指令、首地址与偏移相加的IR指令。当然,如果偏移为常量0时,编译器就不需要生成第二条IR指令了。因此,试图优化操作数寻址部分的IR可能是徒劳的。

然而,“偏移计算部分”的IR序列的情况就比较复杂了,同时,它也为代码的优化创造了条件。如果完全按照语义生成IR,就可能得到类似于上例中的冗余结果。实际上,编译器在生成“偏移计算部分”时,需要解决的核心问题就是常量偏移的折叠。

翻译操作数的基本思想大致如下:可以将生成操作数寻址IR的动作置于semantic053中,即在分析完整个操作数之后,再生成操作数寻址IR。因此,编译器就不得不借助于一个暂存结构,跟踪偏移量的变化情况,并予以记录。在此过程中,遵循常量偏移折叠的原则,尽可能将常量偏移在暂存结构中合并,直到出现变量偏移为止。当然,自出现变量偏移之后,就不必再考虑后续更复杂的常量偏移折叠的情况。例如,b[i].a.p[3],实际上,“.a.p[3]”相对于“b[i]”也是一个常量偏移。不过,由于i是一个变量,所以b[i]相对于b就是一个变量偏移。基于b[i]继续讨论常量偏移折叠可能复杂一些,故后续出现的常量偏移折叠就不予考虑了。具体的源码实现,请读者参考后续章节。

最后,笔者给出一个重要的数据结构,就是先前提及的“暂存结构”。暂存结构的设计是比较重要的,必须既能满足操作数翻译的实际需要,结构也不能过于复杂。在Neo Pascal中,该暂存结构的声明形式如下:

【声明6-7】

m_VarTypeStack:操作数类型栈,主要用于跟踪操作数分析过程中类型信息的变化情况。这是一个非常重要的字段,因为操作数类型分析的结果将直接影响编译的正确性。

m_iVarLink:所属变量信息。由于Var结构只处理变量操作数,所以有必要将所属变量的指针暂存。实际上,这个字段对于编译器获取变量首地址信息是非常有用的。

m_eOffsetType:操作数的偏移类型,这是一个枚举类型的字段。该枚举类型的允许取值分别为ConstOffset(常量偏移)、VarOffset(变量偏移)、NoneOffset(无偏移)。

m_iOffsetLink:操作数的偏移指针。根据m_eOffsetType的取值,该字段的含义是不同的。当m_eOffsetType的值为ConstOffset时,m_iOffsetLink中存储的是常量在常量信息表中的位序。当m_eOffsetType的值为VarOffset时,m_iOffsetLink中存储的是变量在变量信息表中的位序。当m_eOfffsetType的值为NoneOffset时,m_iOffsetType是没有意义的。

m_iDim:数组维度信息。在分析当前操作数时,该字段主要用于记录当前正在分析数组的维度信息,详细实现将在后续章节中讨论。

m_bRef:引用寻址标志。

当然,在语义分析过程中,还需要考虑操作数嵌入引用的情况,例如,a[b.c].p等。因此,暂存结构实际上是一个栈式结构,用于跟踪整个操作数的分析过程。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈