这是我参与更文挑战的第7天，活动详情查看： 更文挑战

简介

抽象语法树（Abstract Syntax Tree）本质上是一个 js 对象
抽象语法树和虚拟节点的关系，如下图：

相关算法储备

指针思想

指针就是下标位置
相关练习题：寻找字符串中连续重复次数最多的字符

// 寻找字符串中连续重复次数最多的字符
const str = 'aaaaaaaabbbbbbbbbbbbbbbbbcccccccccdddddd'
// start 和 end: 指针
let start = 0, end = 1, maxChar = str[0], maxCharLength = 0
// 当 start 指针在 str 长度范围内时进行循环
while (start < str.length){
  // 如果两个指针指向的字符不一样了，说明不是连续重复的字符了
  if (str[start] !== str[end]) {
    // 如果指针之差大于之前存储的最大的连续数
    if (end - start > maxCharLength) {
      maxCharLength = end - start
      maxChar = str[start]
    }
    // 让 start 指针直接追上 end 指针
    start = end
  }
  // 每次循环 end 指针都向后移动一位
  end++
}
console.log(maxChar, maxCharLength) // b 17

递归

凡是遇到“规则重复”，就要想到递归

斐波那契数列

相关练习题：用递归的方法输出斐波那契数列前 10 项

function fn(n) {
  console.count(n)
  return n === 0 || n === 1 ? 1 : fn(n-1) + fn(n-2)
}

for (let i = 0; i < 10; i++) {
  console.log(fn(i))
}

像上面这种解法，会有大量的重复执行，比如 fn(9) 的时候，会去执行 fn(8) 和 fn(7)，而执行 fn(8) 就会再执行一遍 fn(7)。为了避免这种重复的计算，我们可以用一个对象来缓存（cache）已经执行过的函数计算。如下：

// 设置一个缓存对象，用于存储 fn(n) 的值
let cache = {}
function fn(n) {
  console.count(n)
  // 如果 cache 有 n 属性
  if (cache.hasOwnProperty(n)) {
    return cache[n]
  } else { // cache 没有 n 属性，说明是第一次计算
    const v = n === 0 || n === 1 ? 1 : fn(n-1) + fn(n-2)
    cache[n] = v
    return v
  }
}
for (let i = 0; i < 10; i++) {
  console.log(fn(i))
}

形式转换

练习题：将数组 [1, 2, 3, [4, 5, [6, 7]], 8] 转为下图所示的对象格式

此题有 2 种解法
1. 递归数组
这种方法只有在遇到传给 convert 的参数为数组时，才递归

const arr = [1, 2, 3, [4, 5]]
function convert(arr) {
  let convertArr = []
  for (let i = 0; i < arr.length; i++) {
    if (typeof arr[i] === 'number') {
      convertArr.push({ 'value': arr[i] })
    } else if (Array.isArray(arr[i])) {
      convertArr.push({ 'children': convert(arr[i]) })
    }
  }
  return convertArr
}
const res = convert(arr)

2. 递归数组的子元素
这里巧妙的运用了 map 方法的特点，从而传递给 convert2 的参数无论是数组还是数字，都递归

const arr = [1, 2, 3, [4, 5]]
function convert2(item) {
  if (typeof item === 'number') {
    return { 'value': item }
  } else if (Array.isArray(item)) {
    return { 'children': item.map(_item => convert2(_item)) }
  }
}

const res = convert2(arr)

栈

练习题：将字符串 3[1[a]2[b]] 转换成 abbabbabb
这里就用到栈的思想，准备两个栈，一个存放数字，一个存放临时字符串，用一个指针遍历 3[1[a]2[b]]，

• 当指针指向的为数字时，就把数字压入数字栈中
• 当指针指向的为[时，就把一个空字符串压入字符串栈中
• 当指针指向的为字母时，就把字符串栈中栈顶的这一项改为这个字母
• 当指针指向的为]时，就把数字弹栈，字符串中栈顶的这项重复刚刚这个弹出的数字次数，弹栈，然后拼接到新栈顶

图示如下（这里没考虑数字或字母重复的情况，代码里会考虑进去）

代码实现

const str = '3[2[9abc]11[d]]'

// 指针
let i = 0
// 字符串从指针位置开始直至结束的部分
let restStr = str
// 存放数字的栈
const stackNum = []
// 存放字符串的栈
const stackStr = []

