xegaBNF {xegaBNF} | R Documentation |
xegaBNF
implements a grammar compiler for context-free languages
specified in BNF and a few utility functions.
The grammar compiler
generates a grammar object.
This object used by the package
xegaDerivationTrees
, as well as for grammar-based genetic
programming (xegaGpGene
) and grammatical evolution
(xegaGeGene
.
Grammars of context-free languages are represented in Backus-Naur Form (BNF). See e.g. Backus et al. (1962).
The BNF is a meta-language for specifying the syntax of context-free languages. The BNF provides
non-terminal symbols,
terminal symbols, and
meta-symbols of the BNF.
A non-terminal symbol has the following form:
<pattern>
, where pattern is an arbitrary sequence of letters, numbers,
and symbols.
A terminal symbol has the following form:
"pattern"
, where pattern is an arbitrary sequence of letters, numbers,
and symbols.
The BNF has three meta symbols, namely ::=
, |
, and ;
which are used for the specification of production (substitution) rules.
::=
separates the left-hand side of the rule from the right-hand
side of the rule. ;
indicates the end of a production rule.
|
separates the symbol sequences of a compound production rule.
A production rule has the following form:
LHS ::= RHS;
where LHS
is a single non-terminal symbol and
RHS
is either a simple symbol sequence or a compound symbol
sequence.
A production rule with a simple symbol sequence
specifies the substitution of
the non-terminal symbol on the LHS
by the symbol sequence of
the RHS
.
A production rule with a compound symbol sequence
specifies the substitution of
the non-terminal symbol on the LHS
by one of the symbol sequences of
the RHS
.
The BNF may be stored in ASCII text files and edited with standard editors.
A grammar object is represented as a named list:
$name contains the filename of the BNF.
$ST the symbol table.
$PT the production table.
$Start the start symbol of the grammar.
$SPT a short production table without recursive rules.
The main steps of the compilation process are:
Store the filename.
Make the symbol table. See makeSymbolTable
.
Make the production table. See makeProductionTable
.
Extract the start symbol. See makeStartSymbol
.
Compile a short production table. See compileShortPT
.
Return the grammar.
compileBNF(g)
where g
is a character string with a BNF.
isTerminal, isNonTerminal: For testing the symbol type of identifiers in a grammar object.
rules, derives: For choosing rules and for substitutions.
The xegaX-packages are a family of R-packages which implement eXtended Evolutionary and Genetic Algorithms (xega). The architecture has 3 layers, namely the user interface layer, the population layer, and the gene layer:
The user interface layer (package xega
)
provides a function call interface and configuration support
for several algorithms: genetic algorithms (sga),
permutation-based genetic algorithms (sgPerm),
derivation-free algorithms as e.g. differential evolution (sgde),
grammar-based genetic programming (sgp) and grammatical evolution
(sge).
The population layer (package xegaPopulation
) contains
population related functionality as well as support for
population statistics dependent adaptive mechanisms and parallelization.
The gene layer is split into a representation-independent and a representation-dependent part:
The representation indendent part (package xegaSelectGene
)
is responsible for variants of selection operators, evaluation
strategies for genes, as well as profiling and timing capabilities.
The representation dependent part consists of the following packages:
xegaGaGene
for binary coded genetic algorithms.
xegaPermGene
for permutation-based genetic algorithms.
xegaDfGene
for derivation free algorithms as e.g.
differential evolution.
xegaGpGene
for grammar-based genetic algorithms.
xegaGeGene
for grammatical evolution algorithms.
The packages xegaDerivationTrees
and xegaBNF
support
the last two packages:
xegaBNF
essentially provides a grammar compiler.
xegaDerivationTrees
implements an abstract data type for derivation trees.
(c) 2023 Andreas Geyer-Schulz
MIT
<https://github.com/ageyerschulz/xegaBNF>
From CRAN by install.packages('xegaBNF')
Andreas Geyer-Schulz
Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Naur, Peter, Perlis, A. J., Ruthishauser, H., and Samelson, K. (1962) Revised Report on the Algorithmic Language ALGOL 60, IFIP, Rome.