当前位置：文档之家 › 语法制导翻译和中间代码生成

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

  • 格式：ppt
  • 大小：152.00 KB
  • 文档页数：56

下载文档原格式

  / 56

合集下载

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

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

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

A ∨ B→if A then true else B A ∧B→if A then B else false ┐ A →if A then false else true
这种翻译法涉及到如何翻译if-thenelse的问题，将在下面具体讨论。
33
控制语ห้องสมุดไป่ตู้中布尔表达式的翻译
if E then S1 else S2,其中E为布尔式
第8章 语法制导翻译和中间代码生成
经过词法分析、语法分析后，源程序 在静态结构上的正确性得到了保证，编译 程序接着要对源程序进行静态语义检查和 翻译。 语义检查：类型检查、控制流检查、 一致性检查等。 翻译：源程序→中间代码
1
本章主要内容
1. 属性文法 2. 语法制导翻译概念 3. 中间代码的几种形式 4. 几个语句的翻译：如赋值语句、条件语 句等。
26
翻译 a:= -b+c*d
Ｓ
t1:=uminus b t2:=c*d t3:=t1+t2
a
:=
Ｅ1
Ｅ
＋ Ｅ2 Ｅ 21 c ＊
a:=t3
－
Ｅ 11 b
Ｅ 22 d
27
类型转换
如：X := Y + I * J，X,Y为实型，I,J为整型， 则相应的四元式序列应为： – (*i , I , J , T1 ) – ( itr , T1 , _ , T2 ) – ( +r , Y , T2 , T3 ) – ( := , T3 , _ , X )
23
四元式
1. 四元式对中间结果的引用必须通过 给定的名字，而三元式是通过产生中间结 果的三元式编号。四元式之间的联系是通 过临时变量实现的。 2. 四元式出现顺序与原表达式计算顺 序一致。(同三元式)

编译原理-语法制导翻译和中间代码生成

编译原理-语法制导翻译和中间代码生成

例：类型、运算、维数、越界
–语义处理：
执行真正的翻译，生成程序的中间代码目标代码。
–例：变量的存储分配
–例：表达式的求值
–例：语句的翻译（中间代码的生成）
3
8.1 属性文法
• 语义分析的描述 –描述语法规则的同时，编写相应的语义 动作和计算顺序
• 语义的形式化描述 –操作语义学、公理语义学、指称语义学
例8-3 3*5+4 的 语法树与属性计算
T.val=3 F.val=3 digit.lexval=3
E.val=15 T.val=15
＊
Ｌ Print(19)
E.val=19 ＋
T.val=4
F.val=4
F.val=5
digit.lexval=4
dgit.lexval=5
19
T.type=real
• 继承属性 – 从其兄弟结点和父结点的属性值计算出来的 – 如：L.in
• 固有属性（单词属性）
17
属性的计算
• 语法制导翻译：作语法分析，构造语法树，然 后在树的每个结点上添加相应的语义规则
• 综合属性 – 自底向上按照语义规则来计算各结点的综合 属性值
• 继承属性 –需要探讨计算次序
18
文法
E→ -E1 E.p:= mknode('-', 0, E1.p)
E→ (E1) E.p:= E1.p E→ id E.p:= mkleaf(id, id.entry) E→ num E.p:=mkleaf(num,num.val)
37
生成后缀式的属性文法
产生式
语义规则
S→id:=E Print( || E.code || “:=”)

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

第八章语法制导翻译和中间代码生成
但文法开始符号没有继承属性。 终结符只有综合属性。
继承的和综合的属性
属性文法中，对应每一个产生式 A 都有 一套与之相关联的语义规则，每条规则的形 式为：b:=f(c1,c2,……,ck) 其中：f是一个函数，b和c1,c2,……,ck是该 产生式文法符号的属性。
(1)如果b是A的一个属性， c1,c2,……,ck是产 生式右部文法符号的属性或A的其它属性， 则称b是A的综合属性。
To relate each applied occurrence of an identifier in the source program to the corresponding declaration.
语义学
语义形式化、语义建模 文法模型—属性文法 命令式或操作式模型—操作语义学 公理式模型—公理语义学 应用式模型—指称语义学 目前在实际应用中比较流行的语义描述和语
语义规则
D TL T int T real L L1,id
L.in:=T.type T.type=integer T.type:=real L1.in:=L.in addtype(id.entry,L.in)
L id
addtype(id.entry,L.in)
继承属性
一个结点的继承
Real id1,id2,id3
属性文法
使用 N.t 的形式表示与非终结符N相连的属 性t。
T.t的值为int或bool。 与非终结符E的产生式相连的断言表明：两
个T的属性必须相同。
继承的和综合的属性
属性通常分为两类：综合属性和继承属性 综合属性用于“自下而上”传递信息， 继承属性用于“自上而下”传递信息。 非终结符既可有综合属性也可有继承属性，
语义规则 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

