语法制导翻译及中间代码生成

语法制导翻译及中间代码生成5.1引言词法分析与语法分析仅仅是编译程序的一小部分。在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码，然后再将其翻译为目标代码。

优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件

第2页,共30页，2024年2月25日，星期天5.1引言(续)本章要讨论的中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。

目前常见的中间语言有逆波兰表示、三元式、四元式等等。

遗憾的是，中间代码生成与语言的语义密切相关，而语义的形式化描述是一个非常困难的;存在一种称为语法制导翻译的模式，这种模式实际上是对前后文无关文法的一种扩充。方法:对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。

第3页,共30页，2024年2月25日，星期天5.1引言(续)这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。由此可见，抽象文法符号的具体语义信息，是在与语法分析同步的语义处理过程中获取和加工的。文法符号X的语义信息我们称之为语义属性或简称为属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。

第4页,共30页，2024年2月25日，星期天文法符号及其语义属性例如,文法G[E]:产生式 语义子程序E→E(1)+T {E.Val=E(1).val+T.val;}E→T {E.Val=T.Val;}T→digit {T.Val=digit;}为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语义信息栈

语法分析栈语义分析栈TT.Val+‘+’E……#

第5页,共30页，2024年2月25日，星期天本章内容简介本章，我们首先介绍一种适用于定义语义的一种特殊文法

属性文法，并进一步介绍适用于语义翻译的文法

属性翻译文法的相关知识。在第三小节中我们将介绍几种常见的中间语言;在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术。

第6页,共30页，2024年2月25日，星期天5.2属性文法与属性翻译文法

语法制导翻译方法的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。语义子程序的编写质量决定了语义翻译的准确性和有效性。所以,产生式相应语义子程序的正确性是能够进行正确语义翻译的先决条件。

产生式的语义是由组成该产生式的文法符号的语义所决定的。

我们可将这些语义以“属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种附带有语义属性的前后文无关文法，即属性文法。

第7页,共30页，2024年2月25日，星期天5.2.1语义属性与属性文法

定义5.1

一文法符号的语义性质称为该文法符号的语义属性（Attributes），简称为属性。我们用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质，并可任意指定其取值范围。我们用X.a表示A(X)中的属性a

。

属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。终结符至少有一种属性，即词文。当然，它还可能具有其它属性，例如无符号数123，单词“123”就是它的词文，而其数值以及它的类型（整型）是它的其它两个属性。终结符的属性是其内在性质.

非终结符的属性是从其它符号的属性经计算而得的，即由其它符号的属性定义的。

第8页,共30页，2024年2月25日，星期天属性依赖关系各个文法符号的属性之间，可能存在某种依赖关系，这种依赖关系可用属性规则（语义规则）定义。定义5.2

设p:X0→X1X2…Xn是文法G的一个产生式，则与p相关联的属性规则集R(p)={Xi.a=f(Xk1.ak1,…,Xkm.akm)|Xi.a∈A(Xi)}定义了该产生式所涉及的文法符号之属性的求值规则，它表示：Xi的a属性是由的Xk1的ak1属性，…，的Xkm的akm属性计算而得的。

第9页,共30页，2024年2月25日，星期天综合属性与继承属性定义

5.3

对每个产生式p:X0→X1X2…Xn

，设属性定义性出现的集合为AF(p)={Xi.a|Xi.a=f(Xk1.ak1,…,Xkm.akm)∈ R(p),0≤kj≤n}若Xi是产生式左部的非终结符(即i=0),则称属性Xi.a是综合属性(SynthesizedAttributes);若Xi出现在产生式的右部(即1≤i≤n),则称Xi.a是继承属性（InheritedAttributes）。第10页,共30页，2024年2月25日，星期天加注语法树在语法树中,将每个结点均视为由若干个域组成的结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树（AnnotatedSyntaxTree）或装饰树（DecoratedSyntaxTree书中有错!）。由定义5.3可知：在加注语法树中，一个文法符号X在相应结点的综合属性之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故综合属性的求值在语法树中是按自下而上的方式进行的；X的继承属性之值则由X的父结点和(或)其它兄弟结点来定义,故继承属性的求值将按自上而下的方式进行。第11页,共30页，2024年2月25日，星期天属性文法的定义定义5.4

