编译原理(龙书) 一

2016/01/01 阅读笔记

最近对创造语言比较感兴趣,所以准备通读一下编译原理的三大神书:龙书,虎书,鲸书,先从龙书开始。

龙书,全名叫做编译原理和技术(Compilers: Principles,Techniques,and Tools),以其封面的龙而得名。其主要是编译器设计基础课程的教材,但是它介绍的知识不仅试用于编译器设计,也适用于一般的软件设计。全书一共十二章,这一篇笔记主要针对第一章,整体介绍了下编译器。

编译器介绍

编译器的定义:一个读入一种语言(源语言)编写的程序并将其翻译成一个与之等价的另一种语言(目标语言)编写的程序。

编译器的分类:一遍编译器,多遍编译器,装入并执行编译器,调试编译器,优化编译器等多种类别。

编译器的模型:分析-综合。分析部分将源程序切分成一些基本块并形成源程序的中间表示,综合部分把源程序的中间表示转换为目标程序。

语法树:树形结构,每个节点表示一个操作,该节点的子节点表示这个操作的参数。

编译过程:

源程序模块  -->  预处理器 -- 源程序---> 编译器 -- 目标汇编程序 --> 汇编器 -- 可重定位机器代码 --> 装载器/连接-编译器 --> 绝对机器代码

源程序分析

三个过程:

  1. 线性分析(词法分析):从左到右地读取构成源程序的字符流,而且把字符流分组为多个token。
  2. 层次分析(语法分析):token在层次上划分为具有一定层次的多个嵌套组,每个组右整体的含义。
  3. 语义分析:进行检查,确保程序的各个组成部分确实是有意义地组合在一起。

编译各阶段:

符号表管理:每个标识符在符号表中都有一条记录,记录的每个域对应标识符的属性。标识符的属性由词法分析后的各阶段陆续写入符号表,并被使用。 错误检查与报告:发现错误立即停止运行的编译器不是一个好的编译器,错误处理保证编译器出错后还能继续运行检查更多的错误。

一个语句的翻译:

源语句:position := initial + rate * 60

词法分析器: id1 := id2 + id3 * 60

语法分析器:

                :=
 |-----------|-----------|
id1                            +
                    |---------|----------|
                  id2                        *
                                   |-------- |-------|
                                   id3                  60

语义分析:

                :=
 |-----------|-----------|
id1                            +
                    |---------|----------|
                  id2                        *
                                   |-------- |-------|
                                   id3                  inttoreal
                                                           |
                                                          60

中间代码生成:

temp1 := inttoreal(60)
temp2 := id3 + temp1
temp3 := id2 + temp2
id1 := temp3

代码优化:

temp1 := id3 * 60
id1 := id2 + temp1

代码生成:

MOVF  id3, R2
MULF #60.0, R2
MOVF id2, R1
ADDF R2, R1
MOVF R1, id1

编译器辅助

预处理器
  1. 宏处理:允许用户在源程序中定义宏,宏是被经常使用的较长结构的缩写。 2.文件包含:把头文件包含到程序正文中。
  2. 理性预处理器:把现代控制流和数据结构化机制添加比较老式的语言中。如使用宏定义替代while和if语句。
  3. 语言扩充:通过内部宏定义增强语言的能力。
汇编器

处理一些编译器产生的汇编代码,然后交给装配器或者连接编辑器处理。

两道汇编

第一遍: 汇编源程序 –> 第一次遇到标识符 —> 符号表(与编译器的符号表分开) : 标识符 标识符对应的地址 第二遍: 汇编源程序 –> 操作符 –> 对应二进制位序列 –> 标识符 — 符号表 —> 地址 ———> 可重定位的机器代码

可重定位的机器码中所有地址加上起始内存单元地址L可以得到绝对定位机器代码,所有的存储地址的引用都是正确的。

装配器和连接编辑器

装配器包含装入和连接编辑两功能:

  1. 装入:读入可重定位机器代码,修改可重定位地址,存放修改后的指令和数据。
  2. 连接编辑:将多个可重定位机器代码的文件组装成一个程序。

前端与后端

前端:词法分析,语法分析,符号表的建立,语义分析,中间diam生成,相关错误的处理,一部分代码优化。依赖于源程序 后端:代码优化,代码生成,相关错误处理和符号表操作。一般只依赖于中间语言。

Search

    Table of Contents