RSS
Twitter
Facebook
Nodes
of a syntax tree or DAG are stored in an array of records. The integer index of
the record for a node in the array is known as the value
number of that node.
The
signature of a node is a triple < op, l, r> where op is the label, l the
value number of its left child, and r the value number of its right child. The
value-number method for constructing the nodes of a DAG uses the signature of a
node to check if a node with the same signature already exists in the array. If
yes, returns the value number. Otherwise, creates a new node with the given
signature.
Since
searching an unordered array is slow, there are many better data structures to
use. Hash tables are a good choice.
0 comments