编译原理习题答案名师优质课赛课一等奖市公开课获奖课件

编译原理电子教案第六章属性文法和语法制导翻译第1页本章主要内容属性文法和语法制导翻译概念综合属性和继承属性概念、特点S-属性文法与L-属性文法概念及分析方法翻译模式递归下降翻译器设计第2页2本章要求

知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下翻译，自底向上计算继承属性。深刻了解：属性，综合属性，继承属性，依赖图，计算次序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。熟练掌握：对于已知文法G和翻译任务，结构其L-属性定义，将其改造成适于自顶向下分析或自底向上分析翻译模式。第3页3本章教学线索1属性文法（属性翻译文法）1.1属性文法概念1.2属性分类1.3属性计算规则2基于属性文法处理方法3S-属性文法自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性第4页41属性文法（属性翻译文法）语法制导翻译：经过给语法树上各个符号赋予一定含义而且将各个符号进行有结构连接，能够形成语言具体语句含义。这给予我们以启示：能够经过扩充文法，在文法符号上附着一些语义信息，并在这些语义信息间建立相互计算关系，从而在语法分析同时进行语义分析。因为这种分析是在语法分析控制下进行，故称为语法制导翻译。第5页51.1属性文法概念（1）属性文法定义在上下文无关文法基础上，为每个文法符号（终止符和非终止符）配置若干相关“值”（也称：“属性”），对于文法每个产生式都配置了一组属性计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。说明：在普通情况下，整个属性文法是非常复杂。但属性函数关系却通常非常简单。属性也极少依赖于大量其它属性，所以能够将相互依赖属性分割成较小独立属性集，然后单独对每一属性集写出一个属性文法。第6页6（2）属性（Attribute）是编程语言结构任意特征。属性在其包含信息和复杂性等方面改变很大。属性经典例子有：•变量数据类型•表示式值•存放器中变量位置•程序目标代码•数有效位数（3）属性文法普通表示方法：文法规则语义规则规则1规则2…规则n相关属性等式/语义规则相关属性等式/语义规则…相关属性等式/语义规则第7页7例6.1一个简单台式计算器属性文法产生式语义规则L→EnPrint(E.val)E→E1+TE.val=E1.val+T.valE→TE.val=T.valT→T1*FT.val=T1.val*F.valT→FT.val=F.valF→(E)F.val=E.valF→digitF.val=digit.lexval第8页8例6.2：无符号整数属性文法文法规则语义规则Number1→Number2digitNumber→digitdigit→0digit→1digit→2digit→3digit→4digit→5digit→6digit→7digit→8digit→9Number1.val=number2.val*10+digit.valNumber.val=digit.valdigit.val=0digit.val=1digit.val=2digit.val=3digit.val=4digit.val=5digit.val=6digit.val=7digit.val=8digit.val=9第9页91.2属性分类例6.3属性文法为例6.1中属性文法，输入：3*5+4ndigitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln综合属性：用于自下而上传递信息；在语法树中，一个结点综合属性由其子结点属性值确定，所以，通常使用自底向上方法在每一个结点处使用语义规则计算综合属性值。仅仅使用综合属性属性文法称S-属性文法。继承属性：用于自上而下传递信息；在语法树中，一个结点继承属性由此结点父结点和/或弟兄结点一些属性确定。第10页10例6.4继承属性类型说明文法产生式语义规则D→TLL.in=T.typeT→intT.type=integerT→realT.type=realL→L1,idL1.in=L.inAddtype(id.entry,L.in)L→idAddtype(id.entry,L.in)DT.type=realrealL.in=realL.in=real,id3L.in=real,id2id1realid1，id2，id3第11页111.3属性计算规则属性计算规则：设有产生式A→定义b=f（c1，c2，……，ck

）f是一个计算函数，而且（1）b是A一个综合属性，而且c1，c2，……，ck是产生式右边文法符号属性。或者：（2）b是产生式右边某文法符号一个继承属性，而且c1，c2，……，ck是A或产生式右边任何文法符号属性。第12页12注意：假如同一文法符号在文法规则中出现不止一次，那么每次必须用适当下标与在其它地方出现符号区分开来。终止符只有综合属性，它们由词法分析器提供。非终止符既可有综合属性也可有继承属性，文法开始符全部继承属性为属性计算前初始值。属性计算规则中仅能使用对应产生式汉字法符号属性（封装性）。产生式左边继承属性和产生式右边文法符号综合属性由其它产生式属性规则计算。一个句型语法树能够加以扩充，用来表示句型分析中得到各个符号属性间关系：语法树中，一个结点综合属性值由其子结点属性值确定语法树中，一个结点继承属性值由该结点父结点和（或）弟兄结点一些属性值确定第13页13本章教学线索1属性文法（属性翻译文法）

