当前位置：文档之家 › 第五章++语法制导翻译(1)

第五章++语法制导翻译(1)

  • 格式：ppt
  • 大小：288.55 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

编译原理课件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 中间代码
语法制导翻译1(BEST)

语法制导翻译1(BEST)

语法制导的翻译 语义分析的任务：语义分析的输入是语法分析的输出（分析树），输出是中间代码，但同时它还完成了很多语义处理工作。

 语义检查：如，类型、运算、维数、越界等。

 语义处理：如，变量的存储分配、表达式的求值、语句的翻译（中间代码的生成）等。

 总目标：生成等价的中间代码。

 语义分析的主流技术：语法制导翻译技术。

4.1 语法制导的翻译静态语义分析通常包括：① 类型检查。

② 控制流检查。

控制流语句必须使控制转移到合法 的地方。

③ 一致性检查。

④ 相关名字检查。

有时，同一名字必须出现两次或 多次。

例如，Ada语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾， 编译程序必须检查这两个地方用的名字是相同的。

⑤ 名字的作用域分析语法制导的翻译动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。

语法制导的翻译 语义动作的计算是在对应产生式被归约时进行。

 语义规则和产生式相联系的两种方式 语法制导定义 对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。

 语法制导的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。

4.1 语法制导的定义例 简单台式计算器的语法制导定义产 生 式 语 义 规 则 L → E nprint (E .val ) E → E 1 + TE .val := E 1 .val + T.val E → TE .val := T.val T → T 1 * FT.val := T 1.val * F.val T → FT.val := F.val F → (E )F.val := E.val F → digit F.va l := digit .lexval 属性文法（也称属性翻译文法） K nuth在1968年提出 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。

编译原理第五章语法制导翻译

编译原理第五章语法制导翻译


状态 0 1 2 3 4 5 6 7 8
+
s5 r4 r3 r1 r2
LR(0)分析表 action o n b # S4 S3 acc s7 r4 r4 r4 r4 r3 r3 r3 r3 s4 s3 r1 r1 r1 r1 s4 s3 r2 r2 r2 r2
GOTO E T 1 2
6 8
LR分析器的栈加入语义值。
的前缀表示法相比较，其共同的特点是： 1. 运算符的个数不变 2. 运算量的次序和个数不变 同时, 逆波兰表示法还具有两个明显的优点： 1. 无括号，形式简洁清楚 2. 运算符的顺序与运算的次序完全相同
（4）相关名字检查。有时，同一名字必须出现两 次或多次。例如，Ada 语言程序中，循环或程 序块可以有一个名字，出现在这些结构的开头 和结尾，编译程序必须检查这两个地方用的名 字是相同的。 (5)名字的作用域分析

如果语义正确，则进行中间代码的翻译。
中间代码
何谓中间代码 . Intermediate code Intermediate representation Intermediate language
第五章 语法制导翻译和 中间代码的生成
本章的主要内容
语法制导翻译的基本思想；
典型的中间代码表示法；
产生中间代码的语义子程序设计；
各种基本语言成分的自下而上分析的制导
翻译； 类型检查的基本原理。

语义分析是干什么的？
其任务是对语法分析所识别出的各类语法范畴， 分析其含义，并进行初步翻译。 包括两个方面的工作。 首先是对各种语法范畴进行静态语义检查，例 如，变量是否定义、类型是否正确等等。 如果语义正确，则进行中间代码的翻译。
编译原理 第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） 上下文无关文法和属性/规则的结合；
第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本身的属性值来定义
两个概念
将语义规则同语法规则（产生式）联系起来要 涉及两个概念
第5章 语法制导翻译和中间代码生成

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


