Chapt6-第6章-语法制导翻译技术

第6章语法制导翻译技术Nocross,nocrown.

不经历风雨，怎么见彩虹.6.1翻译文法6.2语法制导翻译6.3自顶向下语法制导翻译6.4属性翻译文法6.5属性文法的自顶向下翻译6.6自底向上语法制导翻译第6章语法制导翻译技术语法制导翻译翻译文法、属性翻译文法及其应用

学习重点第6章语法制导翻译技术语义：是程序设计语言中按语法规那么所构成的各个语法成分的含义。例如以下Test语言代码：{inta;b=a+1;writeb;}一个源程序经历了词法分析与语法分析，说明它在书写上和语法上是正确的，但不能保证其在语义上是正确。语义分析的任务：分析程序的含义，并作相应的语义处理。第6章语法制导翻译技术语义分析的功能

②类型和运算合法性检查：检查运算的合法性与运算分量类型的一致性〔或相容性〕，必要时作相应的类型转换。例如，a+b,要求a和b都是算术型〔整型或实型〕，当a和b不是同一种类型时，需进行类型转换。①确定类型：确定标识符所关联数据对象的数据类型〔有时由词法分析完成〕。③识别含义：确定程序中各构造成分组合到一起的含义，并作相应的语义处理。这时对可执行语句生成中间代码或目标代码。

第6章语法制导翻译技术语义分析的功能

⑤一致性检查：在很多程序设计语言中要求对象只能被说明一次。

④控制流检查：控制流语句必须转移到合法的地方。例如，在C语言中，break语句使得控制跳离包括该语句的while、for或switch语句，如果不存在包括它的这样的语句，那么报告错误。⑥其它语义检查：如对象的作用域等。第6章语法制导翻译技术语义分析的实现

语义分析是以语法分析的输出〔语法分析树或其它等价的内部中间表示〕作为输入，输出那么是中间代码，甚至是目标代码。一般情况下，语义分析仅产生中间代码，即语义分析与目标代码生成分成两遍来进行。第6章语法制导翻译技术语义往往是上下文有关的，只宜于用口语描述，语义形式化很困难。目前，比较流行的语义描述和语义处理方法是语法制导翻译技术。语法制导翻译技术根底：形式描述的属性翻译文法特点：把语法与语义分开，但又在语法分析的同时进行相应的语义工作提高了实用性6.1翻译文法

例:设计一个翻译器，它能将中缀表达式翻译成波兰后缀表达式。假设输入串是a+b*c，那么问题:如何实现这个翻译过程呢？a+b*c翻译器abc*+输入串输出串先看输入串a+b*c的推导过程:中缀表达式文法：①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→cEE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c由推导过程EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c得到输入串的语法树：记住翻译目标是：abc*+EE+TTT*FFEcba添加叶子结点，用@表示输出操作〔输出其后的字符〕。EE+TTT*FFEcba@b@a@c@*@+将@符号的叶子结点从左到右连起来，得到@a@b@c@*@+〔注意:这种带有@的符号串称为动作序列。〕执行这个符号序列，得到abc*+这就是翻译结果!EE+TTT*FFEcbaEE+TTT*FFEcba@b@a@c@*@+问题：如何得到这棵带动作符号的语法树呢？在中缀表达式文法〔输入文法〕的根底上参加动作符号，得到翻译文法。①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c

①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F ⑧F→c@c输入文法翻译文法例用输入文法推导a+b*c的过程如下:EE+TE+T*FE+T*cE+F*cE+b*cT+b*cF+b*ca+b*c

用翻译文法进行相同的推导:EE+T@+E+T*F@*@+E+T*c@c@*@+

E+F*c@c@*@+

E+b@b*c@c@*@+

T+b@b*c@c

@*@+

F+b@b*c@c@*@+

a@a+b@b*c@c@*@+①E→E+T ⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c

①E→E+T@+⑤F→(E)②E→T⑥F→a@a③T→T*F@*⑦F→b@b④T→F ⑧F→c@c输入文法翻译文法输入序列活动序列将活动序列中的输入序列去掉，得到动作序列：@a@b@c@*@+6.1翻译文法

