基于AST的算数表达式解析

一月 08, 2021

前序

之前在另一篇文章中<<基于后缀算术表达式的代码解析>>已经实现过简单的（1 + 3 - 5 / 54 * 2）等算术的运算，但是代码逻辑实现满足不了更多场景，如

对数据的赋值：a = b + c
逻辑判断: a == b or a != b
与或非: a && c or a || c

所以为了更好的解决一些场景，这里使用AST（抽象语法树）来解决这部分的问题

准备工作

表达式转 AST
AST 遍历
数据作用域

1、表达式转AST

首先可以参考AST在线转换这里，比如

a + 4

js 代码实现：

npm i acorn

import * as acorn from 'acorn';

const code = '7 / (4 + 3)';
const ast = acorn.parse(code);

转换的效果如下：

{
  "type": "Program",
  "start": 0,
  "end": 5,
  "body": [
    {
      "type": "ExpressionStatement",
      "start": 0,
      "end": 5,
      "expression": {
        "type": "BinaryExpression",
        "start": 0,
        "end": 5,
        "left": {
          "type": "Literal",
          "start": 0,
          "end": 1,
          "value": 1,
          "raw": "1"
        },
        "operator": "+",
        "right": {
          "type": "Literal",
          "start": 4,
          "end": 5,
          "value": 4,
          "raw": "4"
        }
      }
    }
  ],
  "sourceType": "module"
}

假如我们可以通过遍历的手段拿到ast中这里的解析运算值
AST
我们只需要根据type:为（BinaryExpression）(每一个带type字段的对应节点都是一个astNode节点，都有对应的遍历函数)进行左右计算(operator)操作, 如:

BinaryExpression(node) {
    const { operator } = node;
    const leftValue = node?.left?.value as any;
    const rightValue = node?.right?.value as any;
    if (operator === '+') {
        node.value = leftValue + rightValue;    // 关键：注意这里的操作计算值最后被定义赋值到AST node节点本身上了
    }
}

Tips:
遍历AST时，注意是从内到外的遍历，也就是从最child级遍历回到parent结束

如：7 / (4 + 3) 对应AST

{
  "type": "Program",
  "start": 0,
  "end": 11,
  "body": [
    {
      "type": "ExpressionStatement",
      "start": 0,
      "end": 11,
      "expression": {
        "type": "BinaryExpression",
        "start": 0,
        "end": 11,
        "left": {
          "type": "Literal",
          "start": 0,
          "end": 1,
          "value": 7,   // ③式
          "raw": "7"
        },
        "operator": "/",
        "right": {
          "type": "BinaryExpression",
          "start": 5,
          "end": 10,
          "left": {
            "type": "Literal",
            "start": 5,
            "end": 6,
            "value": 4, // ①式
            "raw": "4"  
          },
          "operator": "+", 
          "right": {
            "type": "Literal",
            "start": 9,
            "end": 10,
            "value": 3, // ②式
            "raw": "3"  
          }
        }
      }
    }
  ],
  "sourceType": "module"
}

这里就是需要从child节点的 ①式 + ②式 计算完后再与 ③式 进行操作

2、AST 遍历

通常我们会在算术表达式里遇到以下的AST type节点：（当然你有更多的语法node节点需要支持，你可以再添加type遍历函数）

const walkNode = {
    Identifier(node) {
    // 如 a, b, c等字符等
    },
    Literal(node) {
        // 如 1,2,3,4数字等
    },
    CallExpression(node) {
        // 如 func(a, v)
    },
    AssignmentExpression(node) {
        // 如 a = b + 1
    },
    BinaryExpression(node) {
        // 如 a + b
        // 如 a - b
        // 如 a * b
        // 如 a / b
        // 如 a > b
        // 如 a < b
        // 如 a >= b
        // 如 a <= b
        // 如 a == b
        // 如 a === b
        // 如 a != b
        // 如 a !== b
    },
    UnaryExpression(node) {
        // 如 !a
    },
    LogicalExpression(node) {
        // 如 a || b
    },
    ExpressionStatement(node) {
        // 可看作AST遍历结束节点
    },
}

