编译原理思维导图模板_ProcessOn思维导图、流程图

第一章编译概述

翻译与解释

把源程序翻译成另一种表现形式的翻译器称为编译器（编译程序）

直接执行源程序给出运行结果的翻译器称为解释器（解释程序）

编译的阶段和任务

一、分析阶段：根据源语言的定义，分析源程序的结构

词法分析

扫描，线性分析

可以检测出非法字符错误

依据：构词规则（词法、模式）

语法分析

层次结构的分析

能发现记好流不符合语法规则的错误

依据：语法规则

语义分析

对语句的意义进行检查分析

试图检测出具有正确的语法结构，但对所涉及的操作无意义的结构

依据：语义规则

重要任务：类型检查

二、综合阶段：根据分析结果构造出所要求的目标程序

中间代码生成

可能发现目标程序区超出了允许范围的错

代码优化

目标代码生成

三、符号表的管理

四、错误诊断和处理

最近最后匹配原则

LR分析的错误处理与恢复

软件工具YACC

第五章语法制导翻译技术

语法制导定义

根据翻译目标来确定每个产生式的语义

更具产生式的含义，分析每个符号的语义

把语义以属性的形式附加到相应的文法符号中

根据产生式的语义给出符号属性的求职规则，从而形成语法制导定义

5.1 语法制导定义及翻译方案

5.1.1 语法制导定义

对上下文无关文法的推广

属性集

综合属性

从其子结点的属性值计算出来的

继承属性

从其兄弟结点或父结点的属性值计算出来的

表示上下文之间的依赖关系

5.1.2 依赖图

子主题

5.1.3 计算次序

5.1.4 S属性定义及L属性定义

S属性

L属性

属性计算顺序

深度优先遍历

进入结点前计算它的继承属性

从结点返回时，计算它的综合属性

5.1.5 翻译方案

属性与文法符号对应

语义动作在花括号中，并插入到产生式右部某个合适的位置

翻译方案的设计

对于S属性定义

为每个语义规则建立一个包含赋值的动作

把这个动作放在产生式的右边末尾

对于L属性定义

右部文法符号的继承属性必须在这个符号以前被计算出来

一个动作不能应用这个动作右边的文法符号的综合属性

左边非终结符的综合属性只有在他所引用的所有属性都计算出来之后才能计算

子主题

5.2 S属性定义的自底向上翻译

5.2.1 为表达式构造语法树的语法制导定义

语法树

内部结点表示运算符号

子节点表示运算分量

构造函数

makenode(op,left,right)

makeleaf(id,entry)

makeleaf(num,val)

有向非循环图dag

5.2.2 S属性定义的自底向上翻译

修改分析栈

目的：使之能够保存综合属性

做法：在分析栈中增加一个域，存放综合属性值

修改分析程序

对于终结符

综合属性有词法分析产生

对每个产生式A->XYZ

属性值的计算与归约联系

归约前，执行与产生式相关的代码段

归约：右部符号的相应状态及其属性出栈，左部符号的相应状态及其属性入栈

5.3 L属性定义的自顶向下翻译

预测分析方法对文法的要求

不含左递归

A->α|β FIRST(α)∩FIRST(β) = φ

5.3.1 消除翻译方案中的左递归

M -> 空 { M.s = M.i}

E-> T{ M.i = T.val}M{E.val = M.s}

M-> +T{M1.i = M.i + T.val } M1{ M.s = M1.s}

5.3.2 预测翻译程序的设计

算法5.2 构造语法制导的预测翻译程序

（1）为每个非终结符A建立一个函数

继承属性为形参，综合属性为返回值

（2）A的函数的代码由多个分支组成

（3）与每个产生式相关的程序代码

对带有综合属性x的记号X

对非终结符号B

对每一个语义动作

5.4 L属性定义的自底向上翻译

5.4.1 移走翻译方案中嵌入的语义规则

自底向上的处理继承属性

等价交换：使所有嵌入的动作都出现在产生式的右端末尾

在基础文法中引入新的产生式，形如 M->空

M：标记非终结符号，代替嵌入在产生式中的动作

把被M 代替的动作放在产生式 M->空的末尾

5.4.2 直接使用分析栈中的继承属性

5.4.3 变换继承属性的计算规则

