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

语法制导翻译中间代码生成概述语义处理程序设计语言的语义

静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类类型相容性变量先声明后引用名称相关要求

动态语义

程序单位描述的计算编译程序的语义处理工作静态语义审查解释执行动态语义（计算）生成代码...语

法

分

析

后

的

源

程

序

Þ

语义处理第2页,共126页，2024年2月25日，星期天概述语义形式化语义建模文法模型----属性文法命令式或操作式模型-----操作语义学应用式模型-----指称语义学公理式模型-----公理语义学第3页,共126页，2024年2月25日，星期天属性文法

表达式文法E—>T+T|TorT

T—>n|bE

T1+T2

{T1.type=intT2.type=T1.type E.type:=int}E

T1orT2

{T1.type=bool T2.type=T1.typeE.type:=bool}T

n{T.type:=int}T

b{T.type:=bool}第4页,共126页，2024年2月25日，星期天

操作语义描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。For(expr1;expr2;expr3){expr1;

...Loop:ifexpr2=0gotoout}…

expr3;

gotoloopout:...第5页,共126页，2024年2月25日，星期天公理语义一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。一般的记号{P}S{Q}如果在语句S执行前P为真，则在语句S执行并终止后Q为真。

第6页,共126页，2024年2月25日，星期天

演绎规则的例子规则前驱后继赋值：x:=expr{P(expr)}x:=expr{P(x)}While:{P∧B}S{P}{P}whileBdoSend{P∧(notB)}

if--then--else {B∧P}S1{Q},{(notB)∧P}S2{Q}{P}ifBthenS1

elseS2{Q}第7页,共126页，2024年2月25日，星期天指称语义指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数特点：不但对全部程序赋予全文而且对程序设计语法 每一个语法成分短语（表达式，命令，声明…） 都给予含义。每一个语法成分（短语）的含义是以它的自 成分的含义的术语来定义的。即语义结构平行于语法结构。语义函数：程序设计语言的语义利用映射函数来证 明。语义函数将短语映射到它的指称。第8页,共126页，2024年2月25日，星期天

例：二进制数语言110或10101语法实体指称（自然数）6或21语义实体二进制数文法Numeral::=0

::=1

::=Numeral0

::=Numeral1

自然数Natrual={0,1,2,3,…}

语义函数Valuation:NumeralNatural第9页,共126页，2024年2月25日，星期天Valuation[101]表示把Valuation施用于101Valuation[N]------把它施用于N

定义:Valuation（用四个方程)因为有四个形式numeralValuation[0]

0Valuation[1]

1Valuation[N0]

2

Valuation[N]Valuation[N1]

2

Valuation[N]+1

所以：Valuation[110]=2

Valuation[11]=2

(2

Valuation[1]+1)=2

(2

1+1)=6第10页,共126页，2024年2月25日，星期天属性文法和语法制导翻译虽然形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法第11页,共126页，2024年2月25日，星期天属性文法属性文法(attributegrammar)是一个三元组:A=(G,V,F),其中G:是一个上下文无关文法V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等.属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F:关于属性的属性断言或一组属性的计算规则(称为语义规则).断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.

第12页,共126页，2024年2月25日，星期天属性有两种继承的和综合的属性属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由生计算器的参数提供。

AX1X2…XnA的综合属性,计算S(A):=f(I(X1),…,I(Xn))Xj的继承属性,计算T(Xj):=f(I(A),...I(Xn))1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性.2)终结符只有综合属性.第13页,共126页，2024年2月25日，星期天在一个属性文法中，对应于每个产生式A

都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2…ck)这里，f是一个函数，而且或者 （1）b是A的一个综合属性并且c1,c2…ck是产生式右边文法符号的属性;或者 （2）b是产生式右边某个文法符号的一个继承属性并且c1,c2…ck是A或产生式右边任何文法符号的属性。在两种情况下，我们都说属性b依赖于属性c1,c2…ck

。第14页,共126页，2024年2月25日，星期天

一个属性文法的例子例8.1

非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式L→En对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现语义规则

LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)

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

E.val:=T.val

T.val:=T1.val