function smartRepeat(templateStr) {
  // 这里用 while 而不用 for 循环，因为 i 不一定每次都是 +1
  while (i < str.length - 1) { 
    /* 
    -1 是因为 str 最后一个必为 ]，如果不 -1，那么本例中当指针指到最后一个 ] 时，
    将对数字栈的栈顶，也是最后一个元素 3 进行出栈，
    然后是字符串栈的栈顶，也是最后一个元素 abcabcddddddddddd 进行出栈，然后重复 3 遍拼接到字符串栈的新栈顶，
    可是此时字符串栈已经没有元素了，新栈顶将是 undefined 
    */
    restStr = str.substring(i)
    // 如果是 数字 后面紧跟 [ 开头的字符串
    if (/^(\d+)\[/.test(restStr)) {
      // 捕获数字部分
      const nums = restStr.match(/^(\d+)\[/)[1]
      // 把数字压入数字栈
      stackNum.push(nums)
      // 把空字符串压入字符串栈
      stackStr.push('')
      // 指针跳过相应的长度，+1 是因为把 ] 一起跳过了  
      i += nums.length + 1
    } else if (/^(\w+)\]/.test(restStr)) { // 如果是 字母 后面紧跟 ] 开头的字符串
      // 捕获字母部分
      const str = restStr.match(/^(\w+)\]/)[1]
      // 将字符串栈的栈顶的那一项赋值为捕获的字母
      stackStr[stackStr.length - 1] = str
      // 直接跳过字母的长度
      i += str.length
    } else if (restStr[0] === ']') {
      // 对数字栈进行出栈操作
      const popNum = stackNum.pop()
      // 对字符串栈进行出栈
      const popStr = stackStr.pop()
      // 字符串拼接
      stackStr[stackStr.length - 1] += popStr.repeat(popNum)
      i++ 
    }
  }
  // while 循环结束，此时数字栈和字符串栈各自剩下最后一个元素，将 字符串 重复 数字 遍返回
  return stackStr[0].repeat(stackNum[0])
}
const result = smartRepeat(str)
console.log(result) // 9abc9abcddddddddddd9abc9abcddddddddddd9abc9abcddddddddddd

Tips：repeat是es6的字符串方法，构造并返回一个新字符串，该字符串包含被连接在一起的指定数量的字符串的副本。如果repeat的参数是字符串，则会先转换成数字。

手写实现 AST

原理

首先注意一点，平时在 .vue 文件里写在 template 里的看似 dom 的内容，事实上会经由 vue-loader 的解析，作为字符串提取处理。实现 AST 的原理根本上就是把一段字符串通过指针逐个遍历，根据不同情况进行不同的处理，进行一些栈操作，类似上文中栈里练习题。
比如，想要将如下代码转成 AST

<div>
  <h3>范特西</h3>
  <ul>
    <li>七里香</li>
  </ul> 
</div>

转换目标（AST）

{
  tag: "div", 
  children: [
    {
      tag: "h3", 
      children: [ { text: "范特西", type: 3 }], 
      type: 1,
    },
    {
      tag: "ul", 
      children: [
        {
          tag: "li", 
          children: [{ text: "七里香", type: 3 }], 
          type: 1,
        }
      ], 
      type: 1,
    }
  ], 
  type: 1
}

我们可以准备两个栈和一个用于遍历模板字符串的指针：

• 指针遇到标签则往一个栈（标签栈）中加入该标签名，另一个栈（数组栈）中加入一个空数组（代码里为了方便事实上是加入一个对象 { tag: startTag, children: [] }）
• 指针遇到文字则将数组栈中的栈顶的数组内容改为文字
• 指针遇到闭合标签则将标签栈和数组栈都进行出栈操作（数组栈出栈的内容就是标签栈出栈的标签的内容），然后将出栈的这两个元素组合下，拼接到数组栈的新栈顶的那个数组里。

动图示意如下

代码

// index.js
import parse from './parse.js'
const templateStr = `<div>
  <h3 id="legend" class="jay song">范特西</h3>
  <ul>
    <li>七里香</li>
  </ul> 
</div>`

const ast = parse(templateStr)
console.log(ast)

// parse.js
import parseAttrs from './parseAttrs.js'