课件：第8章语法制导翻译和中间代码生成

课件：第8章语法制导翻译和中间代码生成
都从下标1开始
确定标识符类型的语义描述
（1）P→D；E
（2）D→D；D
（3）D→id:T {addtype (id. Entry, T. type)}
（4）T→char {T. Type:= char}
（5）T→integer {T. Type:= integer}
（6）T→↑T1
{T. Type:= pointer (T1. type)}
}
…
expr3; goto loop out: ...
公理语义
公理语义概念是随着程序正确性的证明而发展的。当
正确性证明能构造时表明程序执行它的规格说前之后都有一个逻辑 表达式对程序的变量进行约束,以此说明这个语句的含义。
一般的记号 {P} S {Q}
程序正确性的证明 什麽是它的规格说明S 明S,开发实现此规格说明的程序P 功能吗
静态语义审查
（1）类型检查。根据类型相容性要求，验证程序中执行的每个操 作是否遵守语言的类型系统的过程，编译程序必须报告不符合类 型系统的信息。
（2）控制流检查。控制流语句必须使控制转移到合法的地方。例 如，在C语言中break语句使控制跳离包括该语句的最小while、for 或switch语句。如果不存在包括它的这样的语句，则就报错。
（7）T→array [num]of T1
{T. Type: = array (num.Val, T1.type)}
类型检查的语义描述
S→id:=E { if id.Type = E.Type
Then S.Type := void
else S.Type := type_ error}
S→if E then S1
属性文法
表达式文法 E—>T+T| T or T T—>n | b

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

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

uminus: 代表一元负运算符; 注意语义过程中形式参数的书写次序与 四元式的对应关系： Emit(T,V1,op,V2 ) 或 Emit(op,V1,V2,T ) 输出四元式(op,V1,V2,T) 当然也可以使用其它书写次序
实际上，在一个表达式中可能会出现各 种不同类型的变量或常数，而不是像图5.1中 的 i 假定为都是同一类型。 也就是说，编译程序还应执行这样的语 义动作：对表达式中的运算对象应进行类型 检查，如不能接受不同类型的运算对象的混 合运算，则应指出错误；如能接受混合运算， 则应进行类型转换的语义处理。
i或id表示的单词，定义一属性 ，用做语 义变量， LookUp（i. name）表示审查是否出现 在符号表中，如在，则返回一指向该登录项的 指针，否则返回nil或null。 Emit(T,V1,op,V2 )输出四元式(op,V1,V2,T) Newtemp( )或NewT ()表示生成一个临时变量， 每调用一次，生成一个新的临时变量。 E.place表示存放E值的变量名在符号表的登录 项或一整数码（若此变量是一个临时变量）
E→E1 * E2 /*语义动作*/ ｛ E.place:=newtemp; E.type:=real ; If E1.Type= int and E2.type=int then {emit(E.place，E1.place，＊i，E2.place)； E.type:= int } else if E1.Type=real and E2.Type= real then emit(E.place，E1.place，＊r，E2.place) else if E1.type=Int then /* E2.type=real */ { t:=newtemp； emit(t, -, itr, E1.place)； emit(E.place，t，＊r ，E2.place) } else /*E1.type=real and E2.type=Int*/ { t:=newtemp；emit(t, -, itr, E2.place) emit(E.Place，E1.place，＊r，t)} } 图 5.2 类型转换的语义处理

编译原理 第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
属性分为两类:综合属性和继承属性.一般情况下, 综合属性属于”自下而上”传递信息,继承属性用于 ”自上而下”传递信息. 又根据不同的处理要求，属性可以多种方式出现， 也就是说，与文法符号相关联的可以是各种属性、 语义规则，或者某种程序设计语言的程序段等。

第八章_3语法制导翻译和中间代码生成-中间代码生成


