当前位置：文档之家 › 语法制导翻译技术

语法制导翻译技术

  • 格式：pdf
  • 大小：1.08 MB
  • 文档页数：102

下载文档原格式

  / 102

合集下载

编译原理课件05语法制导翻译技术和中间代码生成

编译原理课件05语法制导翻译技术和中间代码生成

5.4 中间代码
四元式的特点: 1. 四元式出现的顺序和语法成份的计值 顺序相一致. 2. 四元式之间的联系是通过临时变量实 现的,这样易于调整和变动四元式. 3. 便于优化处理.
5.4 中间代码
编译系统中,有时将四元式表示成另一 种更直观,更易理解的形式——三地址代 码或三地址语句. 三地址代码形式定义为: result := arg1 OP arg2 三地址语句:语句中是三个量的赋值语句, 三地址语句 每个量占一个地址.
5.5 自下而上的语法制导翻译
例3 简单算术表达式翻译到四元式的 语义描述 例如,设有简单算术表达式的文法: E→E+E | E*E | (E) | i
T R / S T
c S a c
c R S
输入是bR / bTc / bSc /ac 输出为: 1 4 5 314 24 31 给出相应语义动作(翻 译方案) S→bTc { print "1"} { print "2"} S→a R T→R { print "3"} R→R/S { print "4"} R→S { print "5"}
5.1 概述
例如: 表达式 A+B*C 对运算对象进行类型检查, 对变 量进行先定义后使用检查 执行真正的翻译 如果静态语义正确, 语义处理则要执 行真正的翻译, 即生成程序的某种中间 代码的形式或直接生成目标代码.
5.1 概述
目前多数编译程序进行语义分析的方 法是采用语法制导翻译法 .它不是一种 采用语法制导翻译法 形式系统, 但它比较接近形式化. 语法制导翻译法使用属性文法为工具 来描述程序设计语言的语义.
5.4 中间代码

编译原理 第5章语法制导的翻译

编译原理 第5章语法制导的翻译

属性和文法符号相关联 规则和产生式相关联

根据需要，将文法符号和某些属性相关联， 并通过语义规则来描述如何计算属性的值


E→E1+T E.code=E1.code || T.code || ‘+’ code表示了我们关心的表达式的逆波兰表示，规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示并置， 然后加上‘+’得到。
digitlexval=3
18
适用于自顶向下分析的SDD


前面的表达式文法存在直接左递归，因 此无法直接用自顶向下方法处理。 消除左递归之后，无法直接使用属性val 进行处理：


比如规则：T→FT’ T’→*FT’ T对应的项中，第一个因子对应于F， 而运算符在T’中。
19
相同表达式的不同文法的比较
38
例5.15 分析栈实现的例子

假设语法分析栈存放在一个被称为stack 的记录数组中，下标top指向栈顶；


stack[top]指向这个栈的栈顶；stack[top-1] 指向栈顶下一个位置； 如果不同的文法符号有不同的属性集合，我 们可以使用union来保存这些属性值。（归 约时，我们知道栈顶向下的各个符号分别是 什么）
语义翻译的流程
输 入 符 号 串 分 析 树 依 赖 图
语
义
规
则
的 计
实际上，编译中语义翻译的实现并不是 按图中的流程处理的；而是随语法分析 的进展，识别出一个语法结构，就对它 的语义进行分析和翻译。
算
9
5.1 语法制导定义

4.什么是语法制导定义（SDD） 上下文无关文法和属性/规则的结合；

语法制导翻译

语法制导翻译
主要内容包括： 1. 语法制导翻译的基本概念 2. 中间代码简介 3. 符号表简介 4. 典型声明语句与可执行语句的翻译
2
4.1 语法制导翻译简介
语法与语义
1. 语法与语义的关系 语法是指语言的结构、即语言的“样子”；语义是指附着于语
言结构上的实际含意 ，即语言的“意义”。 ① 语义不能离开语法独立存在； ② 语义远比语法复杂； ③ 同一语言结构可包含多种含意，不同语言结构可表示相
② 若b是α中某文法符号Xi的属性，c1, c2, ..., ck是A的属性， 或者是α中其它文法符号的属性，则称b是Xi的继承属性。
③ 称(4.1)中属性b依赖于属性c1, c2, ..., ck。
④ 若语义规则的形式如下述(4.2)，则可将其想像为产生式左 部文法符号A的一个虚拟属性。属性之间的依赖关系，在 虚拟属性上依然存在。
k := k+1;
9
4.1 语法制导翻译简介
产生式
语法制导定义
翻译方案
L→E
print(E.post)
print_post(post);
E → E1 + E2 E → num
E.post := E1.post || post(k) := '+'; E2.post || '+'; k := k+1;
1. 编译器各阶段的完整输出，均可以被认为是源程序的某种 中间表示。
2. 本章讨论的是中间代码生成器输出的中间表示，称之为中 间代码。
3. 中间代码实际上应起一个编译器前端与后端分水岭的作用。 4. 要求中间代码具有如下特性，以便于编译器的开发移植和
代码的优化： ① 便于语法制导翻译； ② 既与机器指令的结构相近，又与具体机器无关。 5. 中间代码的主要形式：树、后缀式、三地址码等。

