大连理工大学编译原理PPT

4.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.lexval4.1语法制导的定义4.1.1语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A有一组形式为b:=f(c1,c2,…,ck)的语义规则，其中f是函数，b和c1,c2,…,ck是该产生式文法符号的属性综合属性：如果b是A的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其它属性。继承属性：如果b是产生式右部某个文法符号X的属性。属性值由分析树中它的子结点的属性值来计算属性值由结点的兄弟结点及父结点的属性值来计算。4.1语法制导的定义4.1.2综合属性S属性定义：仅仅使用综合属性的语法制导定义产生式语义规则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.lexval4.1语法制导的定义8+5*2n的注释分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5每个结点的属性值都标注出来的分析树，称为~。4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义注释分析树:结点的属性值都标注出来的分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=58+5*2n4.1语法制导的定义4.1.3继承属性intid,id,id产生式语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)4.1语法制导的定义intid1,id2,id3的注释分析树DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,4.1语法制导的定义4.1.4属性依赖图intid1,id2,id3的分析树的依赖图DTLL.in:=T.typeDintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义4.1.4属性依赖图intid1,id2,id3的分析树的依赖图LL1,idL1.in:=L.in;addtype(id.entry,L.in)DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义4.1.5属性计算次序拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。例：1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1语法制导的定义属性计算次序1、构造输入的分析树，2、构造属性依赖图，3、对结点进行拓扑排序4、按拓扑排序的次序计算属性。温故知新每个文法产生式A有一组形式为b:=f(c1,c2,…,ck)的语义规则，其中f是函数，b和c1,c2,…,ck是该产生式文法符号的属性综合属性：如果b是A的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其它属性继承属性：如果b是产生式右部某个文法符号X的属性。属性值由分析树中它的子结点的属性值来计算属性值由结点的兄弟结点及父结点的属性值来计算。温故知新属性的理解非终结符分析过程（函数）综合属性过程的返回值继承属性过程的参数属性理解—例子intid,id,id产生式语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)温故知新属性理解—例子voidD(){T_temp=T();L_in=T_temp;L(L_in);return;}intT(){switchlookahead{caseINT:returnINTEGER;caseREAL:returnREAL;default:error;}}产生式语义规则DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)温故知新voidL(intL_in){L(L_in);match(‘,’);match(id);addtype(id.entry,L_in);}VoidL(intL_in){match(id);addtype(id.entry,L.in);}4.2S属性定义的自下而上计算4.2.1语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点。语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：if-then-elseBS1S2SifBthenS1elseS2SBS1S2ifthenelse语法树分析树4.2S属性定义的自下而上计算4.2.2(例)用于构造语法树的语法制导定义产生式语义规则EE1+TE.nptr:=mknode(‘+’,E1.nptr,T.nptr)ETE.nptr:=T.nptrTT1*FT.nptr:=mknode(‘*’,T1.nptr,F.nptr)TFT.nptr:=F.nptrF(E)F.nptr:=E.nptrFidF.nptr:=mkleaf(id,id.entry)FnumF.nptr:=mkleaf(num,num.val)4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口EE1+T|TTT1*F|FF(E)Fid|num4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口EE1+T|TTT1*F|FF(E)Fid|num4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口EE1+T|TTT1*F|FF(E)Fid|num4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口EE1+T|TTT1*F|FF(E)Fid|num4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中a的入口指向符号表中b的入口EE1+T|TTT1*F|FF(E)Fid|num4.2S属性定义的自下而上计算a+5*b的语法树的构造E.nptrT.n