剩余串 3＋ 45# ＋45# ＋45# ＋45# ＋45# 5# 5# 5# 5# 5# #
主要动作
r6 r4 r2
r6 r4
r6 # # r3 r1 acc
表达式3 ＋ 4 5的语法语义分析和计值过程
§5.3
中间语言
所谓中间语言，也称中间代码，是复杂性介 于源程序语言和机器语言的一种记号系统。一般 来说，快速编译程序直接生成目标代码，没有将 中间代码翻译成目标代码的额外开销。但是为了 使编译程序结构在逻辑上更为简单明确，使生成 的的目标代码更为高效，通常采用中间语言。 编译程序所使用的中间语言形式较多。常见 的逆波兰式、三元式、四元式和树形表示等。来自bcd
3. 间接三元式 为了尽量不改变三元式表，可以另设一张间 接码表来表示有关三元式在三元式表的 计值顺序。用这种方法获得的中间代码 称为间接三元式。
例如，表达式a := x＋y z b := t－y z 的间接三元式表示如图所示。
三元式列表 （1）（ ，y，z） （2）（＋，x，（1）） （3）（:=，a，（2）） （4）（－，t，（1）） （5）（:=，—，（4））
§5.4 自底向上语法制导翻译
语法制导翻译分为自底向上和自底向下两种。 自底向上语法制导翻译方法就是在自底向上语法 分析过程中逐步执行语义规则。也就是在每次归 约的同时执行相应的语义动作。
5.4.1 简单算术表达式和赋值语句的翻译
简单算术表达式和赋值语句是指不含数组 元素、记录等复杂数据结构的算术表达式和赋值 语句。
简单算术表达式求值的属性文法。 例5.1 ：
规则 1.S→E 2.E→E1＋T 3.E→T 4.T→T1 F 5.T→T1 6.F→（E） 7.F→digit 语义规则 print（E.val） E.val := E1.val＋T.val E.va1 := T.valv T.val := T1.val F.val T.val := T1.val F.val := E.val F.val := digit.lexval
第五章 语法制导翻译

第五章 语法制导翻译


n
Eval:=15 +
Tval:=4
Tval:=15
Fval:=4
Tval:=3 * Fval:=5 digitlexval:=4
Fval:=3
digitlexval:=5
digitlexval:=3 3*5 +4的语义分析过程 11
5.1 语法制导定义(Syntax-directed definitions)
在语法分析推导或归约的每一步骤
中，通过语义规则实现对属性的计
算，以达到对语义的处理
6
换句话说是：为每一个产生式配 上语义规则并且在适当的时候执行这 些规则。
即当归约（或推导）到某个产生式 时，除了按照产生式进行相应的代换 之外(语法分析)，还要按照产生式所对 应的语义规则执行相应的语义动作， 如计算表达式、查填符号表、产生中 间代码(语义分析)
22
练习：设AS为文法的综合属性集，AI 为继承属性集，则下列语法制导定义 中
产生式
语义规则
P→xQR
Q.b=R.d
R.c=1
R.e=Q.a
Q→ u
Q.a=3 23
P→yQR
R→v 试求AS和AI
Q.b=R.f R.c=Q.a R.e=2 R.d=R.c R.f=R.e
24
解：由1知：Q.b,R.e∈AI 由3知： R.c∈AI 由4知： R.d,R.f ∈AS 由2知：Q.a=3∈AS
语法制导定义也叫属性文法，它是在上
下文无关文法的基础上，通过每个文法
符号和一个属性集合相关联，通过每一
个产生式和一个语义规则集合相关联。 语义规则用来计算与产生式中出现的
符号相关联的属性的值 。
9
12
语法制导翻译5.1-5.4

语法制导翻译5.1-5.4

析的同时完成属性计算
5.3 L属性定义的自上而下计算
5.3.1 L属性定义
❖ 如果每个产生式AX1…Xj-1Xj…Xn的每条语 义规则计算的属性是A的综合属性；或者是Xj 的继承属性，但它仅依赖：
该产生式中Xj左边符号X1, X2, …, Xj-1的属性； A的继承属性
❖ S属性定义属于L属性定义
T.val = T1.val F.val T.val = F.val F.val = E.val F.val = digit.lexval
5.2 S属性定义的自下而上计算
简单计算器的语法制导定义改成栈操作代码
产生式
代码段
LEn
print (val [ top1] )
... ... top
Z Z. z
❖ 非终结符既可有综合属性也可有继承属性；
不允许结点N上的继承属性通过N的子结点上的属性值定义 允许N的综合属性通过结点N的继承属性来定义
❖ 总可以用综合属性来改写语法制导定义，但使用带有继承属性 的语法制导定义更为自然。
举例：使用继承属性跟踪一个标识符，看它是出现在赋值号的左 边还是右边来确定它的地址还是它的值—上下文有关
简单计算器的语法制导定义改成栈操作代码
产生式
代码段
... ... top
Z Z. z Y Y. y X X.x ... ...
栈 state val
LEn E E1 + T
ET T T1 F
T F F (E)
print (val [ top1] ) val [top 2 ] = val [top 2]+val [top]
F.val = E.val F.val = digit.lexval
华东师范大学计算机科学技术系PPT课件

华东师范大学计算机科学技术系PPT课件

师范大学计算机科学技术系
11
• 后缀表示可以机械地计算。 • 中缀表示可以机械地转换为后缀表示。
（E.W.Dijkstra) • 例2： (-a*b+c)-d的后缀表示为：a b* uminus c+d-
其中uminus表示一元运算‘-’。
• 后缀表示的推广： O1，O2，……，On， 其中是n元的运算符， Oi为运算对象 i=1,2……n。
01.08.2020
华东师范大学计算机科学技术系
8
3. 如何实现这种翻译？
• 语法制导翻译的关键，是为每个产生式编写翻译子 程序。例1中产生式所带有的这种语义子程序只能 输出这类数字串。现在，要对一个有穷表示的文法 的无穷多个语句，按所给出的语义子程序要完成不 同语句的翻译任务，输出各自的目标代码。难点自 然就集中在如何写这些语义子程序了。
(4) 一致性检查。
如在相同作用域中标识符只能说明一次（重复定 义），case语句的标号不能相同，枚举类型的元素 不能重复，没有定义数据类型等。
01.08.2020
华东师范大学计算机科学技术系
4
二、语法制导翻译
• 例1：对算术表达式文法G[<E>]的一个翻译方案
<E>→<E>+<T> {print “1”}
• 采用属性翻译文法（属性文法），这是一种形式化 的语义分析方法。
01.08.2020
华东师范大学计算机科学技术系
9
结论
• 语法制导的翻译方法就是在语法分析的同时（制导 下）插入一系列的语义动作（由语义子程序提供）， 将源程序（单词形式）翻译成等价的中间代码。
• 主要考虑自底向上句法分析的方法（在归约时调用 语义子程序），设计翻译方案（形成属性文法）。
第五章 语法制导翻译(1)

第五章 语法制导翻译(1)

编译原理 26
另一例 非L属性的语法制导定义
文法符号B的继承属性依赖于它右边文法符号C的 属性。
产生式 ABC
语义规则 A.s := B.b B.i := f(C.c, A.s)
编译原理
27
例5.10
编译原理
28
例5.10 简单类型声明的SDD
产 生 式 语 义 规 则
D TL
T int
id2 2 entry
编译原理
30
float id1, id2, id3的分析树的依赖图
D T 4 type float in 7 in 5 L 8
L 6
, id2 2 entry id3 3 entry
in 9
L 10
,
id1 1 entry
编译原理 31
float id1, id2, id3的注释分析树
(1) p1 := new Leaf(id, entrya); (2) p2 := new Leaf(num, 4); (3) p3 := new Node(„-‟, p1, p2); (4) p4 := new Leaf(id, entryc); (5) p5 := new Node(„+‟, p3,p4); p5 p3 p1 + p4 id entryc p1, p2, ..., p5是指向结点 的指针，entrya和entryc 分别是指向符号表中标 识符a和c的指针。
编译原理
35
为表达式建立语法树的语法制导定义
产生式
EE1+T E E1-T ET T (E) Tid Tnum
语义规则
E.node := new Node(‘+’, E1.node, T.node) E.node := new Node(‘-’ , E1.node, T.node) E.node := T.node T.node := E.node T.node:= new Leaf(id, id.entry) T.node := new Leaf(num, num.val)
编译原理 语法制导翻译

编译原理 语法制导翻译

搜索方法：hash技术…
TinyC中的语法树
typedef enum {StmtK,ExpK} NodeKind; typedef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind; typedef enum {OpK,ConstK,IdK} ExpKind; typedef enum {Void,Integer,Boolean} ExpType; #define MAXCHILDREN 3 typedef struct treeNode { struct treeNode * child[MAXCHILDREN]; struct treeNode * sibling; int lineno; NodeKind nodekind; union { StmtKind stmt; ExpKind exp;} kind; union { TokenType op; int val; char * name; } attr; ExpType type; /* for type checking of exps */ } TreeNode;
作为中间表示形式——分离分析与翻译
在进行语法分析的同时进行翻译存在缺
陷：
适合分析的文法可能未反映自然的语言结构 分析顺序可能与翻译顺序不一致
利用语法制导翻译方法来构造语法树
5.2.1 语法树
（抽象）语法树，压缩形式
关键字和运算符均在内部节点
链式结构会被压缩
语法树压缩例
digit.lexval：终结符只有综合属性，由词法分 析器提供 开始符号通常没有继承属性
5.1.2 综合属性
只有综合属性：S-属性定义
语法树自底向上计算属性

第5章 语法制导翻译1

