工学语法制导的翻译

主讲人：范敏陈意云张昱高等教育出版社编译原理

-42023/9/1第4章语法制导的翻译2引入复习词法分析的任务和正规式的作用语法分析的任务和文法的作用思考语言结构的属性如何计算？何时计算？属性值如何存放？2023/9/1第4章语法制导的翻译3第1章编译器概述第2章词法分析第3章语法分析第4章语法制导的翻译第5章类型检查第6章运行时存储空间的组织和管理第7章中间代码生成第8章代码生成第9章*代码优化第10章*编译系统和运行系统第11章*面向对象语言的编译第12章*函数式语言的编译目录2023/9/1第4章语法制导的翻译44.1语法制导的定义4.2S属性定义的自下而上计算4.3L属性定义的自上而下计算4.4L属性的自下而上计算4.5递归计算第4章语法制导的翻译2023/9/1第4章语法制导的翻译5本章内容介绍一种形式化的语义描述方法语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案介绍语法制导的翻译的实现方法2023/9/1第4章语法制导的翻译6本章学习目标掌握综合属性、继承属性、语法树、翻译方案等概念掌握语法制导的定义方法掌握S属性和L属性的计算方法2023/9/1第4章语法制导的翻译74.1语法制导的定义例：简单台式计算器的语法制导定义基础文法(产生式)

语

义

规

则

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval注意基础文法与拓广文法的区别2023/9/1第4章语法制导的翻译8基础文法基础文法是语法制导定义中的文法。其中，每个文法符号都有一组可以用于计算的属性每个产生式A

有一组形式为b:=f(c1,c2,…,ck)的语义规则。其中f是函数，b,c1,c2,…,ck

是文法符号的属性语义规则一组计算表达式计算相应产生式中文法符号的属性值4.1.1语法制导定义的形式2023/9/1第4章语法制导的翻译9文法符号属性分类继承属性：如果b是产生式右部某个文法符号X的属性，c1,c2,…,ck

是产生式左部文法符号A的属性或产生式右部文法符号属性综合属性：如果b是A的属性，c1,c2,…,ck

是产生式右部文法符号属性或A的继承属性bbb:=f(c1,c2,…,ck)A

X

B属于子结点B属于父结点2023/9/1第4章语法制导的翻译10S属性定义：仅使用综合属性的语法制导定义产

生

式

语

义

规

则

L

E

n

print(E.val)虚拟属性

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.1.2综合属性如何计算综合属性值？2023/9/1第4章语法制导的翻译118+5*2n的计算：1.根据基础文法画出推导出句子的分析树digitLEnTETFdigitT+*FFdigit2023/9/1第4章语法制导的翻译128+5*2n的计算：2.标出分析树中每个结点的属性（如果有）digit.lexvalLE.valn

换行符T.valE.valT.valF.valdigit.lexvalT.val+*F.valF.valdigit.lexval注意注释分析树与分析树之间的区别2023/9/1第4章语法制导的翻译138+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.valF.valdigit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章语法制导的翻译148+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.valF.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章语法制导的翻译158+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章语法制导的翻译168+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2023/9/1第4章语法制导的翻译178+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval=52023/9/1第4章语法制导的翻译188+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.val=5F.valdigit.lexval=52023/9/1第4章语法制导的翻译198+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52023/9/1第4章语法制导的翻译208+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52023/9/1第4章语法制导的翻译218+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章语法制导的翻译228+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.valnT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章语法制导的翻译238+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章语法制导的翻译248+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52023/9/1第4章语法制导的翻译258+5*2n的计算：3.分析树各结点属性的计算可以自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5打印E属性值Print(E.val)2023/9/1第4章语法制导的翻译26利用分析树对S属性定义中综合属性的计算方法小结画出句子（词法记号流符号串）的分析树标出每个结点的属性（如果有）根据语义规则自下而上、从左到右完成各个结点属性的计算2023/9/1第4章语法制导的翻译27intid,id,id文法产生式

语

义

规

则

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

4.1.3继承属性如何计算继承属性值？2023/9/1第4章语法制导的翻译28intid1,id2,id3的注释分析树分析树DintT,id3LLLid2id1,2023/9/1第4章语法制导的翻译29intid1,id2,id3的注释分析树在注释分析树每个L结点，除传递继承属性in给子结点L1外，addtype过程在符号表中将L右子结点上标识符id的类型记为整型：addtype(id.entry,L.in)

DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,包含结点属性T.typeid.entryL.in，虚拟属性L1.in:=L.in2023/9/1第4章语法制导的翻译30intid1,id2,id3的分析树的依赖图

描述结点属性间依赖关系的有向图称为依赖图

D

TL

{L.in:=T.type}4.1.4属性依赖图DintTLin

54type所有属性可用结点表示2023/9/1第4章语法制导的翻译31intid1,id2,id3的分析树的依赖图

L

L1,

id{L1.in:=L.in;

addtype(id.entry,L.in)}

DintT,id3LLLid2id1,1entry102entry3entryin

98in

76in

54typeaddtype(id.entry,L.in)导致的虚拟属性注意：L有两个属性(继承属性in和虚拟属性)2023/9/1第4章语法制导的翻译32拓扑排序：属性结点出现顺序的一种排序，使得有向边只从该次序中先出现的结点指向后出现的结点例：1，2，3，4，5，6，7，8，9，104.1.5属性计算次序DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type只有结点属性传递的方向性不够2023/9/1第4章语法制导的翻译33属性计算过程（1）构造输入串的分析树DintT,id3LLLid2id1,2023/9/1第4章语法制导的翻译34属性计算过程（1）构造输入串的分析树；（2）构造属性依赖图DintT,id3LLLid2id1,entryentryentryininintype2023/9/1第4章语法制导的翻译35属性计算过程（1）构造输入串的分析树；（2）构造属性依赖图；（3）对属性结点进行拓扑排序DintT,id3LLLid2id1,1entry102entry3entryin98in76in54typeaddtype(id.entry,L.in)导致的虚拟属性2023/9/1第4章语法制导的翻译36属性计算过程（1）构造输入串的分析树；（2）构造属性依赖图；（3）对属性结点进行拓扑排序；（4）按拓扑排序的次序计算属性DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type2023/9/1第4章语法制导的翻译37DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type属性计算过程a4:=integer;a5:=a4;addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7;addtype(id1.entry,a9);2023/9/1第4章语法制导的翻译38语义规则的计算方法2023/9/1第4章语法制导的翻译39语义规则的计算方法分析树方法：前面介绍方法（编译速度慢）2023/9/1第4章语法制导的翻译40语义规则的计算方法分析树方法：前面介绍方法（编译速度慢）基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译器，时空改善）2023/9/1第4章语法制导的翻译41语义规则的计算方法分析树方法：前面介绍方法（编译速度慢）基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译器，时空改善）忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制（时空改善）2023/9/1第4章语法制导的翻译42本节小结介绍了语法制导定义、继承属性、综合属性、属性依赖图、拓扑顺序等概念详细介绍了利用分析树计算属性的方法简单对比了属性计算的三种方法2023/9/1第4章语法制导的翻译43作业P140：12023/9/1第4章语法制导的翻译44思考语言结构属性计算的基础是什么？依赖图和拓扑顺序有什么作用？它们对计算S属性定义中的综合属性是否有用？计算语言结构属性的步骤是什么？本节在语法制导定义的基础上通过分析树研究了属性计算次序的问题，那么如何在此基础上编程实现呢？2023/9/1第4章语法制导的翻译454.2S属性定义的自下而上计算

语法树是分析树的浓缩表示：算符和关键字作为内部结点语法树的例子：if-then-elseBS1S24.2.1语法树算符运算对象ifBthenS1elseS2复习S属性定义？2023/9/1第4章语法制导的翻译464.2S属性定义的自下而上计算

语法树是分析树的浓缩表示：算符和关键字作为内部结点语法树的例子：if-then-elseBS1S24.2.1语法树算符运算对象ifBthenS1elseS28+5*2算符优先级别？2023/9/1第4章语法制导的翻译474.2S属性定义的自下而上计算

语法树是分析树的浓缩表示：算符和关键字作为内部结点语法树的例子：if-then-elseBS1S2+*84.2.1语法树算符运算对象ifBthenS1elseS28+5*22023/9/1第4章语法制导的翻译484.2S属性定义的自下而上计算

语法树是分析树的浓缩表示：算符和关键字作为内部结点语法树的例子：if-then-elseBS1S2+*2584.2.1语法树算符运算对象ifBthenS1elseS28+5*22023/9/1第4章语法制导的翻译494.2S属性定义的自下而上计算

