【第2405期】你所见过的最简单的AST入门
前言
㊗️各位读者中秋快乐。今日前端早读课文章由快手@Leo投稿分享。
@Leo，来自快手音视频中台，非典型程序员，爱代码，爱生活，欢迎交流，更欢迎一起做同事~
正文从这开始~~
写在前面
很多铁子可能一直都在谈AST，但是实际开发过程中对它又不怎么在乎。就像空气一样，看不见的东西不代表不重要，AST其实隐藏在各种环节中：比如JavaScript引擎的编译，Vue/React的编译，CSS的预处理器，Babel的编译等等，都在使用着AST。
AST全称Abstract Syntax Tree，即抽象语法树。但是好像「抽象」这个词也太「抽象」了，说人话就是把代码变成JSON，用这段JSON去描述这段代码干了啥。
一段代码的编译过程分为三个重要的步骤：分词、解析、生成可执行代码。下面会通过制作一个简单的计算器去一步一步走完这三个步骤。
开始！
如果我们要写一个计算器去执行 1 + 2 / 2 * 3 + 2 该怎么做呢？
第一步，我们要把所有的数字和运算符给摘出来，这就是「分词」，也叫「词法分析」；
第二步，我们要按照数学规则去把分词的结果变成一段JSON，这就是「编译」，也叫「语法分析」；
第三步，我们要把语法树变成可执行的代码去执行；
第四步，这就完事了，没有第四步。
分词
这一步比较简单，先做一下空值检查和去掉空白字符这种前期处理，然后遍历字符串即可，处理逻辑如下：
function genTokens (str) {
if (!/^(\d|\s|\+|\-|\*|\/)+$/.test(str)) { // 空值检查
throw new Error('请检查输入，只支持数字与四则运算符"+-*/" ')
}
const s = str.replace(/\s/g, '') // 去掉所有的空白字符
let arr = []
for (let char of s) {
const len = arr.length
if (len && !isOperator(arr[len - 1]) && !isOperator(char)) { // 处理两位及以上位数数字，比如10，100
arr[len - 1] = `${arr[len - 1]}${char}`
continue
}
arr.push(char)
}
return arr // 得到结果 ['1', '+', '2', '/', '2', '*', '3', '+', '2']
}
function isOperator (str) {
return /[\+\-\*\/]/.test(str)
}
通过这一步，我们把1 + 2 / 2 * 3 + 2这个字符串变成了数组['1', '+', '2', '/', '2', '*', '3', '+', '2']
编译
编译过程也叫语法分析，因为涉及到了语法，这个过程也是相对比较复杂的过程。
我们思考下这个1 + 2 / 2 * 3 + 2这个计算公式的语法核心是什么？其实就是运算符的优先级，乘除的优先级最高，加减的优先级最低。我们需要把分词阶段得到的数组按照运算优先级变成对应的语法树。
手画了一下我们期望的语法树🌲如下，这个语法树越往下，优先级越高。
我们需要遍历分词阶段得到的数组，遇到运算符后比较优先级：
优先级更高：在上一个运算符节点下沉一级；
优先级相同：在上一个运算符节点上浮一级；
优先级更低：要找到最近的，比当前运算符优先级低一级的运算符节点，再上浮一级；
备注：为什么优先级低的运算符要上浮呢？需要结合下文的第三步来看，第三步我们用了深度优先的方式去递归这棵树🌲
代码如下，核心函数中用的工具函数放在了下方：
function genTree (tokens) {
let lastOpr = null
return tokens.reduce((acc, cur, index) => {
if (index === 0) {
return {
value: cur
}
}
if (isOperator(cur)) {
if (!lastOpr) { // 首个运算符
acc = {
operator: cur,
left: acc
}
lastOpr = acc
return acc
}
switch (priorityComparison(cur, lastOpr.operator)) {
case 1: { // 优先级更高
const old = lastOpr.right
lastOpr.right = {
operator: cur,
left: old,
parent: lastOpr
}
lastOpr = lastOpr.right
break
}
case -1: { // 优先级更低
acc = {
operator: cur,
left: acc
}
lastOpr = acc
break
}
case 0: { // 优先级相同
if (!lastOpr.parent) { // 在顶部节点
acc = {
operator: cur,
left: acc
}
lastOpr = acc
} else {
lastOpr.parent.right = {
operator: cur,
left: lastOpr,
parent: lastOpr.parent
}
lastOpr = lastOpr.parent.right
}
}
}
} else {
if (cur == 0 && lastOpr.operator === '/') { // 兼容0做分母的情况
throw new Error ('分母不能为0')
}
lastOpr.right = {
value: cur
}
}
return acc
}, {})
}
function isOperator (str) {
return /[\+\-\*\/]/.test(str)
}
function priorityComparison (x, y) {
return weightMap[x] - weightMap[y]
}
const weightMap = {
'+': 0,
'-': 0,
'*': 1,
'/': 1
}
通过这一步，我们得到了我们期望的JSON结构。
生成可执行代码
这一步就是把编译阶段得到的JSON结构通过递归的方式变成可执行的代码，代码如下：
function visitor (node) {
if (node.operator) {
return calcValue(visitor(node.left), visitor(node.right), node.operator)
} else {
return node.value
}
}
function calcValue (px, py, rule) {
const [x, y] = [Number(px), Number(py)]
switch(rule) {
case '+': {
return x + y
}
case '-': {
return x - y
}
case '*': {
return x * y
}
case '/': {
return x / y
}
}
}
执行完这一步，我们终于得到了1 + 2 / 2 * 3 + 2的运算结果6!
写在后面
这篇文章是通过一个基础的计算器去模拟AST的过程，让大家有一个入门级的具像的认识。当然上面涉及的算法比较简单，计算器还没有考虑有括号的情况，如果要支持括号，我们第二步的编辑阶段的语法分析的算法要进一步升级，感兴趣的铁子可以自行尝试。
加油奥利给！
音视频中台招人啦，欢迎投递简历，一起来做点好玩儿的~
你将能够负责中台前端的项目搭建与技术选型工作，和算法、大数据、媒体等团队密切协作，与产品和设计团队一起持续正向优化业务体验、不断探索新业务新场景。
欢迎来和大家一起高效工作，快乐生活！
为你推荐
【第1471期】AST抽象语法树——最基础的javascript重点知识
欢迎自荐投稿，前端早读课等你来。