F.val

T.val:=F.valF.val:=E.valF.val:=digit.lexval产生式第15页,共126页，2024年2月25日，星期天设表达式为3＊5+4，则语义动作打印数值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树第16页,共126页，2024年2月25日，星期天继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例8.2继承属性L.in生产式语义规则D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)第17页,共126页，2024年2月25日，星期天

DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Realid1,id2,id3，，第18页,共126页，2024年2月25日，星期天例8.3P–>DSD–>varV;D|

S–>V:=E;S|

V–>x|y|z现在使用两个属性，name和dl，每当一个新的变量声明时，就把它的name属性附给它，name属性是综合属性。将所声明的变量都放到一个变量名字清单中（用语义函数addlist实现），用属性dl综合声明块中声明的所有变量。然后这个dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中P–>DS{S.dl=D.dl}D1–>varV;D2|

{D1.dl=addlist(V.name,D2.dl)}|{D1.dl=NULL}S1–>V:=E;S2|

{check(V.name,S1.dl);S2.dl=S1.dl}V–>x|y|z{V.name='x'}|{V.name='y'}|{V.name='z'}第19页,共126页，2024年2月25日，星期天varx；vary；x:=e；

PDdl={x,y}S

dl={x,y}varV；Ddl={y}V:=e；S

xvarV；Ddl={}y

y

第20页,共126页，2024年2月25日，星期天语法制导的翻译一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）设

是输入字母表且

是输出字母表。定义由语言L1*到语言L2*的一个翻译是由*到*的一个关系T,使得T的定义域为L1且T的值域为L2。使(x,y)∈T的句子y叫做x的一个输出.第21页,共126页，2024年2月25日，星期天语法制导的翻译直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。例8.4：下列翻译模式，它定义翻译，即对每个输入x，其输出y是x的逆转。定义此翻译的规则是产生式

翻译规则(1)s

0s(2)s

1s(3)s

ε

(1)s=s0(2)s=s1

(3)s=ε

第22页,共126页，2024年2月25日，星期天

输入输出对可由(,)表示，其中

是输入句子形式而

是输出句子形式。(S,S)开始用产生式s

0s来扩展得到(0S,S0).再用一次规则(1)，得到(00S,S00)。再用规则(2)，就得到(001S,S100).然后应用规则(3)并得到(001,100)。第23页,共126页，2024年2月25日，星期天

例8.5：把下述产生式定义的算术表达式映射到后缀波兰表示：

EE+TET

TT

FTF

F(E)

Fa

E=ET+

E=T

T=TF

T=F

F=E

F=a产生式

翻译规则第24页,共126页，2024年2月25日，星期天

确定输入a+a

a的输出：

(E,E)(E+T,ET+)

(T+T,TT+)

(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)第25页,共126页，2024年2月25日，星期天

定义：一个语法制导的翻译模式是一个五元组T=(N,,，R,S),其中

(1)N是非终结符的有限集。

(2)

是有限的输入字母表。

(3)

是有限的输出字母表。

(4)R是形如A,的规则的有限集,其中

∈(N∪

)*,∈(N∪

)*且

中那组非终结符是中那组非终结符的置换。

(5)S是N中一个特别的非终结符，即开始符。第26页,共126页，2024年2月25日，星期天

定义：若T=(N,,,R,S)是SDTS,(T)则称为语法制导的翻译(SDT)，文法Gi=(N,

,P,S)，其中P={A|A,属于R)，称为SDTST的基础（或输入）文法。文法G0=(N,,P,S),，其中P={A|A,属于R}，称为T的输出文法。把语法制导的翻译方法看成是将输入文法Gi中的推导树变换成输出文法G0中的推导树。给了输入句子x，可以按如下方式得到x的一个翻译：先为推导x构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为x的一个翻译。第27页,共126页，2024年2月25日，星期天语义制导翻译中的规则A,

对应于每一个文法产生式A

都有与之相关联的一套语义描述

属性文法(attributegrammar)是一个三元组:A=(G,V,F)属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来第28页,共126页，2024年2月25日，星期天语法制导翻译实现从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串