翻译文法是上下文无关文法的推广，是在描述语言文法规那么的右部适当位置参加语义动作得到的。为了区分文法符号与语义动作，在文法的表示中，将代表语义动作的符号前面加动作符号标记@来表示。输入序列：用输入文法通过推导可以得到的终结符号串。活动序列：用翻译文法通过推导得到的符号串。动作序列：从某活动序列中去掉所有输入序列，即由所有动作符号组成的符号串。6.1翻译文法

6.1翻译文法上例的翻译文法可表示成：

G(E)={Vn,Vt,P,E}，其中Vn={E,T,F}Vt={a,b,c,+,*,

@+,@*,@a,@b,@c}

P={E→E+T@+，E→T，T→F，

F→a@a，

T→T*F@*,F→b@b，F→c@c}在高级程序设计语言的翻译中有各种各样的翻译文法，其中的动作符号代表不同的语义动作。在翻译文法中,如果@的动作就是输出其后的符号,可称该文法为符号串翻译文法。符号串翻译文法是翻译文法中的一种特定类型。

6.2语法制导翻译例：根据前面的算术表达式翻译文法，对于输入符号串a+b*c，推导出的活动序列为：a@a+b@b*c@c@*@+其中：a+b*c为输入序列@a@b@c@*@+为动作序列如果执行该动作序列中的动作，那么产生输出序列abc*+，这就是输入序列a+b*c的翻译结果。由于这种翻译结果是通过翻译文法获得的，所以就称为语法制导翻译。语法制导翻译：就是给定一输入序列，根据翻译文法获得翻译该符号串的活动序列，从活动序列中别离出动作符号串，然后执行该动作符号串所规定的动作，从而得到翻译结果。6.2语法制导翻译按语法制导翻译的方法来实现语言的翻译首先要根据输入语言的文法，分析各条产生式的语义，即分析他们要求计算机所完成的操作。分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上，从而实现翻译文法。

6.3自顶向下语法制导翻译自顶向下的语法制导翻译有递归下降翻译和LL(1)翻译。递归下降翻译：递归下降翻译器的实现思路与递归下降分析根本相同，要求也一样，即不能有左递归，头符号集不能相交，只需在适当的位置插入实现动作符号的子程序。6.3自顶向下语法制导翻译例算术表达式翻译文法如下：

E→E+T@+E→TT→T*F@*T→FF→(E)F→i@i注：@为输出其后的符号串。解：去掉文法中的左递归，修改后文法为：

E→T{+T@+}T→F{*F@*}F→(E)|i@i处理E的递归下降翻译程序流程图

处理T的递归下降翻译程序流程图

T→F{*F@*}处理F的递归下降翻译程序流程图

F→(E)|i@i6.3自顶向下语法制导翻译自顶向下的语法制导翻译有递归下降翻译和LL(1)翻译。LL(1)翻译：LL(1)翻译器的实现思路与LL(1)分析法根本相同，要求也一样，即不能有左递归，头符号集不能相交，只需在文法适当的位置插入实现动作符号的子程序，并在LL(1)分析表中参加相应的动作符号。6.3自顶向下语法制导翻译例(P126)考虑下面的输入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D→b

输入文法的LL(1)分析表

设其翻译文法为：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D→@sb6.3自顶向下语法制导翻译翻译文法的LL(1)分析表

注意：对于翻译文法，动作符号像其它符号一样入栈。但当动作符号处于栈顶时，无论当前的输入符号是什么，都要执行由该动作符号所规定的操作，并将该动作符号从栈顶弹出，且不移动读符号指针。

6.3自顶向下语法制导翻译假设翻译器的分析栈的栈顶符号为A，且当前输入符号为a，那么将发生的动作是弹出A，@zD@yc@xB@wa@v入栈。由于此时栈顶为动作符号@v，因此@v出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出v，即out(v)。紧接着，a出栈，读下一个符号c。然后，动作符号@w为栈顶，因此@w出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出w，即out(w)。ac……#A..#@v

a

@w

B..#B..#@v出栈并执行，a出栈，读入c,@w出栈并执行ac……#6.3自顶向下语法制导翻译翻译文法的LL(1)翻译的总控程序总结：1)当翻译器的控制执行程序根据栈顶符号和当前输入符号查该表得到元素为空时，那么转错误处理程序。2)假设控制执行程序识别栈顶符号为动作符号时，不管当前输入符号是什么，将该动作符号从栈中弹出并转相应的子程序以完成所需的翻译〔执行动作〕。对于符号串翻译文法，其语义动作为输出动作符号中的符号串。6.4属性翻译文法引例声明语句文法： ①<声明语句>→TYPEID<变量表>; ②<变量表>→，ID<变量表> ③<变量表>→ε

