这里记录一下我阅读《编程语言实现模式》这本书的一些感受。一开始，对于编译原理，我的印象是这门课非常的艰深。在正式学习之前其实我已经看了很多编译相关的东西，比如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。