2基于属性文法处理方法2.1语法制导翻译2.2

依赖图2.3树遍历属性计算方法2.4

一遍扫描处理方法2.5抽象语法树(AbstractSyntaxtree)3S-属性文法自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性第14页142.1

语法制导翻译

基于属性文法处理过程通常是：对单词符号串进行语法分析，结构语法分析树，然后依据需要遍历语法树，并在语法树各结点处按语义规则进行计算。输入串分析树依赖图语义规则计算图6.1语法制导翻译概观在详细实现时，普通都是随语法分析进展，识别出一个语法结构，就对它语义进行分析和翻译。也就是语义分析是伴随语法分析过程进行。第15页152.2依赖图a．依赖图：一个有向图，在一颗语法树中表示结点继承属性和综合属性之间相互依赖关系（这种属性之间依赖关系由文法语义规则确定）。b．依赖图结构方法：

for语法树中每一结点ndofor结点n文法符号每一个属性ado

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

for语法树中每一个结点ndofor结点n全部产生式对应每一条语义规则

b＝f（c1，c2，…，ck)dofori＝1tokdo

从结点ci到结点b结构一条有向边；注意：假如属性文法不存在属性之间循环依赖关系，那么称该文法为良定义。bC1C2…Ck-1Ck第16页16例6.5E→E1+E2E.val=E1.val+E2.valE.valE1.valE2.valDTrealLL,id3L,id2id14typein5in7in910861entry3entry2entry例6.4中带继承属性文法对于realid1，id2，id3产生式语义规则D→TLL.in=T.typeT→intT.type=integerT→realT.type=realL→L1,idL1.in=L.inAddtype(id.entry,L.in)L→idAddtype(id.entry,L.in)第17页17c．属性计算次序拓扑排序一个有向非循环图拓扑排序是图中结点任何次序m1，m2，…，mk，使得边必须是从序列中前面结点指向后面结点，也就是说,假如mi→mj是mi到mj一条边，那么在序列中mi必须出现在mj前面。若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值计算次序。计算语义规则方法

1）分析树法：输入串→分析树→依赖图→计算次序

2）基于规则方法：在结构编译器时，用手工或专门工具来分析语义规则，确定属性值计算次序。

3）忽略语义规则方法：在语法分析过程中翻译，那么计算次序由分析方法来确定而表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值计算次序能和语法分析过程同时进行。第18页182.3树遍历属性计算方法前提：1）假设语法树已经建立

2）且树中已带有开始符号继承属性和终止符综合属性；方法：深度优先，从左到右进行（也是一个分析树方法）详细算法：While还有未被计算属性doVisitNode(S)//S是开始符号ProcedureVisitNode(N：Node)；beginifN∈VNthen//假设它产生式N→X1…Xm fori=1tomdoifXi∈VNthenbegin

计算Xi全部能够计算继承属性；

VisitNode（Xi）；end；

计算N全部能够计算综合属性；end例子：6.6P143第19页192.4一遍扫描处理方法

在语法分析同时计算属性值，无需结构实际语法树；这种方法同下面两个原因相关：所采取语法分析方法属性计算次序使用一遍扫描语义分析方法，就是为文法中每个产生式配上一组语义规则，而且在语法分析同时执行这些语义规则。在自上而下分析中就是在产生式匹配输入串成功，或者在自下而上分析中，当一个产生式被用于进行规约时，此产生式对应语义规则就被计算，完成相关语义分析和代码产生工作。语法分析过程中完成翻译有许多优点，但也有一些不足：适于语法分析文法可能不完全反应语言成份自然层次结构；语法分析方法限制，对语法树结点访问次序和翻译需要访问次序不一致。第20页202.5抽象语法树(AbstractSyntaxtree)（1）表示程序层次结构树，它把分析树中对语义无关紧要成份去掉，是语法树抽象形式，也称作语法结构树，或结构树。抽象语法树是惯用一个中间表示形式。（2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。产生式S→ifBthenS1elseS2赋值语句语法树if-then-elseassignment／|＼／＼BS1S2variableexpression（3）建立表示式抽象语法树建立表示式抽象语法树使用函数

1）mknode（op，left，right）建立一个运算符号结点，标号是op，两个域left和right指向运算分量结点指针。

