Class: Lrama::State

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

Defined Under Namespace

Classes: Action, InadequacyAnnotation, Item, ReduceReduceConflict, ResolvedConflict, ShiftReduceConflict

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(id, accessing_symbol, kernels) ⇒ State

Returns a new instance of State.



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/lrama/state.rb', line 60

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 = {}
  @annotation_list = []
  @lookaheads_recomputed = false
  @follow_kernel_items = {}
  @always_follows = {}
  @goto_follows = {}
  @lhs_contributions = {}
  @lane_items = {}
end

Instance Attribute Details

#_transitions ⇒ Object

: Array[[Grammar::Symbol, Array[Item]]]



50
51
52
 
# File 'lib/lrama/state.rb', line 50

def _transitions
  @_transitions
end

#accessing_symbol ⇒ Object (readonly)

: Grammar::Symbol



38
39
40
 
# File 'lib/lrama/state.rb', line 38

def accessing_symbol
  @accessing_symbol
end

#always_follows ⇒ Object

: Hash[Action::Goto, Array[Grammar::Symbol]]



56
57
58
 
# File 'lib/lrama/state.rb', line 56

def always_follows
  @always_follows
end

#annotation_list ⇒ Object (readonly)

: Array



45
46
47
 
# File 'lib/lrama/state.rb', line 45

def annotation_list
  @annotation_list
end

#closure ⇒ Object

: Array



43
44
45
 
# File 'lib/lrama/state.rb', line 43

def closure
  @closure
end

#conflicts ⇒ Object (readonly)

: Array



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

def conflicts
  @conflicts
end

#default_reduction_rule ⇒ Object

: Grammar::Rule?



42
43
44
 
# File 'lib/lrama/state.rb', line 42

def default_reduction_rule
  @default_reduction_rule
end

#follow_kernel_items ⇒ Object

: Hash[Action::Goto, Hash[Item, bool]]



55
56
57
 
# File 'lib/lrama/state.rb', line 55

def follow_kernel_items
  @follow_kernel_items
end

#goto_follows ⇒ Object

: Hash[Action::Goto, Array[Grammar::Symbol]]



57
58
59
 
# File 'lib/lrama/state.rb', line 57

def goto_follows
  @goto_follows
end

#id ⇒ Object (readonly)

TODO: rbs-inline 0.11.0 doesn't support instance variables. Move these type declarations above instance variable definitions, once it's supported. see: https://github.com/soutaro/rbs-inline/pull/149

@rbs! type conflict = State::ShiftReduceConflict | State::ReduceReduceConflict type transition = Action::Shift | Action::Goto type lookahead_set = Hash[Item, Array[Grammar::Symbol]]

@id: Integer
@accessing_symbol: Grammar::Symbol
@kernels: Array[Item]
@items: Array[Item]
@items_to_state: Hash[Array[Item], State]
@conflicts: Array[conflict]
@resolved_conflicts: Array[ResolvedConflict]
@default_reduction_rule: Grammar::Rule?
@closure: Array[Item]
@nterm_transitions: Array[Action::Goto]
@term_transitions: Array[Action::Shift]
@transitions: Array[transition]
@internal_dependencies: Hash[Action::Goto, Array[Action::Goto]]
@successor_dependencies: Hash[Action::Goto, Array[Action::Goto]]


37
38
39
 
# File 'lib/lrama/state.rb', line 37

def id
  @id
end

#ielr_isocores ⇒ Object

: Array



52
53
54
 
# File 'lib/lrama/state.rb', line 52

def ielr_isocores
  @ielr_isocores
end

#items ⇒ Object (readonly)

: Array



44
45
46
 
# File 'lib/lrama/state.rb', line 44

def items
  @items
end

#items_to_state ⇒ Object (readonly)

: Hash[Array[Item], State]



47
48
49
 
# File 'lib/lrama/state.rb', line 47

def items_to_state
  @items_to_state
end

#kernels ⇒ Object (readonly)

: Array



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

def kernels
  @kernels
end

#lalr_isocore ⇒ Object

: State



53
54
55
 
# File 'lib/lrama/state.rb', line 53

def lalr_isocore
  @lalr_isocore
end

#lane_items ⇒ Object (readonly)

: Hash[State, Array[[Item, Item]]]



48
49
50
 
# File 'lib/lrama/state.rb', line 48

def lane_items
  @lane_items
end

#lookaheads_recomputed ⇒ Object

: bool



54
55
56
 
# File 'lib/lrama/state.rb', line 54

def lookaheads_recomputed
  @lookaheads_recomputed
end

#predecessors ⇒ Object (readonly)

: Array



46
47
48
 
# File 'lib/lrama/state.rb', line 46

