《自制编程语言 基于C语言》

编辑推荐

前百度高级工程师、专业书《操作系统真相还原》的作者的又一力作

业界专家联名推荐

滴滴系统部技术高级总监于晓声

阿里巴巴蚂蚁金服技术专家肖金亮

百度资深运维工程师陈晓聪

360企业安全集团政企云事业部技术总监冯顾

ACFUN高级运维总监陆景玉

Mobvista运维总监黄梦溪

手把手地教读者从零去实现一门语言，从原理到实践事无巨细

每一步都有实际的代码和详尽的原理说明，读者可以很轻松地掌握各个实现细节

实现脚本语言重要的垃圾回收（GC）、虚拟机（VM）和线程等黑技术都在《自制编程语言 基于C语言》一一呈现

内容简介

《自制编程语言 基于C语言》是一本专门介绍自制编程语言的图书，书中深入浅出地讲述了如何开发一门编程语言，以及运行这门编程语言的虚拟机。《自制编程语言 基于C语言》主要内容包括：脚本语言的功能、词法分析器、类、对象、原生方法、自上而下算符优先、语法分析、语义分析、虚拟机、内建类、垃圾回收、命令行及调试等技术。

《自制编程语言 基于C语言》适合程序员阅读，也适合对编程语言原理感兴趣的计算机从业人员学习。

作者简介

郑钢，网名大刚，毕业于北京大学，前百度运维开发工程师，《操作系统真象还原》作者。

爱父母，爱老婆，爱运动，爱钻研。

精彩书评

《自制编程语言 基于C语言》详细阐述了设计编程语言所需的基本理论，并且以作者自己开发设计的sparrow编程语言为例，引导读者一步一步地实现一门完善的编程语言，《自制编程语言 基于C语言》还讲解了大量的基础类以及垃圾内存回收功能，切实帮助读者从理论过渡到实践，再走向实用。

—肖金亮，阿里蚂蚁金服技术专家

日常有些运维、开发的工作之所以难以开展，很多时候就受限于对底层技术的不了解，《自制编程语言 基于C语言》从独立开发一门编程语言和虚拟机的实践入手，对相关知识进行了阐述，讲解很清楚，实现的技术很值得称赞。

—陈晓聪，百度资深运维工程师

回顾计算机技术发展的这几十年，编程语言层出不穷，语言特性愈发抽象，语言使用则愈发简洁，底层机制隐藏得也越来越深。这种情况下，程序员想深入理解编程语言原理愈发困难，需要花费大量精力去学习艰深的语言设计理论并深入阅读语言实现的源码，但往往事倍功半，收效甚微。《自制编程语言 基于C语言》另辟蹊径，带领读者从零开始自己动手实现一个编程语言及其运行环境，循序渐进，在实践过程中透彻理解编程语言的来龙去脉。

—冯顾，360企业安全集团政企云事业部技术总监

在云与人工智能时代的大背景下，软件从业者都有必要去了解一下虚拟机与一门编程语言。通过对这部分知识的了解能够对操作系统和语言编程有更深刻的理解。市场上介绍编程语言和操作系统入门的书籍不多，而《自制编程语言 基于C语言》是一本较好的读物，很值得读者学习。

—陆景玉，ACFUN高级运维总监

自制编程语言和虚拟机，这是一个看似很深奥的课题，也涉及当今互联网流行的两大主题，许多技术人员对其心驰神往，但要领悟其精髓步履维艰。《自制编程语言 基于C语言》循序渐进、由浅到深地讲解了丰富的基础知识，不但覆盖了常见的编译原理入门，更难能可贵的是，作者讲解的知识覆盖了其独特的理解和视角，相信《自制编程语言 基于C语言》能让读者能够受益匪浅。

—黄梦溪，Mobvista运维总监

目录

第0章　一些可能令人迷惑的问题　1

0.0　成功的基石不是坚持，而是“不放弃”　1

0.1　你懂编程语言的“心”吗　2

0.2　编程语言的来历　2

0.3　语言一定要用更底层的语言来编写吗　2

0.4　编译型程序和脚本程序的异同　8

0.5　脚本语言的分类　10

0.6　为什么CPU要用数字而不是字符串作为指令　11

0.7　为什么脚本语言比编译型语言慢　11

0.8　既然脚本语言比较慢，为什么大家还要用　12

0.9　什么是中间代码　12

0.10　什么是编译器的前端、后端　13

0.11　词法分析、语法分析、语义分析和生成代码并不是串行执行　13

0.12　什么是符号表　14

0.13　什么是关系中的闭包　14

0.14　什么是程序中的闭包　15

0.15　什么是字母表　16

0.16　什么是语言　17

0.17　正规式就是正则表达式　17