2）mkleaf(id，entry)建立一个标识符结点，由标号id标识，一个域entry指向标识符符号表中对应项。

3）mkleaf（num，val）建立一个数结点，标号为num，域val用于存放数值。返回新建立结点指针。第21页21产生式语义规则

EE1+TE.nptr:=mknode('+',E1.nptr,T.nptr)EE1-TE.nptr:=mknode('-',E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)idtoentryanum4

–

idtoentryc

+a-4+c语法树第22页22本章教学线索1属性文法（属性翻译文法）

2基于属性文法处理方法3S-属性文法自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性第23页233S-属性文法自下而上计算s-属性文法：只含有综合属性s-属性文法通常借助于LR分析器来实现，在分析栈中使用一个附加域来存放文法符号综合属性值。

stateval...ZZ.zY...Y.y...…..XX.ztop一个带有综合属性值域分析栈A→

b=f（c1，c2，…，ck）b是A综合属性，ci(1≤i≤k)是中符号属性。综合属性值在自底向上分析过程中，每步归约时，计算对应属性值。

第24页24比如：A→XYZAa＝f(Xx，Yy，Zz)Aa

╱

∣

╲XxYyZz

XX.xYY.yZZ.z……AA.astatevaltoptopstateval……定义式A.a=f（X.x，Y.y，Z.z）（抽象）变成：val[ntop]＝f（val[top-2]，val[top-1]，val[top]）（详细可执行代码）。在执行代码段之前执行：ntop＝top-r+1（r是句柄长度）执行代码段后执行：top＝ntop；总结：采取自底向上分析，比如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行代码段，这就组成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译代码段（语义子程序）就挂在这个钩子上。这么，伴随语法分析进行，归约前调用对应语义子程序,完成翻译任务。第25页25例6.9用LR分析器实现台式计算器产生式代码段LEnprintf(val[ntop])EE+Tval[ntop]:=val[top-2]+val[top]ETTT*Fval[ntop]:=val[top-2]*val[top]TFF(E)val[ntop]:=val[top-1]Fdigit输入stateval产生式3*5+4n--*5+4n33*5+4nF3F→digit*5+4nT3T→F5+4nT*3-+4nT*53-5+4nT*F3-5F→digit+4nT15T→T*F+4nE15E→T4nE+15-nE+415-4nE+F15-4F→digitnE+T15-4T→FnE19E→E+TEn19–L19L→En第26页26本章教学线索1属性文法（属性翻译文法）

2基于属性文法处理方法3S-属性文法自下而上计算4L-属性文法和自顶向下翻译4.1L-属性文法定义4.2翻译模式4.3自顶向下翻译4.4递归下降翻译器设计5自下而上计算继承属性第27页274L-属性文法和自顶向下翻译在语法分析过程中进行语义分析和翻译，属性计算次序受到语法分析建立分析树结点次序限制。一个自然计算属性次序是按深度优先访问分析树结点次序，它适应各种自底向上和自顶向下翻译方法。L-属性文法可用按深度优先次序计算属性值。第28页284.1L-属性文法定义假如A→X1X2…XnP，其每一个语义规则中每一个属性都是一个综合属性，或是Xj(1jn)一个继承属性，这个继承属性仅依赖于：

a．产生式中Xj左边符号X1，X2，…Xj-1属性；

b．A继承属性。每一个S-属性文法都是L-属性文法一个非L-属性文法定义产生式语义规则A→LML.i=l(A.i)M.i=m(l.s)A→QRR.i=r(A.i)Q.i=q(R.s)A.s=f(Q.s)第29页294.2翻译模式1）翻译模式概念：翻译模式是语法制导定义一个便于翻译书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛｝括起来，能够被插入到产生式右部任何适当位置上。这是一个语法分析和语义动作交织表示法，它表示在按深度优先遍历分析树过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算次序。可看成是分析过程中翻译注释。翻译模式确保了按深度优先次序一次扫描就能完成属性计算。例一个简单翻译模式

E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}ET9print(‘9’)R-T5print(‘5’)print(‘-’)R+Tprint(‘2’)print(‘+’)2Rε9-5+2翻译成后缀式95-2+第30页302）翻译模式结构条件：属性文法是L-属性文法；确保语义动作不会引用还没有计算属性值。a.只需要综合属性情况：