def predecessors
  @predecessors
end

#reduces ⇒ Object

: Array



51
52
53
 
# File 'lib/lrama/state.rb', line 51

def reduces
  @reduces
end

#resolved_conflicts ⇒ Object (readonly)

: Array



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

def resolved_conflicts
  @resolved_conflicts
end

Instance Method Details

#==(other) ⇒ Object 



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

def ==(other)
  self.id == other.id
end

#annotate_manifestation ⇒ Object

Definition 3.30 (annotate_manifestation)



352
353
354
355
356
357
358
359
360
361
362
363
 
# File 'lib/lrama/state.rb', line 352

def annotate_manifestation
  inadequacy_list.each {|token, actions|
    contribution_matrix = actions.map {|action|
      if action.is_a?(Action::Shift)
        [action, nil]
      else
        [action, action.rule.empty_rule? ? lhs_contributions(action.rule.lhs, token) : kernels.map {|k| [k, k.rule == action.item.rule && k.end_of_rule?] }.to_h]
      end
    }.to_h
    @annotation_list << InadequacyAnnotation.new(self, token, actions, contribution_matrix)
  }
end

#annotate_predecessor(predecessor) ⇒ Object

Definition 3.32 (annotate_predecessor)



368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
 
# File 'lib/lrama/state.rb', line 368

def annotate_predecessor(predecessor)
  propagating_list = annotation_list.map {|annotation|
    contribution_matrix = annotation.contribution_matrix.map {|action, contributions|
      if contributions.nil?
        [action, nil]
      elsif first_kernels.any? {|kernel| contributions[kernel] && predecessor.lhs_contributions(kernel.lhs, annotation.token).empty? }
        [action, nil]
      else
        cs = predecessor.lane_items[self].map {|pred_kernel, kernel|
          c = contributions[kernel] && (
            (kernel.position > 1 && predecessor.item_lookahead_set[pred_kernel].include?(annotation.token)) ||
            (kernel.position == 1 && predecessor.lhs_contributions(kernel.lhs, annotation.token)[pred_kernel])
          )
          [pred_kernel, c]
        }.to_h
        [action, cs]
      end
    }.to_h

    # Observation 3.33 (Simple Split-Stable Dominance)
    #
    # If all of contributions in the contribution_matrix are
    # always contribution or never contribution, we can stop annotate propagations
    # to the predecessor state.
    next nil if contribution_matrix.all? {|_, contributions| contributions.nil? || contributions.all? {|_, contributed| !contributed } }

    InadequacyAnnotation.new(annotation.state, annotation.token, annotation.actions, contribution_matrix)
  }.compact
  predecessor.append_annotation_list(propagating_list)
end

#append_annotation_list(propagating_list) ⇒ Object 



405
406
407
408
409
410
411
412
413
 
# File 'lib/lrama/state.rb', line 405

def append_annotation_list(propagating_list)
  annotation_list.each do |annotation|
    merging_list = propagating_list.select {|a| a.state == annotation.state && a.token == annotation.token && a.actions == annotation.actions }
    annotation.merge_matrix(merging_list.map(&:contribution_matrix))
    propagating_list -= merging_list
  end

  @annotation_list += propagating_list
end

#append_predecessor(prev_state) ⇒ Object 



471
472
473
474
 
# File 'lib/lrama/state.rb', line 471

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

#clear_conflicts ⇒ Object

Clear information related to conflicts. IELR computation re-calculates conflicts and default reduction of states after LALR computation. Call this method before IELR computation to avoid duplicated conflicts information is stored.



273
274
275
276
277
278
279
280
 
# File 'lib/lrama/state.rb', line 273

def clear_conflicts
  @conflicts = []
  @resolved_conflicts = []
  @default_reduction_rule = nil

  term_transitions.each(&:clear_conflicts)
  reduces.each(&:clear_conflicts)
end

#compute_transitions_and_reduces ⇒ Object 



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/lrama/state.rb', line 104

def compute_transitions_and_reduces
  _transitions = {}
  @_lane_items ||= {}
  reduces = []
  items.each do |item|
    # TODO: Consider what should be pushed
    if item.end_of_rule?
      reduces << Action::Reduce.new(item)
    else
      key = item.next_sym
      _transitions[key] ||= []
      @_lane_items[key] ||= []
      next_item = item.new_by_next_position
      _transitions[key] << next_item
      @_lane_items[key] << [item, next_item]
    end
  end

  # It seems Bison 3.8.2 iterates transitions order by symbol number
  transitions = _transitions.sort_by do |next_sym, to_items|
    next_sym.number
  end

  self._transitions = transitions.freeze
  self.reduces = reduces.freeze
end

#find_reduce_by_item!(item) ⇒ Object 



