class Sequitur::Production

In a context-free grammar, a production is a rule in which its left-hand side (LHS) consists solely of a non-terminal symbol and the right-hand side (RHS) consists of a sequence of symbols. The symbols in RHS can be either terminal or non-terminal symbols. The rule stipulates that the LHS is equivalent to the RHS, in other words every occurrence of the LHS can be substituted to corresponding RHS. Implementation note: the object id of the production is taken as its LHS.

Attributes

digrams[R]

@return [Array<Sequitur::Digram>] The sequence of digrams appearing in the RHS

refcount[R]

@return [Integer] The reference count (= how times other productions reference this one)

rhs[R]

@return [Sequitur::SymbolSequence] The right-hand side (rhs)

consists of a sequence of grammar symbols

Public Class Methods

new() click to toggle source

Constructor. Build a production with an empty RHS.

# File lib/sequitur/production.rb, line 29
def initialize
  @rhs = SymbolSequence.new
  @refcount = 0
  @digrams = []
end

Public Instance Methods

==(other) click to toggle source

Identity testing. @param other [Production, ProductionRef] another production or production reference. @return [TrueClass, FalseClass] true when the receiver and other are the same.

# File lib/sequitur/production.rb, line 38
def ==(other)
  return true if object_id == other.object_id

  if other.is_a?(ProductionRef)
    (other == self)
  else
    false
  end
end
accept(aVisitor) click to toggle source

Part of the ‘visitee’ role in Visitor design pattern. @param aVisitor

# File lib/sequitur/production.rb, line 218
def accept(aVisitor)
  aVisitor.start_visit_production(self)
  rhs.accept(aVisitor)
  aVisitor.end_visit_production(self)
end
append_symbol(aSymbol) click to toggle source

Add a (grammar) symbol at the end of the RHS. @param aSymbol [Object] A (grammar) symbol to add.

# File lib/sequitur/production.rb, line 128
def append_symbol(aSymbol)
  case aSymbol
  when Production
    new_symb = ProductionRef.new(aSymbol)
  when ProductionRef
    if aSymbol.unbound?
      msg = 'Fail to append reference to nil production in '
      msg << to_string
      raise StandardError, msg
    end
    new_symb = aSymbol.dup
  else
    new_symb = aSymbol
  end

  rhs << new_symb
  digrams << Digram.new(rhs[-2], rhs[-1], self) if rhs.size >= 2
end
clear_rhs() click to toggle source

Clear the right-hand side. Any referenced production has its reference counter decremented.

# File lib/sequitur/production.rb, line 149
def clear_rhs
  rhs.clear
end
decr_refcount() click to toggle source

Decrement the reference count by one. @return [Integer]

# File lib/sequitur/production.rb, line 62
def decr_refcount
  raise StandardError, 'Internal error' if @refcount.zero?

  @refcount -= 1
end
derive_step(another) click to toggle source

Replace every occurrence of ‘another’ production in self.rhs by

the symbols in the rhs of 'another'.

@param another [Production, ProductionRef] a production that

consists exactly of one digram (= 2 symbols).

@example Synopsis # Given the production p_A : a p_B b p_B c # And the production p_B : x y # Then… p_A.derive_step(p_B) Modifies p_A as into: p_A -> a x y b x y c

# File lib/sequitur/production.rb, line 204
def derive_step(another)
  (0...rhs.size).to_a.reverse_each do |index|
    next unless rhs[index] == another

    rhs.insert_at(index + 1, another.rhs)
    another.decr_refcount
    rhs.delete_at(index)
  end

  recalc_digrams
end
empty?() click to toggle source

Is the rhs empty? @return [TrueClass, FalseClass] true if the rhs has no members.

# File lib/sequitur/production.rb, line 50
def empty?
  rhs.empty?
end
incr_refcount() click to toggle source

Increment the reference count by one. @return [Integer]

# File lib/sequitur/production.rb, line 56
def incr_refcount
  @refcount += 1
