首页  思维导图  详情

编译原理

2020-06-02 11:34:34   22  举报





AI智能生成

为你推荐

查看更多



编译原理05-03

编译原理部分知识框架

编译原理

语法分析

软件开发

学习笔记

作者其他创作

大纲/内容

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

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

翻译与解释

可以检测出非法字符错误

扫描，线性分析

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

词法分析

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

层次结构的分析

依据：语法规则

语法分析

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

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

依据：语义规则

重要任务：类型检查

语义分析

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

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

中间代码生成

代码优化

目标代码生成

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

三、符号表的管理

四、错误诊断和处理

编译的阶段和任务

前端：主要由与源语言有关而与目标机器无关的那些部分组成

后端：由编译程序中与目标机器有关的部分组成

便于移植，便于编译程序的构造

前端和后端

是指对源程序或其中间形式从头到尾扫描一遍，并作相关的加工处理，生产新的中间形式或目标程序

减少对主存容量的要求

功能独立、单纯、相互联系简单，结构清晰

实现更充分的优化工作，获得高质量目标程序

将前端和后端分开，为移植创造条件

分遍的好处

缺点：增加不少重复性的工作

遍

最近最后匹配原则

LR分析方法对二义文法的应用

LR分析的错误处理与恢复

软件工具YACC

第四章语法分析

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

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

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

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

语法制导定义

对上下文无关文法的推广

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

综合属性

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

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

继承属性

属性集

5.1.1 语法制导定义

5.1.2 依赖图

5.1.3 计算次序

S属性

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

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

深度优先遍历

属性计算顺序

L属性

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

属性与文法符号对应

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

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

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

对于S属性定义

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

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

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

对于L属性定义

翻译方案的设计

5.1.5 翻译方案

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

内部结点表示运算符号

子节点表示运算分量

构造函数

有向非循环图dag

语法树

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

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

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

修改分析栈

综合属性有词法分析产生

对于终结符

属性值的计算与归约联系

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

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

对每个产生式A->XYZ

修改分析程序

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

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

不含左递归

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}

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

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

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

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

对非终结符号B

对每一个语义动作

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

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

5.3.2 预测翻译程序的设计

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

自底向上的处理继承属性

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

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

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

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

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

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

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

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

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

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

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

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

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

① 用Mj -> 空进行归约

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

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

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

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

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

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

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

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

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

1.设计函数头

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

2. 函数体结构

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

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

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

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

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

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

3. 设计分支代码

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

第五章语法制导翻译技术

变量的作用域问题

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

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

问题

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

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

解决方法：

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

目标程序运行时检查

动态检查

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

静态检查

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

唯一性检查

控制流检查

2. 类型检查

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

6.1.1 语义分析程序的任务

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

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

位置

重载运算符

类型强制

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

6.1.2 语义分析程序的位置

6.1.3 错误处理

6.1 语义分析概述

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

辅助正确地生成代码

作用

词法分析阶段建立

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

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

1. 多遍编译程序

语法分析程序是核心模块

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

2. 合并遍的编译程序

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

必须记录的属性

必须常驻内存

存取速度快

空间利用率低

长度有限制

存取速度慢

节省存储空间

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

长度没有限制

问题：标识符长度可变

名字

有数据类型是必须存

无类型的语言可以删除

类型检查

生成代码

空间分配

用于

类型

目标地址按顺序连续分配

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

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

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

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

存储地址

数组引用时，维数要一致

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

数组维数/参数个数

交叉引用表

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

链域/指针

6.2.2 符号表内容

检索

插入

声明语言

引用名字

显式声明的强类型语言

已经声明，则类型检查

首次出现，插入操作

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

隐式声明的语言

插入、检索

块开始，定位

块结束，重定位

对于块结构的语言

定位与重定位

符号表的逻辑结构

6.2.3 符号表操作

不含子模块

所有变量属于整个程序

插入前都要检索

按声明/出现顺序

无序线性表

线性查找

折半查找

按字母顺序排序

有序线性表

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

除法

平方取中法

折叠法

长度相关法

散列/哈希函数H

开放地址法

分离链表法

解决冲突的方法

散列/哈希表

符号表组织

1. 非块结构语言

栈式符号表

栈式散列符号表

2. 块结构语言

6.2.4 符号表组织

6.2 符号表

强类型语言

强调最大程度的限制

隐式类型，无须类型检查

强调数据类型的灵活性

不同的观点

编译程序完成的检查

静态类型检查

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

动态类型检查

不需要动态检查类型错误

健全的类型体制

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

检查

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

显式类型和静态类型检查

语法结构

基本类型

类型构造器

数据类型

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

由类型检查程序实现

类型体制

考虑因素

每个表达式有一个类型

类型有结构

暗示的概念

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

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

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

①数组

T1×T2

②笛卡尔积

域类型：域名+域

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

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

record

③记录

pointer(T)

④指针

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

D->R

⑤函数

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

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

递归定义

6.3.1 类型表达式

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

关键

要么是同样的基本类型

要么是同样的构造器

相同的结构

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

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

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

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

做法

不同，不等价

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

比较二进制序列

结构等价测试

编码方式实例

类型表达式的内部表示

1. 结构等价

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

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

2.名字等价

内部结点

叶子结点

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

6.3.2 类型等价

6.3 类型检查

6.4.1 语言说明

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

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

编译程序的任务

前

后

类型关键字的位置

单一实体

多个同类型的实体

不同种类的实体

标识符表

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

T.width:记录实体的域宽

T.type:记录实体的类型

引入

考虑最内层过程

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

maketable(previous)

数据结构及过程

2. 过程定义的处理

3. 记录声明的处理

声明语句的形式

6.4.2 符号表的建立

无错：integer/real/boolean

有错：type_error

E.type

6.4.3 表达式的类型检查

无错：void

S.type

6.4.4 语句的类型检查

信息不丢失的情况下

强制转换（隐式））

显式转换

6.4.5 类型转换

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

6.5.1 函数和运算符的重载

6.5.2 多态函数

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

第六章语义分析

进程与程序

活动与过程

过程与活动的概念

代码区

静态数据区

控制栈

堆

7.1.1 程序进行空间的划分

返回值

实参区域

访问链

机器状态链

局部数据区

早：中间

晚：两头

用于通信：前

自己用的：后

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

临时数据区

记录内容

7.1.2 活动记录与控制栈

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

7.1程序运行时的存储组织

7.2.1 静态数据存储

7.2.1 栈式数据存储

7.2.3 堆式数据存储

7.2 存储分配策略

7.3.1 程序块

静态变量

1. 非嵌套