编译原理之 html parser

halo 大家好，俺是 132，今天听说有人在公司里分享 asta 的实现原理，内心一万点伤害，fre 颜面何在？

asta 是一个类似于 svelte 的前端框架，它把 template 编译为 dom 指令，最大的好处是 no runtime，适合某些对内存珍贵的场景，比如小程序双线程，RN 的三线程等等

它的本质其实就是个 compiler，今天我们主要说 html parser 的部分，asta 是我写的第二个 html parser 了，第一个小程序的 wxml parser

这两个 parser 套路是一样的，但是针对不同的 case 我采取不同的技巧，希望大家看完能有所收获

编译原理

编译原理是一套死的概念，但是需要我们编译的东西和我们想要的 case 是完全不同的，所以我们设计整个编译器的细节也有所不同

1. tokenizer

我认为编译原理中最重要的环节，也是需要我们最开始要设计的环节

我们拿到一个 html，第一时间应该考虑我们应该怎么拆

asta 中是这么拆的：

<div class="bbb">{aaa}</div>
>
[<div class="bbb">, {aaa}, </div>]

但是在小程序 wxml 中，就不能这么拆了，因为小程序有这样的 case：

<div class="ccc {{bbb}}">ddd {{aaa.length > 0 ? 'eee': fff}}</div>

怎么样，是不是惊呆了，一个简单的 template 中，包含了表达式，纯字符串，变量

这个时候就考验 token 的设计能力了

[<div class=", [ccc ,{{bbb}}], ">, [ddd ,{{aaa.length > 0 ? 'eee': fff}}], </div>]

刺不刺激，就是这么迷乱，但是本质思想是，将 "ccc {{bbb}}" 这种单独拆开，不要放在一起拆

对于表达式，这是个难点，在 vue2 中使用了 with 的奇技淫巧，还是蛮骚的

 with(this.data){
    aaa.length > 0 ? 'eee': fff
 }

所以这个时候另一种 tokenizer 的实现思路就登场了——基于正则

上面讲的 tokenizer，主要是遍历字符串，然后记录索引，实现一个“有限状态机”，正则也可以实现，对于基于线性遍历很难实现的状态机，用正则最合适不过

基于正则的 tokenizer 长这样，感受一下先

let tokenizer = /((?:^|\n+)(?:\n---+|\* \*(?: \*)+)\n)|(?:^``` *(\w*)\n([\s\S]*?)\n```$)|((?:(?:^|\n+)(?:\t|  {2,}).+)+\n*)|((?:(?:^|\n)([>*+-]|\d+\.)\s+.*)+)|(?:!\[([^\]]*?)\]\(([^)]+?)\))|(\[)|(\](?:\(([^)]+?)\))?)|(?:(?:^|\n+)([^\s].*)\n(-{3,}|={3,})(?:\n+|$))|(?:(?:^|\n+)(#{1,6})\s*(.+)(?:\n+|$))|(?:`([^`].*?)`)|(  \n\n*|\n{2,}|__|\*\*|[_*]|~~)/gm,

我们总结的时候再讲这个，但是总体来说，tokenizer 怎么设计怎么拆，直接决定了整个编译器的水准

2. parser

parser 是构建一棵 AST 树的过程，还是那句话，原理是死的，case 是不一样的，我们还是要去“设计”

比如小程序 wxml 的这种 case

<!--template.wxml-->
<template name="aaa">
  <view>
    <text>bbb</text>
  </view>
</template>

<template name="bbb">
  <view>
    <text>bbb</text>
  </view>
</template>

<!--aaa.wxml-->
<import src ="../template/template.wxml"/>
<template is="aaa"/>

<!--bbb.wxml-->
<import src ="../template/template.wxml"/>
<template is="bbb"/>

跨文件的 import/include，想象一下，如果是你，你该怎么办？

遇到 import 就去 readFile？答案肯定是不

遇到这种情况，我也冥思了很久，最终读了 rollup 的代码才有了思路

那就是后置 import

// input
<import src ="../template/template.wxml"/>
<template is="bbb"/>

// output
<template is="bbb"/>

我们忽略所有 import，只保留真正的 templateis=，对应到 rollup 里就是只保留函数调用

// input
import {aaa} from './a.js'
aaa()

// output
aaa()

我们会构建一个图，然后分析到了 aaa() 的调用的时候，再到图里找 aaa 在哪

这种思路对于跨文件的依赖导入特别受用，我把它放到 parser 里来做，在生成 ast 树的时候，顺便生成 block graph

其实类似的思路在 vue3 中叫做 block tree，但不跨文件，没什么难度

值得一提的是，因为 asta 没有这种跨文件的引用关系，所以 asta 中我没有用 block graph，甚至大道从简，我使用了 singlepass 的思路，一次遍历，tokens 和 ast 一起生成了

所以嘛，编译原理是死的，但是 case 是活的，能在不同的 case 下设计出最合理的代码安排，就可以了

3. generator

如果 tokenizer 和 parser 安排的足够好，其实 generator 就是拼字符串了

可是如果 tokenizer 和 parser 设计的不好，那么 generator 就真的变成火葬场了，各种 case by case 应接不暇

所以一个编译器写的怎么样，其实看 generator 的 dirty code 的数量就可以判断出来

根据 case 不同，这块是完全不同的实现，比如 wxml 我最终变异成 jsx，而 asta 则是直接变异成 dom 指令

没什么好讲的，next step

基于正则的 tokenizer

上面讲的是正常的编译思路，但是有很多字符串，一看就不好搞，写 parser 就小题大做了

比如 asta 中对 js 的解析，比如 wean 中 esbuild 插件对 js 的转换

这种如果想不开就会引入 babel 或 acorn 生成 AST 了，但是等你生成 AST 的时候，esbuild 已经从 0.3 s 变成 13s 了……

所以这个时候正则就派上用场了

let count = 0

function add(){
  count++
}

以上是 asta 也就是 svetle 的 js 内容，这个思路是魔术 let 基于分配的响应式，说白了就是匹配

let [count] = [0]

function add(){
  [count]++
}

说的直白点就是这样的，匹配魔术 let 和分配 = 的内容

asta 我还没写完，这块我还是设计，具体实现大家可以期待一下，反正肯定不可能引入 acorn 的，只能走正则

同样的是，esbuild 不提供 AST，也不可能引入会拖慢速度的第三方库，回归正则才是王道

总结

编译原理是死的，case 是活的，人也是活的，之所以编译原理会这么大家这么喜欢，不是这个技术很难

而是这个技术真的很考验水准，同样一个 case 不同的人会做出来不同的代码安排

我一直在寻找某个 case 的最好安排，而不是无脑 case by case

好啦，最近真是绝了，小作文都日更了，绝了绝了

我还在研究 web container，web container 对于 asta 这类编译框架来说，也是很重要的，编译为 wasm 就可以把编译器跑到浏览器中，就不用和 vue 一样同时保持一套 runtime 的 API 了

米娜，再贱！