Class: Lrama::State

Inherits:
Object
  • Object
show all
Defined in:
lib/lrama/state.rb,
lib/lrama/state/shift.rb,
lib/lrama/state/reduce.rb,
lib/lrama/state/resolved_conflict.rb,
lib/lrama/state/shift_reduce_conflict.rb,
lib/lrama/state/reduce_reduce_conflict.rb

Defined Under Namespace

Classes: Reduce, ReduceReduceConflict, ResolvedConflict, Shift, ShiftReduceConflict

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(id, accessing_symbol, kernels) ⇒ State

Returns a new instance of State.



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/lrama/state.rb', line 15

def initialize(id, accessing_symbol, kernels)
  @id = id
  @accessing_symbol = accessing_symbol
  @kernels = kernels.freeze
  @items = @kernels
  # Manage relationships between items to state
  # to resolve next state
  @items_to_state = {}
  @conflicts = []
  @resolved_conflicts = []
  @default_reduction_rule = nil
  @predecessors = []
  @lalr_isocore = self
  @ielr_isocores = [self]
  @internal_dependencies = {}
  @successor_dependencies = {}
  @always_follows = {}
end

Instance Attribute Details

#accessing_symbol ⇒ Object (readonly)

Returns the value of attribute accessing_symbol.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def accessing_symbol
  @accessing_symbol
end

#closure ⇒ Object

Returns the value of attribute closure.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def closure
  @closure
end

#conflicts ⇒ Object (readonly)

Returns the value of attribute conflicts.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def conflicts
  @conflicts
end

#default_reduction_rule ⇒ Object

Returns the value of attribute default_reduction_rule.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def default_reduction_rule
  @default_reduction_rule
end

#id ⇒ Object (readonly)

Returns the value of attribute id.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def id
  @id
end

#ielr_isocores ⇒ Object

Returns the value of attribute ielr_isocores.



13
14
15
 
# File 'lib/lrama/state.rb', line 13

def ielr_isocores
  @ielr_isocores
end

#items ⇒ Object (readonly)

Returns the value of attribute items.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def items
  @items
end

#kernels ⇒ Object (readonly)

Returns the value of attribute kernels.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def kernels
  @kernels
end

#lalr_isocore ⇒ Object

Returns the value of attribute lalr_isocore.



13
14
15
 
# File 'lib/lrama/state.rb', line 13

def lalr_isocore
  @lalr_isocore
end

#reduces ⇒ Object

Returns the value of attribute reduces.



13
14
15
 
# File 'lib/lrama/state.rb', line 13

def reduces
  @reduces
end

#resolved_conflicts ⇒ Object (readonly)

Returns the value of attribute resolved_conflicts.



11
12
13
 
# File 'lib/lrama/state.rb', line 11

def resolved_conflicts
  @resolved_conflicts
end

#shifts ⇒ Object

Returns the value of attribute shifts.



13
14
15
 
# File 'lib/lrama/state.rb', line 13

def shifts
  @shifts
end

Instance Method Details

#always_follows(shift, next_state) ⇒ Object 



379
380
381
382
383
384
385
386
387
388
389
390
391
 
# File 'lib/lrama/state.rb', line 379

def always_follows(shift, next_state)
  return @always_follows[[shift, next_state]] if @always_follows[[shift, next_state]]

  queue = internal_dependencies(shift, next_state) + successor_dependencies(shift, next_state)
  terms = []
  until queue.empty?
    st, sh, next_st = queue.pop
    terms |= next_st.term_transitions.map {|sh, _| sh.next_sym }
    st.internal_dependencies(sh, next_st).each {|v| queue << v }
    st.successor_dependencies(sh, next_st).each {|v| queue << v }
  end
  @always_follows[[shift, next_state]] = terms
end

#annotate_manifestation ⇒ Object 



259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
 
# File 'lib/lrama/state.rb', line 259