8.5
控制语句中布尔表达式的翻译
1
控制语句 S→ if E then S E 的代码 E.true: S 1 的代码 goto out S 2 的代码 out:
else S 2 E.true E.false
E.false:
. 把条件转移的布尔表达式翻译成仅含 把条件转移的布尔表达式翻译成仅含 和无条件转 条件真转 (jrop,B,C,L) 和无条件 转 (jump,_,_,L)的四元式 E =a rop b ⇒ if a rop b goto E.true goto E.false 如 ：a<b or c<d and e<f 翻译成如下四元式： 可 翻译成如下四元式： (1) if a<b goto E.true (2) goto (3) (3) if c<d goto (5) (4) goto E.false (5) if e<f goto E.true (6) goto E.false
• 高级：最接近高级语言，保留了大部分源语言 的结构。 • 中级：介于二者之间，与源语言和机器语言都 有一定差异。 • 低级：最接近机器语言，能够反映目标机的系 统结构，因而经常依赖于目标机。
不同层次的中间代码
源语言 高级语言） （高级语言）
float a[10][20]; a[i][j+2];
中间代码 高级） （高级）
逆波兰 : 四元式 : ABCD-*+ECD–N^/+ (1) ( C D T1 D N T5 T1 ) T2) T4) T5) T6) T7)
(2) ( * B (3) ( + A (4) ( (6) ( / C E (5) ( ^ T4
T2 T3)

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

• 如：说明语句的属性文法
17
翻译模式
◆定义
翻译模式是语法制导定义的一种便于翻译的书写 形式。其中属性与文法符号相对应，语义规则或 语义动作用花括号｛ ｝括起来，可被插入到产生 式右部的任何合适的位置上。
这是一种语法分析和语义动作交错的表示法，他 表达在按深度优先遍历分析树的过程中何时执行 语义动作。
–将值 val 作为表达式 E、项 T 和因子 F 的属性
• 用语义规则描述表达式的求值
7
属性文法（语法制导定义）
•L → E
print( E.val )
• E → E1 + T E.val := E1.val + T.val
•E → T
E.val := T.val
• T → T1 * F T.val := T1.val * F.val
33
四元式（三地址代码）
一般形式 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
条件转移
34
a∶=b*c+b*d的四元式表示
a Print(A.in) a Print(A.in)
24
如果计算A1.in和A2.in的值的动作分别被嵌入在产
生式SA1A2 的右部A1和A2之前，而不是后面，
那么A.in在执行Print（A.in）时已有定义。
S {A1in:=1 }A1{A2 in:=2} A2
A a
{ print(A in) }

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

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
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
结符或非终结符相连,这些属性代表与文 法符号相关信息，如它的类型、值、代码 序列、符号表内容等等 .属性与变量一样， 可以进行计算和传递。
可编辑ppt
11
属性文法
F:关于属性的属性断言或一组属性的计算规 则(称为语义规则) 。 断言或语义规则与 一个产生式相联,只引用该产生式左端或 右端的终结符或非终结符相联的属性。
注意：三元式出现的顺序与原表达式计算顺 序一致。
可编辑ppt
19
间接三元式
用一张间接码表辅以三元式表的办法 来表示中间代码。
例：X:=(A+B)*C Y:=D↑(A+B)
三元式表
间接码表
(1) ( + , A , B )
(1)
(2) ( * , (1) , C )
(2)
(3) (:= , X , (2) )
可编辑ppt
7
如何实现这种翻译
至此不难明白，语法制导翻译的关键 是为每个产生式写相应的语义子程序。
例子中的print产生式序号这种语义子 程序是为了输出数字串而写的语义子程序。 所以一个语义子程序描述了一个产生式对 应的翻译工作。
这些工作有：改变编译程序某些变量 的值、查填各种符号表、发现并报告源程 序错误、产生中间代码。
可编辑ppt
4
翻译要解决的问题
1. 翻译成什么样的代码？ 2. 什么时候实现这种变换(翻译)？ 3. 如何实现这种翻译？
可编辑ppt
5
翻译成什么样的代码
按照相应语义规则产生一种介于源语 言与目标代码之间的一种代码(中间代码)， 它不依赖于机器但又便于产生依赖于机器 的目标代码。
中间代码可用多种方式表示，常见的 有：逆波兰表示法、树形表示法、三元式、 四元式等。
可编辑ppt
16
上述三种方法的比较
三种方法的共同点： 1. 运算量个数不变，顺序也不变。 2. 运算符个数不变。
逆波兰式的优点： 1. 是一个无括号表达式。 2. 逆波兰式的运算符出现的顺序就是原 表达式的运算顺序，因而计算方便。
可编辑ppt
17
举例
1. ( a * b + c ) * d + b * ( a + d * c ) ab*c+d*badc*+*+
句等。
可编辑ppt
2
语法制导翻译的引例
E→E+T E→T T→T*F T→F F→(E) F→i
{print ”1”} {print ”2”} {print ”3”} {print ”4”} {print ”5”} {print ”6”}
在文法的每个 产生式后配了 一个有{ }括起 来的语义子程 序。
可编辑ppt
6
什么时候实现这种变换(翻译)
直观来说，就是为每个产生式配上一个翻 译子程序(语义子程序)，并且在语法分析的 同时执行这些子程序。
具体来说，就是一边分析，一边翻译，语 法分析完成，翻译也就完成了。
语法制导翻译法对自上而下分析或自下而 上分析都适用。
语法制导翻译方法是比较接近于形式化的 翻译方法。
可编辑ppt
8
语义子程序的一般形式
语义子程序写在该产生式后面的花括号 内： • (1) X… { 语义子程序1 } • (2) Y… { 语义子程序2 } • (3) AXY { 语义子程序3 }
可编辑ppt
9
属性文法与语法制导翻译的关系
对于某个压缩了的文法，当把每个文法符 号和一组属性相关联，并把产生式附加以 语义规则的时候，就得到属性文法。
可编辑ppt
12
属性文法的例子
简单算术表达式求值的语义描述
产生式
语义规则
LE
Print(E.val)
E E1+T
Hale Waihona Puke E.val:=E1.val+T.val
ET
E.val:=T.val
T T1 * F TF
T.val:=T1.val F.val T.val:=F.val
F (E)
F.val:=E.val
F digit
F.val:可=编d辑igpiptt .lexval
13
设表达式为3＊5+4，则语义动 作打印数值19
.
L
T.val=3 F.val=3
E.val=15 T.val=15
*
E.val=19
+ F.val=5
T.val=4 F.val=4 digit.lexval=4
digit.lexval=5
digit.lexval=3
3*5+4的带注释的分析树
可编辑ppt
14
中间代码的形式
1. 逆波兰式 2. 三元式、间接三元式和树形表示 3. 四元式
可编辑ppt
15
表达式的表示方法
1. 中缀表达式(一般表达式)：运算符放在运 算量之间。A+B A*B 2. 前缀表达式(波兰表达式)：运算符放在运 算量前面。+AB *AB 3. 后缀表达式(逆波兰表达式)：运算符放在 运算量后面。AB+ AB*
第8章 语法制导翻译和中间代码生成
经过词法分析、语法分析后，源程序 在静态结构上的正确性得到了保证，编译 程序接着要对源程序进行静态语义检查和 翻译。
语义检查：类型检查、控制流检查、 一致性检查等。
翻译：源程序→中间代码
可编辑ppt
1
本章主要内容
1. 属性文法 2. 语法制导翻译概念 3. 中间代码的几种形式 4. 几个语句的翻译：如赋值语句、条件语
2. 赋值语句的后缀式 A：=B+C ABC+：=
可编辑ppt
18
三元式
组成: 算符OP，第一运算量ARG1，第二运算量ARG2 如：a:=b*c+b*d的三元式为：
(1) ( * , b , c )
(2) ( * , b , d )
(3) ( + , (1) , (2) )
(4) ( := , a , (3) )
语法制导的翻译过程：由于属性文法的规 则和产生式是一一对应的关系。所以，由 属性文法确定的语义分析可以在语法分析 的过程中进行。这个过程成为语法制导的 翻译。
可编辑ppt
10
属性文法
属性文法是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法。 V:属性的有穷集,每个属性与文法的一个终
可编辑ppt
3
对(i+i)*i的翻译
不难证明该符号串是文法的合法句子。 按照这个句子向文法开始符号E的归约次 序，且每当归约时调用该句柄的产生式所 对应的语义子程序，便可得到相应的数字 串：64264154632。
这个例子表明：输入源程序为(i+i)*i， 输出为数字串。这是一种变换，而变换的 规则是每当归约时调用相应的语义子程序。 无疑这个例子是翻译的一个十分简单的模 型。