<编译原理>读书笔记
2020/07/22
posted in
编译原理
第一章 引论
1.1 语言处理器
- 编译器(compiler)就是将一种语言编写的程序翻译成另一种语言编写的程序
目标程序可以被调用并产生输出
解释器(interpreter)直接利用源程序将输入映射成为输出.
对比编译器和解释器: 编译器生成的目标程序比解释器快, 解释器的错误诊断效果比编译器好
混合编译器. 如JAVA, JAVA源程序先被编译为字节码(bytecode), 而后由虚拟机对字节码进行解释
字节码的优点: 字节码有更好的跨平台的通用性
JIT编译器: 有些被称为即时 （just in time）编译器的Java编译器在运行中间程序处理输入的前一刻首先把字节码翻译成为机器语言，然后再执行程序
一个语言处理系统的流程
预处理器(preprocessor)负责两项工作:
- 将分割成多个模块的源程序聚合起来
- 将宏转化为源语言语句
1.2 一个编译器的结构
一个编译器的各个步骤
1.2.1 词法分析
词法分析(exical analysis)是编译器的第一个步骤, 又被称为扫描(scanning).
通过词法分析器将字符流转化成为有意义的词素(lexeme)的序列.
而词素会被表示为形如<token-name, attribute-value>的词法单元(token)
源程序
position = initial + rate * 60
经过词法分析后被表示为
一个赋值语句的翻译
1.2.2 语法分析
语法分析(syntax analysis)是编译器的第二个步骤, 又被称为解析(parsing).
语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示
1.2.3 语义分析
语义分析器(semantic analyzer)使用
语法树和符号表中的信息来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。
语义分析阶段的工作内容有:
- 类型检查(type checking): 编译器检查每个运算符是否具有匹配的运算分量。比如，数组下表必须是整数类型。
- 自动类型转换(coercion)
1.2.4 中间代码生成
中间表示在源程序翻译成目标代码的过程中, 可能有一个或多个
中间表示有多种形式, 如:语法树和三地址代码(three-address code), 其中语法树常用在语法分析和语义分析中
三地址代码,例如
有三个特点
- 每个三地址赋值指令的右部最多只有一个运算符
- 编译器应该生成一个临时名字以存放一个三地址指令计算得到的值
- 有些三地址指令的运算分量的少于三个（比如上面的序列1.3中的第一个和最后一个指令）
1.2.5 代码优化
机器无关的代码优化通过改进中间代码使代码更快或者更短/能耗更低
1.2.6 代码生成
将中间表示形式映射为目标语言
合理分配寄存器以存放变量的值
1.2.7 符号表管理
记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息
1.2.8 将多个步骤组合成趟
在一个特定的实现中，多个步骤的活动可以被组合成一趟 （pass）
前端可以和不同的后端组合
1.2.9 编译器构造工具
一些常用的编译器构造工具包括：
- 语法分析器的生成器： 可以根据一个程序设计语言的语法描述自动生成语法分析器。
- 扫描器的生成器： 可以根据一个语言的语法单元的正则表达式描述生成词法分析器。
- 语法制导的翻译引擎： 可以生成一组用于遍历分析树并生成中间代码的例程。
- 代码生成器的生成器： 依据一组关于如何把中间语言的每个运算翻译成为目标机上的机器语言的规则，生成一个代码生成器。
- 数据流分析引擎： 可以帮助收集数据流信息，即程序中的值如何从程序的一个部分传递到另一部分。数据流分析是代码优化的一个重要部分。
- 编译器构造工具集： 提供了可用于构造编译器的不同阶段的例程的完整集合。
1.3 程序设计语言的发展历程
1.3.1 走向高级程序设计语言
语言的分类:
根据代分类
- 第一代语言 是机器语言，
- 第二代语言 是汇编语言，
- 第三代语言 是Fortran、Cobol、Lisp、C、C++、C#及Java这样的高级程序设计语言。
- 第四代语言 是为特定应用设计的语言，比如用于生成报告的NOMAD，用于数据库查询的SQL和用于文本排版的Postscript。
- 第五代语言 指的是基于逻辑和约束的语言，比如Prolog和OPS5。
强制式 （imperative）语言
声明式 （declarative）语言
冯·诺伊曼语言 （von Neumann language）
面向对象语言 （object-oriented language）
脚本语言 （scripting language）