语义分析和语法制导翻译

语义分析和语法制导翻译第六章语义分析和语法制导翻译语义分析的任务：检查语义错误类型检查： 运算数类型一致性检查： 名字声明与引用控制流检查： 转移目标名字检查： 作用域翻译的任务：建立等价的目标程序生成中间语言的指令序列名字绑定： 变量名、过程名建立运行环境第2页,共49页，2024年2月25日，星期天6.1属性文法语义分析与语法制导翻译的描述方法属性文法的定义：Ａ＝（Ｇ，Ｖ，Ｆ）Ｇ是上下文无关文法Ｖ属性的有穷集Ｆ关于属性的断言和谓词第3页,共49页，2024年2月25日，星期天用法针对语义，为文法符号设置属性终结符使用单词的属性为每个产生式设置语义规则通过描述各属性的关系将语义分析和翻译步骤定义为产生式的断言和谓词第4页,共49页，2024年2月25日，星期天例6-1:计算器的算法设计需求：算术表达式的求值设计：编制算术表达式的文法引入属性表示语义信息将值val作为表达式E、项T和因子F的属性用语义规则描述表达式的求值第5页,共49页，2024年2月25日，星期天属性文法（语法制导定义）attr是单词

digit的属性print(val)是输出函数产生式语义规则L→Eprint(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.attr第6页,共49页，2024年2月25日，星期天例6-2：说明语句的类型信息统计说明语句的作用支持语义分析，提供语义检查的依据设计编写说明语句的文法将类型信息作为类型描述T的属性type和变量表L的属性in。目的分析说明语句D，获取变量的类型信息第7页,共49页，2024年2月25日，星期天描述类型信息提取的属性文法entry单词

id的属性(符号表入口)addtype在符号表中为变量填加类型信息产生式语义规则D→TLL.in:=T.typeT→intT.type:=‘integer’T→realT.type:=‘real’L→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)第8页,共49页，2024年2月25日，星期天属性文法的作用抽象描述语义处理的要求语义信息及其计算关系适用于各种语义处理（分析、翻译、计算）语义处理的步骤属性求值计算、断言检查语义处理算法的描述方法一种通用的语义处理算法设计方法第9页,共49页，2024年2月25日，星期天属性分类：综合属性从其子结点的属性值计算出来的；如：E.val、T.type继承属性从其兄弟结点和父结点的属性值计算出来的如：L.in固有属性（单词属性）第10页,共49页，2024年2月25日，星期天属性的计算构造语法分析树，填加响应的语义规则综合属性自底向上按照语义规则来计算各结点的综合属性值继承属性需要探讨计算次序第11页,共49页，2024年2月25日，星期天例6-3：3*5+4的

语法树与属性计算第12页,共49页，2024年2月25日，星期天例6-4：realid1,id2,id3的分析树和属性计算addtypeaddtypeaddtype第13页,共49页，2024年2月25日，星期天仅包括综合属性对于所有Ａ→Ｘ1

Ｘ2

…Ｘn，Ａ的属性计算仅用Ｘ1…Ｘn

的属性如：算术表达式求值的属性文法Ｓ-属性定义：第14页,共49页，2024年2月25日，星期天Ｌ-属性定义：其属性可用深度优先的顺序从左至右计算对于所有Ａ→Ｘ1

Ｘ2

…

ＸnＸi

属性计算仅使用ＡＸ1

Ｘ2

…

Ｘi-1

的属性如：说明语句的属性文法第15页,共49页，2024年2月25日，星期天翻译模式

（TranslationSchemes）特征规定在语法分析中使用语义规则进行计算的次序保证当动作使用某属性时，该属性必须是可用的实现方法将语义动作插入到产生式中的某个位置第16页,共49页，2024年2月25日，星期天例6-5：建立说明语句的翻译方案产生式语义规则D→TLL.in:=T.typeT→intT.type:=‘integer’T→realT.type:=‘real’L→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)将语义动作中的计算向前移，使继承属性的计算出现在其文法符号之前第17页,共49页，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)}第18页,共49页，2024年2月25日，星期天习题1.下列文法是一个二进制数的文法。试根据该文法，编写一个语法制导定义，描述由

S生成的二进制数的数值计算。

S->L.LL->LB|BB->0|12.参照下列表达式文法编写语法制导定义，描述表达式的类型计算。要求在不同精度的数的计算中，结果取精度高的类型。

E->E+T|TT->n.n|n第19页,共49页，2024年2月25日，星期天6.2中间语言用于编译程序源程序经过语义分析被译成中间代码序列（中间语言的语句）用中间语言过渡的好处：便于编译系统的实现、移植、代码优化第20页,共49页，2024年2月25日，星期天常用的中间语言三地址代码（四元式）语法结构树（三元式）后缀式特点形式简单、语义明确、便于翻译独立于目标语言第21页,共49页，2024年2月25日，星期天语法制导编译描述方法利用属性文法描述如何将各种语句和表达式翻译成中间代码工作方式分析与综合并行进行每识别出一个语言结构时，完成相应的语义检查与中间代码生成第22页,共49页，2024年2月25日，星期天语法结构树例6-5：表达式(A-12)*B+6的语法结构树第23页,共49页，2024年2月25日，星期天将赋值语句变换为语法结构树设置属性：E.p是语法结构树指针id.entry是名字的表项入口num.val是数值树构造函数mknode建中间结点mkleaf建叶结点第24页,共49页，2024年2月25日，星期天生成语法树的属性文法第25页,共49页，2024年2月25日，星期天例6-6：a:=b*(-c)+b*(-34)的语法结构树:=*-0+*-0idbnum34idbidcidaroot第26页,共49页，2024年2月25日，星期天语法结构树的三元式表示地址算符操作数操作数012345678910第27页,共49页，2024年2月25日，星期天三地址代码一般形式x:=yopz其中x,y,z为变量名、常数或编译产生的临时变量四元式（op,x,y,z）种类：x:=yopz双目运算