230
231
232
233
234
 
# File 'lib/lrama/state.rb', line 230

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

#first_kernels ⇒ Object 



400
401
402
 
# File 'lib/lrama/state.rb', line 400

def first_kernels
  @first_kernels ||= kernels.select {|kernel| kernel.position == 1 }
end

#goto_follow_set(nterm_token) ⇒ Object

Definition 3.39 (compute_goto_follow_set)



479
480
481
482
483
484
485
486
487
 
# File 'lib/lrama/state.rb', line 479

def goto_follow_set(nterm_token)
  return [] if nterm_token.accept_symbol?
  goto = @lalr_isocore.nterm_transitions.find {|g| g.next_sym == nterm_token }

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

#has_conflicts? ⇒ Boolean

Returns:

  • (Boolean) 


248
249
250
 
# File 'lib/lrama/state.rb', line 248

def has_conflicts?
  !@conflicts.empty?
end

#inadequacy_list ⇒ Object

Definition 3.27 (inadequacy_lists)



328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
 
# File 'lib/lrama/state.rb', line 328

def inadequacy_list
  return @inadequacy_list if @inadequacy_list

  inadequacy_list = {}

  term_transitions.each do |shift|
    inadequacy_list[shift.next_sym] ||= []
    inadequacy_list[shift.next_sym] << shift.dup
  end
  reduces.each do |reduce|
    next if reduce.look_ahead.nil?

    reduce.look_ahead.each do |token|
      inadequacy_list[token] ||= []
      inadequacy_list[token] << reduce.dup
    end
  end

  @inadequacy_list = inadequacy_list.select {|token, actions| actions.size > 1 }
end

#internal_dependencies(goto) ⇒ Object

Definition 3.8 (Goto Follows Internal Relation)



492
493
494
495
496
497
498
499
 
# File 'lib/lrama/state.rb', line 492

def internal_dependencies(goto)
  return @internal_dependencies[goto] if @internal_dependencies[goto]

  syms = @items.select {|i|
    i.next_sym == goto.next_sym && i.symbols_after_transition.all?(&:nullable) && i.position == 0
  }.map(&:lhs).uniq
  @internal_dependencies[goto] = nterm_transitions.select {|goto2| syms.include?(goto2.next_sym) }
end

#is_compatible?(filtered_lookahead) ⇒ Boolean

Definition 3.43 (is_compatible)

Returns:

  • (Boolean) 


307
308
309
310
311
312
313
314
 
# File 'lib/lrama/state.rb', line 307

def is_compatible?(filtered_lookahead)
  !lookaheads_recomputed ||
    @lalr_isocore.annotation_list.all? {|annotation|
      a = annotation.dominant_contribution(item_lookahead_set)
      b = annotation.dominant_contribution(filtered_lookahead)
      a.nil? || b.nil? || a == b
    }
end

#item_lookahead_set ⇒ Object

Definition 3.26 (item_lookahead_sets)



434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
 
# File 'lib/lrama/state.rb', line 434

def item_lookahead_set
  return @item_lookahead_set if @item_lookahead_set

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

#item_lookahead_set=(k) ⇒ Object 



455
456
457
 
# File 'lib/lrama/state.rb', line 455

def item_lookahead_set=(k)
  @item_lookahead_set = k
end

#lhs_contributions(sym, token) ⇒ Object

Definition 3.31 (compute_lhs_contributions)



418
419
420
421
422
423
424
425
426
427
428
429
 
# File 'lib/lrama/state.rb', line 418

def lhs_contributions(sym, token)
  return @lhs_contributions[sym][token] unless @lhs_contributions.dig(sym, token).nil?

  transition = nterm_transitions.find {|goto| goto.next_sym == sym }
  @lhs_contributions[sym] ||= {}
  @lhs_contributions[sym][token] =
    if always_follows[transition].include?(token)
      {}
    else
      kernels.map {|kernel| [kernel, follow_kernel_items[transition][kernel] && item_lookahead_set[kernel].include?(token)] }.to_h
    end
end

#lookahead_set_filters ⇒ Object

Definition 3.38 (lookahead_set_filters)



319
320
321
322
323
 
# File 'lib/lrama/state.rb', line 319

def lookahead_set_filters
  @lookahead_set_filters ||= kernels.map {|kernel|
    [kernel, @lalr_isocore.annotation_list.select {|annotation| annotation.contributed?(kernel) }.map(&:token)]
  }.to_h
end

#non_default_reduces ⇒ Object 



97
98
99
100
101
 
# File 'lib/lrama/state.rb', line 97

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

#nterm_transitions ⇒ Object 



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

