Vue源码解读四：AST抽象语法树

本文基于模板引擎，结合虚拟DOM的探讨。根据三者的关系总结如下图：graphTDA[templatesyntax]-->|Analysis|B(抽象语法树AST)B-->|Call|C[渲染函数是h函数]C-->|生成|D[虚拟节点差异/补丁]D-->|更新|E（接口）1.什么是抽象语法树（AST）？AbstractSyntaxTree，抽象语法树（简称：AST）本质上是一个js对象。先将模板语法转为抽象语法树，再将语法树（主要起过渡作用）编译成普通的HTML语法。vue中使用模板语法编写的html结构并不是真正的dom。vue底层把字符串看成字符串，逐字逐句地审核字符串，解析成JS对象。2、抽象语法树和虚拟节点是什么关系？如上图所示，模板语法->抽象语法树AST->渲染函数(h函数)->虚拟节点-(diff/patch)>接口，现在我们已经明白了AST是从模板语法中获取的，那么这个过程是如何进行的？先从和这个相关的最基本的算法说起吧~3.相关算法储备1).指针思维（JS中的指针只是字符串或数组的下标位置，与C语言中的指针不同，我再说一句，C语言中的指针是可以操作内存的）这里是一个体验指针在js中应用的算法实例：在字符串aaaaaabbbbbbbccccccccccccccdddd'中找到连续重复次数最多的字符。在求解这个算法的时候，既然有“最”，就必须要进行比较，而且至少要有两个对象进行比较，所以我们首先要想到的是需要设置两个指针，如何确定这两个指针的位置两个指针毛呢布？再看题目是“连续”，所以两个指针的初始位置一定是相邻的，如下图所示：确定了两个指针i和j的位置后，开始比较。比较时，如果i和j指向的字符相同，则i不动，j向后移动；否则，此时将j的值赋给i，j向后移动一位，表示赋值前，i和j之前的字符相同；开始新一轮的i,j是否相同比较，比较的结束条件是i不小于这个字符串的长度。分析完解题思路，代码就很容易写了：//给定一个字符串varstr='aaaaaabbbbbbbccccccccccccccdddddd';//设置两个指针vari=0,j=1;//记录最大数ofrepetitionsvarmaxRepeat=0;//记录重复次数最多的字符；varmaxRepeatStr='';//当i还在范围内时，继续查找while(i<=str.length-1){//看i和j指向的字符是不是指向的字符不同if(str[i]====str[j]){j++;}else{//控制台。+str[i]+'repeated'+(j-i)+'times')//与当前重复次数最多的比较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的项的个数//递归需要有一个结束函数fib(n){console.log('fid-n:',n)//检查下标n是0还是1，如果是，返回常量1//如果不是，递归返回n==0||n==1？1:fib(n-1)+fib(n-2)}for(vari=0;i<9;i++){console.log(fib(i))}这样做的内存开销非常大，也就是说每次计算都需要重新计算前两项，所以优化了上面的算法，这里引入了一个缓存的概念，让每次计算的值都缓存起来，下次计算只需要可以取出缓存中的两项进行计算。for(vari=0;i<10;i++){console.log(fib(i));}//定义一个缓存对象来存储计算的项varcache={};functionfib(n){//检查缓存对象中是否有这个值，有则直接返回if(cache.hasOwnProperty(n)){returncache[n]}//缓存对象没有这个值//看下标n是0或1，如果是，返回常量1//如果不是，递归varv=(n===0||n===1)?1:fib(n-1)+fib(n-2);//写入缓存，也就是说，每计算一个值，这个值都要存入缓存对象中cache[n]=v;returnv;}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进行存储，然后按照这个规则对自身中的数和数组进行处理，直到没有数组为止。通常的做法是将这个数组作为一个整体进行递归：//解决方案①//测试数组vararr=[1,2,3,[4,5,[6,7],8],9];varindexI=0;//转换函数functionconvert(arr){indexI++;//准备一个结果数组varresult=[];//遍历传入的arr的每一项for(vari=0;iconvert1(_item))}}}varobj1=convert1(arr1)console.log(indexJ)//12console.log(obj1)4)Stack，也称栈，是一个有限操作的线性表。只有表尾可以进行插入和删除的一端称为栈顶，相反，另一端称为栈底。向栈中插入新元素也称为压入、压入或压入；从堆栈中删除元素也称为入栈或出栈。后进先出（LIFO）特点：在栈中的元素中，最先进的必须最后出栈，最后入栈的必须先出栈。在JS中，栈可以用数组来模拟。有必要限制使用push()和pop()，而不是unshift()和shift()。也就是说，数组的末尾是堆栈的顶部。可以使用面向对象的方法来更好地封装堆栈。栈和递归很像词法分析，经常使用栈的数据结构来尝试写出“智能重复”smartRepeat函数，实现：把3[abc]改成abcabcabc，把3[2[a]2[改成b]]Change2[1[a]3[b]2[3[c]4[d]]]intoaabbaabbaabbintoabbbcccddddcccddddabbbcccddddcccddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddciftheinputstringisillegal,forexample:2[a3[b]]isanerror是的，应该加一个1，即2[1[a]3[b]][abc]是错误的，应该加一个1，即1[abc]看到这个题目，是不是有点像上面的指针示例？来回呼应，指针的例子是找重复的字符，这个例子是根据[前的数字扩展字符。结合栈的概念，本例的解决方案是：遍历每一个字符，如果是数字，则将该数字压入栈①；如果是[，则将空串入栈②；如果是字母，就用这个字符代替栈顶的空串②；如果是]，将栈①中的数字n弹出入栈，然后在栈②中重复栈顶的字母n（这个数）次，从栈中弹出②，拼接上新栈顶②。函数smartRepeat(templateStr){让索引=0;//指针让stack1=[],stack2=[];//stack1存储数字，stack2存储临时字符串varrest=templateStr;//剩下的字符串while(index

Hello

• A
• B
• C
• D