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

Question

I need to allow a user to write expressions and build XML tree from the expression. My plan is to use math.js which parses and generates an expression tree, then convert that expression tree into DOM tree, and then convert DOM tree into XML using XMLSerializer. The part in bold is tricky one.

For the expression:

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

math.js generates the following expression tree:

 FunctionNode    sqrt
                   |
  OperatorNode     +
                  / \
  ConstantNode   2   x   SymbolNode

Now I need to convert it to DOM. I'd like to use the traversal API exposed by the library. They have traverse method, that recursively traverse all nodes in a node tree and executes given callback for this node and each of its child nodes. The path parameter in the callback is a string containing a relative JSON Path.

My first attempt that included keeping a reference to the parent DOM node didn't work as expected:

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;
      ...
    }
  });

So I started looking at how HAST is transformed into JSX, and they use the following approach:

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

So I gather I'd need to somehow use stack as well. But their pattern exposes enter and leave callback points, while with traverse from math.js I have only a single point.

Is it possible to do what I'm trying to achieve with a single point using stack or else how to do it?

user_989121 · Answer

You can extend the node object with a custom property like DOM and append children to the DOM of the parent node:

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)

user_2545680 · Answer

I managed to solve it like this using forEach method available on each node and stack idea from the HAST/JSX conversion code I referenced in my question:

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;
  }

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

2 Answers