语法树是分析树的浓缩表示：算符和关键字是作为内部结点语法制导翻译可以基于分析树，也可以基于语法树if-then-elseBS1S2+*2584.2.1语法树算符运算对象ifBthenS1elseS28+5*22023/9/1第4章语法制导的翻译504.2.2构造语法树的语法制导定义语法树的存储语法树的结点可以用有若干域的记录来实现对于算符结点：一个域存放算符，该域作为该结点的标记，其余两个域含指向运算对象的指针三地址对于基本运算对象结点：一个域存放运算对象类别，另一个域存放其值二地址用于语法制导翻译时，一个结点可能还有其它域来保存加在该结点的其它属性值（即域中保存属性值存储位置的指针）结点的类型2023/9/1第4章语法制导的翻译51产生式语

义

规

则

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf

(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

用于构造算术表达式语法树的语法制导定义mkleaf(id,entry)：建立标识符id的结点，结点的entry域用于存放该标识符条目的指针2023/9/1第4章语法制导的翻译52产生式语

义

规

则

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf

(num,num.val)

用于构造算术表达式语法树的语法制导定义mkleaf(num,val)：建立数num的结点，结点的val域用于存放该数值2023/9/1第4章语法制导的翻译53产生式语

义

规

则

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

用于构造算术表达式语法树的语法制导定义mknode(op,left,right)：建立算符op的结点，指针域left和right分别存放该算符左、右运算对象的指针2023/9/1第4章语法制导的翻译54a+5*b的语法树的构造P112结点属性E.nptrT.nptrF.nptrE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口变量aleftright数值5变量b2023/9/1第4章语法制导的翻译55a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译56a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译57a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译58a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译59a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译60a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译61a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译62a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口aleftright5b自下而上、从左到右构造语法树2023/9/1第4章语法制导的翻译63a+5*b的语法树的构造+id*numid2023/9/1第4章语法制导的翻译64S属性可以由自下而上分析器在语法分析输入时完成计算，即“边分析边计算”自下而上分析器用栈保存已经分析的子树的信息，S属性定义的翻译器可以借助LR分析器的生成器来实现LR分析器可以把文法符号的综合属性放在它的栈内，每当归约时，根据出现在栈顶的产生式右部符号串中符号的属性来计算左部符号的综合属性4.2.3S属性的自下而上计算复习LR分析器的工作原理：栈内可以不存储文法符号综合属性来自于子节点或自身的继承属性2023/9/1第4章语法制导的翻译65将LR分析器增加一个域来保存综合属性值ZZ.zYY.yXX.x......栈statevaltop2023/9/1第4章语法制导的翻译66将LR分析器增加一个域来保存综合属性值ZZ.zYY.yXX.x......栈statevaltop若产生式A

→XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)右部符号从左至右压入栈内2023/9/1第4章语法制导的翻译67将LR分析器增加一个域来保存综合属性值ZZ.zYY.yXX.x......若产生式A

→XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)，那么归约后：......AA.a......栈statevaltoptoptop=top-2Top’2023/9/1第4章语法制导的翻译68例：台式计算器的语法制导定义改成栈操作代码

ZZ.zYY.yXX.x......栈statevaltop产

生

式

语义规则

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexvalTop’2023/9/1第4章语法制导的翻译69例：台式计算器的语法制导定义改成栈操作代码

ZZ.zYY.yXX.x......栈statevaltop产

生

式

代码段

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexvalTop’2023/9/1第4章语法制导的翻译70例：台式计算器的语法制导定义改成栈操作代码

nEE.val............产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置Top’2023/9/1第4章语法制导的翻译71例：台式计算器的语法制导定义改成栈操作代码

TT.val+EE.val......产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置Top’2023/9/1第4章语法制导的翻译72例：台式计算器的语法制导定义改成栈操作代码

TT.val..................产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不变

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置2023/9/1第4章语法制导的翻译73例：台式计算器的语法制导定义改成栈操作代码

FF.val*TT.val......产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不变

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

T.val:=F.val

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置Top’2023/9/1第4章语法制导的翻译74例：台式计算器的语法制导定义改成栈操作代码

FF.val..................产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不变

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不变

F

(E)

