什么是编译器

compiler

把 高级语言程序 等价转换成 低级语言程序（如汇编语言/机器语言） 的程序

分为几种

• 诊断编译程序（Diagnostic Compiler）：帮助开发和调试
• 优化编译程序（Optimizing Compiler）：提高目标代码的执行效率
  • 现代的编译器同时提供了调试、优化等功能
• 交叉编译程序（Cross Complier）：
  • 宿主机（运行编译程序的机器），目标机（运行目标程序的机器）
  • 宿主机和目标机不一样，叫做交叉编译
• 可变目标编译程序（Retargetable Complier）
  • 针对不同硬件进行调整和替换

编译 vs. 解释

• 编译器实际上是一种“翻译程序”。
  • 它最终输出一个目标程序
• 还有一类“翻译程序”是解释器（Interpreter）
  • 输入源程序，但不产生目标程序，而是边解释边执行
  • 不会有一个完整的目标程序。而是取一条指令，翻译成机器指令并执行；然后取下一条指令，继续执行。

计算思维：新时代的一种基本技能

• 是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为
• 它包括了一系列广泛的计算机科学的思维方法：
  • 抽象（Abstraction），有若干定义：
    • 忽略一个主题中与当前问题(或目标)无关的那些方面，以便更充分地注意与当前问题(或目标)有关的方面
    • 从众多的事物中抽取出共同的、本质性的特征，舍弃其非本质的特征
    • 是一种从个体把握一般、从现象把握本质的认知过程和思维方法
  • 自动化(Automation)
    • 将计算思维成果物化的过程
    • 编译原理中的自动化：有限自动机、预测分析程序、算符优先分析、LR分析…
  • 问题分解(Decomposition)
    • 大的、复杂问题分解成多个小的、简单的问题
    • 编译原理中：编译过程分成多个阶段（词法分析、语法分析、中间代码生成、目标代码生成）
  • 递归（Recursion）：一种特殊的分解方式
    • 分解后，子问题和原问题是一类问题，但是问题更小。
    • 分解到足够小之后，解法十分简单
    • 编译中大量递归
  • 权衡（Tradeoff）
    • 理论可实现 vs 实际可实现
  • 保护、冗余、容错、纠错和恢复
  • 利用启发式推理来寻求解答
  • 在不确定情况下的规划、学习和调度

编译过程

编译过程（以英译中做比喻）

• 词法分析：识别句子中的一个个单词
• 语法分析：分析句子的结构
• 中间代码产生：做初步翻译
• 优化：对译文做修饰
• 目标代码产生：得到最终的译文

词法分析

• 任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出单词符号
• 依循的原则：构词规则
• 描述工具：有限自动机

语法分析

• 任务：在词法分析的基础上，根据语法规则把单词符号串分解成各类语法单位(语法范畴)
• 依循的原则：语法规则
• 描述工具：上下文无关文法

中间代码产生

• 任务：对各类语法单位按语言的语义进行初步翻译
• 依循的原则：语义规则
• 描述工具：属性文法
• 中间代码：三元式，四元式，树，…

优化

• 任务：对前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码
• 依循的原则：程序的等价变换规则

目标代码产生

• 任务: 把中间代码变换成特定机器上的目标代码依赖于硬件系统结构和机器指令的含义
• 目标代码三种形式
  • 汇编指令代码: 不能直接运行，需要先汇编再运行
  • 绝对指令代码: 可直接运行（地址是绝对地址）
  • 可重新定位指令代码: 需要连接（地址是相对地址，可以从任何位置装载），装载后才能运行

编译程序的组成

编译程序包括这些部分：

• 词法分析器
• 语法分析器
• 语义分析和中间代码生成器
• 优化段
• 目标代码生成器

符号表管理模块

• 存储编译过程中，各种对象的存储、组织、修改

出错处理

• 发现源程序中的错误，把有关错误信息（错误位置、错误信息）报告给用户
• 语法错误
  • 源程序中不符合语法（或词法）规则的错误
  • 非法字符、括号不匹配、缺少 ; …
• 语义错误
  • 源程序中不符合语义规则的错误
  • 说明错误、作用域错误、类型不一致、…

遍（pass）：对源程序或源程序的中间表示从头到尾扫描一次