那这个时候只需要根据node的value及operator等进行相应的运算即可, 这里需要安装一个模块包:

npm i acorn-walk

import * as walk from 'acorn-walk'

walk.simple(ast, walkNode);

这样通过acorn-walk这个库可以轻松遍历ast的node节点，这个使用即可根据当前节点进行对应的操作.

3、数据作用域

一般我们解析对应的表达式都有变量的概念：比如a + b, 不是仅仅的等于ab，而是根据当前a,b的可能是变量的概念，去进行相加（如 a = 3, b = 4）最后结果是7.

这也是对应以a,b,c...这种字符为标识类型的节点进行计算时，需要注意的，而且我们来看下它的type类型：

// 如：a
{
    "type": "Identifier",
    "start": 0,
    "end": 1,
    "name": "a"
}

它的type为Identifier, 是一种标记的概念，本身可能就是一个变量。则遍历的时候需要去查找下当前作用域下对应的值

const walkNode = {
    ....
    Literal(node) {
        node.value = dataScope[node?.name] || node?.name;   
        // dataScope 为自定义作用域
        // Literal 需要节点赋值value属性保持在上一父节点拿到真实的值
    },
    ...
}

因此有了作用域我们可以补全下我们的遍历函数：

let result;
const walkNode = {
    Identifier(node) {
        node.value = dataScope[node?.name] || node?.name;
    },
    Literal(node) {
        node.value = dataScope[node?.value] || node?.value;
    },
    CallExpression(node) {
        const { callee = {}, arguments: args = [] } = node;
        const { name } = callee!;
        const argsParams = args.map(d => d.value) || [];
        node.value = InnerFuncs[name!]?.(...argsParams);    
        // InnerFuncs 自己内置定义的函数调用
        // import { InnerFuncs } from './Functions';
        /**
            InnerFuncs = {
                func1: () {
                    return data;
                },
                func2: () {
                    return data;
                }
            };
        */
    },
    AssignmentExpression(node) {
        const { operator } = node;
        // const leftValue = node?.left?.value as any;
        const rightValue = node?.right?.value as any;
        if (operator === '=') {
            _lodashSet(dataScope, node.left.name, rightValue);  // 需要引入import _lodashSet from 'lodash/set';
        }
    },
    BinaryExpression(node) {
        const { operator } = node;
        const leftValue = node?.left?.value as any;
        const rightValue = node?.right?.value as any;
        if (operator === '+') {
            node.value = leftValue + rightValue;
        } else if (operator === '-') {
            node.value = leftValue - rightValue;
        } else if (operator === '*') {
            node.value = leftValue * rightValue;
        } else if (operator === '/') {
            node.value = leftValue / rightValue;
        } else if (operator === '>') {
            node.value = leftValue > rightValue;
        } else if (operator === '<') {
            node.value = leftValue < rightValue;
        } else if (operator === '>=') {
            node.value = leftValue >= rightValue;
        } else if (operator === '<=') {
            node.value = leftValue >= rightValue;
        } else if (operator === '==') {
            node.value = leftValue == rightValue;
        } else if (operator === '===') {
            node.value = leftValue === rightValue;
        } else if (operator === '!=') {
            node.value = leftValue != rightValue;
        } else if (operator === '!==') {
            node.value = leftValue !== rightValue;
        }
    },
    UnaryExpression(node) {
        const { operator } = node;
        if (operator === '!') {
            node.value = !node?.argument?.value;
        }
    },
    LogicalExpression(node) {
        const { operator } = node;
        const leftValue = node?.left?.value as any;
        const rightValue = node?.right?.value as any;
        if (operator === '||') {
            node.value = leftValue || rightValue;
        } else if (operator === '&&') {
            node.value = leftValue && rightValue;
        }
    },
    ExpressionStatement(node) {
        result = node?.expression?.value;
    }
}

总结

此种方式使用AST解析算术表达式，更加容易扩展语法及函数，带来更加方便的遍历操作。

← DDA算法文章 →