Finding common subexpressions: algorithm

Now that we know about the uniq storage option, we can discuss the algorithm that we will use to find the common subexpressions. We will use the uniq storage option, so all common subexpressions appear as shared nodes in the tree (as we have seen earlier). This means that it is sufficient to do a tree-walk, and mark the nodes that we visit more than once. We chose this algorithm because it is easy to express in Kimwitu.

After the tree walk we have a list of (names of) all common subexpressions of the expression (we have a list of names, and a mapping from names to expressions).

The following picture shows the result of applying the algorithm on our 'running example'. It shows the attributed tree, together with the mappings list.

next overview up
Last updated at 03 February '98 by