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

语法制导翻译概括

  • 格式：ppt
  • 大小：283.50 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

编译原理第八章—语法制导翻译

编译原理第八章—语法制导翻译


属性文法

属性的抽象表示 例如：E.val（值） E.type（类型） E.code（代码序列） E.place（存储空间）
属性文法

E
T
文法G：

+
T
ET1+T2|T1 or T2 Tnum|true|false
3
4
ET1+T2 {T1.t=int AND T2.t=int} ET1orT2{ T1.t=bool AND T2.t=bool} E{T1.t=T2.t} Tnum {T.t=int} T{T1.t=int} + Ttrue {T.t=bool} T{T2.t=int} Tfalse {T.t=bool}
语法分析
语义分析 中间代码生成 中间代码 语 义 处 理
后 端 处 理
代码生成
汇编代码
语义处理
源语言程序 词法分析 前 端 处 理 语法分析 语义分析 语 义 处 理 后 端 处 理
代码生成
汇编代码
语义分析基础

语义处理的实现（第八章）

属性文法：描述语义规则。 语法制导翻译：在语法分析的同时，执行语义规则描述 的动作： • 检查静态语义 • 生成中间代码/目标代码 为语义分析提供类型、作用域等信息。 为代码生成提供类型、作用域、存储类别、存储（相对 ）位置等信息。
语义分析基础

语法与语义的关系

语法是指语言的结构、即语言的“样子”； 语义是指附着于语言结构上的实际含意 ，即语言的“ 意义”。 语义不能离开语法独立存在； 语义远比语法复杂； 同一语言结构可以包含多种含意，不同语言结构表示相 同含意； 语法与语义之间没有明确的界线。
6-1-语义分析和语法制导翻译

6-1-语义分析和语法制导翻译

（Inherited Attributes）。
2022/2/4
7
属性文法的定义
定义6.3 属性文法AG是一个四元组：AG=(G,A,R,B), 其中, G是已简化的CFG;
A=∪X∈VA(X)是属性的有限集合;
R= ∪p∈PR(p)是属性定义规则的有限集;
B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使R(p)有效 的条件；
1．每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每 个属性都有一个允许值的集合（属性的值域，可以是无限集）。
2．非终结符和动作符的属性可分为继承属性与综合属性两类。
3．继承属性的定义规则为：
①开始符号的继承属性具有指定的初始值；
②对于给定的产生式p:Y→X1X2…Xn∈P,Xi的继承属性值由p中其它符号 的属性值进行计算：Xi.a=f(Y.b, Xk1.ak1,…,Xkm.akm) i{k1,…,km}
2022/2/4
2
中间代码
中间代码生成：
–指把单词符号串形式的源程序转换为另一种等价的便于 代码优化处理和目标代码生成表示。
两个主要问题：
–如何描述语言的语义（语法制导翻译方法）； – 中间代码如何表示（逆波兰表示、三元式、四元式等）。
2022/2/4
3
语法制导翻译方法概述
语法制导翻译方法
– 在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的 语义子程序进行翻译（产生中间代码）的方法。
– 实质就是根据文法中每个产生式的语义，为其配备若干个语义子程序， 对所要完成的功能进行描述。
产生式语义：
– 由组成该产生式所有文法符号的语义决定。
语义：
– 文法符号X的语义信息，称之为语义属性或简称为属性。 – 可用形如X.ATTR的记号来表示文法符号X的相关语义属性。
编译原理第五章语法制导翻译

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


状态 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） 上下文无关文法和属性/规则的结合；
编译原理第八-章语法制导翻译

编译原理第八-章语法制导翻译

