Class: Ibex::LALR::IELR::StateSplitter

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/lalr/ielr/state_splitter.rb,
sig/ibex/lalr/ielr/state_splitter.rbs

Overview

Splits LR(0) isocores only where an inadequacy would change the resolved action. New states copy their transition arrays; no mutable transition table is shared between isocores.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, states, transitions, items, goto_follows, resolver: nil) ⇒ StateSplitter

rubocop:disable Metrics/AbcSize -- initialization wires the phase tables once.

RBS:

  • (IR::Grammar grammar, Array[core_set] states, transitions transitions, Array[packed_items] items, GotoFollows goto_follows, ?resolver: ConflictResolver?) -> void

Parameters:



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 29

def initialize(grammar, states, transitions, items, goto_follows, resolver: nil)
  @grammar = grammar
  @base_states = states
  @base_transitions = transitions
  @base_items = items
  @goto_follows = goto_follows
  @resolver = resolver || ConflictResolver.new(grammar)
  @kernel_cores = states.map { |state| kernel_items(state) }
  annotator = Annotator.new(grammar, states, transitions, items, goto_follows, resolver: @resolver)
  @annotations = annotator.build
  @inadequacies = annotator.inadequacies
  @split_stable_discarded = annotator.split_stable_discarded
  @item_lookaheads = annotator.item_lookaheads
  @states = states.each_with_index.map do |_state, state_id|
    SplitState.new(core: @kernel_cores.fetch(state_id),
                   transitions: transitions.fetch(state_id).sort_by(&:first).map(&:dup),
                   lalr_isocore: state_id)
  end
  @lalr_isocores = states.each_index.to_a
  @isocore_nexts = states.each_index.to_a
  @lookaheads_recomputed = Array.new(states.length, false)
  @lookahead_sets = states.each_with_index.map do |_state, state_id|
    @kernel_cores.fetch(state_id).each_index.map do |index|
      @item_lookaheads.fetch(state_id, index)
    end
  end
  @filters = {}
  @split_states = 0
end

Instance Attribute Details

#annotations ⇒ Array[Array[Annotation]] (readonly)

Signature:

  • Array[Array[Annotation]]

Returns:



19
20
21
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 19

def annotations
  @annotations
end

#inadequacies ⇒ Array[Array[Inadequacy]] (readonly)

Signature:

  • Array[Array[Inadequacy]]

Returns:



23
24
25
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 23

def inadequacies
  @inadequacies
end

#lalr_isocores ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


21
22
23
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 21

def lalr_isocores
  @lalr_isocores
end

#split_stable_discarded ⇒ Integer (readonly)

Signature:

  • Integer

Returns:

  • (Integer) 


24
25
26
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 24

def split_stable_discarded
  @split_stable_discarded
end

#split_states ⇒ Integer (readonly)

Signature:

  • Integer

Returns:

  • (Integer) 


22
23
24
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 22

def split_states
  @split_states
end

#states ⇒ Array[SplitState] (readonly)

Signature:

  • Array[SplitState]

Returns:



20
21
22
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 20

def states
  @states
end

Instance Method Details

#append_isocore(after_id, lookaheads) ⇒ Integer

RBS:

  • (Integer after_id, Array[Integer]) -> Integer

Parameters:

  • after_id (Integer)
  • (Array[Integer])

Returns:

  • (Integer) 


175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 175

def append_isocore(after_id, lookaheads)
  source = @states.fetch(after_id)
  @states << SplitState.new(
    core: source.core.dup,
    transitions: source.transitions.map(&:dup),
    lalr_isocore: @lalr_isocores.fetch(after_id)
  )
  appended = @states.length - 1
  @lalr_isocores << @lalr_isocores.fetch(after_id)
  @isocore_nexts << @isocore_nexts.fetch(after_id)
  @isocore_nexts[after_id] = appended
  @lookaheads_recomputed << true
  @lookahead_sets << lookaheads
  @split_states += 1
  appended
end

#build ⇒ [ Array[packed_items], transitions ]

RBS:

  • () -> [Array[packed_items], transitions]

Returns:

  • ([ Array[packed_items], transitions ]) 


61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 61

