您可以捐助,支持我们的公益事业。

1元 10元 50元





认证码:  验证码,看不清楚?请点击刷新验证码 必填



  求知 文章 文库 Lib 视频 iPerson 课程 认证 咨询 工具 讲座 Model Center   Code  
会员   
   
 
     
   
 
 订阅
手把手教你写一个 AST 抽象语法树
 
 
  971  次浏览      20 次
 2023-9-25
 
编辑推荐:
本文主要阐述 AST 解析器的实现方法和主要细节。 希望能为大家提供一些参考或帮助。
文章来自于CSDN,由火龙果Linda编辑推荐。

如何解析成 AST ?

我们知道 HTML 源码只是一个文本数据,尽管它里面包含复杂的含义和嵌套节点逻辑,但是对于浏览器,Babel 或者 Vue 来说,输入的就是一个长字符串,显然,纯粹的一个字符串是表示不出来啥含义,那么就需要转换成结构化的数据,能够清晰的表达每一节点是干嘛的。字符串的处理,自然而然就是强大的正则表达式了。

本文阐述 AST 解析器的实现方法和主要细节,简单易懂~~~~~~~~,总共解析器代码不过百行!

目标

本次目标,一步一步将如下 HTML 结构文档转换成 AST 抽象语法树

  1. <div class="classAttr" data-type="dataType" data-id="dataId" >我是外层div
  2. <span>我是内层span</span>
  3. </div>

结构比较简单,外层一个 div,内层嵌套一个 span,外层有 class,data,stye 等属性。

  1. {
  2. "node": "root",
  3. "child": [{
  4. "node": "element",
  5. "tag": "div",
  6. "class": "classAttr",
  7. "dataset": {
  8. "type": "dataType",
  9. "id": "dataId"
  10. },
  11. "attrs": [{
  12. "name": "style",
  13. "value": "color:red"
  14. }],
  15. "child": [{
  16. "node": "text",
  17. "text": "我是外层div"
  18. }, {
  19. "node": "element",
  20. "tag": "span",
  21. "dataset": {},
  22. "attrs": [],
  23. "child": [{
  24. "node": "text",
  25. "text": "我是内层span"
  26. }]
  27. }]
  28. }]
  29. }

不难发现,外层是根节点,然后内层用 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

标签内可以是任意字符,那么任意字符如何描述呢?

`<${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 的正则

  1. "class=abc".match(attr);
  2. // output
  3. (6) ["class=abc", "class", "abc", undefined, undefined, "abc", index:
  4. 0, input: "class=abc", groups: undefined]
  5. "class='abc'".match(attr);
  6. // output
  7. (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 字符。

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\-\.]*>/

上述正则完整描述了一个节点,理解了签名的描述,现在看起来是不是很简答啦~

AST 解析实战

有了前面的 HTML 节点的正则表达式的基础,我们现在开始解析上面的节点元素。

标签的起始

标签内的内容

标签的结束

于是将上述正则拆分:

  1. const DOM = /<[a-zA-Z_][\w\-\.]*(?:\s+([a-zA-Z_:][-a-zA-Z0-9_:.]*)
    \s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+)))*>[\s\S]*<\/[a-zA-Z_][\w\-\.]*>/
    ;
  2. // 增加()分组输出
  3. const startTag = /<([a-zA-Z_][\w\-\.]*)((?:\s+([a-zA-Z_:][-a-zA-Z0-9_:.]
  4. *)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+)))*)\s*(\/?)>/;
  5. const endTag = /<\/([a-zA-Z_][\w\-\.]*)>/;
  6. const attr = /([a-zA-Z_:][-a-zA-Z0-9_:.]*)\s*=\s*(?:"([^"]*)"|'([^']*)'|([^\s"'=<>`]+))/g
  7. // 其他的就是标签里面的内容了

不难发现,标签已 < 开头,为标签起始标识位置,已 </ 开头的为标签结束标识位置。

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

我们开始一段一段处理上面的 html 字符串吧~

  1. const bufArray = [];
  2. const results = {
  3. node: 'root',
  4. child: [],
  5. };
  6. let chars;
  7. let match;
  8. while (html&&last!=html){
  9. last = html;
  10. chars = true;// 是不是文本内容
  11. // do something parse html
  12. }

bufArray: 用了存储未匹配完成的起始标签

首先判断是否是 </ 开头,如果是则说明是标签结尾标识

  1. if(html.indexOf("</")==0){
  2. match = html.match(endTag);
  3. if(match){
  4. chars = false;
  5. html = html.substring(match[0].length);
  6. match[0].replace(endTag, parseEndTag);
  7. }
  8. }

已 </ 开头,且能匹配上实时截止标签的正则,则该 html 字符串内容要向后移动匹配到的长度,继续匹配剩下的。

