Module: Ibex::LALR::DefaultReductions

Defined in:
lib/ibex/lalr/default_reductions.rb

Overview

Selects size-reducing default actions without changing any terminal cell.

Constant Summary collapse

ERROR_ACTION =

@rbs! private def select_default: (Hash[Integer, IR::parser_action] actions, Array terminal_ids) -> IR::parser_action? private def self.select_default: (Hash[Integer, IR::parser_action] actions, Array terminal_ids) -> IR::parser_action?

{ type: :error }.freeze

Class Method Summary collapse

Class Method Details

.apply(states, terminal_ids:) ⇒ Object 



14
15
16
 
# File 'lib/ibex/lalr/default_reductions.rb', line 14

def apply(states, terminal_ids:)
  states.map { |state| optimize(state, terminal_ids: terminal_ids) }
end

.optimize(state, terminal_ids:) ⇒ Object 



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/ibex/lalr/default_reductions.rb', line 20

def optimize(state, terminal_ids:)
  return state if state.default_action

  default_action = select_default(state.actions, terminal_ids)
  return state unless default_action

  actions = {} #: Hash[Integer, IR::parser_action]
  terminal_ids.each_with_object(actions) do |token_id, result|
    action = state.actions[token_id]
    result[token_id] = action || ERROR_ACTION unless action == default_action
  end
  IR::AutomatonState.new(id: state.id, items: state.items, transitions: state.transitions,
                         actions: actions, gotos: state.gotos, default_action: default_action,
                         conflicts: state.conflicts)
end

.select_default(actions, terminal_ids) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/ibex/lalr/default_reductions.rb', line 41

def select_default(actions, terminal_ids)
  candidates = [] #: Array[IR::reduce_action]
  actions.each_value do |action|
    next unless action[:type] == :reduce

    reduction = action #: IR::reduce_action
    candidates << reduction
  end
  candidates.uniq!
  candidates.sort_by! { |action| action.fetch(:production) }
  candidate = candidates.max_by do |action|
    saved_entries = actions.count { |_token_id, candidate| candidate == action }
    [saved_entries, -action.fetch(:production)]
  end
  return unless candidate

  optimized_size = terminal_ids.count { |token_id| actions[token_id] != candidate } + 1
  candidate if optimized_size < actions.length
end