编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)

简介: 编译原理复习五:属性文法与三地址码的生成(附题目与答案 超详细)

需要原卷和答案请点赞关注收藏后评论区留言私信~~~

一、属性文法

1.属性文法:在上下文无关文法的基础上,为每个文法符号引进一组属性,且让该文法中的重写规则附加上语义规则时,称该上下文无关文法为属性文法。(属性文法往往以语法制导定义和翻译模式两种形式出现。具体说明问度娘)

注意:

(1)属性与变量一样,可以进行计算和传递。

(2)属性加工的过程即是语义处理的过程。

(3)属性分为综合属性(用于“自下而上”传递信息)和继承属性(用于“自上而下”传递信息)。

(1. 语义规则的形式:产生式A—>α的语义规则的形式为b:=f(c1,c2,…,ck)。就是属性b依赖于属性c1,c2,…,ck。

其中:

f是一个函数;

b—A的综合属性,且c1,c2,…,ck是α中文法符号的属性;

b—α中某个文法符号的继承属性, 且c1,c2,…,ck是A或α中任何文法符号的属性.

(2.VT—VN的属性

(1) VT — 只有综合属性,由词法分析器提供.

(2) VN — 既可有综合属性也可有继承属性; 开始符号S的所有继承属性作为属性计算前的初始值.

(3.属性的计算/获得

(1)由该产生式提供的计算规则计算获得:产生式右边的继承属性,产生式左边的综合属性。

(2)由其它产生式的属性规则计算或由属性计算器的参数提供:产生式左边的继承属性,产生式右边的综合属性

2.综合属性:通常使用自底向上的方法(由子确父),S—属性文法:仅使用综合属性的属性文法.

3.继承属性:用继承属性来表示程序设计语言结构中的上下文依赖关系很方便.(由父兄却该结点继承属性)

下面我们来用题目进行具体的属性文法生成实战

题目如下

For-statement has the usual form:

for i:= initial to final do S

the meaning of for-statement can be illustrated as:

t1 = newtemp();||t2=newtemp();||

t1:=initial;

t2:=final;

if t1≤t2 then

begin

v:=t1;

S;

while v≠t2 do

begin

v:=v+1;

S;

end

end

1:Give the attribute grammar for “while E do S”

2:Given the three-address code corresponding to the for-statement:  for v:=1 to 10 do x:=x+1.

第一问需要写出while E do S的属性文法,这个循环语句想必逻辑很好理解,答案如下

S while E do S

S’.begin=newlabel;

E.true=newlabel;

E.false=S’.next;

S.next=S’.begin;

S’.code=Label S’.begin || E.code || Label E.true || S.code ||goto S’.begin

题目解析:newlabel函数用来生成一个新的标号,因为While语句执行完语句体内的代码后要跳回到开头重新判断条件,所以文法开头begin要生成一个新标号用于跳转,同理判断条件为真时要跳转到语句体内部,所以也有newlabel,然后false时直接跳出循环,所以是整个文法的next,即跳转到该代码的下一条语句中

二、三地址码

三地址代码

三地址代码中,一条指令的右侧最多只有一个运算符,也就是说,不允许出现组合的算术表达式。因此,像 x+y*z 这样的源语言表达式要被翻译成

t1 = y*z;
t2 = x + t1;
x = t2;

其中, t1 和 t2 是编译器产生的临时名字。因为三地址代码拆分了多运算符算术表达式以及控制流语句的嵌套结构,所以适用于目标代码的生成和优化。因为三地址表达式用名字来表示程序计算得到的中间结果,所以可以方便地进行重组。

三地址代码基于两个基本的概念:地址和指令。简单地说,地址就是运算分量,指令就是运算符,一个地址的表现形式可以是变量名、常量或者编译器生成的临时变量。下面是几种常见的三地址指令形式:

我们以上面题目的第二问来进行讲解,答案如下

t1=1

t2=10

if t1 ≤ t2 goto L1

goto L2

label L1

v=t1 t3=x+1  x=t3

label L4

if v ≠ t2 goto L3

goto L2

Label L3

v=v+1   t4=x+1  x=t4

goto L4

label L2

halt

下面再拿一道题目进行讲解

Give the sequence of three-address code corresponding to the following program: (No need to give the attribute grammar for translation)

Repeat:

y:=y-1;

if y>0 then y:=y-x

else y=y+x

end

Until y>x and y<100;

write y

对应答案如下

100:y=y-1

101:if y>0 goto 104

102:y=y+x

103:goto 105

104:y=y-x

105:if y<=x goto 100

106:if y>=100 goto 100

107:write y

创作不易 觉得有帮助请点赞关注收藏~~~

相关文章
|
6月前
|
自然语言处理 算法 编译器
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
编译原理复习一:正则表达式-NFA NFA-DFA DFA最小化(附题目与答案 超详细)
269 0
|
3月前
|
机器学习/深度学习 C语言
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
要保持最小的步数,每一次汉诺塔问题(无论是最初还是递归过程中的),如果此时初始柱盘子数为偶数,我们第一步是把最上面的盘子移动到中转柱,如果为奇数,我们第一步则是将其移动到目标柱。
62 0
【C语言篇】递归详细介绍(基础概念习题及汉诺塔等进阶问题)
|
5月前
|
IDE 编译器 开发工具
详细解读C语言程序设计:现代方法(第2版)第二章全部习题答案
详细解读C语言程序设计:现代方法(第2版)第二章全部习题答案
38 0
|
6月前
|
存储 安全 编译器
【C++初阶】10 .习题①
【C++初阶】10 .习题①
64 2
|
6月前
编译原理复习六:依赖图、注释语法树上节点的求值讲解(附题目与答案 超详细)
编译原理复习六:依赖图、注释语法树上节点的求值讲解(附题目与答案 超详细)
262 0
|
Java
Java基础语法之运算符一(附练习和答案)
Java基础语法之运算符一(附练习和答案)
225 0
|
存储 算法 C语言
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)
[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)
|
存储 C++
C++ Primer Plus 第十一章答案 使用类
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
67 0
【初阶C语言】有关的经典题型内含数组及递归函数题型讲解(入门适用)(一)
【初阶C语言】有关的经典题型内含数组及递归函数题型讲解(入门适用)(一)