def annotate_manifestation
  inadequacy_list.transform_values {|actions|
    actions.map {|action|
      if action.is_a?(Shift)
        [action, nil]
      elsif action.is_a?(Reduce)
        if action.rule.empty_rule?
          [action, lhs_contributions(action.rule.lhs, inadequacy_list.key(actions))]
        else
          contributions = kernels.map {|kernel| [kernel, kernel.rule == action.rule && kernel.end_of_rule?] }.to_h
          [action, contributions]
        end
      end
    }.to_h
  }
end

#annotate_predecessor(predecessor) ⇒ Object 



276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
 
# File 'lib/lrama/state.rb', line 276

def annotate_predecessor(predecessor)
  annotation_list.transform_values {|actions|
    token = annotation_list.key(actions)
    actions.transform_values {|inadequacy|
      next nil if inadequacy.nil?
      lhs_adequacy = kernels.any? {|kernel|
        inadequacy[kernel] && kernel.position == 1 && predecessor.lhs_contributions(kernel.lhs, token).nil?
      }
      if lhs_adequacy
        next nil
      else
        predecessor.kernels.map {|pred_k|
          [pred_k, kernels.any? {|k|
            inadequacy[k] && (
              pred_k.predecessor_item_of?(k) && predecessor.item_lookahead_set[pred_k].include?(token) ||
              k.position == 1 && predecessor.lhs_contributions(k.lhs, token)[pred_k]
            )
          }]
        }.to_h
      end
    }
  }
end

#annotation_list ⇒ Object 



235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
 
# File 'lib/lrama/state.rb', line 235

def annotation_list
  return @annotation_list if @annotation_list

  @annotation_list = annotate_manifestation
  @annotation_list = @items_to_state.values.map {|next_state| next_state.annotate_predecessor(self) }
    .reduce(@annotation_list) {|result, annotations|
      result.merge(annotations) {|_, actions_a, actions_b|
        if actions_a.nil? || actions_b.nil?
          actions_a || actions_b
        else
          actions_a.merge(actions_b) {|_, contributions_a, contributions_b|
            if contributions_a.nil? || contributions_b.nil?
              next contributions_a || contributions_b
            end

            contributions_a.merge(contributions_b) {|_, contributed_a, contributed_b|
              contributed_a || contributed_b
            }
          }
        end
      }
    }
end

#append_predecessor(prev_state) ⇒ Object 



352
353
354
355
 
# File 'lib/lrama/state.rb', line 352

def append_predecessor(prev_state)
  @predecessors << prev_state
  @predecessors.uniq!
end

#clear_transitions_cache ⇒ Object 



99
100
101
102
103
 
# File 'lib/lrama/state.rb', line 99

def clear_transitions_cache
  @nterm_transitions = nil
  @term_transitions = nil
  @transitions = nil
end

#compatible_lookahead?(filtered_lookahead) ⇒ Boolean

Returns:

  • (Boolean) 


182
183
184
185
186
187
188
189
 
# File 'lib/lrama/state.rb', line 182

def compatible_lookahead?(filtered_lookahead)
  !lookaheads_recomputed ||
    @lalr_isocore.annotation_list.all? {|token, actions|
      a = dominant_contribution(token, actions, item_lookahead_set)
      b = dominant_contribution(token, actions, filtered_lookahead)
      a.nil? || b.nil? || a == b
    }
end

#compute_shifts_reduces ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/lrama/state.rb', line 45

def compute_shifts_reduces
  _shifts = {}
  reduces = []
  items.each do |item|
    # TODO: Consider what should be pushed
    if item.end_of_rule?
      reduces << Reduce.new(item)
    else
      key = item.next_sym
      _shifts[key] ||= []
      _shifts[key] << item.new_by_next_position
    end
  end

  # It seems Bison 3.8.2 iterates transitions order by symbol number
  shifts = _shifts.sort_by do |next_sym, new_items|
    next_sym.number
  end.map do |next_sym, new_items|
    Shift.new(next_sym, new_items.flatten)
  end
  self.shifts = shifts.freeze
  self.reduces = reduces.freeze
