PL真有意思（一）：引言

断断续续学编译原理到之前发过写一个编译器和正则表达式引擎系列文章也有一段时间了，然后最近看完PLP这本书，这本书应该算是入门书，但是对我这种半吊子收获很大。所以为了弥补最近学操作系统和接外包摸的鱼，就想写写看完这本书的收获。(为拙劣的标题道歉

程序设计语言的谱系

现在的新语言都是一撮一撮的出来，但是基本都可以用他们的计算模型来分成两类，一类是更关心计算机做什么的 说明式 ，一类是更关心计算机怎么做的 命令式

一般认为像函数式逻辑式语言都算是说明式，而冯诺依曼式和面向对象的都被认为是命令式

函数式

函数式是基于函数的递归定义的计算模型，一般从本质上来看，函数式把程序认为是一种从输入到输出的函数，使用更简单的函数通过逐步细化的过程来定义

逻辑式

逻辑式里经典的应该就是Prolog了，逻辑式一般将计算看作是一种找出满足某些特定关系的值的尝试过程

冯诺依曼式

冯诺依曼式最重要的就是通过副作用也就是修改寄存器里的值来对后续计算产生影响，像C和Fortran都属于冯诺依曼式

几个例子

如果C语言来实现求最大公约数，可以发现C语言偏向通过迭代和反复修改变量的值来实现

int gcd(int a, intb) {
    while (a != b) {
      if (a > b) {
        a = a - b;
      } else {
        b = b - a;
      }
    }
}

从lisp来看，则更加关注输入和输出的数学关系，要算出最大公约数，需要对函数的不断的扩充和精简

(define gcd
  (lambda (a b)
    (cond ((= a b) a)
          ((> a b) (gcd (- a b) b))
          (else (gcd (- b a) a)))))

对于像C或者Java入门的人，看到Prolog可能头都大了，因为Prolog和命令式的思考逻辑完全不同，逻辑式更倾向给出一组公理和检测规则，期望系统能给出相应合理的值，我也仅限于能看懂这些小程序

gcd(A,B,G) :- A = B, G = A.
gcd(A,B,G) :- A > B, C is A - B, gcd(C,B,G)
gcd(A,B,G) :- B > A, C is B-A
gcd(C,A,G)

编译和解释

下面再看两个概念，编译和解释。

编译一般是指从一个语言到另一个语言的翻译，无论是高级语言到汇编还是高级语言到高级语言都算是编译。而解释就是直接执行代码，但是现代的解释器，一般还有虚拟机一层，即翻译到虚拟机指令再由虚拟机进行执行

自举

很多语言的编译器都是由自己编译而成的，所以问题就是，最开始的编译器是怎么编译的？

假设现在要为Java编写一个编译器，我们可以先用C语言编写一个Java小子集的编译器，然后再手动将C语言翻译到这个Java子集，就可以由这个子集编译运行自己，然后就可以不断扩充这个编译器

编译概览

其实这个在之前那个写编译器的系列是说得最详细的，这个系列是想要写写笔记对实践和语言设计结合的说。

• 词法分析

有关词法分析其实就是将字符流化成单词流，记录每个单词的信息，然后通常还会有其它更多的信息让编译器更好的生成错误信息

• 语法分析

语法分析通常会用到一个概念：上下文无关文法，就是用来定义语法形式的，比如while语句就可以这样表示

while-statment := WHILE ( expr ) statment

一般语法分析过程最后的输出都是树状结构

• 语义分析和中间代码生成

语法分析只保证源代码语法格式的正确，但是却不能保证其它的正确性，比如对于静态类型的语言，可能就会在编译时直接检测出类型错误

而在语义分析过程一般还需要借助一个叫做符号表的数据结构，这个符号表将每个标识符都映射到关于它的已知信息

中间代码的生成通常是会将树形结构翻译成更接近汇编的中间线性格式，但是中间格式不是必须的，比如之前那个系列里还写了C的解释器，虽然很残缺，它是没有中间代码的，连虚拟机都没有，是直接进行遍历语法树进行执行解释的

• 代码优化

有些代码改进是机器无关的，即可以在中间格式上就进行优化，但是有的代码优化是平台相关的，所以就需要在最后对目标语言优化

• 目标代码生成

代码生成阶段就是根据之前生成的线性结构和符号表信息对目标代码的生成

小结

这一篇主要说了几个范式的语言和编译过程的概括，对摸鱼进行忏悔