class Panini::DerivationStrategy::Leftmost

The Leftmost strategy is a naive strategy for deriving sentences from a grammar. It will aways substitute for the leftmost nonterminal first. If a nonterminal has more than one production, they will be chosen in a round-robin ordering.

This implementation is slow and will not work on many grammars.

In other words, don't use this! It's in place because it is simple to and was used for early testing.

Public Class Methods

new(grammar) click to toggle source
Calls superclass method Panini::DerivationStrategy::Base::new
# File lib/derivation_strategy/leftmost.rb, line 30
def initialize(grammar)
  build_production_proxies(grammar)
  super(grammar)
end

Public Instance Methods

sentence() click to toggle source

Generates a sentence.

# File lib/derivation_strategy/leftmost.rb, line 44
def sentence
  derived_sentence, substituted = [@grammar.start], false
  begin
    derived_sentence, substituted = substitution_pass(derived_sentence)
  end while substituted
  derived_sentence
end

Private Instance Methods

build_production_proxies(grammar) click to toggle source
# File lib/derivation_strategy/leftmost.rb, line 35
def build_production_proxies(grammar)
  @production_proxies = {}
  grammar.nonterminals.each do |nonterminal|
    @production_proxies[nonterminal] = RoundRobinProductionChoiceProxy.new(nonterminal)
  end
end
substitution_pass(derived_sentence) click to toggle source
# File lib/derivation_strategy/leftmost.rb, line 52
def substitution_pass(derived_sentence)
  substituted = false
  derived_sentence = derived_sentence.flat_map do |term|
    if !substituted && (term.class == Nonterminal)
      substituted = true
      @production_proxies[term].production
    else
      term
    end
  end
  return derived_sentence, substituted
end