Overview

编译器和解释器的区别

• Compiler:
  • program -> compiler -> exec + data -> output
• Interpreters：
  • program+data -> Interpreter -> output

历史

• 1954 IBM develops the 704
  • 这个时候发现software取代hardware，成了性能的瓶颈。
• Speedcoding:
  • 1953, by Jon Backus
  • 解释型语言
  • 优势是提高了开发效率
  • 劣势是代码执行效率很低
    • 比直接手写代码慢10-20倍
    • 解释器占了300字节，相当于全部内存的30%

实际上，Speedcoding并没有流行起来，但John Backus认为自己的思路是有正确的，并将它用到了另一个项目中。由于当时的重要的application主要是scientific application。学术界通常都需要计算机能直接执行公式（Formulas）,John Backus认为Speedcoding最大的问题是使用了解释器去实时解析公式，于是他这次改变了思路：将公式（Formulas）先变成可执行的机器码（Translate），这样能加快程序的执行速度，同时又能保持开发的高效，于是便有了FORTRAN 1。

• FORTRAN 1
  • 1954 - 1957
  • 1958 : 50% 的代码都是通过FORTRAN写的
  • 世界上第一个编译器诞生了
  • FORTRAN成了世界上第一个比较成功的高级编程语言，对计算机科学产生了深远的影响
  • 现代的编译器保留了FORTRAN 1的一些框架：
    • Lexical Analysis
    • Parsing
    • Sementic Analysis
    • Optimization
    • Code Generation

How Compiler Works

Lexical Analysis

LA也叫词法分析，LA的输入是程序字符串，输出是一系列的词法单元（token），例如：

main(){
	printf("Hello World");
}

LA会依次读取程序的每一个字符，并将其存入token buffer中，然后不断check当前buffer中的token是否存在于token表中（对于任何一门编程语言都有一组可参考的token符号表）。例如，读到main时，buffer状态如下：

--------------------
| Token Buffer      |
|--------------------
| niam              |
---------------------

查token表发现，main属于关键字，因此标记为一个token, 依次类推，上面代码可以分解为以下的一些tokens:

Keyword: main, printf
Operator: (, ), {, }, ;
Constant: "Hello World"
Seperator: space

每个token都可以用一个tuple来表示：

<token-name，attribute-value>

token的name代表这个token的类型，value用来记录该token在符号表中的index。例如下面语句的token表示为

pos = initial + rate  *  60

1. pos是一个token，用<id,1>，id表示这个token是一个符号，1表示它在符号表的第一个位置
2. =是一个token，用<=>表示，因为它不是符号，因此不计入符号表
3. initial是token，用<id,2>表示
4. +是一个token，用<+>表示
5. rate是token，用<id,3>表示
6. *是一个token，用<*>表示
7. 60是一个token，用<number,4>表示，严格意义来说它不计入符号表

上述语句经过LA之后变成:[ <id,1>, <=>, <id,2>, <+>, <id,3>, <*>, <60> ]，其语法树结构如下：

Parsing

Parsing也叫语法分析(syntax analysis)，Parsing的目的是将LA产生的一系列token形成语法树。 假如我们要解析一个英文句子，可以把它的结构用树形结构来描述，例如下面句子的树形结构为

This line is a long sentence

我们分析代码语句成分也是类似的，例如下面语句：

if x==y then 
	z = 1;
else 
	z = 2;

类似的树形结构为:

Semantic Analysis

一旦树形结构确定，接下来就是最难的语义分析，编译器在这方面很难保持它的理解和programmer的理解是一致的，以英语为例：

“Jack said Jerry left his assignment at home.”

编译器很难理解his指的是jack还是jerrry。再来看一种极端情况:

“Jack said Jack left his assignment at home?”

编译器不理解，到底有几个人，两个Jack是不是同一个人，his只谁？

这种问题对于编译器来说，是variable binding，编译器在处理这类变量名称模糊的情况，是由严格语法规定的：

{
	int jack = 3;
	{
		int jack = 4;
		cout<<jack; 
	}
}

上面的例子中两个jack都是相同的类型，因此编译器需要通过scope来判断输出哪一个jack。除了通过variable binding之外，还可以使用类型判断语义。比如:

“Jack left her homework at home.”

Jack的类型为male，her显然类型为female。由此，编译器便可以知道句子中Jack和her不是同一个人，对应到程序中，便是有两个不同类型的变量。

Optimization

优化通常是用来减少代码体积，例如：”But a little bit like editing” 可被优化成：”But akin to editing”，节省了代码容量，代码能运行的更快，消耗内存较少，编译器的优化是有针对性的，比如：

x = y*0 

在满足一定条件时才会会被优化成:

x = 0

仅仅当，x，y是整数的时候，编译器才会这么优化。当x或y为浮点型时，x,y为NAN类型，而

NAN * 0 = NAN

Code Generation：生成代码

• 生成汇编代码
• 转换成平台相关语言

小结

• 基本上所有的compiler都会遵从上面几个步骤
• 但是从FORTRAN开始，上面5部分的比重却在发生变化：
  • 对于比较老的编译器来说，L,P所占的比重会很高，S,O会很低
  • 对于现代编译器来说，由于有了工具，L,P所在比重明显下降，而O所占的比重却大幅度上升

Economy of Programming Language

• 为什么有很多种编程语言？
  • 科学计算，需要大量计算，需要对float point numbers支持，需要对array支持的很好和并行计算。并不是每种语言都能很好的支持上面的需求，FORTRAN在这方面做的很好。
  • 商用：需要持久化存储，report generation，数据分析。SQL在这方面做的很好 - 系统编程：low level control of resource，real time constrains。C/C++ - 需求很多，很难设计一种语言满足所有场景。
• 为什么还有新的编程语言不断涌现？
  • 传统语言改变的很慢，学习新语言很容易。如果新语言能更快的解决问题，那么它就有存在的价值

附录 Cool Overview

• Cool是用来学习编译器的语言:(Classroom Object Oriented Language)。
• Compiler很容易被实现
• 特性：抽象，静态类型，继承，内存管理等。
• 目标 : 生成MIPS汇编代码

demo

• 使用emacs:
  • %emacs 1.cl
• 编译cool：
  • %coolc 1.cl
  • 生成 1.s的汇编代码
• 运行cool:
  • %spim 1.s

Resource

• Stanford Compiler Course
• Udacity Compiler Course
• Compiler