关于ast:手把手教你写一个-AST-抽象语法树

AST 解析器工作中常常用到，Vue.js 中的 VNode 就是如此！
其实如果有须要将非结构化数据转换成结构化对象用来剖析、解决、渲染的场景，咱们都能够用此思维做转换。

logo

咱们晓得 HTML 源码只是一个文本数据，只管它外面蕴含简单的含意和嵌套节点逻辑，然而对于浏览器，Babel 或者 Vue 来说，输出的就是一个长字符串，显然，纯正的一个字符串是示意不进去啥含意，那么就须要转换成结构化的数据，可能清晰的表白每一节点是干嘛的。字符串的解决，自然而然就是弱小的正则表达式了。

本文论述 AST 解析器的实现办法和次要细节，简略易懂~~~~，总共解析器代码不过百行！

本次指标，一步一步将如下 HTML 构造文档转换成 AST 形象语法树

<div class="classAttr" data-type="dataType" data-id="dataId" style="color:red"> 我是外层 div
    <span> 我是内层 span</span>
</div>

构造比较简单，外层一个 div, 内层嵌套一个 span，外层有 class,data，stye 等属性。
麻雀虽小，五脏俱全，根本蕴含咱们常常用到的了。其中转换后的 AST 构造有哪些属性，须要怎么的模式显示，都能够依据须要本人定义即可。
本次转换后的构造：

{
    "node": "root",
    "child": [{
        "node": "element",
        "tag": "div",
        "class": "classAttr",
        "dataset": {
            "type": "dataType",
            "id": "dataId"
        },
        "attrs": [{
            "name": "style",
            "value": "color:red"
        }],
        "child": [{
            "node": "text",
            "text": "我是外层 div"
        }, {
            "node": "element",
            "tag": "span",
            "dataset": {},
            "attrs": [],
            "child": [{
                "node": "text",
                "text": "我是内层 span"
            }]
        }]
    }]
}

不难发现，外层是根节点，而后内层用 child 一层一层标记子节点，有 attr 标记节点的属性，classStr 来标记 class 属性，data 来标记 data- 属性，type 来标记节点类型，比方自定义的 data-type=”title” 等。

先来看几组简略的正则表达式：

^ 匹配一个输出或一行的结尾，/^a/ 匹配 ”ab”，而不匹配 ”ba”
匹配一个输出或一行的结尾，/ 匹配 ”ba”，而不匹配 ”ab”
匹配后面元字符 0 次或屡次，/ab*/ 将匹配 a,ab,abb,abbb
匹配后面元字符 1 次或屡次，/ab+/ 将匹配 ab,abb, 然而不匹配 a
[ab] 字符集匹配，匹配这个汇合中的任一一个字符(或元字符)，/[ab]/ 将匹配 a,b,ab
\w 组成单词匹配，匹配字母，数字，下划线，等于[a-zA-Z0-9]

首先咱们将如下的 HTML 字符串用正则表达式示意进去：

<div> 我是一个 div</div>

这个字符串用正则形容大抵如下：

以 < 结尾跟着 div 字符，而后接着 >，而后是中文“我是一个 div”，再跟着 </，而后持续是元素 div 最初已 > 结尾。

div 是 HTML 的标签，咱们晓得 HTML 标签是已字母和下划线结尾，蕴含字母、数字、下滑线、中划线、点号组成的，对应正则如下：

const ncname = '[a-zA-Z_][\w-.]*'

于是组合的正则表达式如下：

`<${ncname}>`

依据下面剖析，很容易得出正则表达式为下：

`<${ncname}></${ncname}>`

我是一个 div

标签内能够是任意字符，那么任意字符如何形容呢？
\s 匹配一个空白字符 \S 匹配一个非空白字符 \w 是字母数字数字下划线
\W 是非 \w 的
同理还有 \d 和 \D 等。
咱们通常采纳 \s 和 \S 来形容任何字符（1、通用，2、规定简略，利于正则匹配）：

`<${ncname}>[\s\S]*</${ncname}>`

HTML 标签上的属性名称有哪些呢，常见的有 class,id,style,data- 属性，当然也能够用户轻易定义。然而属性名称咱们也须要遵循原则，通常是用字母、下划线、冒号结尾 (Vue 的绑定属性用: 结尾，通常咱们不会这么定义) 的，而后蕴含字母数字下划线中划线冒号和点的。正则形容如下：

const attrKey = /[a-zA-Z_:][-a-zA-Z0-9_:.]*/

HTML 的属性的写法目前有以下几种：

class=”title”
class=’title’
class=title

const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)=("([^"]*)"|'([^']*)'|([^\s"'=<>`]+)/

attrKey 跟着 =，而后跟着三种状况:

”结尾跟着多个不是 ” 的字符，而后跟着”结尾
‘ 结尾跟着多个不是‘的字符，而后跟着 ‘ 结尾
不是（空格，”，’,=,<,>）的多个字符

咱们测试一下 attr 的正则

"class=abc".match(attr);
// output
(6) ["class=abc", "class", "abc", undefined, undefined, "abc", index: 0, input: "class=abc", groups: undefined]

"class='abc'".match(attr);
// output
(6) ["class='abc'","class","'abc'", undefined,"abc", undefined, index: 0, input:"class='abc'", groups: undefined]

咱们发现，第二个带单引号的，匹配的后果是 ”‘abc’”，多了一个单引号‘，因而咱们须要用到正则外面的非匹配获取（?:）了。
例子：

"abcde".match(/a(?:b)c(.*)/);   输入 ["abcde", "de", index: 0, input: "abcde"]

这里匹配到了 b，然而在 output 的后果外面并没有 b 字符。
场景：正则须要匹配到存在 b，然而输入后果中不须要有该匹配的字符。
于是我么减少空格和非匹配获取的属性匹配表达式如下：

const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+))/

\= 两边能够减少零或多个空格，= 号左边的匹配括号应用非匹配获取，那么相似 = 号右侧的最外层大括号的获取匹配生效，而内层的括号获取匹配的是在双引号和单引号外面。成果如下：

从图中咱们清晰看到，匹配的后果的数组的第二位是属性名称，第三位如果有值就是双引号的，第四位如果有值就是单引号的，第五位如果有值就是没有引号的。

有了下面的标签匹配和属性匹配之后，那么将两者合起来就是如下：

/<[a-zA-Z_][\w\-\.]*(?:\s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+)))*>[\s\S]*<\/[a-zA-Z_][\w\-\.]*>/

上述正则残缺形容了一个节点，了解了签名的形容，当初看起来是不是很简答啦~

有了后面的 HTML 节点的正则表达式的根底，咱们当初开始解析下面的节点元素。
显然，HTML 节点领有简单的多层次的嵌套，咱们无奈用一个正则表达式就把 HTML 的构造都一次性的表述进去，因而咱们须要一段一段解决。
咱们将字符串分段解决，总共分成三段：

标签的起始
标签内的内容
标签的完结

于是将上述正则拆分：

const DOM = /<[a-zA-Z_][\w\-\.]*(?:\s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+)))*>[\s\S]*<\/[a-zA-Z_][\w\-\.]*>/;
// 减少 () 分组输入
const startTag = /<([a-zA-Z_][\w\-\.]*)((?:\s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+)))*)\s*(\/?)>/;

const endTag = /<\/([a-zA-Z_][\w\-\.]*)>/;

const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+))/g

// 其余的就是标签外面的内容了

不难发现，标签已 < 结尾，为标签起始标识地位，已 </ 结尾的为标签完结标识地位。
咱们将 HTML 拼接成字符串模式，就是如下了。

let html = '<div class="classAttr"data-type="dataType"data-id="dataId"style="color:red"> 我是外层 div<span> 我是内层 span</span></div>';

咱们开始一段一段解决下面的 html 字符串吧~

const bufArray = [];
const results = {
    node: 'root',
    child: [],};
let chars;
let match;
while (html&&last!=html){
    last = html;
    chars = true;// 是不是文本内容
    // do something parse html
}

bufArray: 用了存储未匹配实现的起始标签
results: 定义一个开始的 AST 的节点。
咱们再循环解决 HTML 的时候，如果曾经解决的字符，则将其删除，这里判断 last!=html 如果解决一轮之后，html 还是等于 last，阐明没有须要解决的了，完结循环。

首先判断是否是 </ 结尾，如果是则阐明是标签结尾标识

if(html.indexOf("</")==0){match = html.match(endTag);
    if(match){
        chars = false;
        html = html.substring(match[0].length);
        match[0].replace(endTag, parseEndTag);
    }
}

