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]