当前位置：文档之家 › 编译原理作业解析——第五章语法制导翻译技术

编译原理作业解析——第五章语法制导翻译技术

  • 格式：ppt
  • 大小：625.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

编译原理课件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 中间代码

编译原理第五章 语法制导翻译及中间代码生成

编译原理第五章 语法制导翻译及中间代码生成
① ② ③ ④ (U_minus, b, - ) ( + , c, d ) ( * , ①, ② ) ( := , ③, a )
式①中的运算符U_minus表示一元减运算。
翻译程序中使用的辅助函数
⒈int LookUp(char *Name)—以Name查 符号表，若查到则返回相应登记项的序号 (≥1),否则返回0。 ⒉int Enter(char* Name)—以Name为名 字在符号表中登录新的一项,返回值为该项 的序号。 ⒊int Entry(char *Name)—以Name为名 字查、填符号表:
定义 5.3 对每个产生式p:X0→X1X2…Xn ， 设属性定义性出现的集合为 AF(p)={Xi.a|Xi.a=f(Xk1.ak1,…,Xkm.ak m) ∈R(p), 0≤kj≤n} 若Xi 是产生式左部的非终结符(即i=0),则称 属 性 Xi.a 是 综 合 属 性 (Synthesized Synthesized Attributes);若Xi 出现在产生式的右部(即 Attributes 1≤i≤n),则称Xi.a是继承属性（Inherited Inherited Attributes）。 Attributes
逆波兰表示
每一运算符都置于其运算对象之后，故称 为后缀表示。 特点: 特点:表达式中各个运算 运算是按运算符出现的 运算符出现的 顺序进行的，无须使用括号来指示运算顺 顺序进行的 序，因而又称为无括号式 无括号式。
逆波兰表示逆波兰表示-例子
中缀表示 后缀表示
A+B AB+ A+B*C ABC*+ (A+B)*(C+D) AB+CD+* x/y^z-d*e xyz^/de*(a=0∧b>3)∨(e∧x<>y) 思考：能否表示if e then s1 else s2这样的语句？ a0=b3>∧exy<>∧∨ ∧ ∧∨ 将后缀式的符号存放在POST[n]中，

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

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

编译原理课件05语法制导翻译技术和 中间代码生成
21、静念园林好，人间良可辞。 22、步步寻往迹，有处特依依。 23、望云惭高鸟，临木愧游鱼。 24、结庐在人境，而无车马喧；问君 何能尔 ？心远 地自偏 。 25、人生归有道，衣食固其端。
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到ቤተ መጻሕፍቲ ባይዱ时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特

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

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

状态 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） 上下文无关文法和属性/规则的结合；

编译原理 第5章 语法制导翻译技术和中间代码生成

编译原理 第5章 语法制导翻译技术和中间代码生成

必须使用下标进行区分。例： number1number2digit
8
●
example
1) 已知无符号数文法如下，请改写成值属性文法，并对345 进行语义分析。 number number digit | digit digit 0|1|2|3|4|5|6|7|8|9 解： grammar rule
21
对 345进行属性值计算的语法树
number (val=34*10+5=345)
number (val=3*10+4=34)
number (val=3) digit (val=4) 4
digit (val=5) 5
digit (val=3) 3
22
●
example
2) 已知简单的整数算术表达式文法如下，请改写成值属性文 法，并对 (34-3)*42 进行语义分析。 exp exp + term | exp-term | term term term*factor | factor factor (exp) | number 解： grammar rule exp1 exp2+term exp1 exp2-term exp term term1 term2*factor term factor factor (exp) factor number
10
■ 练习
1.简单的整数算术表达式文法如下，请改写成 值属性文法。 E E+ T | T T T*F | F F (E) | I 2. 已知无符号数文法如下，请改写成值属性 文法。 NND|D D0|1|2|3|4|5|6|7|8|9
11
属性分为两类:综合属性和继承属性.一般情况下, 综合属性属于”自下而上”传递信息,继承属性用于 ”自上而下”传递信息. 又根据不同的处理要求，属性可以多种方式出现， 也就是说，与文法符号相关联的可以是各种属性、 语义规则，或者某种程序设计语言的程序段等。

