Notes

这里记录一下我阅读《编程语言实现模式》这本书的一些感受。一开始，对于编译原理，我的印象是这门课非常的艰深。在正式学习之前其实我已经看了很多编译相关的东西，比如V8，以及前端模板引擎等等。当时的感觉就是十分神奇。上了课之后首先接触的是形式文法、自动机和正规表达式等等。我的感觉就是，这些东西，是如何被前端大神们运用来写相关框架的呢，完全看不出门路嘛！ Jame Kyle的分享—《How to write a compiler》虽然很好，但是和有实际运用价值的编译技能还差的远呢。 看龙书看的欲哭无泪，后来转而看《自制编程语言》，把crowbar的代码和流程大概了解了一下。最大的收获就是了解了yacc和lex。此前我对于Lexer和Parser还是抱有一定的恐惧心理的。 最终让我认清门路的是戴嘉华的这篇博客。后来我去翻了翻编译原理课本，让我彻底搞清楚几个事情： 第一点，虽然波神说的很对，最关键的是动手去写，但了解必要的理论是很重要的。问题就在于，编译这边理论很多，类似有限自动机和正规表达式的转换等等知识，后端代码生成和优化等等，会加重认知的负担。所以关键就是，对于一个普通的工程师来说，开发文本处理或者DSL相关程序需要掌握的编译原理知识是哪些。 第二点，需要了解的概念有： 主流编译器，解释器的流水线 形式文法（EBNF） LL(1)文法，以及EBNF和LL(1)之间的转换 根据LL(1)文法写递归下降Parser 了解不同的AST类型，会设计AST 第二章&&第三章 这章主要讲基于LL(1)的Tokenizing和Parsing。 很妙的一点在于，在写关于形式文法的地方，这本书没有将BNF和乔姆斯基之类的科班教材中讲的，而是讲文法当成是一种DSL，这其实是非常正确的。Parser Generator的输入一般就是某种类似BNF的DSL。本书中的例子是ANTLR（一个parser generator）的DSL。 这种务实的风格是延续在整个第二章中的，讲LL(1)的First和Follow集的时候，是这样说的： 正规的定义中通常使用FIRST和FOLLOW两个运算来计算向前看集合，而实际使用时，这个问题可以等价于“哪些词法单元可能会出现在这个解析选项的开头”，这种思维方式更容易掌握，FIRST和严格定义就不在这里解释了，因为它比较复杂，而且这里也用不着其原理。如果有兴趣，可以在网上找到很多相关材料。 First集合的数学定义是这样的： 试想一下，如果初学者接触到的是严谨的数学定义，而不是一个相对直白的解释和代码演示的话，还是会有不少人打退堂鼓的。 在实际的学习中，还是需要一些如上文中的“等价于”那样的解释。 LL(1)的parser是最简单的。也是其余递归下降模式的基础框架。实现的方式就是为每一个规则写一个对应的函数，函数里按First集合来编写，规则里的运算符都可以转化为if或者while等到逻辑，如果是终结符就match，如果是非终结符就递归调用对应规则的函数。 我看了Regularjs中parser的代码以及上文中vdom模板引擎的代码，结合书中的例子，大概搞懂了，接下来可以把书中的例子用js写一遍试试。 第二章最后讲了LL(k)类型的parser。LL(k)就是任意k个token的lookup。LL(k)的需求，拿mcss来说，就是： mcss有点特殊，是个LL(n)的解释器，比如在设计中，函数在mcss是 First-class的，可以被返回或传入函数，并保持作用域信息，所以它是一种特殊的值，定义我设计与一般赋值一样。 $size = ($width, $height) { // … } >这里当你不读取到`{ ` 是无法判断 `=` 后面是函数定义 还是 普通css中的 compound >values . 众所周知参数列表可能无限长，所以必须是LL(n)的Parser才能够解答。 有些语言语法里有很相似的语言结构，它们只在最后边才有区别。比如C++的函数定义和函数声明的前面都是一样的，直到;或{才能加以区别。 所以想要能够写DSL解释器的话，LL(k)式的模式也是要懂的。LL(k)的问题就是要要预parse，如果条件满足，再真正parse一遍。这样带来的问题就是运行效率上比较慢。解决的办法是**回溯法**，通过类似动态规划的空间换时间的方法，缓存parse的结果，加速parse的过程。 ### 第四章 Vue的AST。

《编码》这本书被列了入我们团队技术方向培养方案的必读书目，可见这本书的地位。因此，我觉得有必要来撰写一篇导读，来帮助大家看透一些问题，把这本书上的知识和课本中的知识对应起来，并且形成一个体系。 《编码》讲的是什么呢？笼统的说，就是用自底向上的角度一层层的解析计算机的原理。比如第一章到第三章将的是编码的本质——信息和符号的对应。第四章到第六章讲的是电信号可以用来表示一种编码，从而传递信息。第七章到第九章介绍了二进制，也就是计算机系统中最基本的编码形式。第十章：逻辑与开关和第十一章：门，介绍了布尔代数，以及如何使用门电路进行布尔代数的运算。第十二章和第十三章介绍了二进制加法器和减法器，加法器已然是现代CPU中运算单元的雏形了。第十四章介绍的反馈与触发器是实现计算机中储存芯片的基础。第十五章字节与十六进制是为理解后续的存储器数据格式而准备的。第十六章讲了存储器的组织，这便是现代计算机系统中存储系统的原理。第十七章，是全书最难的一章，讲了如何制作一个CPU。CPU本质上就是一个可以编程的运算器。第十八章介绍了从算盘到机械结构到电子管再到晶体管的技术革命，晶体管、超大规模集成电路使得现代CPU的出现成为了可能。第十九章介绍了Intel 8080CPU的指令集。第二十章介绍了字符的存储格式，这可以帮助你理解计算机是如何存储文本的。第二十一章：总线，介绍了计算机系统中CPU、内存和I/O设备如何通信。第二十二章是一个简短的操作系统简史，注意到从这里我们涉及了软件层面的内容。第二十三章定点数和浮点数比较独立，主要讲了计算机是如何存储浮点数的。第二十四章和第二十五章则介绍了编程语言和图形学基础。 我们可以清晰的看到从硬件到软件，从具体到抽象，从底层到顶层的一个脉络。 这本书其实包含了我们计算机专业中《数字逻辑》、《计算机组成原理》、《微机系统与接口原理》三门课的主干内容。作者没有试图灌输大量的理论知识，而是试图将这些知识串联起来，包括最后的操作系统和编程语言，其实和计算机硬件是有着不可分割的关系的。在《编码》这本书中你就可以很自然的在章节的推进中体会到这种联系。 下面我会对一些章节进行详细的解读。主要是解释难点，拓展一些知识，并且写清这一章节的知识对应我们的哪门专业课，而专业课和这本书的要求有何不同等等。 我希望这本书可以让大家看清计算机的本质，计算机的本质其实就是一个处理信息的机器。你输入数据，计算机输出数据。首先我们需要一套编码系统来表示这些数据，而二进制的编码正好与半导体的性质相吻合，我们可以用布尔代数来对现实问题进行建模，通过门电路来表示这个布尔代数，从而制造出可以进行某种运算的电路。而如果这个电路可编程，再加上输入输出接口，那就是一个CPU了。至于是半导体和二进制之间孰先孰后呢，你可以做进一步的研究（从书中来看，第一台计算机ENIAC是采用十进制的，所以看来应该是半导体在先，二进制在后）（所以今后如果计算机的物理介质有了更新，我们也许就会换一种新的编码方案了）。 在书中大量讲到的门电路、继电器等等属于实现层面，大家了解一下就好。我们不是电气工程师，我们是软件工程师。当然理解硬件层面细节对于写好代码是很有帮助的。这主要解释的是一个“为什么”的问题。 你了解了CPU的指令集，和CPU的工作方式，你就理解为什么我们在程序运行时需要“栈”这个数据结构。 你了解了字符的编码以及浮点数的编码，你就不会奇怪于为什么0.1+0.2不等于0.3。 我们要关注的主要是如何用编码来抽象问题。比如用二进制来表示数据，进行运算。比如用指令来对CPU进行编程。比如 第一章：至亲密友、第二章：编码与组合和第三章：布莱叶盲文与二进制码 前几章就举了几个编码的例子，让你知道——编码可以用来传递信息。然后布莱叶盲文是一种二进制的编码，因为和计算机的二进制特点符合，所以被拉出来讲了。接下去几章就是铺垫一些电学基础，让你知道我们可以用开关的开和闭，来表示1和0的编码。这样后面就可以借助这个特性，拿开关和电线来组装计算机了。 第四章：手电筒的剖析、第五章：绕过拐角的通信 第五章里最重要的概念就是接地。大地电阻很大，但大地是导体。电子只要流动就能形成电能，电子是哪里来的？是不是一个环路？这个不重要。接地处电子往大地那里移动，电势就低。电池那边的电子就可以往接地处移动了。 有人说，那我一个电路，中间拿掉一个导线，为什么不能接通？因为空气的电阻太大了··· 电子没法移动到空气中。 第十章：逻辑与开关与第十一章：门 第十章首先介绍的内容是：布尔代数。 布尔代数，其实在我们的《离散数学》课里就接触过。注：如果没学过离散数学，可以买《离散数学及其应用》这本书学习，这里说到的形式逻辑主要指命题逻辑《离散数学》里一开始讲的逻辑，比如这种形式的： 我们知道一个命题可能是真（T），也可能是假（F）。那如果我们把T和F换成1和0，然后将命题逻辑中的合取，析取，否定等关系换了一种表示形式，这就成了布尔代数。 布尔代数中每个变量都是一个{0,1}的集合。命题逻辑中的合取在布尔代数中用·或者AND表示，而析取则用+或者OR表示。否定则用表示。 在第十一章中，有一个布尔表达式： (M·N·(W+T)+(F·N·(1-W))+B) 我们代入每个变量之中，运用布尔代数运算符的规则，就可以计算出这布尔表达式的值是True或者是False。 这就是问题的关键了，布尔代数是一个抽象的计算模型。我们可以将现实世界的问题，抽象成布尔表达式（当然这个最终是因为我们可以用命题逻辑来表示现实世界的问题）。 讲到这里，似乎和计算机没有什么关系。但最精彩的部分就在下面，我们可以用布尔代数设计电路。 一个机械开关，有开启和闭合两种状态，可以用来表示0或者1。这个是《编码》前几章大力铺垫的一个事实。既然这样，那我们就可以用两个开关的并联或者串联来表示AND和OR逻辑。更进一步，我们可以用开关和电线表示任何布尔表达式。 值得注意的是，用布尔代数可以用某种电路来等价的表示这个事实。从在19世纪50年代乔治·布尔发明布尔代数开始，一直到20世纪30年代才被信息论之父香农发现。尽管逻辑电路所需的开关和电线在19世纪都已经存在了。可见这种等价关系的革命性意义。 当然，反过来，布尔表达式也可以指导我们设计电路。事实上这个是目前所有逻辑电路设计的理论基础。 《数字逻辑》这门课讲布尔代数，主要是作为设计电路的一种工具。假如我们要设计电路，解决这个现实问题。这个问题被抽象成几个输入和输出。这些输入和输出是可能是0或者1。我们知道不同变量输入时对应的输出，也就是所谓的真值表。利用真值表，我们可以写出一个布尔表达式。但这个布尔表达式可以化简。我们可以用卡诺图等方式进行化简，化简的目的是简化电路。最终，化简的电路可以转化为门电路。 《编码》里只是简单的介绍了布尔代数和门电路，没有深入的介绍电路的设计。这是比较明智的，因为如何设计电路不是我们要关心的话题。《数字逻辑》中在电路设计这块涉及的还有功能表到布尔表达式的转换，布尔表达式的化简等等。有兴趣的同学可以了解一下。 总结一下，这两章对我们最大的启发就是：逻辑电路设计的理论基础是布尔代数。布尔代数可以用逻辑电路进行等价表示。而逻辑电路则是计算机所有硬件的基础。 第十二章：二进制加法器 这章一开始说： 如果我们可以造出加法器，同样地，就可以利用加法来实现减法、乘法和除法，计算按揭付款，引导火箭飞到火星、下棋，以及填写我们的话费账单 大家可能觉得这是夸张的说法，但其实加法器的确就是CPU中最重要的部分。实现了加法器，再加上存储系统，和控制器，就是一个基本的计算机了。 所以这章内容可以说是《编码》这本书介绍的如何制造一台计算机中的第一次飞跃（第二次飞跃是第十七章，自动操作）。 说的很神奇，其实加法器就是由简单的门电路构成的一个电路而已。 我们已经知道了各种门电路的输入输出，那问题就是，如何来利用门电路，设计一个相对复杂的电路呢？ 这部分的知识对应的是大学中的《数字逻辑》课程。电路的设计有一套成熟的方法，当然我们先不考虑那么多，先来看看《编码》的作者是如何设计这个加法器电路的。 对于一个电路，我们首先要确定输入和输出，并写出一个真值表。 我们进行二进制数的相加时，会分别相加两个二进制数的每一位，如果有进位，则将进位加入下一位二进制数的相加中。 这样，我们就可以将两个二进制数的加法，转化为多次的一位二进制数加法。一位二进制数加法的输入是两个个加数。输出是一位的二进制数，以及一个进位数。比如输入是1加1，输出结果是0，进位位是1。 现在我们就可以列出两个真值表，一个是加法的真值表，一个是进位的真值表。 +加法 0 1 0 0 1 1 1 0 +进位 0 1 0 0 0 1 0 1 好了，现在我们可以进入第二步，根据真值表，设计电路。 我们要设计这样一个电路，输入A和B，都是一位二进制数，输出结果C和进位数D，也是都是一位二进制数。 我们观察真值表的输入和输出，发现进位表的真值和与门是一样的。而加法表的真值和异或门是一样的。 P141页的半加器，就是简单地将一个异或门和一个与门连到相同的输入端。异或门输出的就是加法结果，与门输出的则是进位的结果。 为什么这个叫半加器呢，因为这个半加器还无法完成真正的加法，因为它的输入中没有考虑进位。真正的一位加法器，输入有两个加数，以及进位位，输出结果和进位位。 P142页顶部的图就是全加器。它的原理就是级联两个半加器，将第一个半加器的结果和输入的进位位相加，对于两个半加器输出的进位位，则用一个或门来处理。或门在这里其实也是起一个加法器的作用，只不过两个级联的半加器的进位输出不会同时为1*（如果前一个半加器产生进位，那结果必然是0，那后一个半加器就不可能产生进位了）*，因此不用考虑输入都为1的情况。 P144页底部的图，讲8个全加器连接起来，前一个全加器的进位位输出是后一个全加器的进位位输入，第一个全加器的进位输入是0。这样我们就得到了一个8位加法器。...

读老道(Douglas Crockford)的《Javascript:The Good Parts》中关于array.splice()方法的实现代码，现在自己加一些注释。 ...