如何将表达式树 (AST) 转换为 DOM 树 (XML)

Question

我需要允许用户编写表达式并从表达式构建 XML 树。我的计划是使用 math.js 来解析并生成 expression tree, then convert that expression tree into DOM tree, and then convert DOM tree into XML using XMLSerializer。粗体部分是有技巧的部分。

对于表达式：

const node = math.parse('sqrt(2 + x)')

math.js 生成以下表达式树：

 FunctionNode    sqrt
                   |
  OperatorNode     +
                  / \
  ConstantNode   2   x   SymbolNode

现在我需要将其转换为 DOM。我想使用库公开的遍历 API。他们有 traverse 方法，递归遍历节点树中的所有节点，并为此节点及其每个子节点执行给定的回调。回调中的 path 参数是一个包含相对 JSON 路径的字符串。

我的第一次尝试（包括保留对父 DOM 节点的引用）没有按预期工作：

const parent = new DocumentFragment();
let tmpParent = parent;

  const node = math.parse('3 * x + 2');
  node.traverse(function(node, path, parent) {
    switch (node.type) {
      case 'OperatorNode':
        const operator = document.createElement('div');
        tmpParent.appendChild(operator);
        tmpParent = operator;
        break;
      case 'ConstantNode':
        const constant = document.createElement('span');
        tmpParent.appendChild(constant);
        tmpParent = constant;
      ...
    }
  });

所以我开始研究如何 HAST is transformed into JSX，他们使用了以下方法：

walk(estree, {
    enter: function(node) {
      stack.push();
      ...
    }
    leave: function(node) {
      ...
        stack.pop();
      }
    }
  })

所以我想我也需要以某种方式使用 stack。但是他们的模式公开了 enter 和 leave 回调点，而 traverse 来自 math.js 我只有一个点。

是否可以通过使用堆栈的单点实现我想要实现的目标，或者如何实现？

Answer 1

您可以使用自定义属性扩展节点对象，例如 DOM 并将子节点附加到父节点的 DOM：

const node = math.parse('sqrt(2 + x)')

node.traverse(function(node, path, parent) {
    switch (node.type) {
      case 'FunctionNode':
        node.DOM = document.createElement('div')
        break
      case 'OperatorNode':
        node.DOM = document.createElement('p');
        break;
      case 'ConstantNode':
        node.DOM = document.createElement('span');
        break;
      case 'SymbolNode':
        node.DOM = document.createElement('b');
        break
    }
    
    if (parent)
      parent.DOM.appendChild(node.DOM)

});
  
console.log(node.DOM.outerHTML)

<script src="https://unpkg.com/mathjs@9.4.2/lib/browser/math.js"></script>

Answer 2

我使用每个节点上可用的 forEach 方法和我在问题中引用的 HAST/JSX 转换代码中的 stack 想法设法解决了这个问题：

const parent = new DocumentFragment();
const stack = [];

function _traverse(node, buildDomNode, dom) {
    // this is equivalent to `enter` callback
    stack.push(dom);

    node.forEach(function(child, path, parent) {
      let d = buildDomNode(child, path, parent, dom);
      _traverse(child, buildDomNode, d);
    });

    // this is equivalent to `leave` callback
    stack.pop();
}

const node = math.parse('3 * x + 2');
const dnode = buildDomNode(node, null, null, parent);
stack.push(dnode);

_traverse(node, buildDomNode, dnode);

function buildDomNode(node, path, parent, dom) {
    let dnode;

    switch (node.type) {
      case 'OperatorNode':
        dnode = document.createElement('div');
        break;
      case 'ConstantNode':
        dnode = document.createElement('span');
        ...
    }

    dom.appendChild(dnode);
    return dnode;
  }

如何将表达式树 (AST) 转换为 DOM 树 (XML)

How to transform an expression tree (AST) into DOM tree (XML)

javascript

algorithm

abstract-syntax-tree