其中TYPE代表类型，其值可为int或real或bool。

问题：将输入符号串“inta,b;”翻译为:intaintb思考：能否通过在文法产生式右部添加动作符号实现该翻译？6.4属性翻译文法引例声明语句文法： ①<声明语句>→TYPEID<变量表>; ②<变量表>→，ID<变量表> ③<变量表>→ε

其中TYPE代表类型，其值可为int或real或bool。

输入：inta,b;输出：intaintb输入串inta,b;”的推导过程：<声明语句>TYPEID<变量表>;TYPEID，ID<变量表>;TYPEID,ID问题：无法将文法符号TYPE、ID与输入符号int、a、b关联起来！6.4属性翻译文法6.4属性翻译文法

属性：对文法符号引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、代码序列、符号表内容等。属性值可以在语法分析过程中计算和传递。属性一般用标识符表示，通常写在相应文法符号的下边，它的意义局限于它所在的产生式。属性加工的过程就是语义的处理过程。属性的分类综合属性继承属性通常规定，每个文法符号的综合属性和继承属性的交集为空。6.4属性翻译文法

综合属性：综合属性的计算规那么是按“自下而上”方式进行，即文法产生式左部符号的某些属性根据其右部符号的属性和/或自己的其它属性计算而得。在语法树中，如果一个结点的某一属性，其值由子结点的属性值来计算，那么该属性为综合属性。综合属性可用“↑”来表示。对终结符号其综合属性具有指定的初始值,该初始值由词法分析程序提供。例Ap→Xq,rYs,tp=q+s,r=p+t其中，p是综合属性，r不是综合属性，q,s,t不能确定，需参考其它产生式的属性计算规那么才能确定。6.4属性翻译文法

继承属性：继承属性的计算规那么是按“自上而下”方式进行，即文法产生式右部符号的某些属性根据其左部符号的属性和/或右部的其它符号的某些属性计算而得。在语法中，如果一个结点的某一属性，其值由该结点的父结点和/或兄弟结点的属性值来计算，那么该属性为继承属性。继承属性可用“↓”来表示。开始符号的继承属性具有初始值。例Ap→Xq,rYs,tp=q+s,r=p+t

显然，r是继承属性。6.4属性翻译文法例算术表达式的属性翻译文法:①S→E↑q@ANSWER↓r r=q②E↑p→E↑q+T↑r

p=q+r③E↑p→T↑q

p=q④T↑p→T↑q*F↑r

p=q*r⑤T↑p→F↑q

p=q⑥F↑p→(E↑q) p=q⑦F↑p→NUM↑q

p=q

6.4属性翻译文法语义规那么(语义动作或翻译子程序)：为输入文法配备计算属性的计算规那么，称为语义规那么。如上例中，p=q+r就是语义规那么。产生式只能产生符号串，它并未指明所产生的符号串的含义是什么。语义规那么给出了一个产生式所产生的符号串的含义，而且还根据这种含义规定了对应的加工动作。这些加工动作包括查填各类表格、改变编译程序的某些变量的值、打印各种错误信息以及生成中间形式代码等。6.4属性翻译文法属性翻译文法〔或属性文法〕：对于某个压缩的上下文无关文法，当为文法符号引进一组属性，且让该文法中的产生式附加上语义规那么时，称该上下文无关文法为属性翻译文法。6.4属性翻译文法语义分析的翻译过程：步骤1分析输入符号串，建立语法树；步骤2从语法树得到描述结点属性间依赖关系的依赖图，由此依赖图得到语义规那么的计算次序；步骤3进行语义规那么计算，得到翻译结果。语义分析翻译过程的分类：自顶向下的翻译自底向上的翻译6.4属性翻译文法自顶向下的语义分析翻译过程的例如声明语句文法： ①<声明语句>→TYPEID<变量表>; ②<变量表>→，ID<变量表> ③<变量表>→ε

其中TYPE代表类型，其值可为int或real或bool。

属性翻译文法：

1)<声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<变量表t2>

