> Grater 目前在比较初期的阶段，[代码已开源](https://github.com/nanyang24/grater)，可以在[这里](https://nanyang24.github.io/Grater/)体验

> Hi，首先在开始之前，我得承认，我并没有 CS 教育的经历。通常这句话的后面一定有转折语句，我想这里还是不要有了。所以虽参考多个领域内概念，但落地总体还是偏向于实用主义。

 
 

在专注前端一段时间后，可能会发现工具链中有很多都包含基础的 Parser，比如 TypeScript 的

[Parser](https://github.com/microsoft/TypeScript/blob/master/src/compiler/parser.ts)，React 使用的 Parser 是 [Acorn](https://github.com/acornjs/acorn) 以及 [Acorn-JSX](https://github.com/acornjs/acorn-jsx) ，之前是使用 Esprima 的 [fork 版本](https://github.com/facebook/esprima)，ESLint 也是一样，只是改了名字叫 [Espree](https://github.com/eslint/espree)，而 Babel 使用了自己的 [Parser](https://github.com/babel/babel/tree/master/packages/babel-parser)。

可能会有个疑惑是为什么不利用 Lex/Yacc 来快速实现，而是选择 CP 值有些低的手写方式。有实现一个 JS AST Parser 的想法来自于 “我想与 JS 更近一点”，很难描述这种情感，通常人们可能普遍认为这是一种自我描述性质的解释。在这个过程中看了很多类型的 Parser 实现，由衷感谢这些开源巨人们，没有这些作为参考，绝对没有这篇文章以及 Grater。

 
 

Grater 是一个输出符合 ESTree 定义结构 AST 的 ECMAScript Parser，目前基本实现了大部分 ES5 所包含的定义，初期大目标是追上最新 ES 标准实现。在输入符合语法规则的代码前提下，解析出 AST，没有做 Tokens 的输出（也是因为 Tokens 并没有一个官方规范标准），以及更加复杂的错误恢复机制

使用 TS 来书写 Grater 是为了尽量减少一些心智负担，能够预想到这个项目不会很小，增加一些必要的约束可以提高效率，也能利用 ES-Tree 的类型定义完善结构

实现一个最普世的 AST Parser，流程如下：

`SourceCode ~~ Tokenizer ~~> Token Stream ~~ Parsing ~~> AST`

 

简要来说，源码将被 `Tokenizer` 后形成 一长串不同类型的 `Token` 字节流，以便于我们按照规范的定义，在 `Parsing` 阶段解析相应的语法语句结构，形成特定的 `AST` 结构。

> 我们目标是产生符合标准的 AST，也就是要符合 [The ESTree Spec](https://github.com/estree/estree)，而解析方式也尽量按照 ECMAScript® Language Specification 中的描述去实现。

 
 

## 阶段 1 : Tokenizer

`Tokenizer` 词法分析 (Lexical Analysis)，也就是常说的 分词 ，将要解析的源解析为逐个符合特定语言规则的符号，这个过程通过实现 DFA 做具体的分词工作

> Lexer / Scanner 都是在描述这个阶段

### 实现分词的方式

根据语言的词法规则，标记出一串字符中的不同类型 Token

这里我们简单 parse 一个 stream：`age ≥ 26`

![!img](http://cdn.nanyang.io/images/age%3E=26.png)

> Identifier、Number、>= 都是终结符，终结符都是词法分析中产生的 Token。
> 而那些非叶子节点，就是非终结符。
> 文法的推导过程，就是把非终结符不断替换的过程，让最后的结果没有非终结符，只有终结符。

利用实现好的 DFA，在不同的状态进行转移，解析出 Token

- 完整的语法词法分析器只是一个具有完善状态和转移路线的 FSA
- 为了简化 Token 的解析，所以 Token 通常会采用正则文法（如名称、运算符、常量、注释）

 

### 为 Token 分配状态

在之后的 Parsing 过程中会经常使用到 判断当前 Token 是否符合一类定义的情况

比如: 判断当前 Token 是否为 `Keyword` 或者 `Pattern`

我们可以利用 `位运算` 进行状态的分配 ([压缩状态](http://mark-story.com/posts/view/using-bitmasks-to-indicate-status))

在字符定义中，我们可以为字符配置特有的状态

```jsx
/* Variable declaration */
VarKeyword = 71 | IsKeyword,
LetKeyword = 72 | IsKeyword,
ConstKeyword = 73 | IsKeyword,

LeftBrace = 12 | IsPatternStart, // {
LeftBracket = 19 | IsPatternStart | IsPropertyOrCallExpression, // [
```

```jsx
// will match `{` and `[` or Keyword
if (parser.token & Token.IsPatternStart || parser.token & Token.IsKeyword) {
 // todo
}
```

 

### 判断 Keyword 的方式

语言都有各自的保留字，比如 `let`，`function`，`true`/`false`

查看了 Esprima 的[谓词实现](https://github.com/jquery/esprima/blob/45c9ab14d96f7f7fa88333fdd897487a8c20082f/src/scanner.ts#L348)，觉得还可以有简约的实现

```tsx
private isKeyword(id: string): boolean {
 switch (id.length) {
 case 2:
 return (id === 'if') || (id === 'in') || (id === 'do');
 case 3:
 return (id === 'var') || (id === 'for') || (id === 'new') ||
 (id === 'try') || (id === 'let');
 case 4:
 return (id === 'this') || (id === 'else') || (id === 'case') ||
 (id === 'void') || (id === 'with') || (id === 'enum');
			// ...
 default:
 return false;
 }
}
```

由于我们可以知道当前 Token 的字符值，这里简单使用了 HashMap 取值的方式：

```tsx
function scanIdentifier(parser: IParserState): Token {
	// ...
	//
 return mapKeywordTable[parser.tokenValue] || Token.Identifier;
}

...
// Keyword hash-map Table
export const mapKeywordTable: { [key: string]: Token } = {
 this: { value: Token.ThisKeyword },
 function: { value: Token.FunctionKeyword },
 if: { value: Token.IfKeyword },
 return: { value: Token.ReturnKeyword },
 var: { value: Token.VarKeyword },
 else: { value: Token.ElseKeyword },
}
```

> BTW: 正则判断并没有优势

 
 

## 阶段 2 : Parsing

`Parsing` 语法分析 (Syntactic Analysis)，在这个阶段将在 Tokenizer 的基础上进行语法结构的识别

Grater 采用的解析方式是常见的 LL(k) Parser，是一种 自顶向下的 Parser

其中两个 L 的意思分别是：`Left-to-right` , `Leftmost derivation`

语句的规则通常 左边是 非终结符(Non-terminal)，右边是 产生式(Production Rule)，这种表达方式是 [上下文无关文法](https://en.wikipedia.org/wiki/Context-free_grammar)(Context-free grammar)，在解析的过程中，非终结符将被其产生式替换，直到最后全部变成 终结符(Terminal)，也就是 Token，这一系列的过程叫做 `Derivation` （`Leftmost derivation` 指总是先把左边的非终结符展开，也就是从最左的非终结符开始推导，而且是深度优先）

 

其中 `Recursive Descent Parsing` 的实现其实很简单，非常的直观

> 实际上，JS 语法并不是完全纯粹的 Context-free grammar
> 而递归下降的实现里可以做到超越 CFG，在 Recursion func 中可以传递 context，在有需要上下文解析的情况里用到，以及丰富错误信息

 

### 消除左递归 left recursion

由于 Grater 是没有 [Backtracking](https://en.wikipedia.org/wiki/Backtracking)，那么就需要分析时对每个文法做正确的展开

但遇到左递归的文法，就会有问题，解决的方法通常是将左递归转化为等价的右递归形式

例如在 Binary Expression 的词法规则中，产生式的第一个元素是它自身，那么程序就会无限地递归下去，这种情况就叫做左递归。

比如 加法表达式的产生式中有一条是 “加法表达式 + 乘法表达式”

我们用 `2 + 3` 这个加法表达式来举例

ECMAScript Language Specification 中加法表达式的定义式:

_[AdditiveExpression](https://tc39.es/ecma262/#prod-AdditiveExpression)_

- _[MultiplicativeExpression](https://tc39.es/ecma262/#prod-MultiplicativeExpression)_
- _[AdditiveExpression](https://tc39.es/ecma262/#prod-AdditiveExpression)_ **+** _[MultiplicativeExpression](https://tc39.es/ecma262/#prod-MultiplicativeExpression)_
- _[AdditiveExpression](https://tc39.es/ecma262/#prod-AdditiveExpression)_ **-** _[MultiplicativeExpression](https://tc39.es/ecma262/#prod-MultiplicativeExpression)_

_[MultiplicativeExpression](https://tc39.es/ecma262/#prod-MultiplicativeExpression)_

- _[ExponentiationExpression](https://tc39.es/ecma262/#prod-ExponentiationExpression)_
- _[MultiplicativeExpression](https://tc39.es/ecma262/#prod-MultiplicativeExpression) [MultiplicativeOperator](https://tc39.es/ecma262/#prod-MultiplicativeOperator) [ExponentiationExpression](https://tc39.es/ecma262/#prod-ExponentiationExpression)_

接下来，我们只保留关键信息，简化的 [BNF](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form) :

```js
Additive: Multiplicative | (Additive + Multiplicative);

Multiplicative: IntLiteral | (Multiplicative * IntLiteral);
```

非终结符通常只用了一个大写字母代表，通常可简写为：

```tsx
A -> M
 | A + M
 | A - M
```

我们的 Token 串是 `2 + 3`，来进行匹配规则

1. 应用第一条规则 A -> M，2 + 3 不是 M 表达式，转移到使用 A -> A + M 的方法匹配
2. A + M 将从 A 开始推导，重复了第一步的操作，导致了 infinite loop

- 如果对第二个步骤不理解，比如认为 2+3 应该符合 A + M 这个规则
 这样认为是因为本能的使用了广度优先，而我们的 Parser 是依照深度优先

然后可以通过转换文法消除左递归

A: M | M + A

再进行推导就消除了之前的循环

> 其实 左递归的问题 与 运算符优先级也有关联

 
 

### Operator Precedence 运算符优先级

优先级是通过在语法推导中的层次来决定的：优先级越低的，越先尝试推导。
而对应在 AST 树中，层次越深，优先级越高

例如：`1 + 2 * 3` 产生的 AST 结构为

```json
{
 "type": "Program",
 "sourceType": "script",
 "body": [
 {
 "type": "ExpressionStatement",
 "expression": {
 "type": "BinaryExpression",
 "left": {
 "type": "Literal",
 "value": 1
 },
 "right": {
 "type": "BinaryExpression",
 "left": {
 "type": "Literal",
 "value": 2
 },
 "right": {
 "type": "Literal",
 "value": 3
 },
 "operator": "*"
 },
 "operator": "+"
 }
 }
 ]
}
```

Grater 采用 [Precedence climbing method](https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method) 实现高效的运算符优先级解析。
如果当前运算符的优先级小于前一个运算符，则提前返回叶子节点。并将 高优先级运算符 左右两边的节点合并为一个 `BinaryExpression`

还有几个特殊的情况需要处理：

1. 括号优先于所有运算符
1. `^` 是右关联的，而所有其他二进制运算符是左关联的

 

> 这里提及两个解决优先级相关的算法
>
> 1. [Precedence climbing](http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing)
> 2. [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm)

 

## Conclusion

如果你有想法打算尝试写一个 Parser，我的建议是 Just write it，你可以先不用管那些固有理论，着手去实现它，在实现过程中不断优化，遇到问题再依据理论加以解决

> _Sometimes you gotta run before you can walk — Iron Man_

### Contribution

> 为 Grater 实现更多的功能及识别更多的语法

如果你有兴趣贡献代码給 Grater，让它变成更完善的 Parser，非常欢迎结合你的思考来实现 Grater 目前所需的功能点，在[这里](https://github.com/nanyang24/Grater/blob/master/README.md#-feature-to-do-list)可以查看

## Reference

1. [Acorn: Alternative, faster React.js JSX parser](<[https://rreverser.com/gh-acorn-jsx/](https://rreverser.com/gh-acorn-jsx/)>)
2. [Operator-precedence parser](<[https://en.wikipedia.org/wiki/Operator-precedence_parser](https://en.wikipedia.org/wiki/Operator-precedence_parser)>)
3. [LR parser](<[https://en.wikipedia.org/wiki/LR_parser](https://en.wikipedia.org/wiki/LR_parser)>)
4. [LL parser](<[https://en.wikipedia.org/wiki/LL_parser](https://en.wikipedia.org/wiki/LL_parser)>)
5. [Top-down parsing](<[https://en.wikipedia.org/wiki/Top-down_parsing](https://en.wikipedia.org/wiki/Top-down_parsing)>)
6. [Recursive descent parser](<[https://en.wikipedia.org/wiki/Recursive_descent_parser](https://en.wikipedia.org/wiki/Recursive_descent_parser)>)
7. [Left recursion](<[https://en.wikipedia.org/wiki/Left_recursion](https://en.wikipedia.org/wiki/Left_recursion)>)
8. [NFA](<[https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton](https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton)>)
9. [Context-free grammar](<[https://en.wikipedia.org/wiki/Context-free_grammar](https://en.wikipedia.org/wiki/Context-free_grammar)>)

实现一个 ECMAScript Parser 需要做的事情

该为这混乱的一年画上句号了。

2020 年以一场 Pandemic 为开局，注定是特别的一年。

### 生活

因为疫情，春节行程变得不同寻常，那段日子不断查看每日疫情报告，返工的日期也不断延后。因为女朋友当时还在北京工作，她就提前返京了，我刚好需要从北京转机回深圳，也就“想尽办法”的先到了北京（机票被取消 3 次后抓住了每周只有一班的绿皮车）。

到了北京之后，国内疫情形势加重，大多数公司都开始 WFH。

 

在北京租的房子在西郊线的茶棚，离颐和园特别近。和市区的喧嚣不同，这里就像日本的乡下，能让心灵放松下来

<figure>
 <img
 src="https://cdn.nanyang.io/images/6B2A4E04-5081-42AF-83C4-0025EEB35796.jpeg"
 alt="茶棚站旁边的铁轨">
 <figcaption>茶棚站旁边的铁轨</figcaption>
</figure>

<figure>
 <img
 src="https://cdn.nanyang.io/images/5AFD4955-8737-49E2-868D-495F8A54DB82.jpeg"
 alt="夕阳下的车站">
 <figcaption>夕阳下的车站</figcaption>
</figure>

<figure>
 <img
 src="https://cdn.nanyang.io/images/726CFACE-FFBA-4D48-9ADD-82D30F94DD2D.jpeg"
 alt="时常会去逛逛旁边的颐和园">
 <figcaption>时常会去逛逛旁边的颐和园</figcaption>
</figure>

<figure>
 <img
 src="https://cdn.nanyang.io/images/B7F3CB58-DC24-4E09-BBA3-788E8ACF8824.jpeg"
 alt="小区旁边的公园">
 <figcaption>小区旁边的公园</figcaption>
</figure>

 

休息日会去商业中心，那时候北京属于半封城状态，繁华地段也是人很少

在西单大悦城的 Apple Store 见到了 Pro Display XDR 和 Mac Pro 的实物

![image](https://cdn.nanyang.io/images/E95AB0B0-9CB3-4789-B9FA-710FF6B2F83F.jpeg)

每年 Apple 都会邀请知名导演拍摄一部有关春节味道的短片，今年是《女儿》

[Chinese New Year — Daughter](httpss://www.youtube.com/watch?v=bvtwWhKdxhM)

其实我一直对春节期间的归途部分，充满了兴趣，紧迫感和兴奋感和很多情绪杂糅在一起

<figure>
 <img
 src="https://cdn.nanyang.io/images/82466D87-B2E8-41FE-ACF7-DC8597A022E4.jpeg"
 alt="突然就没有密恐了">
 <figcaption>突然就没有密恐了</figcaption>
</figure>

 

转眼陆续返工，我们相继回到了深圳。

这是我当初选择的城市

即使已经如此熟悉这个城市，也不能消散我对它的喜爱，这座有海有山的城。

日常虽然忙碌，倒也充实。通勤时都会思考一些或大或小的事情

在路途中遇到之前便见过的陌生人，那种感觉很奇妙，甚至有点惊悚，仿佛往前走的只有时间

 

今年生日礼物收到了 明日香 的二号机，来自贴心的 GF，完成了初号机二号机的大集合！

![image](https://cdn.nanyang.io/images/B54B192C-5A78-430F-9246-F40E58EE254F.jpeg)

 

墙上也多了两幅框画

- [The Chart of Cosmic Exploration](httpss://popchart.co/products/the-chart-of-cosmic-exploration)

描绘了人类 56 年勇敢探索宇宙的探测器轨道（Luna 2 in 1959 to DSCOVR in 2015）

- [SpaceX Dragon](httpss://www.spacex.com/vehicles/dragon/)

SpaceX Dragon 飞掠地球的场景

![image](https://cdn.nanyang.io/images/C391D6B6-37D4-4BE2-A613-7AB672EA3B81.jpeg)

 

因为疫情的关系，5 月东京之行被迫取消，索性专注在了国内，也刚好去一些之前感兴趣但没有成行的地方

比如 重庆 和 成都

在 5D 的重庆，会看等高线是必修课 hhh，有着在其他城市绝无仅有的体验。还有遍地都是又爱又辣的火锅，推荐一定要去感受下。

重庆夜景非常容易出片，加上十月份常见的大雾，后期拉下曲线就有 Cyberpunk 的味道

![image](https://cdn.nanyang.io/images/86D85E14-B18A-4560-86DD-13A67D47FA3E.jpeg)

相比与重庆的喧闹和特别，几百公里外的成都截然不同

成都的第一感受是舒适，安静。很适合我这样做行程只做 50%的人。来之前也不会想到太古里还不错，与之相连的大慈寺闹中取静，香火隆盛。

计划中还有去附近的湖边野营，刚好感受一下 “蜀道” 的魅力，其中有一段在山上，迷雾笼罩仿佛驾驶在仙境

> BTW 未来一定要去 Nürburgring 体验一下
> ![image](https://cdn.nanyang.io/images/Nürburgring.png)

在经历曲折盘山路到达雅女湖后才得知因为雨水丰沛，导致湖水暴涨，淹没了原本的露营区域，计划宣告失败

<figure>
 <img
 src="https://cdn.nanyang.io/images/B1FB3412-7658-4AEC-809C-144DD4ABBB01.jpeg"
 alt="从酒店房间望去的雅女湖">
 <figcaption>从酒店房间望去的雅女湖</figcaption>
</figure>

 

今年看了很多 YouTuber 制作的内容，还有博客，很喜欢在屏幕前的时光，网络让我有随时触摸到世界任何地方能力的错觉。从他们书写的字里行间，视频的每一帧画面，感受不同个体散发的美好。

另外罗列一些值得记录的事情

1. 对 Racing line 的理解加强，在东莞卡丁车场练习，还在广州试玩了直驱模拟器，以后打算在家搞一套
2. 在川崎店里试了 Ninjia 400，基于深圳的禁摩政策还在犹豫中
3. 哈尔滨滑雪 🏂，喜欢掌控平衡的感觉，希望明年有机会去日本滑粉雪
4. 回内蒙古看望我的父母
5. 见了 GF 的父母
6. 逛 2020 广州车展，第一次去车展，没有预想的好，而且都是常见车，花钱去 4S 店感觉……
7. 扛着三脚架在雨天拍摄重庆夜景，一次难忘的经历！
8. 跟随 TPA 拍摄人像，Key 是与模特的沟通，传达摄影师的意图
9. 更新了 2 米长的实木桌和人体工程学椅，氛围灯也上了，对于热衷桌面文化的人，简直不要太开心
10. 今年本打算购置电脑，其实是去年年底就有这个想法了，奈何订了一台鸽了一年多的机箱，到现在也没收到。后面就开始等新款 iMac 了，目前看样子还要继续等下去。
11. 剧看的不多，刷完了 The Queen's Gambit 、The Crown 和 Drive To Survive 1 & 2
12. 借着 Mini 4WD 在深圳的比赛，完成童年的没做的事情，顺势动手做了一辆当下时代的 MS 避震车
13. 对电子产品克制了许多，考虑许久 CP 值才会真的下单，今年入了
 1. iPad Pro 2020，旅行剪辑修片，日常 GF 画画看书
 2. Sigma 24-70mm F2.8 DG DN，终于有一颗变焦头了，大爱
 3. Samsung SSD T7 Touch，旅行快速存储方案
 4. Dyson V11 Torque Drive，如同洗碗机般重要的存在
14. 投资收益不错，得益于科技股在 2020 年普遍高涨，未来还是一如既往价值投资
15. ......

其实还有太多想分享的东西，一不小心又写成分享文，以上的内容有空会写成详细文章

 

### 职业

我目前的职业是 Front-End Engineer

今年是 JS 诞生 25 周年，也是我的 25 周年。是的，我和 JS 同岁 😂

去年 9 月份离开了 Bellcode，有很多不舍，经常回忆（现在还留着很多当时同事的恶搞照片 hhh）。

紧接着 10 月份来了 CODING，进入了代码托管部门。说来也巧，在大学的时候使用过 CODING 的产品，当时也不会想到日后会有更多的缘分。

业余时间正在成为~~精读 ECMAScript 规范的 language lawyer~~，在做一个完整解析 ES 的 Parser，第一个版本应该会实现了 ES5 的绝大部分语法，Release 尽力不鸽的在~~明年 3 月（要补的测试用例太多了，实在头大）~~

也顺手做了几个有关 Router 的 lib。另外一直在优化这个网站的体验，有空基于 Server Component 玩一下。

 

### Next

- [Do One Thing and Do It Well](httpss://en.wikipedia.org/wiki/Unix_philosophy)
- 博客的技术向，多借鉴 Netflix Tech Blog
- 做技术要自信，做人同理
- 把生活过得有趣
- 健康第一位

回顾一年中发生的事情，如今看来更像是一段段剪影

Reactive State

最后推荐一些采用相似思想的工具和体会方式: