第6章语法制导翻译技术分析

第6章语法制导翻译技术2024/10/231内容提要引言翻译文法语法制导翻译自顶向下语法制导翻译自底向上语法制导翻译属性翻译文法属性文法的自顶向下翻译属性文法的自底向上翻译2024/10/232引言编译程序的逻辑工作过程词法分析和语法分析仅仅对源程序做形式变换和检查。语义分析检查程序语义是否正确。中间代码生成将语义分析后的结果翻译成代码。上述工作过程采用串行处理方式实际应用中语法分析、语义分析、中间代码生成采用并行处理方式词法分析语法分析语义分析代码优化目标代码生成目标代码源程序中间代码生成2024/10/233并行处理方式：

对文法中的每个产生式都附加一些动作(语义分析、操作符号表、代码生成等),在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的其它动作，完成语义分析和代码生成等工作。（边分析边翻译）并行处理方式涉及几个概念翻译文法语法制导翻译属性翻译文法

2024/10/234翻译文法：在描述语言规则的文法产生式右部的适当位置加入动作而得到的文法。翻译文法@为动作符号标记，由符号@开始的符号串称为一个动作符号。2024/10/235例：构造中缀表达式文法的翻译文法，得到其后缀表达式。①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①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把中缀表达式文法叫做输入文法；在输入文法上添加动作后形成的文法叫做翻译文法使用中缀表达式文法推导得到终结符号串叫做输入序列；使用翻译文法推导得到的符号串称为活动序列。从活动序列中去掉所有动作符号得到输入序列，而所有动作符号组成的符号串称为动作序列。从动作序列中去掉动作符号标记得到输出序列（翻译结果）2024/10/236例：对于符号串(a+b)*c用输入文法推导输入序列(a+b)*c:E=>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)*c用翻译文法推导活动序列(a@a+b@b@+)*c@c@*: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@+)*c@c@*将活动序列(a@a+b@b@+)*c@c@*中的动作符号去掉得到输入序列：(a+b)*c所有动作符号组成的符号串即动作序列为：@a@b@+@c@*

去掉动作符号标记得到：ab+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@c2024/10/237由于翻译文法是在输入文法的产生式右部的适当位置插入动作符号形成的，因此，翻译文法产生的动作序列受输入语言的文法控制（语法制导）。语法制导翻译：根据输入文法，分析各条产生式的语义(要求计算机所完成的操作)，分别编出完成这些操作的子程序或程序段(称为语义子程序或语义动作)，并把这些子程序或程序段的名字作为动作符号插入到输入文法各产生式右部的适当位置上，从而实现翻译文法。

①E→E+T@+ ⑤F→(E)②E→T⑥F→a@a③T→T*F@* ⑦F→b@b④T→F ⑧F→c@c①E→E+T⑤F→(E)②E→T ⑥F→a③T→T*F⑦F→b④T→F⑧F→c2024/10/238语法制导翻译9语法制导翻译的基本思想通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法：

1．将文法符号所代表的语言成分的意思，用隶属于该文法符号的属性表示；

2．用语义规则(语义规则的执行就是语义动作)规定产生式所代表的语言成分之间的关系（即属性之间的关系），即用语义规则实现属性计算。3.语义动作(语义规则的执行)：在语法分析的适当时刻（如推导或归约）执行附在对应产生式上的语义规则，以实现对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。2024/10/23自顶向下的语法制导翻译：递归下降翻译、LL(1)翻译。递归下降翻译(在适当位置插入实现动作符号的子程序）:例:算术表达式翻译文法如下：(@为输出其后的符号串)①E→E+T@+②E→T③T→T*F@*

④T→F ⑤F→(E)⑥F→a@a⑦F→b@b⑧F→c@c消除左递归得到：

E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c自顶向下语法制导翻译

10FIRST(TE’)={(,a,b,c}FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}FIRST(FT’)={(,a,b,c}FIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}FIRST((E))={(}FIRST(a@a)={a}FIRST(b@b)={b}FIRST(c@c)={c}求FIRST集和FOLLOW集不考虑动作符号11－对改写后文法的每个非终结符号编写一个函数。对于产生式E→TE’FIRST(TE’)={(,a,b,c}－用E1表示E’

E(){if(ch∈FIRST(TE’)) {T();E1();}elseerror();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c12对于产生式

E’→+T@+E’|ε-用E1表示E’FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}E1(){ if(ch==‘+’) {ch=getnextsymbol();T();OUT(“+”);E1()；

} elseif(ch∈FOLLOW(E’))return;elseerror();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c对于产生式

T→FT’-用T1表示T’T(){if(ch∈FIRST(FT’)){F();T1();}else error();}2024/10/23E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c对于产生式T’→*F@*T’|εFIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}-用T1表示T’T1(){if(ch==‘*’){ch=getnextsymbol();F();OUT(“*”);T1()；}elseif(ch∈FOLLOW(E’))return;elseerror();}2024/10/2314E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c对于产生式F→(E)|a@a|b@b|c@c

F(){if(ch==‘a’){ch=getnextsymbol();OUT(“a”);}elseif(ch==‘b’){ch=getnextsymbol();OUT(“b”);}elseif(ch==‘c’){ch=getnextsymbol();OUT(“c”);}elseif(ch==‘(’）

{ch=getnextsymbol();E();if(ch==‘)’)ch=getnextsymbol();} elseerror（）;}2024/10/23152024/10/2316FIRST(TE’)={(,a,b,c}FIRST(+T@+E’)={+}FOLLOW(E’)={#,)}FIRST(FT’)={(,a,b,c}FIRST(*F@*T’)={*}FOLLOW(T’)={#,+,)}FIRST((E))={(}FIRST(a@a)={a}FIRST(b@b)={b}FIRST(c@c)={c}思考：句子a+b*c的翻译输出是什么？E→TE’E’→+T@+E’|εT→FT’T’→*F@*T’|εF→(E)|a@a|b@b|c@c输出：abc*+LL(1)翻译器

例：输入文法：①A→aBcD②A→b③B→c④B→aA⑤D→cD⑥D→b

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

符号输入符号

abc#ABDA→aBcDB→aA

A→b

D→b

B→cD→cD

翻译文法：①A→@va@wB@xc@yD@z②A→b③B→c@r④B→a@mA⑤D→cD@n⑥D→@sb符号

输入符号

abc#ABDA→@va@wB@xc@yD@zB→a@mAA→b

D→@sb

B→c@rD→cD@n

翻译文法的LL(1)分析表

翻译文法的动作符号同样入栈，当其处于栈顶时，无条件出栈并执行其规定的操作，不移动读符号指针。

构造翻译文法分析表不考虑动作符号2024/10/2317a……A..#@v

a

@w

B@x.#B..#@v出栈并执行，a出栈，@w出栈并执行

符号

输入符号

abc#ABDA→@va@wB@xc@yD@zB→a@mA

A→b

D→@sb

B→c@rD→cD@n

2024/10/2318波兰翻译文法：对于一个文法,当且仅当文法中每个产生式右部的所有动作符号都只出现在所有输入符号和非终结符号的右边,则称此类翻译文法为波兰翻译文法。例：0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

0)S→E1)E→E+T2)E→T3)T→T*F4)T→F5)F→(E)6)F→i

自底向上的语法制导翻译2024/10/2319状态

ACTION

GOTO

i+*()#ETF0S5

S4

1231

S6

A

2R2S7R2R2

3R4R4R4R4

4S5

S4

8235R6R6R6R6

6S5

S4

937S5

S4

108

S6

S11

9R1S7R1R1

10R3R3R3R3

11R5R5R5R5

算术表达式的LR分析表使用带动作符号的产生式归约要执行动作符号规定的动作。波兰翻译0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

2024/10/2320步骤状态栈符号栈输入串ACTIONGOTO10#i+i#S5205#i+i#R63303#F+i#R42402#T+i#R21501#E+i#S66016#E+i#S570165#E+i#R6380163#E+F#R4990169#E+T#R111001#E#ACC输入符号串i+i#的翻译过程归约之后执行@ADD,输出ADD0)S→E1)E→E+T@ADD2)E→T3)T→T*F@MULT4)T→F5)F→(E)6)F→i

2024/10/2321思考：若用栈计算后缀表达式，产生式6可添加什么动作？属性：指与文法符号的类型和值等有关的一些语义信息，在编译中用属性描述被处理对象的语义特征。属性代表与文法符号相关的语义信息。属性的设置和语法结构的语义以及翻译程序的需要有关。例如:文法符号X的类型属性:X.type文法符号X的值属性:X.val文法符号X的代码序列:X.code文法符号X的内存：X.place文法符号X的符号表入口指针:X.entry等。属性翻译文法注：教材中用箭头↑和↓代替.2024/10/232223属性、语义规则属性和变量一样，可以在语法分析过程中进行计算和传递。语义规则：属性的计算规则,属性的加工和计算过程。由语义处理过程、语义动作、语义子程序来实现。属性分为两类：综合属性和继承属性。终结符只有综合属性,由词法分析器提供例：i.lexval表示单词符号“数”的词法值id.entry表示单词符号“标识符”的符号表入口非终结符既可以有综合属性也可以有继承属性注：教材中属性前用↑表示综合属性，↓表示继承属性2024/10/2324两种属性：综合属性综合属性用于“自下而上”传递信息。综合属性：在语法树中，一个结点的综合属性值由其子结点的属性值确定。通常结合自下而上的语法分析在每一个结点处使用语义规则计算综合属性的值---由下层子结点的属性值计算上层父结点的综合属性值，随着自下而上语法分析的进行，最终可计算出开始符号的综合属性值。AX1X2…XnA.bX1.c1X2.c2…Xn.

ckAX1X2…Xn综合属性A.b=f(c1,c2,…,ck)带属性的语法树2024/10/23例：设计一个语法分析程序接受算术表达式，并通过添加动作符号输出表达式的值。已知符号串翻译文法如下：①S→E@ANSWER②E→E+T③E→T④T→T*F⑤T→F⑥F→(E)⑦F→NUM@ANSWER的动作是输出表达式的计算结果。表达式3+2*3的词法分析结果如下：

NUM↑3+NUM↑2*NUM↑3其中NUM代表无符号整数,↑数字串表示该符号的属性2024/10/2325改写每一个产生式，添加符号属性变量名，并定义符号属性之间的关系即属性求值规则(语义规则)，得到：

属性文法求值规则

①S→E↑q@ANSWER↓rr=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↑qp=q通过自底向上进行求值的属性，称为综合属性，用↑来表示。终结符号的综合属性具有初始值，由词法分析给出。2024/10/2326SET+E@ANSWERF*TTFNUM↑3

FNUM↑2

NUM↑3

NUM↑3+NUM↑2*NUM↑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

NUM↑3+NUM↑2*NUM↑3带属性计算的语法树

属性文法求值规则①S→E↑q@ANSWER↓rr=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在归约过程中完成属性值的计算⑦⑤③⑦⑤⑦④②2024/10/232728两种属性：继承属性继承属性用于“自上而下”传递信息。继承属性：在语法树中，一个结点的继承属性由此结点的父结点和(或)兄弟结点的某些属性确定。可以用继承属性来表示程序语言结构中的上下文依赖关系。继承属性的计算可以结合自上而下的语法分析进行A

X1…X

…XnA.

ck

X1.c1…X.b…Xn.ciAX1X2…X…Xn

继承属性X.b=f(c1,c2,…,ck)2024/10/23例：声明语句文法 ①<声明语句>→TYPEID<变量表>; ②<变量表>→，ID<变量表> ③<变量表>→ε

其中TYPE可为int，real，bool假设词法分析程序输出单词符号时，对变量名输出单词记号ID和变量名；对TYPE输出单词记号TYPE和类型名。构造语法分析程序，能输出变量名及其类型

2024/10/23291、添加语义动作@SET_TYPE输出变量名及类型，因此@SET_TYPE带有两个属性，即变量名和类型：

@SET_TYPE↓n1，t1语法分析程序读到一个变量后，调用SET_TYPE。因此文法改写为：

(1)<声明语句>→TYPEID@SET_TYPE<变量表>;(2)<变量表>→，ID@SET_TYPE<变量表>(3)<变量表>→ε2、确定需要的属性TYPE需要一个属性(类型名)，即TYPE↑tID需要一个属性(变量名)，即ID↑n<变量表>需要一个属性，即<变量表↓t2>2024/10/23303、确定语义规则（属性求值规则）产生式(1)的TYPE↑t和ID↑n由词法分析输出得到。产生式(2)从词法分析只能得到ID↑n，令产生式(2)左边<变量表↓t2>=产生式(1)右边<变量表↓t2>,得到翻译文法：<声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<变量表↓t2>

t2=t，t1=t，n1=n（属性求值规则）2)<变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2>

t2=t，t1=t，n1=n（属性求值规则）3)<变量表>→ε

(1)<声明语句>→TYPEID@SET_TYPE<变量表>;(2)<变量表>→，ID@SET_TYPE<变量表>(3)<变量表>→ε2024/10/2331假设输入符号串为inta,b；，词法分析输出为TYPE↑intID↑a,D↑b；，则带有属性的语法树如图所示按自顶向下或自左向右方式求得的属性称为继承属性,其前面冠以↓表示。

声明语句

；@SET_TYPE↓a,int

ID↑a

TYPE↑int

变量表↓int

@SET_TYPE↓b,int

ID↑b

变量表↓int

，ε

TYPE↑intID↑a,D↑b；的语法树<声明语句>→TYPE↑tID↑n@SET_TYPE↓n1,t1<变量表↓t2>

(1)t2=t，(2)t1=t，(3)n1=n（属性求值规则）2)<变量表↓t>→，ID↑n@SET_TYPE↓n1,t1<变量表↓t2>

(4)t2=t，(5)t1=t，(6)n1=n（属性求值规则）3)<变量表

>→ε

2024/10/233233属性文法：编译技术中采用的一种语义描述工具，是一种适用于定义语言语义的特殊文法，即：在语言的文法中增加了属性的文法。属性翻译文法：是以一个上下文无关文法为基础,为每个文法符号引进一组属性(语义值)，对文法的每个产生式都配备一组与之相关联的属性的计算规则(语义规则)而得到的文法。或者说：符号具有属性并带有属性求值规则的翻译文法称为属性翻译文法其具体定义如下：2024/10/231)文法的每个终结符、非终结符和动作符号都可以有一个有穷的属性集。2)每个非终结符和动作符号属性可分为综合属性和继承属性。3)继承属性的求值规则：①开始符号的继承属性具有初始值。②对产生式左部的非终结符，其继承属性则继承前面产生式中该符号已有的继承属性值。③右部的符号，其继承属性由产生式中其它符号属性值进行计算。（语法树上的父亲和兄弟）2024/10/23344)综合属性的求值规则：①

终结符号的综合属性具有指定的初始值。在具体实现中，初始值由由词法分析程序提供。②

产生式右部的非终结符号的综合属性值，则取后面以该非终结符号为产生式左部时求得的综合属性值。③

产生式的左部的非终结符号的综合属性值，由产生式中左部或右部的某些符号的属性值进行计算。④给定一动作符号，其综合属性值用该动作符号的其它属性值进行计算。2024/10/2335翻译要求：翻译输出是四元式代码

输出符号串中的每个双目运算都用一个四元式表示。四元式的顺序与执行时的运算顺序相同。四元式有三个参数，从左到右为∶左操作数，右操作数，运算结果。

例：翻译器将表达式a+b翻译成如下四元式∶

ADDa,b,t1其中t1是临时变量，保存表达式的结果。对于表达式：a+a*b，词法分析得到ID↑a+ID↑a*ID↑b，属性翻译文法翻译得到：

MULTab,t1ADDat1,t2例：算术表达式的翻译文法：E→E+TE→TT→T*FT→FF→(E)F→ID

2024/10/23361、设计翻译文法：E→E+T@ADDE→TT→T*F@MULTT→FF→(E)F→ID

2024/10/23372、确定属性和求值规则，构造属性翻译文法1)令每个非终结符有一个综合属性：临时变量，保存由它产生的表达式结果。2)输入符号ID有一个综合属性：符号的变量名。3)动作符号有三个继承属性：左操作数、右操作数、运算结果。属性翻译文法如下：E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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

输出ADDy,z,t动作符号@MULT↓y,z,t

输出MULTy,z,t2024/10/2338ID↑a

E↑x

T↑r

+E↑q

F↑p

*T↑q

T↑p

F↑x

F↑x

ID↑a

ID↑b

@MULT↓y,z,t

@ADD↓y,z,t

表达式a+a*b的属性语法树E↑t2

T↑t1

E↑a

F↑b

T↑a

T↑a

F↑a

F↑a

@MULT↓a,z,t

@ADD↓a,z,t

产生新变量t2产生新变量t1E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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=p2024/10/2339@MULT↓a,b,t

@MULT↓a,b,t1

@ADD↓a,t1,t

@ADD↓a,t1,t2

属性翻译文法的语法树需要保证完整性，即保证所有属性能通过计算赋值。不同分析方法对文法有不同要求。L-属性翻译文法：自顶向下分析时保证语法树的完整性属性文法的自顶向下翻译2024/10/23402024/10/2341

属性翻译文法是L-属性翻译文法，当且仅当对其中的每个产生式A→X1X2…Xn，下面三个条件成立：1．右部符号Xi(1≦i≦n)的继承属性之值，仅依赖于X1,X2,…,Xi-1的任意属性或A的继承属性（P133继承属性规则③的限制）；

（L的含义：符号的继承属性只依赖于该符号左边的属性值）2．左部符号A的综合属性值仅依赖于A的继承属性或右部符号Xi(1≦i≦n)的任意属性（P133综合属性规则③的限制）；3．对一动作符号而言，其综合属性值依赖于该动作符号的继承属性（P133继承属性规则④的限制）。条件2、3避免求值的循环依赖；给定文法后可通过构造依赖图进行拓扑排序证明）例：文法中有产生式为：A↓I1↑S2,S3→B↓I4C↑S5D↑S6↓I7,I8E↓I9根据L-属性的限制条件，I4=F(I1)、S2=G(I7,S6)合法，而I4=H(S2)不合法。

条件1条件2L-属性文法翻译的实现——递归下降翻译

处理思路和处理不带属性的翻译文法相同，由于属性的存在需要改造对非终结符的处理方法：1)若非终结符具有属性，则该非终结符的分析函数具有形参，形参数目等于其属性个数。

2)对于继承属性，采用值传递方式，将继承属性值传入被调函数，即在函数调用中所对应的实参是继承属性的值。

3)对于综合属性，采用引用（地址）传递方式，以便将值回传给主调函数,即实参是一个变量引用（地址），在函数返回之前，把综合属性的值赋给该变量。

2024/10/2342为了进行属性翻译的程序设计，作下述约定：

1)将属性名用作变量名和参数名。

2)所有出现在左部的同名非终结符，应具有相同的属性名表。例:产生式L↑a↓b→E↓iR↓j，i,j=b,a=i+2L↑x↓y→H↑z↓w，w=y,z=2,x=z+y改成：L↑a↓b→E↓iR↓j，i,j=b,a=i+2L↑a↓b→H↑z↓w，w=b,z=2,a=z+b2024/10/23433)若两个属性值相同，则给它们相同的名字，但左部符号的属性值相等时，不能改变成相同的名字。规则S→A↑aB↓bC↓c，当b=a，c=a时，可写成S→A↑aB↓aC↓a规则L↑a→A↓b@f↓c

，当a=b,c=b时，可写成L↑a→A↓a@f↓a规则L↓a↑b→xB↓cC↓d,当c=a,d=a时，

可写成L↓a↑b→xB↓aC↓a但当b=a时，不能写成L↓a↑a→aB↓aC↓a理由：左部非终结符号的属性将作为该非终结符号分析函数的形参，而一个函数的形参不能重名。如函数L(inta,intb)不可写成L(inta,inta)。2024/10/2344采用C语言编写属性翻译程序时采用的方法：1)形式参数：产生式左部非终结符的属性名表设计成相应的形参表；将继承属性的形参名说明为值形参(即简单变量)，综合属性形参名说明为指针变量。2)局部变量：产生式中与在左部出现的属性名不同的属性名变成相应函数的局部变量。3)非终结符的代码：对于右部出现的每个非终结符的函数调用，该非终结符的属性作为实参。2024/10/23454)终结符的代码：对文法中出现的每个终结符，将赋值语句插入到函数中它所对应的NEXTSYM之前，把保存在读符号程序NEXTSYM中的终结符号属性(某个全局变量中)赋给终结符属性中的每个属性变量（读下一个符号前赋值）。5)动作符号的代码：对出现在文法中的每个动作符号，插入代码对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后执行相应动作。2024/10/23466)属性规则的代码：与每个产生式有关的属性求值规则，插入其代码以便对属性求值规则的右部求值，并把结果赋给该规则左部的每个变量。可以把这些代码放在属性计算规则的所有自变量已知之后，且函数值被使用之前的任何地方。7)主程序：MAIN函数中，对文法开始符号的每一个综合属性的名字变成主程序的局部变量，然后调用开始符号对应的函数。2024/10/2347例：为算术表达式的L-属性翻译文法编写递归下降翻译器。E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

2024/10/2348如何得到该文法？1、消除左递归2、命名改造2024/10/2349E↑x→E↑q+T↑r@ADD↓y,z,t，y=q,z=r,t=NEWT，x=tE↑x→T↑px=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=pE↑x→T↑pE'↓q↑y

x=yq=pE'↓q↑y→+T↑r@ADD↓p,s,t0E'↓t1↑tt0=NEWTp=qs=rt1=t0t=t0y=tE'↓q↑y→εy=qT↑x→F↑pT'↓q↑yx=yq=pT'↓q↑y→*F↑r@MULT↓p,s,t0T'↓t0↑tt0=NEWTp=qs=rt1=t0t=t0y=tT'

↓q↑y→εy=qF↑q→(E↑p)|ID↑pq=p消除左递归ETF+TE’εIDE’T’εFIDT’ε2024/10/2350命名处理E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

E↑x→T↑pE'↓q↑y

x=yq=pE'↓q↑y→+T↑r@ADD↓p,s,t0E'↓t1↑tt0=NEWTp=qs=rt1=t0t=t0y=tE'↓q↑y→εy=qT↑x→F↑pT'↓q↑yx=yq=pT'↓q↑y→*F↑r@MULT↓p,s,t0T'↓t0↑tt0=NEWTp=qs=rt1=t0t=t0y=tT'

↓q↑y→εy=qF↑q→(E↑p)|ID↑pq=p对产生式E↑t→T↑pE'↓p↑t，t为综合属性,形参用指针变量intE(int*t){intes=0;intp;es=T(&p);

es=E1(p,t);

return(es);}E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

方法1方法2方法32024/10/2351对产生式E'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑t和

E'↓p↑t→εp为继承属性,形参用整型变量,t为综合属性,形参用指针变量intE1(intp,int*t){intr,es,t0;if(ch=='+'){ch=getword();es=T(&r);t0=NEWT();printf(“ADD%c,%c,%c\n",p,r,t0);es=E1(t0,t);return(es);}elseif(ch=='('||ch=='#') {*t=p; return(0);}elseerror();}......E'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑t

t0=NEWT

E'↓p↑t→εt=p......方法4，但+无属性方法5，动作符号无综合属性方法62024/10/2352intNEWT(){staticinti=64;

i=i+1;

return(i);}对产生式T↑t→F↑pT'↓p↑tt为综合属性,形参用指针变量intT(int*t){intes=0,p;es=F(&p);