def build
  state_id = 0
  while state_id < @states.length
    @states.fetch(state_id).transitions.each_index do |index|
      target = @states.fetch(state_id).transitions.fetch(index).fetch(1)
      compute_state(state_id, target, index)
    end
    state_id += 1
  end
  [pack_items, packed_transitions]
end

#compatible?(state_id, incoming) ⇒ Boolean

RBS:

  • (Integer state_id, Array[Integer]) -> bool

Parameters:

  • state_id (Integer)
  • (Array[Integer])

Returns:

  • (Boolean) 


149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 149

def compatible?(state_id, incoming)
  return true unless @lookaheads_recomputed.fetch(state_id)

  @annotations.fetch(@lalr_isocores.fetch(state_id)).all? do |annotation|
    current = dominant_contribution(annotation, @lookahead_sets.fetch(state_id))
    next true unless current

    candidate = dominant_contribution(annotation, incoming)
    !candidate || current == candidate
  end
end

#compute_goto_follow_set(state_id, nonterminal_id) ⇒ Integer

RBS:

  • (Integer state_id, Integer nonterminal_id) -> Integer

Parameters:

  • state_id (Integer)
  • nonterminal_id (Integer)

Returns:

  • (Integer) 


120
121
122
123
124
125
126
127
128
129
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 120

def compute_goto_follow_set(state_id, nonterminal_id)
  goto_id = @goto_follows.goto_for(@lalr_isocores.fetch(state_id), nonterminal_id)
  raise Ibex::Error, "missing GOTO for #{nonterminal_id} from #{state_id}" unless goto_id

  bits = @goto_follows.always_follows.fetch(goto_id)
  Bits.each_set_bit(@goto_follows.follow_kernel_items.fetch(goto_id)) do |index|
    bits |= @lookahead_sets.fetch(state_id).fetch(index)
  end
  bits
end

#compute_state(from_id, to_id, transition_index) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer from_id, Integer to_id, Integer transition_index) -> void

Parameters:

  • from_id (Integer)
  • to_id (Integer)
  • transition_index (Integer) 


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
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 76

def compute_state(from_id, to_id, transition_index)
  incoming = propagate_lookaheads(from_id, to_id)
  target = to_id
  found = false
  loop do
    if compatible?(target, incoming)
      found = true
      break
    end
    break if @isocore_nexts.fetch(target) == to_id

    target = @isocore_nexts.fetch(target)
  end

  if !found
    target = append_isocore(target, incoming)
  elsif !@lookaheads_recomputed.fetch(target)
    raise Ibex::Error, "IELR target changed before initial lookahead computation" unless target == to_id

    @lookahead_sets[target] = incoming
    @lookaheads_recomputed[target] = true
  else
    merge_lookaheads(target, incoming)
  end
  @states.fetch(from_id).transitions.fetch(transition_index)[1] = target
end

#dominant_contribution(annotation, lookaheads) ⇒ Object?

RBS:

  • (Annotation, Array[Integer]) -> Object?

Parameters:

Returns:

  • (Object, nil) 


162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 162

def dominant_contribution(annotation, lookaheads)
  token_bit = 1 << annotation.inadequacy.token
  selected = annotation.inadequacy.contributions.each_index.select do |index|
    row = annotation.matrix.fetch(index)
    row.nil? || Bits.each_set_bit(row).any? { |kernel| lookaheads.fetch(kernel).anybits?(token_bit) }
  end
  return nil if selected.empty?

  contributions = selected.map { |index| annotation.inadequacy.contributions.fetch(index) }
  SplitStability.resolve(@resolver, annotation.inadequacy.token, contributions)
end

#kernel_index_of(state_id, production_id, dot) ⇒ Integer?

RBS:

  • (Integer state_id, Integer production_id, Integer dot) -> Integer?

Parameters:

  • state_id (Integer)
  • production_id (Integer)
  • dot (Integer)

Returns:

  • (Integer, nil) 


237
238
239
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 237

def kernel_index_of(state_id, production_id, dot)
  @kernel_cores.fetch(@lalr_isocores.fetch(state_id)).index([production_id, dot])
end

#kernel_items(items) ⇒ Array[item_core]

RBS:

  • (core_set items) -> Array[item_core]

Parameters:

  • items (core_set)

Returns:

  • (Array[item_core]) 


