理论教育 编译器设计之路:语法制导翻译探索

编译器设计之路:语法制导翻译探索

时间:2023-11-04 理论教育 版权反馈
【摘要】:可以毫不夸张地说,目前所能见到的绝大多数编译器都是基于语法制导翻译实现的。Neo Pascal同样如此,因此,读者有必要了解一下语法制导翻译的相关概念。语法制导翻译就是在上下文无关文法产生式的适当位置插入相应的程序片段,随着语法分析过程的深入,根据每个产生式中的语义子程序进行翻译的方式。语法制导翻译,顾名思义,整个翻译过程是由语法分析器控制的,所有的语义子程序同样是由其驱动的。图4-2 语法制导翻译计算表达式4+2*3的过程

编译器设计之路:语法制导翻译探索

前面,主要讨论了语义分析与IR生成模块的基本任务,本小节将继续深入研究其设计与构造的相关技术。实际上,语义就是语法单位的含义,故脱离了语法空谈语义是没有任何意义的。例如,for(i_1;i<10;i++);语句中三个表达式的含义是完全不同的,其中表达式i<10含有循环的终止条件的语义。但是,如果将这个表达式单独提到for语句之外考虑,该表达式也就不具备循环终止条件的含义了。

由于语义与语法之间存在着一定的关系,很多编译器设计者试图从语法分析器的角度思考语义分析与IR生成模块的设计与构造。经过不断探索,提出一种有效且通用的方案一语法制导翻译(syntax-directed translation)。可以毫不夸张地说,目前所能见到的绝大多数编译器都是基于语法制导翻译实现的。Neo Pascal同样如此,因此,读者有必要了解一下语法制导翻译的相关概念。

语法制导翻译就是在上下文无关文法产生式的适当位置插入相应的程序片段(称为语义子程序或语义动作),随着语法分析过程的深入,根据每个产生式中的语义子程序进行翻译的方式。

例4-1 使用语法制导计算表达式4+2*3的值。

【文法4-1】

978-7-111-32164-4-Chapter04-2.jpg

978-7-111-32164-4-Chapter04-3.jpg

说明:

(1)文法4-1是文法3-10的扩充,在文法3-10的适当位置插入了相应的语义子程序,以实现算术表达式的自动计算。(www.daowen.com)

(2)文法4-1仅应用于常量表达式的计算,暂不考虑变量,所以,文法4-1中将原来文法3-10的I->var产生式删除了。

(3)DataStack、OpStack是两个栈结构,DataStack的元素是常量操作数,OpStack的元素是表达式的运算符。push、pop是入栈和出栈的方法。

(4)大括号之间的程序段是一个整体元素,即称为语义子程序。为了便于讲解,为每个语义子程序进行了编号。如果某些大括号的编号相同,表示其语义子程序完全相同。计算过程如图4-2所示。

实际上,语法分析扫描输入单词流的过程就是顺序阅读输入源程序的过程,而语义子程序就是在阅读到特定位置时需执行的动作或者需完成的工作。语法制导的实现并不复杂,也不存在太多的理论基础。这可能就是语法制导能够被广泛应用于编译器设计的主要原因,即使它不是一个完备形式系统。

语法制导翻译,顾名思义,整个翻译过程是由语法分析器控制的,所有的语义子程序同样是由其驱动的。因此,不同的语法分析方法对语义子程序的要求也是完全不同的。通常,自上而下的语法分析是一个从全局到局部的分析过程,而自下而上的语法分析是一个从局部到全局的分析过程。当然,两者各有特点,也都存在不足。国内编译原理教材大多数都是以后者的语义子程序为例讲解的。不过,笔者更倾向于前者,觉得此方法更适合手工构造。

978-7-111-32164-4-Chapter04-4.jpg

图4-2 语法制导翻译计算表达式4+2*3的过程

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

我要反馈