export default function(templateStr) {
  // 准备一个指针
  let i = 0
  // 准备两个栈
  // 初始添加元素 { children: [] } 是因为如果不加， stackContent 在遇到最后一个封闭标签进行弹栈后，stackContent 里就没有元素了，也没有 .children 可以去 push 了
  const stackTag = [], stackContent = [{ children: [] }] 
  // 指针所指位置为开头的剩余字符串
  let restTemplateStr = templateStr
  // 识别开始标签的正则
  const regExpStart = /^<([a-z]+[1-6]?)(\s?[^>]*)>/

 while (i < templateStr.length - 1) {
  restTemplateStr = templateStr.substring(i)
  // 遇到开始标签
  if (regExpStart.test(restTemplateStr)) {
    const startTag = restTemplateStr.match(regExpStart)[1] // 标签
    const attrsStr = restTemplateStr.match(regExpStart)[2] // 属性
    // 标签栈进行压栈
    stackTag.push(startTag)
    // 内容栈进行压栈
    stackContent.push({
      tag: startTag,
      attrs: parseAttrs(attrsStr),
      type: 1,
      children: []
    })
    i += startTag.length + attrsStr.length  + 2 // +2 是因为还要算上 < 和 >
  } else if (/^<\/[a-z]+[1-6]?>/.test(restTemplateStr)) { // 遇到结束标签
    const endTag = restTemplateStr.match(/^<\/([a-z]+[1-6]?)>/)[1]
    // 结束标签应该与标签栈的栈顶标签一致
    if (endTag === stackTag[stackTag.length -1]) {
      // 两个栈都进行弹栈
      stackTag.pop()
      const popContent = stackContent.pop()
      stackContent[stackContent.length - 1].children.push(popContent)
      i += endTag.length + 3 // +3 是因为还要算上 </ 和 >
    } else {
      throw Error('标签' + stackTag[stackTag.length -1] + '没有闭合')
    }
  } else if (/^[^<]+<\/[a-z]+[1-6]?>/.test(restTemplateStr)) { // 遇到内容
    const wordStr = restTemplateStr.match(/^([^<]+)<\/[a-z]+[1-6]?>/)[1] // 捕获结束标签 </> 之前的内容，并且不能包括开始标签 <>
    if (!/^\s+$/.test(wordStr)) { // 如果捕获的内容不为空
      // 将内容栈栈顶元素进行赋值
      stackContent[stackContent.length - 1].children.push({
        text: wordStr,
        type: 3
      })
    }
    i += wordStr.length
  } else {
    i++
  }
 }
 // 因为定义 stackContent 的时候就默认添加了一项元素 { children: [] }，现在只要返回 children 的第一项就行 
 return stackContent[0].children[0]
}

为了处理标签内可能的属性，注意，我们截取每个属性的标准不是简单的判断空格，因为属性里可能有多个值，他们之间可能有空格，所以判断依据是不在双引号内的空格

// parseAttrs.js
export default function(attrsStr) {
  const attrsStrTrim = attrsStr.trim() // 去空格
  if (attrsStrTrim) {
    let point = 0 // 断点
    let isYinhao = false // 是否是引号
    let result = [] // 结果数组
    for (let index = 0; index < attrsStrTrim.length; index++) {
      if (attrsStrTrim[index] === '"') isYinhao = !isYinhao
      // 遇到空格且不在双引号内，就截取从 point 到此的字符串
      if (!isYinhao && /\s/.test(attrsStrTrim[index])) {
        const attrs = attrsStrTrim.substring(point, index)
        result.push(attrs)
        point = index
      }
    }
    result.push(attrsStrTrim.substring(point + 1)) // 最后一个属性是没有通过 for 循环得到的，所以要专门加上，+1 是为了去除开始的空格
    // ["id="legend"", "class="jay song""]
    result = result.map(item => {
      // 根据等号拆分
      const itemMatch = item.match(/(.+)="(.+)"/)
      return {
        name: itemMatch[1],
        value: itemMatch[2]
      }
    })
    return result
  } else {
    return []
  }
}

至此，本次分享的主要内容已经结束~

One More Thing

这里对上文代码中用到的 console.count() 和 hasOwnProperty() 做点补充说明

console.count()

首先，该特性是非标准的，请尽量不要在生产环境中使用它！
输出 count() 被调用的次数，接受一个可选参数 label，每次调用，如果标签一样，则对应的计数数字会增加 1，如果不一样则重新开始计数

hasOwnProperty()

用来检测一个对象是否含有特定的自身属性；
和 in 运算符不同，hasOwnProperty 会忽略掉那些从原型链上继承到的属性，
也就是上面的代码 if (cache.hasOwnProperty(n)) 其实也可以写成 if (n in cache)