• 一遍可以对应多个阶段。例如，在一遍内完成词法分析、语法分析、中间代码生成
• 一个阶段可以分成多个遍。优化阶段，有很多遍，例如先识别基本结构、然后初步优化，然后循环优化，等等

编译前端 和 编译后端 分离，好处

• 编译程序逻辑结构清晰
• 提高复用
  • 保留前端，替换后端，得到同一种高级语言，不同目标机器的编译器
  • 保留后端，替换前端，得到不同高级语言，在同一个目标机器上的编译器

编译程序生成

方式1:高级语言书写 使用高级语言，快速实现另一个语言的编译器。在 A 机器上：

1. 假设我们已经有了 L1 语言的编译器 (L1->A)
2. 那么我们可以用 L1 语言来写 L2 语言的编译器 (L2->A) L1写的
   • （由于 L1 是个高级语言，用它来写一个编译器会简单很多）
3. 接下来我们 用第1步的编译器编译，第2步的编译器（ (L2->A) L1写的），就得到了一个编译器 (L2->A)

方式2:编译程序的移植，也就是获得另一个机器上的编译器

1. 假设我们有个编译器 L->A，它可以把 L 语言编译成 A 机器上的程序，它在 A 机器上运行
2. 又假设我们用 L 语言编写一个 “L->B” 的编译器 L->B(A机器上运行，L语言写的)
   • 由于 L 是个高级语言，因此写起来会简单很多
3. 把第2步的编译器交给第1步的编译器来编译，得到编译器 L->B(A机器上运行)，这就是一个交叉编译的编译器
4. 把第2步的编译器交给第3步的编译器来编译，得到编译器 L->B(B机器上运行)，这就是 B 机器上的编译器

方式3:自编译

1. 把一个高级语言分解 L=L1+L2+...+Ln
2. 先在 L1 上做一个编译器（简单）
3. 然后在用 L1 对应的语言做 L1+L2 的编译器
4. 以此类推，得到 L1+L2+...+Ln 的编译器

现代已经有自动产生编译程序的程序 编译器产生器

• LEX：词法分析程序的产生器
• YACC：语法分析程序的产生器
• 甚至还有获得整个编译器的产生器

高级语言

优点

• 更接近数学语言（或工程语言、或自然语言）
• 可读性强，容易review
• 编写效率高
• 容易移植

程序语言的定义：语法 + 语义 + 语用

• 语法 = 词法规则 + 语法规则，描述的是形式规则
  • 词法规则：基本单词。（常数、标识符、基本字、算符、界符）
    • 工具：有限自动机
  • 语法规则：表达式、语句、分程序、过程、函数、程序等
    • 工具：上下文无关文法
• 语义：一组规则，用它可以定义一个程序的意义
  • 操作语义、指称语义、代数语义

高级语言的分类

• 强制式语言(Imperative Languge)/过程式语言
  • FORTRAN、C、Pascal，Ada
• 应用式语言(Applicative Language)：注重程序所表示的功能，而不是一个语句接一个语句地执行
  • LISP、ML
• 基于规则的语言( Rule-based Language)检查一定的条件，当它满足值，则执行适当的动作
  • Prolog
• 面向对象语言(Object-Oriented Language)
  • 封装、继承和多态性
  • Smalltalk，C++，Java

然后罗列一下高级语言的一般特性

• 程序结构（主程序、辅程序、变量作用yu）
• 数据结构与操作（数据类型的属性、值、操作）
  • 初等数据类型（整形、双精度、加减乘除等）
  • 数组等
  • struct
• 表达式、控制语句
  • 算符的优先次序
  • 赋值语句（左值 存储单元地址、右值 存储单元内容）。赋值号左边的变量必须有左值，右边的变量必须有右值
  • 控制语句。转移语句、条件语句、循环语句、调用语句、返回语句

语句分类

• 功能上分类
  • 执行性语句
  • 说明性语句。定义变量、运算等
• 形式上分类
  • 简单句：不包含其它语句的语句
  • 符合句：包含其它语句的语句

词法分析

• 字母表：一个有穷字符集合

• ---

参考资料

《编译原理》课程，国防科技大学，中国大学MOOC https://www.icourse163.org/course/NUDT-1003101005