如果不是已 </ 开头的,则判断是否是 < 开头的,如果是说明是标签起始标识,同理,需要 substring 来剔除已经处理过的字符。

  1. else if(html.indexOf("<")==0){
  2. match = html.match(startTag);
  3. if(match){
  4. chars = false;
  5. html = html.substring(match[0].length);
  6. match[0].replace(startTag, parseStartTag);
  7. }
  8. }

如果既不是起始标签,也不是截止标签,或者是不符合起始和截止标签的正则,我们统一当文本内容处理。

  1. if(chars){
  2. let index = html.indexOf('<');
  3. let text;
  4. if(index < 0){
  5. text = html;
  6. html = '';
  7. }else{
  8. text = html.substring(0,index);
  9. html = html.substring(index);;
  10. }
  11. const node = {
  12. node: 'text',
  13. text,
  14. };
  15. pushChild(node);
  16. }

如果是文本节点,我们则加入文本节点到目标 AST 上,我们着手 pushChild 方法,bufArray 是匹配起始和截止标签的临时数组,存放还没有找到截止标签的起始标签内容。

  1. function pushChild (node) {
  2. if (bufArray.length === 0) {
  3. results.child.push(node);
  4. } else {
  5. const parent = bufArray[bufArray.length - 1];
  6. if (typeof parent.child == 'undefined') {
  7. parent.child = [];
  8. }
  9. parent.child.push(node);
  10. }
  11. }

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

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

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

,即最后一个未匹配的节点。

在每一轮循环中,如果是符合预期,HTML 字符串会越来越少,直到被处理完成。

接下来我们来处理 parseStartTag 方法,也是稍微复杂一点的方法。

  1. function parseStartTag (tag, tagName, rest) {
  2. tagName = tagName.toLowerCase();
  3. const ds = {};
  4. const attrs = [];
  5. let unary = !!arguments[7];
  6. const node = {
  7. node: 'element',
  8. tag:tagName
  9. };
  10. rest.replace(attr, function (match, name) {
  11. const value = arguments[2] ? arguments[2] :
  12. arguments[3] ? arguments[3] :
  13. arguments[4] ? arguments[4] :'';
  14. if(name&&name.indexOf('data-')==0){
  15. ds[name.replace('data-',"")] = value;
  16. }else{
  17. if(name=='class'){
  18. node.class = value;
  19. }else{
  20. attrs.push({
  21. name,
  22. value
  23. });
  24. }
  25. }
  26. });
  27. node.dataset = ds;
  28. node.attrs = attrs;
  29. if (!unary){
  30. bufArray.push(node);
  31. }else{
  32. pushChild(node);
  33. }
  34. }

 

遇到起始标签,如果该起始标签不是一个结束标签(unary 为 true,如:,如果本身是截止标签,那么直接处理完即可),则将起始标签入栈,等待找到下一个匹配的截止标签。

我们接下来看下处理截止标签

  1. function parseEndTag (tag, tagName) {
  2. let pos = 0;
  3. for (pos = bufArray.length - 1; pos >= 0; pos--){
  4. if (bufArray[pos].tag == tagName){
  5. break;
  6. }
  7. }
  8. if (pos >= 0) {
  9. pushChild(bufArray.pop());
  10. }
  11. }

 

记录还未匹配到的起始标签的 bufArray 数组,从最后的数组位置开始查找,找到最近匹配的标签。

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

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

到此,一个简单的 AST 解析器已经完成了。

 

   
971 次浏览       20
相关文章

深度解析:清理烂代码
如何编写出拥抱变化的代码
重构-使代码更简洁优美
团队项目开发"编码规范"系列文章
相关文档

重构-改善既有代码的设计
软件重构v2
代码整洁之道
高质量编程规范
相关课程

基于HTML5客户端、Web端的应用开发
HTML 5+CSS 开发
嵌入式C高质量编程
C++高级编程

最新活动计划
UAF架构体系与实践 5-17[北京]
用户体验与界面设计 5-22[北京]
MBSE(基于模型的系统工程)6-20[北京]
大模型微调原理与实操 6-20[厦门]
图数据库与知识图谱 6-27[北京]
Linux内核编程及设备驱动 7-25[北京]
 
 
最新文章
.NET Core 3.0 正式公布:新特性详细解读
.NET Core部署中你不了解的框架依赖与独立部署
C# event线程安全
简析 .NET Core 构成体系
C#技术漫谈之垃圾回收机制(GC)
最新课程
.Net应用开发
C#高级开发技术
.NET 架构设计与调试优化
ASP.NET Core Web 开发
ASP.Net MVC框架原理与应用开发
成功案例
航天科工集团子公司 DotNet企业级应用设计与开发
日照港集 .NET Framewor
神华信 .NET单元测试
台达电子 .NET程序设计与开发
神华信息 .NET单元测试