Re: Object-oriented compiler construction: ideas?

Arch Robison <robison@kai.com> wrote:
    [reference snip]
>Thanks for citation, Chris. Two more years of experience of using iterators
>for traversing an IR has convinced me that iterators are the way to go.
>I'll summarize some of the arguments here. By iterator, I mean
>"iterator with cursor". That is, something that you can write
>C-style loops in such as:
>
> for( iterator i = root; !i; i++ )
> inspect( *i )
>
>even thought the traversal may be over a tree. I'll take "visitor"
>to mean a procedure that apply's some visitor function to each node
>of an IR. By "explicit recursive traversal", I mean writing this
>sort of thing:
>
> function inspect( node ) {
> if( node has left child )
> inspect( left child of node );
> if( node has right child )
> inspect( right child of node );
> }
    [ pro/con arguments of iterators vs. recursion summarized]


The approach I favour is the following:
[if you don't like reading the code the basic idea is:
instead of writing either an iterator or a recursive traversal,
perform the recursive traversal gathering (pointers) to the
objects visited in an array (in traversal order).
Then iterate over the array using the standard C for()]


            void
            inspect_graph(Graph some_graph)
            {
int size = nodes_graph(some_graph);
Node * nodes = alloca( size );


num = depth_first_walk_graph(some_graph, size, nodes);
for( i = 0; i < num; i ++ ) {
inspect( array[i] );
}
            }


and
            int
            depth_first_walk_graph(Graph some_graph, int size, Node nodes[])
            {
FOR_NODES_GRAPH(some_graph, node)
mark_node(node) = 0;
END_NODES_GRAPH
return do_depth_first_walk_graph(root_graph(graph), size, nodes);
            }


            static int
            do_depth_first_walk_graph(Node node, int size, Node nodes[])
            {
int n;
if( mark_node(node) )
return 0;


mark_node(node) = 1;
nodes[0] = node;
n = 1;
FOR_SUCCS_NODE(node, succ)
n += do_depth_first_walk_graph(succ, size-n, &nodes[n]);
END_SUCCS_NODE
return n;
            }


Effectively: do the traversal, and gather the traversal sequence into an array;
after that, traverse that sequence in an arbitrary order.


For instance, to number the nodes in reverse dfs order, write the for() loop
as a decreasing loop, and then number the nodes appropriately.


Note this works ONLY in those cases where the inspect() process does not alter
the graph being traversed.


Also, it relies on the ability of determining an upper bound on the size of
the returned sequence.


And yes - I _know_ alloca() is non-portable. Substitute a malloc()/free() if
you want to.


:)
Mayan
--
| Mayan Moudgill
| mayan@watson.ibm.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.