理论教育 实现编译器表达式翻译-编译器设计之路

实现编译器表达式翻译-编译器设计之路

时间:2023-11-04 理论教育 版权反馈
【摘要】:第33行:判断两个操作数是否都是常量,如果都是常量,则进行常量折叠,否则进行表达式翻译。第44、45行:调用OpVarSemantic完成表达式翻译。程序6-7 semantic.cpp理解了类型系统表m_iVarProcessId属性的含义及其相应的语义动作后,分析表达式翻译函数OpVarSemantic的源代码就变得非常容易了。

实现编译器表达式翻译-编译器设计之路

这里,先简单讨论一下Neo Pascal表达式翻译的相关数据结构。先前提到的翻译模型主要涉及两个栈结构,即操作数栈、运算符栈。声明形式如下:

【声明6-6】

978-7-111-32164-4-Chapter06-24.jpg

Operation栈的元素就是运算符的ID,所以其类型就是int。这两个栈结构比较简单,不再多作解释。下面,笔者来解释各语义子程序主要功能,以便读者理解和阅读源代码

978-7-111-32164-4-Chapter06-25.jpg

本小节只介绍前4个子程序的实现,而semantic060、semantic053、semantic096与semantic097将在后续章节中讨论。

程序6-4 semantic.cpp

978-7-111-32164-4-Chapter06-26.jpg

978-7-111-32164-4-Chapter06-27.jpg

semantic050获得当前单词的ID(即运算符的ID),并将其压入Operation栈。除了“@”运算符外,其他运算符都必须由semantic050压入Operation栈,并无需区分是单目运算符还是双目运算符。

程序6-5 semantic.cpp

978-7-111-32164-4-Chapter06-28.jpg

semantic049的功能就是为常量操作数生成一个OpInfo的实例,并将其压入Operand栈供翻译表达式使用。设置m_iType属性为OpInfo::CONST表示这个操作数是常量操作数。当然,其m_iLink属性的值就是该常量符号在常量信息表中的位序号,即指向该常量符号的指针。m_bRef标志对于常量操作数是没有任何意义的。

程序6-6 semantic.cpp

978-7-111-32164-4-Chapter06-29.jpg

978-7-111-32164-4-Chapter06-30.jpg

第6~29行:从Operand、Operation栈获取第一、二操作数及运算符。这个过程是比较简单的,读者只需注意以下两个要点:第一,操作数的顺序。由于栈的特性,所以先出栈的元素是第二操作数,后出栈的元素才是第一操作数。第二,栈访问的安全性。这里笔者进行了严格的栈空检查。有些读者可能会有疑问,这里的三个栈空检查是否有必要?从理论上来说,确实可以省略这三个栈空检查,因为语法分析器完全有能力保证栈访问的安全性。不过,这并不是一种良好的编程习惯,所以笔者不推荐使用。

第30行:根据第一、二操作数类型及运算符ID,调用TypeCompatible函数检索类型系统表。当TypeCompatible函数返回一l时,则表示两个操作数在给定运算符环境下是不相容的。当TypeCompatible函数返回大于或等于0的值时,则表示两个操作数在给定运算符环境下是相容的,且给出了相应的翻译规则。所谓“翻译规则”就是指类型系统表的一个表项。前面已经详细解释了类型系统表的相关结构与声明,不再赘述。

第33行:判断两个操作数是否都是常量,如果都是常量,则进行常量折叠,否则进行表达式翻译。由于前面已经检查了操作数的相容性,所以这里并不需要额外判断。

第35、36行:调用OpConstSemantic完成常量折叠。这里,只需将两个操作数、类型系统表表项的m_iProcessId属性和m_iRsltType属性作为参数传递给OpConstSemantic函数即可。关于OpConstSemantic函数的详细实现稍后分析。

第41--43行:申请一个临时变量用以存储表达式的计算结果,而临时变量的类型由类型系统表表项的m_iRsltType属性决定。值得注意的是,C、Pascal的表达式都比较简单,其计算结果类型只可能是基本类型,而不可能是复杂类型(数组、结构等),故m_iRsltType属性足以描述结果类型。不过,在C++等面向对象语言中,允许表达式的结果类型是复杂类型甚至类,因此推断结果类型可能会复杂一些。

第44、45行:调用OpVarSemantic完成表达式翻译。将两个操作数、运算符及类型系统表表项、结果操作数作为参数传递给OpConstSemantic函数即可,生成IR的工作由OpVarSemantic函数完成。关于OpVarSemantic函数的详细实现稍后分析。

下面,再来看看OpVarSemantic、OpConstSemantic的实现细节。

如果操作数满足常量折叠的要求,则调用OpConstSemantic函数计算操作结果,否则调用OpVarSemantic函数生成计算的IR。当表达式的操作数不都为常量时,也就无法进行常量折叠。OpVarSemantic的设计思想非常简单,即根据类型系统表表项的相关描述生成相应的IR。简言之,就是根据类型系统表表项的m_iVarProcessId属性,完成相应的语义动作。在Neo Pascal的类型系统表中,一共设置了5种语义动作,分别以编号1~5标识。由于实际的Neo Pascal类型系统表规模太大,笔者仅截取了其中数行表项为例,见表6-3。

表6-3 Neo Pascal类型系统表示例