为每一个语义规则建立一个包含赋值动作，并把这个动作放在对应产生式右边末尾。比如：T→T1*FTval=T1val*FvalT→T1*F{Tval=T1val*Fval}b.现有综合属性又有继承属性:产生式右边符号继承属性必须在这个符号以前动作中计算出来。一个动作不能引用这个动作右边符号综合属性。(因为综合属性是在该符号全部分析动作结束后计算）产生式左边非终止符综合属性只有在它所引用全部属性都计算出来以后才能计算。计算这种属性动作通常可放在产生式右端末尾。第31页314.3自顶向下翻译用翻译模式结构自顶向下翻译。从翻译模式中消除左递归对于一个翻译模式，若采取自顶向下分析，必须消除左递归和提取公共左因子，在改写基本文法时考虑属性值计算。例图6.13带左递归文法翻译模式被转换成图6.14带右递归文法翻译模式。

EE1+T｛Eval:=E1val+Tval}EE1-T｛Eval:=E1val-Tval｝

ET{E.val:=Tval}T(E)

｛Tval:=Eval｝

Tnum

｛Tval:=numval}

图6.13带左递归文法翻译模式

第32页32

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}图6.14经过转换带有右递归文法翻译模式R.s=R.iET.val=9num.val=9R.i=9-T.val=5num.val=5R.i=4+T.val=2num.val=2R.i=6εR.s=R1.sR.s=R1.sE.val=R.s计算表示式9-5+2第33页33关于左递归翻译模式更普通化讨论左递归翻译模式

A→A1Y｛A.a:=g(A1.a，Y.y)}A→X｛A.a:=f(X.x)}（6.2）每一个文法符号都有一个综合属性，用对应小写字母表示，g和f是任意函数。消除左递归，文法转换成

A→XRR→YR|ε（6.3）再考虑语义动作，翻译模式变为：

A→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}

（6.4）经过转换翻译模式与图6.14中一样,使用R继承属性i和综合属性s。（6.2）和（6.4）结果是一样第34页34A.a=g(g(f(X.x),Y1.y),Y2.y)Y2A.a=g(f(X.x),Y1.y)A.a=f(X.x)Y1XAXR.i=f(X.x)Y1R.i=g(f(X.x),Y1.y)Y2R.i=g(g(f(X.x),Y1.y),Y2.y)输入：XY1Y2εA→A1Y｛A.a:=g(A1.a,Y.y)}A→X｛A.a:=f(X.x)}（6.2）

A→X｛Ri:=f(Xx)}R｛A.a:=R.s}R→Y｛R1i:=g（Ri，Yy）}R1｛Rs:=R1

s}R→ε｛Rs:=Ri}

（6.4）第35页35建立表示式抽象语法树翻译模式：

EE1+T{Enptr:=mknode(´+´,E1nptr,Tnptr)}

EE1-T{Enptr:=mknode(´-´,E1nptr,Tnptr)}ET{Enptr:=Tnptr}

从翻译模式中消除左递归，变成以下翻译模式：

E→T{Ri:=Tnptr}R｛Enptr:=Rs}R→＋

T｛R1i:=mknode('+',Ri,Tnptr)}R1｛Rs:=R1

s}R→-T｛R1i:=mknode('-',Ri,Tnptr)}R1{Rs:=R1s}R→ε｛Rs:=Ri}T→(E){Tnptr:=Enptr}T→id{Tnptr:=mkleaf(id,identry)}T→num｛Tnptr:=mkleaf(num,numval)}第36页36使用继承属性结构a-4+5语法树ETidnptridtoentryforaR-Tnumnptrnum

4i-R+Tidnptridtoentryforc+iRεsi第37页374.4递归下降翻译器设计算法6.1预测语法制导翻译器建立输入：一个带有适合预测分析基础文法语法制导翻译模式。输出：一个语法制导翻译器代码。方法：在预测分析器中加入语义动作代码。AVN,建立一个可递归调用函数过程A。为A每一个继承属性都设置一个形式参数，函数返回值是A综合属性值。函数过程A代码（指用符号形式表示数据和程序）要依据当前输入符号来决定使用哪一个产生式。与每一个产生式相关代码，从左到右根椐产生式右部是单词符号、非终止符号还是语义动作，分别是：（a）对于带有综合属性x单词符号X，x存放在X.x中，Match(X)。（b）对于BVN，编写一个赋值语句c:=B（b1,b2,…，bk)

其中，b1，b2，…，bk是继承属性，c是综合属性。（c）对于每个动作，动作代码抄进翻译器中，用代表属性变量来代替对属性每一次引用。第38页38例:R→addopT｛R1．i:=mknode（addoplexeme，Ri，Tnptr）