第06章 语法制导翻译技术

1S.PO.P语义分析及生成中间代码程序代码生成程序代码优化程序语法分析程序词法分析程序错误处理符号表管理2第六章语法制导翻译技术教学目标要求理解翻译文法的概念理解语法制导翻译和属性翻译文法的含义明确自顶向下和自底向上语法制导翻译的区别和特点36.1翻译文法6.2语法制导翻译6.3自顶向下语法制导翻译6.4属性翻译文法6.5属性文法的自顶向下翻译6.6自底向上语法制导翻译教学内容4第六章语法制导翻译技术编译程序的最终目的是把源程序翻译成目标代码。词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。语义分析和中间代码生成技术：程序语言中间代码目标代码翻译翻译5第六章语法制导翻译技术在对源程序的编译过程中在有语法制导和非语法制导两种翻译方法。语法制导翻译：以语法分析为主导的语义处理。在语法分析的同时，根据文法规则进行语义处理，并生成中间代码或目标代码。非语法制导翻译：翻译方法不依赖于语言的文法规则.实际应用中比较流行的语义分析方法：基于属性文法的语法制导翻译方法6后缀式中缀表示后缀表示a+bab+a+b*cabc*+(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特点1、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值7分别给出下列表达式的后缀表示a+b*(c-d)(a-b)*c+d3.-a+b*(-c+d)4.X:=-(a+b)/(c-d)-(a+b*c)1.abcd-*+2.ab-c*d+3.a-bc-d+*+4.Xab+-cd-/abc*+-:=86.1翻译文法翻译文法：上下文无关文法的推广，在文法规则的右部适当位置加入语义动作得到的。例：中缀表达式翻译成波兰后缀表达式a@a+b@b*c@c@*@+a+b*c输入串abc*+输出结果活动序列@为动作符号标记@+为一个动作符号9由输入文法（中缀算术表达式）构造翻译文法（后缀算术表达式）①E→E+T ②E→T ③T→T*F④T→F⑤F→(E)⑥F→a⑦F→b⑧F→c①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c翻译文法就是在原有的输入文法基础上，在规则右部适当位置加入动作符号所得。10①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c其中：

@+,@*,@a为动作符号。@为动作符号标记，后面为字符串。在本例中，其对应语义子程序的功能是要输出打印动作符号标记后面的字符串。所以：产生式1：E→E+T@+的语义是分析E,+和T，输出+产生式6：F→a@a的语义是分析a，输出a11例：符号串(a+b)*bE=>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(F+T)*F=>(a+T)*F=>(a+F)*F=>(a+b)*F=>(a+b)*b用输入文法推导：ETTF*F(E)E+TTFaFbb12用翻译文法推导得到活动序列(a@a+b@b@+)*b@b@*：E=>T=>T*F@*=>F*F@*=>(E)*F@*=>(E+T@+)*F@*=>(T+T@+)*F@*=>(F+T@+)*F@*=>(a@a+T@+)*F@*=>(a@a+F@+)*F@*=>(a@a+b@b@+)*F@*=>(a@a+b@b@+)*b@b@*ETTF*F(E)E+TTFaFb@*@＋b@b@a@b13下面给出输入文法和翻译文法的概念：输入文法：未插入动作符号时的文法。由输入文法可以通过推导产生输入序列。翻译文法：插入动作符号的文法。由翻译文法可以通过推导产生活动序列。 输入序列 动作序列

14定义

翻译文法是上下文无关文法，其终结符号集由输入符号和动作符号组成。由翻译文法所产生的终结符号串称为活动序列。活动序列：由翻译文法推导出的符号串，由终结符和动作符号组成。●从活动序列中，抽去动作符号，则得输入序列(a+b)*b●从活动序列中，抽去输入序列，则得动作序列，执行动作序列，则完成翻译任务：

@a@b@+@b@*ab+b*

(a@a+b@b@+)*b@b@*15例：翻译文法G(E)={Vn，Vt，P，E}，其中Vn={E,T,F}Vt={a,b,c,+,*,(,),@+,@*,@a,@b,@c}P={E→E+T@+,F→(E),E→T,F→a@a,T→T*F@*,F→b@b,T→F,F→c@c}在高级程序设计语言的翻译中有各种各样的翻译文法，其中的动作符号代表不同的语义动作。符号串翻译文法：若插入文法中的动作符号对应的语义子程序是输出动作符号标记@后的字符串的文法。166.2语法制导翻译例：输入序列：a+b*c活动序列：a@a+b@b*c@c@*@+动作序列：@a@b@c@*@+翻译结果：abc*+语法制导翻译：按翻译文法进行的翻译。给定一输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作的过程。176.2语法制导翻译语法制导翻译的主要思想：在文法的适当位置插入语义动作符号，当按文法分析到动作符号时就调用相应的语义子程序，完成翻译任务。翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。对偶：（输入序列，动作序列）如：(a+b*c,@a@b@c@*@+)是算术表达式翻译文法定义的一个翻译。186.3自顶向下语法制导翻译自顶向下的语法制导翻译：递归下降翻译LL(1)翻译器196.3.1递归下降翻译要求：不能有左递归，头符号集不能相交在适当的位置插入实现动作符号的子程序。①E→E+T@＋②E→T ③T→T*F@*④T→F⑤F→(E)⑥F→i@i消除左递归①E→T｛+T@＋｝② ③T→F｛*F@*｝④⑤F→(E)⑥F→i@i20处理E的递归下降翻译程序流程图E→T｛+T@＋｝

TEINPUTSYM=下一个符号TOUT(“+”)INPUTSYM=‘+’出口YN21处理E的递归下降翻译程序代码E→T｛+T@＋｝

intE(){ intes=0;

es=T(); while(ch==‘+’){ ch=getchar();

es=T();

printf(“+”); } returnes;}TEINPUTSYM=下一个符号TOUT(“+”)INPUTSYM=‘+’出口YN22处理T的递归下降翻译程序流程图T→F｛*F@*｝FTINPUTSYM=下一个符号FOUT(“*”)INPUTSYM=‘*’出口YN23处理T的递归下降翻译程序代码T→F｛*F@*｝FTINPUTSYM=下一个符号FOUT(“*”)INPUTSYM=‘*’出口YNintT(){ intes=0;

es=F(); while(ch==‘*’){ ch=getchar();

es=F();

printf(“*”); } returnes;}24处理F的递归下降翻译程序流程图F→(E)F→i@iEFINPUTSYM=下一个符号

INPUTSYM=‘)’出口YNINPUTSYM=‘(’INPUTSYM=下一个符号

YNINPUTSYM=下一个符号

INPUTSYM=‘i’OUT(i)ERRORERRORN25处理F的递归下降翻译程序代码F→(E)F→i@iintF(){intes=0;

if(ch==‘(’){ ch=getchar();

es=E();

if(ch!=‘)’) return3; else{ ch=getchar(); returnes; }}else{…}｝else{

if(isalpha(ch)){ //判断是否为字母

printf(“%c”,ch); ch=getchar(); returnes; } elsereturn4;}266.3.2LL(1)翻译器考虑下面的输入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D→b输入文法的LL(1)分析表27如果我们在该输入文法的适当地方插入翻译所需要的动作符号，那么，可得到如下的翻译文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D→@sb输入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D→b28翻译文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D→@sb翻译文法的LL(1)分析表29对于翻译文法，动作符号像其它符号一样入栈。但当动作符号处于栈顶时，无论当前的输入符号是什么，都要执行由该动作符号所规定的操作，并将该动作符号从栈顶弹出，且不移动读符号指针。a……栈顶A，当前输入符号a时，操作：A出栈；@zD@yc@xB@wa@v入栈；@v出栈并执行；a出栈；@w出栈并执行。

306.3.2LL(1)翻译器将LL(1)分析扩充为LL(1)语言的翻译器，只需扩充相应分析表的动作部分并具体实现完成每个动作符号的子程序，就可得到翻译文法所确定语言的翻译程序。316.4属性翻译文法在翻译文法的基础上，可以进一步定义属性文法，翻译文法中的符号，包括终结符、非终结符和动作符号均可带有属性，这样能更好的描述和实现编译过程。属性可以分为两种：综合属性继承属性326.4.1综合属性基本操作数带有属性的表达式文法G[E]：

1.

E→E+F 4.

T→F2.

E→T 5.

F→(E)3.

T→T*F 6.

F→iC

此文法能够产生如下的输入序列：（i3

＋i9)*i233根据给定的文法，可写出该输入序列的语法树自底向上的属性计算ET*TFF(E)E+TTFi3i2

Fi9所以，用表示属性计算是自底向上的，称为综合属性。ET*TFF(E)E+TTFi3i2

Fi9339391212122242434

产生式求值规则1.Ep4

→Eq5+Tr2 p4=q5+r2;2.Ep3

→Tq4p3=q4;3.Tp2

→Tq3*Fr1p2=q3*r1;4.Tp2

→Fq2p2=q2;5.Fp1

→(Eq1)p1=q1;6.Fp1

→iq1p1=q1;说明：

p,q,r为属性变量名。属性变量名局部于每个产生式，也可使用不同的名字。

求值规则：综合属性是自底向上求值。为了形式地表示上述表达式的属性求值过程，可以改写上述文法：356.4.2继承属性考虑下列文法：G[<说明>]：1.<说明>→Typeid<变量表>2.<变量表>→，id<变量表>3.<变量表>→ε符号表A整型BC整型其中

Type:类型名（值：int,real,bool等）

id：变量名（值：指向该变量符号表项的指针）上述文法所产生的语句：intA，BC该文法的翻译任务：将声明的变量填入符号表完成该工作的动作符号：@set_table36翻译文法：1.<说明>→Typeid@set_table<变量表>2.<变量表>→，id@set_table<变量表>3.<变量表>→ε填表时需要的信息：类型，名字，以及填的位置如何得到？类型和名字在词法分析时得到，可设两个综合属性。37Typett中放类型值

idn

n中放变量名填表动作符号也可带有属性：

@set_table↓t1，n1

↓t1，n1

可从前面得到，所以称为继承属性，继承前面的值

<变量表>

↓t2↓t2

同上属性翻译文法：1.<说明>→Typetidn@set_table↓t1,n1<变量表>↓t2

t2=t；t1=t；n1=n;

2.<变量表>↓t2

→，idn@set_table↓t1,n1<变量表>↓t3

t3＝t2；t1=t2；n1=n;3.<变量表>↓t2

→

ε38例：inta，bTypeint

idａ

,

idｂ

语法树：

<说明>Typeint

idａ

@set_table↓int,ａ

<变量表>↓int

,idｂ

@set_table↓intｂ

<变量表>↓int

ε继承属性求值：自顶向下综合属性求值：自底向上39

符号表aintbintpintａ，ｂ的分析翻译过程：<说明>Type

intid

a@set_table↓int,a<变量表>↓intType

intida@set_table↓int,a，id

b

@set_table↓int,b+翻译文法：<说明>→Typeid@set_table<变量表><变量表>→，id@set_table<变量表><变量表>→ε406.4.3属性翻译文法定义当翻译文法的符号具有属性，并带有属性求值说明时，就称为属性翻译文法。其具体定义如下：1)文法的每个终结符、非终结符和动作符号都可以有一个有穷的属性集。2)每个非终结符和动作符号属性可分为综合属性和继承属性。3)继承属性的求值规则：①～③4)综合属性的求值规则：①～④41继承属性的求值规则：①~③①开始符号的继承属性具有初始值。②对产生式左部的非终结符，其继承属性则继承前面产生式中该符号已有的继承属性值。③右部的符号，其继承属性由产生式中其它符号属性值进行计算。继承属性求值：自顶向下一个结点的继承属性值是由其父结点或兄弟结点的某些属性决定的42综合属性的求值规则：①~④①对终结符号其综合属性具有指定的初始值。在具体实现中，该初始值将由词法分析程序提供。②产生式右部的非终结符号的综合属性值，则取后面以该非终结符号为产生式左部时求得的综合属性值。③产生式的左部的非终结符号的综合属性值，由产生式中左部或右部的某些符号的属性值进行计算。④给定一动作符号，其综合属性值将用该动作符号的其它属性值进行计算。综合属性求值：自底向上一个结点的综合属性值是其子结点的某些属性来决定的436.5属性文法的自顶向下翻译6.5.1L-属性翻译文法（L-ATG）这是属性翻译文法中较简单的一种。其输入文法要求是LL(1)文法，可用自顶向下分析构造分析器。在分析过程中可进行属性求值。一属性翻译文法称为是L-属性的，对其中的每个产生式A→X1X2…Xn，下面的三个条件成立：①右部符号Xj(1jn)的继承属性之值，仅依赖于X1,X2,…,Xj-1的任意属性或A的继承属性；②左部符号A的综合属性之值仅依赖于A的继承属性或（和）右部符号Xj(1jn)的任意属性；③对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。44①右部符号Xj(1jn)的继承属性之值，仅依赖于X1,X2,…,Xj-1的任意属性或A的继承属性；继承属性求值规则：（1）产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值。（2）产生式右部符号的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。体现自顶向下，自左向右的求值特性。45②左部符号A的综合属性之值仅依赖于A的继承属性或（和）右部符号Xj(1jn)的任意属性；③对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。综合属性求值规则：（1）产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值。（2）产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某个右部符号的属性进行计算。（3）动作符号的综合属性用该符号的继承属性或某个右部符号的属性进行计算。体现自底向上，自右向左的求值特性。46例：A→BC求值顺序：1)A的继承属性（若A为开始符号，则有指定值,否则由上面产生式右部符号的继承属性求得）2)B的继承属性（由A的继承属性求得）3)B的综合属性（由下面产生式中左部符号为B的综合属性求得）4)C的继承属性（由A的继承属性和B的属性求得）5)C的综合属性（由下面产生式中左部符号为C的综合属性求得）6)A的综合属性（由A→BC计算）476.5.2L-属性文法翻译的实现——递归下降翻译方法：对于每个非终结符号都编写一个翻译子程序（过程）。根据该非终结符号具有的属性数目，设置相应的参数。继承属性：声明为赋值形参综合属性：声明为变量形参过程调用语句的实参：继承属性:继承属性值综合属性:属性变量名（传地址，返回时有值）U↓x,y→ProcedureU(x,y);x—赋值形参

y—变量形参‥48关于属性名的约定：1）产生式左部的同名非终结符使用相同的属性名。（递归下降分析法所必须）<L>↑a↓b→e↓I<R>↓J<L>↑x↓y→<H>↓z↑w<S>→I↑a<B>↓b<C>↓cb,c:=a

<S>→I↑x<B>↓x<C>↓x<L>↑x↓y→e↓I<R>↓J<L>↑x↓y→<H>↓z↑w2）具有相同值的属性取相同的