def nterm_transitions # steep:ignore
  @nterm_transitions ||= transitions.select {|transition| transition.is_a?(Action::Goto) }
end

#predecessor_dependencies(goto) ⇒ Object

Definition 3.9 (Goto Follows Predecessor Relation)



513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
 
# File 'lib/lrama/state.rb', line 513

def predecessor_dependencies(goto)
  state_items = []
  @kernels.select {|kernel|
    kernel.next_sym == goto.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|
    state.nterm_transitions.find {|goto2| goto2.next_sym == item.lhs }
  }
end

#predecessors_with_item(item) ⇒ Object 



460
461
462
463
464
465
466
467
468
 
# File 'lib/lrama/state.rb', line 460

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

Definition 3.40 (propagate_lookaheads)



290
291
292
293
294
295
296
297
298
299
300
301
302
 
# File 'lib/lrama/state.rb', line 290

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

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

#rr_conflicts ⇒ Object 



260
261
262
263
264
 
# File 'lib/lrama/state.rb', line 260

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

#selected_term_transitions ⇒ Object 



206
207
208
209
210
 
# File 'lib/lrama/state.rb', line 206

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

#set_items_to_state(items, next_state) ⇒ Object 



137
138
139
 
# File 'lib/lrama/state.rb', line 137

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

#set_lane_items(next_sym, next_state) ⇒ Object 



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

def set_lane_items(next_sym, next_state)
  @lane_items[next_state] = @_lane_items[next_sym]
end

#set_look_ahead(rule, look_ahead) ⇒ Object 



142
143
144
145
146
147
148
 
# File 'lib/lrama/state.rb', line 142

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

  reduce.look_ahead = look_ahead
end

#set_look_ahead_sources(rule, sources) ⇒ Object 



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

def set_look_ahead_sources(rule, sources)
  reduce = reduces.find do |r|
    r.rule == rule
  end

  reduce.look_ahead_sources = sources
end

#split_state? ⇒ Boolean

Returns:

  • (Boolean) 


283
284
285
 
# File 'lib/lrama/state.rb', line 283

def split_state?
  @lalr_isocore != self
end

#sr_conflicts ⇒ Object 



253
254
255
256
257
 
# File 'lib/lrama/state.rb', line 253

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

#successor_dependencies(goto) ⇒ Object

Definition 3.5 (Goto Follows Successor Relation)



504
505
506
507
508
 
# File 'lib/lrama/state.rb', line 504

def successor_dependencies(goto)
  return @successor_dependencies[goto] if @successor_dependencies[goto]

  @successor_dependencies[goto] = goto.to_state.nterm_transitions.select {|next_goto| next_goto.next_sym.nullable }
end

#term_transitions ⇒ Object 



165
166
167
 
# File 'lib/lrama/state.rb', line 165

def term_transitions # steep:ignore
  @term_transitions ||= transitions.select {|transition| transition.is_a?(Action::Shift) }
end

#transition(sym) ⇒ Object

Move to next state by sym



215
216
217
218
219
220
221
222
223
224
225
226
227
 
# File 'lib/lrama/state.rb', line 215

def transition(sym)
  result = nil

  if sym.term?
    result = term_transitions.find {|shift| shift.next_sym == sym }.to_state
  else
    result = nterm_transitions.find {|goto| goto.next_sym == sym }.to_state
  end

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

  result
end

#transitions ⇒ Object 



170
171
172
173
174
175
176
177
178
 
# File 'lib/lrama/state.rb', line 170

def transitions
  @transitions ||= _transitions.map do |next_sym, to_items|
    if next_sym.term?
      Action::Shift.new(self, next_sym, to_items.flatten, @items_to_state[to_items])
    else
      Action::Goto.new(self, next_sym, to_items.flatten, @items_to_state[to_items])
    end
  end
end

#update_transition(transition, next_state) ⇒ Object 



181
182
183
184
185
 
# File 'lib/lrama/state.rb', line 181

def update_transition(transition, next_state)
  set_items_to_state(transition.to_items, next_state)
  next_state.append_predecessor(self)
  update_transitions_caches(transition)
end

#update_transitions_caches(transition) ⇒ Object 



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

def update_transitions_caches(transition)
  new_transition =
    if transition.next_sym.term?
      Action::Shift.new(self, transition.next_sym, transition.to_items, @items_to_state[transition.to_items])
    else
      Action::Goto.new(self, transition.next_sym, transition.to_items, @items_to_state[transition.to_items])
    end

  @transitions.delete(transition)
  @transitions << new_transition
  @nterm_transitions = nil
  @term_transitions = nil

  @follow_kernel_items[new_transition] = @follow_kernel_items.delete(transition)
  @always_follows[new_transition] = @always_follows.delete(transition)
end