分析树

属性依赖图

语义规则的计算顺序

第29页,共126页，2024年2月25日，星期天依赖图由称为依赖图的一个有向图描述分析树中的继承属性和属性中间的相互依赖关系。

依赖图的构造算法：

for分析树中每一个结点ndo

for

结点的文法符号的每一个属性ado

为a在依赖图中建立一个结点；

for

分析树中每一个结点ndo

for结点n所用产生式对应的每一个语义规则

b:=f(c1,c2,…ck)do

fori:=1tokdo

从ci结点到b结点构造一条有向边

第30页,共126页，2024年2月25日，星期天依赖图----例8.2例8.2继承属性L.in生产式语义规则D

TL

T

int

T

real

L

L1,idL

idL.in:=T.typeT.type=integerT.type:=real

L1.in:=L.in

addtype(id.entry,L.in)

addtype(id.entry,L.in)第31页,共126页，2024年2月25日，星期天例8.2Realid1,id2,id3分析树的依赖图

5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1..1第32页,共126页，2024年2月25日，星期天依赖图中的结点由数字来标识。从代表T.type的结点4有一条有向边连到代表L.in的结点5，因为根据产生式E→TL的语义规则L1.in=L.in，可知L1.in依赖于L.in，所以有两条向下的有向边分别进入结点7和9。每一个与L产生式有关的语义规则addtype(id.Entry,L.in)都产生一个虚属性，结点6、8和10都是为这些虚属性构造的。第33页,共126页，2024年2月25日，星期天良定义的属性文法。

很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。从事贸易如，p、c1、c2都是属性，若有下求值规则：p:=f1(c1)、c1:=f2(c2)、c2:=f3(p)时，就无法对p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。第34页,共126页，2024年2月25日，星期天属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,…,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点，语义规则b:=f(c1,c2,…ck)中的属性c1,c2,…ck在计算b以前都是可用的。第35页,共126页，2024年2月25日，星期天属性文法说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。例8.2Realid1,id2,id3分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用an来代表依赖图中与序号n的结点有关的属性： a4:=real a5:=a4

addtype(id3,entry,a5); a7:=a5; addtype(id2,entry,a7) a9:=a7

addtype(id1,entry,a9)这些语义规则的计算将把real类型填入到每个标识符对应的符号表项中。第36页,共126页，2024年2月25日，星期天

属性计算方法树遍历的属性计算方法

设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。一遍扫描的处理方法与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无无需构造实际的语法树。因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：（1）所采用的语法分析方法（2）属性的计算次序。第37页,共126页，2024年2月25日，星期天例：定义定点二进制数的CFG:(1)N

S•S(2)S

SB(3)S

B(4)B

0(5)B

1

第38页,共126页，2024年2月25日，星期天非终结符N表示整个二进制数的数值，综合属性v附加在N上：Nv非终结符B表示一个二进制数字，它有自己的值v，但该值分配给N的值与它的位置有关，是与2成比例，比例因子f是从S继承的属性,所以：Bvf非终结符S表示一个二进制数字串，它也有值，但该值与串的位置有关，与f有关与串的长度l有关:Sfvl第39页,共126页，2024年2月25日，星期天构造数值的属性断言可以如下:

Nv——>Sf1v1l1•Sf2v2l2[v=v1+v2;f1=1;f2=2-l2]Sfvl——>Sf1v1l1Bf2v2[f1=2f;f2=f;v=v1+v2;l=l1+1]——>Bfv[l=1]Bfv——>0[v=0]——>1[v=f]第40页,共126页，2024年2月25日，星期天

N

v

S

i1

l1“•”S

i2

l2[v=i1+2-l2•i2]

S

i

l

S

i1

l1B

i2[i

=2i1+i2;;l=l1+1]

B

i[l=1]

B

i

“0”[i=0]

“1”[i=1]第41页,共126页，2024年2月25日，星期天

在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的s-属性

适用于自底向上的计算L-属性适用于自顶向下的分析，也可用于自底向上。

