Vue源码解读四:AST抽象语法树
SegmentFault
共 20708字,需浏览 42分钟
·
2021-09-03 23:35
1. 抽象语法树(AST)是什么?
模板语法先变成抽象语法树,然后再将语法树(主要起过渡作用)编译为正常的HTML语法。
vue 中使用模板语法所写的html结构,不是真正的dom,vue底层视作字符串,逐字审查字符串,解析为JS对象。
2. 抽象语法树和虚拟节点的关系?
那既然已经了解了AST是由模板语法得到的,那这个处理过程到底是怎么进行的呢?先从与此相关的最基本算法说起~
3. 相关算法储备
确定了i,j两指针位置后,就开始进行比较了,比较过程中如果i,j指向的字符相同,则i不动,j后移;否则将j此刻的值赋给i,j后移一位,说明在赋值之前,i,j之前的字符都是相同的;开启新一轮i,j是否相同的比较,比较的结束条件是i不小于这个字符串的长度length。
// 给定一个字符串
var str = 'aaaaaabbbbbbbcccccccccccccddddd';
// 设置两指针
var i = 0, j = 1;
// 记录重复最多次数
var maxRepeat = 0;
// 记录重复最多的字符;
var maxRepeatStr= '';
// 当i还在范围内的时候,应该继续寻找
while(i <= str.length - 1) {
// 看i指向的字符和j指向的字符是不是不相同
if (str[i] ==== str[j]) {
j++;
} else {
// console.log(i+'和'+j+'之间的文字连续相同,字母'+str[i]+'重复了'+ (j - i) + '次')
// 和当前重复次数最多的进行比较
if (j - i > maxRepeat) {
// 如果当前文字重复次数(j-i)超过了此时的最大值
// 就让它成为最大值
maxRepeat = j - i;
maxRepeatStr = str[i]
}
i = j;
j++;
}
}
// 循环结束之后,就可以输出答案了
console.log('maxRepeatChar', maxRepeatChar)
// 试输出斐波那契数列的前10项,即1、1、2、3、5、8、13、21、34、55
// 创建一个函数,功能是返回下标为n的这项的数字
// 递归需要有终点
function fib(n) {
console.log('fid-n:', n)
// 看下标n是不是0或1,如果是,返回常数1
// 如果不是,就递归
return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
}
for (var i = 0; i < 9; i++) {
console.log(fib(i))
}
所以优化以上的算法,在此引入一个缓存的概念,这样每次计算的值都进行缓存,再进行下次计算时只需要把缓存里的两项拿出来做计算就可以。
for(var i = 0; i < 10; i ++) {
console.log(fib(i));
}
// 定义一个缓存对象,用来存放已经计算的项
var cache = {};
function fib(n) {
// 判断缓存对象中有没有这个值,如果有,直接返回
if (cache.hasOwnProperty(n)) {
return cache[n]
}
// 缓存对象没有这个值
// 看下标n是不是0或1,如果是,返回常数1
// 如果不是,就递归
var v = (n === 0 || n === 1) ? 1 : fib(n -1) + fib(n - 2);
// 写入缓存,也就是说,每算一个值,就要把这个值存入缓存对象
cache[n] = v;
return v;
}
{
children: [
{value: 1},
{ value: 2},
{ children: [
{value: 3},
{ children: [
{ value: 4},
{ value: 5}
]},
{value: 6}
]},
{ value: 7},
{ children: [
{ value: 8},
{ value: 9}
]}
]
}
// 解法①
// 测试数组
var arr = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexI = 0;
// 转换函数
function convert(arr) {
indexI++;
// 准备一个结果数组
var result = [];
// 遍历传入的arr的每一项
for (var i = 0; i < arr.length; i++) {
// 如果遍历到的数字是number,直接放进去
if (typeof arr[i] == "number") {
result.push({value: arr[i]})
} else if (Array.isArray(arr[i])) {
// 如果遍历到的是数组,先建一个children
result.push({
children: convert(arr[i])
})
console.log('result:', result)
}
}
// console.log('result:', result)
return result;
}
var obj = convert(arr)
console.log(indexI) // 3
console.log(obj)
// 解法②
// 测试数组
var arr1 = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexJ = 0;
// 转换函数
// 即写法1的递归次数小于写法②,写法②中,遇见任何类型数据都要递归一下
function convert1(item) {
indexJ++;
if (typeof item == 'number') {
return {value: item}
} else if (Array.isArray(item)) {
// 如果传进来的参数是数组
return {
children: item.map(_item => convert1(_item))
}
}
}
var obj1 = convert1(arr1)
console.log(indexJ) // 12
console.log(obj1)
又名堆栈,它是一种运算受限的线性表,仅在表尾能进行插入和删除操作。这一端被称为栈顶,相对地,把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈;从一个栈删除元素又称作出栈或退栈。
后进先出(LIFO)特点:栈中的元素,最先进栈的必定最后出栈,后进栈的一定会先出栈。
JS中,栈可以用数组模拟。需要限制只能使用push()和pop(),不能使用unshift()和shift()。即数组尾是栈顶。
可以用面向对象等手段,将栈封装的更好。
栈栈和递归非常像
词法分析的时候,经常要用到栈这个数据结构
将3[2[a]2[b]]变为aabbaabbaabb
将2[1[a]3[b]2[3[c]4[d]]]变为abbbcccddddcccddddabbbcccddddcccdddd不用考虑输入字符串是非法的情况,比如:
[abc]是错误的,应该补一个1,即1[abc]
[
前的数字展开字符。结合栈的概念,那这个例子的解法思路是:
遍历每一个字符,如果是数字,那么就将该数字压入栈①;如果是
[
,就把空字符串压入栈②;如果是字母,就用这个字符替换栈②顶的空字符串;如果是
]
,就将栈①中的数字n弹栈,再把栈②中栈顶的字母重复n(这个数字)次数,从栈②中弹出,拼接到新栈②的顶上。
function smartRepeat(templateStr) {
let index = 0; // 指针
let stack1 = [], stack2 = []; // stack1存放数字,stack2存放临时字符串
var rest = templateStr; // 字符串剩余部分
while(index < templateStr.length - 1){ // 遍历
rest = templateStr.substring(index); // 剩余部分
if (/^\d+\[/.test(rest)){ // 看当前剩余部分是不是以数字和[开头
let times = Number(rest.match(/^(\d+)\[/)[1]); // 得到这个数字
stack1.push(times); // 就把数字压栈
stack2.push('') // 把空字符串压栈
index += times.toString().length + 1; // 让指针后移,times这个数字是多少位数,就后移多少位在加1
} else if (/^\w+]/.test(rest)){
// 如果是字母,那么此时就把栈顶这项改为这个字母
let word = rest.match(/^(\w+)\]/)[1];
stack2[stack2.length - 1] = word;
// 让指针后移,word这个数字是多少位数,就后移多少位在加1
index += word.length
} else {
// 如果这个字符是],那么就
// Ⅰ将stack1弹栈,就把字符串栈②的栈②顶的元素重复刚刚这个数字次数,
let times_pop = stack1.pop();
// Ⅱ弹栈②(stack2),
let word = stack2.pop();
// Ⅲ把字符串栈的新栈顶的元素重复刚刚弹出的那个字符串指定次数,拼接到新栈②顶上
// repeat 是es6的方法,比如'a'.repeat(3), 得到'aaa'
stack2[stack2.length - 1] += word.repeat(times_pop)
index += 1
}
}
// while结束之后,stack1和stack2中肯定还剩余1项。
// 返回栈2中剩下的这一项,重复栈1中剩下的这1项次数,组成这个字符串
// 如果剩的个数不对,那就是方括号]没有闭合
return stack2[0].repeat(stack1[0])
}
var str = smartRepeat('3[1[a]3[b]2[3[c]4[d]]]')
console.log(str) // abbbcccddddcccddddabbbcccddddcccddddabbbcccddddcccdddd
AST的形成
var templateString = `
<div class="box aa" id="mybox">
<h3>你好</h3>
<ul>
<li>A</li>
<li>B</li>
<li>C</li>
<li>D</li>
</ul>
</div>
`
var ast = parse(templateString)
console.log('ast:\n', ast)
parse.js
export default function (templateString) {
// 指针
var index = 0;
// 剩余部分
var rest = '';
// 开始标记
var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
// 结束标记
var endRegExp = /^\<\/([a-z]+[1-6]?)/;
// 准备两个栈;
var stack1 = [];
var stack2 = [{children: []}];
// 抓取结束标记前的文字
var wordRepExp = /^([^\<]+)\<\/[a-z]+[1-6]/
while (index < templateString.length - 1) {
rest = templateString.substring(index)
// console.log(templateString[index])
// 识别遍历到的这个字符,是不是一个开始标签
if (startRegExp.test(rest)) {
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2];
// console.log('检测到开始标记:', tag)
// 将开始标记推入栈中
stack1.push(tag)
stack2.push({children: [], tag: tag, attrs: parseAttrString(attrsString)})
// 指针移动标签的长度加2再加attrsString的长度,因为<>占两位
const attrLen = attrsString ? attrsString.length : 0;
index += tag.length + 2 + attrLen;
} else if (endRegExp.test(rest)) {
// 识别遍历到的字符,是不是结束标签
// 指针移动标签的长度加3,因为</>占三位
let tag = rest.match(endRegExp)[1];
// 此时tag一定是和stack1栈顶元素相同的
let pop_tag = stack1.pop();
if (tag == pop_tag) {
let pop_arr = stack2.pop();
if (stack2.length) {
// 检查stack2[stack2.length - 1]是否有children属性,如果没有就创建一个数组
stack2[stack2.length - 1].children.push(pop_arr)
}
} else {
throw new Error(stack1[stack1.length - 1] + '标签没有封闭')
}
// console.log('检测到结束标记:', tag)
index += tag.length + 3;
// console.log(stack1, JSON.stringify(stack2))
} else if (wordRepExp.test(rest)) {
// 识别遍历到的这个字符,是不是文字,并且不是全空
let word = rest.match(wordRepExp)[1];
// 看word是不是全是空
if (!/^\s+$/.test(rest)) {
// 不是空
// console.log('检测到文字-', word)
// 改变此时sctack2栈顶元素
stack2[stack2.length - 1].children.push({
'text': word,
'type': 3
})
}
// 指针移动标签的长度加字符长度
index += word.length;
} else {
// 标签中的文字
index++;
}
}
// console.log(stack2)
// 此时stack2就是我们之前默认放置的一项了,此时要返回这一项的children即可
return stack2[0].children[0];
}
parseAttrString.js
// 把attrsString 组装为数组之后返回
export default function (attrsString) {
if (!attrsString) return []
// console.log('attrsString', attrsString)
// 当前是否在引号内
var isYinhao = false;
// 断点
var point = 0;
// 结束数组
var result = [];
// 遍历attrsString,而不是用split()一个空格分隔
for (let i = 0; i < attrsString.length; i++) {
let char = attrsString[i];
if (char == '"') {
isYinhao = !isYinhao
} else if (char == ' ' && !isYinhao) {
// 遇见了空格,并且不在引号内
// console.log(i)
if (!/^\s*$/.test(attrsString.substring(point, i))) {
result.push(attrsString.substring(point, i).trim())
}
point = i;
}
}
// 循环结束之后,最后还剩一个属性k-v
result.push(attrsString.substring(point).trim())
// 下面的代码功能是:将["k=v","k=v", "k=v"]变为[{name: k, value: v}, {name: k, value: v}]这种类型
result = result.map(item => {
// 根据等号拆分
const o = item.match(/^(.+)="(.+)"$/);
return {
name: o[1],
value: o[2]
}
})
console.log(result)
return result
}
评论