语法制导翻译概括
一般来讲,对出现在产生式右边的继承属性和出现在
产生式左边的综合属性都必须提供一个计算规则,属性
计算规则中只能使用相应产生式的文法符号的属性,这
有利于产生式范围内“封装属性的依赖性。然而,出
现在产生式左边的继承属性和出现在产生式右边的综合
属性不由所给的产生式的属性计算规则进行计算,它们 由其它产生式的属性规则计算,由属性计算器的参数提 供。
• 则表达式(*)*e的四元式为:
•
(1) t1
•
(2) t21*c
•
(3) t32
•
(4) t43*e
•
(5) t54
• 同样要将算法语言翻译成相应的四元式, 也要将四元式扩充到其他运算符,如()表
示无条件转向第L条四元式。
6.1.4 汇编代码
汇编语言是依赖于机器的低级程序设计语 言,它是面向具体的计算机系统或相应 的计算机系列的,它和三元式相比有以 下优点:
逆波兰、四元式、三元式、树型
6.1.1 逆波兰记号(后缀式)
• 将运算对象写在前面,把运算符号写在后面
表达式
*c ()*c **d
逆波兰式
*+ * **
• 后缀式的计算机处理
• 后缀式的最大优点是易于计算机处理
• 处理过程:
• 从左到右扫描后缀式,每碰到运算对象就推进 栈;碰到运算符就从栈顶弹出相应目数的运算对象 施加运算,并把结果推进栈。最后的结果留在栈
2.b是 中的符号的一个继承属性并且c1, c2,…,是A或 中的任何文法符号的属性。
在两种情况下,都说 属性b依赖于属性c1,c2,…,。
要特别强调的是:
(1)终结符只有综合属性,它由词法分析器提供; (2)非终结符既可以有综合属性也可以有继承属性, 文法开始符号的所有继承属性作为属性计算前的初始值。
例顶:。表达式-b+c*d的后缀式 *+的计值过程
d
c
t2
t1
tb 1
t1
t1= - b
t2= c*d t3= t12
• 逆波兰表示法的扩充
• 逆波兰表示法很容易扩充到表达式以外的范 围
• 例如: 语句
逆波兰表示 备注
看作二目运算符
L E S1 S2
L 1S2¥
看成一目运算符, 表示
把¥ 看成三目运 算符,表示 – –
语法制导翻译法不论对自上而下分析或自下而上分析 都适用
翻译的任务:语法结构的静态语义分析 和正确性检查,若正确,则翻译成中间代 码或目标代码。
使用的方法:称作语法制导翻译。
基本思想(简言之):根据翻译的需要设 置文法符号的属性(这些属性代表与文法 符号相关的信息),以描述语法结构的语
例义如,。一个变量的属性有类型,层次,存储地址等。
(
)
可以使编译程序的结构清晰、简单、明确。源程序的一种内 部表示,不依赖目标机的结构,易于机械生成目标代码的中间表 示。
为什么要此阶段及使用原则
主要优点是可移植(与具体目标程序无关),且易于目标代码优化 原则:1、形式比较简单,容易翻译成相应的目标机器代码。
2、能充分反映源程序的特点。
中间代码的几种形式
语义规则所描述的工作可以包括属性计算、静态语义检 查、符号表操作、代码生成等。语义规则可能产生副作 用(如产生代码),也可能不是变元的严格函数(如某 个规则给出可用的下一个数据单元的地址)。这样的语 义规则通常写成过程调用,或过程段。 综合属性:
语法制导定义的形式
一个属性文法它包含一个上下文无关文法和一系列 语义规则,这些语法规则附在文法的每个产生式上。 在一个语法制导定义中, A→ P都有与之相关 联的一套语义规则,规则形式为
b:= f(c1,c2,…,), f是一个函数,而且
1.b是A的一个综合属性并且c1,c2,…,是 中的符号的属性,或者
逆波兰示例
• 例: • 把下述产生式定义的算术表达式映射到后缀波兰表示:
产生式
E E T T TF
T F F (E) F a
翻译成分
• 确定输入 a的输出:
•
() ()
•
()
•
()
•
()
•
( +)
•
( +)
•
( +)
•
( +)
6.1.2 三元式和树形表示
• 格式: (算符, 第一运算对象, 第二运算对象)
• 如:
**d
=
(1) (*) (2) (*)
a
+
(3) (+,(1),(2)) (4) (=,(3))
*
*
b
c
b
d
6.1.3 四元式
• 由于三元式中的结果是用它的编号表示的,当在三 元式进行优化后,就要用一定的时间重新安排三元 式的编号,很费时间。为了防止优化后的重新编址, 在三元式基础上增加了一个存放结果的单元,这就 形成了四元式子,是一种最常用的形式。
(1)能方便地翻译成目标机器指令。 (2)不必直接计算转移地址。 (3)可以使用各种数据表示法。
6.2 语法制导翻译的概述(如何 把源程序翻译成相应的中间代码)
基本思想: 在语法分析过程中,随着分析的步步进展,每当 使用一条产生式进行推导(对于自上而下分析) 或归约(对于自下而上分析),就执行该产生式 所对应的语义动作,完成相应的翻译工作。 语法制导翻译就是把语言的一些属性附加到代表 语言结构的文法符号上,这些属性值是由附加到 文法产生式的“语义规则”中计算的,也就是为 每个产生式配备翻译子程序,即语义子程序。
• 格式: (算符, 第一运算对象, 第二运算对象, 结果)
• 如: **d (1) (*1) (2) (*2) (3) (123) (4) (3)
四元式的特点
• 类似于三地址指令
• 四元式虽然比三元式多了一结果的引用,但有利于优 化和代码生成
• 为了便于书写四元式也可以写成如下形式:
• <结果><运算对象1><运算符><运算对象2>
编译程序的功能和组织结构
表处理
前 端中 中后目端
源 程 序
词语语间间标 法法义代代代 分分分码码码 析析析生优生
目 标 程 序
成化成
错误处理
第六章 语法制导翻译
6.1 中间代码的形式 6.2 语法制导翻译的概述 6.3 自底向上的制导翻译
6.1 中间代码(源程序的中间形式)
何谓中间代码:
表达式的属性有类型,值等。属性值的计算和产生 式相联系。随着语法分析的进行,执行属性值的计 算,完成语义分析和翻译的任务。
• 属性一般分为两类:综合属性和继承属性。 简单的说,综合属性用于“自下而上”传递 信息,而继承属性用于“自上而下”传递信 息。
• 属性加工加工的过程即是语义处理的过 程,对于文法的每一个产生式都配备了一组 属性的计算规则,则称为语义规则。