编译原理笔记1-引论

1.1 基本概念

一、发展

机器语言 —— 汇编语言 —— 高级语言 —— 工具语言

二、翻译程序

把某一种语言程序（称为源语言程序）等价地转换成另一种语言程序（称目标语言程序）的程序

三、编译程序

把某一种高级语言程序等价地转换成另一种低级语言程序（如汇编语言或机器语言）的程序

编译程序的分类：

诊断编译程序&优化编译程序
交叉编译程序&可变目标编译程序

四、解释程序

把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身

五、执行高级语言程序的步骤

高级语言程序 —— 编译 —— 低级语言目标程序 —— 目标程序 —— 执行

1.2 编译过程

一、程序的编译过程

词法分析
语法分析
中间代码产生
优化
目标代码生成

并非每个编译过程都有以上全过程

词法分析

输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号

**依据的原则：**构词规则

**描述工具：**正规式和有限自动机

语法分析

在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位

**依据的原则：**语法规则

**描述工具：**上下文无关文法

中间代码产生

对各类不同的语法范畴按语言的语义进行初步翻译

**依据的原则：**语义规则

**中间代码：**三元式、四元式、树形结构等

优化

对于当前阶段的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码

**依据的原则：**程序的等价变换规则

目标代码产生

把中间代码变换成特定机器上的目标代码

依赖于硬件系统结构和机器指令的含义

目标代码的三种形式：

**绝对指令代码：**可以直接运行
**可重新定位指令代码：**需要连接装配
**汇编指令代码：**需要进行汇编

二、编译程序的逻辑结构

三、表格与表格管理

常见的表格：符号名表、常数表、标号表、入口名表、过程引用表

四、出错管理

**出错处理程序：**发现源程序中的错误，把有关的错误信息报告给用户

语法错误、语义错误

五、遍

所谓遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序

每遍由从外存上获得前一遍的工作结果开始，完成工作后，把结果存在外存上。每遍工作完成后所占用的存贮空间大部分被释放

六、编译前端和后端

编译前端：与源语言有关，词法分析，语法分析，语义分析，中间代码产生，与机器无关的优化

编译后端：与目标机有关，与目标机有关的优化，目标代码的产生

1.3 高级语言程序简介

一、参数传递

**传地址：**实参计算出结果，把地址送形参
**传值：**把实参的值计算出来送形参
**传名：**相当于进行代换

二、存贮管理

**静态存贮分配：**编译时就安排好目标程序运行时的全部数据空间，并能确定每个数据项目的单元地址
**动态存贮分配：**如果允许递归、可变数据结构，必须动态分配
- 栈式：整个程序的数据空间安排在一个栈中
- 堆式：允许自由地申请和退还空间（new和delete操作）