怎样设计一套程序设计语言?

大哉问。让我试试从最简单的概念角度回答一下:

首先要有爱。纯粹的,不屈的,倾注全心的爱。对于一个语言所塑造,只存在你想象之中的完美世界的爱……

……呃,然后你要决定你想设计的语言应该解决什么问题。虽然阿达·爱蕾丝女士[1]作为世界上第一个程序员,并没有使用任何特定的人造语言来编程,但现如今世风日下、人心不古,人们不再满足于用计算机算个伯努利数列,还要它解决登月、模拟核爆、设计气动外形、乃至用红鸟炸绿猪这样棘手的技术问题。面对不同的领域、不同的需求、不同的抽象层级、不同的思考范式,也就产生了各有特长的编程语言。专注于高效、便捷地解决某特定范畴之内问题的语言,叫做领域专用语言(Domain Specific Language,DSL)[2],而可以跨越若干领域解决问题的语言,叫做泛用语言(General-Purpose Language,GPL)[3]。常见的 DSL 比如 MATLAB、SQL 等等;常见的 GPL 自然就是那些 C 啦 Python 啦什么的。哦还有汇编。当然,两类语言之间的分界并不是很明显,有些语言一开始是作为 DSL 设计的,后来渐渐朝着 GPL 的方向发展,比如 PHP 和 JavaScript;反过来也有大量基于 GPL 开发而来的 DSL。注意也不是所有的计算机语言都可以归入这两类,有些语言被创造出来的理由很简单——“因为我们可以做到”,或者“就是为了好玩”,所以它们唤作“蛋痛编程语言”(Esoteric Programming Language)。

当然你的第一个自制语言也许只是为了尝试一下这件事情是否可行。尝试可行性,其实已经接近于“就是为了好玩”的境界了,所以要有蛋痛的觉悟,因为从头设计一套编程语言是颇为蛋痛的事情,几乎要事必躬亲,花费几天时间来实现微不足道的功能,展示给别人看时却招来“这有什么稀奇?”的茫然一问。如果不能乐在其中,如果爱意不够纯粹、不屈、倾注全心,是没办法做成的。

从最基本的角度看,一种编程语言就是:把一组特定的词汇,按照一组特定的语法规则组合到一起,形成计算机可以通过某种方式“理解”的东西,可以让计算机据此执行特定的动作

先看看这件事情的最底层。所谓“计算机执行动作”,其实只是“把一个二进制数字传入 CPU,然后等待什么事情发生”的形而上描述。二进制计算机所能理解的唯一东西就是二进制数字,称为“机器码”[5]。比如:

10110 000 01100001

这串数字,对于某颗 CPU 来说,就是“把 01100001 放到 000 号寄存器里”的指令,其中“10110”的部分,就是 CPU 能懂得的“放入”指令。这样的指还有许许多多,比如做加法、求逻辑“与”,跳转,加密等等,全都只是一些二进制数字而已。

对人类来说,这种纯数字的写法太难记忆,就把它转写成:

MOV AL, 97

其中 MOV 代表“10110”,AL 代表 000 号寄存器,97 则是二进制数 01100001 的十进制表示。其他的数字指令也一并用这种简记法来转写,比如[6]。使用这样的一种转写方法来写程序,就是汇编语言(当然,这是一种极度简化的说法)。汇编语言谈不上太多设计,其实几乎就是在直接告诉 CPU 应该做什么。把汇编语言转化为机器码的程序,称为“汇编器(Assembler)“。

汇编语言的优势是很低级,你直接控制 CPU 的行为;汇编语言的缺点也是它太低级,你必须直接控制 CPU 的行为。看看“把 A 的值放进甲寄存器;B 的值放进乙寄存器;把乙寄存器的值放进 A;把甲寄存器的值放进 B。”这段汇编指令——它想干什么?运行一下之后会看到,A 和 B 的值互换了。那么,能不能直接写“交换变量 A 和 B 的值”,然后由计算机来分解为一串机器码的组合呢?

所谓的“高级”编程语言就是这样的原理。将高级编程语言翻译成机器码(或者其他更接近机器码的形式)的过程,也就是计算机“理解”语言的过程,叫做“编译”,而完成这一工作的程序,叫做“编译器(compiler)”或者“解释器(interpreter)”,两者的区别是,编译器一次性解析所有代码并转换成机器码(但通常不会运行),而解释器则每解析一小部分就运行一小部分。