要想从栈中取得继承属性，当且仅当文法允许属性值再栈中存放的位置可以预测

如果不确定，则引入标记非终结符，等价变换

用标记非终结符号模拟非复制规则的语义规则

算法5.3 L属性定义的自底向上分析和翻译

对每个产生式A->X1X2X3...Xn

引入n个新的标记非终结符M1，M2，...，Mn

用A->M1X1M2X1....MnXn代替原式

属性Xj.i 总是在Mj处计算，且发送在开始做归约的动作之前

在自底向上分析过程中，各个属性都可以被计算出来

① 用Mj -> 空进行归约

② 用A->M1X1M2X2...MnXn归约

5.4.4 改写语法制导定义为S属性定义

5.5 通用的语法制导翻译方法

为每一个非终结符号A 建立一个函数，该函数keyi是递归的

1.设计函数头

分析树结点和继承属性作为形参，综合属性作为返回值

为每一个属性都声明一个相应的局部变量

2. 函数体结构

如果有多个候选式，则首先根据当前节点处使用产生式来确定应执行的分支

3. 设计分支代码

根据相关语义规则来设计向相应的分支程序代码

根据属性间的依赖关系确定访问子节点的顺序

子节点可以是内部结点或叶子结点

叶子结点，对应记号X有综合属性x，则将它的值保存在属性X.x声明的变量中

内部结点，对应于非终结符号B

如果有继承属性B.i，则先根据语义规则生成计算B.i值的代码

产生一个函数调用语句c = B（n,b1,b2....），其中n为B对应的分析树结点，c对应于B 的综合属性变量

第六章语义分析

6.1 语义分析概述

问题

变量的作用域问题

同一作用域内同名变量的重复声明问题

表达式、赋值语句中的类型一致性问题

解决方法：

利用语法制导翻译技术实现语义分析

设计专门的语义动作补充上下文无关文法的分析程序

6.1.1 语义分析程序的任务

将变量的定义与引用联系起来，对源程序的含义进行检查

1. 收集并保存上下文有关的信息

2. 类型检查

动态检查

目标程序运行时检查

静态检查

读入源程序但不执行源程序的情况下进行的检查

检验结构的类型是否与其上下文所期望的一致，检查操作的合法性和数据类型的相容性

唯一性检查

控制流检查

6.1.2 语义分析程序的位置

位置

以语法树为基础，检查语法成分在语义上是否满足上下文对它的要求

输出的是带有语义信息的语法树

有助于生成正确的目的代码

重载运算符

类型强制

6.1.3 错误处理

6.2 符号表

作用

检查语义（即上下文有关）的正确性

辅助正确地生成代码

6.2.1 符号表的建立和访问时机

1. 多遍编译程序

词法分析阶段建立

在符号表中的位置作为记号的属性

适用于非块结构语言的编译

2. 合并遍的编译程序

语法分析程序是核心模块

当声明语句被识别，，标识符和它的属性一起写入符号表中

6.2.2 符号表内容

名字

必须记录的属性

必须常驻内存

问题：标识符长度可变

长度有限制

存取速度快

空间利用率低

长度没有限制

串描述符：包含位置指针和长度两个子域

存取速度慢

节省存储空间

类型

有数据类型是必须存

无类型的语言可以删除

用于

类型检查

生成代码

空间分配

存储地址

对于静态存储分配的语言（如FORTRAN）

目标地址按顺序连续分配

对于块结构的语言（如Pascal，C）

采用二元地址<blkn, offset>

blkn：块的嵌套深度，用于确定分配给声明变量的块的数据区的基址

offset：变量的目的地址偏移量，指示该变量的存储单元在数据区中相对于基址的位置

数组维数/参数个数

数组引用时，维数要一致

过程调用时，实参和形参一致

交叉引用表

链域/指针

为了便于产生按字母顺序排列的交叉引用表

6.2.3 符号表操作

插入、检索

显式声明的强类型语言

声明语言

检索

插入

引用名字

检索

隐式声明的语言

每次出现都按首次出现处理

检索

已经声明，则类型检查

首次出现，插入操作

定位与重定位

对于块结构的语言

块开始，定位

块结束，重定位

符号表的逻辑结构

6.2.4 符号表组织

1. 非块结构语言

不含子模块

所有变量属于整个程序

符号表组织

无序线性表

按声明/出现顺序