语法制导的翻译方案

语法制导的翻译方案

语法制导的翻译方案1. 引言语法制导翻译是一种基于文法规则的翻译技术，它可以将源语言文本转化为目标语言文本。

在本文档中，我们将介绍语法制导的翻译方案，包括其基本原理、常用方法以及在实际应用中的一些注意事项。

2. 基本原理语法制导的翻译方案基于上下文无关文法（Context-Free Grammar，CFG）和语义动作，它通过在文法规则中插入动作，实现从源语言到目标语言的翻译过程。

在每个文法规则中，我们可以定义一个或多个动作，这些动作在分析过程中被触发，并产生对应的目标语言文本。

3. 常用方法3.1 自顶向下翻译自顶向下翻译是一种从文法的起始符号开始，逐步扩展语法树的过程。

它可以按照语法规则的顺序依次进行翻译，对于每个文法规则，我们可以定义相应的语义动作来生成目标语言文本。

自顶向下翻译的优点是简单直观，但在处理左递归时可能会出现无限递归的情况。

3.2 自底向上翻译自底向上翻译是一种从文法的终结符开始，逐步构建语法树的过程。

它通过将终结符逐步合并为非终结符，最终构建出完整的语法树。

自底向上翻译的优点是可以有效处理左递归，并且可以在翻译过程中处理语法上的歧义。

3.3 语法推导翻译语法推导翻译是一种基于文法推导的翻译方法。

它通过将源语言文本转化为一个推导序列，然后通过逐步应用文法规则，将推导序列转化为目标语言文本。

语法推导翻译的优点是可以明确表示翻译过程中的每一步，并且可以通过扩展文法规则来处理文法上的不完备性。

4. 实际应用中的注意事项在实际应用中，语法制导的翻译方案需要考虑以下几点注意事项：•文法设计：文法的设计需要充分考虑源语言和目标语言之间的语法结构和语义关系。

合理地定义文法规则和语义动作，可以提高翻译的准确性和效率。

•优化翻译过程：在翻译过程中，我们可以通过优化技术来提高翻译的效率。

例如，可以使用语法分析器生成的语法树作为翻译的输入，避免重复的语法分析过程。

•处理语义歧义：在翻译过程中，可能会遇到多义词或歧义句子的情况。

属性文法和语法制导翻译

属性文法和语法制导翻译

id1
如果一属性文法不存在属性 之间的循环依赖关系，那么 称该文法为良定义的
T type
5 in L
4
real
7 in L y 8 ,
y6 id3 entry 3
9 in L y 10 ,
id2 entry 2
id1 entry 1
属性的计算顺序
无环有向图的拓扑排序
无环有向图中节点m1,m2,…,mk的拓扑排序是：若 mi→mj是从mi到mj的边，那么在此排序中mi先于mj 依赖图的任何拓扑排序都给出了一个分析树中各节点 语义规则计算的正确顺序，即在计算f之前，语义规则
real id1,id2,id3
语法制导翻译
基于属性文法的处理过程通常是：
对符号串进行语法分析，
构造语法分析树
根据需要遍历语法树并在语法树的各结点处按语义规 则进行计算。
这种由源程序的语法结构驱动的处理办法就是语法制 导翻译法。
在某些情况下，在进行语法分析的同时完成语义规则
的计算而无须明显地构造语法树或构造属性之间的依
real L.in=real ,
id3
L.in=real ,
id2
id1

产生式 D→TL T→int T→real L→L1 , id
L→id
语义规则 L.in := T.type T.type := integer T.type := real L1.in := L.in addtype(id.entry, L.in) addtype(id.entry, L.in)
为每个包括过程调用的语义规则引入一个虚综合属性b，把每条 语义规则都变成b=f(c1,c2,...,ck)的形式 依赖图的每个结点表示一个属性 边表示属性间的依赖关系。如果属性b依赖于属性c，那么从c到 b就有一条有向边

