Vue源碼解讀四：AST抽象語(yǔ)法樹(shù)
1. 抽象語(yǔ)法樹(shù)(AST)是什么？
模板語(yǔ)法先變成抽象語(yǔ)法樹(shù)，然后再將語(yǔ)法樹(shù)（主要起過(guò)渡作用）編譯為正常的HTML語(yǔ)法。
vue 中使用模板語(yǔ)法所寫(xiě)的html結(jié)構(gòu)，不是真正的dom，vue底層視作字符串，逐字審查字符串，解析為JS對(duì)象。
2. 抽象語(yǔ)法樹(shù)和虛擬節(jié)點(diǎn)的關(guān)系？
那既然已經(jīng)了解了AST是由模板語(yǔ)法得到的，那這個(gè)處理過(guò)程到底是怎么進(jìn)行的呢？先從與此相關(guān)的最基本算法說(shuō)起~
3. 相關(guān)算法儲(chǔ)備
確定了i，j兩指針位置后，就開(kāi)始進(jìn)行比較了，比較過(guò)程中如果i，j指向的字符相同，則i不動(dòng)，j后移；否則將j此刻的值賦給i，j后移一位，說(shuō)明在賦值之前，i，j之前的字符都是相同的；開(kāi)啟新一輪i，j是否相同的比較，比較的結(jié)束條件是i不小于這個(gè)字符串的長(zhǎng)度length。
// 給定一個(gè)字符串
var str = 'aaaaaabbbbbbbcccccccccccccddddd';
// 設(shè)置兩指針
var i = 0, j = 1;
// 記錄重復(fù)最多次數(shù)
var maxRepeat = 0;
// 記錄重復(fù)最多的字符；
var maxRepeatStr= '';
// 當(dāng)i還在范圍內(nèi)的時(shí)候，應(yīng)該繼續(xù)尋找
while(i <= str.length - 1) {
// 看i指向的字符和j指向的字符是不是不相同
if (str[i] ==== str[j]) {
j++;
} else {
// console.log(i+'和'+j+'之間的文字連續(xù)相同，字母'+str[i]+'重復(fù)了'+ (j - i) + '次')
// 和當(dāng)前重復(fù)次數(shù)最多的進(jìn)行比較
if (j - i > maxRepeat) {
// 如果當(dāng)前文字重復(fù)次數(shù)（j-i）超過(guò)了此時(shí)的最大值
// 就讓它成為最大值
maxRepeat = j - i;
maxRepeatStr = str[i]
}
i = j;
j++;
}
}
// 循環(huán)結(jié)束之后，就可以輸出答案了
console.log('maxRepeatChar', maxRepeatChar)
// 試輸出斐波那契數(shù)列的前10項(xiàng)，即1、1、2、3、5、8、13、21、34、55
// 創(chuàng)建一個(gè)函數(shù)，功能是返回下標(biāo)為n的這項(xiàng)的數(shù)字
// 遞歸需要有終點(diǎn)
function fib(n) {
console.log('fid-n:', n)
// 看下標(biāo)n是不是0或1，如果是，返回常數(shù)1
// 如果不是，就遞歸
return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2)
}
for (var i = 0; i < 9; i++) {
console.log(fib(i))
}
所以優(yōu)化以上的算法，在此引入一個(gè)緩存的概念，這樣每次計(jì)算的值都進(jìn)行緩存，再進(jìn)行下次計(jì)算時(shí)只需要把緩存里的兩項(xiàng)拿出來(lái)做計(jì)算就可以。
for(var i = 0; i < 10; i ++) {
console.log(fib(i));
}
// 定義一個(gè)緩存對(duì)象，用來(lái)存放已經(jīng)計(jì)算的項(xiàng)
var cache = {};
function fib(n) {
// 判斷緩存對(duì)象中有沒(méi)有這個(gè)值，如果有，直接返回
if (cache.hasOwnProperty(n)) {
return cache[n]
}
// 緩存對(duì)象沒(méi)有這個(gè)值
// 看下標(biāo)n是不是0或1，如果是，返回常數(shù)1
// 如果不是，就遞歸
var v = (n === 0 || n === 1) ? 1 : fib(n -1) + fib(n - 2);
// 寫(xiě)入緩存，也就是說(shuō)，每算一個(gè)值，就要把這個(gè)值存入緩存對(duì)象
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}
]}
]
}
// 解法①
// 測(cè)試數(shù)組
var arr = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexI = 0;
// 轉(zhuǎn)換函數(shù)
function convert(arr) {
indexI++;
// 準(zhǔn)備一個(gè)結(jié)果數(shù)組
var result = [];
// 遍歷傳入的arr的每一項(xiàng)
for (var i = 0; i < arr.length; i++) {
// 如果遍歷到的數(shù)字是number，直接放進(jìn)去
if (typeof arr[i] == "number") {
result.push({value: arr[i]})
} else if (Array.isArray(arr[i])) {
// 如果遍歷到的是數(shù)組，先建一個(gè)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)// 解法②
// 測(cè)試數(shù)組
var arr1 = [1,2, 3, [4, 5, [6, 7], 8], 9];
var indexJ = 0;
// 轉(zhuǎn)換函數(shù)
// 即寫(xiě)法1的遞歸次數(shù)小于寫(xiě)法②，寫(xiě)法②中，遇見(jiàn)任何類型數(shù)據(jù)都要遞歸一下
function convert1(item) {
indexJ++;
if (typeof item == 'number') {
return {value: item}
} else if (Array.isArray(item)) {
// 如果傳進(jìn)來(lái)的參數(shù)是數(shù)組
return {
children: item.map(_item => convert1(_item))
}
}
}
var obj1 = convert1(arr1)
console.log(indexJ) // 12
console.log(obj1)
又名堆棧，它是一種運(yùn)算受限的線性表，僅在表尾能進(jìn)行插入和刪除操作。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。
向一個(gè)棧插入新元素又稱作進(jìn)棧、入棧或壓棧；從一個(gè)棧刪除元素又稱作出棧或退棧。
后進(jìn)先出(LIFO)特點(diǎn)：棧中的元素，最先進(jìn)棧的必定最后出棧，后進(jìn)棧的一定會(huì)先出棧。
JS中，?？梢杂?span style="box-sizing: border-box;font-weight: bolder;">數(shù)組模擬。需要限制只能使用push()和pop()，不能使用unshift()和shift()。即數(shù)組尾是棧頂。
可以用面向?qū)ο蟮仁侄?，將棧封裝的更好。
棧棧和遞歸非常像
詞法分析的時(shí)候，經(jīng)常要用到棧這個(gè)數(shù)據(jù)結(jié)構(gòu)
將3[2[a]2[b]]變?yōu)閍abbaabbaabb
將2[1[a]3[b]2[3[c]4[d]]]變?yōu)閍bbbcccddddcccddddabbbcccddddcccdddd不用考慮輸入字符串是非法的情況，比如：
[abc]是錯(cuò)誤的，應(yīng)該補(bǔ)一個(gè)1，即1[abc]
[前的數(shù)字展開(kāi)字符。結(jié)合棧的概念，那這個(gè)例子的解法思路是：
遍歷每一個(gè)字符，如果是數(shù)字，那么就將該數(shù)字壓入棧①；如果是
[，就把空字符串壓入棧②；如果是字母，就用這個(gè)字符替換棧②頂?shù)目兆址?/span>如果是
]，就將棧①中的數(shù)字n彈棧，再把棧②中棧頂?shù)淖帜钢貜?fù)n(這個(gè)數(shù)字)次數(shù)，從棧②中彈出，拼接到新棧②的頂上。
function smartRepeat(templateStr) {
let index = 0; // 指針
let stack1 = [], stack2 = []; // stack1存放數(shù)字，stack2存放臨時(shí)字符串
var rest = templateStr; // 字符串剩余部分
while(index < templateStr.length - 1){ // 遍歷
rest = templateStr.substring(index); // 剩余部分
if (/^\d+\[/.test(rest)){ // 看當(dāng)前剩余部分是不是以數(shù)字和[開(kāi)頭
let times = Number(rest.match(/^(\d+)\[/)[1]); // 得到這個(gè)數(shù)字
stack1.push(times); // 就把數(shù)字壓棧
stack2.push('') // 把空字符串壓棧
index += times.toString().length + 1; // 讓指針后移，times這個(gè)數(shù)字是多少位數(shù)，就后移多少位在加1
} else if (/^\w+]/.test(rest)){
// 如果是字母，那么此時(shí)就把棧頂這項(xiàng)改為這個(gè)字母
let word = rest.match(/^(\w+)\]/)[1];
stack2[stack2.length - 1] = word;
// 讓指針后移，word這個(gè)數(shù)字是多少位數(shù)，就后移多少位在加1
index += word.length
} else {
// 如果這個(gè)字符是]，那么就
// Ⅰ將stack1彈棧，就把字符串棧②的棧②頂?shù)脑刂貜?fù)剛剛這個(gè)數(shù)字次數(shù)，
let times_pop = stack1.pop();
// Ⅱ彈棧②(stack2)，
let word = stack2.pop();
// Ⅲ把字符串棧的新棧頂?shù)脑刂貜?fù)剛剛彈出的那個(gè)字符串指定次數(shù)，拼接到新棧②頂上
// repeat 是es6的方法，比如'a'.repeat(3), 得到'aaa'
stack2[stack2.length - 1] += word.repeat(times_pop)
index += 1
}
}
// while結(jié)束之后，stack1和stack2中肯定還剩余1項(xiàng)。
// 返回棧2中剩下的這一項(xiàng)，重復(fù)棧1中剩下的這1項(xiàng)次數(shù)，組成這個(gè)字符串
// 如果剩的個(gè)數(shù)不對(duì)，那就是方括號(hào)]沒(méi)有閉合
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 = '';
// 開(kāi)始標(biāo)記
var startRegExp = /^\<([a-z]+[1-6]?)(\s[^\<]+)?\>/;
// 結(jié)束標(biāo)記
var endRegExp = /^\<\/([a-z]+[1-6]?)/;
// 準(zhǔn)備兩個(gè)棧；
var stack1 = [];
var stack2 = [{children: []}];
// 抓取結(jié)束標(biāo)記前的文字
var wordRepExp = /^([^\<]+)\<\/[a-z]+[1-6]/
while (index < templateString.length - 1) {
rest = templateString.substring(index)
// console.log(templateString[index])
// 識(shí)別遍歷到的這個(gè)字符，是不是一個(gè)開(kāi)始標(biāo)簽
if (startRegExp.test(rest)) {
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2];
// console.log('檢測(cè)到開(kāi)始標(biāo)記:', tag)
// 將開(kāi)始標(biāo)記推入棧中
stack1.push(tag)
stack2.push({children: [], tag: tag, attrs: parseAttrString(attrsString)})
// 指針移動(dòng)標(biāo)簽的長(zhǎng)度加2再加attrsString的長(zhǎng)度，因?yàn)?lt;>占兩位
const attrLen = attrsString ? attrsString.length : 0;
index += tag.length + 2 + attrLen;
} else if (endRegExp.test(rest)) {
// 識(shí)別遍歷到的字符，是不是結(jié)束標(biāo)簽
// 指針移動(dòng)標(biāo)簽的長(zhǎng)度加3，因?yàn)?lt;/>占三位
let tag = rest.match(endRegExp)[1];
// 此時(shí)tag一定是和stack1棧頂元素相同的
let pop_tag = stack1.pop();
if (tag == pop_tag) {
let pop_arr = stack2.pop();
if (stack2.length) {
// 檢查stack2[stack2.length - 1]是否有children屬性，如果沒(méi)有就創(chuàng)建一個(gè)數(shù)組
stack2[stack2.length - 1].children.push(pop_arr)
}
} else {
throw new Error(stack1[stack1.length - 1] + '標(biāo)簽沒(méi)有封閉')
}
// console.log('檢測(cè)到結(jié)束標(biāo)記:', tag)
index += tag.length + 3;
// console.log(stack1, JSON.stringify(stack2))
} else if (wordRepExp.test(rest)) {
// 識(shí)別遍歷到的這個(gè)字符，是不是文字，并且不是全空
let word = rest.match(wordRepExp)[1];
// 看word是不是全是空
if (!/^\s+$/.test(rest)) {
// 不是空
// console.log('檢測(cè)到文字-', word)
// 改變此時(shí)sctack2棧頂元素
stack2[stack2.length - 1].children.push({
'text': word,
'type': 3
})
}
// 指針移動(dòng)標(biāo)簽的長(zhǎng)度加字符長(zhǎng)度
index += word.length;
} else {
// 標(biāo)簽中的文字
index++;
}
}
// console.log(stack2)
// 此時(shí)stack2就是我們之前默認(rèn)放置的一項(xiàng)了，此時(shí)要返回這一項(xiàng)的children即可
return stack2[0].children[0];
}
parseAttrString.js
// 把a(bǔ)ttrsString 組裝為數(shù)組之后返回
export default function (attrsString) {
if (!attrsString) return []
// console.log('attrsString', attrsString)
// 當(dāng)前是否在引號(hào)內(nèi)
var isYinhao = false;
// 斷點(diǎn)
var point = 0;
// 結(jié)束數(shù)組
var result = [];
// 遍歷attrsString，而不是用split()一個(gè)空格分隔
for (let i = 0; i < attrsString.length; i++) {
let char = attrsString[i];
if (char == '"') {
isYinhao = !isYinhao
} else if (char == ' ' && !isYinhao) {
// 遇見(jiàn)了空格，并且不在引號(hào)內(nèi)
// console.log(i)
if (!/^\s*$/.test(attrsString.substring(point, i))) {
result.push(attrsString.substring(point, i).trim())
}
point = i;
}
}
// 循環(huán)結(jié)束之后，最后還剩一個(gè)屬性k-v
result.push(attrsString.substring(point).trim())
// 下面的代碼功能是：將["k=v","k=v", "k=v"]變?yōu)閇{name: k, value: v}, {name: k, value: v}]這種類型
result = result.map(item => {
// 根據(jù)等號(hào)拆分
const o = item.match(/^(.+)="(.+)"$/);
return {
name: o[1],
value: o[2]
}
})
console.log(result)
return result
}
評(píng)論
圖片
表情