es=T1(p,t);

return(es);}E↑t→T↑pE'↓p↑tE'↓p↑t→+T↑r@ADD↓p,r,t0E'↓t0↑tt0=NEWT

E'↓p↑t→εt=pT↑t→F↑pT'↓p↑tT'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

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

2024/10/2353intT1(intp,int*t){intr,es,t0;if(ch=='*'){ch=getword();es=F(&r);t0=NEWT();

printf(“MULT%c,%c,%c\n",p,r,t0);es=T1(t0,t);return(es);}elseif(ch=='+'||ch=='#'||ch==')'){*t=p;return(0);}elseerror();}......T'↓p↑t→*F↑r@MULT↓p,r,t0T'↓t0↑tt0=NEWT

T'↓p↑t→εt=p......2024/10/2354对产生式T’↓p↑t→*F↑r@MULT↓p,r,t0T’↓t0↑t和T’

↓p↑t→ε，p为继承属性,形参用整型变量；t为综合属性,形参用指针变量intF(int*p){intes=0;if(ch=='('){ch=getword();es=E(p);

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

{*p=ch; ch=getword(); return(es); }elsereturn(4);}}对产生式F↑p→(E↑p)|ID↑pp为综合属性,形参用指针变量方法42024/10/2355主程序：1、MAIN函数中对开始符号的每一个综合属性作为其局部变量；2、调用开始符号对应的函数，如果实参对应开始符号的继承属性，则以值参方式传入该属性的初始值；如果对应开始符号的综合属性，则传入该属性局部变量的地址。E↑t→T↑pE'↓p↑tmain(){intes=0,t;printf("请输入算术表达式(操作数只能是单个字母)：");ch=getword();printf("输出四元式为：\n");es=E(&t);

if(es==0)printf("\n翻译成功!\n");elseprintf("\n表达式有语法错误!\n");}方法7（1）方法7（2）2024/10/2356运行程序输入：a*(b+c)+b*d输出四元式序列为：其中A、B、C、D都是临时变量。ADDb,c,AMULTa,A,BMULTb,d,CADDB,C,D2024/10/235758输入：NUM↑2*NUM↑4+NUM↑6#E'↓t0↑tNUM↑2*E↑tT↑pF↑pT'↓p↑t+F↑rE'↓p↑t

T↑rNUM↑6F↑p

2024/10/23T'↓p↑t

NUM↑4F↑2T'↓2↑tF↑4MULT↓p,r,t0MULT↓2,r,t0MULT↓2,4,t0MULT↓2,4,8T'↓t0↑tT'↓8↑tADD↓p,r,t0F↑6T'↓6↑tT'↓8↑8T'↓2↑8T↑8E'↓8↑tT↑6T'↓6↑6E'↓8↑14ADD↓8,6,t0ADD↓8,6,14E'↓14↑tE'↓14↑14E↑14调用进入返回递归下降翻译程序的运行（将文法中ID改为NUMt0=p+rt0=p*r）L-属性文法翻译的实现—LL(1)法扩充翻译文法的LL(1)翻译器：对所有符号，符号本身和属性同时进栈。将栈符号设计为两部分(符号名、属性域)例：对符号串ABC，假定A有属性A1和A2，B有属性B1，C无属性。入栈后如图所示。

A属性

A1属性

A2B属性B1C…#2024/10/2359例：文法S→E↑p@ANSWER↓r

r=pE↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑q

p=q

构造其翻译器

步骤：1、栈符号设计2、构造LL(1)分析表3、设计语义动作2024/10/23601、栈符号设计根据属性类型确定属性域的存放内容，可存放属性值和指向属性值的指针。对于综合属性，其属性域存放一个指针，指向存贮该属性值的单元。对于继承属性，其属性域直接保存其属性值。继承属性的属性域刚入栈时为空，但在该栈符号变成栈顶符号之前的某一时刻，必须通过计算赋值，即在成为栈顶时，继承属性的属性域必须有值。2024/10/2361@MULT

继承属性1

继承属性2

综合属性指针

@ADD继承属性1

继承属性2

综合属性指针

@ANSWER

继承属性NUM

综合属性指针E综合属性指针SS的栈符号

E的栈符号

NUM的栈符号

@ANSWER的栈符号

@ADD的栈符号

@MULT的栈符号

S→E↑p@ANSWER↓r

r=pE↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=RE↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=RE↑p→NUM↑q

p=q

2024/10/23622、构造属性翻译文法LL(1)分析表。符号输入符号

+*NUM#SE121314

LL(1)析表(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=1+A2,p=R(3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=R(4)E↑p→NUM↑q

p=q

2024/10/23633、语义动作设计假定要求翻译器计算输出由文法定义的表达式值,三个动作符号的翻译动作为：1)@ADD：把头两个域的内容相加并将结果存贮在第三个域所指的单元中，然后出栈。2)@MULT：把头两个域的内容相乘并将结果存贮在第三个域所指的单元中，然后出栈。3)@ANSWER：输出属性域的内容结果，然后出栈。

2024/10/23641)#入栈，文法开始符号S入栈，输入指针指向符号++NUM↑2NUM↑3#