x:=opy单目运算

x:=y赋值

ifxrelopygotol条件转移第28页,共49页，2024年2月25日，星期天其他三地址代码gotol 无条件转移paramx 实在参数callp,n(n是参数个数) 过程调用returnx 过程返回x:=y[i] 数组运算x[i]:=yx:=&y 指针运算x:=*y*x=y第29页,共49页，2024年2月25日，星期天6.3

赋值语句的翻译翻译的需求充分了解各种语言现象的语义包括：控制结构、数据结构、单词充分了解它们的实现方法目标语言的语义了解中间代码的语义了解运行环境第30页,共49页，2024年2月25日，星期天实现赋值语句的翻译语义过程产生一条中间代码gen(code)产生新的临时变量newtemp属性设置中间代码序列code存储位置place第31页,共49页，2024年2月25日，星期天赋值语句的四元式翻译S→id:=ES.code:=E.code||gen(id.place':='E.place)E→E1+E2E.place:=newtemp;E.code:=E1.code||E2.code||gen(E.place':='E1.place'+'E2.place)E→E1*E2E.place:=newtemp;E.code:=E1.code||E2.code||gen(E.place':='E1.place'*'E2.place)第32页,共49页，2024年2月25日，星期天注释：||表示代码序列的连接E→-E1E.place:=newtemp;E.code:=E1.code||gen(E.place':=0-'E1.place)E→(E1)E.place:=E1.place;E.code:=E1.codeE→idE.place:=id.place;E.code:=''E→numE.place:=num.val；E.code:=''第33页,共49页，2024年2月25日，星期天例6-7：

翻译a:=-c+b*34第34页,共49页，2024年2月25日，星期天结果：开始符号的属性S.code1)找出分析树中使用的产生式规则2)根据产生式的语义规则，代换公式中的各属性3)反复使用1)和2)改写公式，最后得到代码生成语句组成的公式组成语句的翻译结果（中间代码序列）第35页,共49页，2024年2月25日，星期天中间代码的生成过程S.code=>E.code||gen(‘a:=‘E.place) /*‘a’=>id.place*/=>E1.code||E2.code ||gen(‘t1:=‘E1.place’+’E2.place) ||gen(‘a:=t1’) /*newtemp=>t1=>E.place*/=>E11.code||gen(‘t2:=0-’E11.place) /*newtemp=>t2=>E1.place*/第36页,共49页，2024年2月25日，星期天 ||E21.code||E22.code ||gen(‘t3:=’E21.place’*’E22.place) /*newtemp=>t3=>E2.place*/ ||gen(‘t1:=t2+t3’)||gen(‘a:=t1’)=>gen(‘t2:=0-c’)||gen(‘t3:=b*34’) /*‘c’=>E11.place*/ /*‘b’=>E21.place*/ /*‘34’=>E22.place*/ ||gen(‘t1:=t2+t3’)||gen(‘a:=t1’) /*‘’=>E21.code=>E22.code*/第37页,共49页，2024年2月25日，星期天表达式翻译中的其他问题运算类型检查利用符号表保存的名字类型类型自动转换填加专用指令临时变量空间的统计了解需求、及时释放第38页,共49页，2024年2月25日，星期天6.4控制结构的翻译高级语言的控制结构顺序begin语句;语句…end条件if_then_elseif_thenswitchcase循环while_dodo_whileforrepeat_util三地址代码的控制结构gotolifxrelopygotol第39页,共49页，2024年2月25日，星期天S→whileCdoS1

的翻译属性设置布尔式C真出口true假出口false语句S入口begin后续段入口nextC.codetoC.truetoC.false=S.nextS.begingotoS.beginS.next…S.codeS1.codeC.truetoS1.next=S.begin第40页,共49页，2024年2月25日，星期天

S→whileCdoS1

代码生成的语义规则

C.false:=S.next; C.true:=newlabel; S.begin:=S1.next:=newlabel;S.code:=gen(S.begin':')||C.code|| gen(C.true':')||S1.code||gen('goto'S.begin)语义过程新标号的产生newlabel继承属性：C.trueC.falseS.next综合属性：S.codeS.begin第41页,共49页，2024年2月25日，星期天S→ifCthenS1elseS2

的翻译C.codetoC.truetoC.falseS1.codeC.truetoS1.next=S.nextS2.codeC.falsetoS2.next=S.nextgotoS.nextS.next…S.begin第42页,共49页，2024年2月25日，星期天S→ifCthenS1elseS2

代码生成的语义规则

C.true:=newlabel; C.false:=newlabel; S1.next:=S2.next:=S.next;S.code:=C.code||gen(C.true':')||S1.code|| gen('goto'S.next)||gen(C.false':')||S2.code第43页,共49页，2024年2月25日，星期天简单布尔表达式的翻译 C→E1relopE2语义规则C.code:=E1.code||E2.code ||gen('if'E1.placerelop.opE2.place'goto‘C.true)||gen('goto‘C.false)第44页,共49页，2024年2