xegaBNF {xegaBNF}

Package xegaBNF

Description

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.

BNF (Backus-Naur Form)

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

1. non-terminal symbols,

2. terminal symbols, and

3. 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.

Editing BNFs

The BNF may be stored in ASCII text files and edited with standard editors.

The Internal Representation of a Grammar Object

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 Compilation Process

The main steps of the compilation process are:

1. Store the filename.

2. Make the symbol table. See makeSymbolTable.

3. Make the production table. See makeProductionTable.

4. Extract the start symbol. See makeStartSymbol.

5. Compile a short production table. See compileShortPT.

6. Return the grammar.

The User-Interface of the Compiler

compileBNF(g) where g is a character string with a BNF.

Utility Functions for xegaX-Packages

• isTerminal, isNonTerminal: For testing the symbol type of identifiers in a grammar object.

• rules, derives: For choosing rules and for substitutions.

The Architecture of the xegaX-Packages

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:

  1. The representation indendent part (package xegaSelectGene) is responsible for variants of selection operators, evaluation strategies for genes, as well as profiling and timing capabilities.

  2. 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.

Copyright

(c) 2023 Andreas Geyer-Schulz

License

MIT

URL

<https://github.com/ageyerschulz/xegaBNF>

Installation

From CRAN by install.packages('xegaBNF')

Author(s)

Andreas Geyer-Schulz

References

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.