end

#dominant_contribution(token, actions, lookaheads) ⇒ Object 



203
204
205
206
207
208
209
210
211
212
213
214
215
 
# File 'lib/lrama/state.rb', line 203

def dominant_contribution(token, actions, lookaheads)
  a = actions.select {|action, contributions|
    contributions.nil? || contributions.any? {|item, contributed| contributed && lookaheads[item].include?(token) }
  }.map {|action, _| action }
  return nil if a.empty?
  a.reject {|action|
    if action.is_a?(State::Shift)
      action.not_selected
    elsif action.is_a?(State::Reduce)
      action.not_selected_symbols.include?(token)
    end
  }
end

#find_reduce_by_item!(item) ⇒ Object 



132
133
134
135
136
 
# File 'lib/lrama/state.rb', line 132

def find_reduce_by_item!(item)
  reduces.find do |r|
    r.item == item
  end || (raise "reduce is not found. #{item}")
end

#follow_kernel_items(shift, next_state, kernel) ⇒ Object 



309
310
311
312
313
314
315
316
317
 
# File 'lib/lrama/state.rb', line 309

def follow_kernel_items(shift, next_state, kernel)
  queue = [[self, shift, next_state]]
  until queue.empty?
    st, sh, next_st = queue.pop
    return true if kernel.next_sym == sh.next_sym && kernel.symbols_after_transition.all?(&:nullable)
    st.internal_dependencies(sh, next_st).each {|v| queue << v }
  end
  false
end

#goto_follow_set(nterm_token) ⇒ Object 



357
358
359
360
361
362
363
364
365
 
# File 'lib/lrama/state.rb', line 357

def goto_follow_set(nterm_token)
  return [] if nterm_token.accept_symbol?
  shift, next_state = @lalr_isocore.nterm_transitions.find {|sh, _| sh.next_sym == nterm_token }

  @kernels
    .select {|kernel| follow_kernel_items(shift, next_state, kernel) }
    .map {|kernel| item_lookahead_set[kernel] }
    .reduce(always_follows(shift, next_state)) {|result, terms| result |= terms }
end

#goto_follows(shift, next_state) ⇒ Object 



367
368
369
370
371
372
373
374
375
376
377
 
# File 'lib/lrama/state.rb', line 367

def goto_follows(shift, next_state)
  queue = internal_dependencies(shift, next_state) + predecessor_dependencies(shift, next_state)
  terms = always_follows(shift, next_state)
  until queue.empty?
    st, sh, next_st = queue.pop
    terms |= st.always_follows(sh, next_st)
    st.internal_dependencies(sh, next_st).each {|v| queue << v }
    st.predecessor_dependencies(sh, next_st).each {|v| queue << v }
  end
  terms
end

#has_conflicts? ⇒ Boolean

Returns:

  • (Boolean) 


148
149
150
 
# File 'lib/lrama/state.rb', line 148

def has_conflicts?
  !@conflicts.empty?
end

#inadequacy_list ⇒ Object 



217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/lrama/state.rb', line 217

def inadequacy_list
  return @inadequacy_list if @inadequacy_list

  shift_contributions = shifts.map {|shift|
    [shift.next_sym, [shift]]
  }.to_h
  reduce_contributions = reduces.map {|reduce|
    (reduce.look_ahead || []).map {|sym|
      [sym, [reduce]]
    }.to_h
  }.reduce(Hash.new([])) {|hash, cont|
    hash.merge(cont) {|_, a, b| a | b }
  }

  list = shift_contributions.merge(reduce_contributions) {|_, a, b| a | b }
  @inadequacy_list = list.select {|token, actions| token.term? && actions.size > 1 }
end

#internal_dependencies(shift, next_state) ⇒ Object 



393
394
395
396
397
398
399
400
 
