Build Your Own Lisp 中文版 (2018年)资料

BuildYourOwn

Lisp中文版

刘阳

TableofContents

第零零章-关于

第零一章•介绍

第零二章-安装

第零三章•基础

第零四章•交互

第零五章•编程语言

第零六章・语法分析

第零七章•计算

第零八章・错误处理

第零九章・s-表达式

第零十章-Q-表达式

第十一章-变量

第十二章・函数

第十三章-条件分支

第十四章♦字符串

第十五章•标准库

第十六章-彩蛋

第十七章・附录

TableofContents

第零零章•关于1.1

第零一章-介绍1.2

第零二章•安装1.3

第零三章•基础1.4

第零四章•交互1.5

第零五章-编程语言1.6

第零六章・语法分析1.7

第零七章-计算1.8

第零八章・错误处理1.9

第零九章・S-表达式1.10

第零十章•Q-表达式1.11

第H-一章•变量1.12

第十二章・函数1.13

第十三章•条件分支1.14

第十四章•字符串1.15

第十五章•标准库1.16

第十六章・彩蛋1.17

第十七章•附录1.18

第零零章•关于

在本书中，你将在学习C语言的同时学会编写你自己的编程语言一一一个100

0行左右代码的简单Lispo不过我们并不是从零开始编写的，在代码中我用到

了一个外部的库来完成一些初始化的工作。但是剩下的最重要的部分都是我们

一行一行编写的，而且在本书结束时，你将会拥有一个属于自己的“麻雀虽小,

五脏俱全”的Lisp。

很多人非常想学习C语言，但却无从下手。现在大可不必担心了。如果你能坚

持看完本书，我敢保证，至少你将拥有一个非常酷的新语言可以把玩，说不定

还能成为一个熟练的C程序员呢！

原作者(Author)：DanielHolden(contact@theorange

duck,com)

•阅读地址：http:〃buildyourownlisp.com/

•项目主页：Bui1dYourOwnLisp

•共享协议：CCBY-NC-SA3.0

译者(Translator)：KSCO(numbksco@gmail.com)

•阅读地址：https:〃ksco.gitbooks.io/build-your-own-lisp/

•项目主页：Bui1dYourOwnLispCn

・共享协议：CCBY-NC-SA3.0

第零一章•介绍

这本书是给谁看的

本书是为那些想学习C语言，或是想知道怎样构建自己的编程语言的人编写的。

本书不适合作为第一本编程入门书籍。但是如果你之前有一点编程的基础，不

管是什么语言，我相信你都会在本书中找到一些新奇而有趣的东西。

我会把本书写的尽量的通俗易懂，对初学者更加友好。但是初学者可能还是会

感觉本书的内容很有挑战性。我们会遇到非常多的新概念，而且还会同时学习

两门截然不同的编程语言哦！

在写代码遇到问题的时候，如果到网上寻求帮助，你可能会发现人们对你并不

友好。他们很多时候并不是在帮助你解决问题，而是炫耀他们在这方面的“知

之甚多”。他们可能会指责你的错误，其实潜台词就是“你不适合写代码，不

要再让你的烂代码污染这个世界了”。

在几次类似的经历之后，你很可能就会心灰意冷，觉得自己根本算不上一个程

序员，或是自己压根儿不喜欢编程。你可能曾经想过要编写一门属于自己的编

程语言或是其它的有趣而富有挑战性的项目。但是后来你意识到，难度太大了,

我根本就做不到。

对此，我只能感到抱歉。程序员们可能无礼、自大、傲慢、脾气暴躁，但是这

些都无可指责。毕竟每天加班累的跟狗一样，自然需要一个地方发泄。但是你

需要知道的是，没有人是天生就会的。每个人都曾经是初学者。都犯过跟你一

样的低级错误。所以，请不要放弃这项富有创造力的工作，而是努力去改变这

个世界！

为什么要学习C语言

C语言是世界上最流行的，最具有影响力的编程语言之一。Linux操作系统就

是用C语言写成的。AppleOSX和MicrosoftWindows中也大量的用到了C

语言。C语言甚至还被用于微型电脑中一一你家的冰箱和汽车可能就运行着使

用C语言写就的程序。在现代的软件开发中，软件形式的多样化使得C语言

在很多方面并不是首选，但是学会C语言仍然是软件开发者的必备技能之一。

C语言是自由的。从Unix,Linux到自由软件运动，它都起到了举足轻重的作

用。而C语言本身也同样是自由的，它将自己所有的东西和盘托出，不藏不掖,

甚至包括了自己的缺点。它几乎不限制你做任何事情，即使那样做会发生糟糕

的事情。它给了你足够多的选择，该怎么做就全看你自己了。

掌握了C语言，就会懂得什么才是强大，巧妙和自由。在电脑前动动指尖就会

让世界更加美好。

怎样学习c语言

c语言是一门很难学的语言。它有很多陌生的概念，而且初学者很难理解透彻。

本书中，我不会去详细的介绍c语言的语法规则，或是循环和条件语句的编写

方法之类的东西。我会告诉你的是构建真实世界中的C语言程序的方法。这种

方式对于读者来说通常更加难以理解，但是却会教给你很多传统方法给不了的

