Class: Ibex::LALR::IELRPartition

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

Overview

Deterministically merges compatible canonical LR(1) states and splits partitions until their outgoing transitions are congruent.

Constant Summary collapse

AUGMENTED_PRODUCTION =

RBS:

  • type contribution_action = [:shift] | [:reduce, Integer] | [:accept]

Returns:

  • (Integer) 
-1 #: Integer

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, states, transitions, profile: false) ⇒ IELRPartition

Returns a new instance of IELRPartition.

RBS:

  • (IR::Grammar grammar, Array[item_set] states, transitions transitions, ?profile: bool) -> void

Parameters:

  • grammar (IR::Grammar)
  • states (Array[item_set])
  • transitions (transitions)
  • profile: (Boolean) (defaults to: false) 


27
28
29
30
31
32
33
34
35
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 27

def initialize(grammar, states, transitions, profile: false)
  @grammar = grammar
  @states = states
  @transitions = transitions
  @contributions = Array.new(states.length) { |state_id| action_contributions(state_id) }
  @initial_partition_count = nil
  @final_partition_count = nil
  @profile = profile
end

Instance Attribute Details

#final_partition_count ⇒ Integer? (readonly)

Signature:

  • Integer?

Returns:

  • (Integer, nil) 


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

def final_partition_count
  @final_partition_count
end

#initial_partition_count ⇒ Integer? (readonly)

RBS:

  • @grammar: IR::Grammar

  • @states: Array[item_set]

  • @transitions: transitions

  • @contributions: Array[Hash[Integer, Set[contribution_action]]]

  • @initial_partition_count: Integer?

  • @final_partition_count: Integer?

  • @profile: bool

Returns:

  • (Integer, nil) 


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

def initial_partition_count
  @initial_partition_count
end

Instance Method Details

#action_contributions(state_id) ⇒ Hash[Integer, Set[contribution_action]]

RBS:

  • (Integer state_id) -> Hash[Integer, Set[contribution_action]]

Parameters:

  • state_id (Integer)

Returns:

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


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

def action_contributions(state_id)
  actions = Hash.new { |hash, key| hash[key] = Set.new } #: Hash[Integer, Set[contribution_action]]
  @transitions.fetch(state_id).each_key do |symbol_id|
    symbol = @grammar.symbol_by_id(symbol_id)
    actions[symbol_id] << [:shift] if symbol&.terminal?
  end
  @states.fetch(state_id).each do |production_id, dot, lookahead|
    next unless dot == rhs_for(production_id).length

    action = production_id.negative? ? [:accept] : [:reduce, production_id] #: contribution_action
    actions[lookahead] << action
  end
  actions
end

#build ⇒ [ Array[packed_items], transitions ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions ]) 


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

def build
  partitions = initial_partitions
  @initial_partition_count = partitions.length if @profile
  partitions = refine_transitions(partitions)
  @final_partition_count = partitions.length if @profile
  indexes = partition_indexes(partitions)
  items = partitions.map { |members| merge_items(members) }
  transitions = partitions.map do |members|
    @transitions.fetch(members.first).to_h do |symbol_id, target|
      [symbol_id, indexes.fetch(target)]
    end
  end
  [items, transitions]
end

#compatible?(members) ⇒ Boolean

A canonical member may gain an action only where it previously had no action. Every nonempty member cell must equal the merged cell.

RBS:

  • (state_partition members) -> bool

Parameters:

  • members (state_partition)

Returns:

  • (Boolean) 


78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 78

def compatible?(members)
  merged = Hash.new { |hash, key| hash[key] = Set.new } #: Hash[Integer, Set[contribution_action]]
  members.each do |state_id|
    @contributions.fetch(state_id).each { |token_id, actions| merged[token_id].merge(actions) }
  end
  merged.all? do |token_id, actions|
    members.all? do |state_id|
      member_actions = @contributions.fetch(state_id)[token_id]
      member_actions.nil? || member_actions.empty? || member_actions == actions
    end
  end
