Module: Ibex::LALR::UnreachableStates

Defined in:
lib/ibex/lalr/unreachable_states.rb,
sig/ibex/lalr/unreachable_states.rbs

Overview

Optional post-resolution compaction. It is intentionally off by default because state numbers are part of diagnostics and golden output.

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.reachable_states(states, start_states) ⇒ Object

RBS:

  • (Array[IR::AutomatonState], Array[Integer]) -> Array[Integer]



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/ibex/lalr/unreachable_states.rb', line 36

def reachable_states(states, start_states)
  visited = {}
  queue = start_states.dup
  until queue.empty?
    state_id = queue.shift
    next if visited[state_id]

    visited[state_id] = true
    state = states.fetch(state_id)
    state.gotos.each_value { |target| queue << target }
    state.actions.each_value do |action|
      queue << action[:state] if action[:type] == :shift
    end
  end
  visited.keys.sort
end

.remap_action(action, mapping) ⇒ Object

RBS:

  • (IR::parser_action?, Hash[Integer, Integer]) -> IR::parser_action?



61
62
63
64
65
66
67
 
# File 'lib/ibex/lalr/unreachable_states.rb', line 61

def remap_action(action, mapping)
  return nil unless action
  return action unless action[:type] == :shift
  return { type: :shift, state: mapping.fetch(action[:state]) } if mapping.key?(action[:state])

  { type: :error }
end

.remap_conflict(conflict, mapping) ⇒ Object

RBS:

  • (IR::conflict, Hash[Integer, Integer]) -> IR::conflict



70
71
72
73
74
75
76
 
# File 'lib/ibex/lalr/unreachable_states.rb', line 70

def remap_conflict(conflict, mapping)
  result = conflict.dup
  if result[:type] == :shift_reduce && mapping.key?(result[:shift_to])
    result[:shift_to] = mapping.fetch(result[:shift_to])
  end
  result
end

.remap_edges(edges, mapping) ⇒ Object

RBS:

  • (Hash[Integer, Integer], Hash[Integer, Integer]) -> Hash[Integer, Integer]



54
55
56
57
58
 
# File 'lib/ibex/lalr/unreachable_states.rb', line 54

def remap_edges(edges, mapping)
  edges.each_with_object({}) do |(symbol_id, target), result|
    result[symbol_id] = mapping[target] if mapping.key?(target)
  end
end

.remove(states, start_states) ⇒ Object

RBS:

  • (Array[IR::AutomatonState] states, Array[Integer] start_states) -> [Array[IR::AutomatonState], Hash[Integer, Integer]]



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

def remove(states, start_states)
  reachable = reachable_states(states, start_states)
  mapping = reachable.each_with_index.to_h { |old_id, new_id| [old_id, new_id] }
  return [states, mapping] if reachable.length == states.length

  compacted = reachable.map do |old_id|
    state = states.fetch(old_id)
    transitions = remap_edges(state.transitions, mapping)
    gotos = remap_edges(state.gotos, mapping)
    actions = state.actions.transform_values { |action| remap_action(action, mapping) }
    default_action = remap_action(state.default_action, mapping)
    conflicts = state.conflicts.map { |conflict| remap_conflict(conflict, mapping) }
    IR::AutomatonState.new(
      id: mapping.fetch(old_id), items: state.items, transitions: transitions,
      actions: actions, gotos: gotos, default_action: default_action, conflicts: conflicts
    )
  end
  [compacted, mapping]
end

Instance Method Details

#self?.reachable_states ⇒ Array[Integer]

RBS:

  • (Array[IR::AutomatonState], Array[Integer]) -> Array[Integer]

Parameters:

Returns:

  • (Array[Integer]) 


13
 
# File 'sig/ibex/lalr/unreachable_states.rbs', line 13

def self?.reachable_states: (Array[IR::AutomatonState], Array[Integer]) -> Array[Integer]

#self?.remap_action ⇒ IR::parser_action?

RBS:

  • (IR::parser_action?, Hash[Integer, Integer]) -> IR::parser_action?

Parameters:

  • (IR::parser_action, nil)
  • (Hash[Integer, Integer])

Returns:

  • (IR::parser_action, nil) 


19
 
# File 'sig/ibex/lalr/unreachable_states.rbs', line 19

def self?.remap_action: (IR::parser_action?, Hash[Integer, Integer]) -> IR::parser_action?

#self?.remap_conflict ⇒ IR::conflict

RBS:

  • (IR::conflict, Hash[Integer, Integer]) -> IR::conflict

Parameters:

  • (IR::conflict)
  • (Hash[Integer, Integer])

Returns:

  • (IR::conflict) 


22
 
# File 'sig/ibex/lalr/unreachable_states.rbs', line 22

def self?.remap_conflict: (IR::conflict, Hash[Integer, Integer]) -> IR::conflict

#self?.remap_edges ⇒ Hash[Integer, Integer]

RBS:

  • (Hash[Integer, Integer], Hash[Integer, Integer]) -> Hash[Integer, Integer]

Parameters:

  • (Hash[Integer, Integer])
  • (Hash[Integer, Integer])

Returns:

  • (Hash[Integer, Integer]) 


16
 
# File 'sig/ibex/lalr/unreachable_states.rbs', line 16

def self?.remap_edges: (Hash[Integer, Integer], Hash[Integer, Integer]) -> Hash[Integer, Integer]

#self?.remove ⇒ [ Array[IR::AutomatonState], Hash[Integer, Integer] ]

RBS:

  • (Array[IR::AutomatonState] states, Array[Integer] start_states) -> [Array[IR::AutomatonState], Hash[Integer, Integer]]

Parameters:

Returns:



10
 
# File 'sig/ibex/lalr/unreachable_states.rbs', line 10

def self?.remove: (Array[IR::AutomatonState] states, Array[Integer] start_states) -> [ Array[IR::AutomatonState], Hash[Integer, Integer] ]