The idea with this kind of tree is that it is an elegant structured representa-
tion of a sequence of arithmetic instructions. Each branch in the tree is roughly
equivalent to an instruction in the decompiled program. It is up to the decom-
piler to perform data-flow analysis on these instructions and construct such a
tree. Once a tree is constructed it becomes fairly trivial to produce high-level
language expressions by simply scanning the tree. The process of constructing
expression trees from individual instructions is discussed below in the data-
flow analysis section.Control Flow Graphs
In order to reconstruct high-level control flow information from a low-level
representation of a program, decompilers must create a control flow graph
(CFG) for each procedure being analyzed. A CFG is a graph representation of
the internal flow with a single procedure. The idea with control flow graphs is
that they can easily be converted to high-level language control flow con-
structs such as loops and the various types of branches. Figure 13.2 shows
three typical control flow graph structures for an ifstatement, an if-else
statement, and a whileloop.Figure 13.2 Typical control flow graphs: (a) a simple ifstatement (b) an if-else
statement (c) a whileloop.(a) (b) (c)462 Chapter 13