【从零开始学习计算机科学】编译原理(五)语法制导翻译

发布于:2025-03-14 ⋅ 阅读:(17) ⋅ 点赞:(0)

语法制导翻译

语法表述的是语言的形式,或者说是语言的样子和结构。而程序设计语言中另一方面,是附着在语言结构上的语义;语义揭示了程序本身的涵义、施加于语言结构上的限制、要执行的动作。

语法制导翻译就是如何在语法上绑定语义。语法制导翻译是目前最常用的语义分析技术,具体包括两种标记方法:语法制导定义(Syntax-directed definitions)SDD和语法制导的翻译方案(Syntax-directed translation scheme)SDT。

语法制导定义SDD

语法制导翻译的基本思想是在上下文无关文法的基础上,将语言结构的语义以属性的形式赋予代表此结构的文法符号。其属性的计算以语义规则的形式赋予由文法符号组成的产生式。属性可以代表任何对象:字符串、数字、内存单元或其它对象。

例如,对于文法:

E → \to E 1 E_1 E1+T

E → \to T

T → \to F

F → \to digit

假设F.val、T.val、E.val分别为文法符号F、T、E的属性值。digit.lexval为文法符号digit的属性:当digit为常数时,digit.lexval为在常数表中的入口,当digit为标识符时,digit.lexval为在符号表中的入口

语义规则用来计算与产生式中出现的文法符号相关联的属性的值。在一个语法制导定义中,语法规则中的任一条产生式 A → α A\to\alpha Aα,都有与之相关联的一套语义规则。比如:

E → \to E 1 E_1 E1+T , E.val := E 1 E_1 E1.val + T.val

E → \to T , E.val := T.val

T → \to F , T.val := F.val

F → \to digit , F.val := digit.lexval

为每一个产生式配上语义规则并且在适当的时候执行。即,当归约或推导到某个产生式时,除了按照产生式进行相应的代换之外(语法分析),还要按照所对应的语义规则执行操作,如计算表达式、查填符号表、产生中间代码。

语法树结点N上的非终结符号A的属性可分为两种:

综合属性:只能通过N的子节点或N本身的属性值(一个节点可有多个属性)来定义。语法规则中等号的左边必然为产生式头部。

继承属性:只能通过N的父节点、N本身和N的兄弟结点上的属性值来定义。

在语法分析树中为每个文法符号上加上它们的属性,则称为带注释的语法分析树,简称注释语法分析树。

SDD的求值顺序

对于同时具有继承属性和综合属性的SDD,不能保证有一个顺序来对所有节点上的属性进行求值。例如产生式 A → B A \to B