第5章(语法制导翻译技术)-1

第5章(语法制导翻译技术)-1
三元式序列 (1) ( + , A , B ) (2) ( * , (1) , C ) (3) ( = , X , (2) ) (4) ( + , A , B ) (5) (↑ , D , (4) ) (6) ( = , Y, (5) ) 间接三元式 间接码表 三元式表 (1) (1) ( + , A , B ) (2) (2) ( * , (1) , C ) (3) (3) ( = , X , (2) ) (1) (4) (↑ , D , (1) ) (4) (5) ( = , Y, (4) ) (5)
1.E → E(1)＋E(2) 2.E → E(1)*E(2) 3.E → (E(1)) 4.E → digit
{E.val ＝E(1).val ＋E(2).val} {E.val ＝E(1).val*E(2).val} {E.val ＝E(1).val} {E.val ＝Lex.digit} 句子 7+8*5
例2. i↑( i /( i – i ) )的逆波兰式 i i i i – /↑ i↑( i /( i – i ) )的四元式 t1= i – i t2= i / t1 t3= i ↑ t2
5.5.1 简单算术表达式和赋值语句的翻译
语义函数 emit（T＝arg1 OP arg2） （ ＝ 功能是生成一个三地址语句，并送 到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时变量名字， 并回送新的临时变量名的整数码。 如T1，T2等。
第5章 语法制导翻译技术和中间代 码生成
四元式的特点： 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 3. 便于优化处理。 四元式还可以表示条件的转移 (if a>b goto 0) (goto 0)

编译原理5语法制导翻译技术和中间代码生成new

编译原理5语法制导翻译技术和中间代码生成new

作一个100次的循环：
i:=1;
10: if i<=100 then begin s:=s+i; i:=i+1; goto 10
end
i 1 := i 100 <= 21 FJ s s 1 2 3 4 5 i + := i i 1 + := 4 RJ
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
5.3语法制导翻译概述 语法制导翻译法的基本思想：对文法中的每个产生式都附加 上一个语义动作或语义子程序，在执行语法分析的过程中， 每当使用一条产生式进行推导或归约时，就执行相应的产生 式的语义动作。 这些语义动作不仅指明了该产生式所产生的符号串的意义， 而且还根据这种意义规定了对应的加工动作，从而完成预定 的翻译工作。 语法制导翻译法就是在语法分析过程中随着分析的逐步发展， 根据相应文法的每一规则所对应的语义子程序进行翻译的方 法。具体分为自底向上语法制导翻译和自顶向下语法制导翻 译两种。
k:=i*i –j * j ;
i:=0 ; j:=0 End
4 )循环语句的逆波兰表示
对于所有循环语句，我们都可以把它改造为条件语句和转向语 句的组合。
例：for i:=a to b do S:=S+i 可以改写为： i:=a; 10: if i<=b then begin S:=S+i; i:=i+1; goto 10 end
例：赋值语句
x:=5 逆波兰式：x5:=； x:=a*b-c/d 逆波兰式：xab*cd/-:=
2)转向语句的逆波兰式表示 转向语句：goto〈标号〉 逆波兰表示为：〈标号〉LJ 3)条件语句的逆波兰表示

编译原理--语法制导的翻译 ppt课件

编译原理--语法制导的翻译 ppt课件