已 </ 结尾，且能匹配上实时截止标签的正则，则该 html 字符串内容要向后挪动匹配到的长度，持续匹配剩下的。
这里应用了 replace 办法，parseEndTag 的参数就是 ”()” 匹配的输入后果了，曾经匹配到的字符再 parseEndTag 解决标签。

如果不是已 </ 结尾的，则判断是否是 < 结尾的，如果是阐明是标签起始标识，同理，须要 substring 来剔除曾经解决过的字符。

else if(html.indexOf("<")==0){match = html.match(startTag);
    if(match){
        chars = false;
        html = html.substring(match[0].length);
        match[0].replace(startTag, parseStartTag);
    }
}

如果既不是起始标签，也不是截止标签，或者是不合乎起始和截止标签的正则，咱们对立当文本内容解决。

if(chars){let index = html.indexOf('<');
    let text;
    if(index < 0){
        text = html;
        html = '';
    }else{text = html.substring(0,index);
        html = html.substring(index);;
    }
    const node = {
        node: 'text',
        text,
    };
    pushChild(node);
}

如果是文本节点，咱们则退出文本节点到指标 AST 上，咱们着手 pushChild 办法，bufArray 是匹配起始和截止标签的长期数组，寄存还没有找到截止标签的起始标签内容。

function pushChild (node) {if (bufArray.length === 0) {results.child.push(node);
    } else {const parent = bufArray[bufArray.length - 1];
        if (typeof parent.child == 'undefined') {parent.child = [];
        }
        parent.child.push(node);
    }
}

如果没有 bufArray，阐明以后 Node 是一个新 Node，不是上一个节点的嵌套子节点，则新 push 一个节点；否则取最初一个 bufArray 的值，也就是最近的一个未匹配标签起始节点，将以后节点当做为最近节点的子节点。

<div><div></div></div>

显然，第一个 </div> 截止节点，匹配这里的第二个起始节点

，即最初一个未匹配的节点。

在每一轮循环中，如果是合乎预期，HTML 字符串会越来越少，直到被解决实现。

接下来咱们来解决 parseStartTag 办法，也是略微简单一点的办法。

function parseStartTag (tag, tagName, rest) {tagName = tagName.toLowerCase();

    const ds = {};
    const attrs = [];
    let unary = !!arguments[7];

    const node = {
        node: 'element',
        tag:tagName
    };
    rest.replace(attr, function (match, name) {const value = arguments[2] ? arguments[2] :
            arguments[3] ? arguments[3] :
                arguments[4] ? arguments[4] :'';
        if(name&&name.indexOf('data-')==0){ds[name.replace('data-',"")] = value;
        }else{if(name=='class'){node.class = value;}else{
                attrs.push({
                    name,
                    value
                });
            }
        }
    });
    node.dataset = ds;
    node.attrs = attrs;
    if (!unary){bufArray.push(node);
    }else{pushChild(node);
    }
}

遇到起始标签，如果该起始标签不是一个完结标签 (unary 为 true，如：, 如果自身是截止标签，那么间接解决完即可)，则将起始标签入栈，期待找到下一个匹配的截止标签。
起始标签除了标签名称外的属性内容，咱们将 dataset 内容放在 dataset 字段，其余属性放在 attrs

咱们接下来看下解决截止标签

function parseEndTag (tag, tagName) {
    let pos = 0;
    for (pos = bufArray.length - 1; pos >= 0; pos--){if (bufArray[pos].tag == tagName){break;}
    }
    if (pos >= 0) {pushChild(bufArray.pop());
    }
}

记录还未匹配到的起始标签的 bufArray 数组，从最初的数组地位开始查找，找到最近匹配的标签。
比方：

<div class="One"><div class="Two"></div></div>

class One 的标签先入栈，class Two 的再入栈，而后遇到第一个 </div>，匹配的则是 class Two 的起始标签，而后再匹配的是 class One 的起始标签。

到此，一个简略的 AST 解析器曾经实现了。

当然，本文是实现一个简略的 AST 解析器，根本主逻辑曾经蕴含，完整版参考如下：

残缺解析参考：vue-html-parse[1]

本文的 AST 解析器的残缺代码如下：

easy-ast[2]

[1]

残缺解析参考：vue-html-parse: https://github.com/vuejs/vue/…

[2]

easy-ast: https://github.com/antiter/bl…

关于ast:手把手教你写一个-AST-抽象语法树

如何解析成 AST？

指标

回顾正则表达式

匹配标签元素

匹配标签属性

匹配节点

AST 解析实战

参考资料