静态单赋值形式（Static Single Assi…
一种优化的三地址码形式，通过消除冗余和不必要的赋值操作，提高代码的执行效率。
目标代码生成
机器语言
将中间代码转换为机器语言，以便在特定的计算机硬件上执行。
指令选择
根据中间代码和目标机器的指令集，选择合适的指令进行目标代 码生成。
寄存器分配
为中间代码中的变量分配寄存器，以优化目标代码的执行效率。
03
02
语法制导翻译
根据源语言的语法规则，将源代码 逐步翻译为目标代码。
代码优化
在翻译完成后，对目标代码进行优 化，以提高执行效率。
04
递归下降翻译
语法分析
将源代码分解为一个个的子句或语句， 并确定每个子句或语句的类型。
中间代码生成
将处理后的子句或语句转换成中间代 码。
语义处理
根据子句或语句的类型，编写相应的 语义动作，处理每个子句或语句的语 义。
语法分析
根据语法规则，将词素或符号组合成一个个的语法结构，如表达式、语句等。
中间代码生成
将语法结构转换成中间代码，通常是一种更接近于机器语言的代码形式。
代码优化
对中间代码进行优化，以提高执行效率。
自顶向下翻译
01
目标语言的设计
首先设计目标语言的语法和语义， 然后编写相应的语义动作。
语义检查
在翻译过程中进行语义检查，确保 源代码的语义正确性。
代码优化
控制流优化
通过消除冗余的分支和循环，优化代码的控制流结构。
数据流优化
通过消除冗余的计算和数据传输，优化代码的数据流 路径。
死代码消除
删除在程序执行过程中永远不会被使用的代码，减少 程序的体积和提高执行效率。
第8章：语法制导翻译

第8章：语法制导翻译

第八章 语法制导翻译
学习目标 语义分析程序将依据语言的语义规则对语法分析得到 的语法结构进行静态语义检查（确定类型、 的语法结构进行静态语义检查（确定类型、类型和运算合法 性检查、 性检查、识别含义与相应的语义处理及其它一些静态语义检 ），并用另一种内部形式表示出来 并用另一种内部形式表示出来， 查），并用另一种内部形式表示出来，或者直接用目标语言 表示出来。 表示出来。
8.1.1 一般原理
翻译的任务：首先是语义分析和正确性检查，若正确， 翻译的任务：首先是语义分析和正确性检查，若正确， 则翻译成中间代码或目标代码。 则翻译成中间代码或目标代码。 语义分析通常采用语法制导翻译。基本思想是，根据翻 语义分析通常采用语法制导翻译。基本思想是 语法制导翻译 译的需要设置文法符号的属性，以描述语法结构的语义。 译的需要设置文法符号的属性，以描述语法结构的语义。 例如，一个变量的属性有类型，层次，存储地址等。 例如，一个变量的属性有类型，层次，存储地址等。表 达式的属性有类型，值等。 达式的属性有类型，值等。属性值的计算和产生式相联 随着语法分析的进行，执行属性值的计算， 系。随着语法分析的进行，执行属性值的计算，完成语 义分析和翻译的任务。 义分析和翻译的任务。
(3)
8.1.1 一般原理
例如: 例如 SDTS T1=({a,b,c,+,,[,]},{E,T,A},{ADD,SUB,N EG,x,y,z},R,E)，其中 由下 ，其中R由下 列翻译规则组成： 列翻译规则组成： ①E→ E+T,T E ADD → E→ ②E→ E-T,E T SUB ③E→ –T,T NEG → ④E→ T,T → ⑤T→ [E],E → ⑥T→ A,A → ⑦A→ a,x → ⑧A→ b,y → ⑨A→ c,z →
06第6章语法制导翻译技术概论

06第6章语法制导翻译技术概论


① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
2020/11/13
8
语法制导翻译的基本思想 通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执 行相应的语义动作。 具体方法： 1．将文法符号所代表的语言成分的意思，用隶属于该文法符 号的属性表示； 2．用语义规则(语义规则的执行就是语义动作)规定产生式所 代表的语言成分之间的关系（即属性之间的关系），即用语义 规则实现属性计算。 3.语义动作(语义规则的执行)： 在语法分析的适当时刻（如推导或归约）执行附在对应产生 式上的语义规则，以实现对语言结构语义的处理，如计算、查 填符号表、生成中间代码、发布出错信息等。
10
－对改写后文法的每个非终结符号编写一个函数。
代标 码代 优码 化生
目 标 代 码
成
成
➢ 词法分析和语法分析仅仅对源程序做形式变换和检查。
➢ 语义分析检查程序语义是否正确。
➢ 中间代码生成将语义分析后的结果翻译成代码。
☻上述工作过程采用串行处理方式 ☻实际应用中语法分析、语义分析、中间代码生成采用并
行处理方式
2020/11/13
3
并行处理方式：
消除左递归得到： E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@c
求FIRST集和 FOLLOW集不 考虑动作符号
FIRST(TE’)={(,a,b,c} FIRST(+T@+E’)={+} FOLLOW(E’)={#,)} FIRST(FT’ )={(,a,b,c} FIRST(*F @* T’)={*} FOLLOW(T’)={#,+,)} FIRST((E))={(} FIRST(a@a)={a} FIRST(b@b)={b} FIRST(c@c)={c}
第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本身的属性值来定义
两个概念
将语义规则同语法规则（产生式）联系起来要 涉及两个概念
最新六章语法制导翻译与属文法

最新六章语法制导翻译与属文法


2021/1/11
10
典型处理方法二
翻译模式
通过将属性与文法符号关联，并将语义规则插入到产生式 的右部来描述语言结构的翻译方案
在产生式的右部的适当位置，插入相应的语义动 作，按照分析的进程，执行遇到的语义动作
D → T { L.inh := T.type } L
T → int { T.type := integer }
这两种情况下，都说属性b依赖于属性c1，c2，…，ck
2021/1/11
14
例6.1 台式计算器的语法制导定义
产生式 LEn E E1+T E T T T1*F T F F (E) F digit
语义规则 print(Eval)(可看作是L的虚属性) Eval := E1val+Tval Eval := Tval Tval := T1val+Fval Tval := Fval Fval := Eval Fval := digitlexval
E→E1 + E2
E.val:=E1.val+E2.val
语法结构具有规定的语义
问题：如何根据被识别出的语法成分进行 语义处理？
亦即怎样将属性值的计算及翻译工作同产生式 相关联？
2021/1/11
9
典型处理方法一
语法制导定义
通过将属性与文法符号关联、将语义规则与产生 式关联来描述语言结构的翻译方案
2021/1/11
16
继承属性
当分析树的结构同源代码的抽象语法不“匹 配”时，继承属性将非常有用。下面的例子 可以说明怎样用继承属性来解决这种不匹配 问题，产生这种不匹配的原因是因为文法通 常是为语法分析而不是为翻译设计的。
例6.2
第五章 语法制导翻译

第五章 语法制导翻译


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
第五章 语法制导翻译(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)

语法制导翻译概述

例如，一个变量的属性有类型，层次，存储地址等 。表达式的属性有类型，值等。属性值的计算和产 生式相联系。随着语法分析的进行，执行属性值的 计算，完成语义分析和翻译的任务。
❖ 属性一般分为两类：综合属性和继承属性。 简单的说，综合属性用于“自下而上”传递 信息，而继承属性用于“自上而下”传递信 息。
逆波兰、四元式、三元式、树型
6.1.1 逆波兰记号（后缀式）
❖ 将运算对象写在前面，把运算符号写在后面
表达式 a+b a+b*c (a+b)*c a=b*c+b*d
逆波兰式 ab+ abc*+ ab+c* abc*bd*+=
❖ 后缀式的计算机处理 ➢ 后缀式的最大优点是易于计算机处理 ➢ 处理过程：
❖ 格式： (算符, 第一运算对象, 第二运算对象, 结果)
❖ 如： a=b*c+b*d (1) (*,b,c,t1) (2) (*,b,d,t2) (3) (+,t1,t2,t3) (4) (=,t3,-,a)
四元式的特点
❖ 类似于三地址指令 ❖ 四元式虽然比三元式多了一结果的引用，但有利于优
化和代码生成 ❖ 为了便于书写四元式也可以写成如下形式： ❖ <结果>:=<运算对象1><运算符><运算对象2> ❖ 则表达式a+(-b*c+d)*e的四元式为：
从左到右扫描后缀式，每碰到运算对象就推进栈； 碰到运算符就从栈顶弹出相应目数的运算对象施加 运算，并把结果推进栈。最后的结果留在栈顶。
例：表达式－b＋c*d的后缀式 b@cd*+的计值过程
d
c
t2
t1
bt1

第五章语法制导的翻译

第五章语法制导的翻译本章继续展开2.3节的主题：使用上下文无关文法来引导对语言的翻译。

本章讨论的翻译技术将在第六章中被用于类型检查和中间代码生成。

这些技术也可以用于实现那些完成特殊任务的小型语言；本章包含了一个有关排版的例子。

如2.3.2节讨论的，我们把一些属性附加到代表语言构造的文法符号上，从而把信息和一个语言构造联系起来。

一个语法制导定义通过附加在文法规则上的语义规则来定义属性的值。

比如，一个从中缀表达式到后缀表达式的翻译器可能包含如下的产生式和规则：产生式语义规则E→E1+T E.code = E1.code || T.code || ‗+‘(5.1)这个产生式有两个非终结符号E和T；E1的下标区分了E在产生式体中的出现和E在产生式头上的出现。

E和T都有一个字符串类型的属性code。

上面的语义规则指明E的代码是通过将E1.code、T.code和字符‗+‘连接而得到的。

虽然这个规则明确指出对E的翻译结果是根据E1、T的翻译结果和‘+‘构造得到的，直接通过字符串操作来实现这个翻译过程可能很低效。

根据2.3.5节，一个语法制导的翻译方案在产生式体中包含了被称为语义动作的程序片段。

比如E→E+T{print ‗+‘} (5.2)按照惯例，语义动作被放在花括号之内。

（对于作为文法符号出现的花括号，我们将用单引号把它们括起来，比如‗{‘和‗}‘。

）一个语义动作在产生式体中的位置决定了这个动作的执行顺序。

在产生式(5.2)中的语义动作出现在所有文法符号之后的末端；一般情况下，语义动作可以出现在一个产生式体中的任何位置。

对这两种标记方法作一个比较。

语法制导定义更加易读，因此更适合作为对翻译的规约。

而翻译方案更加高效，因此更加适合用于翻译的实现。

最通用的完成语法制导翻译的方法是先构造一个语法分析树，然后通过访问这棵树的结点来计算各个属性的值。

在很多情况下，翻译可以在扫描分析过程中完成，不需要构造出明确的语法分析树。

编译第七章语法制导翻译_OK


{PRINT E ●VAL}
• (1)E E(1) +E(2) {E●VAL=E(1)●VAL+E(2)●VAL}
• (2)E E(1) * E(2) {E●VAL=E(1)●VAL*E(2)●VAL}
• (3)E (E(1)) {E●VAL=E(1)●VAL}
• (4)E i
{E●VAL=LEXVAL}
语义子程序
• (0)S’ E
{PRINT VAL[TOP]}
• (1)E E(1) +E(2) {VAL[TOP]=VAL[TOP]+VAL[TOP+2]}
• (2)E E(1) * E(2) {VAL[TOP]=VAL[TOP]*VAL[TOP+2]}
• (3)E (E(1)) {VAL[TOP]=[TOP+1]}
语义子程序
• (1)A i=E {GEN(=,E●PLACE,_,ENTRY(i)}
• (2)E -E(1) {T=NEWTEMP;
• ----
GEN(@,E(1)●PLACE,_,T);
• ----
E●PLACE=T}
• (3)E E(1)*E(2) {T=NEWTEMP;
•
GEN(*,E(1)●PLACE,E(2)●PLACE,T);
• 2、实例：对布尔式X+Y>Z∨A∧( B∨C) 进行翻译：
SYM栈
i i= i=i=-i i=-E i=E i=E* i=E*( i=E*(i i=E*(E
PLACE栈
---------B --T1 --T1--T1---T1--C --T1--C
生成四元式
(@,B,-,T1)
❖21

语法制导的翻译


E2
E2=E1*c
二、其它语法成分的逆波兰表示：
1.赋值语句:
<左部>:=<表达式>
把‘:=’看成一个运算符号——赋值运算，它为一特殊的双目运算，则对应的逆波兰表示为：
<左部> <表达式的逆波兰表示> :=
例：x:=100
逆波兰表示为：
x100 :=
x:=a*b+c/d
逆波兰表示为：
xab*cd/+:=
例
（1）递归子程序法的代码生成 （2）利用优先矩阵的语法分析直接生成目标代码 （3）利用逆波兰算法进行语法、语义分析
（1）语法分析－语义分析： 直接生成目标代码 优点：编译相对简单，时间效率高 缺点：空间代价较高 （2）语法分析－－中间代码－优化－目标代码
后缀表示法与前缀表示法及中缀表示法相比较，其共同的特点是：
(1)运算符的个数不变 ;
(2)运算量的次序和个数不变。
在计算机处理过程中可以用一个栈 (硬件或软件栈) 来计算它的值。一般的计算过程是：自左向右扫描后缀式，每逢遇到运算量就令其入栈； 遇到K目运算符，则将它作用于栈顶的K个项，并用运算结果代替这K个项。
(+ , T1 , T2 , T)
例2.-(a*b-c)
(* , a , b , T1)
(- , T1 , c , T2)
(@ , T2 , / , T)
@表示单目运算减
赋值语句的四元式：
把赋值看成一种运算，<分量2 >为空
例1：x:=10
(:= , 10, / , x)
例2：x:= -(a*b-c)
7.2 两种编译流程
例如有如下表达式： a+b a+b*c (a+b)*c

第五篇语法制导的翻译


注意：if(curToken == ε)肯定不对，因 为ε不是一个符号
具有受控副作用的语义规则
• 属性文法没有副作用，但增加了描述的复杂度
– 比如语法分析时如果没有副作用，标识符表就必须 作为属性传递。 – 可以把标识符表作为全局变量，然后通过副作用函 数来添加新标识符；
• 受控的副作用
– 不会对属性求值产生约束，即可以按照任何拓扑顺 序求值，不会影响最终结果。 – 或者对求值过程添加简单的约束。
• 那么
– A XR – R YR1 – Rε R.i = f(X.x); A.a = R.s R1.i = g(R.i, Y.y); R.s=R1.s R.s = R.i
• 新文法中R对应的部分和原文法中A对应的部分互补；
– 对于AXY1Y2……Yn；如果R对应于YYi……Yn；互补的 A对应于AY1……Yi-1 – R.i等于互补的A的A.s
*
F
T’1
digit:5 ε
适用于自顶向下分析的SDD
• 注意：T’的属性inh实际上继承了相应的*号的 左运算分量。
3*5的注释分析树
• 请观察inh属性是如何传递的。
消直接左递归时语义规则的处理
• 假设：
– AA1Y A.a = g(A1.a, Y.a) – AX A.a = f(X.x)
• 递归子程序法中，在过程A()的最后计算A的属性（此时 A调用的其他过程（对应于子结构）已经调用完毕）
在分析树上计算SDD
• 按照后序遍历的顺序计算属性值即可 postorder(N) { for(从左边开始，对N的每个子结点C) postorder(c); //递归调用返回时，各子结点的属性计算完毕 对N的各个属性求值； } • 在LR分析过程中，我们实际上不需要构造分析树的 结点。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
一般来讲，对出现在产生式右边的继承属性和出现在
产生式左边的综合属性都必须提供一个计算规则，属性
计算规则中只能使用相应产生式的文法符号的属性，这
有利于产生式范围内“封装属性的依赖性。然而，出
现在产生式左边的继承属性和出现在产生式右边的综合
属性不由所给的产生式的属性计算规则进行计算，它们 由其它产生式的属性规则计算,由属性计算器的参数提 供。
• 则表达式(*)*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￥
看成一目运算符， 表示
把￥ 看成三目运 算符，表示 – –
语法制导翻译法不论对自上而下分析或自下而上分析 都适用
翻译的任务：语法结构的静态语义分析 和正确性检查，若正确，则翻译成中间代 码或目标代码。
使用的方法:称作语法制导翻译。
基本思想（简言之）:根据翻译的需要设 置文法符号的属性(这些属性代表与文法 符号相关的信息)，以描述语法结构的语
例义如，。一个变量的属性有类型，层次，存储地址等。
（
）
可以使编译程序的结构清晰、简单、明确。源程序的一种内 部表示，不依赖目标机的结构，易于机械生成目标代码的中间表 示。
为什么要此阶段及使用原则
主要优点是可移植(与具体目标程序无关)，且易于目标代码优化 原则：１、形式比较简单，容易翻译成相应的目标机器代码。
２、能充分反映源程序的特点。
中间代码的几种形式
语义规则所描述的工作可以包括属性计算、静态语义检 查、符号表操作、代码生成等。语义规则可能产生副作 用（如产生代码），也可能不是变元的严格函数（如某 个规则给出可用的下一个数据单元的地址）。这样的语 义规则通常写成过程调用，或过程段。 综合属性：
语法制导定义的形式
一个属性文法它包含一个上下文无关文法和一系列 语义规则，这些语法规则附在文法的每个产生式上。 在一个语法制导定义中， 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 中间代码(源程序的中间形式)
何谓中间代码：
表达式的属性有类型，值等。属性值的计算和产生 式相联系。随着语法分析的进行，执行属性值的计 算，完成语义分析和翻译的任务。
• 属性一般分为两类：综合属性和继承属性。 简单的说，综合属性用于“自下而上”传递 信息，而继承属性用于“自上而下”传递信 息。
• 属性加工加工的过程即是语义处理的过 程，对于文法的每一个产生式都配备了一组 属性的计算规则，则称为语义规则。