中国科学技术大学陈意云编译原理全套参考资料chapter4.docx
- 文档编号:16099355
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:42
- 大小:37.71KB
中国科学技术大学陈意云编译原理全套参考资料chapter4.docx
《中国科学技术大学陈意云编译原理全套参考资料chapter4.docx》由会员分享,可在线阅读,更多相关《中国科学技术大学陈意云编译原理全套参考资料chapter4.docx(42页珍藏版)》请在冰点文库上搜索。
中国科学技术大学陈意云编译原理全套参考资料chapter4
中国科学技术大学陈意云编译原理全套参考资料chapter4
第四章语法制导的翻译
在3.7节用Yacc写的例子中,我们看到一种有用的描述形式:
语言结构的属性附加在代表语言结构的文法符号上,这些属性值由附加在文法产生式的语义动作来计算,这些语义动作在归约对应的产生式时进行计算,由此得到结果。
这种描述形式可用来描述编译器的语义分析,因此本章系统地研究这种称之为“语法制导下的语言翻译”的描述方法及其实现。
它的语义动作(有时称为语义规则)的计算可以产生代码、把信息存入符号表、显示出错信息、或完成其它工作。
语义规则的计算结果就是我们所要的记号流的翻译。
本章讨论语义规则和产生式相联系的两种方式:
语法制导的定义和翻译方案。
语法制导定义是较抽象的翻译说明,它隐蔽了一些实现细节;而翻译方案陈述了一些实现细节,主要是指明了语义规则的计算次序。
在第五章说明语义检查和第七章描述中间代码生成时,大量使用这两种方法。
本章还讨论语法制导定义和翻译方案的实现方法。
概念上的方法是,首先分析输入的记号串,建立分析树,然后从分析树得到描述结点属性间依赖关系的有向图,从这个依赖图得到语义规则的计算次序,然后进行计算,最终得到翻译的结果。
实际的实现并不需要按上面步骤逐步进行,本章将讨论几种不同限制下的实现方法。
4.1语法制导的定义
语法制导的定义是上下文无关文法的推广,其中每个文法符号都有一个属性集合,它分成两个子集,分别叫做该文法符号的综合属性集合和继承属性集合。
如果我们把分析树上的结点看成是保存对应文法符号的属性的记录,那么属性对应记录的域。
属性可以表示任何东西:
串、数、类型、内存单元,或其它想表示的东西。
分析树结点的属性值由该结点所用产生式的语义规则定义。
在语法制导定义中,我们把其中的文法称为基础文法。
本节介绍语法制导定义的形式及其概念上的实现模型。
4.1.1语法制导定义的形式
在语法制导定义中,每个文法符号有一组属性,每个文法产生式A,,有一组形式为b:
=f(c,c,…,c)的语义规则,其中f是函数,b和c,c,…,c是该产生式的文法符号的12k12k
属性,并且:
(1)如果b是A的属性,c,c,…,c是产生式右部文法符号的属性或A的其它属12k
性,那么b叫做文法符号A的综合属性。
(2)如果b是产生式右部某个文法符号X的属性,c,c,…,c是A的属性或右部12k
文法符号的属性,那么b叫做文法符号X的继承属性。
在这两种情况下,我们都说属性b依赖于属性c,c,…,c。
每个文法符号的综合属性12k
集和继承属性集的交集应为空。
一般来说,结点的综合属性的值是通过分析树中它子结点的属性值来计算;继承属性的值由结点的兄弟结点和父结点的属性值来计算。
语义规则函数通常是表达式。
有时,语法制导定义中某些规则的目的是要产生副作用,如打印值或修改全程量,这样的语义规则写成过程调用或程序段。
可以把它们想象成定义了产生式左部非终结符的一个虚拟综合属性,这个虚拟属性和符号:
=在该规则中没有显式表示出来。
属性文法是指语义规则函数无副作用的语法制导定义。
例4.1图4.1的语法制导定义表示一个台式计算器程序。
这个定义分别给非终结符E、
1
T和F一个存放整数值的综合属性val。
对每个E、T和F产生式,语义规则从产生式右部非终结符的属性值val(或digit的lexval)计算产生式左部非终结符的属性值val。
表4.1简单台式计算器的语法制导定义
产生式语义规则
L,Enprint(E.val)
E,E+TE.val:
=E.val+T.val11
E,TE.val:
=T.val
T,T*FT.val:
=T.val*F.val11
T,FT.val:
=F.val
F,(E)F.val:
=E.val
F,digitF.val:
=digit.lexval
记号digit有综合属性lexval,它的值由词法分析器提供。
产生式L,En的语义动作是打印由E产生的算术表达式的值,我们把它看成定义了L的一个虚拟属性。
这个台式计算器的Yacc说明在图3.25已给出,那儿的目的是用来说明LR分析时的翻译。
在语法制导定义中,终结符看成只有综合属性,因而定义中没有提供计算终结符属性的语义规则,终结符的属性值通常由词法分析器提供。
开始符号没有任何继承属性。
4.1.2综合属性
综合属性在实践中有广泛应用。
仅仅使用综合属性的语法制导定义叫做S属性定义。
对于S属性定义,分析树各结点属性的计算可以自下而上地完成:
从叶结点到根,通过计算语义规则而得到结点的属性。
4.2节将描述LR分析器的生成器怎样实现以LR文法为基础的S属性定义。
每个结点的属性值都标注出来的分析树叫做注释分析树(annotatedparsetree),计算各结点属性值的过程叫做分析树的注释或修饰。
例4.2例4.1的S属性定义说明一台式计算器。
例如,若输入是表达式8+5*2,并跟随一个换行符,那么该计算器打印值18。
图4.1是8+5*2n的注释分析树,在树的根结点打印18。
L
nE.val=18
E.val=8T.val=10+
F.val=2T.val=5*T.val=8
digit.lexval=2F.val=5F.val=8
digit.lexval=8digit.lexval=5
图4.18+5*2n的注释分析树
为了明白属性值是怎么计算的,考虑最左边最底层的内部结点,它使用的产生式是F,digit,对应的语义规则是F.val:
=digit.lexval。
从该规则得到该结点的属性F.val为8,因为它的子结点digit的lexval是8。
同样地,该结点的父结点的属性T.val也为8。
我们再以产生式E,E+T的结点为例,这个结点的属性E.val由产生式E,E+T和语1
2
义规则E.val:
=E.val+T.val定义。
当我们在这个结点运用该语义规则时,子结点E的val11为8,子结点T的val为10,故在此结点求得E.val的值为18。
4.1.3继承属性
在分析树中,一结点的继承属性是由该结点的父结点和/或兄弟结点的属性来定义的。
程序设计语言的一些语法结构的属性依赖于它们所在的上下文,此时使用继承属性是方便的。
在下面的例子中,继承属性传递类型信息给一张声明标中的各个标识符。
例4.3在表4.2的语法制导定义中,非终结符D产生的声明由保留字int或real及一张标识符表组成。
非终结符T有综合属性type,它的值由声明中的保留字决定。
产生式D,TL的语义规则置L的继承属性为声明中的类型。
产生式L,L,id的语义规则L.in:
=L.in11把继承属性in沿分析树向下传递类型。
L产生式的规则调用过程addtype,把类型信息加到符号表中各个标识符的条目(属性entry给出条目的入口)中。
表4.2有继承属性的语法制导定义
产生式语义规则
D,TLL.in:
=T.type
T,intT.type:
=integer
T,realT.type:
=real
L,L,idL.in:
=L.in;11
addtype(id.entry,L.in)
L,idaddtype(id.entry,L.in)
图4.2给出句子intid,id,id的注释分析树。
这些属性值的确定首先是计算根的左子123
结点属性T.type,然后在根的右子树自上而下地计算三个L结点的L.in。
在每个L结点,我们还调用过程addtype,在符号表中将右子结点上的标识符的类型记为整型。
D
L.in=integerT.type=integer
L.in=integeridint3
L.in=integerid2
id1
图4.2intid,id,id的注释分析树123
使用继承属性的地方很多,例如,我们可以用继承属性来记住标识符是出现在赋值号的左边呢还是右边,以便决定是需要它的地址还是需要它的值。
重写语法制导定义使之仅使用综合属性总是可能的,但有时会使得重写后的文法失去了简洁和直观,反而不如使用带继承属性的语法制导定义自然。
4.1.4属性依赖图
如果分析树一结点的属性b依赖某个结点的属性c,那么属性b的语义规则的计算必须
3
在属性c的语义规则的计算之后。
分析树结点的属性间的互相依赖可以用一种叫做依赖图的有向图来描绘。
在构造分析树的依赖图之前,我们先为由过程调用组成的语义规则引入虚拟综合属性
…,c)的形式。
依赖图的组成是这样的,分析b,使得每条语义规则都能写成b:
=f(c,c12k
树上每个结点的所有属性在依赖图上各有一个结点,如果属性b依赖于属性c,那么从c的结点到b的结点有一条有向边。
例如,若S.s:
=f(A.a,B.b,C.c)是产生式S,ABC的语义规则,它定义了依赖于属性A.a,B.b和C.c的综合属性S.s。
如果把这个产生式用于分析树,那么在依赖图上有4个结点S.s,A.a,B.b和C.c,并且结点A.a,B.b和C.c分别有边到结点S.s。
如果产生式S,ABC有语义规则A.a:
=f(S.s,B.b,C.c),那么在依赖图上,结点S.s,B.b和C.c分别有边到结点A.a,因为A.a依赖于S.s,B.b和C.c。
例4.4图4.3给出了图4.2分析树的依赖图。
在图4.3中,虚线表示的是分析树;依赖图的结点用数表示,边用实线表示。
从结点4的T.type到结点5的L.in有一条边,因为根据产生式D,TL的语义规则L.in:
=T.type,L.in依赖于T.type。
因为产生式L,L,id的语1义规则L.in:
=L.in导致L.in依赖于L.in,因此依赖图上有分别到达结点7和9的两条向下11
的边。
L产生式的语义规则addtype(id.entry,L.in)导致虚拟属性的建立,结点6,8,10是这样的虚拟属性结点。
D
TLin54type6
Lintegeridin7833entry
Lin910id22entry
id1entry1
图4.3图4.2分析树的依赖图
4.1.5属性计算次序
拓扑排序是无环有向图的结点的一种排序m,m,…,m,它使得边只会从这个次序中12k
先出现的结点到后出现的结点,也就是若m,m是从m到m的边,那么在此排序中m先ijiji于m。
j
显然,依赖图的任何拓扑排序都是分析树中结点属性计算的一个正确次序,即按拓扑排序进行计算的话,用语义规则b:
=f(c,c,…,c)计算b时,属性c,c,…,c已经计算12k12k过了。
这样,由语法制导定义说明的翻译可以准确地按下述步骤完成:
(1)首先根据基础文法构造输入的分析树;
(2)按上面讨论的方法构造属性依赖图;
(3)对依赖图的结点进行拓扑排序,得到语义规则的计算次序;
(4)按这个次序计算属性,得到输入串的翻译。
例4.5图4.3的依赖图中,每条边从序号较低的结点到序号较高的结点,因此结点1,2,…,10构成该图的一个拓扑排序。
我们把依赖图中序号为n的结点的属性写成a,那n
4
么从这个拓扑排序可以得下面的程序:
a:
=integer;4
a:
=a;54
addtype(id.entry,a);35
a:
=a;75
addtype(id.entry,a);27
a:
=a;97
addtype(id.entry,a);19
这些语义规则的计算把类型integer存于符号表中每个标识符的条目中。
我们把语义规则的这种计算方法称为分析树方法。
若依赖图有环,则这种方法失败。
这种方法的缺点是编译速度很慢,因为它是在编译过程中决定属性的计算次序。
显然,要想提高编译速度,必须考虑在编译前,即在构造编译器的时候就能把计算次序确定下来,免去编译时的构造依赖图和拓扑排序等工作。
下面概述的两种方法分别是从手工构造编译器和自动生成编译器的角度考虑的改进。
在构造编译器时,用专门的工具或用手工对产生式的语义规则进行分析,对每个产生式,得到与它相联系的一组语义规则的计算次序。
这样,把计算次序在编译前确定下来;编译时,分析树上结点属性的计算就按事先确定的次序进行。
这种方法称为基于规则的方法,它适用于手工构造编译器。
这种方法的缺点是,一些属性依赖关系复杂的语法制导定义很难事先确定属性计算次序,因此这种方法对语法制导定义的种类有限制。
如果我们事先确定了属性的计算策略,反过来要求编译器的设计者遵守我们限定的计算策略去写语义规则,那么这种方法称为忽略规则的方法(obliviousmethod)。
例如,若我们的策略是边分析边计算,即在分析的同时完成属性计算,那么编译器的设计者在写语义规则时,必须考虑到分析树的结点是从左向右地生成等特点对属性计算带来的限制。
这种方法适用于编译器的自动生成,它大大限制了能够实现的语法制导定义的种类,但是能够得到高效的编译器。
基于规则的方法和忽略规则的方法都不必在编译时显式构造依赖图,和分析树方法相比,它们使编译器的时空效率大大改进。
从4.2节开始介绍的各种翻译方法都属于这两种方法。
4.2S属性定义的自下而上计算
我们已初步了解了如何用语法制导定义来说明翻译,从本节开始,我们一边熟悉语法制导定义,一边研究其实现。
对任意语法制导定义都适用的翻译器是很难建立的,但对语法制导定义的一些常用形式,它们的翻译器很容易构造。
本节考虑S属性定义这一类语法制导定义。
我们通过构造语法树的语法制导定义来熟悉S属性定义。
4.2.1语法树
语法树是分析树的浓缩表示(有些书把分析树称为语法树,而把这里的语法树称为抽象语法树),对表示语言结构是有用的。
语法树作为中间表示允许把翻译从分析中分离出来,形成先分析后翻译的方式。
即使是边分析边翻译,语法树作为一种概念上的中间表示,也是有用的。
C编译器通常构造语法树。
在语法树中,算符和关键字不是作为叶结点,而是作为内部结点,这些内部结点对应分析树中这些叶结点的父结点。
例如,对于产生式S,ifBthenSelseS,可以把它的右部12
5
看成有一个算符if-then-else和3个运算对象B,S和S,它的语法树见图4.4(a)。
12
语法树中另一个简单的地方是单非产生式链可能消失,图4.4(b)是表达式8+5*2的语法树。
语法制导翻译可以基于分析树,也可以基于语法树,方法是一样的。
如同在分析树中那样,在语法树中我们也可以把属性附加到结点。
+if-then-else
*8
SB2S125
(b)(a)
图4.4语法树的例子
4.2.2构造语法树的语法制导定义
本节我们给出构造表达式的语法树的语法制导定义。
首先介绍一下数据结构,语法树的结点可以用有若干域的记录来实现。
对于算符结点,一个域存放算符,该域作为该结点的标记,其余两个域含指向运算对象的指针。
对于基本运算对象结点,一个域存放运算对象类别,另一个域存放其值。
当用于翻译时,语法树的结点可能还有其它域来保存加在该结点的其它属性值(或属性值的指针)。
下面我们解释语义规则中用到的函数,这些函数用来建立语法树的叶结点和内部结点,每个函数都返回新建结点的指针。
(1)mkleaf(id,entry)。
它建立标记为id的标识符结点,结点有一个域entry,它是符号表中该标识符条目的指针。
(2)mkleaf(num,val)。
它建立标记为num的数结点,结点有一个域val,它是该数的值。
(3)mknode(op,left,right),它用来建立标记为op的算符结点,结点有两个指针域,分别是left和right。
表4.3是为含+和*的表达式构造语法树的S属性定义。
它给文法的产生式添加语义规则来安排函数mknode和mkleaf的调用,以便构造语法树。
E,T和F的综合属性nptr用来记住函数调用返回的指针。
表4.3构造表达式语法树的语法制导定义
产生式语义规则
E,E+TE.nptr:
=mknode(‘+’,E.nptr,T.nptr)11
E,TE.nptr:
=T.nptr
T,T*FT.nptr:
=mknode(‘*’,T.nptr,F.nptr)11
T,FT.nptr:
=F.nptr
F,(E)F.nptr:
=E.nptr
F,idF.nptr:
=mkleaf(id,id.entry)
F,numF.nptr:
=mkleaf(num,num.val)
例4.6图4.5给出了表达式a+5*b的注释分析树和执行语义规则所构造出的语法树,分析树由带点的线表示。
标有非终结符E,T和F的分析树结点,其综合属性nptr指向由
6
该非终结符推出的表达式的语法树的根结点。
产生式F,id和F,num的语义规则定义的属性F.nptr也是指针,它们分别指向代
entry和num.val是词法单元的值,词法分析器把它们随记表标识符和数的叶结点。
属性id.
号id和num一起返回。
在图4.5中,当表达式E只有一项,即使用产生式E,T时,属性E.nptr和T.nptr的
值一样。
当使用产生式E,E+T的语义规则E.nptr:
=mknode(‘+’,E.nptr,T.nptr)时,先前11
的规则已把E.nptr和T.nptr分别置为指向叶结点a和内部结点5*b1
E.nptr
T.nptr+E.nptr
F.nptrT.nptr*T.nptr
+
F.nptridF.nptr
numid*
idnum5id
指向符号表中a的入口指向符号表中b的入口
图4.5a+5*b的语法树的构造
处于图4.5的下部,由记录形成的树是构成输出的真正语法树;而虚线表示的树是分析树,它可能仅有象征的意义。
+5*b,实际执行的一列函数调用如下:
根据表4.3的语法制导定义,对于输入a
(1)p:
=mkleaf(id,entrya);1
(2)p:
=mkleaf(num,5);2
(3)p:
=mkleaf(id,entryb);3
(4)p:
=mknode(‘*’,p,p);423
(5)p:
=mknode(‘+’,p,p);514
我们可以看出,写语法制导定义比写普通的程序更困难。
对程序而言,整个程序的执行流程是显式地用语句描述的。
而语法制导定义中语义规则的执行受输入的语法的制导,当识别出输入串的一个语法结构时(可以看成发生一个事件),执行其相应的动作,因此这是一种事件驱动的程序设计。
4.2.3S属性的自下而上计算
综合属性可以由自下而上的分析器在分析输入时完成计算。
分析器可以把文法符号的综合属性值放在它的栈里,每当归约时,根据出现在栈顶的产生式右部符号的属性来计算左部符号的综合属性。
我们说明如何扩展分析器的栈使之能够保存综合属性。
在4.5节我们将看到这种实现也支持一些继承属性。
S属性定义的翻译器可以借助LR分析器的生成器来实现,例如3.7节讨论的Yacc。
根据S属性定义,分析器的生成器可以构造出翻译器,它在分析输入时计算属性。
7
自下而上分析器用栈来保存已分析子树的信息。
我们可以在分析栈中增加一个域来保存综合属性值,图4.6给出了一个例子。
我们假设拓展后的分析栈由状态数组state和值数
)分析表的指针或下标(注意,组val实现,如图4.6所示的那样。
state的每个条目是LR(1
文法符号隐含在状态里,无需存放在栈中),但为直观起见,我们用文法符号来代替状态,这个符号就是3.5节所描述的分析栈中被状态盖住的那个符号。
val数组为文法符号存放的综合属性。
如果state的第i个符号是A,那么val[i]保存对应这个A的分析树结点的属性值。
栈顶由指针top指示,并假定综合属性刚好在每步归约前计算。
若产生式A?
XYZ的语义规则是A.a:
=f(X.x,Y.y,Z.z),那么在XYZ归约成A之前,属性Z.z的值在val[top],Y.y的值在val[top,1],X.x的值在val[top,2]。
如果某个符号没有属性,那么val数组对应条目没有定义。
归约后,top的值减2,复盖A的状态放进state[top](即X原来的位置),综合属性的值A.a放进val[top]。
......
top
ZZ.z
YY.y
XX.x栈
......
stateval
图4.6有综合属性域的分析栈
例4.7再次考虑表4.1的台式计算器的语法制导定义。
图4.1的注释分析树上的综合属性可以由LR分析器在分析输入8+5*2n期间计算。
同前面一样,假定词法分析器提供属性digit.lexval的值。
当分析器把digit移进栈时,记号digit置入state[top],它的属性值放在val[top]。
我们用3.5节的技术构造基础文法的LR分析器。
为了计算属性,需要修改分析器,让它在归约前执行表4.1的语义动作,这些语义动作可以翻译成表4.4的栈操作代码段。
这些代码段实际上就是用属性在val数组的位置代替表4.1语义规则的属性而得到。
表4.4用LR分析器实现台式计算器
产生式代码段
L,Enprint(val[top,1])
E,E+Tval[top,2]:
=val[top,2]+val[top]1
E,T
T,T*Fval[top,2]:
=val[top,2],val[top]1
T,F
F,(E)val[top,2]:
=val[top,1]
F,digit
表4.4中的代码段中,属性计算的结果都置入val数组中top,2的位置是因为刚好对应产生式的右部都是3个符号。
这里的top指归约前的栈顶,归约后它的值会根据右部符号的多少进行调整。
表4.5展示了面临输入8+5*2n时分析器的动作序列。
每步动作后分析栈的state域和val域的内容都在图中给出,我们仍然用对应的文法符号代替状态。
为直观起见,我们还用
8
实际的输入数字代替记号digit。
考虑看见第一个输入符号8时的动作序列。
首先分析器把对应记号digit的状态移进栈(状态由8表示,属性值8在val域)。
第二步,分析器用产生式F,digit归约并完成语义规则F.val:
=digit.lexval的计算。
第三步,分析器按T,F归约,完成其语义规则的计算。
第四步,分析器按E,T归约,完成其语义规则的计算。
注意,没有代码段和这3个产生式相联,所以val数组不改变,但
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国科学技术大学 陈意云 编译 原理 全套 参考资料 chapter4
![提示](https://static.bingdoc.com/images/bang_tan.gif)