编译原理（龙书）-- 引论笔记

语言处理机

编译器
- 编译器是一个程序，可以阅读某一种语言（源代码），并将之翻译成另一种等价的语言（目标语言）编写的程序
- 源程序 $\Longrightarrow$ 编译器 $\Longrightarrow$ 目标程序
解释器
- 解释器直接利用用户提供的输入执行源程序中指定的操作（并不通过翻译的方式生成目标程序）
优缺点
- 编译器产生的机器语言目标程序通常比一个解释器快很多
- 解释器的错误诊断效果通常比编译器更好，因为它逐个语句执行源程序
Java语言处理器
- 结合了编译和解释过程
- 源程序 $\Longrightarrow$ 编译器 $\Longrightarrow$ 中间程序（字节码）+ 输入 $\Longrightarrow$ 虚拟机 （解释执行） $\Longrightarrow$ 输出
- Java的即时编译器：将字节码翻译成机器语言，再执行程序（跳过解释执行过程）
语言处理系统
- 源程序 $\Longrightarrow$ 预处理器 $\Longrightarrow$ 经过预处理的源程序 $\Longrightarrow$ 编译器 $\Longrightarrow$ 目标汇编程序 $\Longrightarrow$ 汇编器 $\Longrightarrow$ 可重定位机器代码 + 库文件、可重定位对象文件 $\Longrightarrow$ 链接器/加载器 $\Longrightarrow$ 目标机器代码
- 预处理器
  - 将分割成多个文件的源程序聚合成一个独立的文件
  - 将宏转换为源语言语句
- 链接器
  - 大型程序通常需要分成多个部分进行编译，可重定向的机器代码有必要需要和其他可重定向对象文件以及库文件链接到一起，形成真正在机器上运行的代码
  - 解决：一个文件中的代码指向另一个文件中的位置，链接器解决外部内存地址问题
- 加载器
  - 将所有的可执行目标文件放到内存中执行

编译器的结构

组成
- 前端：分析部分，检查语法语义、生成符号表和中间表示
- 后端：综合部分，根据符号表和中间表示中的信息构建目标程序
编译步骤
- 字符流 $\Longrightarrow$ 词法分析器 $\Longrightarrow$ 符号流 $\Longrightarrow$ 语法分析 $\Longrightarrow$ 语法树 $\Longrightarrow$ 语义分析 $\Longrightarrow$ 语法树 $\Longrightarrow$ 中间代码生成器 $\Longrightarrow$ 中间表示形式 $\Longrightarrow$ 机器无关代码优化器 $\Longrightarrow$ 中间表示形式 $\Longrightarrow$ 代码生成器 $\Longrightarrow$ 目标机器语言 $\Longrightarrow$ 机器相关代码优化器 $\Longrightarrow$ 目标机器语言
词法分析（扫描）
- 读入源程序字符流，将它们组织成有意义的词素（lexeme）序列
- <token-name(抽象符号),attribute-value(指向符号表中关于这个词法单元的条目)>
- 例如：
  - position = initial + rate * 60
  - <id,1><=><id,2><+><id,3><*><60>
语法分析
- 使用由词法分析器生成的各个词法单元的第一个分量来创建树型的中间表示
- 常用的表示方法：语法树（树中的每个内结点表示运算，子节点表示该运算的分量）
语义分析
- 使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致
- 收集类型信息，并把这些信息存放在语法树或符号表中
- 类型检查
中间代码生成
代码优化
代码生成
符号表管理
- 记录源程序中使用的变量的名字，并收集和每个名字的各种属性有关的信息
- 这些属性可以提供一个名字的存储分配、它的类型、作用域等信息
- 符号表数据结构为每个变量名字创建了一个记录条目
将多个步骤组合成趟
- 在特定的实现中，多个步骤可以组合成一趟（pass）
编译器构造工具
- 常用编译器构造工具
  - 语法分析器的生成器
  - 扫描器的生成器
  - 语法制导的翻译引擎
  - 代码生成器的生成器
  - 数据流分析引擎
  - 编译器构造工具集

程序设计语言

按代分类
- 机器语言（第一代）
- 汇编语言（第二代）
- 高级程序设计语言（第三代）
- 为特定应用设计的语言（第四代，例如SQL）
- 基于逻辑和约束的语言（第五代，例如Prolog、OPS5）
按计算任务的完成方式分类
- 强制式：程序中指明如何完成一个计算任务
  - 例如：C、C++、C#、Java
- 声明式：程序中指明进行哪些计算
  - 例如：ML、Haskell、Prolog
冯·诺依曼语言：指以冯·诺依曼计算机体系结构为计算模型的程序语言
面向对象语言：指用一组相互作用的对象组成程序的变成风格
脚本语言：具有高层次运算符的解释型语言，通常被用于把多个计算过程“粘合”在一起