232
233
234
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 232

def kernel_items(items)
  items.select { |production_id, dot| production_id.negative? || dot.positive? }.to_a.sort
end

#lhs_for(production_id) ⇒ Integer

RBS:

  • (Integer production_id) -> Integer

Parameters:

  • production_id (Integer)

Returns:

  • (Integer) 


242
243
244
245
246
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 242

def lhs_for(production_id)
  return @grammar.symbol(@grammar.starts.fetch(-production_id - 1)).id if production_id.negative?

  @grammar.productions.fetch(production_id).lhs
end

#lookahead_set_filters(state_id) ⇒ Array[Integer]

RBS:

  • (Integer state_id) -> Array[Integer]

Parameters:

  • state_id (Integer)

Returns:

  • (Array[Integer]) 


132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 132

def lookahead_set_filters(state_id)
  core_id = @lalr_isocores.fetch(state_id)
  return @filters.fetch(core_id) if @filters.key?(core_id)

  filters = Array.new(@kernel_cores.fetch(core_id).length, 0)
  @annotations.fetch(core_id).each do |annotation|
    token_bit = 1 << annotation.inadequacy.token
    annotation.matrix.each do |row|
      next if row.nil?

      Bits.each_set_bit(row) { |index| filters[index] |= token_bit }
    end
  end
  @filters[core_id] = filters
end

#merge_lookaheads(state_id, incoming) ⇒ void

This method returns an undefined value.

RBS:

  • (Integer state_id, Array[Integer]) -> void

Parameters:

  • state_id (Integer)
  • (Array[Integer]) 


193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 193

def merge_lookaheads(state_id, incoming)
  changed = false
  incoming.each_with_index do |bits, index|
    added = bits & ~@lookahead_sets.fetch(state_id).fetch(index)
    next if added.zero?

    @lookahead_sets.fetch(state_id)[index] |= added
    changed = true
  end
  return unless changed

  @states.fetch(state_id).transitions.each_index do |index|
    target = @states.fetch(state_id).transitions.fetch(index).fetch(1)
    break unless @lookaheads_recomputed.fetch(target)

    compute_state(state_id, target, index)
  end
end

#pack_items ⇒ Array[packed_items]

RBS:

  • () -> Array[packed_items]

Returns:

  • (Array[packed_items]) 


213
214
215
216
217
218
219
220
221
222
223
224
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 213

def pack_items
  @states.each_with_index.map do |state, state_id|
    packed = Hash.new { |hash, key| hash[key] = Set.new }
    @base_items.fetch(state.lalr_isocore).each do |core, values|
      packed[core].merge(values)
    end
    state.core.each_with_index do |core, index|
      packed[core] = Set.new(Bits.each_set_bit(@lookahead_sets.fetch(state_id).fetch(index)).to_a)
    end
    packed
  end
end

#packed_transitions ⇒ transitions

RBS:

  • () -> transitions

Returns:

  • (transitions) 


227
228
229
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 227

def packed_transitions
  @states.map { |state| state.transitions.to_h { |symbol, target| [symbol, target] } }
end

#propagate_lookaheads(from_id, to_id) ⇒ Array[Integer]

RBS:

  • (Integer from_id, Integer to_id) -> Array[Integer]

Parameters:

  • from_id (Integer)
  • to_id (Integer)

Returns:

  • (Array[Integer]) 


104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 104

def propagate_lookaheads(from_id, to_id)
  filters = lookahead_set_filters(to_id)
  @kernel_cores.fetch(to_id).each_with_index.map do |(production_id, dot), index|
    bits = if dot > 1
             previous = kernel_index_of(from_id, production_id, dot - 1)
             previous ? @lookahead_sets.fetch(from_id).fetch(previous) : 0
           elsif dot == 1
             compute_goto_follow_set(from_id, lhs_for(production_id))
           else
             raise Ibex::Error, "IELR transition produced a dot-zero kernel"
           end
    bits & filters.fetch(index)
  end
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


249
250
251
252
253
 
# File 'lib/ibex/lalr/ielr/state_splitter.rb', line 249

def rhs_for(production_id)
  return [lhs_for(production_id)] if production_id.negative?

  @grammar.productions.fetch(production_id).rhs
end