；

t2=t，t1=t，n1=n2)<变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2

>

t2=t，t1=t，n1=n3)<变量表>→ε

其中，过程SET_TYPE输出变量名及其类型。给出输入符号串“inta,b;”的语义分析翻译过程。输入：inta,b;输出：aintbint6.4属性翻译文法声明语句

；ID↑a

TYPE↑int

变量表ID↑b变量表，εinta,b；的语法树

解：输入符号串“inta,b;”的语义分析翻译过程：声明语句

；@SET_TYPE↓n1,t2

ID↑n

TYPE↑t

变量表↓t2

@SET_TYPE↓n1,t1

ID↑n变量表↓t2

，εinta,b；的语法树加入动作符号和属性t2=t，t1=t，n1=nt2=t，t1=t，n1=n6.4属性翻译文法声明语句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int

变量表↓int

@SET_TYPE↓b,int

ID↑b变量表↓int

，εinta,b；的翻译树解：输入符号串“inta,b;”的语义分析翻译过程：输出aintbint声明语句

；@SET_TYPE↓n1,t2

ID↑n

TYPE↑t

变量表↓t2

@SET_TYPE↓n1,t1

ID↑n变量表↓t2

，εinta,b；的语法树加入动作符号和属性t2=t，t1=t，n1=nt2=t，t1=t，n1=n6.4属性翻译文法自底向上的语义分析翻译过程的例如输入算术表达式3+2*3，应输出9，给出输入符号串3+2*3的语义分析翻译过程。①S→E@ANSWER②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→NUM

①S→E↑q@ANSWER↓r r=q②E↑p→E↑q+T↑r

p=q+r③E↑p→T↑q

p=q④T↑p→T↑q*F↑r

p=q*r⑤T↑p→F↑q

p=q⑥F↑p→(E↑q) p=q⑦F↑p→NUM↑q

p=q翻译文法属性翻译文法SET+EF*TTFNUM↑3

FNUM↑2

NUM↑3

3+2*3的语法树

NUM↑3

SE↑9

T↑6

+E↑3

@ANSWER↓9

F↑3

*T↑2

T↑3

F↑3

F↑2

NUM↑2

NUM↑3

3+2*3的翻译树

解：输入符号串3+2*3的语义分析翻译过程：6.4属性翻译文法输出96.4属性翻译文法例设计一个属性翻译文法，要求对于输入的中缀表达式，经过翻译将输出具有下面性质的四元组代码序列∶

输出符号串中的每个双目运算都用一个四元式表示。四元组中的四元式的顺序与执行时要完成的运算顺序相同。每个四元式有四个参数，自左向右的顺序为∶

运算符，左操作数，右操作数，运算结果

例如，翻译器处理表达式a+b将生成如下的四元式∶

ADD,a,b,t1

其中t1是临时变量，保存表达式的结果。翻译器处理表达式a+a*b将生成

MULT,a,b,t1ADD,a,t1,t26.4属性翻译文法解：第一步先设计满足上述要求的翻译文法。翻译文法：E→E+T@ADDE→TT→T*F@MULTT→FF→(E)F→ID

输入文法：E→E+TE→TT→T*FT→FF→(E)F→ID

6.4属性翻译文法属性翻译文法：E↑x→E↑q+T↑r@ADD↓y,z,t

y=q,z=r,t=NEWT，x=tE↑x→T↑p

x=pT↑x→T↑q*F↑r@MULT↓y,z,t

y=q,z=r,t=NEWT，x=tT↑x

→F↑p

x=pF↑x→(E↑p)x=pF↑x

→ID↑p

x=p其中，NEWT是一个函数，每次调用它时返回一个新的临时变量名，临时变量名按产生顺序分别为t1、t2、…等。动作符号@ADD↓y,z,t输出“ADD,y,z,t”，动作符号@MULT↓y,z,t输出“MULT,y,z,t”第二步，构造属性和求值规那么，把翻译文法构造成属性翻译文法。6.4属性翻译文法ID↑a

ET+EF*TTFFID↑a

ID↑b

表达式a+a*b的语法树ID↑a

E↑t2

T↑t1

+E↑a

F↑b

*T↑a

T↑a

F↑a

F↑a

ID↑a

ID↑b

表达式a+a*b的翻译树@MULT↓a,b,t1