978-7-111-32164-4-Chapter06-31.jpg

注意,为了便于阅读,这里给出的类型系统表是未经编码的,并且直接以字段的中文含义标识列名。其中,变量操作码即为m_iVarProcessId属性。下面,就针对这5种语义动作逐一解释,如表6-4所示。

表6-4 变量操作码对应的语义动作

978-7-111-32164-4-Chapter06-32.jpg

(续)

978-7-111-32164-4-Chapter06-33.jpg(www.daowen.com)

无论是双目运算表达式,还是单目运算表达式,都是由OpVarSemantic函数生成IR的,而生成IR的依据就是类型系统表。下面,再来看OpVarSemantic函数的源代码实现。

程序6-7 semantic.cpp

978-7-111-32164-4-Chapter06-34.jpg

978-7-111-32164-4-Chapter06-35.jpg

理解了类型系统表m_iVarProcessId属性的含义及其相应的语义动作后,分析表达式翻译函数OpVarSemantic的源代码就变得非常容易了。详细的源代码注释似乎已经没什么意义了,这里,笔者只想对其中的SymbolTbl.GetTmpVar函数稍作解释。

在OpVarSemantic函数中,调用了一个SymbolTbl.GetTmpVar函数。不过,这个函数是GetTmpVar的另一种重载形式,它的第2个参数的类型是OpType(即IR操作符)。根据这个OpType类型的参数,函数得到相应的类型信息,并以此类型信息申请临时变量。注意,函数对第2个参数是有一定限制的,必须是NPIR中类型转换相关操作符,因为只有这类操作符才包括类型信息,例如,ChrToStr、ByteToInt等。获得了临时变量的类型信息后,函数就按照标准的申请流程完成临时变量的申请即可。由于相关源代码比较简单,就不再详细列出。

下面,再来谈谈常量折叠的相关实现。这里的常量折叠的基本思想与表达式翻译是比较类似的,它也是基于类型系统表完成的,只不过它需要处理的分支情况要多得多。在Neo Pascal表达式分析过程中,合法的常量折叠情形一共有47种。不过,这47种分支的工作流程都是同样的,即根据运算符及不同类型的操作数,由编译器在编译阶段计算结果,并将结果压入Operand栈,常量折叠的过程并不生成任何IR。

程序6-8 Semantic.cpp

978-7-111-32164-4-Chapter06-36.jpg

978-7-111-32164-4-Chapter06-37.jpg

978-7-111-32164-4-Chapter06-38.jpg

978-7-111-32164-4-Chapter06-39.jpg

978-7-111-32164-4-Chapter06-40.jpg

978-7-111-32164-4-Chapter06-41.jpg

978-7-111-32164-4-Chapter06-42.jpg

978-7-111-32164-4-Chapter06-43.jpg

978-7-111-32164-4-Chapter06-44.jpg

由于类型的存在,常量折叠的问题就有许多复杂变化。笔者将常量折叠的核心语义动作从OpConstSemantic函数中抽象出来了,即建立了OpConstFold函数。其目的就是为了使OpConstFold函数可以被优化阶段相关算法复用。虽然OpConstFold函数规模比较庞大,但是逻辑却比较简单。读者阅读相关源代码时,只需把握以下两个要点即可:

(1)分支情景。了解分支设置的意义及其所处理的代码情景是理解源码的前提,笔者已作了详细的注释说明。

(2)常量的形式。读者应该了解各种类型的常量在常量信息表中的表示形式,即ConstInfo对象各属性的取值情况,如表6-5所示,同时,还需注意以下两点:

1)整型常量的值可以从m_fVal和m_iVal属性获取,这样可以使OpConstFold函数节省许多判断。

2)Pascal语言中唯一的指针常量就是nil。

表6-5 常量的值域属性

978-7-111-32164-4-Chapter06-45.jpg

最后看看单目运算表达式的语义子程序semantic052的实现细节。

程序6-9 Semantic.cpp

978-7-111-32164-4-Chapter06-46.jpg

978-7-111-32164-4-Chapter06-47.jpg

semantic052的主要工作就是完成单目运算表达式的翻译与处理。由于semantic052源代码的实现与semantic051是非常类似的,所以不再详细分析。这里,笔者只想谈一个关于单目运算符“+”(正号)的小问题。“+”是一个比较特殊的运算符,无论是表达式翻译,还是常量折叠,编译器都不需要为此作任何处理或生成任何IR。当然,更不可以产生类似“+一i等于i”的常识性错误。

至此,笔者已经详细介绍了表达式处理的相关实现,包括表达式翻译及常量折叠两个部分。表达式处理的程序并不庞大,结构也比较简单,应该不难理解。由于Neo Pascal的表达式处理完全是基于庞大的类型系统表实现的,所以读者应该紧密结合类型系统表阅读相关源代码,否则,一切都是没有意义的。类型系统的设计方案也并不唯一,类型系统表只是一种易于实现、便于理解的方式。而这种方式的缺点就是二维表的结构需要耗费一定存储空间,处理效率不高。对于一些类型系统复杂的语言来说,构建类型系统表可能是一项极其庞大与惊人的工程,这是Neo Pascal甚至C语言都无法比拟的。在这种情况下,就应该考虑采用一些更为高效的算法。

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

我要反馈