0.18　什么是正规（表达）式和正规集　17

0.19　什么是有穷自动机　18

0.20　有穷自动机与词法分析的关系　19

0.21　词法分析用有穷自动机（有穷状态自动机）的弊端　19

0.22　什么是文法　20

0.23　BNF和EBNF，非终结符和终结符，开始符号及产生式　21

0.24　什么是句型、句子、短语　23

0.25　什么是语法分析　24

0.26　语法分析中的推导和归约为什么都要最“左”　25

0.27　什么是语义分析　26

0.28　什么是语法制导　27

0.29　词法分析器吃的是lex，挤出来的是token　27

0.30　什么是“遍”　28

0.31　文法为什么可以变换　28

0.32　为什么消除左递归和提取左因子　28

0.33　FIRST集、FOLLOW集、LL(1)文法　29

0.34　最右推导、最左归约、句柄　31

0.35　算符优先分析法　32

0.36　算符优先文法　33

0.37　非终结符中常常定义的因子和项是什么　33

0.38　什么是抽象语法树　33

0.39　编译器如何使用或实现文法中的产生式　34

0.40　程序计数器pc与ip的区别　35

第　1章设计一种面向对象脚本语言　36

1.1　脚本语言的功能　36

1.2　关键字　37

1.3　脚本的执行方式　38

1.4　“纯手工”的开发环境　38

1.5　定义sparrow语言的文法　38

第２章　实现词法分析器　46

2.1　柔性数组　46

2.2　什么是字节序　47

2.3　一些基础的数据结构（本节源码stepByStep/c2/a）　48

2.4　定义虚拟机结构（本节源码stepByStep/c2/b）　56

2.5　实现源码读取（本节源码stepByStep/c2/c）　57

2.6　unicode与UTF-8　59

2.6.1　什么是unicode　59

2.6.2　什么是UTF-8　59

2.6.3　UTF-8编码规则　60

2.6.4　实现UTF-8编码、解码（本节源码stepByStep/c2/d）　61

2.7　实现词法分析器parser（本节源码stepByStep/c2/e）　66

2.7.1　lex和token　66

2.7.2　字符串和字符串内嵌表达式　66

2.7.3　单词识别流程　67

2.7.4　定义token和parser　68

2.7.5　解析关键字及获取字符　71

2.7.6　解析标识符和unicode码点　73

2.7.7　解析字符串、内嵌表达式、转义字符　75

2.7.8　跳过注释和空行　77

2.7.9　获取token　79

2.7.10　token匹配和初始化parser　84

2.8　构建主程序（本节源码stepByStep/c2/f）　85

2.9　编译、测试（本节源码stepByStep/c2/f）　88

2.9.1　一个简单的makefile　88

2.9.2　测试paser　92

第3章　类与对象　95

3.1　对象在C语言中的概貌　95

3.2　实现对象头（本节源码stepByStep/c3/a）　96

3.3　实现class定义（本节源码stepByStep/c3/a）　99

3.4　实现字符串对象（本节源码stepByStep/c3/a）　101

3.5　模块对象和实例对象（本节源码stepByStep/c3/a）　103

3.6　upvalue、openUpvalue和closedUpvalue　106

3.7　实现函数对象、闭包对象与调用框架（本节源码stepByStep/c3/a）　107

3.8　完善词法分析器之数字解析（本节源码stepByStep/c3/b）　111

3.9　完善词法分析器之字符串解析和获取token（本节源码stepByStep/c3/b）　114

3.10　最终版词法分析器的功能验证（本节源码stepByStep/c3/b）　116

3.11　实现list列表对象（本节源码stepByStep/c3/c）　118

3.12　range对象（本节源码stepByStep/c3/c）　121

3.13　迟到的class.c（本节源码stepByStep/c3/c）　122

3.14　map对象（本节源码stepByStep/c3/c）　124

3.14.1　哈希表　124

3.14.2　map对象头文件及entry　125

3.14.3　冲突探测链与伪删除　126

3.14.4　map对象的实现　128

3.15　线程对象（本节源码stepByStep/c3/c）　134

3.15.1　线程、协程浅述　134

3.15.2　运行时栈　137

3.15.3　用户线程的实现　138

第4章　原生方法及基础实现　142

4.1　解释器流程（本节源码stepBystep/c4/a）　142

4.2　符号表　144

4.2.1　模块的符号表　144

4.2.2　类方法的符号表　144

4.2.3　模块变量符号表　146

4.2.4　局部变量符号表　147

4.2.5　常量符号表　147

4.3　方法在运行时栈中的参数　147

4.4　定义模块变量（本节源码stepByStep/c4/b）　148

4.5　原生方法（本节源码stepByStep/c4/b）　154

4.5.1　定义裸类　154