@ADD↓a,t1,t2

产生新变量t2，输出：ADD,a,t1,t2产生新变量t1，输出：MULT,a,b,t16.5

属性文法的自顶向下翻译自顶向下的语义分析翻译过程例如---回忆属性翻译文法：

1)<声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<变量表t2>

；

t2=t，t1=t，n1=n2)<变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2

>

t2=t，t1=t，n1=n3)<变量表>→ε

输入符号串“inta,b;”的翻译树如下。声明语句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int变量表↓int

@SET_TYPE↓b,int

ID↑b变量表↓int

，ε属性值依赖于上一级的<变量表>属性值依赖于左边的a和int6.5

属性文法的自顶向下翻译分析按照自顶向下的有序方式对某个属性求值时，应当确保所需要的根本值。我们需要对属性计算规那么设定约束条件！要求文法必须是L-属性文法。6.5

属性文法的自顶向下翻译L-属性翻译文法满足下面三个条件：〔1〕给定一产生式，其右部符号的继承属性值是以左部符号的继承属性或出现在给定符号左边的产生式右部符号的任意属性为变元的函数。〔2〕给定一产生式，其左部符号的综合属性值是以左部符号的继承属性或某个右部符号的任意属性为变元的函数。〔3〕给定一动作符号，其综合属性值是以该动作符号的继承属性为变元的函数。6.5

属性文法的自顶向下翻译例假设文法中有产生式为：A↓I1↑S2,S3→B↓I4C↑S5D↑S6↓I7,I8E↓I9根据L-属性的限制条件，I4=F(I1)、I4=123、I7=G(I1)合法，而I4=H(S2)、I4=K(S6,I4)那么不合法。

例(P134)假设文法中有产生式为：

A↓a1↑a2→B↓b1↑b2C↓c1↑c2A、B和C的属性可以按下面的顺序进行求值∶

1)A的继承属性a1

；2)B的继承属性b1

；

3)B的综合属性b2；4)C的继承属性c1

；

5)C的综合属性c2

；6)A的综合属性a2

。

6.5

属性文法的自顶向下翻译为了进行属性翻译的程序设计，我们采用下述约定：1)产生式中的属性名字用作变量和参数的名字。例：L↑a↓b→E↓iR↓j写成子程序〔函数〕时，表示为：intL(inta,intb){inti,j;…}6.5

属性文法的自顶向下翻译为了进行属性翻译的程序设计，我们采用下述约定：2)所有出现在左部的同名非终结符，应具有相同的属性名表。在左部同名非终结符属性名表的同一化过程中，属性名称的改动范围仅局限于产生式左部。属性重新命名以后，应修改某些属性求值规那么。例产生式L↑a↓b

→E↓iR↓ji,j=b，a=i+2L↑x↓y→H↑z↓ww=y，z=2，x=z+y

按约定2，应改成L↑a↓b→E↓iiR↓ji,j=b，a=i+2L↑a↓b→H↑z↓ww=b，z=2，a=z+b6.5

属性文法的自顶向下翻译为了进行属性翻译的程序设计，我们采用下述约定：3)如果两个属性有相同的值，那么可给它们相同的名字，但对于左部符号的属性值相等时，不能改变成相同的名字。

例对规那么L↓a↑b→aB↓cC↓d,当c,d=a时，可写成:L↓a↑b→aB↓aC↓a但当b=a时，上式不能写成L↓a↑a→aB↓aC↓a这是因为过程L(inta,intb)不可写成L(inta,inta)。6.5

属性文法的自顶向下翻译采用C语言编写L-属性文法递归下降翻译程序时采用的方法：1)形式参数：产生式左部非终结符的属性名表设计成相应过程的形式参数表。继承属性→值形参(即简单变量)

综合属性→指针变量。2)局部变量：在产生式中，与左部属性名不同的属性名变成相应过程的局部变量。3)非终结符的代码：产生式右部的每个非终结符的过程调用，该非终结符的属性作为实参。要注意：如果实参是简单变量，形参是指针变量，调用时实参应为简单变量的地址。6.5

属性文法的自顶向下翻译采用C语言编写L-属性文法递归下降翻译程序时采用的方法：4)输入符号的代码：对文法中出现的每个输入符号(即终结符号)，将赋值语句插入到过程中它所对应的NEXTSYM之前，把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量。5)动作符号的代码：对出现在文法中的每个动作符号，插入代码便于对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后输出相应的符号。6.5

