next up previous contents
Next: Grammar Specification Up: Grammar definition Previous: Grammar definition   Contents

Tree-as-Hash-Table Genotype Representation

Hash tables, also known as associative arrays, can be hijacked to encode string-based tree structures as explained in the code snippet below. The keys in the genome hash-tree follow the syntax: nodeTYPExx, where TYPE is replaced by an all-capitals string describing the type of the node (see Section 7.2), and xx is a unique identifier (for there may be many nodes of the same type).

  $tree{nodeS0} = 'One day in {nodeS1}.';
  $tree{nodeS1} = '{nodeS2} {nodeS3}';
  $tree{nodeS2} = 'late';
  $tree{nodeS3} = 'August';
  $string = $tree{nodeS0};
  do { print "$string\n" } while ($string =~ s/{(\w+)}/$tree{$1}/);

  # outputs the following:
    One day in {nodeS1}.
    One day in {nodeS2} {nodeS3}.
    One day in late {nodeS3}.
    One day in late August.
Tree-as-hash-table explanation. In Perl, the syntax $one{two} = 'three' means that in a hash table named `one', the value `three' is stored for the key `two'. The iterated search-and-replace (s/patt/repl/) looks for hash keys contained within curly braces and replaces them with the contents of the hash.

Bob MacCallum 2003-02-03