第42页,共126页，2024年2月25日，星期天S－属性文法的自下而上计算S－属性文法，它只含有综合属性。综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。S－属性文法的翻译器通常可借助于LR分析器实现。在S－属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。第43页,共126页，2024年2月25日，星期天产生式语义规则０）Ｌ→Ｅｐｒｉｎｔ（Ｅ.ｖａｌ）１）Ｅ→Ｅ1＋ＴＥ.ｖａｌ∶＝Ｅ1.ｖａｌ＋Ｔ.ｖａｌ２）Ｅ→ＴＥ.ｖａｌ∶＝Ｔ.ｖａl３）Ｔ→Ｔ1*ＦＴ.ｖａｌ∶＝Ｔ1.ｖａｌ×Ｆ.ｖａｌ４）Ｔ→FＴ.ｖａｌ∶＝F.ｖａｌ５）Ｆ→（Ｅ）Ｆ.ｖａｌ∶＝Ｅ.ｖａｌ６）Ｆ→ｄiｇiｔＦ.ｖａｌ:＝ｄｉｇｉｔ.ｌｅｘｖａｌLR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。

LR分析器增加语义栈

第44页,共126页，2024年2月25日，星期天

２＋３*５的分析和计值过程步骤动作状态栈语义栈(值栈)符号栈余留输入串１）０－＃２＋3*５＃２）０５－－＃２＋3*５＃３）ｒ６０３－２＃Ｆ＋３*５＃４）ｒ４０２－２＃Ｔ＋３*５＃５）ｒ２０１－２＃Ｅ＋３*５＃６）０１６－２－＃Ｅ＋３*５＃７）０１６５－２－－＃Ｅ＋３*５＃８）ｒ６０１６３－２－３＃Ｅ＋Ｆ*５＃９）ｒ４０１６９－２－３＃Ｅ＋Ｔ*５＃１０）０１６９７－２－３－＃Ｅ＋Ｔ*５＃１１）０１６９７５－２－３－－＃Ｅ＋Ｔ*５＃１２）ｒ６０１６９７（１０）－２－３－５＃Ｅ＋Ｔ*Ｆ#１３）ｒ３０１６９－２－（１５）＃Ｅ＋Ｔ＃１４）ｒ１０１－（１７）＃Ｅ＃１５）接受第45页,共126页，2024年2月25日，星期天BOTTOM—UP语义处理是作类型检查，对二目运算符的运算对象进行类型匹配审查。(LR分析）：增加语义栈归约时进行语义动作.例8.7G[E]:(1)ET+T(2)ETorT(3)Tn(4)Tb

第46页,共126页，2024年2月25日，星期天E

T1+T2

{ifT1.type=intandT2.type=intthenE.type:=int

elseerror}

E

T1orT2

{ifT1.type=boolandT2.type=boolthenE.type:=bool

elseerror}T

n{T.type:=int}T

b{T.type:=bool}

第47页,共126页，2024年2月25日，星期天

G[E]:(1)ET+T(2)ETorT(3)Tn(4)Tb第48页,共126页，2024年2月25日，星期天第49页,共126页，2024年2月25日，星期天L－属性文法和自顶向下翻译一个属性文法称为L－属性文法，如果对于每个产生式A→X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1≤j≤n）的一个继承属性且这个继承属性仅依赖于：（1）产生式Xj在左边符号X1，X2，…，Xj-1的属性；（2）A的继承属性。S－属性文法一定是L－属性文法，因为（1）、（2）限制只用于继承属性。L－属性文法允许一次遍历就计算出所有属性值。LL（1）这种自上而下分析文法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现L属性文法的计算。第50页,共126页，2024年2月25日，星期天例（中缀表达式翻译成相应的后缀表达式）

E→TR

R→addopT{print(addop.Lexeme)}R1|ε

T→num{print(num.val)}

翻译模式（Translationschemes）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号｛｝括起来，插入到产生式右部的合适位置上。第51页,共126页，2024年2月25日，星期天输入串9－5+2的语法树，每个语义动作都作为相应产生式左部符号的结点的儿子，按深度优先次序执行图中的动作后，打印输出95－2+。

