当前位置：文档之家 › 《编译原理》第6章

《编译原理》第6章

  • 格式：ppt
  • 大小：1.59 MB
  • 文档页数：52

下载文档原格式

  / 52

合集下载

编译原理第6章习题答案

编译原理第6章习题答案
1）抽象语法树 2）四元式序列 3）三元式序列 4）间接三元式序列
1）抽象语法树：
2）四元式序列：
3）三元式序列：
4）间接三元式序列：
6.4.1 向图6-19的翻译方案中加入对应于下列产生式的规则： 1） E E1 * E2 2） E E1 (单目加)
E.addr = E1.addr E.code = E1.code
例如：+3
6.4.2 使用图6-20中的增量式翻译方案重复练习6.4.1
{E.addr = E1.addr}
在增量方式中，gen不仅要构造出一个新的三地址指令，还 要将它添加到至今为止已生成的指令序列之后。
6.4.3 使用使用图6-22所示的翻译方案来翻译下 列赋值语句： 2） x = a[i][j] + b[i][j] 假设w1为数组a的第一维的宽度，w2为数组b 的第一维的宽度，整数宽度为w。第6章习题答案
作业： 6.1.1 6.2.1 6.4.1 6.4.2 6.4.3 6.6.1
6.7.1 (1) 补充习题1
第6章 中间代码生成
6.1.1 为下面的表达式构造DAG ((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))
6.2.1 将算术表达式 a+-(b+c) 翻译成
补充习题1：用本节所给的翻译模式(采用回填）翻译语句： if (a<b || c<d && e<f ) A1 else A2; while (a<b) A3 ; 假定语句序号从100起算，又假定A1、A2、A3语句各生成10条指令。
100 if a<b goto 106 101 goto 102 102 if c<d goto 104 103 goto 117 104 if e<f goto 106 105 goto 117 106 107 . A1 . 115 116 goto 127 117 118 A2 . . 126 127 if a<b goto 129 128 goto 140 129 130 A3 . . 138 139 goto 127 140 141 142 143 144 145

编译原理课件(刘铭)第6章

编译原理课件(刘铭)第6章

本章小结
也就是说标识符是一个没有意义 的字符序列，而名字有确切的意义。 在程序语言中标识符可以是一个变量 的名字或一个函数的名字。
例如 area , 作为标识符，它没有 任何意思，但作为名字，可以表示 变量名或函数名等。
本章小结
3. 符号表的查找
符号表查找算法与该符号表的构造方法 密切相关即有顺序查找、折半查找和杂 凑查找算法。
6.3 符号表的组织
一个编译程序，从词法分析、语法 分析、语义分析到代码生成的整个过程 中，符号表是连贯上下文进行语义检查、 语义处理、生成代码和存储分配的主要 依据，因此符号表的组织直接关系到这 些语义功能的实现和语义处理的时空效 率。
6.3 符号表的组织
符号表的表格形式
名 字 栏 信 息 栏
符号表的作用
符号表的组织
符号表的建立和查找
6.1 符号表的作用与生成期
符号表的作用 符号表用来存放程序语言中出现 的有关标识符的属性和特征。 符号表在整个编译期间的作用归 纳为以下几个方面： 将标识符的名字及属性登录在符号 表中
6.1 符号表的作用与生成期
在分析说明语句时，编译程序根 据说明语句信息将标识符的相应属性 如标识符的类型：实型，整型，布尔 型等；标识符的种属：数组名，变量 名，过程名，函数名等; 标识符的作用 域：全局变量或局部变量等信息登录 到符号表中。
名字栏存放标识符的名字，信息栏存放 名字相关属性。
. . .
. . .
6.3 符号表的组织
符号表的总体组织 1. 编译程序按名字的不同属性构造出多 个符号表。如常量表、变量名表等。 符号表结构相同，表项等长。不便管理。
2. 编译程序把语言中的所有名字组织在 一张符号表中。 符号表便于管理，但表结构复杂且表项 不等长。

916076-编译原理原理与技术-第6章 中间代码生成

916076-编译原理原理与技术-第6章 中间代码生成

6.2 声 明 语 句
P M D; S {addWidth (top (tblStack), top (offsetStack) ); pop(tblStack); pop (offsetStack); }
M {t = mkTable (nil); push(t, tblStack); push (0, offsetStack); }
6.1 中 间 语 言
6.1.4 静态单赋值形式（SSA） • 一种便于某些代码优化的中间表示 • 和三地址代码的主要区别
– 所有赋值指令都是对不同名字的变量进行赋值 – 一个变量在不同路径上都被定值的解决办法
if (flag) x = 1; else x = 1; y = x a; 的条件语句改成
6.1 中 间 语 言
6.1.3 三地址代码 一般形式：x = y op z
• 例 表达式x + y z翻译成的三地址语句序列是 t1 = y z t2 = x + t1
6.1 中 间 语 言
• 三地址代码是语法树或DAG的一种线性表示 • 例 a = (b + cd ) + cd
语法树的代码
6.2 声 明 语 句
符号表实例
图5.14的 Pascal程序
sort 空 表头
a x readArray exchange
quickSort
指向readArray 指向exchange
readArray 表头 i
exchange 表头
quickSort 表头
k v
partition
partition
t1 = b t2 = c d t3 = t1 + t2 t4 = t3 + t2 a = t4

编译原理第6章习题与答案

编译原理第6章习题与答案

第6章习题6-1 将下列中缀式改写为逆波兰式。

(1) -A*(B+C)/(D-E)(2) ((a*d+c)/d+e)*f+g(3) a+x≤4∨(c>d*3)(4) a∨b∧c<d*e/f6-2 将下列逆波兰式改写为中缀式。

(1) abc*+(2) abc-*cd+e/-(3) abc+≤a0>∧ab+0≠a0<∧∨6-3 将下列语句翻译成四元式序列。

(1) X:=A*(B+C)+D(2) if A∧(B∨(C∨D)) then S1 else S2(3) while A<C∧B>0 doif A=1 then C:=C+1 else A:=A+26-4 设有二维PASCAL数组A[1··10,1··20]和三维PASCAL数组B[1··10, 1··20,1··30]，给出赋值语句A[I,J]:=B[J,I+J,I+1]+X的四元式序列。

第5章习题答案6-1 解：(1) A-BC+*DE-/(2) ad*c+d/e+f*g+(3) ax+4≤cd3*>∨(4) abcde*f/<∧∨6-2 解：(1) a+b*c(2) a*(b-c)-(c+d)/e(3) a≤b+c∧a>0∨a+b≠0∧a<06-3 解：(1) (1) (+,B,C,T1)(2) (*,A,T1 ,T2)(3) (+,T2 ,D,T3)(4) (=,T3 ,0,X)(2) 如下所示：(1) (jnz,A,0,3);(2) (j,0,0,p+1);(3) (jnz,B,0,9);(4) (j,0,0,5);(5) (jnz,C,0,9);(6) (j,0,0,7);(7) (jnz,D,0,9);(8) (j,0,0,p+1);(9) 与S1相应的四元式序列(p) (j,0,0,q)(p+1) 与S2相应的四元式序列(q) …(3) 假设所产生的四元式序列编号从1开始(1) (j<A,C,3)(2) (j,0,0,13)(3) (j>,B,0,5)(4) (j,0,0,13)(5) (j=,A,1,7)(6) (j,0,0,10)(7) (+,C,1,T1)(8) (=,T1 , ,C)(9) (j,0,0,1)(10) (+,A,2,T2)(11) (=,T2 , ,A)(12) (j,0,0,1)(13) …6-4 解：(1) (*,I,20,T1)(2) (+,J,T1,T1)(3) (-,a A,C A ,T2)(4) (+,I,J,T3)(5) (*,J,20,T4)(6) (+,T3 ,T4 ,T4)(7) (+,I,1,T5)(8) (*,T4,30,T6)(9) (+,T5 ,T6 ,T6)(10) (-,a B,C B ,T7)(11) (=[],T7[T6],0,T8)(12) (+,T8 ,X,T9)(13) ([]=,T9 ,0,T2[T1])（注：(1)～(3)是计算下标变量A[I,J]XXX的四元式，T2中存放的是CONSTPART部分，而T1中存放的是VARPART部分，a A表示数组A的首XXX；(4)～(10) 是计算下标变量B[J,I+J,I+1]XXX的四元式，T7中存放的是CONSTPART 部分，而T6中存放的是VARPART部分，a B表示数组B的首XXX。

编译原理课程设计之第六章 语义分析

编译原理课程设计之第六章 语义分析

mcy
2
语义分析的任务：
计算各类语法成分的语义信息(属性信息)，一般将收集
的语义信息存放到相应的信息表中，在编译程序中符号 表是用来存放源程序中标示符相关属性(语义)信息的一 种信息表。 静态语义检查
类型检查：指类型相容问题的检查，如果操作符作用于不相容的操作数， 则编译器应该报错。 上下文有关问题的检查：当某个对象出现时，要求它必须在前面的某个 适当位置已经出现过。 唯一性检查：有时，要求某个对象只能被定义一次。 控制流检查：引起控制流从某个结构中跳转出来的语句，必须能够决定 控制流转向的目标地址。
（1）所采用的语法分析方法
（2）属性的计算次序。 语法分析方法都要求从左向右处理输入程 序，等价于要求属性能通过从左向右遍历 分析树进行赋值。
mcy
44
定义属性a1,...,ak 的一个属性文法是L-属性(Lattributed)文法，如果满足
mcy
37
num→digit
num.val=digit.val digit.base=num.base digit.val=0 digit.val=1 digit.val=7
digit→0 digit→1 ...... digit→7
mcy
38
digit→8
digit→9
if digit.base=8 then digit.val=error else digit.val= 8 if digit.base=8 then digit.val= error else digit.val 9
mcy
29
文法规则
语义规则 var-list.dtype = type.dtype type.dtype = integer type.dtype = real

北大编译原理chapter6

北大编译原理chapter6
29
(12）CHARACTER FUNCTION PRDUCE（）
（13) CHARACTER * 80 BUFFER
（14） INTEGER NEXT
（15） SAVE BUFFER，NEXT
(16) DATA NEXT／81／
（17） IF(NEXT.GT.80）THEN
（18) READ（*，'（A)')BUFFER
15
environment
state
名字
存储单元
值
l-value
r-value
存储分配
程序运行
图6.5 从名字到值的两个阶段映射
16
静态概念 过程定义 名字说明 说明的作用域
动态对应 过程活动 名字的绑定 活动的生存期
17
6.1.6 提出的问题
编译程序组织存储分配所采用策略和方法主
要取决于对源程序中下面的问题的回答。
可能有几处说明，语言的作用域规则规定：
在语句序列中引用的一个名字是在何处说
明的名字。
3 . 编译时，处理说明把名字及其属性信息填
写进符号表(add(id.entry,id.vul)); 处理引用
名字时，查找这个名字的属性信息
（lookup(id)),符号表管理程序根据语 言的
作用域规则，使 lookup(id)返回id的作用域
3. 栈:Pascal,c 4. 堆: Pascal,c
21
6.2.2 活动记录 把过程的一个活动所需要的信息组织成一
块连续的存储单元，称为活动记录。 一个活动所需要的信息的每个数据项有相
同的生存期，因此，组织成一个活动记录是 很自然的。
对于pascal语言来说，运行过程中，当调用 一个过程时，在栈顶构筑它的活动记录；当 这个过程的活动执行完后，把它从栈顶弹出。