end
last_digram() click to toggle source

Retrieve the last digram appearing in the RHS (if any). @return [Sequitur::Digram, NilClass] last digram in the rhs otherwise nil.

# File lib/sequitur/production.rb, line 114
def last_digram
  digrams.empty? ? nil : digrams.last
end
positions_of(symb1, symb2) click to toggle source

Find all the positions where the digram occurs in the rhs @param symb1 [Object] first symbol of the digram @param symb2 [Object] second symbol of the digram @return [Array<Integer>] the list of indices where the digram occurs in rhs. @example

# Given the production p : a b c a b a b d
#Then ...
p.positions_of(a, b) # => [0, 3, 5]
# Caution: "overlapping" digrams shouldn't be counted
# Given the production p : a a b a a a c d
# Then ...
p.positions_of(a, a) # => [0, 3]
# File lib/sequitur/production.rb, line 165
def positions_of(symb1, symb2)
  # Find the positions where the digram occur in rhs
  indices = [-2] # Dummy index!
  (0...rhs.size).each do |i|
    next if i == indices.last + 1

    indices << i if (rhs[i] == symb1) && (rhs[i + 1] == symb2)
  end

  indices.shift

  indices
end
recalc_digrams() click to toggle source

Enumerate the digrams appearing in the right-hand side (rhs) @return [Array<Sequitur::Digram>] the list of digrams found in rhs of this production.

# File lib/sequitur/production.rb, line 84
def recalc_digrams
  return [] if rhs.size < 2

  result = []
  rhs.symbols.each_cons(2) { |couple| result << Digram.new(*couple, self) }
  @digrams = result
end
reduce_step(another) click to toggle source

Given that the production P passed as argument has exactly 2 symbols

in its rhs s1 s2, substitute in the rhs of self all occurrences of
s1 s2 by a reference to P.

@param another [Production, ProductionRef] a production that

consists exactly of one digram (= 2 symbols).
# File lib/sequitur/production.rb, line 184
def reduce_step(another)
  (symb1, symb2) = another.rhs.symbols
  pos = positions_of(symb1, symb2).reverse

  # Replace the two symbol sequence by the production
  pos.each { |index| rhs.reduce_step(index, another) }

  recalc_digrams
end
references() click to toggle source

Select the references to production appearing in the rhs. @return [Array<ProductionRef>]

# File lib/sequitur/production.rb, line 70
def references
  rhs.references
end
references_of(a_prod) click to toggle source

Look in the rhs all the references to a production passed a argument. @param a_prod [Production, ProductionRef] The production to search for. @return [Array<ProductionRef>]

# File lib/sequitur/production.rb, line 77
def references_of(a_prod)
  real_prod = a_prod.is_a?(ProductionRef) ? a_prod.production : a_prod
  rhs.references_of(real_prod)
end
repeated_digram?() click to toggle source

Detect whether the last digram occurs twice Assumption: when a digram occurs twice in a production then it must occur at the end of the rhs @return [TrueClass, FalseClass] true when the digram occurs twice in rhs.

# File lib/sequitur/production.rb, line 102
def repeated_digram?
  return false if rhs.size < 3

  my_digrams = digrams
  all_keys = my_digrams.map(&:key)
  last_key = all_keys.pop
  same_key_found = all_keys.index(last_key)
  !same_key_found.nil?
end
single_digram?() click to toggle source

Does the rhs have exactly one digram only (= 2 symbols)? @return [TrueClass, FalseClass] true when the rhs contains exactly two symbols.

# File lib/sequitur/production.rb, line 94
def single_digram?
  rhs.size == 2
end
to_string() click to toggle source

Emit a text representation of the production rule. Text is of the form: object id of production : rhs as space-separated sequence of symbols. @return [String]

# File lib/sequitur/production.rb, line 122
def to_string
  "#{object_id} : #{rhs.to_string}."
end