ETR9print(‘9’)-Tprint(‘-’)R5print(‘5’)+Tprint(‘+’)R2print(‘2’)ε第52页,共126页，2024年2月25日，星期天L－属性文法在自顶向下分析中的实现

带左递归的文法的翻译模式E→E1+T {E.val:=E1.val+T.val}E→E1－T {E.val:=E1.val－T.val}E→T {E.val:=T.val}T→(E) {T.val:=E.val}T→num {T.val:=num.val}

第53页,共126页，2024年2月25日，星期天消除左递归的同时考虑属性，构造新的翻译模式

E→T {R.i:=T.val}R {E.val:=R.s}R→+T {R1.i:=R.i+T.val}R1 {R.s:=R1.s}R→-T {R1.i:=R.i-T.val}R1 {R.s:=R1.s}R→ε {R.s:=R.i}T→(E){T.val:=E.val}T→num {T.val:=num.val}第54页,共126页，2024年2月25日，星期天计算表达式9-5+2.ER.i=9T.val=5T.val=9R.i=4

R.i=6T.val=2num.val=9num.val=5num.val=2_+

第55页,共126页，2024年2月25日，星期天在上页的翻译模式中，每个数都是由T产生的，并且T.val的值就是由属性num.val给出的数的词法值。子表达式9－5中的数字9是由最左边的T生成的，但是减号和5是由根的右子结点R生成的。继承属性R.i从T.val得到值9。计算9－5并把结果4传递到中间的R结点这是通过产生式中嵌入的下面动作实现：{R1.i:=R.i－T.val}类似的动作把2加到9－5的值上，在最下面的R结点处产生结果R.i＝6。这个结将成为根结点处E.val的值,R的综合属性s在图中没有表示出来，它用来向上复制这一结果一直到树根。

第56页,共126页，2024年2月25日，星期天对于自顶向下分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。如图中的第二个产生式中，第一个动作（对R1.i赋值）是在T被完全展开成终结符号后执行的，第二个动作是在R1被完全展开成终结符号后执行的。正如前面我们所讨论的，一个符号的继承属性必须由出现在这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。第57页,共126页，2024年2月25日，星期天转换左递归翻译模式的方法推广到一般

假设翻译模式1：A→A1Y {A.a:=g(A1。a,Y.y)}A→X {A.a:=f(X.x)} 每个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数消除左递归，文法转换成：A→XRR→YR｜ε 再考虑语义动作，翻译模式变为2A→X {R.i:=f(X.x)}R {A.a:=R.s}R→Y {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s}R→ε {R.s:=R.i}第58页,共126页，2024年2月25日，星期天翻译模式1和翻译模式2的结果是一样的。可以给出串XY1Y2两棵带注释的语法树看出来，一棵是根据翻译模式1自下而上计算属性的。一棵是根据翻译模式2自上而下计算的。第59页,共126页，2024年2月25日，星期天

A→A1Y {A.a:=g(A1。a,Y.y)}

A→X {A.a:=f(X.x)}

A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X.x,Y1.y)Y2A.a=f(X.x)Y1X

AAYAYX第60页,共126页，2024年2月25日，星期天

A→X{R.i:=f(X.x)}R→Y {R1.i:=g((R.i),Y.y)}

R{A.a:=R.s}

R1{R.s:=R1.s}

A→XRR→YR｜εAXRY1RY2R