F.val:=E.val

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置2023/9/1第4章语法制导的翻译75例：台式计算器的语法制导定义改成栈操作代码

)EE.val(......产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不变

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不变

F

(E)

val[top

2]

:=val[top

1]

F

digit

F.val:=digit.lexval栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置Top’2023/9/1第4章语法制导的翻译76例：台式计算器的语法制导定义改成栈操作代码

digitdigit.lexval..................产

生

式

代码段

L

E

n

print(val[top

1])

E

E1+T

val[top

2]:=val[top

2]+val[top]

E

T

val[top]不变

T

T1*

F

val[top

2]:=val[top

2]

val[top]

T

F

val[top]不变

F

(E)

val[top

2]

:=val[top

1]

F

digit

val[top]不变栈statevaltop:=左边为归约后左部文法符号的属性值，下标为值的存储位置2023/9/1第4章语法制导的翻译774.3L属性定义的自上而下计算边分析边翻译的方式能否用于继承属性？属性的计算次序受分析方法所限定的分析树结点建立次序的限制2023/9/1第4章语法制导的翻译784.3L属性定义的自上而下计算边语法分析边翻译的方式能否用于继承属性？属性的计算次序受分析方法所限定的分析树结点建立次序的限制语法分析方法的共同特点：分析树的结点是自左向右生成如果属性信息自左向右流动，那么就有可能在分析的同时完成L属性计算L代表属性从左向右传递的方向2023/9/1第4章语法制导的翻译79（1）如果每个产生式A

X1

X2…Xj…Xn

的每条语义规则计算的属性是A的综合属性；或者（2）如果是Xj

的继承属性，1

j

n,但它仅依赖于：该产生式中Xj左边（兄弟结点）符号X1,X2,…,Xj-1的属性A的继承属性 那么语法制导定义是L属性定义4.3.1L属性定义2023/9/1第4章语法制导的翻译80（1）如果每个产生式A

X1

X2…Xj…Xn

的每条语义规则计算的属性是A的综合属性；或者（2）如果是Xj

的继承属性，1

j

n,但它仅依赖于：该产生式中Xj左边（兄弟结点）符号X1,X2,…,Xj-1的属性A的继承属性 那么语法制导定义是L属性定义S属性定义是L属性定义的一个特例2023/9/1第4章语法制导的翻译81例：变量类型声明的语法制导定义是一个L属性定义

产生式

语

义

规

则

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

2023/9/1第4章语法制导的翻译82计算属性需要考虑执行语义规则的时机翻译方案将语义动作放在{}内，并将它当作文法符号插入产生式右部任何位置语义动作插入的位置就是产生式的项目中的点的位置执行时机：当语法分析到该文法符号（语义动作）而进行推导或归约时，执行该语义动作4.3.2翻译方案什么是项目？2023/9/1第4章语法制导的翻译83只有综合属性的翻译方案的建立 首先为每条语义规则建立一个放在一对{}括号内赋值动作，然后把这些动作分别放在对应产生式右部的末端2023/9/1第4章语法制导的翻译84例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)}

2023/9/1第4章语法制导的翻译85例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}

R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章语法制导的翻译86例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章语法制导的翻译87例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

2023/9/1第4章语法制导的翻译88例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

关注动作2023/9/1第4章语法制导的翻译89例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

关注动作2023/9/1第4章语法制导的翻译90例:把有加和减的中缀表达式翻译成后缀表达式 如果输入是8+5

2，则输出是85+2

E

TR

R

addopT{print(addop.lexeme)}R1|

T

num{print(num.val)} E

TR

num{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print(

)}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}

关注动作2023/9/1第4章语法制导的翻译91有继承属性的翻译方案的建立

建立含有继承属性翻译方案的规则： （1）产生式右部符号的继承属性必须在先于该符号的动作中计算 （2）一个动作不能引用该动作右边符号的综合属性

（3）左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算，且计算该属性的动作通常放在产生式右部末端2023/9/1第4章语法制导的翻译92例：数学排版语言EQN

Esub1.valS

BB

B1B2

B

B1

subB2B

textE1.valS

BB1B2B1subB2B2textsubtexttext2023/9/1第4章语法制导的翻译93例：数学排版语言EQN（B.ps为继承属性）

Esub1.val产

生

式

语

义

规

则

S

B

B.ps:=10;S.ht:=B.ht

B

B1B2

B1.ps:=B.ps;B2.ps:=B.ps;B.ht:=max(B1.ht,B2.ht)B

B1

subB2