属性文法的自顶向下翻译采用C语言编写L-属性文法递归下降翻译程序时采用的方法：4)输入符号的代码：对文法中出现的每个输入符号(即终结符号)，将赋值语句插入到过程中它所对应的NEXTSYM之前，把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给输入符号属性中的每个属性变量。5)动作符号的代码：对出现在文法中的每个动作符号，插入代码便于对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后输出相应的符号。6.5

属性文法的自顶向下翻译采用C语言编写L-属性文法递归下降翻译程序时采用的方法：6)属性规那么的代码：与每个产生式有关的属性求值规那么，插入其代码以便对属性求值规那么的右部求值，并把结果赋给该规那么左部的每个变量。可以把这些代码放在属性计算规那么的所有自变量之后，且函数值被使用之前的任何地方。7)主程序：C语言都是从MAIN函数开始运行。在MAIN函数中，对文法的开始符号，其相应的每一个综合属性的名字变成主程序的局部变量，然后调用开始符号对应的过程。在调用时，如果实参对应开始符号的继承属性，那么对每个继承属性以该属性的初始值作为值参传入，对每个综合属性取该属性的局部变量的地址传入。6.5

属性文法的自顶向下翻译例算术表达式属性翻译文法如下,用C语言实现其递归下降翻译器。E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r

@ADD↓p,r,t0E'↓t0↑t

t0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r

@MULT↓p,r,t0T'↓t0↑t

t0=NEWT

T'↓p↑t→εt=pF↑p->(E↑p)|ID↑p

6.5

属性文法的自顶向下翻译main()//主程序{ intes=0,t;printf("请输入算术表达式(操作数只能是单个字母)："); ch=getchar(); printf("输出四元式为：\n");

es=E(&t);

//调分析表达式E的翻译程序，

E↑t→T↑pE'↓p↑t if(es==0)printf("\n翻译成功!\n"); elseprintf("\n表达式有语法错误!\n");}6.5

属性文法的自顶向下翻译//产生式E↑t→T↑pE'↓p↑t的翻译子程序，t为综合属性,形参用指针变量intE(int*t)

{intes=0;

intp;es=T(&p);//调分析T子程序

es=E1(p,t);//调分析E'子程序，t是指针

return(es);}E(int*t)intpT(&p)E’(p,t)return//产生式E'↓p↑t→+T↑r

@ADD↓p,r,t0E'↓t0↑t|ε的翻译子程序，其中，p为继承属性，形参用整型变量，t为综合属性，形参用指针变量intE1(intp,int*t)

{intr,es=0,t0;if(ch=='+'){ch=getchar();es=T(&r);

t0=NEWT();

//产生一个临时变量

printf("ADD,%c,%c,%c\n",p,r,t0);es=E1(t0,t);return(es);}else {*t=p; return(0);}}E’(intp,int*t)intr,t0;‘+’?nextsymT(&r)t0=NEWT()E’(t0,t)return*t=pnyn//返回一个临时变量,顺序产生A、B、...、Z，最多产生26个临时变量intNEWT(){staticinti=64;//设置i为静态变量确保下次调用时i为上次调用的结果

i=i+1;return(i);}6.5属性文法的自顶向下翻译6.5

属性文法的自顶向下翻译//产生式T↑t→F↑pT'↓p↑t的翻译子程序，t为综合属性,形参用指针变量intT(int*t)

{

int

es=0,p;

es=F(&p);

//调分析F子程序

es=T1(p,t);//调分析T'子程序return(es);}T(int*t)intpF(&p)T’(p,t)return//产生式T'↓p↑t→*F↑r

@MULT↓p,r,t0T'↓t0↑t

|ε的翻译子程序intT1(intp,int*t)

{

intr,es=0,t0; if(ch=='*') {ch=getchar();es=F(&r);

t0=NEWT();//产生一个临时变量

printf("MULT,%c,%c,%c\n",p,r,t0);

es=T1(t0,t); return(es);}else{*t=p;return(0);}}T’(intp,int*t)intr,t0;‘*’?nextsymF(&r)t0=NEWT()T’(t0,t)return*t=pny//产生式F↑p→(E↑p)|ID↑p

的翻译子程序intF(int*p)

//分析F子程序{intes=0;if(ch=='('){ch=getchar();es=E(p);

//调分析E子程序

if(ch!=')')return(3);else{ch=getchar();return(es);}}else{ if(isalpha(ch))

//判断是否为字母

{*p=ch; ch=getchar(); return(es); }elsereturn(4);}}F(int*p)‘(’?nextsymE(p)nextsymreturn*p=chny‘)’?nextsym字母?yy6.5