属性文法AG是一个四元组：AG=(G,A,R,B),其中,G是已简化的CFG;A=∪X∈VA(X)是属性的有限集合;R=∪p∈PR(p)是属性定义规则的有限集;B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件；且同时满足：（1）对G中任意两个不同的文法符号X和Y而言，属性集合A(X)和A(Y)不相交,A(X)∩A(Y)=

（2）在G的任意一个语法树中，对文法符号X的每一次出现，可用于计算X的每个属性之值的规则至多有一条。

第12页,共30页，2024年2月25日，星期天属性文法(续)由定义5.4可知，属性文法实际上就是对前后文无关文法的一种拓广。另外，每个产生式中的任一文法符号的属性计算规则只能是唯一的，且任一文法符号的综合属性集与继承属性集不相交，即AS(X)∩AI(X)=

,其中：AS(X)={X.a|p:XP,X.a

AF(p)}AI(X)={X.a|q:YXP,X.a

AF(q)}第13页,共30页，2024年2月25日，星期天例5.1

简单赋值语句文法的属性文法第14页,共30页，2024年2月25日，星期天第15页,共30页，2024年2月25日，星期天属性文法中的一些限制在属性文法中，由于每个非终结符号的属性都由若干文法符号的属性通过相应的属性规则来定义，所以，就不能排除某文法符号的属性由其自身定义的可能性。为避免这种情况的发生，我们需对属性文法作一定的限制。定义5.5

对于L(G)中每个句子所对应的语法树T，若其每个结点标记符号的所有属性之值均可有效地计算，则称相应属性文法AG是良定义的。此外，若所有条件B(p)均取true值，则称L(G)中的这个句子是正确赋予属性的（或称T是可加注的）。 从定义5.5可以看出，在良定义属性文法的任何语法树中，不会出现属性依赖于自身的现象。

第16页,共30页，2024年2月25日，星期天属性依赖关系定义5.6

对于每个产生式p:X0→X1X2…Xn∈P,直接属性依赖关系由下式给出：

DDP(p)={(Xi.a,Xj.b)|Xj.b=f(…,Xi.a,…)∈R(p)}

若序偶(Xi.a,Xj.b)∈DDP(p)，则称属性Xj.b依赖于属性Xi.a

，记作Xi.a→Xj.b。

显然，若有Xi.a→Xj.b

，则对Xj.b的计值，应在求出Xi.a的值之后进行。但若Xi.a又直接或间接地依赖于Xj.b,则称属性Xi.a和Xj.b是循环依赖的。含有属性循环依赖的属性文法AG，其中的一些属性之值将不能得到有效的计算。

第17页,共30页，2024年2月25日，星期天依赖关系图定义5.7

设T是L(G)中一个句子相应的加注语法树，并设在构造T时使用过产生式p:X0→X1X2…Xn

，对于T中由X0,X1,X2,…,Xn所标记的每个结点，若有

(Xi.a,Xj.b)∈DDP(p),则在树中引一条从到的有向边，由此而得到的树称之为该句子的属性化语法树。 所有这样的有向边构成的集合DT(T)，称为树T上的依赖关系。根据DT(T)所构造的关系图称为依赖关系图（或简称为依赖图）。例如，对于例5.1所给文法下的一个句子x:=y+z，相应属性化语法树的依赖关系如P191图5-3所示。

第18页,共30页，2024年2月25日，星期天属性文法的良定义性判别有了属性化的语法树及其依赖关系图，我们就可根据图中是否有回路来确定一属性文法是否是良定义的。定理5.1

一个属性文法是良定义的，当且仅当对于它的每棵语法树T，相应的依赖关系图是一个无回路有向图（directedacyclicgraph）。从P191图5-3可以看出，该语法树相应的依赖关系DT(T)未出现回路，通过对其文法的验证，可知该属性文法是良定义的。为便于设计编译程序，实际工作中我们只处理良定义的属性文法。至于有关良定义文法的判定算法，读者可参阅文献18。第19页,共30页，2024年2月25日，星期天5.2.2属性翻译文法

由于属性文法的抽象性和属性定义的任意性，当我们把它用于进行语义翻译时，就会发现仅有属性文法是不够的，须在属性文法的基础上做进一步的工作。首先，我们应对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即要求属性文法是良定义的。其次，我们还应将属性规则改造为计算属性值的语义程序，即将静态的规则改写为可动态执行的语义动作。经过这样的改造后，我们就可得到一种新的文法—属性翻译文法。