接下来就要考虑两个问题:高级语言要让人写起来方便;也要让计算机易懂。因为人类是难搞的物种,所以前者通常是语言设计的重点。毕竟,只要懂些编程的基本知识,任何人都可以在三天时间里设计出一门计算机语言,并且让计算机读懂它(也就是写出编译器),但要让一种计算机语言写起来舒服、读起来易懂、管理起来方便,所需耗费的心力和时间则相去不可以道里计。探寻这一问题的种种思潮所引发的范式转换和生产力革命,是计算机历史的永恒主题之一。计算机语言越来越高级,使用起来越来越简单,实现却越来越复杂;许多编程观念比如面向对象(object orientation)、函数编程(functional programming)、事件驱动(event driven)之诞生、沉寂、重现、兴盛和定型,都经由编程语言有所体现。

当然这并不是说编译部分就不重要。可靠、高效、灵活的编译器是一切编程工作的基石。我们日常所用的编译器都是如此千锤百炼的东西,以至于你很少会意识到它们本身也是复杂的软件工程项目,也有可能出问题,也在不断地发展着。十年前和现在的编译器,从架构理念到实现都有不小的差别。好在这种差别算不上天翻地覆,计算机语言编译的大致过程一直都是如下几个步骤:

  1. 高级语言的源代码经过词法分析(lexical analysis)成为一堆符记(token)
  2. 符记经过句法分析(syntactic analysis)成为语法树(abstract syntax tree, AST)
  3. 语法树经过优化,比如去除冗余的部分,最后映射成为机器码(machine code)

第一步,词法分析,根据的是语言设计者所规定的词汇规则。比如 PHP 规定变量前头必须加个 $ 符号,就是这样的规则。通常通过正则表达式(regular expression)给出这些规则。根据规则来分析源代码的编译器组件叫做词法分析器(lexer)或者扫描器(scanner)。扫描器可以自己手写,也可以让叫做 scanner generator 的程序读取一个正则表达式,然后帮你生成一个 scanner,比如 lex [7] 就是这样一个工具。词法分析的目的是判断人类写下的每个词是不是合乎拼写规则,如果不符的话,显然也就无法编译了。

第二步,句法分析,根据的是语言设计者所规定的语法规则。关于形式语言的语法理论,涉及到语言学和数理逻辑,是一个复杂而艰深的领域,好在对于设计一门计算机语言来说,只需要知道,计算机语言的语法通常是上下文无关文法(context-free grammar)[8] 即可:生成一条计算机语句的规则与这一规则所处的环境无关。这样一来,解析一条编程语句的过程就是确定的无二的。根据规则来将上一步骤获得的词汇解析为特定的数据结构——比如语法树——的工具,叫做句法分析器(parser)。同样,句法分析器可以自己写,也可以用特定的方法(最常见的是巴克斯范式(BNF)[9])给出下上下文无关文法的形式语言描述,然后用所谓 parser generator 来生成。可以说,语法树(或者类似的中间产物)代表了从编程语句中提炼出来的意义,这是整个编译过程的核心所在。

第三步,语法树或者其他的语义表示方法经由优化器(optimizer)的修剪,送入负责将特定结构转化为目标机器代码的程序生成可以运行的二进制程序。这一步必须考虑执行效率优化和目标架构的特点,与高级编程语言本身已经并无太大关联了。

了解以上步骤之后,就可以设计编程语言了。相关的指导书籍有很经典的几本,分别是:

龙书(Dragon Book): Compilers: Principles, Techniques, & Tools
虎书(Tiger Book):Compiler Implementation in C
鲸书(Whale Book):Advanced Compiler Design and Implementation
橡书(Ark Book) :Engineering a Compiler
还有魔法书(Wizard Book):Structure and Interpretation of Computer Programs

[1] en.wikipedia.org/wiki/A
[2] en.wikipedia.org/wiki/D ,注意 DSL 并不一定是编程语言,有些 DSL 只用来描述数据
[3] en.wikipedia.org/wiki/G
[4] en.wikipedia.org/wiki/E
[5] en.wikipedia.org/wiki/M
[6] en.wikipedia.org/wiki/X
[7] en.wikipedia.org/wiki/L
[8] en.wikipedia.org/wiki/C
[9] en.wikipedia.org/wiki/B
原发布于 https://www.zhihu.com/question/19756886/answer/13078616