AST 抽象语法树
抽象语法树的本质就是一个 JS 对象;
对象包含 tag attrs type children 等属性;
模板语法–>转成字符串–>转成 AST 语法树
模板语法—>正常的 HTML 语法(算法编写难度极大)
模板语法—>抽象语法树—->正常的 HTML 语法(算法编写难度较小)
抽象语法树和虚拟节点的关系
模板语法–>抽象语法树–>渲染函数(h 函数)–>虚拟节点—经过 diff—>界面
学习内容
- 相关算法储备
- AST 形成算法
- 手写 AST 编译器
- 手写文本解析功能
- AST 优化
- 将 AST 生成 h 函数
算法储备
指针思想
寻找字符串中,连续重复次数最多的字符串 “aaaaaabbbbbbbbcccccccccccccccddddddd”;
/**
* 寻找字符串中,连续重复次数最多的字符串 "aaaaaabbbbbbbbcccccccccccccccddddddd";
* 指针就是下标(不是C语言的指针,c语言的指针可以操作内存)
* i:0; j:0
*
* aaaaaabbbbbbbbcccccccccccccccddddddd
* i j
* 指针移动规律: (不管怎么样j都要后移,)
* 如果i和j指向的字一样,那么i不动,j后移
* 如果i和j指向的字不一样,此时说明他们之间的字都是连续相同的(统计一下j和i的差距,就是当前差距的字符数量),让i追上j,j后移,直到i是否还在范围内,不在范围内就循环结束了
*
*/
window.ZhiZhen = function (str) {
// 指针
var i = 0;
var j = 1;
// 字符串
var str = "aaabbbbccccc";
// 记录当前存的出现次数多的字符
var word = "";
// 记录当前存的出现次数多的字符的数量
var count = 0;
while (i < str.length - 1) {
if (str[i] != str[j]) {
if (count < j - i) {
count = j - i;
word = str[i];
}
i = j;
}
j++;
}
return word;
};
递归深入
斐波那契
试着输出斐波那契数列的前 10 项.即 1 1 2 3 5 8 13 21 34 55
思考代码是否有大量重复的计算?
应该如何的解决重复计算的问题?
/**
* 试着输出斐波那契数列的前10项.即1 1 2 3 5 8 13 21 34 55
* 思考代码是否有大量重复的计算?
* 应该如何的解决重复计算的问题?
*/
var cache = {}; // 缓存对象
window.DiGuiShenRu = function fib(n) {
// 方法1. 基本写法(存在大量的重复计算,每次计算都是要找到最底层的1)
// return n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2); // 如果是0 1 那么就返回1; 如果不是就递归
// 方法2. cache思想(把之前的计算都记下来)
// {
// fib(0): 1,
// fib(1): 1,
// fib(2): 2,
// fib(3): 3,
// fib(4): 5,
// }
// 判断缓存对象是否有,有直接用,没有才计算
if (cache.hasOwnProperty(n)) {
return cache[n];
} else {
// 缓存对象没有这个值,看下标如果是0 1 那么就返回1; 如果不是就递归
var v = n == 0 || n == 1 ? 1 : fib(n - 1) + fib(n - 2);
cache[n] = v;
return v;
}
};
形式转换(高维数组)
写法 1 的递归次数是要远远大于写法 2 的,因为写法 1 遇到任何东西都要递归一次
// 形式转换
// 试着将高维数组[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 }],},
// ];
// }
window.XingShiZhuanHuan = function arrayMethod() {
// 写法 1
function convert1(arr) {
// 准备一个结果数组
var result = [];
for (let i = 0; i < arr.length; i++) {
const element = arr[i];
// 如果是数字number,那么就直接推入
if (typeof element == "number") {
result.push({ value: element });
// 如果是数组,那么就继续循环递归
} else if (Array.isArray(arr)) {
result.push({
children: convert1(element),
});
}
}
return result;
}
// return convert1([1, 2, [3, [4, 5], 6], 7, [8, 9]])
// 写法 2 (映射 map)
// 参数不再是arr,而是item,意味着itme可能是数字也可能是数组
function convert2(item) {
// 如果传进来的是数字
if (typeof item == "number") {
return { value: item };
} else if (Array.isArray(item)) {
// 如果传进来的是数组
return {
children: item.map((_item) => convert2(_item)),
};
}
}
return convert2([1, 2, [3, [4, 5], 6], 7, [8, 9]]);
};
栈
栈(stack)又名堆栈,他是运算受限的线性表,仅在表尾能进行插入和删除操作。这一端被称为栈顶。相对的把另一端称为栈底。
向一个栈插入新元素。又称作进栈，入栈或压栈。从一个栈删除元素又称作出栈或退栈。
后进先出(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
*
* 实现思路:
* 两个栈: 一个数字栈,一个字符串栈
* 遍历每一个字符,
* 1. 如果这个字符是个数字,那么就把数字压栈,把空字符压栈
* 2. 如果这个字符是个字母,那么此时就把栈顶这项改为这个字母
* 3. 如果这个字符是个],那么就将这个数字弹栈,就把字符串这个栈的栈顶的元素,重复刚刚的这个次数,拼接到栈的新栈顶上
* 正则表达式的相关方法
*/
window.smartRepeat = function (templateStr) {
// 指针
var index = 0;
// 栈1 存放数字
var stack1 = [];
// 栈2 存放临时字符串
var stack2 = [];
// 剩余部分
var rest = templateStr;
while (index < templateStr.length - 1) {
// 剩余部分
rest = templateStr.substring(index);
// 看当前的剩余部分是不是数字和[开头
if (/^\d+\[/.test(rest)) {
// 得到这个数字
let times = rest.match(/^(\d+)\[/)[1] - 0;
// 把数组和空字符压栈
stack1.push(times);
stack2.push("");
// 让指针后移,times是多少位往后移动多少位加1位
// 加一位是为了让[也移动一位
index += times.toString().length + 1;
} else if (/^\w+\]/.test(rest)) {
// 如果这个字符是字母,那么此刻就把栈顶这项改为这个字母
let word = rest.match(/^(\w+)\]/)[1];
// console.log(word);
stack2[stack2.length - 1] = word;
// 让指针后移,word 是多少位往后移动多少位
index += word.length;
} else if (rest[0] == "]") {
// 如果这个字符是],
// 1. 那么就将 stack1 的最后一项 A 弹栈,
// 2. 把 stack2 的最后一项 B 弹栈
// 3. 把 A 重复 B 次数 得到 C , 然后把 stack2 新栈顶的数据拼上 C
let times = stack1.pop();
let word = stack2.pop();
stack2[stack2.length - 1] += word.repeat(times);
index++;
}
// while结束之后,stack1 和 stack2 中肯定还剩余一项,如果剩余的个数不对,那么就是用户的问题,方括号没有闭合等原因
}
return stack2[0].repeat(stack1[0]);
};
正则表达式的相关方法
search 加 g 不加都一样
// 替换所有数字为空字符
'123大中小abc'.replace(/\d/g, '') // 返回 '大中小abc'
// 返回了第一个数字的下标
'123大中小abc'.search(/\d/) // 返回0
// 返回了第一个数字的下标
'123大中小abc'.search(/\d/g) // 返回0
'123大中小abc'.match(/\d/) // ['1', index: 0, input: '123大中小abc', groups: undefined]
'123大中小abc'.match(/\d/g) // ['1', '2', '3']
/^\d/.test('abc') // false
/^\d/.test('123abc') // true
'34[abc]'.match(/^\d+\[/) // ['34[', index: 0, input: '34[abc]', groups: undefined]
// 加个括号可以捕获,显示在返回的第一项
'34[abc]'.match(/^(\d+)\[/) // ['34[', '34', index: 0, input: '34[abc]', groups: undefined]
手写 AST 抽象语法树源码
-
独立功能拆分为 js 文件,独立类,每个模块可以单元测试
-
先完成主干,然后修剪枝叶
思路: 和上一个思路相似,
-
就是两个栈,一个 栈 A 存标签,一个 栈 B 存标签里面的内容,
-
遇到标签进 A, 同时 B 也需要一个进一个数组([]是了放内容,是 AST 语法树的格式,内容放到数组内,我们上个例子是搞个字符串,这里和哪里用法一样),
-
遇到内容, 就把这个内容放到进 B 的最后一个数组内 组成 C([我是内容]),
-
遇到结束标签,就把 C 和 A 的最后一起拿出来,把 C 以 children 的形式标记到 A 的最后一个标签上组成 D,然后把 D 存到 B 的最后一个数组内
parse.js
import parseAttrsString from "./parseAttrsString.js";
export default function (templateStr) {
// 指针
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 < templateStr.length - 1) {
rest = templateStr.substring(index);
// console.log(templateStr[index]);
// 识别遍历到的这个字符是不是开始标签
if (startRegExp.test(rest)) {
let tag = rest.match(startRegExp)[1];
let attrsString = rest.match(startRegExp)[2]; // 也就是获取属性的内容 class="box" id="mybox"
// console.log("检测到 Start 标记", tag);
// 将开始标记推入 stack1
stack1.push(tag);
// 将空数组推入 stack2
stack2.push({
tag: tag,
children: [],
attrs: parseAttrsString(attrsString),
});
// 指针移动标签的长度+2,因为<>也占了两位, 再加上 attrsString 的长度
const attrsStringLength = attrsString != null ? attrsString.length : 0;
index += tag.length + 2 + attrsStringLength;
} else if (endRegExp.test(rest)) {
// 识别遍历到的这个标签是不是一个结束标签
let tag = rest.match(endRegExp)[1];
// 指针移动标签的长度+2,因为</>也占了三位
// console.log("检测到 End 标记", tag);
let pop_tag = stack1.pop();
// 此时 tag 一定是和 stack1 顶部是相同的
if (tag == pop_tag) {
let pop_arr = stack2.pop();
if (stack2.length > 0) {
stack2[stack2.length - 1].children.push(pop_arr);
}
} else {
throw new Error(pop_tag + " 标签没有封闭");
}
index += tag.length + 3;
} else if (wordRegExp.test(rest)) {
// 识别遍历到的这个标签是不是文字,并且不能是全空的文字
let word = rest.match(wordRegExp)[1];
// 看word是不是全是空,
if (!/^\s+$/.test(word)) {
// 不是全是空
// console.log("检测到 Word 内容", word);
// 改变此时 stack2 的栈顶的数据
stack2[stack2.length - 1].children.push({ text: word, type: 3 });
}
index += word.length;
} else {
// 这里就是标签中的文字
index++;
}
}
return stack2[0].children;
}
parseAttrsString.js
/**
*把 attrsString 变成数组返回
* class="box id="mybox
* 返回成
* [{name: class, value: box},{name: id, value: mybox]
*
* 关于空格删除的问题,我们需要考虑这个是没用的空格,还是在引号内的空格,引号内的需要留下,外的需要干掉
* class="aa bb cc" id="dd"
* 1. 需要一个变量 isInYinHao = false 遍历上面的字符,一直往下走,
* 2. 走到奇数个数的引号,就把 isInYinHao = true, 在走到偶数个数的引号,就 isInYinHao = false,
* 3. 然后当 true的时候遇到了空格,那说明是属性里的,留下,false时候遇到了就删除这个空格
*
*/
export default function (attrsString) {
if (attrsString === undefined) {
return [];
}
console.log(attrsString);
let isInYinHao = false; // 当前是否在引号内
let ponit = 0; // 断点
let resultArr = [];
for (let i = 0; i < attrsString.length; i++) {
const char = attrsString[i];
if (char === '"') {
isInYinHao = !isInYinHao;
} else if (char === " " && !isInYinHao) {
// 遇到了空格,并且不在引号内
console.log(i);
if (!/^\s*$/.test(attrsString.substring(ponit, i))) {
resultArr.push(attrsString.substring(ponit, i).trim());
ponit = i;
}
}
}
// 循环结束还会剩一个的
resultArr.push(attrsString.substring(ponit));
// *把 attrsString 变成数组返回
// * class="box id="mybox
// * 返回成
// * [{name: class, value: box},{name: id, value: mybox]
// *
resultArr = resultArr.map((item) => {
// 根据等号拆分
const o = item.match(/^(.+)="(.+)"$/);
return {
name: o[1],
value: o[2],
};
});
return resultArr;
}
用法
import parse from "./parse.js";
var templateStr = `<div>
<h3 class="aa bb" id="mybox">你好</h3>
<ul>
<li>A</li>
</ul>
</div>`;
const ast = parse(templateStr);
console.log(ast);
// [
// {
// "tag": "div",
// "children": [
// {
// "tag": "h3",
// "children": [
// {
// "text": "你好",
// "type": 3
// }
// ],
// "attrs": [
// {
// "name": "class",
// "value": "aa bb"
// },
// {
// "name": " id",
// "value": "mybox"
// }
// ]
// },
// {
// "tag": "ul",
// "children": [
// {
// "tag": "li",
// "children": [
// {
// "text": "A",
// "type": 3
// }
// ],
// "attrs": []
// }
// ],
// "attrs": []
// }
// ],
// "attrs": []
// }
// ]
© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END