第20页,共30页，2024年2月25日，星期天翻译文法的定义定义5.8

在文法产生式右部适当的位置上插入语义动作而得的新文法称为翻译文法或增广文法(AugmentedGrammar)。在一翻译文法中，若每个产生式右部中的全部语义动作均出现在所有文法符号的右边，则称这样的翻译文法为波兰翻译文法。

为了区分文法符号与语义动作，在本书中我们用一对花括号‘{’及‘}’将插入的语义动作括起来（语义动作采用C语言格式书写）。而且，我们还把语义动作视为翻译文法中的一个“符号”，称为动作符号。插入语义动作后，翻译文法产生式的一般形式为：A→(

{statement;})*

∈V*第21页,共30页，2024年2月25日，星期天翻译文法（续）翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统自动执行花括号内指定的语义动作，在执行完该动作之后才继续进行下一步的语法分析。例：Expr→TermExpr’Expr’→+Term{WriteCode(“+”);}Expr’ |

Term→FactorTerm’Term’→*Factor

{WriteCode(“*”);}

Term’ |

Factor→operand

{WriteCode( yytext);}

|(Expr)第22页,共30页，2024年2月25日，星期天递归下降分析中的翻译文法若用递归下降法进行语法分析，则与非终结符号Expr’相对应的递归程序可扩充为：int

Eprim(){if(CurrentToken==‘+’)

if(Term()) {WriteCode(“+”);

if(Eprim())return

1;else

return

0; }

if(CurrentToken==‘)‘||CurrenToken==‘#’)return

1;

else

return

0;}第23页,共30页，2024年2月25日，星期天属性翻译文法的定义定义5.9

属性翻译文法（AttributeTranslationGrammar，简记为ATG）是具有以下性质的翻译文法：1．每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每个属性都有一个允许值的集合（属性的值域，可以是无限集）。2．非终结符和动作符的属性可分为继承属性与综合属性两类。3．继承属性的定义规则为： ①开始符号的继承属性具有指定的初始值；

②对于给定的产生式p:Y→X1X2…Xn∈P,Xi的继承属性值由p中其它符号的属性值进行计算：Xi.a=f(Y.b,Xk1.ak1,…,Xkm.akm)i{k1,…,km}

4．综合属性的定义规则为：①对于给定的产生式p:Y→X1X2…Xn∈P，Y的综合属性值由p中某些符号的属性计算：

Y.u=f(Y.v,Xk1.ak1,…,Xkm.akm)1≦kj≦n；

②对于动作符号，其综合属性值由该动作符的其它属性计算；

③终结符的综合属性具有指定的初始值。

第24页,共30页，2024年2月25日，星期天对属性文法的一些限制定义5.10

一属性翻译文法称为是L-属性的，当且仅当对其中的每个产生式p:A→X1X2…Xn，下面的三个条件成立：1．右部符号Xi(1≦i≦n)的继承属性之值，仅依赖于X1,X2,…,Xi-1的任意属性或A的继承属性；2．左部符号A的综合属性之值仅依赖于A的继承属性或(和)右部符号Xi(1≦i≦n)的任意属性；

3．对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。

第25页,共30页，2024年2月25日，星期天方法符号属性的求值顺序A的继承属性(∈AI(A))；

X1的继承属性(∈AI(X1))；

X1的综合属性(∈AS(X1),进入X1的子树后，返回时求出）；

…

Xn的继承属性(∈AI(Xn))；

Xn的综合属性(∈AS(Xn),进入Xn的子树后,返回时求出）；A的综合属性(∈AS(A),返回到A的上层）。第26页,共30页，2024年2月25日，星期天表达式属性翻译文法例5.2表达式属性翻译文法：⒈Program→

⒉

|{$1=$2=NewName();}Expr {FreeName($0);} ‘;’

Program

⒊Expr→Term

Expr’⒋Expr’→’+’{$1=$2=NewName();}Term{printf(“+, %s,%s,%s\n”,$0,$$,$0);FreeName($0);} Expr’⒌

|

⒍Term→FactorTerm’⒎Term’→’*’{$1=$2=NewName();}Factor

{printf(“*,

%s,%s,%s\n”,$0,$$,$0);FreeName($0);}Term’⒏

|

⒐Factor→Number{printf(“:=,%s,-,%s\n”,yytext,$$);}⒑

|

第27页,共30页，20