第8讲 语法制导翻译_1

第8讲 语法制导翻译_1
输入：
3*5+4n
副作用(Side effect)
语义规则
E.val=15 + T.val=4
print(E.val)
E.val = E1 .val + T.val E.val = T.val
T.val = T1val × F.val
T.val = F.val
T.val=15
F.val=4
T.val=3 * F.val=5 digit.lexval=4
如果一个SDD是S属性的，可以按照语法分析树节点的任何 自底向上顺序来计算它的各个属性值
S-属性定义可以在自底向上的语法分析过程中实现
L- 属 性 定 义
L-属性定义( 也称为L属性的SDD或L-SDD) 的 直观含义：在一个产生式所关联的各属性之间， 依赖图的边可以从左到右，但不能从右到左 ( 个SDD是L-属性定义，当且仅当它的每个属性要 么是一个综合属性，要么是满足如下条件的继承属 性：假设存在一个产生式A→X1X2…Xn，其右部符 号Xi (1 i n)的继承属性仅依赖于下列属性：
A的继承属性 产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性 Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路
将每个产生式和一组语义规则相关联，用来计算 该产生式中各文法符号的属性值
文法符号的属性
综合属性 ( synthesized attribute) 继承属性 ( inherited attribute)
综 合 属 性 ( synthesized attribute)
在分析树结点 N上的非终结符A的综合属性只能通 过 N的子结点或 N本身的属性值来定义
两个概念
将语义规则同语法规则（产生式）联系起来要 涉及两个概念

语义分析与语法制导翻译

/* newtemp => t1 => E.place */ => E11.code || gen( ‘t2:= 0 -’ E11.place )
/* newtemp => t2 => E1.place */
|| E21.code || E22.code || gen( ‘t3:=’ E21.place’*’E22.place )
9
8
三地址代码
一般形式 x := y op z
其中 x, y, z 为变量名、常数或编译 产生的临时变量
四元式（op, x, y, z）
种类：x := y op z
双目运算
x := op y
单目运算
x := y
赋值
if x relop y goto l
条件转移
其他三地址代码
goto l param x call p, n (n是参数个数) return x x := y[i] x[i] := y x := &y x := *y *x = y
注释： || 表示代码序列的连接
Ｓ
例 6-7：
翻译 a:= -c+b*34
id := Ｅ
Ｅ1 ＋
Ｅ2
－
Ｅ 11 Ｅ 21 ＊
Ｅ 22
id id
num
结果：开始符号的属性 S.code
1) 找出分析树中使用的产生式规则 2) 根据产生式的语义规则，代换公式中的
各属性 3) 反复使用 1) 和 2) 改写公式，最后得
如：算术表达式求值的属性文法
Ｌ-属性定义：
其属性可用深度优先的顺序从左 至右计算
对于所有 Ａ→Ｘ1 Ｘ2 … Ｘn Ｘi 属性计算仅使用Ａ Ｘ1 Ｘ2 …

第08章语法制导翻译和中间代码生成

28
常用的中间语言
• 三地址代码（四元式） 三地址代码（四元式） • 语法结构树（三元式） 语法结构树（三元式） • 后缀式
特点
• 形式简单、语义明确、便于翻译 形式简单、语义明确、 • 独立于目标语言
29
三元式和树形表示
• 每个三元式由三个部分组成，分别是：算符op， 每个三元式由三个部分组成，分别是：算符op， op 第一运算对象ARG1和第二运算对象ARG2 ARG1和第二运算对象ARG2。 第一运算对象ARG1和第二运算对象ARG2。运算 对象可能是源程序中的变量， 对象可能是源程序中的变量，也可能是某个三 元式的结果，用三元式的编号表示。 元式的结果，用三元式的编号表示。 • 表达式的树形表示很容易实现：简单变量或常 表达式的树形表示很容易实现： 数的树就是该变量或常数自身，如果表达式e1 数的树就是该变量或常数自身，如果表达式e1 e2的树分别为T1和T2，那么e1+e2 e1*e2， 的树分别为T1 e1+e2， 和e2的树分别为T1和T2，那么e1+e2，e1*e2， e1的树分别为 的树分别为： －e1的树分别为：
9
–lexval 是单词 digit 的属性 lexval
例8-3 3*5+4 的
语法树与属性计算
Ｌ Print(19) E.val=19
E.val=15 T.val=15 T.val=3 F.val=3 digit.lexval=3 ＊
＋
T.val=4 F.ቤተ መጻሕፍቲ ባይዱal=4
F.val=5 dgit.lexval=5
• 用中间语言过渡的好处： 用中间语言过渡的好处：
–便于编译系统的实现、移植、代码优化 便于编译系统的实现、移植、 便于编译系统的实现

