编译原理（1）总结

  本科是网络工程，由于没有学<<编译原理>>这门课，打算两个月把国科大的编译原理梳理完，把其中我认为的精髓概括一下，三天一篇，作为笔记。

一、什么是编译程序

  为了了解什么是编译程序，首先了解下翻译程序是什么：

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

  而编译程序就是一种翻译程序。它把某一种高级语言程序等价转换为另一种低级语言程序（如汇编语言或机器语言）的程序。   编译程序还有以下分类：

• 诊断编译程序（Diagnostic Complier，帮助程序员排错）
• 优化编译程序（Optimizing Complier，提高目标代码执行效率）
• 交叉编译程序(Cross Complier)

两个概念：

• 宿主机（运行编译程序的机器）
• 目标机（运行目标源程序的机器） 一般来说，宿主机和目标机是同一类型机器，如果不同，则叫做交叉编译程序，如在Windwos交叉编译可在Linux上运行的程序。
• 可变目标编译程序（Retargetable Complier）

  还有一种翻译程序——解释程序（Interpreter），即把源语言的源程序作为输入，但不产生目标程序，而是边解释边执行源程序。

二、为什么要学习编译原理

• 理解计算系统
• 设计计算系统
• 训练计算思维
  • 抽象
  • 自动化
  • 问题分解
  • 递归
  • 权衡
  • 保护、冗余、容错、纠错和恢复
  • 利用启发式推理来寻求解答
  • 在不确定情况下的规划、学习和调度
  • ......

三、编译过程

  编译程序是怎样把高级语言（如C++）翻译成低级语言的（如机器指令）的？

The complier can translate a program from source language to target language.

  以把英文翻译为中文为例。

• 识别出句子中的单词——词法分析
• 分析句子的结构——语法分析
• 根据句子的含义进行初步翻译——中间代码产生
• 对译文进行修饰——优化
• 写出最后的译文——目标代码产生

1. 词法分析

  任务：对源程序字符串进行扫描和分解，识别出单词符号。   原则：构词规则   工具：有限自动机

2. 语法分析

  任务：在词法分析的基础上，根据语法规则把单词符号分解成各类语法单位（语法范畴）   原则：语法规则   工具：上下文无关文法

3. 中间代码产生

  任务：对各类语法单位按语言的 语义进行初步翻译。   原则：语义规则   工具：属性文法   中间代码：三元式、四元式、树...

4. 优化

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

4. 目标代码产生

  任务：把中间代码变换成特定机器上的目标代码。   原则：依赖于硬件系统结构和机器中指令的具体含义

  目标代码三种形式

• 汇编指定代码：需要进行汇编
• 绝对指定代码：可直接运行
• 可重定位指令代码：需要链接

四、编译程序的结构

五、编译程序的开发

1. 使用机器语言

优点：可针对具体机器，充分发挥计算机的系统功能（使用某些特殊指令）、生成的程序效率高。 缺点：可读性极差、可维护性极低、开发效率极低、可移植性极低。

2.使用汇编语言

优点：机器指令语义化，有一定可读性。可针对具体机器，充分发挥计算机的系统功能（使用某些特殊指令）、生成的程序效率高。 缺点：需要相应汇编器，可读性差、可维护性低、开发效率低、可移植性低。

3.使用高级语言

  如果已存在某种高级语言（如C++，已存在C++的编译器和汇编器）。现假设新语言为S，目标语言为T，实现语言为I，那么，可以利用现有的I语言为编程工具，编写从S语言到T语言的编译器，这样，一种新的语言S就产生了。因此，高级语言的产生过程最开始一定是由机器语言迭代产生的。

优点：程序易读、易理解、易维护、编码效率高。 缺点：不能精准控制目标代码的生成，目标代码执行效率可能不高，可通过插入目标代码方式解决。（如在C/C++中通过内联汇编实现，C#通过EMIT写IL代码实现）