# File 'lib/lrama/state.rb', line 393

def internal_dependencies(shift, next_state)
  return @internal_dependencies[[shift, next_state]] if @internal_dependencies[[shift, next_state]]

  syms = @items.select {|i|
    i.next_sym == shift.next_sym && i.symbols_after_transition.all?(&:nullable) && i.position == 0
  }.map(&:lhs).uniq
  @internal_dependencies[[shift, next_state]] = nterm_transitions.select {|sh, _| syms.include?(sh.next_sym) }.map {|goto| [self, *goto] }
end

#item_lookahead_set ⇒ Object 



319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'lib/lrama/state.rb', line 319

def item_lookahead_set
  return @item_lookahead_set if @item_lookahead_set

  kernels.map {|item|
    value =
      if item.lhs.accept_symbol?
        []
      elsif item.position > 1
        prev_items = predecessors_with_item(item)
        prev_items.map {|st, i| st.item_lookahead_set[i] }.reduce([]) {|acc, syms| acc |= syms }
      elsif item.position == 1
        prev_state = @predecessors.find {|p| p.shifts.any? {|shift| shift.next_sym == item.lhs } }
        shift, next_state = prev_state.nterm_transitions.find {|shift, _| shift.next_sym == item.lhs }
        prev_state.goto_follows(shift, next_state)
      end
    [item, value]
  }.to_h
end

#item_lookahead_set=(k) ⇒ Object 



338
339
340
 
# File 'lib/lrama/state.rb', line 338

def item_lookahead_set=(k)
  @item_lookahead_set = k
end

#lhs_contributions(sym, token) ⇒ Object 



300
301
302
303
304
305
306
307
 
# File 'lib/lrama/state.rb', line 300

def lhs_contributions(sym, token)
  shift, next_state = nterm_transitions.find {|sh, _| sh.next_sym == sym }
  if always_follows(shift, next_state).include?(token)
    nil
  else
    kernels.map {|kernel| [kernel, follow_kernel_items(shift, next_state, kernel) && item_lookahead_set[kernel].include?(token)] }.to_h
  end
end

#lookahead_set_filters ⇒ Object 



191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/lrama/state.rb', line 191

def lookahead_set_filters
  kernels.map {|kernel|
    [kernel,
     @lalr_isocore.annotation_list.select {|token, actions|
       token.term? && actions.any? {|action, contributions|
         !contributions.nil? && contributions.key?(kernel) && contributions[kernel]
       }
     }.map {|token, _| token }
    ]
  }.to_h
end

#lookaheads_recomputed ⇒ Object 



178
179
180
 
# File 'lib/lrama/state.rb', line 178

def lookaheads_recomputed
  !@item_lookahead_set.nil?
end

#non_default_reduces ⇒ Object 



39
40
41
42
43
 
# File 'lib/lrama/state.rb', line 39

def non_default_reduces
  reduces.reject do |reduce|
    reduce.rule == @default_reduction_rule
  end
end

#nterm_transitions ⇒ Object 



81
82
83
 
# File 'lib/lrama/state.rb', line 81

def nterm_transitions
  @nterm_transitions ||= transitions.select {|shift, _| shift.next_sym.nterm? }
end

#predecessor_dependencies(shift, next_state) ⇒ Object 



411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
 
# File 'lib/lrama/state.rb', line 411

def predecessor_dependencies(shift, next_state)
  state_items = []
  @kernels.select {|kernel|
    kernel.next_sym == shift.next_sym && kernel.symbols_after_transition.all?(&:nullable)
  }.each do |item|
    queue = predecessors_with_item(item)
    until queue.empty?
      st, i = queue.pop
      if i.position == 0
        state_items << [st, i]
      else
        st.predecessors_with_item(i).each {|v| queue << v }
      end
    end
  end

  state_items.map {|state, item|
    sh, next_st = state.nterm_transitions.find {|shi, _| shi.next_sym == item.lhs }
    [state, sh, next_st]
  }