（２）设code 为综合属性，代表各非终结符 的代码属性
type为综合属性，代表各非终结符的类型属 性
inttoreal把整型值转换为相等的实型值 vtochar将数值转换为字符串
5.3.3 给出一个SDD对x*(3*x+x*x)这样的表达式求 微分。表达式中涉及运算符+和*，变量x和常 量。假设不进行任何简化，也就是说，比如 3*x将被翻译为3*1+0*x。
ST z , R4
8.2.6 确定下列指令序列的代价。
1）
LD R0 , y
2
LD R1 , z
2
ADD R0 , R0 , R1 1
ST x , R0
2
总代价：7
3）
LD R0 , c
2
LD R1 , i
2
MUL R1 , R2 , 8 2
ST a(R1) , R0 2
总代价：8
8.3.3 假设使用栈式分配，且假设a和b都是元素大小为4字节 的数组，为下面的三地址语句生成代码。
的位数次幂值(2 length of L)
S L1.L2 S.val = L1.val +L2.val / L2.b; S L S.val = L.val; L L1 B L.val = L1.val *2 + B.val;
L.b = L1.b*2; L B L.val = B.val; L.b = 2; B 0 B.val = 0; B 1 B.val = 1;
2）三个语句序列 x = a[i] y = b[i] z = x*y
LD R1 , i MUL R1 , R1 , 4 ADD R1 , R1 , SP LD R2 , a(R1) ST x(SP) , R2 LD R3 , i MUL R3 , R3 , 4 ADD R3 , R3 , SP LD R4 , b(R3) ST y(SP) , R4 LD R5 , x(SP) LD R6 , y(SP) MUL R5 , R5 , R6 ST z(SP) ,R5

编译原理作业解析——第五章语法制导翻译技术[xiwang]

编译原理作业解析——第五章语法制导翻译技术[xiwang]
100 (+, y, 1, T1) 101 (j=, x, T1, 103) 102 (j, , , 106) 103 (*, x, y, T2) 104 (:=,T2, , x) 105 (j, , , 113) 107 (j, , , 113) 108 (-, x, 1, T3) 109 (:=,T3, , x) 110 (+, y, 2, T4) 111 (:=,T4, , y) 112 (j, , , 113) 113
解答:
P195
四元式序列如下所示： (1) (jnz, a, , 3) a的四元式，当a为真时，则转向第3个四元式 (2) (j, , , 0) (3) (jnz, b, , 5) b的四元式，当b为真时，则转向第3个四元式 (4) ( j, , , 2) 无条件转向第2个四元式 (5) (j>, c, d, 0) c>d的四元式 (6) (j, , , 4) 无条件转向第4个四元式 <BE>•TC表示<BE>真出口的链首 <BE>•FC表示<BE>假出口的链首 每个链尾的四元式第4分量均为0，表示结束标记
预祝
大
家 考
出
好
成
绩
！
, 0/ቤተ መጻሕፍቲ ባይዱ02) , 0)
, 0/104) , 0/101)
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10
语法制导翻译过程
(4)
四元式
E∧E∧’c>d {BP(E(1)•TC=102, NXQ=104); E∧’•FC:= E(1)•FC=103} (5) E∧E∧’E 104 (j>, c, d, 0) {E•TC:=104; E•FC:=105} 105 (j, , , 0/103) (6) E∧E(1) { E(1)•TC:= E•TC =104; E(1)•FC:= MERG(E∧’•FC=103, E•FC=105)=105} (7) E(2) { E(2) •TC= E(1)•TC =104; E(2) •FC:= MERG(E∧•FC=101, E•FC=105)=105}

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

编译原理第5章语法制导翻译及中间代码生成

编译原理第5章语法制导翻译及中间代码生成

