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



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

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 



34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/sequitur/production.rb', line 34

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

#append_symbol(aSymbol) ⇒ Object

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



130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/sequitur/production.rb', line 130

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 back reference counter decremented



151
152
153
154
155
156
157
 
# File 'lib/sequitur/production.rb', line 151

def clear_rhs()
  if rhs
    refs = references
    refs.each { |a_ref| a_ref.unbind }
  end
  @rhs = []
end

#decr_refcount ⇒ Object 



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

def decr_refcount()
  fail StandardError if @refcount == 0
  @refcount -= 1
end

#empty? ⇒ Boolean

Is the rhs empty?

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/sequitur/production.rb', line 48

def empty?
  return rhs.empty?
end

#incr_refcount ⇒ Object 



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

def incr_refcount()
  @refcount += 1
end

#last_digram ⇒ Object

Return the last digram appearing in the RHS.



108
109
110
111
 
# File 'lib/sequitur/production.rb', line 108

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

#positions_of(symb1, symb2) ⇒ Object

Find all the positions where the digram occurs in the rhs Synopsis: Given the production p -> a b c a b a b d Then p.positions_of(a, b) should returns [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) should returns [0, 3]



166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/sequitur/production.rb', line 166

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

Return the list digrams found in rhs of this production.



77
78
79
80
81
82
83
84
 
# File 'lib/sequitur/production.rb', line 77

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

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

  @digrams = result
end

#references ⇒ Object

Return the set of productions appearing in the rhs.



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

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

#references_of(aProduction) ⇒ Object

Return the set of references to a given production



68
69
70
71
 
# File 'lib/sequitur/production.rb', line 68

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

#repeated_digram? ⇒ Boolean

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:

  • (Boolean) 


97
98
99
100
101
102
103
104
105
 
# File 'lib/sequitur/production.rb', line 97

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

#replace_digram(another) ⇒ Object

Substitute in self all occurrences of the digram that appears in the rhs of the other production Pre-condition: another has a rhs with exactly one digram (= a two-symbol sequence).



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

def replace_digram(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

#replace_production(another) ⇒ Object

Replace every occurrence of 'another' production in rhs by the rhs of 'another'. Given the production p_A -> a p_B b p_B c And the production p_B -> x y Then the call p_A.replace_production(p_B) Modifies p_A as into: p_A -> a x y b x y c



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
 
# File 'lib/sequitur/production.rb', line 211

def replace_production(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

#single_digram? ⇒ Boolean

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

Returns:

  • (Boolean) 


89
90
91
 
# File 'lib/sequitur/production.rb', line 89

def single_digram?
  return rhs.size == 2
end

#to_string ⇒ Object

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



118
119
120
121
122
123
124
125
126
127
 
# File 'lib/sequitur/production.rb', line 118

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