东西。本书并不能保证让你成为C语言的专家，但至少会让你学会一些有实际

意义的知识，而不是学习一些没有意义的程序片段。

本书包含了17个短小精练的章节。你应该安排好你的阅读进度，每天按照计

划阅读并及时实践。建议每天至少阅读一个章节。读完本书之后，你还可以继

续完善你的Lisp,使它更加完整与强大。

你自己的Lisp

阅读学习本书的最好方式正如同本书的书名，BuildYourOwnLisp。如果你学

起来比较轻松，我建议你尝试添加或修改已有代码，为语言添加新的特性。虽

然每一章都会有详细解释，但我还是给出了大量的代码示例。我知道很多人会

直接将代码拷贝到自己的项目中，但是这样做通常不如自己亲自将代码写出来

更加印象深刻。所以，请不要这样做!

第零二章•安装

在开始学习c语言之前，我们需要安装一些必要的东西，搭建好编程的环境。

好在过程并不复杂，我们只需要两个工具：代码编辑器和编译器。

代码编辑器

代码编辑器其实就是一个更适合写代码的文本编辑器。它提供一些诸如关键字

高亮，智能提示等功能帮助我们更快更好的编写代码。

•在Linux上，我建议你用gedito不过如果你手头上有现成的代码

编辑器也是可以的，但请不要使用IDEO杀鸡焉用宰牛刀，本书构建

的小小程序不会用到IDE所提供的便利，反而让你不清楚发生了什

么。

•在MacOSX上，一个可以使用的编辑器是TextWrangler,如果你

有其他喜欢的，也是可以的，但请不要使用Xcode,这种小项目使用

IDE反而会让你搞不清楚细节。

•在MicrosoftWindows上，我建议你使用Notepad++,如果你有其

他喜欢的也是可以的啦。但是请不要使用VisualStudio,因为它对

C语言的支持并不好，使用它会遇到很多问题。

编译器

编译器的作用是将我们写好的c语言的代码翻译成电脑能够直接运行的程序。

不同的操作系统安装编译器的过程也是有差别的。

另外编译和运行c程序需要知道一些基本的命令行操作，本书不会教你怎么使

用命令行。如果你从来没听说过命令行，你可以到网上搜一些教程看看。

•在Linux上，你可以通过下载并安装开发包获得C语言的编译器。

如果你的系统是Ubuntu或Debian,你可以通过这行命令来安装：s

udoapt-getinstallbuild-essential。

•在MacOSZ上，你需要在应用商店里下载并安装最新版的Xcodeo

然后在命令行中运行xcode-select-install来安装CommandLine

Tools。

•在MicrosoftWindows上，你可以下载并安装MinGW,具体的安装

及配置方法可以到网上搜几个教程看一看，这里不再细说。

测试安装好的C编译器

为了验证一下C编译器是否安装成功了，请在命令行中键入下面的语句并运行:

cc-version

如果你得到了一些关于编译器版本的信息，那就说明安装成功了！譬如，在我

的Mac上，返回信息如下所示：

$cc--versionAppleLLVMversion7.0.0(clang-700.1.76)Target:x86_64-apple-

darwinl5.0.0Threadmodel:posix

HelloWorld

至此，环境搭建工作已经完成了。现在打开你的代码编辑器，将下方的代码输

入到其中。新建一个文件夹，用于存放编写的代码。并把刚刚的代码保存到这

个文件夹中，起名为hello_world.co这就是我们的第一个C程序啦！

ttinclude<stdio.h>intmain（intargc,char**argv）{puts（，zHello,world!，z）;

return0;}

接下来我会一行一行的解释这个程序。

第一行，我们包含了一个名为Stdio.h的头文件进来。这条语句让我们可以使

用标准输入输出库所提供的函数。

接下来，我们声明一个名为main的函数，该函数接受一个int类型的输入

argc,和一个char**类型的输入argv,返回int类型的值。所有的C程

序都必须包含main函数，它是程序执行的起点。

在main函数当中调用了一个名为puts的函数（这个函数就是由stdio.h提

供给我们的哦），并传递了“Hello,world!”参数，这个函数会将传进去的He

llo,world!输出到命令行中。puts是putstring的简写形式。函数中的第

二条语句是return0;。它的作用是结束main函数并返回0值。0代表程序

正常退出，没有发生错误。

编译

在运行这个程序之前，我们首先要将它编译成可执行的程序。打开命令行，然

后跳转到hello_world.c被保存的目录。你可以通过运行以下命令来编译你的

程序：

cc-std=c99-Wallhello_world.c-ohello_world

这条语句编译了hello_world.c里面的代码，产生了一个新的可执行文件，叫

做hello_worldo-std=c99是为了告诉编译器我们使用的是哪个标准的C语言。

通过指定标准，只要我们写的程序符合标准的规范，我们的程序就可以在多个

平台上编译并运行。

如果编译成功了，你会在hello_world.c同目录下看到一个名为hello_world

的新文件。在命令行里面敲入./heUo_world,按一下回车键，就可以运行这

个程序了。会在命令行打印出Hello,world!字样。

恭喜！你成功的编译并运行了你的第一个C程序!

错误