语法制导翻译和中间代码生成

addtype(id.entry,L.in)
继承属性L.in
语 义 规 则
语句： real id1， id2， id3 的分析树，采用自上而下的分析方法
产 生 式
D TL
T int
T real
L L1,id
L id
L.in:=T.type
T.type=integer
F.val=3
F.val=5
digit.lexval=4
digit.lexval=5
digit.lexval=3
+
*
3*5+4的带注释的分析树
如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S属性定义。通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个节点的属性值。
表达式文法 E→T+T| T or T T → n | true | false
E → T1 + T2 { T1.type = int AND T2.type = T1. type E.type :=int } E → T1 or T2 { T1.type = bool AND T2.type= T1.type E.type :=bool } T → n { T.type := int } T → true { T.type := bool } T → false { T.type := bool }
T.type:=real
L1.in:=L.in
addtype(id.entry,L.in)
addtype(id.entry,L.in)
D
L.in= real
L.in= real
L.in= real
T.type=real

语法制导翻译和中间代码生成【共50张PPT】


例 完成类型检查的属性文法
1) E→T1+T2{T1.t＝int AND T2.t＝int}
2) E→T1 or T2 {T1.t＝bool AND T2.t＝bool}
3) T→num
{T.t :＝int}
4) T→true {T.t :＝bool}
5) T→false
{T.t :＝bool}
6.1 属性文法(续)
四元式（续）
四元式的优点：
四元式比三元式更便于优化 优化要求改变运算顺序或删除某些运算，引起编号的变化。 三元式通过编号引用中间结果，编号的变化引起麻烦；四元 式通过临时变量引用中间结果，编号变化无影响。
四元式对生成目标代码有利
四元式表示很类似于三地址指令，很容易转换成机器代 码。
四元式（续）
3) E→T
{ E.val :＝T.val }
4) T→T1*F { T.val :＝T1.val * F.val }
5) T→F
{ T.val :＝F.val }
6) F→(E) { F.val :＝E.val }
7) F→digit { F.val :＝digit.lexval }
E.val、T.val、F.val都是综合属性
每个使用性标识符是否都有声明？ 运算符的分量类型是否相容？ 赋值语句的左右部的类型是否相容？
➢ 赋值语句的翻译目标：
在赋值语句右部表达式产生的四元式序列后加一 条赋值四元式
简单赋值语句到四元式的翻译
考虑如下文法描述的简单赋值句的翻译： A→i:=E E→E+E|E*E|-E|(E)|i (6.1)
:=
a
+
叶子结点代表运算量， 非叶子结点代表运算符
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

11/84
3*5+4的分析树加注释的过程
L Print (19) E .val=19 E .val=15 T .val=15 T .val=3 * F .val=5 + T .val=4 F .val=4 digit .lexval=4
F .val=3
digit .lexval=3
digit .lexval=5
9/84
简单算术表达式求值的语法制导定义
产生式 LE EE1+T E T TT1*F TF F(E) Fdigit


语义规则 print(E.val) E.val=E1.val+T.val E.val=T.val T.val=T1.val*F.val T.val=F.val F.val=E.val F.val=digit.lexval
?

属性值的计算可以在语法分析过程中进行。
12/84
继承属性


分析树中，一个结点的继承属性值由该结点的父结 点和/或它的兄弟结点的属性值决定。 可用继承属性表示程序设计语言结构中上下文之间 的依赖关系
–可以跟踪一个标识符的类型 –可以跟踪一个标识符，了解它是出现在赋值号的右边还是 左边，以确定是需要该标识符的值还是地址。
第5章 语法制导翻译技术
LI Wensheng, SCST, BUPT
知识点：语法制导定义、翻译方案 S-属性定义、L-属性定义 S-属性定义的翻译 L-属性定义的翻译
语法制导翻译技术