插入前都要检索

有序线性表

按字母顺序排序

线性查找

折半查找

散列/哈希表

查找时间与表中记录数无关

散列/哈希函数H

除法

平方取中法

折叠法

长度相关法

解决冲突的方法

开放地址法

分离链表法

2. 块结构语言

栈式符号表

栈式散列符号表

6.3 类型检查

不同的观点

强调最大程度的限制

强类型语言

强调数据类型的灵活性

隐式类型，无须类型检查

检查

静态类型检查

编译程序完成的检查

动态类型检查

目标程序运行时完成的检查

健全的类型体制

不需要动态检查类型错误

强类型语言

能够保证程序不会有运行时的类型错误

显式类型和静态类型检查

可尽早检出程序错误，减少可能出现的执行错误

6.3.1 类型表达式

考虑因素

语法结构

数据类型

基本类型

类型构造器

类型体制

把类型指派给语法结构的规则

由类型检查程序实现

暗示的概念

每个表达式有一个类型

类型有结构

递归定义

1. 基本类型是类型表达式

int char, 错误类型type_error,回避类型 void

2. 类型名是类型表达式，因为类型表达式可以命名

3. 类型构造器作用域类型表达式的结构仍是类型表达式

①数组

array(I,T)

元素类型为T和下标为I的数组

②笛卡尔积

T1×T2

③记录

record

记录各域类型的笛卡尔积上

域类型：域名+域

record((i×integer)×(c×char))

④指针

pointer(T)

⑤函数

D->R

定义域类型D到值域类型R的映射

4. 类型表达式中可以包含变量（类型变量），变量的值也是类型表达式

6.3.2 类型等价

关键

精确地定义什么情况下两个类型表达式等价

1. 结构等价

相同的结构

要么是同样的基本类型

要么是同样的构造器

类型表达式结构等价当且仅当完全相同

类型表达式的内部表示

为了提高测试效率，可以对类型表示式进行编码

做法

对基本类型规定确定位数、确定位置的二进制编码

对类型构造器规定确定位数的二进制编码

结构等价测试

比较二进制序列

不同，不等价

相同，用算法6.1作进一步测试

编码方式实例

2.名字等价

名字等价把每个类型名看成是一个可区别的类型

两个类型表达式名字等价，当且仅当它们完全相同

类型表达式的图形表示：类型图

内部结点

叶子结点

6.4 一个简单的类型检查程序

6.4.1 语言说明

6.4.2 符号表的建立

编译程序的任务

分离出每一个被声明的实体

尽可能多的将该实体的信息填入符号表

声明语句的形式

类型关键字的位置

前

后

标识符表

单一实体

多个同类型的实体

不同种类的实体

1. 过程中声明语句的处理

考虑最内层过程

引入

全局变量offset，记录相对地址

T.width:记录实体的域宽

T.type:记录实体的类型

2. 过程定义的处理

数据结构及过程

maketable(previous)

enter(table, name , type, offset)

addtheader(table, num, pwth, type, width)

addwidth(table, width)

enterproc( table, name, newtable)

3. 记录声明的处理

6.4.3 表达式的类型检查

E.type

无错：integer/real/boolean

有错：type_error

6.4.4 语句的类型检查

S.type

无错：void

有错：type_error

6.4.5 类型转换

强制转换（隐式））

信息不丢失的情况下

显式转换

6.5 类型检查有关的其他主题

6.5.1 函数和运算符的重载

6.5.2 多态函数

第七章运行环境

7.1程序运行时的存储组织

过程与活动的概念

进程与程序

活动与过程

7.1.1 程序进行空间的划分

代码区

静态数据区

控制栈

堆

7.1.2 活动记录与控制栈

记录内容

返回值

实参区域

控制栈

访问链

机器状态链

局部数据区

临时数据区

根据确定每个域所需空间大小的时间早晚安排其座位

早：中间

晚：两头

用于通信：前

自己用的：后

7.1.3 名字的作用域及名字绑定

7.2 存储分配策略

7.2.1 静态数据存储

7.2.1 栈式数据存储

7.2.3 堆式数据存储

7.3 非局部名字的访问

7.3.1 程序块

7.3.2 静态作用域规则下非局部名字的访问

1. 非嵌套

静态变量

2. 嵌套

过程及名字的嵌套关系