4.5.2　定义返回值与方法绑定的宏　155

4.5.3　定义原生方法　157

4.5.4　符号表操作　159

4.5.5　定义类、绑定方法、绑定基类　160

4.6　元类及实现（本节源码stepByStep/c4/b）　161

4.6.1　meta-class类、class类、object类　161

4.6.2　创建元类，绑定类方法　163

4.7　加载模块（本节源码stepByStep/c4/c）　164

4.8　虚拟机简介　166

4.8.1　虚拟机分类及优缺点　166

4.8.2　为什么要采用虚拟机　168

4.8.3　虚拟机的简单优化　170

4.9　字节码　171

第5章　自上而下算符优先——TDOP　177

5.1　自上而下算符优先—TDOP　177

5.2　来自DouglasCrockford的教程　177

5.3　TDOP原理　194

5.3.1　一些概念　194

5.3.2　一个小例子　196

5.3.3　expression的思想　197

5.3.4　while（rbp

5.3.5　进入expression时当前token的类别　201

5.3.6　TDOP总结　202

第6章　实现语法分析与语义分析　204

6.1　定义指令（本节源码stepByStep/c6/a）　204

6.2　核心脚本（本节源码stepByStep/c6/a）　206

6.3　写入指令（本节源码stepByStep/c6/a）　212

6.4　编译模块（本节源码stepByStep/c6/a）　216

6.5　语义分析的本质　218

6.6　注册编译函数（本节源码stepByStep/c6/b）　218

6.7　赋值运算的条件　221

6.8　实现expression及其周边（本节源码stepByStep/c6/c）　223

6.9　局部变量作用域管理　228

6.10　变量声明、中缀、前缀及混合运算符方法签名（本节源码stepByStep/c6/d）　229

6.11　解析标识符（本节源码stepByStep/c6/e）　233

6.11.1　处理参数列表及相关　233

6.11.2　实现运算符和标识符的签名函数　235

6.11.3　upvalue的查找与添加　239

6.11.4　变量的加载与存储　242

6.11.5　编译代码块及结束编译单元　243

6.11.6　各种方法调用　246

6.11.7　标识符的编译　249

6.12　编译内嵌表达式（本节源码stepByStep/c6/f）　256

6.13　编译bool及null（本节源码stepByStep/c6/g）　258

6.14　this、继承、基类（本节源码stepByStep/c6/h）　259

6.15　编译小括号、中括号及list列表字面量（本节源码stepByStep/c6/i）　260

6.16　编译方法调用和map字面量（本节源码stepByStep/c6/j）　263

6.17　编译数学运算符（本节源码stepByStep/c6/k）　266

6.18　编译变量定义（本节源码stepByStep/c6/l）　270

6.19　编译语句　274

6.19.1　编译if语句（本节源码stepByStep/c6/m）　274

6.19.2　编译while语句（本节源码stepByStep/c6/n）　275

6.19.3　编译return、break和continue语句（本节源码stepByStep/c6/o）　280

6.19.4　编译for循环语句（本节源码stepByStep/c6/p）　284

6.19.5　编译代码块及单一语句（本节源码stepByStep/c6/q）　288

6.20　编译类定义（本节源码stepByStep/c6/r）　289

6.20.1　方法的声明与定义　289

6.20.2　构造函数与创建对象　291

6.20.3　编译方法　293

6.20.4　编译类定义　296

6.21　编译函数定义（本节源码stepByStep/c6/s）　298

6.22　编译模块导入（本节源码stepByStep/c6/t）　300

第7章　虚拟机　306

7.1　创建类与堆栈框架（本节源码stepByStep/c7/a）　306

7.2　upvalue的创建与关闭（本节源码stepByStep/c7/b）　309

7.3　修正操作数（本节源码stepByStep/c7/c）　312

7.4　执行指令（本节源码stepByStep/c7/d）　314

7.4.1　一些基础工作　314

7.4.2　解码、译码、执行（本节源码stepByStep/c7/d）　316

7.5　运行虚拟机（本节源码stepByStep/c7/e）　334

第8章　内建类及其方法　337

8.1　Bool类及其方法（本节源码stepByStep/c8/a）　337

8.2　线程类及其方法（本节源码stepByStep/c8/b）　338

8.3　函数类及其方法和函数调用重载（本节源码stepByStep/c8/c）　345

8.4　Null类及其方法（本节源码stepByStep/c8/d）　347

8.5　Num类及其方法（本节源码stepByStep/c8/e）　348

8.6　String类及其方法（本节源码stepByStep/c8/f）　355

8.7　List类及其方法（本节源码stepByStep/c8/g）　369

8.8　Map类及其方法（本节源码stepByStep/c8/h）　374

