next up previous contents
Next: Random Initialisation of Programs Up: Grammar definition Previous: Tree-as-Hash-Table Genotype Representation   Contents

Grammar Specification

PerlGP is a strongly typed system. In fact, all evolved code must be syntactically correct to be awarded fitness. When random individuals or subtrees are generated, PerlGP follows a grammar (defined by the user). The format of this grammar is analogous to the tree-as-hash encoding described above, and is explained in the code below:

  $F{ROOT} = [ '{STATEMENT}' ];
  $T{ROOT} = [ '# nothing' ];

  $F{STATEMENT} = [ 'print "{STRING}!\n";',
                    '$s = "{WORD}";',

  $T{STATEMENT} = [ '# just a comment',

  $F{STRING} = [ '{STRING}, {STRING}',
                 '{WORD}' ];

  $T{STRING} =
    $T{WORD} = [ 'donuts', 'mmm', '$s' ];

Grammar specification as a pair of hashes, %F for functions and %T for terminals. The keys in the hashes are the user-defined node types (i.e. data types). Node types must be in capital letters only. The values are anonymous arrays containing the possible expansions for that type. When another function or terminal is needed, it is signalled by a node type in curly braces. The ROOT node type must always be defined. Function definitions are optional (in this example there is no function of type WORD) but terminals must be defined for every type.

Bob MacCallum 2003-02-03