如果你的C语言程序写的存在问题，可能会导致编译失败。这个错误可能是简

单的语法错误，也可能是其他的一些难以理解的复杂错误。

编译失败后，编译器会向你提供一些有用的错误信息，如果你看不懂，可以到

网上搜索一下。你要相信，在你之前肯定有很多人遇到了和你一样的错误。另

外，程序中可能同时存在多个错误，记得要从第一条开始解决。

而有时，程序虽然编译成功了，但是运行的时候却崩溃掉了。这就需要对程序

进行一些调试性的工作，设法找出问题所在。调试程序是进阶内容，超出了本

书的讨论范围。

文档

在本书提供的代码中，可能会遇到一些你从来没有见过的函数。如果想知道这

个函数的作用，应该去查找C语言标准库的在线文档,这个文档中介绍了C

语言中所有的标准库函数的作用及其用法。

参考

参考是用来干嘛的？

在参考部分，我通常会给出这章中用到的代码作为总览。如果你自己写的程序

遇到了错误，请不要把这里的代码简单的拷贝粘贴就完事了。一定要自己尝试

着找出错误，并解决它。

hello_world.c

ttinclude<stdio.h>intmain(intargc,char**argv){puts("Hello,world!zz);

return0;}

彩蛋

彩蛋是用来干嘛的?

在彩蛋部分，我通常会提出一些有趣的，有挑战性的问题。请尽力尝试解决它

们。你没有必要把它们全做出来，因为有些是很有难度的。

•将"Hello,world!z/改为其他的问候语。

•如果没有main函数，编译会得到什么错误？

•使用在线文档查看puts函数的用法。

第零三章•基础

这本章中，我会带你快速的浏览一遍C语言的基本特性(feature)。C语言的

特性非常少，而且语法也相当的简单明了。但是这并不代表C语言很简单，有

深度的内容绝不会浮于表面。所以，接下来我们将快速地了解一下C语言的基

础，在后面的章节中再慢慢深入。

本章的目的是让所有的读者位于同一水平线上。C的新手可以在本章多花一些

时间，而已经对C有一定程度了解的同学则可以大致浏览一遍或直接跳过本章。

程序

C语言程序是由函数定义和类型定义组成的。

因此一个源文件就是一系列的函数和类型。每个函数都可以调用其他函数或调

用自身（递归），可以使用任何已经声明的或内建的数据类型。

你还可以调用其他库提供的函数，使用库中提供的数据类型，这也是C中多层

级系统的复杂性不断增长的根源。

在前一章中，我们提到，所有的程序都是从main函数开始执行的。从main

函数开始不断地调用越来越多的函数，完成期望的工作。

变量

C中的函数可以拥有多个变量。变量其实就是一个有名字的数据项。

C中的每个变量都有一个特定的类型。这些类型可能是内建的，也可能是我们

自定义的。声明一个新变量的时候，首先需要将类型的名字写在前面，然后紧

跟的是变量的名字，你还可以使用=给这个变量赋一个初始值。变量的声明

是一个涔句，在C语言中，所有的语句必须由；结尾。

如果要创建一个名为count的整数（int）,则可以这样写：

intcount;

如果要给count赋一个初始值：

intcount=10;

下面列出了C语言中一些内建的类型:

类型名描述举例

void空类型

char单个的字符/字节charlast_initial='H';

int整数intage=32;

long可以表示更大的数的整数longage_of_universe

float浮点数floatliters_per_pint=0.568f;

double精度更高的浮点数doublespeed_of_swa11ow=0.01072896;

函数声明

函数是一个针对变量的操作过程，同时可能也会改变当前程序的状态。它接受

多个输入值，计算并返回一个输出值。

声明函数时，首先将返回值的类型写在前面，后面紧跟函数的名字，而后的一

对圆括号里面包裹函数的输入参数，参数之间用，进行分割。函数体部分紧

跟其后，包裹在一对花括号(}里，里面包含了函数执行的所有语句，语句之

间使用；分隔。return语句用来结束函数的执行，并返回一个值。

下面的代码演示了一个将两个int型变量x,y求和之后并返回的函数写法。

intaddtogether(intx,inty){intresult二x+y;returnresult;}

调用函数时，首先写上函数名，然后函数参数紧跟其后，包裹在一对圆括号里,

参数之间用逗号分开。比如说，我们调用上面的函数，并将计算结果保存到a

dded变量中：

intadded二add_together(10,18);

结构体声明

结构体用来声明一个新的类型。它可以将多个变量捆绑在一起。

我们可以使用结构体表示更加复杂的数据类型。例如，为了表示一个二维空间

里的点，我们可以创建一个名为point的结构体将两个float类型的变量x,

y绑在一起。我们可以同时使用struct和typedef来声明一个结构体：

typedefstruct{floatx;floaty;}point;

注意，我们应该将结构体放在所有用到它的函数的上方。这个类型和内建的基

本数据类型的用法没有任何区别。获取结构体内部的变量时，需要使用小数

点.，后面紧跟要获取的变量名：

pointp;p.x=0.1;p.y=10.0;floatlength=sqr.(p.x*p.x+p.y*p.y);

指针

指针类型是普通类型的变体，只需普通类型的后面添加*后缀即可。比如，i

nt*就是一个int类型的指针。在之前的main函数的输入参数列表中，我

们还见过一个char**类型，这是一个char类型的指针的指针。

指针是C语言的精髓所在，也是C语言中比较难理解的知识点，我们会在以

后的章节中详细讲解。目前的阶段我们还不会用到指针，所以你只需要知道有

这个东西就可以了。

字符串

在C语言中，字符串由char*类型表示。它是由一串字符（char）组成的，并

以一个空终结字符结尾。字符串是C语言的一个重要且复杂的部分，我们会在

接下来的几章中详细的学习它。

字符串还可以字面量来表示，将要表示的字符串包裹在双引号〃中就可以了。

比如说我们之前用过的“Hello,world!"。现在，你只需要记住，只要看到ch

ar*类型，就当成字符串来看待就可以了。

条件分支

条件分支语句可以让程序在只有条件为真的时候才去执行一段代码。

我们使用if关键字来声明条件语句，执行条件跟在后面，包裹在一对圆括号

里，后面紧跟一对花括号里面包裹着条件为真时执行的代码。if语句后面可

以跟一个else语句，包含条件为假时执行的代码。

我们可以使用或兼作寿H)和分操作■多(&&)将多个条件组合在一起。