8.9　range类及其方法（本节源码stepByStep/c8/i）　380

8.10　System类及其方法（本节源码stepByStep/c8/j）　383

8.11　收尾与测试（本节源码stepByStep/c8/k）　388

第9章　垃圾回收　393

9.1　垃圾回收浅述　393

9.2　理论基础　395

9.3　标记—清扫回收算法　396

9.4　一些基础结构（本节源码stepByStep/c9/a）　397

9.5　实现GC（本节源码stepByStep/c9/a）　400

9.6　添加临时根对象与触发GC　411

第　10章命令行及调试　415

10.1　释放虚拟机（本节源码stepByStep/c10/a）　415

10.2　简单的命令行界面（本节源码stepByStep/c10/a）　415

10.3　调试（本节源码stepByStep/c10/b）　417

前言/序言

推荐序

很高兴能成为《自制编程语言 基于C语言》的首批读者，也很高兴能为《自制编程语言 基于C语言》写推荐序。

刚拿到《自制编程语言 基于C语言》手稿时，从书名上我意识到这是对我胃口的书。果然，整书阅对以后，收获颇多。如今程序员的开发成本已经很低了，项目中有各种成熟的框架和库可供选择和使用，但还有人能静下心来研究编译器这么底层的技术，实属难得。《自制编程语言 基于C语言》犹如一把火炬，点燃了技术人内心对开发的热情。

依稀记得2010年年初在百度与郑刚初次见面的情景，那时他工作之余的时间基本都用在向各个技术专家请教、讨论各类技术问题上，他是我带过的人中最勤奋的人之一。时间荏苒，一分耕耘一分收获，看到他今天的成长，尤感欣慰。

《自制编程语言 基于C语言》讲述了一门脚本语言（sparrow）的开发过程，这是一本“步步为营”式的书籍，延续了他编写《操作系统真象还原》的风格，手把手地教读者从零实现一门语言，从原理到实践每一步都有实际的代码和详尽的原理说明，通过运行书中各小节中的代码，读者可以很轻松地掌握各个细节，因此《自制编程语言 基于C语言》的学习曲线并不陡峭，甚至很平坦。另外，值得欣喜的是，《自制编程语言 基于C语言》所编写的脚本语言并不是用Java、C++等入门难度略大的语言实现的，而是用C语言，这是我们学习编程的基础语言。也就是说，《自制编程语言 基于C语言》并不需要专业的开发经验即可上手学习。另外，在实现过程中并未用到复杂的库函数或系统调用，可以负责地说，《自制编程语言 基于C语言》已经将学习成本降到最低。

C语言是一种面向过程的语言，如何用一种面向过程的语言去实现一种面向对象的语言很有意思。另外，PHP和Perl语言虽然也实现了类，但它们其实是一种面向过程的语言，并不是纯粹的面向对象语言，而sparrow语言是一种纯粹的面向对象语言，它在设计之初就采用对象的方式来处理脚本语言中类的成员和方法，这仿佛让我们看到了面向对象编程语言的基因。众所周知，当今最流行的脚本语言应属Python，Python也是用C语言实现的，也许你很好奇Python的内部原理，但是想到它将近有4万行的源代码时，也许甚至不想看它的源程序了。那么研读《自制编程语言 基于C语言》中的sparrow语言会是一种更好的选择，其源码不足7100行，阅读过程轻松愉快，但可以学到系Python这种语言的实现原理。

对于脚本语言来说，两个重要方面就是垃圾回收和运行环境。垃圾回收就是我们平时所说的GC（GarbageCollection）。有了GC，程序员不需要手工释放所分配的对象，可以使精力专注于业务逻辑而不用担心内存泄漏问题。在sparrow语言中同样实现了GC，通过此部分代码你可以看到GC的原理，以及哪些对象才能被回收。运行时环境就是脚本语言中的虚拟机，即VM（如Java语言的JVM也是一种VM）。脚本语言是通过虚拟机才能运行的，如何把编译器生成的操作码转换为实际的代码行为，这里面的工作对大多数人来说很神秘。相信各位在源码中一探究竟之后会发现：GC和VM这两个神秘的黑盒子不过如此。另外，也许程序员最感兴趣的就是线程，关于线程在用户态下是如何实现的、线程如何实现调度，《自制编程语言 基于C语言》将告诉你答案。总之，但凡涉猎，开卷有益。

每个程序员都有实现属于自己编程语言的梦想，说其是梦想，原因是实现的难度很大......这种情况一直持续到《自制编程语言 基于C语言》的出现。《自制编程语言 基于C语言》讲的是纯粹的技术“干货”，符合郑刚一贯的写作风格，这是他静心写出来的东西，内容满满，很值得阅读。

于晓声

滴滴系统部技术高级总监