S#符号栈：输入串+NUM↑2NUM↑3#

E↑p@ANSWER↓r#符号栈：2)查分析表S行+列，入栈，因为r=p，所以E↑p为指向@ANSWER↓r的指针。

符号输入符号

+*NUM#SE121314

输入符号串+NUM↑2NUM↑3#的分析过程：2024/10/2365(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R(3)E↑p→*E↑qE↑r@MULT↓A1,A2↑R

A1=q,A2=r,R=A1*A2,p=R(4)E↑p→NUM↑q

p=q

NUM↑2NUM↑3#

E↑qE↑r@ADD↓A1↓A2↑R@ANSWER↓r#符号栈：

3)查分析表E行+列,E出栈前,E↑p指向@ANSWER↓r,因为E↑p=@ADD↑R,所以@ADD↑R指向@ANSWER↓r;新入栈的E↑qE↑r,分别指向@ADD↑A1↑A2;因栈顶为+,+出栈,读下一个符号。

符号输入符号

+*NUM#SE121314

2024/10/2366E↑p@ANSWER↓r#(1)S→E↑p@ANSWER↓r

r=p(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R......+NUM↑2NUM↑3#

NUM↑3#

E↑r@ADD2↓A2↑R@ANSWER↓r#符号栈：

4)查分析表E行NUM列，E出栈前,E↑q指向@ADD↑A1,而E↑q=NUM↑q,所以NUM↑q入栈,把NUM

↑2放入E出栈前E↑q指向的单元@ADD↑A1。然后，NUM出栈,读下一个符号。

2024/10/2367......(4)E↑p→NUM↑qp=q

符号输入符号

+*NUM#SE1213

14

符号栈：E↑qE↑r@ADD↓A1↓A2↑R@ANSWER↓r#NUM↑2NUM↑3#

符号输入符号

+*NUM#SE1213

14

5)查分析表E行NUM列，E出栈前,E↑r指向@ADD↑A2,而E↑r=NUM↑q,所以NUM↑q入栈,把NUM↑3放入E↑r指向的单元@ADD↑A2。然后NUM出栈，读下一个符号。

#

@ADD23↑R@ANSWER↓r#符号栈：2024/10/2368.......(4)E↑p→NUM↑q

p=q

NUM↑3#

E↑r@ADD2↓A2↑R@ANSWER↓r#符号栈：

6)栈顶为动作符号@ADD：把头两个域内容2和3相加，并把计算结果5存贮在第三个域@ADD↑R所指的@ANSWER↓r中，出栈。#

@ANSWER5#符号栈：2024/10/2369符号输入符号

+*NUM#SE1213

14

......(2)E↑p→+E↑qE↑r@ADD↓A1,A2↑R

A1=q,A2=r,R=A1+A2,p=R#

@ADD23↑R@ANSWER↓r#符号栈：7)栈顶为动作符号@ANSWER,输出属性域的内容5，出栈。栈内为#，输入指针指向#，成