B1.ps:=B.ps;B2.ps:=shrink(B.ps);B.ht:=disp(B1.ht,B2.ht)B

text

B.ht:=text.h

*B.ps

E1.val2023/9/1第4章语法制导的翻译94例：数学排版语言EQN（B.ps为继承属性）

S

{B.ps:=10} B {S.ht:=B.ht}

B

{B1.ps:=B.ps}

B1 {B2.ps:=B.ps}

B2 {B.ht:=max(B1.ht,B2.ht)}

B

{B1.ps:=B.ps}

B1 sub {B2.ps:=shrink(B.ps)} B2 {B.ht:=disp(B1.ht,B2.ht)}

B

text {B.ht:=text.h

*B.ps}规则一规则三2023/9/1第4章语法制导的翻译95例：左递归的消除可能引起继承属性(可能原 来只有综合属性）-算术表达式语法制导定义产生式语

义

规

则

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

E

T

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F

(E)

F.nptr:=E.nptr

F

id

F.nptr:=mkleaf(id,id.entry)

F

num

F.nptr:=mkleaf(num,num.val)

2023/9/1第4章语法制导的翻译96 算术表达式文法

E

E+T|T

T

T

*

F|F

F

(E)|id 消除左递归后文法：

E

TR R

+TR1

|

T

FW

W

*

FW1

|

F

(E)|idA

Aa|b消除直接左递归：A

bA

A

aA

|

其中：R和W为引入的辅助文法符号2023/9/1第4章语法制导的翻译97E

T {R.i:=T.nptr}

R

{E.nptr:=R.s}R

+ T {R1.i

:=mknode(‘+’,R.i,T.nptr)}

R1

{R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr}

W

{T.nptr:=W.s}W

* F {W1.i

:=mknode(‘*’,W.i,F.nptr)}

W1

{W.s:=W1.s}W

{W.s:=W.i}F

(E) {F.nptr:=E.nptr}F

id {F.nptr:=mkleaf(id,id.entry)}F

num {F.nptr:=mkleaf(num,num.entry)}R和W的i属性是继承属性2023/9/1第4章语法制导的翻译98E

T {R.i:=T.nptr} R {E.nptr:=R.s}R

+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=W.s}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}F

(E) {F.nptr:=E.nptr}F

id {F.nptr:=mkleaf(id,id.entry)}F

num {F.nptr:=mkleaf(num,num.entry)}2023/9/1第4章语法制导的翻译99用算术表达式语法制导定义构造a*5*b语法树12345678910111213141516TF.nptrF.nptridi

W**F.nptridnumididnum5**指向符号表中a的入口指向符号表中b的入口i

W

siW

略去了E

TR

T

部分递归：自上而下从左到右推导而非归约2023/9/1第4章语法制导的翻译100把预测分析器的构造方法推广到翻译方案的 实现（每个非终结符都对应一个过程或函数）——参见p126算法4.1）：适用于自上而下分析例：产生式R

+TR|

的分析过程： procedureR; begin iflookahead=‘+’thenbegin match(‘+’);T;R end elsebegin/*

什么也不做*/ end end

4.3.3预测分析器的设计预测分析器的特点？2023/9/1第4章语法制导的翻译101产生式R

+TR|

的语法树的递归下降构造：functionR(i:

syntax_tree_node):

syntax_tree_node; var nptr,i1,s1,s:

syntax_tree_node;

addoplexeme:char; begin iflookahead=‘+’thenbegin /*

匹配产生式R

+TR

*/ addoplexeme:=lexval;/*

载入运算符*/ match(‘+’); nptr:=T;

i1:=mknode(addoplexme,i,nptr);

s1:=R(i1);

s:=s1 end elses:=i;/*

产生式

R

*/ returns end;R:i,sT:nptr+:addoplexeme2023/9/1第4章语法制导的翻译102改变文法可能导致继承属性或综合属性例如：消除左递归可能产生继承属性

Pascal的声明，如m,n:integer D

L:T

T

integer|char

L

L,id|id4.3.4用综合属性代替继承属性2023/9/1第4章语法制导的翻译103Pascal的声明，如m,n:integer D

L:T

T

integer|char

L

L,id|id改成从右向左归约 D

idL

L

,idL|:T

T

integer|char2023/9/1第4章语法制导的翻译104Pascal的声明，如m,n:integer D

L:T

T

integer|char

L

L,id|id改成从右向左归约 D