03
生成过程
在编译器中，源代码首先被解析成抽象语法树（Abstract Syntax Tree,
ቤተ መጻሕፍቲ ባይዱ
AST），然后通过遍历AST生成三地址代码。在生成过程中，需要考虑
变量的生命周期、作用域和数据类型等因素。
循环优化
定义
循环优化是指在生成中间代码的 过程中，对循环结构进行优化以 提高程序执行效率的过程。
中间代码优化
对中间代码进行优化，以提高生成的 目标代码的效率。
三地址代码
01
定义
三地址代码是一种中间代码形式，它由一系列运算符和操作数组成，用
于表示程序中的控制流程和数据流。
02
特点
三地址代码具有高度规范化、结构清晰的特点，易于理解和生成。它通
常采用三地址表达式的形式，包括变量、常量、运算符和括号等元素。
解析过程
从文法的终结符号出发，逐步构建语法树或 抽象语法树，直到最终生成目标代码。
优点
能够充分利用语义信息，减少冗余操作，提高解析 效率。
缺点
实现较为复杂，需要构建语法树或抽象语法 树，且对于某些复杂的文法结构，可能存在 无法生成目标代码的情况。
递归下降分析法
解析过程
将文法规则分解为一系列子句，每个子句对应一个递归函数。根据输入的源代 码字符串，从根节点开始递归调用这些函数，直到识别出一个完整的语句或表 达式。
常见优化技术
常见的循环优化技术包括循环展开、 循环合并、循环嵌套、循环不变计算 外提等技术。这些技术可以减少循环 次数、提高循环体内部的计算速度， 从而提升程序的执行效率。
实现方式
循环优化通常在生成三地址代码 后进行，通过对三地址代码进行 分析和变换实现。优化过程中需 要考虑程序的控制流和数据流， 以保持程序的正确性。

编译原理 语法制导翻译

编译原理 语法制导翻译
搜索方法：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

第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 属性文法与属性翻译文法
语法制导翻译方法的实质，就是根据文法中每个产 生式所蕴含的语义，为其配备一个（或多个）处理 语句或子程序，对所要完成的功能进行描述。 产生式的语义是由组成该产生式的文法符号的语义 所决定的。 将这些语义以“属性”的形式附加到各个文法符号 上，再根据产生式所蕴含的语义，给出每个文法符 号的属性的求值规则，从而形成一种附带有语义属 性的前后文无关文法，即属性文法。 语义属性主要有两类：综合属性和继承属性

第五章语法制导的翻译

第五章语法制导的翻译
– 规则和产生式相关联
• 对于文法符号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是上下文无关文法和属性/规则的结合；

ch05 语法制导翻译技术

ch05 语法制导翻译技术

digit .lexval=4
digit .lexval=3
属性值的计算可以在语法分析过程中进行。
15
继承属性
分析树中，一个结点的继承属性值由该结点的父结 点和/或它的兄弟结点的属性值决定。 可用继承属性表示程序设计语言结构中上下文之间 的依赖关系
– 可以跟踪一个标识符的类型 – 可以跟踪一个标识符，了解它是出现在赋值号的右边还是 左边，以确定是需要该标识符的值还是地址。
18
Wensheng Li BUPT
addtype(id3.entry,L.in)
addtype(id2.entry,L.in)
id3
addtype(id1.entry,L.in)
id2
二、依赖图
分析树中，结点的继承属性和综合属性之间的相互 依赖关系可以由依赖图表示。 为每个包含过程调用的语义规则引入一个虚拟综合 属性b，以便把语义规则统一为b=ƒ(c1,c2,…,ck) 的形式。 依赖图中：
语义规则
一般情况：
– 语义规则函数可写成表达式的形式。
某些情况下：
– 一个语义规则的唯一目的就是产生某个副作用，如打印一 个值、向符号表中插入一条记录等； – 这样的语义规则通常写成过程调用或程序段。 – 看成是相应产生式左部非终结符号的虚拟综合属性。 – 虚属性和符号‘=’都没有表示出来。
Wensheng Li BUPT
– 为每个属性设置一个结点 – 如果属性b依赖于c，那么从属性c的结点有一条有向边连 到属性b的结点。
Wensheng Li BUPT
19
算法5.1
构造依赖图
输入：一棵分析树 输出：一张依赖图 方法：
for (分析树中每一个结点n) for (结点n处的文法符号的每一个属性a) 为a在依赖图中建立一个结点; for (分析树中每一个结点n) for (结点n处所用产生式对应的每一个 语义规则 b=ƒ(c1,c2,…,ck)) for (i=1;i<=k;i++) 从ci结点到b结点构造一条有向边;

编译原理chapter5 语法制导翻译

