第5章 语法制导翻译和中间代码生成.ppt

《第5章 语法制导翻译和中间代码生成.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、文法和语言的基本知识编译概述词法分析与有穷自动机语法分析语法制导翻译和中间代码生成符号表的组织和管理123456代码优化静态存储分配目标代码生成789第5章语法制导翻译和中间代码生成自动机编译中的语义处理是两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间边式形式（中间代码），要么生成实际的目标代码。§5.1属性文法属性文法的形式定义：一个属性文法形式上可定义为一个三元组A，A=（G，V，F）。其中G表示一个上下文无关文法；

2、V表示属性的有穷集；F表示有关属性的断言或谓词的有穷集。属性可以分为综合属性和继承属性两类。综合属性一般用于自下而上传递信息，而继承属性常常用于自上而下传递信息。简单算术表达式求值的属性文法。规则语义规则1.S→Eprint（E.val）2.E→E1＋TE.val:=E1.val＋T.val3.E→TE.va1:=T.valv4.T→T1FT.val:=T1.valF.val5.T→T1T.val:=T1.val6.F→（E）F.val:=E.val7.F→digitF.val:=digit.lexval例5.1：此例中，每一个非终结符都有一个表示整数值的属性val，如E

3、.va1，表示E的整数值。按照语义规则，每个规则的左部符号如E，T，F等的属性值的计算取决于各自相应的右部非终结符，我们把这种属性称为综合属性。单词digit仅有综合属性，它的值是由词法分析程序提供的。与规则S→E关联的语义规则是一个过程print（E.vd），其功能是打印由E产生的表达式的值。对于在语义规则中并没有出现文法符号S，我们认为其属性是虚的或者空的。说明语句中各种变量的类型信息的语义描述。规则语义规则1.D→TLL.in:=T.type2.T→intT.type:=integer3.T→realT.type:=real4.L→L1，idL1.in:=L.inadd

4、type（id.entry，L.in）5.L→idaddtype（id.entry，L.in）例5.2：与例中对应的原文法可以表示为1.D→intL｜realL2.L→L，id｜id下图是句子intid1，id2的语法树。用“→”表示属性信息的传递情况。DTLLint，id1id2属性信息的传递情况§5.2语法制导翻译概述语法制导翻译技术分为自底向上语法制导翻译和自顶向下语法制导翻译。下面以LR语法制导翻译为例，讨论如何具体实现语法制导翻译。假定有输入串3＋45，这是一个简单的算术表达式，相应的文法及各产生式的语义规则见例5.1。表达式3＋45的语法制导翻译法求值过程语法

5、树描述图E.val:=335E.val:=234E.val:20E.val:=5E.val:=4+Sny.valYSn-1x.valX┋┋┋S0-#状态栈语义值栈文法符号符号栈扩充的LR分析栈状态actiongoto＋（）d#ETF0s4s51231s6acc2s7r2r2r23r4r4r4r44s4s58235r6r6r6r66s4s5937s4s5108s6s119s7r1r1r110r3r3r3r311r5r5r5r5LR分析表步骤状态栈语义栈符号栈剩余串主要动作10-#3＋45#205--#3＋45#303-3#F＋45#r6402-3#T＋45#r450

6、1-3#E＋45#r26016-3-#E＋5#70165-3--#E＋45#80163-3-4#E＋F5#r690169-3-4#E＋T5#r41001697-3-4-#E＋T5#11016975-3-4--#E＋T5#120169（10）-3-4-5#E＋TFr6130169-3-20#E＋T#r31401-23#E#r115acc表达式3＋45的语法语义分析和计值过程§5.3中间语言所谓中间语言，也称中间代码，是复杂性介于源程序语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序

7、结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中间语言。编译程序所使用的中间语言形式较多。常见的逆波兰式、三元式、四元式和树形表示等。逆波兰式是最简单的一种中间语言形式，用逆波兰式表示的表达式也称做后缀式。它的特点是将运算对象写在前面，把运算符号写在后面，比如把x＋y写成xy＋，把xy写成xy。对于简单表达式E，相应的逆波兰式E′遵循下面的转换规则：表达式逆波兰式EE′(E)E′5.3.1逆波兰式－EE@（负号“－”是一元运算符，为了区别于减号“－”，通常写成@）E1opE2E1′E