end

#predecessors_with_item(item) ⇒ Object 



342
343
344
345
346
347
348
349
350
 
# File 'lib/lrama/state.rb', line 342

def predecessors_with_item(item)
  result = []
  @predecessors.each do |pre|
    pre.items.each do |i|
      result << [pre, i] if i.predecessor_item_of?(item)
    end
  end
  result
end

#propagate_lookaheads(next_state) ⇒ Object 



164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/lrama/state.rb', line 164

def propagate_lookaheads(next_state)
  next_state.kernels.map {|item|
    lookahead_sets =
      if item.position == 1
        goto_follow_set(item.lhs)
      else
        kernel = kernels.find {|k| k.predecessor_item_of?(item) }
        item_lookahead_set[kernel]
      end

    [item, lookahead_sets & next_state.lookahead_set_filters[item]]
  }.to_h
end

#rr_conflicts ⇒ Object 



158
159
160
161
162
 
# File 'lib/lrama/state.rb', line 158

def rr_conflicts
  @conflicts.select do |conflict|
    conflict.type == :reduce_reduce
  end
end

#selected_term_transitions ⇒ Object 



105
106
107
108
109
 
# File 'lib/lrama/state.rb', line 105

def selected_term_transitions
  term_transitions.reject do |shift, next_state|
    shift.not_selected
  end
end

#set_items_to_state(items, next_state) ⇒ Object 



69
70
71
 
# File 'lib/lrama/state.rb', line 69

def set_items_to_state(items, next_state)
  @items_to_state[items] = next_state
end

#set_look_ahead(rule, look_ahead) ⇒ Object 



73
74
75
76
77
78
79
 
# File 'lib/lrama/state.rb', line 73

def set_look_ahead(rule, look_ahead)
  reduce = reduces.find do |r|
    r.rule == rule
  end

  reduce.look_ahead = look_ahead
end

#sr_conflicts ⇒ Object 



152
153
154
155
156
 
# File 'lib/lrama/state.rb', line 152

def sr_conflicts
  @conflicts.select do |conflict|
    conflict.type == :shift_reduce
  end
end

#successor_dependencies(shift, next_state) ⇒ Object 



402
403
404
405
406
407
408
409
 
# File 'lib/lrama/state.rb', line 402

def successor_dependencies(shift, next_state)
  return @successor_dependencies[[shift, next_state]] if @successor_dependencies[[shift, next_state]]

  @successor_dependencies[[shift, next_state]] =
    next_state.nterm_transitions
    .select {|next_shift, _| next_shift.next_sym.nullable }
    .map {|transition| [next_state, *transition] }
end

#term_transitions ⇒ Object 



85
86
87
 
# File 'lib/lrama/state.rb', line 85

def term_transitions
  @term_transitions ||= transitions.select {|shift, _| shift.next_sym.term? }
end

#transition(sym) ⇒ Object

Move to next state by sym



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/lrama/state.rb', line 112

def transition(sym)
  result = nil

  if sym.term?
    term_transitions.each do |shift, next_state|
      term = shift.next_sym
      result = next_state if term == sym
    end
  else
    nterm_transitions.each do |shift, next_state|
      nterm = shift.next_sym
      result = next_state if nterm == sym
    end
  end

  raise "Can not transit by #{sym} #{self}" if result.nil?

  result
end

#transitions ⇒ Object 



89
90
91
 
# File 'lib/lrama/state.rb', line 89

def transitions
  @transitions ||= shifts.map {|shift| [shift, @items_to_state[shift.next_items]] }
end

#update_transition(shift, next_state) ⇒ Object 



93
94
95
96
97
 
# File 'lib/lrama/state.rb', line 93

def update_transition(shift, next_state)
  set_items_to_state(shift.next_items, next_state)
  next_state.append_predecessor(self)
  clear_transitions_cache
end