编译原理chapter5 语法制导翻译
S-属性定义 唯独只使用综合属性的语法制导定义。 结点属性值的计算正好和自底向上分析建立 分析树结点同步进行。 例 5 .2
输入：3*5+4n
9
L
Eval:=19
n
Eval:=15 +
Tval:=4
Tval:=Biblioteka 5Fval:=4Tval:=3 * Fval:=5 digitlexval:=4
Fval:=3
继承属性值是由此结点的父结点和／或 兄弟结点的某些属性值来决定的。
例5 . 3 变量说明的类性定义
int a,b,c 11
表5.2 带有继承属性L.in的语法制导定义
产生式
语义规则
DTL
Lin:=T type
T int
T type :=integer
T real
T type :=real
L L1,id
1．b是A的一个综合属性并且c1，c2，…，ck 是中的符号的属性，或者
2．b是中的符号的一个继承属性并且c1，
c2，…，ck是A或中的任何文法符号的属性。
在两种情况下，都说属性b依赖于属性c1，
c2，…，ck。
7
例5.1 台式计算器程序的语法制导定义（表5.1)
产生式
语义规则
LEn E E1+T E T T T1*F T F F (E) F digit
L1 in :=L in addtype(id entry,L in)
L id
addtype(id entry,L in)
12
D
T4 type
in 5 L
real ,
in 7 L 8
6 id3 3 entry
in 9 L 10 ,

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

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

X.x Y.y Z.z top
编译原理
4
L→En E → E1 + T E→T T → T1 * F T→F F→ (E) → F → digit
{ 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; }
编译原理 31
表达式9 5+2的计算 表达式9-5+2的计算
E val T.val=9 num.val=9 i=9Rs
-
T.val=5
i=4Rs i=6Rs
num.val=5 + T.val=2 num.val=2
编译原理
ε
32
例5.15 转换后的构造语法树的翻译模式
E→T R R→+ T R1 R→T R1 R→ε T→( E ) T → id T → num
A → A1Y A→X { A.a := g (A1.a, Y.y) } { A.a := f (X.x) }
消除左递归后： A→X { R.i := f (X.x) } R { A.a := R.s } R→Y { R1.i := g (R.i, Y.y) } R1 { R.s := R1.s } R→ε { R.s := R.i }
编译原理
8
例5.16 翻译为前缀表达式
L→En E → {print(‘+’)} E1+ T E→T T → {print(‘*’)} T1* F T→F F → (E) F → digit {print(digit.lexval)}
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

, 0/102) , 0)
, 0/104) , 0/101)
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10
语法制导翻译过程
(4)
四元式
E∧E∧’c>d {BP(E(1)•TC=102, NXQ=104); E∧’•FC:= E(1)•FC=103} (5) E∧E∧’E 104 (j>, c, d, 0) {E•TC:=104; E•FC:=105} 105 (j, , , 0/103) (6) E∧E(1) { E(1)•TC:= E•TC =104; E(1)•FC:= MERG(E∧’•FC=103, E•FC=105)=105} (7) E(2) { E(2) •TC= E(1)•TC =104; E(2) •FC:= MERG(E∧•FC=101, E•FC=105)=105}
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10 4. 将下列中缀式改写为后缀式表示： (2) ((a*d+c)*d+e)*f+g : 解答: ad*c+d*e+f*g+ (4) x-5∨x 5 : 解答: x5- x5 ∨

