Derivation tree operations are needed for implementing
grammar-based genetic programming and grammatical evolution:
Generating a random derivation trees of a context-free grammar
of bounded depth, decoding a derivation tree,
choosing a random node in a derivation tree,
extracting a tree whose root is a specified node, and
inserting a subtree into a derivation tree at a specified node.
These operations are necessary for the initialization and
for decoders of a random population of programs,
as well as for implementing crossover and mutation operators.
Depth-bounds are guaranteed by switching to a grammar
without recursive production rules.
For executing the examples, the package 'BNF' is needed.
The basic tree operations for generating, extracting, and
inserting derivation trees as well as the conditions
for guaranteeing complete derivation trees have been
presented in Geyer-Schulz (1997, ISBN:978-3-7908-0830-X).
The use of random integer vectors for the generation
of derivation trees has been introduced in
Ryan, C., Collins, J. J., and O'Neill, M. (1998)
# The R script xegaBNF.R
The directory xegaBNF contains the implementation
of the grammar compiler which translates a file
with the BNF of a grammar into the internal
representation of the grammar.
The easiest installation is by using install.packages from R.
1. Linux:
Start R in the directory where you have stored xegaBNF_0.0.0.1.tar.gz
> install.packages("xegaBNF_0.0.0.1.tar.gz")
1. Windows:
Start R in the directory where you have stored xegaBNF_0.0.0.1.zip
The R script xegaBNF.R generates
1. the man pages of the package.
2. the pdf documentation of the package.
3. the compilation and installation of the package.
(You must adapt the variables path and pName
in the script xegaBNF.R:
path<-"~/dev/iaa/genetic/xega/"
pName<-"xegaBNF"
to the directory where you copy the package.
You need to install the R-package devtools for this R script.
There are two ways to use the code:
1. Change into the R directory which contains the code, start R and load all code files:
source("xegaBNF.R")
Note that the package xegaBNF provides the functions
of the grammar compiler needed
for the option "sgp" of the algorithm sga of the family sgX.
Use the pdf-Manual!
2. Adapt the path in xegaBNF.R and install the library xegaBNF:
Rscript xegaBNF.R
Restart R and
library(xegaBNF)
You get all elements of the package by
xegaBNF::
and pressing the tabulator.
You get the man page by e.g
?booleanGrammar()
or
help(booleanGrammar)
All examples given on a man page can be executed by
example(booleanGrammar)
Note that man pages and examples are only available, if you install
the package as a library.