end

#compatible_partitions(members) ⇒ Array[state_partition]

RBS:

  • (Array[Integer] members) -> Array[state_partition]

Parameters:

  • members (Array[Integer])

Returns:

  • (Array[state_partition]) 


66
67
68
69
70
71
72
73
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 66

def compatible_partitions(members)
  partitions = [] #: Array[state_partition]
  members.each do |state_id|
    partition = partitions.find { |candidate| compatible?(candidate + [state_id]) }
    partition ? partition << state_id : partitions << [state_id]
  end
  partitions
end

#core_key(items) ⇒ Array[item_core]

RBS:

  • (item_set items) -> Array[item_core]

Parameters:

  • items (item_set)

Returns:

  • (Array[item_core]) 


159
160
161
162
163
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 159

def core_key(items)
  items.map do |production_id, dot, _lookahead|
    [production_id, dot] #: item_core
  end.uniq.sort
end

#initial_partitions ⇒ Array[state_partition]

RBS:

  • () -> Array[state_partition]

Returns:

  • (Array[state_partition]) 


56
57
58
59
60
61
62
63
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 56

def initial_partitions
  cores = {} #: Hash[Array[item_core], Array[Integer]]
  @states.each_with_index do |items, state_id|
    cores[core_key(items)] ||= []
    cores.fetch(core_key(items)) << state_id
  end
  cores.values.flat_map { |members| compatible_partitions(members) }
end

#merge_items(members) ⇒ packed_items

RBS:

  • (state_partition members) -> packed_items

Parameters:

  • members (state_partition)

Returns:

  • (packed_items) 


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

def merge_items(members)
  merged = Hash.new { |hash, key| hash[key] = Set.new } #: packed_items
  members.each do |state_id|
    @states.fetch(state_id).each do |production_id, dot, lookahead|
      merged[[production_id, dot]] << lookahead
    end
  end
  merged
end

#partition_indexes(partitions) ⇒ Hash[Integer, Integer]

RBS:

  • (Array[state_partition] partitions) -> Hash[Integer, Integer]

Parameters:

  • partitions (Array[state_partition])

Returns:

  • (Hash[Integer, Integer]) 


112
113
114
115
116
117
118
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 112

def partition_indexes(partitions)
  indexes = {} #: Hash[Integer, Integer]
  partitions.each_with_index do |members, partition_id|
    members.each { |state_id| indexes[state_id] = partition_id }
  end
  indexes
end

#refine_transitions(partitions) ⇒ Array[state_partition]

RBS:

  • (Array[state_partition] partitions) -> Array[state_partition]

Parameters:

  • partitions (Array[state_partition])

Returns:

  • (Array[state_partition]) 


92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 92

def refine_transitions(partitions)
  loop do
    indexes = partition_indexes(partitions)
    refined = partitions.flat_map do |members|
      members.group_by { |state_id| transition_signature(state_id, indexes) }.values
    end
    return partitions if refined == partitions

    partitions = refined
  end
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


148
149
150
151
152
153
154
155
156
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 148

def rhs_for(production_id)
  if production_id.negative?
    name = @grammar.starts.fetch(-production_id - 1)
    start = @grammar.symbol(name) || raise(Ibex::Error, "missing start symbol #{name}")
    return [start.id]
  end

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

#transition_signature(state_id, indexes) ⇒ Array[[ Integer, Integer ]]

RBS:

  • (Integer state_id, Hash[Integer, Integer] indexes) -> Array[[Integer, Integer]]

Parameters:

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

Returns:

  • (Array[[ Integer, Integer ]]) 


105
106
107
108
109
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 105

def transition_signature(state_id, indexes)
  @transitions.fetch(state_id).map do |symbol_id, target|
    [symbol_id, indexes.fetch(target)] #: [Integer, Integer]
  end.sort
end