AXR.i=f(X.x)Y1R.i=g(f(X.x,Y1.y)Y2R.i=g(g(f(X.x,Y1.y),Y2.y)

第61页,共126页，2024年2月25日，星期天思考问题-把建立语法树的翻译模式变换成适合预测分析的模式E

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

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

T{E.nptr:=T.nptr)第62页,共126页，2024年2月25日，星期天自下而上计算继承属性讨论在自下而上的分析过程中实现L－属性文法的方法。这种方法可以实现任何基于LL（1）文法的L－属性文法，它还可以实现许多（不是所有）基于LR（1）文法的L－属性文法。这种方法是S-属性文法的自下而上翻译技术的一般化第63页,共126页，2024年2月25日，星期天自下而上分析器对产生式A→XY的右部是通过把X和Y从分析栈中移出并用A代替它们。假设X有一个综合属性X.s，按照前面所介绍的方法我们把它与X一起放在分析栈中。由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。也就是说，如果继承属性Y.i是由复写规则Y.i:=X.s定义的，则可以在需要y.i值的地方使用X.s的值。在自下而上分析中计算属性值时复写规则起非常重要的作用。看下面例子。第64页,共126页，2024年2月25日，星期天假设某翻译模式为：D→T {L.in:=T.type}LT→int {T.type:=integer}T→real {T.type:=real}L→ {L1.in:=L.in}L1,id {addtype(id.entry,L.in)}L→id {addtype(id.entry,L.in)}第65页,共126页，2024年2月25日，星期天回顾例8.2Realid1,id2,id3分析树的依赖图

5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1..1第66页,共126页，2024年2月25日，星期天例8.2输入串realRealid1,id2,id3的分析过程当L的右部被归约时，T恰好在这个右部的下面输入状态(符号）使用产生式Realid1,id2,id3#id1,id2,id3#realid1,id2,id3#TT

real,id2,id3#Tid1,id2,id3#TLL

idid2,id3#TL,,id3#TL,id2,id3#TLL

Li,did3#TL,#TL,id3#TLL

Li,d#DD

TL第67页,共126页，2024年2月25日，星期天

用综合属性代替继承属性有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如,m,n:integer。这样的说明的文法可由下面形式的产生式构成D→L：TT→integer|charL→L,id|id因为标识符由L产生而类型不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符L从第一个产生式中它的右边T中继承了类型，则我们得到的属性文法就不是L－属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。第68页,共126页，2024年2月25日，星期天一个解决的方法是重新构造文法使类型作为标识符表的最后一个元素：D→idLL→,idL|:TT→integer|char这样，类型可以通过综合属性L.type进行传递，当通过L产生每个标识符时，它的类型就可以填入到符号表中。

第69页,共126页，2024年2月25日，星期天语义制导翻译的编译实现:例8.6E–>TE'E'–>ATE'|

T–>FT'T'–>MFT'|

F–>(E)|intA–>+|-M–>*|/第70页,共126页，2024年2月25日，星期天E->TE'E'->ATE'{rhs=PopOperand();lhs=PopOperand();switch(PopOperator()){caseADD:PushOperand(lhs+rhs);break;caseSUB:PushOperand(lhs-rhs);break;}}|

{/*empty,donothing*/}T->FT'T'->MFT'{rhs=PopOperand();lhs=PopOperand();switch(PopOperator()){caseMUL:PushOperand(lhs*rhs);break;caseDIV:PushOperand(lhs/rhs);break;}}|

{/*empty,donothing*/}A->+{PushOperator(ADD);}|-{PushOperator(SUB);}M->*{PushOperator(MUL);}|/{PushOperator(DIV);}F->int{PushOperand(intval);}|(E){/*handledduringparsingofE*/}第71页,共126页，2024年2月25日，星期天parse2+4*3:分析动作桥分析栈运算对象栈运算符栈PredictE–>TE‘E#PredictT–>FT'TE‘#PredictF–>intFT'E‘#MatchintintT'E‘#PredictT'–>

T'E‘#2PredictE'–>ATE'ATE'#2PredictA–>+ATE‘#2Match++TE‘#2PredictT–>FT'TE‘#2+PredictF–>intFT'E‘#2+MatchintintT'E‘#2+PredictT'–>MFT'T'E‘#42+PredictM–>*MFT'E‘#42+Match**FT'E‘#42+PredictF–>intFT'E‘#42*+MatchintintT'E‘#42*+PredictT'–>

T'E‘#342*+PredictE'–>

E‘#122+Success!#14第72页,共126页，2024年2月25日，星期天Yacc或bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号$$表示产生式左端的属性，$n表示存取产生式右端第n个文法符号相联的属性如例8.3作为Yacc的输入，可写成：P→DS{$2.dl=$1.dl}D1→varV；D{$$.dl=addlist($2.name，$4.dl)}|{$$.dl=null}S1→V:=e；S{check($1.name，$$.dl)；

$5.dl=$$.dl}|V→x{$$.name=’x’}|y{$$.name=’y’}|z{$$.name=’z’}第73页,共126页，2024年2月25日，星期天如果数据结构attribute定义属性name和dl，可以具体化为：

typestruct_attribute{

char*name；

struct_attribute*list；

}attribute；

P→DS{$2.list=$1.list}D1→varV；D{$$.list=add_to_list($2.name，$4.list)}|{$$.list=null}S1→V:=e；S{check($1.name，$$.list)；

$5.list=$$.list}|V→x{$$.name=’x’}|y{$$.name=’y’}|z{$$.name=’z’}第74页,共126页，2024年2月25日，星期天语义分析语义分析属性文法和语法制导翻译方法和技术应用于语义分析中。第75页,共126页，2024年2月25日，星期天语义分析通常包括：（1）类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。（3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。（4）相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。

(5)名字的作用域分析第76页,共126页，2024年2月25日，星期天类型和声明（Typesanddeclarations）一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型:基本类型：int,float,double,char,bool等等.也可能允许在基本类型基础上用户自己定义的类型，如枚举型.复合类型：数组,指针，记录/结构/联合,类等等.这些类型由基本类型构成.复杂类型：链表，栈，队，树，堆，表格等等.可以把它们组织成ADT.一个语言不一定支持这类高级的抽象。声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传给编译，声明的地方传递生命周期信息也有些语言允许声明初始化变量。如:doublecalculate(inta,doubleb);//functionprototypeintx=0;//globalvariablesavailablethroughoutdoubley;//theprogramintmain(){intm[3];//localvariablesavailableonlyinmainchar*n;...}第77页,共126页，2024年2月25日，星期天强类型的-任何数据类型都可以在编译时确定弱类型的.进行类型检查的时间：编译时，运行时，或者两者结合.静态类型检查编译时进行类型检查动态类型检查，将类型信息并到运行时每个数据单元中.隐含类型转换.第78页,共126页，2024年2月25日，星期天P→D；ED→D；|id:TT→char|integer|aray[num]ofT|↑TE→literal|num|id|EmodE|E[E]|E↑P代表程序；D代表说明；E代表表达式。如程序语句：key:integer;keymod1999语言本身提供两种基本类型：char和integer。除此之外还有缺省的基本类型type_error和void。假定所有数组都从下标1开始第79页,共126页，2024年2月25日，星期天确定标识符类型的部分翻译模式（1）P→D；E（2）D→D；D（3）D→id:T{addtype(id.Entry,T.type)}（4）T→char{T.Type:=char}（5）T→integer{T.Type:=integer}（6）T→↑T1{T.Type:=pointer(T1.type)}（7）T→array[num]ofT1

{T.Type:=array(num.Val,T1.type)}第80页,共126页，2024年2月25日，星期天

语句的类型检查的翻译模式S→id:=E{ifid.Type=E.TypeThenS.Type:=voidelseS.Type:=type_error}S→ifEthenS1{ifE.type=booleanthenS.Type:=S1.typeelseS.type:=type_error}S→whileEdoS1{ifE.type=booleanThenS.type:=S1.TypeelseS.type:=type_error}第81页,共126页，2024年2月25日，星期天设计类型检查程序1.辨认语言中可用的类型2.辨认具有类型的语言结构3.辨认语言的语义规则第82页,共126页，2024年2月25日，星期天InDecaf

basetypes：int,double,bool,stringcompoundtypes：arraysandclasses.Anarraycanbemadeofanytype(eitherabasetype,aclass,oroutofotherarrays).Classesareabitspecialinthattheclassnamemustbedeclaredbeforeitcanbeusedinadeclaration.ADTscanbeconstructedusingclasses,buttheyaren’thandledinanywaydifferentlythanclasses,sowedon’tneedtoconsiderthemspecially.第83页,共126页，2024年2月25日，星期天InDecaftherelevantlanguageconstructsconstants,everyconstanthasanassociatedtype.Ascannertellsusthesetypesaswellastheassociatedlexeme.variables：allvariables(global,