Name. posttype Name. primtype; Expr. posttype ( Name. primtype int_ type) ?int_ type : real _ type; }
2. Expr Name (1) Add Name ( 2 ) { Attribution: Name (1) . environment Expr . environment ; Name ( 2 ) . environment Expr . environment ;
int Entry(char *Name){ int i=LookUp(Name);
if(i) return i; else return Enter(Name);
翻译程序中使用的辅助函数(续)
⒋int Trip(int op,int arg1,int arg2)—根据给定 的参数产生一个三元式 (op,arg1,arg2) 并将它送入三元式表中，其返回值为表中序号。 为区分参数 arg 表示的是 三元式 还是变量，约定 当arg<0时表示三元式序号；arg>0表示变量在 符号表中登记项序号；arg=0表示参数为空。
文法符号及其语义属性
例如,文法G[E]: 产生式 语义子程序 E→E(1)+T {E.Val=E(1).val+T.val;} E→T {E.Val=T.Val;} T→digit {T.Val=digit;} 为了能在语法分析过程中平行地进行语 义处理，可在语法分析栈旁边并行地设 置一个语义信息栈
语法分 析栈 T + E … # … 语义分 析栈 T.Val ‘+’
5.2 属性文法与属性翻译文法
语法制导翻译方法的实质，就是根据文法中每个产 生式所蕴含的语义，为其配备一个（或多个）处理 语句或子程序，对所要完成的功能进行描述。 产生式的语义是由组成该产生式的文法符号的语义 所决定的。 将这些语义以“属性”的形式附加到各个文法符号 上，再根据产生式所蕴含的语义，给出每个文法符 号的属性的求值规则，从而形成一种附带有语义属 性的前后文无关文法，即属性文法。 语义属性主要有两类：综合属性和继承属性

五章 语法制导的翻译5.1-5.3


5.1 语法制导的定义
分析树各结点属性的计算可以自下而上地完成
L E.val = 18 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 + T.val = 5 F.val = 5 digit.lexval = 5 n T.val = 10 F.val = 2 digit.lexval = 2
5.1 语法制导的定义
分析树各结点属性的计算可以自下而上地完成
L E.val = 18 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 + T.val = 5 F.val = 5 digit.lexval = 5 n T.val = 10 F.val = 2 digit.lexval = 2
5.1 语法制导的定义

例 int id1, id2, id3的标注了部分属性的分析 树
不可能像像综合属性那样自下而上标注属性 D
T.type = integer
int
L.in = integer
L.in = integer
, id2
id3
L.in = integer
,
id1
5.1 语法制导的定义
5.1 语法制导的定义
分析树各结点属性的计算可以自下而上地完成
L E.val = 18 E.val = 8 T.val = 8 F.val = 8 digit.lexval = 8 + T.val = 5 F.val = 5 digit.lexval = 5 n T.val = 10 F.val = 2 digit.lexval = 2
5.1.4 属性依赖图 例 int id1, id2, id3的分析树（虚线）的依赖 图（实线） L L1, id L1.in = L.in;

语法制导翻译技术

}
3. E →（E(1)）{ E.place ＝ E(1).place；} 2020/3/7
第5章 语法制导翻译技术和中间代 码生成
四元式的特点： 1. 四元式出现的顺序和语法成份的计值
顺序相一致。 2. 四元式之间的联系是通过临时变量实
现的，这样易于调整和变动四元式。
3. 便于优化处理。 四元式还可以表示条件的转移
(if a>b goto 0) (goto 0)
2020/3/7
第5章 语法制导翻译技术和中间代 码生成
第5章 语法制导翻译技术和中间代 码生成
➢语义过程 Lookup（） 功能是审查是否出现在符号表中， 在则返回其指针，否则返回NULL。
➢语义变量 E.place 表示存放非终结符E值的变量名在符号 表中的入口地址或临时变量名的整数码。
2020/3/7
第5章 语法制导翻译技术和中间代 码生成
2020/3/7
间接三元式
间接码表 三元式表
(1) (1) ( + , A , B )
(2)
(2) ( * , (1) , C )
(3) (1)
(3) ( = , X , (2) )
(4) (5)
(4) (↑ , D , (1) ) (5) ( = , Y, (4) )
第5章 语法制导翻译技术和中间代 码生成
E E.val = 47
E
+
E.val = 7
E 7 E.val = 8
E E.val = 40
*
E
E.val = 5
8
5
2020/3/7
第5章 语法制导翻译技术和中间代 码生成
5.4 编译中常用的中间代码:

第五章语法制导的翻译

– 规则和产生式相关联
• 对于文法符号X和属性a，我们用X.a表示分 析树中的某个标号为X的结点的值。
• 一个分析树结点和它的分支对应于一个产 生式规则，而对应的语义规则确定了这些 结点上的属性的取值。
分析树和属性值(1)
• 假设我们需要知道一个表达式的类型，以及对 应代码将它的值存放在何处，我们就需要两个 属性：type，place；
T’*FT’
– T对应的项中，第一个因子对应于F，而运算符 却在T’中。
– 需要继承属性来完成这样的计算
相同表达式的不同文法的比较
• 输入串：3*4*5
• 请观察左边的T对应的部分，和右边的T’对应部分
– Ti和T’i恰好互补
• 计算方法：把T’之外部分的值继承给T’。
T3
T
T2 * F
F
T’3
T1 *
分析树和属性值(2)
E.Type = FLOAT E E.Place = &tmp2
E.Type = FLOAT
T.Type = INT

E.Place = &a E + T T.Place = &tmp
T.Type = FLOAT T T.Place = &a
F.Type = FLOAT F F.Place = &a id.lexValue=a id
加法表达式的逆波兰表示由两个分量的逆波兰表示
并置，然后加上‘+’得到。
• 语法制导翻译：
– 在产生式体中加入语义动作，并在适当的时候执行 这些语义动作
– EE1+T {print ‘+’;}
语法制导的定义（SDD）
• SDD是上下文无关文法和属性/规则的结合；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
编译原理 26
另一例 非L属性的语法制导定义
文法符号B的继承属性依赖于它右边文法符号C的 属性。
产生式 ABC
语义规则 A.s := B.b B.i := f(C.c, A.s)
编译原理
27
例5.10
编译原理
28
例5.10 简单类型声明的SDD
产 生 式 语 义 规 则
D TL
T int
编译原理
9
综合属性： E.val, T.val, F.val, digit.lexval 在语法制导定义中，终结符号只有综合属性，它们 的值由词法分析程序提供；digit.lexval 假设开始符号没有继承属性。
编译原理
10
5.1.2 对SDD求值
S属性定义：仅仅使用综合属性的语法制导定义称 为S属性定义。 例5.1中的S属性定义详细说明了一台计算器读入包 含数字，括号，+和*运算符的算术表达式，随后再 读入一个换行字符n，然后打印出表达式值的过程 。 分析树各结点属性的计算可以自底向上地完成。
digit.lexval = 5
编译原理
12
例5.3
产 生 式 语 义 规 则
TFT′ T′ * F T1′ T′ F digit
T′.inh = F.val T.val = T′.syn T1′.inh = T′.inh F.val T′.syn = T1′.syn T′.syn = T′.inh F.val := digit.lexval
编译原理
13
图5-4
T.val = 15
F.val = 3 digit.lexval =3 * T′.inh = 3 .syn =15 F.val = 5 digit.lexval = 5
T1′.inh = 15 .syn =15
编译原理
14
继承属性
一个结点的继承属性值由该结点的父结点和（或） 兄弟结点的属性决定。
编译原理
3
语法制导翻译的一般过程
输入符号串 分析树
依赖图
语义规则的计算顺序
一个句子的翻译过程可以与语法分析过程并行。
编译原理 4
5.1 语法制导定义
语法制导定义是对CFG的推广，每个文法符号都有 一个相关的属性集。 属性：语义信息。一个文法符号通常用一个或若干 个属性来描述它的语义信息。典型例子： 变量的数据类型 表达式的值 变量的存储位置 程序的目标代码
23
5.2.4 L属性定义
一个语法制导定义是L属性定义，如果任意一条产 生式A X1X2 ... Xn，其右部符号Xj(1 j n)的继承 属性仅依赖于 1. 产生式中Xj的左边的符号X1, X2 ,... Xj-1的属性； 2. A的继承属性。 对综合属性没有限制。显然，所有的S属性定义都 是L属性定义。
L.in := T.type
T. type := integer
T float
L L1, id L id
T. type := float
L1.in := L.in; addtype (id.entry, L.in ) addtype (id.entry, L.in )
29
id.entry : 指向符号表的id表目的指针，由词法分析得到 编译原理
id
entrya p2
num 4
to entry for c
38
to entry for a
编译原理
例5.12 L属性定义
产生式
E T E' E' + T E'1
语义规则
E.Node = E'.syn E'.inh = T.Node E'1.inh = new Node(„+‟, E'.inh . T.node) E'.syn = E'1.syn E'1.inh = new Node(„-‟, E'.inh . T.node) E'.syn = E'1.syn E'.syn = E'.inh T.Node = E.node T.Node = new Leaf (id, id.entry) 39 编译原理 T.Node = new Leaf (num, num.val)
编译原理
24
例5.8 L属性
编译原理
25
例5.9 非L属性
文法符号Q的继承属性依赖于它右边文法符号R的 属性。
产生式 A L M A Q R 语义规则 L.i := l(A.i ) M.i := m(L.s) A.s := f(M.s) R.i := r(A.i ) Q.i := q(R.s) A.s := f(Q.s)
第五章 语法制导翻译
1
在文法中，文法符号通常都有明确的意义，文法符 号之间也有确定的语义关系。
用属性描述语义信息，用语义规则描述属性之间的 关系，将语义规则与语法规则相结合。
语法制导翻译(Syntax-Directed Translations)： 在语法分析的过程中计算语义属性值。
编译原理
编译原理
6
语义规则：描述产生式中各文法符号的属性之间的 依赖关系。通常用函数或程序语句的形式表示。 依赖图：表示文法符号属性之间依赖关系的有向图。 注释分析树：每个结点都带有属性值的分析树。
编译原理
7
每个产生式A有一组形如b := f(c1, c2, …, ck )的 语义规则，其中f 是函数，并且满足下面两种情形 之一： 1. b是A的综合属性，c1, c2 , …, ck是产生式右部文 法符号的属性。 2. b是产生式右部某个文法符号的继承属性，且c1 , c2 , …, ck也是该产生式文法符号的属性。 称属性b依赖于属性c1, c2 , …, ck。
33
5.3.1 抽象语法树
语法树是分析树的压缩表示：算符和关键字作为内 部结点。 语法制导翻译可以基于分析树，也可以基于语法树。 语法树的例子：
if-then-else
B S1 S2
+
8
5
编译原理
* 2
34
构造表达式的语法树
三个对象： 1. node (op, left, right)：运算符结点； 2. leaf(id, entry)：标识符叶子结点； 3. leaf(num, val)：数叶子结点。
编译原理
36
图5.11 a-4+c的语法树的构造
6 E node 4 E node 2 E node 1 T node
+
3 T node
5 T node
-
id
num + id num 4
编译原理
id
id to entry for
to entry for c
37
下面函数调用建立表达式a-4+c的语法树。
编译原理
8
例5.1 简单台式计算器的语法制导定义
产 生 式 LEn E E1 + T ET 语 义 规 则 print (E.val) E.val := E1 .val + T.val E.val := T.val
T T1 * F TF F (E) F digit
T.val := T1.val F.val T.val := F.val F.val := E.val F.val := digit.lexval
编译原理
20
循环依赖Circular dependency
产生式 AB 语义规则 A.s := B.i B.i := A.s + 1
A A.s
B
B.i
编译原理 21
属性计算次序
构造输入的分析树， 构造属性依赖图， 对结点进行拓扑排序， 按拓扑排序的次序计算属性。
编译原理
22
5.2.3 S属性定义
编译原理
11
8+5*2 n的注释分析树 (annotated parse tree)
L n
E.val = 18 E.val = 8
T.val = 8 F.val = 8 digit.lexval = 8 +
T.val = 10 * F.val = 2
digit.lexval = 2
T.val = 5 F.val = 5
编译原理
35
为表达式建立语法树的语法制导定义
产生式
EE1+T E E1-T ET T (E) Tid Tnum
语义规则
E.node := new Node(‘+’, E1.node, T.node) E.node := new Node(‘-’ , E1.node, T.node) E.node := T.node T.node := E.node T.node:= new Leaf(id, id.entry) T.node := new Leaf(num, num.val)
2
介绍一种形式化的语义描述方法：语法制导的翻译， 包括两种具体形式 语法制导定义(Syntax-Directed Definitions, SDD)：定义翻译所必须的语义属性和语义规则， 一般不涉及计算顺序。 翻译模式(translation schemes)： 给出语义规 则的计算顺序。 介绍语法制导翻译的实现方法。
如果一个SDD的每个属性都是综合属性，则它是S属性。可 以按照分析树的自底向上顺序来计算各属性值。 后序遍历 postorder (N) { for (从左边开始，对N的每个结点C) postorder (C); 计算N的属性值； } S属性定义可以在自底向上语法分析过程中实现。
编译原理