第15讲-语义分析-I

2020/2/26中国科大1/34编译原理和技术大连理工软件学院胡彦[e-mail]2020/2/26中国科大2/34LR(1)分析练习总结课堂练习中的情况不会构造识别活前缀DFA知道构造识别活前缀DFA，但是项目集里的项目构建不完全，遗漏加点项不会构造分析表2020/2/26中国科大3/34LR(1)分析练习题目基于LR(1)项目来构造识别G活前缀的DFA，并基于DFA构建分析表.SV=ESEV*EVidEV2020/2/26中国科大4/34LR(1)分析练习解答过程答：Step1.对原文法进行拓广(添加产生式S-S’)SV=ESEV*EVidEVSS’SV=ESEV*EVidEV2020/2/26中国科大5/34LR(1)分析练习解答过程Step2:构建识别（拓广）文法活前缀的DFAI0:S’-·S,$S-·V=E,$S-·E,$V-·*E,=/$V-·id,=/$E-·V,$I1:S’-S·,$SI2:S-V·=E,$E-V·,$VEI3:S-E·,$*I4:V-*·E,=/$E-·V,=/$V-·*E,=/$V-·id,=/$idI5:V-id·,=/$=I6:S-V=·E,$E-·V,$V-·*E,$V-·id,$EI8:S-*E·,=/$VI9:E-V·,=/$*id指向I5EI10:S-V=E·,$*I12:V-*·E,$E-·V,$V-·*E,$V-·id,$VI7:E-V·,$V指向I7idI11:V-id·,$EI13:S-*E·,$V指向I7*id指向I112020/2/26中国科大6/34LR(1)分析练习解答过程构建分析表首先，为表达式编号然后，计算action表和goto表[0]SS’[1]SV=E[2]SE[3]V*E[4]Vid[5]EV2020/2/26中国科大7/34LR(1)分析练习解答过程构建分析表Action(0,*)=s4,action(0,id)=s5Goto(0,S)=1,goto(0,V)=2,goto(0,E)=3Action(1,$)=accAction(2,=)=s6Goto(2,V)=7Action(3,$)=r2Action(4,*)=s4,action(4,id)=s5Goto(4,E)=8,goto(4,V)=9…2020/2/26中国科大8/34语义分析简介编译程序的目标：将源程序翻译成为语义等价的目标程序源程序与目标程序具有不同的语法结构，表达的结果却是相同的2020/2/26中国科大9/34语义分析简介语义分析的功能审查每个语法结构的静态语义例：类型、运算、维数、越界在验证完静态语义后，才执行真正的翻译例：变量的存储分配例：表达式的求值例：语句的翻译（中间代码的生成）2020/2/26中国科大10/34语义分析简介语义信息是上下文有关的例如：变量使用前要先定义文法定义可以写成：L={wcw|w是任意的a和b的串}其中第一个w代表标识符的声明后一个w表示对标识符的引用问题：这个文法不是上下文无关的怎么办呢？2020/2/26中国科大11/34语义分析简介目前情况上下文无关文法能够有效描述语言语法结构具有有效的分析方法，如LR(1)、LALR等程序语义编译器进行翻译的时候所必须的信息无法用上下文无关文法表示这两者之间怎么衔接？属性文法2020/2/26中国科大12/34属性文法由Knuth在1968年提出基本思想为文法G描述的语法结构添加语义属性通常是为每个语法树结点添加所需的属性描述添加一系列的语义规则附加在文法G的产生式上如果添加的语义规则是有副作用的，那么这种属性文法又称为语法制导定义2020/2/26中国科大13/34属性文法表达式文法EE+T|ETTT*F|TEF(E)|Fdigit为了计算表达式的值，首先为这个文法的非终结符添加val属性2020/2/26中国科大14/344.1语法制导的定义例简单台式计算器的语法制导定义产生式语义规则LEnEE1+TETTT1*FTFF(E)FdigitF.val:=digit.lexvalT.val:=F.valT.val:=T1.val*F.valE.val:=T.valE.val:=E1.val+T.valF.val:=E.valprint(E.val)2020/2/26中国科大15/344.1语法制导的定义4.1.1语法制导定义的形式基础文法每个文法符号有一组属性每个文法产生式A有一组形式为b:=f(c1,c2,…,ck)的语义规则，其中f是函数，b和c1,c2,…,ck是该产生式文法符号的属性综合属性：如果b是A的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其它属性。继承属性：如果b是产生式右部某个文法符号X的属性，c1,c2,…,ck是产生式右部文法符号的属性或A的其它属性。属性值由分析树中它的子结点的属性值来计算属性值由结点的兄弟结点及父结点的属性值来计算。2020/2/26中国科大16/344.1语法制导的定义关于属性的一些常识终结符只有综合属性，并且这些综合属性通常由词法分析器提供开始符号没有任何继承属性因为开始符号没有任何的兄弟结点或者父结点。2020/2/26中国科大17/344.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.lexval2020/2/26中国科大18/344.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每个结点的属性值都标注出来的分析树，称为～。2020/2/26中国科大19/344.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*2n2020/2/26中国科大20/344.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*2n2020/2/26中国科大21/344.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*2n2020/2/26中国科大22/344.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*2n2020/2/26中国科大23/344.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*2n2020/2/26中国科大24/344.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*2n2020/2/26中国科大25/344.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*2n2020/2/26中国科大26/344.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*2n2020/2/26中国科大27/344.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*2n2020/2/26中国科大28/344.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*2n2020/2/26中国科大29/344.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*2n2020/2/26中国科大30/344.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*2n2020/2/26中国科大31/344.1语法制导的定义4.1.3继承属性intid,id,id产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type:=integerT.type:=realL1.in:=L.in;addtype(id.entry,L.in)addtype(id.entry,L.in)综合属性计算2020/2/26中国科大32/344.1语法制导的定义intid1,id2,id3的注释分析树DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,2020/2/26中国科大33/344.1语法制导的定义4.1.4属性依赖图intid1,id2,id3的分析树的依赖图DTLL.in:=T.typeDintT,id3LLLid2id1,1entry102entry3entryin98in76in54type2020/2/26中国科大34/344.1语法制导的定义4.1.4属性依赖图intid1,id2,id3的分析树的依赖图LL1,idL1.in:=L.in;addtype(id.en