Class: Wallace::GE::BackusNaurForm

Inherits:
Object
  • Object
show all
Defined in:
lib/modules/ge/backus_naur_form.rb

Overview

This class holds the details of a BNF grammar and provides methods for producing a derivation from a given sequence of integers.

Rather than having a special class for grammar sequences, we simply use arrays to store grammar sequences, ensuring the best possible compatibility with existing array-based operators.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root, rules) ⇒ BackusNaurForm

Constructs a new BNF Grammar.

Parameters:

  • root, the root symbol in the grammar (at which all derivations start).

  • rules, the rules of this grammar, given as a hash, indexed by symbol.



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/modules/ge/backus_naur_form.rb', line 21

def initialize(root, rules)

  # Convert each rule into a sequence of symbol derivations.
  # Transform each string-based derivation into a sequence of tokens.
  @rules = Hash[rules.map { |rule, derivations|
    derivations.map! { |derivation|
      tokens = []
      until derivation.empty?
        left, tag, right = derivation.partition(/{\w+}/)
        tokens << Wallace::GE::Literal.new(left) unless left.empty?
        tokens << Wallace::GE::Symbol.new(tag[1...tag.length-1]) unless tag.empty?
        derivation = right
      end
      tokens
    }
    [rule.to_s, derivations]
  }].freeze

  # Could ensure that the root is a valid symbol.
  @root = root.to_s.freeze

end

Instance Attribute Details

#root ⇒ Object (readonly)

The root symbol for this grammar (where all derivations begin).



14
15
16
 
# File 'lib/modules/ge/backus_naur_form.rb', line 14

def root
  @root
end

Instance Method Details

#[](symbol) ⇒ Object Also known as: derivations

Returns the list of possible derivations for a given symbol.



51
52
53
 
# File 'lib/modules/ge/backus_naur_form.rb', line 51

def [](symbol)
  @rules[symbol]
end

#derive(sequence, opts = {}) ⇒ Object

Produces a grammar derivation from a given sequence of integers.

Parameters:

  • sequence, the sequence of integers to produce a derivation from.

  • opts, a hash of keyword options for this method. -> random, the RNG to use during the derivation process. -> wrap, flag indicating whether the sequence should be wrapped when

    all genetic material has been used.

    -> max_wraps, the maximum number of times the sequence should be

    wrapped.

Returns: A grammar derivation object for the produced derivation.



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# File 'lib/modules/ge/backus_naur_form.rb', line 69

def derive(sequence, opts = {})

  # For now wrapping is forced.
  opts[:wrap] = true
  opts[:max_wraps] ||= 1 if opts[:wrap]

  derivation = Wallace::GE::GrammarDerivation.new

  # Keep processing the sequence of tokens until none remain.
  #
  # * Literal tokens are appended to the end of the derivation.
  # * Symbol tokens are converted into a given symbol derivation,
  #   using the next codon as the index if there is more than a single
  #   choice.
  # * When there are no codons left to consume then we either:
  #   a) Add a new codon to the sequence (until the limit is reached). [DISABLED]
  #   b) Reset the codon index to zero, wrapping the sequence round.
  queue = [Wallace::GE::Symbol.new(@root)]
  codon_index = 0
  sequence_length = sequence.length
  num_wraps = 0

  until queue.empty?
    token = queue.shift
    if token.is_a? Wallace::GE::Literal
      derivation << token.value
    else
      options = @rules[token.value]
      if options.length == 1
        queue += options[0]
      else

        # Check if there are no remaining codons in the sequence.
        if (codon_index >= sequence_length)

          # If wrapping is enabled, reset the codon pointer to the
          # start of the sequence, unless the maximum number of wraps
          # has been encountered.
          if opts[:wrap]
            raise Wallace::Errors::GenotypeExhaustedError if num_wraps != opts[:max_wraps] # throw error?
            codon_index = 0
            num_wraps += 1
          end

        end

        queue = options[sequence[codon_index] % options.length] + queue
        codon_index += 1
      end
    end
  end

  return derivation.freeze

end

#size ⇒ Object Also known as: length

Returns the number of symbols in the BNF.



45
46
47
 
# File 'lib/modules/ge/backus_naur_form.rb', line 45

def size
  @rules.size
end