语义分析涉及到语言的语义 形式语义学的研究开始于20世纪60年代初 形式语义学可以分为三类
– 操作语义学：通过说明程序在一个机器中是如何执行的来定义程序的 语义，着重模拟数据加工过程中计算机系统的操作 – 指称语义学：使用数学函数来描述程序和程序的构成，函数通过把语 义值联系到正确的语法结构来描述程序的语义，主要描述数据加工的 结果 – 公理语义学：把数理逻辑应用于语言的语义，语言结构与谓词转换器 联系在一起，语言结构的行为以命题刻画，通过描述程序执行对程序 断言的影响来定义程序、语句或语言结构的语义，主要用于程序正确 性证明

语法制导翻译技术
– 多数编译程序普遍采用的一种技术 – 比较接近形式化
2/84
语法制导翻译

基本思想：为了翻译由上下文无关文法确定的语言，可以对文法符号 附加属性，并且在文法中设置对属性求值的语义规则，语义规则和非 终结符的每个产生式相关 两种描述语法制导翻译的形式
– 语法制导定义：是关于语言翻译的高层次规格说明，隐去实现细节，不规 定翻译顺序 – 翻译方案：给出实现途径，指明语义规则的求值顺序
综合属性val与每一个非终结符号E、T、F相联系 表示相应非终结符号所代表的子表达式的整数值 LE的语义规则是一个过程，打印出由E产生的算术表达式 的值，可以认为是非终结符号L的一个虚拟综合属性。
10/84
综合属性




分析树中，如果一个结点的某一属性由其子结点的 属性确定，则这种属性为该结点的综合属性。 如果一个语法制导定义仅仅使用综合属性，则称这 种语法制导定义为S-属性定义。 对于S-属性定义，通常采用自底向上的方法对其分 析树加注释，即从树叶到树根，按照语义规则计算 每个结点的属性值。 简单台式计算机的语法制导定义是S-属性定义
13/84
用继承属性L.in传递类型信息的语法制导定义
产生式 DTL Tint Treal LL1,id Lid

语义规则 L.in=T.type T.type=integer T.type=real L1.in=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)


语法制导翻译的一般步骤： 输入符号串
分析树
依赖图 语义规现，不需要显式地产生分析树和 依赖图。“L-属性”定义包含了所有能够不显式构造分析树而完成的 翻译
3/84
翻译结果

生成代码
–可以为源程序产生中间代码 –可以直接生成目标机指令



属性b依赖于属性c1、c2、…、ck。 语义规则函数都不具有副作用的语法制导定义称 为属性文法
8/84
语义规则

一般情况：
–语义规则函数可写成表达式的形式。

某些情况下：
–一个语义规则的唯一目的就是产生某个副作用，如打印一 个值、向符号表中插入一条记录等； –这样的语义规则通常写成过程调用或程序段。 –看成是相应产生式左部非终结符号的虚拟综合属性。 –虚属性和符号‘=’都没有表示出来。
对输入符号串进行解释执行 向符号表中存放信息 给出错误信息 翻译的结果取决于语义规则
–使用语义规则进行计算所得到的结果就是对输入符号串 进行翻译的结果。
4/84
语法制导翻译技术
5.1 5.2 5.3 5.4 语法制导定义及翻译方案 S-属性定义的自底向上翻译 L-属性定义的自顶向下翻译 L-属性定义的自底向上翻译 小 结
5/84
5.1

语法制导定义及翻译方案
是上下文无关文法的推广
每个文法符号都可以有一个属性集，可以包括两类属性：综 合属性和继承属性。
– 分析树中一个结点的综合属性是从其子结点的属性值计算出来的 – 继承属性是从其兄弟结点和/或父结点的属性值计算出来的 – 分析树中某个结点的属性值是由与在这个结点上所用产生式相应的语 义规则决定的。

依赖图：由语义规则建立的属性之间的关系
– 用途：可以得到语义规则的计算顺序

语义规则的副作用：语义规则是一个动作或过程 带注释的分析树：每个节点都带有属性值

分析树加注释（装饰分析树）：计算各节点属性值的一系列 活动
6/84
本节内容安排
一、语法制导定义 二、依赖图 三、计算次序 四、S属性定义和L属性定义 五、翻译方案
7/84
一、语法制导定义
在一个语法制导定义中，对应于每一个文法产生式 A，都有与之相联系的一组语义规则，其形式为： b=(c1,c2,…,ck) 这里，是一个函数，而且或者
(1) b是A的一个综合属性，且c1、c2、…、ck是产生式 右部文法符号的属性，或者 (2) b是产生式右部某个文法符号的一个继承属性，且c1、 c2、…、ck是A或产生式右部任何文法符号的属性。