本篇内容是在模板引擎的根底上，联合虚构DOM进行的探讨，基于三者之间的关系，总结出下图示意：
graph TD A[模板语法] -->|解析| B(形象语法树AST) B --> |调用|C[渲染函数即h函数] C -->|生成| D[虚构节点diff/patch] D --> |更新| E(界面)1. 形象语法树(AST)是什么？
形象语法树，Abstract Syntax Tree(简称：AST)实质上就是一个js对象。
模板语法先变成形象语法树，而后再将语法树（次要起过渡作用）编译为失常的HTML语法。
vue 中应用模板语法所写的html构造，不是真正的dom，vue底层视作字符串，逐字审查字符串，解析为JS对象。
2. 形象语法树和虚构节点的关系？
如前文图示，模板语法->形象语法树AST->渲染函数（h函数）->虚构节点-(diff/patch)>界面
那既然曾经理解了AST是由模板语法失去的，那这个处理过程到底是怎么进行的呢？先从与此相关的最根本算法说起~
3. 相干算法储备
1). 指针思维(JS中的指针只是字符串或者数组的一个下标地位，不同于C语言中的指针，多说一句，C语言中的指针是能够操作内存的)
在此列一个算法例子，领会指针在js中的利用：找出字符串aaaaaabbbbbbbcccccccccccccddddd'中，间断反复呈现次数最多的字符。
在解这个算法的时候，既然有“最多”，那必然是有比拟，而比拟的对象至多得有两个，因而首先就要想到咱们须要设置两个指针，而这两个指针的地位如何确定呢？再一看题目是“间断”，所以两指针的初始地位必然是相邻的，如下图：
确定了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)2)递归深刻-即规定复现
同上列举一个例子，领会递归的运算效率：试输入斐波那契数列的前10项，即1、1、2、3、5、8、13、21、34、55。而后请思考，代码是否有大量反复的计算？应该如何解决反复计算？
察看推理得出，这一列数字从第三项起都是本身得前两项之和，所以每次只有前两项相加即可，高级代码如下：
// 试输入斐波那契数列的前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;}3)递归的深刻用法(离最终的AST算法越来越靠近了~)
试将高维数组[1, 2, [3, [4, 5], 6], 7, [8], 9]变为图中所示的对象
{ children: [ {value: 1}, { value: 2}, { children: [ {value: 3}, { children: [ { value: 4}, { value: 5} ]}, {value: 6} ]}, { value: 7}, { children: [ { value: 8}, { value: 9} ]} ]}这个算法是将多维数组解决为一个对象，从第一层去遍历，如果是数字，则存为对象，若是数组，则存为该层的一个子级chldren，再依照此法则解决本人里边的数字，数组，直到再没有数组为止。通常的做法是将这个数组作为整体去递归：
// 解法①// 测试数组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) // 3console.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) // 12console.log(obj1)4)堆栈
- 又名堆栈，它是一种运算受限的线性表，仅在表尾能进行插入和删除操作。这一端被称为栈顶，绝对地，把另一端称为栈底。
- 向一个栈插入新元素又称作进栈、入栈或压栈；从一个栈删除元素又称作出栈或退栈。
- 后进先出(LIFO)特点：栈中的元素，最先进栈的必然最初出栈，后进栈的肯定会先出栈。
- JS中，栈能够用数组模仿。须要限度只能应用push()和pop()，不能应用unshift()和shift()。即数组尾是栈顶。
- 能够用面向对象等伎俩，将栈封装的更好。
- 栈栈和递归十分像
- 词法剖析的时候，常常要用到栈这个数据结构
试编写“智能反复”smartRepeat函数，实现：
将3[abc]变为abcabcabc
将3[2[a]2[b]]变为aabbaabbaabb
将2[1[a]3[b]2[3[c]4[d]]]变为abbbcccddddcccddddabbbcccddddcccdddd
不必思考输出字符串是非法的状况，比方：
2[a3[b]]是谬误的，应该补一个1，即2[1[a]3[b]]
[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) // abbbcccddddcccddddabbbcccddddcccddddabbbcccddddcccddddAST的造成
有了后面四局部的铺垫，根本把握了AST所须要的算法及数据结构，上面给出一个模板字符串(相当于vue种template中的模板)
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函数就是将模板解析为AST，最终返回AST，解析过程和上例基本相同：
parse.jsexport 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];}在这个AST的合成过程，还有一个不能疏忽的细节是：标签所带的属性，如class，id等，所以parseAttrString函数中就是对标签属性的解决：
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}