清华大学编译原理课件Chapter6

32
6.3 算符优先分析法
• 简单优先技术对符号表中的所有符号之间 建立优先关系。但是，有些情况下，不需 要对所有两个符号之间建立优先关系。 • 算符优先分析技术只在终结符号之间建立 优先关系。
33
算符优先分析法的基本思想
• 这种方法是效仿算术式的四则运算而建立 起来的。对于算术表达式，只需要按照运算符 之间的优先关系，就可以确定运算的顺序。不 需要考虑操作数就可以对表达式进行分析。 • 例如：E+T*F，只需要知道*的优先级高于 +，就可以知道T*F是句柄。 • 刚开始是对表达式文法进行分析，但是目 前已不限于此。在一般的文法中，终结符号的 地位相当于运算符号。 34
第6章 自底向上优先分析法
1
6.1 概 述
• 从推导的角度，从输入符号出发，试图 把它规约成识别符号。每一步都寻找特 定的某个类型的短语（一般是简单短语） 进行归约。在分析过程中，每次归约的 都是最左边的简单短语（或其它短语）。 • 从语法树的角度，以输入符号为树的叶 子结点，试图向根结点方向往上构造语 法树。
定理6.4的证明(续)
• 如果t=j-1，那么, 由句柄1，Sj-1 ◄ Sj；
由句柄2， Sj-1 = Sj 或者Sj-1 ► Sj；矛盾！
• 如果t=i+1，由句柄1，Si ► Si+1；
由句柄2，Si ◄ Si+1 或者 Si = Si+1。
• 如果i<= t <= j；那么
– Sj在句柄中：
– Si在句柄内部，但是Si+1在句柄之后，必然 有规则U→…Si，且存在规范句型…USi+1…。 – 如果Si+1在句柄内，而Si在句柄外，那么必 然存在规范句型…SiU…，且 有U→Si+1…。