在条件语句中，凡是不为0的结果都是真的。这点需要牢记，因为很多条件测

试语句都是以此为依据编写的。

检测x是否在10到100之间的条件语句可以这样写：

if(x>10&&x<100){puts(/zxisgreaterthan10andlessthan100!〃)；)

else{puts(/?xislessthan11orgreaterthan99!〃)；}

循环

循环可以不断的执行一段代码，直到条件变为假，或者计数完成。

在C语言中有两种类型的循环。第一种是while循环。while循环不断地执

行一段代码，直到条件为假停止。首先while关键字在前，后面紧跟包裹在一

对圆括号中的条件语句，最后是包裹在一对大括号中的待执行语句。下面是一

个例子：

inti=10;while(i>0){puts(Z/LoopIteration");i=i-1;}

第二种循环是for循环，跟while的条件语句不同的是，for循环需要三个

以；隔开的表达式：一个初始化语句，一个条件语句和一个递增语句。其中

初始化语句在循环开始之前执行；条件语句每次迭代都会判断一次，如果为假,

循环就退出了；递增语句在每次迭代的最后执行。for循环通常用来计数，因

为它的表示方法比while更加简洁。下面的例子中，我们从0递增到9,每

次加1,共执行了10次：

for(inti=0;i<10;i++){puts("LoopIteration'");}

彩蛋

使用for循环打印5次"Hello,world!”。

使用while循环打印5次"Hello,world!"。

编写一■个函数Hello,可以打印n次"Helloworld!”,然后在main

函数中调用它。

除了变量一节中列出的内建类型，还有哪些呢？

除了〉和〈，还有哪些比较操作符？

除了+和-，还有哪些算数运算符？

+=运算符是什么？它是如何工作的？

do...while循环是是什么？它是如何工作的？

switch语句是什么？它是如何工作的？

break关键字是用来干嘛的？

•continue关键字是用来干嘛的？

•typedef关键字的作用是什么？

第零四章•交互

读取-求值-输出

在编写我们的Lisp之前，我们需要寻找一种和它交互的方式。最简单的方法,

我们可以修改代码，重新编译，然后再次运行。这个方案虽然理论上可行，但

是太为繁琐。如果可以动态地和程序进行交互，我们就可以快速地测试程序在

各种条件下的行为。我们称这种模式为交互提示。

这种模式下的程序读取用户的输入，在程序内部进行处理，然后返回一些信息

给用户。这种系统也被叫做REPL,是read-evaluate-printloop（读取-求值

-输出循环）的简写。这种技术被广泛地应用在各种编程语言的解释器中，如果

你学过Python,那你一定不会陌生。

在编写一个完整的REPL之前，我们先实现一个简单的程序：读取用户的输入,

简单处理后返回给用户。在后面的章节中，我们会对这个程序不断扩展，最后

能够正确地读取并解析一个真正的Lisp程序，并将结果返回给用户。

交互提示

为了实现这个简单的想法，可以使用一个循环不断打印信息并等待用户输入。

为了获取用户输入的内容，我们可以使用stdio.h中的fgets函数。这个函

数可以一直读取直到遇到换行符为止。我们需要找个地方存储用户的输入。为

此可以声明一个固定大小的数组缓冲区。

一旦获取到用户输入的字符串，就可以使用printf将它打印到命令行中。

ttinclude<stdio.h>/*Declareabufferforuserinputofsize2048*/static

charinput[2048];intmain(intargc,char**argv){/*PrintVersionandE

xitInformation*/puts(^LispyVersion0.0.0.0.l，z);puts("PressCtrl+cto

Exit\n〃);/*Inaneverendingloop*/while(1){/*Outputourpro

mpt*/fputs(z，lispy>stdout);/*Readalineofuserinputofmaxi

mumsize2048*/fgets(input,2048,stdin);/*Echoinputbacktouse

r*/printf("Noyou'rea%s〃，input);}return0;}

代码中的/*…*/是什么？

这是C语言中的注释，是为了向其它阅读代码的人解释代码作用的。在编译的

时候，会被编译器忽略掉。

现在来深入解读一下这个程序。

staticcharinput[2048];这行代码声明了一个拥有2048个字符长度的全局数

组。这个数组中存储的数据可以在程序的任何地方获取到。我们会把用户在命

令中输入的语句保存到这里面来。static关键字标明这个数组仅在本文件中可

见。[2048]表明了数组的大小。

我们使用while⑴来构造一个无限循环，条件语句1永远都为真，所以这个

循环会一直执行下去。

我们使用fputs打印提示信息。这个函数和前面介绍过的puts函数区别是

fputs不会在末尾自动加换行符。我们使用fgets函数来获取用户在命令行中

输入的字符串。这两个函数都需要指定写入或读取的文件。在这里，我们使用

stdin和stdout作为输入和输出。这两个变量都是在〈stdio.h〉中定义的，

用来表示向命令行进行输入和输出。当我们把stdin传给fgets后，它就会

等待用户输入一串字符，并按下回车键。如果得到了字串，就会把字串连同换

行符存放到input数组中。为了不让获取到的数据太大数组装不下，我们还要

指定一下可以获取的最大长度为2048o

我们使用printf函数将处理后的信息返回给用户。printf允许我们同时打印

多个不同类型的值。它会自动对第一个字符串参数中的模式进行匹配。例如，

在上面的例子中，可以在第一个参数中看到%s字样。printf将自动把%s

替换为后面的参数中的值。s代表字符串（string）。

更多关于printf的模式种类及其用法，可以参考文档。

我怎么才能知道一些类似于fgets或printf的函数的用法？

很明显你不可能一开始就知道这些标准库函数的作用和用法，这些都需要经验。

幸运的是，C语言的标准库非常精炼。绝大多数的库函数都可以在平时的练习

中了解并学会使用。如果你想要解决的是底层的、基本的问题，关注一下参考

文档会大有裨益,因为很可能标准库中的某个函数所做的事情正是你想要的！

编译

你可以使用在第二章介绍过的命令来编译上面的程序：

cc-std=c99-Wallprompt,c-0prompt

编译通过之后，你应该试着运行并测试一下这个程序。测试完成后，可以使用

Ctrl+c快捷键来退出程序。如果一切正常，你会得到类似于下面的结果：

LispyVersion.1PressCtrl+ctoExitlispy>helloNoYou，reahello1

ispy>mynameisDanNoYou'reamynameisDanlispy>Stopbeingsorude!No

You，reaStopbeingsorude!lispy>

编辑输入

如果你用的是Mac或Linux,当你用左右箭头键编辑在程序中的输入时，你会

遇到一个奇怪的问题：

LispyVersion0.0.0.0.3PressCtrl+ctoExitlispy>hel"[[D^[[C

使用箭头键不会前后移动输入的光标，而是会产生像或.[[C这种奇怪

的字符。很明显这不是我们想要的结果。

而在Windows上则不会有这个现象。

在Mac和Linux上，我们需要用到editline库来解决这个问题。并把fput

s和fgets替换为这个库提供的相同功能的函数。

如果你用的是Windows系统，则可以直接跳到本章的最后。因为接下来的几个

小节都是和安装与配置editline相关的内容。

使用editline库

我们会用到editline库提供的两个函数：readline和add_historyoreadlin

e和fgets一样，从命令行读取一行输入，并且允许用户使用左右箭头进行

编辑。add_history可以纪录下我们之前输入过的命令，并使用上下箭头来获

取。新的程序如下所示：

ttinclude<stdio.h>#include<stdlib.h>^include<editline/readline.h>ttinclud

e<editline/history.h>intmain(intargc,char**argv){/*PrintVersion

andExitInformation*/puts(z，LispyVersion0.0.0.0.1，/);puts(，zPressCtrl+

ctoExit\n〃);/*Inaneverendingloop*/while(1){

char*input=readline(zzlispy>〃)；/*Addi

nputtohistory*/add_history(input);/*Echoinputbacktouser*/

printf(^Noyou'rea%s\n〃，input);/*Freeretrievedinput*/free(in

put);}return0;}

我们增加了一^些新的头文件。<stdlib.h>提供了free函数。<editline/readl

ine.h>和<editline/history.h>提供了editline库中的readline和add_h

istory函数。

在上面的程序中，我们使用readline读取用户输入，使用add_history将该

输入添加到历史纪录当中，最后使用printf将其加工并打印出来。

与fgets不同的是，readline并不在结尾添加换行符。所以我们在printf

函数中添加了一个换行符。另外，我们还需要使用free函数手动释放readli

ne函数返回给我们的缓冲区input。这是因为readline不同于fgets函数,

后者使用已经存在的空间，而前者会申请一块新的内存，所以需要手动释放。

内存的申请与释放问题我们会在后面的章节中深入讨论。

链接editline并编译

如果你使用前面我们提供的命令行来编译这个程序，你会得到类似于下面的错

误，因为在使用之前，你必须先在电脑上安装editline库。

fatalerror:editline/readline.h:Nosuchfileordirectory#include<editlin

e/readline.h>

在Mac上，editline包含在CommandLineTools中，安装方法我们在第二

章有说明。安装完后，可能还是会出现头文件不存在的编译错误。这时，可以

移除^include<editline/history.h>这行代码,再试一'次。

在Linux上，可以使用sudoapt-getinstalllibedit-dev来安装editlineo

在Fedora上，使用su-c〃yuminstalllibedit-dev*〃命令安装。

一旦你安装好了editline,你可以再次编译试一下。然后将会得到如下的错误:

undefinedreferenceto\readline'undefinedreferenceto'add_history，

这是因为没有将editline链接到程序中。我们需要使用-ledit标记来完成

链接，用法如下：

cc-std=c99-Wallprompt,c-ledit-oprompt

再次运行程序，就可以自由地编辑输入的文字了！

为什么我的程序还是不能编译？

在有些系统上，editline的安装、包含、链接的方式可能会有些许差别，请善

用搜索引擎哦。

预处理器

对于这样的一个小程序而言，我们针对不同的系统编写不同的代码是可以的。

但是如果我把我的代码发给一个使用不同的操作系统的朋友，让他帮我完善一

下代码，可能就会出问题了。理想情况下，我希望我的代码可以在任何操作系

统上编译并运行。这在C语言中是个很普遍的问题，叫做可移植性(portabili

ty)o这通常都是个很棘手的问题。

但是C提供了一个机制来帮助我们，叫做预处理器(preprocessor)。

预处理器也是一个程序，它在编译之前运行。它有很多作用。而我们之前就已

经悄悄地用过预处理器了。任何以井号#开头的语句都是一个预处理命令。

为了使用标准库中的函数，我们已经用它来包含(include)过头文件了。

预处理的另一个作用是检测当前的代码在哪个操作系统中运行，从而来产生平

台相关的代码。而这也正是我们做可移植性工作时所需要的。

在Windows上，我们可以伪造一■个readline和add_history函数，而在其他

系统上就使用editline库提供给我们的真正有作用的函数。

为了达到这个目的，我们需要把平台相关的代码包在#ifdef、#else和ttendif

预处理命令中。如果条件为真，包裹在ttifdef和#else之间的代码就会被执

行，否则，#else和endif之间的代码被执行。通过这个特性，我们就能写出

在Windows、Linux和Mac三大平台上都能正确编译的代码了：

ttinclude<stdio.h>ttinclude<stdlib.h>/*IfwearecompilingonWindowscomp

ilethesefunctions*/ttifdef_WIN32ttinclude<string.h>staticcharbuffer[2

048];/*Fakereadlinefunction*/char*readline(char*prompt){fputs(pro

mpt,stdout);fgets(buffer,2048,stdin);char*cpy=malloc(strlen(buffe

r)+l);strcpy(cpy,buffer);cpy[strlen(cpy)-1]='\0';returncpy;}/*

Fakeadd_historyfunction*/voidadd_history(char*unused){}/*Otherwisei

ncludetheeditlineheaders*/Seisettinclude<editline/readline.h>^include<

editline/history.h>ttendifintmain(intargc,char**argv){puts(，zLispyV

ersion0.0.0.0.1");puts("PressCtrl+ctoExit'rT);while(){

owineithercasereadlinewillbecorrectlydefined*/char*input=read

line(/zlispy>〃)；add_history(input);printf(Z/Noyou'rea%s\n/z,inpu

t);free(input);}return0;}

参考

prompt_unix.c

ttinclude<stdio.h>^include<stdlib.h>#include<editline/readline.h>tfinclud

e<editline/history.h>intmain(intargc,char**argv){/*PrintVersion

andExitInformation*/puts(Z/LispyVersion0.0.0.0.l，z);puts("PressCtrl+

ctoExit\n〃);/*Inaneverendingloop*/while(1){

char*input=readline(zzlispy>〃)；/*Addi

nputtohistory*/add_history(input);/*Echoinputbacktouser*/

printf(^Noyou，rea%s\n，z,input);/*Freeretrivedinput*/free(inp

ut);}return0;}

prompt_windows.c

ttinclude<stdio.h>/*Declareabufferforuserinputofsize2048*/static

charinput[2048];intmain(intargc,char**argv){/*PrintVersionandE

xitInformation*/puts(z，LispyVersion0.0.0.0.T');puts(，zPressCtrl+cto

Exit\n〃);/*Inaneverendingloop*/while(1){

mpt*/fputs(z/lispy>stdout);/*Readalineofuserinputofmaxi

mumsize2048*/fgets(input,2048,stdin);/*Echoinputbacktouse

r*/printf("Noyou'rea%s〃，input);}return0;}

prompt,c

^include<stdio.h>ttinclude<stdlib.h>/*IfwearecompilingonWindowscomp

ilethesefunctions*/ttifdef_WIN32ttinclude<string.h>staticcharbuffer[2

048];/*Fakereadlinefunction*/char*readline(char*prompt){fputs(pro

mpt,stdout);fgets(buffer,2048,stdin);char*cpy=malloc(strlen(buffe

r)+l);strcpy(cpy,buffer);cpy[strlen(cpy)-1]='\0';returncpy;}/*

Fakeadd_historyfunction*/voidadd_history(char*unused){}/*Otherwisei

ncludetheeditlineheaders*/Seisettinclude<editline/readline.h>^include<

editline/history.h>ttendifintmain(intargc,char**argv){puts(，zLispyV

ersion0.0.0.0.1");puts("PressCtrl+ctoExit'rT);while(){

owineithercasereadlinewillbecorrectlydefined*/char*input=read

line(/zlispy>〃)；add_history(input);printf(Z/Noyou'rea%s\n/z,inpu

t);free(input);}return0;}

彩蛋

•将提示信息lispy〉换成其他你喜欢的。

•修改打印的信息。

・在程序开头的提示信息中添加一些其他的信息。

•在字符串中，\n表示什么？

•printf还有哪些输出模式？

•如果你向printf传递一个与模式不匹配的值会怎样？

•预处理器ttifndef有什么用？

•预处理器^define有什么用？

•_WIN32在Windows中有定义，那在Linux和Mac中定义了什么呢？

第零五章•编程语言

什么是编程语言？

编程语言和自然语言非常相似，也有它背后固有的结构和规则来界定语句的正

确性。当我们读写自然语言时，语言的规则就在无意中学会了。学习编程语言

也是一样，需要长久的读写练习才能掌握。一旦掌握，我们就可以利用这些规

则去理解其他人的代码，并写出自己的代码。

在19世纪50年代，语言学家NoamChomsky定义了一系列关于语言的重要

理论。这些理论支撑了我们今天对于语言结构的基本理解。其中重要的一条结

论就是：自然语言都是建立在递归和重复的子结构之上的。

举例来说：

Thecatwalkedonthecarpet.

根据英语的规则，名词cat可以被两个由and连接的名词代替：

Thecatanddogwalkedonthecarpet.

我们可以像之前一样再次使用这个规则，将cat替换为两个使用and符号连

接的新名词。我们还可以使用另外一个规则，将一个名词替换为一个形容词加

一个名词，其中形容词作为对名词的修饰：

Thecatandmouseanddogwalkedonthecarpet.

Thewhitecatandblackdogwalkedonthecarpet.

以上，我们只是简单的举两个例子。英语的语法规则远不止于此，汉语的语法

规则就更复杂了，呵呵。

我们注意到，在编程语言中也有相似的规则。在C语言中，if语句可以包含

多条的新语句，新语句当然也可以是另一个if语句。这些递归和重复的规则

在语言的其他部分也同样是适用的。

if(x>5){returnx;}

if(x>5){if(x>10){returnx;}}

Chomsky提出的理论是非常重要的。它意味着，虽然一门语言可以表达无限的

内容，我们仍然可以使用有限的规则去解析所有用该门语言写就的东西。这些

有限的规则就叫语法(grammar)o

对于语法，我们有多种表达方式。最容易想到的方式就是使用白话文。譬如，

我们可以这样说：“句子必须是动词短语〃、”动词词组可以是动词,也可以是副

词加动词”等等(译注：事实上，这也是我们最初学习英语语法的主要方式)。

这种形式对于人类来说是非常容易理解的，但是对于计算机却太模糊的、难以

理解的。所以在写程序时，我们需要对语法有一个更标准化的描述。

为了定义一门编程语言(例如我们将要编写的Lisp),我们首先需要能够正确解

析用户按照语法规则写就的程序。为此需要编写一个涔法解断器，用来判断用

户的输入是否合法，并产生解析后的内部表示。内部表示是一种计算机更容易

理解的表示形式，有了它，我们后面的解析、求值等工作会变得更加的简单可

行。

但是这一部分往往是枯燥繁琐的体力活，我们显然不希望在这上面浪费时间。

所以我们就采用了一个叫做mpc的库来帮助我们完成工作。

解析器组合子

mpc是我(原作者)编写的一个解析器组合子(ParserCombinators)库。这意味

着，你可以使用这个库为任何语言编写语法解析器。编写语法解析器的方法有

很多，使用解析器组合子的好处就在于，它极大地简化了原本枯燥无聊的工作,

而仅仅编写高层的抽象语法规则就可以了。

编写语法规则

下面我们来编写一个柴犬语(匹胆)的语法解析器以便熟悉mpc的用法。

先来看一下Doge语言的语法描述：

•形容词(Adjective)包括wow>many>so、such符号。

•名词(Noun)包括lisp>language>c、book>build符号。

•短语(Phrase)由形容词(Adjective)后接名词(Noun)组成。

•Doge语言由0到多个短语(Phrase)组成。

现在我们尝试定义一下形容词和名词，为此我们创建两个解析器，类型是mpc_

parser_t*,然后将解析器存储在Adjective和Noun两个变量中。mpc_or函

数产生一个解析器，它可接受的语句必须是指定语句中的一个。而mpc_sym将

字符串转化为一个语句。

下面的代码也正如我们上面的描述一样：

/*Buildaparser'Adjective'torecognizedescriptions*/mpc_parser_t*Adjec

tive=mpc_or(!,mpc_sym(z/wow，z),mpc_sym(z，manyz/),mpc_syin(〃so〃)，mpc_sym

("such"));/*Buildaparser'Noun'torecognizethings*/mpcparsert*Nou

n=mpc_or(5,mpc_syni(〃lisp〃)，mpc_sym(z，language/z),mpc_sym(/zbookz/),mpc_sy

m(〃build〃)，mpc_sym(〃c〃));

我怎样才能使用上面的这些mpc库提供的函数？

现在先不用担心编译和运行程序的事情，先确保理解背后的理论知识。在下一

章中我们将使用使用mpc实现一个更加接近我们的Lisp的语言。

接下来，我们使用已经定义好的解析器Adjective、Noun来定义短语(Phras

e)解析器。mpc_and函数返回的解析器可接受的语句必须是各个语句按照顺序

出现。所以我们将先前定义的Adjective和Noun传递给它，表示形容词后面

紧跟名词组成短语。mpcf_strfold和free指定了各个语句的组织及删除方式,

我们可以暂时忽略它们。

mpcparsert*Phrase二mpc_and(2,mpcf_strfold,Adjective,Noun,free);

Doge语言是由0到多个短语(Phrase)组成的。mpc_many函数表达的正是这

种逻辑关系。同样的，我们可以暂时忽略mpcf_strfold参数。

mpc_parser_t*Doge二mpc_many(mpcf_strfold,Phrase);

上述语句表明Doge可以接受任意多条语句。这也意味着Doge语言是无穷的。

下面列出了一些符合Doge语法的例子：

〃wowbooksuchlanguagemanylisp"〃socsuchbuildsuchlanguage""manybuild

wowc〃〃〃〃wowlispwowcmanylanguage”〃soc〃

我们可以继续使用mpc提供的其他函数，一步一步地编写能解析更加复杂的语

法的解析器。相应地，随着复杂度的增加，代码的可读性也会越来越差。所以,

这种写法其实并不简单。mpc还提供了一系列的帮助函数来帮助用户更加简单

地完成常见的任务，具体的文档说明可以参见项目主页。使用这些函数能够更

好更快地构建复杂语言的解析器，并能够提供更加精细地控制。

更加自然的语法规则

mpc允许我们使用一种更加自然的方式来编写语法规则。我们可以将整个语言

的语法规则写在一个长字符串中，而不是使用啰嗦难懂的C语句。我们也不再

需要关心如何使用mpcf_strfold或是free参数组织或删除各个语句。所有

的这些工作都是都是自动完成的。

下面，我们使用这个方法重新编写了上面实现过的Doge语言：

mpc_parser_t*Adjective=mpc_new(zzadjective，/);mpc_parser_t*Noun=mpc_

new("noun");mpc_parser_t*Phrase=mpc_new("phrase");mpc_parser_t*Doge

二mpc_new(，zdoge，z);mpca_lang(MPCALANGDEFAULT,

\adjective:\〃wow\〃|\〃many\〃\|\〃so\〃|\〃

such\〃；\noun:\〃lisp\〃|\，zlanguage\，z\

|\〃book\〃|\〃build\〃|\〃c\〃；\phrase:<adjective><noun>;

\doge:〈phrase〉*;\〃，Adjective,Noun,Phra

se,Doge);/*Dosomeparsinghere...*/mpc_cleanup(4,Adjective,Noun,Phr

ase,Doge);

即使你现在暂时不理解上面的长字符串的语法规则，也能明显地感觉到这个方

法要比之前的清晰的多。下面就来具体的学习一下其中的某些特殊符号的意义

及用法。

注意到，现在定义一个语法规则分为两个步骤：

1.使用mpc_new函数定义语法规则的名字。

2.使用mpca」ang函数具体定义这些语法规则。

mpca.lang函数的第一个参数是操作标记，在这里我们使用默认选项。第二个

参数是C语言的一个长字符串。这个字符串中定义了具体的语法。它包含一系

列的递归规则。每个规则分为两部分，用冒号：隔开，冒号左边是规则的名

字，右边是规则的定义，使用；表示规则结束。

定义语法规则的一些特殊符号的作用如下：

语法表示作用

〃1〃

ab要求字符串ab

，，

a要求字符a

ab要求先有一个字符a,后面紧跟一个字符b

'a'1'b'要求有字符a或字符b

'a，*要求有0个或多个字符a

'a'+要求有1个或多个字符a

<abba>要求满足名为abba定义的语法规则

似曾相识的感觉?

上面的一些语法规则有没有似曾相识的感觉？你没有猜错，mpca_lang函数就

是用mpc_many>mpc_and、mpc_or这些函数来实现的，干净利落，不拖泥带

水。

根据表中给出的规则尝试着理解一下上面的代码，看看是不是等价于之前我们

前面用代码定义过的语法解析器？

在后面的章节中，我们会使用这个方法来定义我们的语法规则。刚开始可能并

不是那么容易理解，但随着时间的推移，我们练习的越来越多，你也将会更加

熟悉，并将知道如何创建和编辑自己的语法规则。

本章更加注重的是理论知识，所以在做彩蛋部分时，不要太在意正确性，思考

实现的方式才是最重要的。

参考

doge_code.c

ttinclude〃mpc.h〃intmain(intargc,char**argv){/*Buildaparser'Adje

ctive，torecognizedescriptions*/mpc_parser_t*Adjective=mpc_or(4,

mpc_sym