\myheading{Data structure}

Our toy decompiler will use just one single data structure, representing expression tree.

Many programming textbooks has an example of conversion from Fahrenheit temperature to Celsius, using the following formula:

\begin{center}
{\large $celsius = (fahrenheit - 32) \cdot \frac{5}{9}$}
\end{center}

This expression can be represented as a tree:

\input{\CURPATH/fahr1}

How to store it in memory?
We see here 3 types of nodes: 1) numbers (or values); 2) arithmetical operations; 3) symbols (like ``INPUT'').

Many developers with \ac{OOP} in their mind will create some kind of class.
Other developer maybe will use ``variant type''.

I'll use simplest possible way of representing this structure: a Python tuple.
First element of tuple can be a string:
either ``EXPR\_OP'' for operation, ``EXPR\_SYMBOL'' for symbol or ``EXPR\_VALUE'' for value.
In case of symbol or value, it follows the string.
In case of operation, the string followed by another tuples.

Node type and operation type are stored as plain strings---to make debugging output easier to read.

There are \emph{constructors} in our code, in \ac{OOP} sense:

\begin{lstlisting}
def create_val_expr (val):
    return ("EXPR_VALUE", val)

def create_symbol_expr (val):
    return ("EXPR_SYMBOL", val)

def create_binary_expr (op, op1, op2):
    return ("EXPR_OP", op, op1, op2)
\end{lstlisting}

There are also \emph{accessors}:

\begin{lstlisting}
def get_expr_type(e):
    return e[0]

def get_symbol (e):
    assert get_expr_type(e)=="EXPR_SYMBOL"
    return e[1]

def get_val (e):
    assert get_expr_type(e)=="EXPR_VALUE"
    return e[1]

def is_expr_op(e):
    return get_expr_type(e)=="EXPR_OP"

def get_op (e):
    assert is_expr_op(e)
    return e[1]

def get_op1 (e):
    assert is_expr_op(e)
    return e[2]

def get_op2 (e):
    assert is_expr_op(e)
    return e[3]
\end{lstlisting}

The temperature conversion expression we just saw will be represented as:

\input{\CURPATH/fahr2}

\dots or as Python expression:

\begin{lstlisting}
('EXPR_OP', '/', 
	('EXPR_OP', '*',
	('EXPR_OP', '-', ('EXPR_SYMBOL', 'arg1'), ('EXPR_VALUE', 32)), 
	('EXPR_VALUE', 5)), 
('EXPR_VALUE', 9))
\end{lstlisting}

In fact, this is \ac{AST} in its simplest form.
\ac{AST}s are used heavily in compilers.