目录
在计算机科学中，抽象
语法树（abstract syntax tree或者缩写为AST），或者语法树（syntax tree），是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。
我们可以理解为：把 template（模板）解析成一个对象，该对象是包含这个模板所以信息的一种数据，而这种数据浏览器是不支持的，为Vue后面的处理template提供基础数据。
JavaScript中的指针其实就是下标位置，下面以一个例子来使用指针思想。
寻找字符串中连续最多的字符
（如果i和j指向的字是一样的j不动，i后移，不一样说明之间 的字母是连续的让j追上i 后移）
let str = 'aaaaabbcccdd'
// 指针
let i = 0, j = 0, maxlen = 0, maxStr = '';
while (i <= str.length) {
if (str[i] != str[j]) {
console.log(`${j}和${i}之间的文字相同都是字符${str[j]}他们重复了${i - j}次`);
if (maxlen < i - j) {
maxlen = i - j
maxStr = str[j];
}
j = i
}
i++
}
console.log(maxStr);规则复现就要想到递归
试输出斐波那契数列第十项思考是否有重复计算（采用缓存的思路减少重复计算）
function fib(n) {
console.count('计数')
let v = n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
return v
}
let cache = {}
function fib2(n) {
console.count('计数')
// hasOwnProperty表示是否有自己的属性。这个方法会查找一个对象是否有某个属性，
if (cache.hasOwnProperty(n)) {
return cache[n]
}
let v = n == 0 || n == 1 ? 1 : fib2(n - 1) + fib2(n - 2)
cache[n] = v
return v
}
for (let i = 0; i <= 9; i++) {
fib2(i)
}
console.log(cache);
我们都知道数组是一种线性结构，并且可以在任意位置插入和删除数据。但是有时为了实现某些功能，我们必须对这种任意性加以限制。而栈和队列就是常见的受限的线性结构。
栈是一种受限的线性表，后进先出。其限制是仅允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端称为栈底。LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。向一个栈插入新元素又称为进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一个栈删除元素又称作出栈或退栈，它把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素
需求：实现一个“智能重复”函数，实现下面字符串的转换
将 2[abc] 转成 abcabc 将 2[1[a]2[b]] 转成 abbabb 将 2[1[a]2[3[b]4[c]]] 转成 abbbccccbbbccccabbbccccbbbcccc
思路：
1、定义两个栈（数组），栈1（stack1）、栈2（stack2），stack1用来存储数字，stack2用来存储字符串
2、定义一个指针（索引），默认从0开始
3、循环这个字符串，指针一直向后移动，直到指针等于字符串长度减1
4、获取当前指针指向的这个字符，然后进行判断
a）、如果是数字stack1中推入这个数字，stack2中推入一个空字符，指针继续向后移动
b）、如果是“[”什么都不做，指针继续向后移动
c）、如果是字符串将stack2栈顶项修改为该字符串，指针继续向后移动
d）、如果是“]”
function handleStr(str) {
let stack1 = [] // 存放数字
let stack2 = [''] // 存放字母
// 指针
let index = 0
while (index < str.length) {
// 剩余部分
let nowStr = str.substring(index)
// 以数字开头
if (/^\d+\[/.test(nowStr)) {
// 得到这个数字
let num = nowStr.match(/^(\d+)\[/)[1]
// 数字stack1中推入这个数字，stack2中推入一个空字符，指针继续向后移动
stack1.push(Number(num))
stack2.push('')
index += num.length + 1
} else if (/^\w+\]/.test(nowStr)) {
// 如果是字符串将stack2栈顶项修改为该字符串，指针继续向后移动
let word = nowStr.match(/^(\w+)\]/)[1]
stack2[stack2.length - 1] = word
index += word.length
} else if (nowStr[0] == ']') {
// stack1栈顶数字弹出，得到需要重复的次数
let num = stack1.pop()
// stack2栈顶字符串弹出
let subStr = stack2.pop()
// 将stack2栈顶项修改为：tack栈顶项 + 重复后的字符串
stack2[stack2.length - 1] += subStr.repeat(num)
index++
}
}
return stack2[0]
}
console.log(handleStr('2[1[a]2[b]]'));
有识别开始标签的正则表达式（识别a-z的小写字母和0-6数字组成的标签）
识别结束符号的正则表达式（识别闭合的标签）
识别文字的正则表达式（不考虑文字与标签同级的情况）
在while循环中遍历传入的字符串
定义两个栈，栈1和栈2。
当识别到一个开始的标签符号，那么就将这个标签入栈1，把空字符串入栈2。
当识别到的字符是标签内的文字，那么就将栈2栈顶这项改为文字。
当识别到结束标签，那么就将这个标签符号弹栈，就把栈2栈顶的元素push到栈二新的栈顶上的。
var templateString = `<div>
<h1>你好</h1>
<ul>
<li>a</li>
<li>b</li>
<li>c</li>
</ul>
</div>
`
function parse(templateString) {
//准备指针
var index = 0;
//剩余部分
var rest = '';
//开始标记
var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
//结束标签
var endRegExp = /^\<\/([a-z]+[1-6]?)\>/;
//识别文字
var wordRegExp = /^([^\<]+)\<\/([a-z]+[1-6]?)\>/;
//准备两个栈
var stack1 = [];
var stack2 = [{ 'children': [] }];
//遍历
while (index < templateString.length - 1) {
rest = templateString.substring(index);
//识别遍历到的这个字符，是不是一个开始标签
if (startRegExp.test(rest)) {
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2];
const attrsStringLength = attrsString != null ? attrsString.length : 0;
console.log("检测到开始标记", tag);
//将开始标记推入栈1中
stack1.push(tag);
//将空数组推入栈2 中
stack2.push({ 'tag': tag, 'children': [], 'attrs': parseAttrsString(attrsString) });
//指针移动标签的长度+2？因为<>也占两位
index += tag.length + 2 + attrsStringLength;
} else if (endRegExp.test(rest)) {
//识别这个字符是不是一个结束标签
//指针移动标签的长度加3，</>占三位
let tag = rest.match(endRegExp)[1];
console.log("检测到结束标记", tag);
//此时tag一定是和栈1顶部的是相同的
let pop_tag = stack1.pop();
if (tag == pop_tag) {
// 弹栈
let pop_arr = stack2.pop();
console.log(pop_arr);
if (stack2.length > 0) {
stack2[stack2.length - 1].children.push(pop_arr);
}
} else {
throw new Error(stack1[stack1.length - 1] + "标签没有封闭");
}
index += tag.length + 3;
console.log(stack1);
console.log(stack2);
} else if (wordRegExp.test(rest)) {
// 遍历到这个字符是不是文字
let word = rest.match(wordRegExp)[1];
if (!/^\s+$/.test(word)) {
// 不是全是空
console.log("检测到文字", word);
// 改变此时Stack2栈顶元素中
stack2[stack2.length - 1].children.push({ 'text': word, 'type': 3 });
}
index += word.length;
} else {
index++;
// 标签中的文字
}
}
// 此时stack2就是我们之前默认放置的一项了，此时要返回这一项的children即可
return stack2[0].children[0];
}
const ast = parse(templateString)
识别attrs
函数功能：将获取到的字符串attrs转换成数组对象的形式。
思路：利用引号和空格将其拆分。
首先遍历字符串，遇到引号后将其 isStr 属性设置成true，此时在引号内遇到空格不用管，当遇到下一个引号时设置 isStr 为false。此时在 isStr为false的情况下再遇见引号就将前面的字符串截取出来放入到数组中。
最后将数组里面的内容利用map进行拆分。
function parseAttrsString(attrsString) {
if (attrsString == undefined) return [];
// 当前是否在引号内
var isStr = false;
// 断点
var point = 0;
// 结果数组
var result = [];
// 遍历attrsString
for (let i = 0; i < attrsString; i++) {
let char = attrsString[i];
if (char == '"') {
isStr = !isStr;
} else if (char == ' ' && !isStr) {
// 遇见了空格，并且不在引号内
console.log(i);
if (!/^\s*$/.test(attrsString.substring(point, i))) {
result.push(attrsString.substring(point, i).trim());
point = i;
}
}
}
// 循环结束之后，最后还剩一个属性
result.push(attrsString.substring(point).trim());
result = result.map(item => {
// 根据等号拆分
const o = item.match(/^(.+)="(.+)$/);
return {
name: o[1],
name: o[2]
}
});
return result;
}