编译原理 第6章-LR分析-小结资料

LR(0)项目集规范族; 对LR(1)或 LALR(1)分析表，构造 LR(1)项目集规范族。
Compiler Construction Principles
(2)构造识别文法规范句型活前缀的DFA。 (3)将DFA转换成相应的LR分析表。
四种分析表的构造基本相同，仅对含 归约项目的项目集构造分析表元素不同。
构造该文法的LR(0)项目集族和转换函 数如下图所示。
I0:
S′→·S S →·(S)
S
S →·
(
S
I2:SS S
→(·S) →·(S) →·
(
I1: S'→S.
I3: S →(S·) )
I4: S →(S)·
0. S' →S 1. S →(S) 2. S →ε
见表
该文法不是LR(0)文法。因为I0，I2中 含有移进—归约的冲突。
)
I6: S→S(S·), )/(
2. S → ε S →· , )/(
S →S·(S), )/(
Compiler Construction Principles
所有的LR(1)项目集中没有移进—归约 的冲突,所以该文法为LR(1)文法 或该文法为SLR(1)文法, 任何SLR(1)文 法都是LR(1)或LALR(1)文法
3 S2 S4
4 r1 r1 r1
FOLLOW(S) ={ #, (, ) }
Compiler Construction Principles
步骤 栈中状态
10
2 01
3 012
4 0123
5 01232
6
012323
7 0123234
8 0123
9 01234

编译原理第6章 运行时存储空间组织和符号表


运行时存储空间组织和符号表
3
当前活动记录一般包含如下内容： 连接数据： ①返回地址 ②动态链：指向调用该过程前的运行活动记录地 址的指针。运行时，使运行栈上各数据区按动态 建立的次序连成链。链头为栈顶起始位置。 ③静态链：指向静态直接外层最新活动记录地址 的指针，用来访问非局部数据。 形式单元：存放相应实在参数的地址或值。 局部数据区：局部数据、内情向量、临时单元。 ( P164 图6.7 )
2013-6-28
运行时存储空间组织和符号表
35
1
14
例：n=13 32
2013-6-28
运行时存储空间组织和符号表
36
三、 名字的作用范围 1、Fortran的符号表组织
2013-6-28
运行时存储空间组织和符号表
37
2、Pascal符号表组织
最近嵌套作用域原则：一个名字的作用 域是那个包含了这个名字的说明的最小 函数。 设计符号表： ①采用栈符号表：新的名字从栈顶填入， 每当进入一个过程时建立一张子符号表， 退出时释放。 ②引入过程的嵌套层次表（DISPLAY）
2013-6-28
运行时存储空间组织和符号表
14
§2 静态存储分配
FORTRAN77采用的是静态存储分配，它 的程序是段结构，整个程序由主程序段和若 干个子程序段组成，它的每个数据名所需的 存储空间大小都是常量，并且不允许递归调 用，这样，整个程序所需存储空间的总量在 编译时就能完全确定，所以，可以采用静态 存储分配方式。
2013-6-28
运行时存储空间组织和符号表
42
2013-6-28
运行时存储空间组织和符号表
43
2013-6-28
运行时存储空间组织和符号表

《编译原理》(陈火旺版)课后作业参考答案ch6-10

第6章 属性文法和语法制导翻译7. 下列文法由开始符号S 产生一个二进制数，令综合属性v al 给出该数的值：试设计求S.val 的属性文法，其中，已知B 的综合属性c, 给出由B 产生的二进位的结果值。

例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。

【答案】11. 设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。

【答案】第7章 语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）：3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4. 按7.3节所说的办法，写出下面赋值句A:=B*(－C+D ) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

【答案】5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码： A[i, j]:=B [i, j] + C[A [k, l]] + d [ i+j] 【答案】6. 按7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。

【答案】用作数值计算时产生的四元式： 用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While A<C and B<D do if A=1 then C:=C+1else while A ≦D do A:=A+2; 【答案】第9章 运行时存储空间组织4. 下面是一个Pascal 程序：当第二次( 递归地) 进入F 后，DISPLAY 的内容是什么？当时整个运行栈的内容是什么？ 【答案】第1次进入F 后，运行栈的内容： 第2次进入F 后，运行栈的内容：第2次进入F 后，Display 内容为：5. 对如下的Pascal 程序，画出程序执行到(1)和(2)点时的运行栈。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。