属性文法的自顶向下翻译运行这段程序，假设输入：a*(b+c)+b*dADD,b,c,AMULT,a,A,BMULT,b,d,CADD,B,C,D输出四元式序列为：其中A、B、C、D都是临时变量。6.5

属性文法的自顶向下翻译要实现属性翻译文法的LL(1)翻译器，是对翻译文法的LL(1)翻译器进行扩充,方法是(P139)：对于所有符号，不仅符号进分析栈，其属性也同时进栈。即将栈符号设计为两局部，符号名和属性域。任何栈符号的域都是在栈内的一些存贮单元。A属性A1属性A2B属性B1C…#例(P139)对符号串ABC，假定A有两个属性，B有一个属性而C没有任何属性。假设符号名也占用一个存贮单元，那么相应A的栈符号用三个存贮单元，B用二个，C用一个。6.5

属性文法的自顶向下翻译例(P139)文法：S→E↑p@ANSWER↓rr=pE↑p→+E↑qE↑r@ADD↓A1,A2↑RA1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑RA1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑qp=q

构造该属性翻译文法的LL(1)翻译器。符号输入符号

+*NUM#SE+*NUM#125

13

5

14

5

ACCEPTLL(1)翻译器的分析表1:POP,PUSH(@ANSWERE)2:POP,PUSH(@ADDEE+)3:POP,PUSH(@MULTEE*)4:POP,PUSH(NUM)5:POP,NEXTSYM6.5

属性文法的自顶向下翻译解：第一步获得其翻译文法的LL(1)分析表。6.5

属性文法的自顶向下翻译1、栈符号设计属性文法的每个符号有属性，所以每个符号入栈时，必须连属性一起入栈。〔1〕综合属性：其属性域存放一个指针，指向存贮该属性值的单元；〔2〕继承属性：其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但是在该栈符号变成栈顶符号之前的某一时刻，它们必须接受相应的属性值，即在成为栈顶时，继承属性的属性域必须有值。第二步扩充翻译文法的LL(1)翻译器6.5

属性文法的自顶向下翻译@MULT

继承属性A1

继承属性A2

综合属性R(指针)@ADD继承属性A1

继承属性A2综合属性R(指针)

@ANSWER

继承属性rNUM

综合属性q(指针)E综合属性p(指针)SS的栈符号

E的栈符号

NUM的栈符号

@ANSWER的栈符号

@ADD的栈符号

@MULT的栈符号

根据设计好的栈符号，对属性翻译文法构造LL(1)分析表。

符号输入符号

+*NUM#SE+*NUM#125

13

5

14

5

ACCEPT属性翻译文法的LL(1)分析表1:POP,PUSH(@ANSWER↓rE↑p)2:POP,PUSH(@ADD↓A1,A2↑RE↑rE↑q+)3:POP,PUSH(@MULT↓A1,A2↑RE↑rE↑q*)4:POP,PUSH(NUM↑q),把NUM的属性值q放入NUM的属性域指向的单元.5:POP,NEXTSYM

6.5

属性文法的自顶向下翻译2、语义动作设计假定要求翻译器所要完成的工作是计算由文法定义的表达式的值并输出，那么三个动作符号的翻译动作为：1)@ADD：把头两个域的内容相加，并把计算结果存贮在第三个域所指的单元中〔由R=A1+A2〕；POP。2)@MULT：把头两个域的内容相乘，并把积存贮在第三个域所指的单元中〔由R=A1*A2〕；POP。3)@ANSWER：输出属性域r的内容结果；POP。6.5

属性文法的自顶向下翻译1)初始状态+NUM↑2NUM↑3#

S#符号栈：

+NUM↑2NUM↑3#

E↑p@ANSWER↓r#符号栈：

2)查分析表S