第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10 5. 将下列后缀式改写为中缀式表示： (1) abc-*cd+e/- : 解答: a*(b-c)-(c+d)/e (3) abc+a0>∧ab+0<>a0<∧∨ : 解答: (a b+c∧a>0) ∨(a+b<>0∧a<0)
S3 r4 , E∷=i S4 SUB4
4
0264
02643 02647 026 0269 01
--a--a---a-b -- a+b - - a+b – - a+b
#(E+
b)#
S3
5
#(E+b
)#
r4 , E∷=i
SUB4
6
#(E+E
)#
r1 , E∷=E+E
SUB1
7
8 9
#(E
#(E) #E
预祝
大
家 考
出ቤተ መጻሕፍቲ ባይዱ
好
成
绩
！
)#
# #
S9
r1 , E∷=(E) acc SUB3
10. 将下列布尔表达式翻译成四元式序列，并给出语法制导翻译 过程（作为条件控制）： 第十三次作业（6月8日布置） a∧b∧c>d
解答:
P195
四元式序列如下所示： (1) (jnz, a, , 3) a的四元式，当a为真时，则转向第3个四元式 (2) (j, , , 0) (3) (jnz, b, , 5) b的四元式，当b为真时，则转向第3个四元式 (4) ( j, , , 2) 无条件转向第2个四元式 (5) (j>, c, d, 0) c>d的四元式 (6) (j, , , 4) 无条件转向第4个四元式 <BE>•TC表示<BE>真出口的链首 <BE>•FC表示<BE>假出口的链首 每个链尾的四元式第4分量均为0，表示结束标记
编译原理作业解析—— 第五章语法制导翻译技术
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10 2. 给出下面表达式的后缀式表示： (3) a+b*(c+d/e) : 解答: abcde/+*+ (4) (a∧b)∨(┐c∨d) : 解答: ab∧c┐d∨∨ (5) –a+b*(-c+d) : 解答: a-bc-d+*+ (6) (a∨b) ∧(c∨┐d∧e) : 解答: ab∨cd ┐e∧∨∧
第十四次作业 P195 12、13、14(2)
P195 14. 将下列while语句翻译成四元式序列： (2) while a<c∧b<d do if a=1 then c :=c+1 else while a<=d do a :=a+2 107(:=,T1,-,C) 108(J,-,-.100) 四元式序列： 109(J=,A,D,111) 100(J<,A,C,102); 110(J,-,-,100) 101(J,-,-,0) 111(+,A,’2’,T2) 102(J<,B,D,104) 112(:=,T2,-,A) 103(J,-,-,101) 113(J,-,-,109) 104(J=,A,’1’.106) 114(J,-,-,100) 105(J,-,-,109) 115 106(+,C,’1’,T1) S· CHAIN=103
100 (+, y, 1, T1) 101 (j=, x, T1, 103) 102 (j, , , 106) 103 (*, x, y, T2) 104 (:=,T2, , x) 105 (j, , , 113) 107 (j, , , 113) 108 (-, x, 1, T3) 109 (:=,T3, , x) 110 (+, y, 2, T4) 111 (:=,T4, , y) 112 (j, , , 113) 113
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10
按下列格式写出分析符号串5*6过程
6.
解 答:
调用子程序 步骤 状态栈 语义值栈 — 符号栈 输入串 （a+b）# 归约规则及动作
0
0
#
S2
1 2 3
02 023 026
—— ——— ——a
#( #(a #(E
a+b)# +b)# +b)#
第十四次作业 P195 12、13、14(2)
12. 写出下列条件赋值语句的四元式序列： z := if a>c then x+y else x+y-0.5
解答: 根据语义子程序，其条件赋值语句四元式序列为：
100 (j>, a, c, 102) 101 (j, , , 105) 102 (+, x, y, T1) 103 (:=,T1, , z) 104 (j, , , 108) 105 (+, x, y, T2) 106 ( -, T2, 0.5, T3) 107 (:=,T3, -, z) 108
第十三次作业 P194 1、2、4(2)(4) 5(3) 8 10
解答: 语法制导翻译过程 四元式 a∧b∧c>d (1) E∧b∧c>d 100 (jnz, a, {E•TC:=100; E•FC:=101} 101 ( j , , (2) E∧b∧c>d {BP(E(1)•TC=100, NXQ=102); E∧•FC:= E(1)•FC=101} (3) E∧E∧c>d 102 (jnz, b, {E•TC:=102; E•FC:=103} 103 ( j , ,
第十四次作业 P195 12、13、14(2) 13. 将下列条件语句翻译成四元式序列： if x=y+1 then x := x*y else while x<>0 do begin x :=x-1; y :=y+2 end
解：根据语义子程序，其条件赋值语句四元式 序列为： 106 (j<>, x, 0, 108)