Class: Sequitur::Production

Inherits:
Object
  • Object
show all
Defined in:
lib/sequitur/production.rb

Overview

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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Production

Constructor. Build a production with an empty RHS.



27
28
29
30
31
 
# File 'lib/sequitur/production.rb', line 27

def initialize()
  clear_rhs
  @refcount = 0
  @digrams = []
end

Instance Attribute Details

#digrams ⇒ Object (readonly)

The sequence of digrams appearing in the RHS



23
24
25
 
# File 'lib/sequitur/production.rb', line 23

def digrams
  @digrams
end

#refcount ⇒ Object (readonly)

The reference count (= how times other productions reference this one)



20
21
22
 
# File 'lib/sequitur/production.rb', line 20

def refcount
  @refcount
end

#rhs ⇒ Object (readonly)

The right-hand side (rhs) consists of a sequence of grammar symbols



17
18
19
 
# File 'lib/sequitur/production.rb', line 17

def rhs
  @rhs
end

Instance Method Details

#==(other) ⇒ Object

Identity testing.

Parameters:

  • other —

    [] another production or production reference.

Returns:

  • true when the receiver and other are the same.



38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/sequitur/production.rb', line 38

def ==(other)
  return true if object_id == other.object_id

  if other.is_a?(ProductionRef)
    result = (other == self)
  else
    result = false
  end

  return result
end

#accept(aVisitor) ⇒ Object

Part of the 'visitee' role in Visitor design pattern.

Parameters:



253
254
255
256
257
258
259
260
261
262
263
264
265
 
# File 'lib/sequitur/production.rb', line 253

def accept(aVisitor)
  aVisitor.start_visit_production(self)

  rhs.each do |a_symb|
    if a_symb.is_a?(ProductionRef)
      a_symb.accept(aVisitor)
    else
      aVisitor.visit_terminal(a_symb)
    end
  end

  aVisitor.end_visit_production(self)
end

#append_symbol(aSymbol) ⇒ Object

Add a (grammar) symbol at the end of the RHS.

Parameters:

  • aSymbol (Object) —

    A (grammar) symbol to add.



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/sequitur/production.rb', line 144

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
        fail 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 ⇒ Object

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



165
166
167
168
169
170
171
 
# File 'lib/sequitur/production.rb', line 165

def clear_rhs()
  if rhs
    refs = references
    refs.each(&:unbind)
  end
  @rhs = []
end

#decr_refcount ⇒ Object

Decrement the reference count by one.



63
64
65
66
 
# File 'lib/sequitur/production.rb', line 63

def decr_refcount()
  fail StandardError, 'Internal error' if @refcount == 0
  @refcount -= 1
end

#derive_step(another) ⇒ Object

Replace every occurrence of 'another' production in self.rhs by the symbols in the rhs of 'another'.

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

Examples:

Synopsis

Parameters:



234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# File 'lib/sequitur/production.rb', line 234

def derive_step(another)
  (0...rhs.size).to_a.reverse.each do |index|
    next unless rhs[index] == another

    # Avoid the aliasing of production reference
    other_rhs = another.rhs.map do |symb|
      symb.is_a?(ProductionRef) ? symb.dup : symb
    end
    rhs.insert(index + 1, *other_rhs)
    another.decr_refcount
    rhs.delete_at(index)
  end

  recalc_digrams
end

#empty? ⇒ Boolean

Is the rhs empty? @ return true if the rhs has no members.

Returns:

  • (Boolean) 


53
54
55
 
# File 'lib/sequitur/production.rb', line 53

def empty?
  return rhs.empty?
end

#incr_refcount ⇒ Object

Increment the reference count by one.



58
59
60
 
# File 'lib/sequitur/production.rb', line 58

def incr_refcount()
  @refcount += 1
end

#last_digram ⇒ Digram

Retrieve the last digram appearing in the RHS (if any).

Returns:

  • (Digram) —

    last digram in the rhs otherwise nil.



120
121
122
123
 
# File 'lib/sequitur/production.rb', line 120

def last_digram()
  result = digrams.empty? ? nil : digrams.last
  return result
end

#positions_of(symb1, symb2) ⇒ Array

Find all the positions where the digram occurs in the rhs

Examples:

# 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]

Parameters:

  • symb1 (Object) —

    first symbol of the digram

  • symb2 (Object) —

    second symbol of the digram

Returns:

  • (Array) —

    the list of indices where the digram occurs in rhs.



185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/sequitur/production.rb', line 185

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

  return indices
end

#recalc_digrams ⇒ Array

Enumerate the digrams appearing in the right-hand side (rhs)

Returns:

  • (Array) —

    the list of digrams found in rhs of this production.



86
87
88
89
90
91
92
93
 
# File 'lib/sequitur/production.rb', line 86

def recalc_digrams()
  return [] if rhs.size < 2

  result = []
  rhs.each_cons(2) { |couple| result << Digram.new(*couple, self) }

  @digrams = result
end

#reduce_step(another) ⇒ Object

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.

Parameters:



205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/sequitur/production.rb', line 205

def reduce_step(another)
  (symb1, symb2) = another.rhs
  pos = positions_of(symb1, symb2).reverse

  # Replace the two symbol sequence by the production
  pos.each do |index|
    if rhs[index].is_a?(ProductionRef)
      rhs[index].bind_to(another)
    else
      rhs[index] = ProductionRef.new(another)
    end
    index1 = index + 1
    rhs[index1].unbind if rhs[index1].is_a?(ProductionRef)
    rhs.delete_at(index1)
  end

  recalc_digrams
end

#references ⇒ Array of ProductionRef

Select the references to production appearing in the rhs.

Returns:



71
72
73
 
# File 'lib/sequitur/production.rb', line 71

def references()
  return rhs.select { |symb| symb.is_a?(ProductionRef) }
end

#references_of(aProduction) ⇒ Array

Look in the rhs all the references to a production passed a argument. aProduction [aProduction or ProductionRef] The production to search for.

Returns:

  • (Array) —

    the array of ProductionRef to the passed production



78
79
80
81
 
# File 'lib/sequitur/production.rb', line 78

def references_of(aProduction)
  refs = references
  return refs.select { |a_ref| a_ref == aProduction }
end

#repeated_digram? ⇒ true/false

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

Returns:

  • (true/false) —

    true when the digram occurs twice in rhs.



108
109
110
111
112
113
114
115
116
 
# File 'lib/sequitur/production.rb', line 108

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)
  return !same_key_found.nil?
end

#single_digram? ⇒ true/false

Does the rhs have exactly one digram only (= 2 symbols)?

Returns:

  • (true/false) —

    true when the rhs contains exactly two symbols.



99
100
101
 
# File 'lib/sequitur/production.rb', line 99

def single_digram?
  return rhs.size == 2
end

#to_string ⇒ String

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

Returns:

  • (String) 


131
132
133
134
135
136
137
138
139
140
 
# File 'lib/sequitur/production.rb', line 131

def to_string()
  rhs_text = rhs.map do |elem|
    case elem
      when String then "'#{elem}'"
      else elem.to_s
    end
  end

  return "#{object_id} : #{rhs_text.join(' ')}."
end