Translation

# Syntax-Directed Translation #

This stage is where we get an opportunity to modify and restructure the tree from a syntax point of view, into a semantic point of view.

To avoid “How to Draw an Owl Step 2: Finish the Owl”, we will continue with the interpteter theme for the moment. Instead of figuring out all the analyses required, let’s ask: what intermediate representation can be interpreted by Python?

Python is quite nice in that it will simply evaluate any mathematical expression for you if it is standalone. If our compiler can create something we can `eval`, then that means it is valid “machine code” for the “machine” we are targeting.

The way to do this is to convert our tree into a standard infix expression. The two trees from earlier would respectively be:

``````> 2 3 +
(2 + 3)
> 2 3 4 + *
((4 + 3) * 2)
``````

Both of those outputs are valid python expressions that can simply be passed to `eval` to get our answer.

The easiest conversion method is to use a clever 2016 Paper which describes an algorithm called BAIT: Bracket Algorithm for Infix Traversal.

It applies parentheses (“brackets”) to each leaf node (containing a number) based on its position in the tree. Once this has been applied, doing an infix traversal on the tree and concatenating it into a single string will get a correct textual representation.

At this point `expr` is the output string above if printed. Apply that repeatedly, and we get our final code:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 `````` ``````# requires package: binarytree==6.5.1 from binarytree import Node, get_parent def exprs_from_tree(nodes): # build an expression in python out of the tree using an in-order traversal # combined with a bracket algorithm described here: # https://www.um.edu.mt/library/oar/bitstream/123456789/14892/1/ # Converting%20a%20binary%20tree%20expression%20to%20infix%20 # notation%20using%20the%20BAT%20algorithm.pdf def _uphill_search(root, node): p = get_parent(root, node) if p is None: return 0, 'left' if p.right == node: direction = 'right' else: direction = 'left' order = 0 while True: node = p order += 1 p = get_parent(root, node) if p is None: break if p.right == node: newdir = 'right' else: newdir = 'left' if newdir != direction: break return order, direction while len(nodes) > 0: for leaf in nodes[-1].leaves: order, direction = _uphill_search(nodes[-1], leaf) if direction == 'left': if isinstance(leaf.value, int): leaf.value = str(leaf.value) leaf.value = '(' * order + leaf.value else: if isinstance(leaf.value, int): leaf.value = str(leaf.value) leaf.value = leaf.value + ')' * order expr = ' '.join(n.value for n in nodes[-1].inorder) yield expr del nodes[-1] ``````

If you would like to support my development of OpGuides, please consider supporting me on GitHub Sponsors or dropping me some spare change on Venmo @vegadeftwing - every little bit helps ❤️