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 =

Signature:

  • Integer

Returns:

  • (Integer) 
-1 #: Integer

Instance Method Summary collapse

Constructor Details

#initialize(grammar, states, transitions) ⇒ IELRPartition

Returns a new instance of IELRPartition.

RBS:

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

Parameters:

  • grammar (IR::Grammar)
  • states (Array[item_set])
  • transitions (transitions) 


19
20
21
22
23
24
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 19

def initialize(grammar, states, transitions)
  @grammar = grammar
  @states = states
  @transitions = transitions
  @contributions = Array.new(states.length) { |state_id| action_contributions(state_id) }
end

Instance Method Details

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

RBS:

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

Parameters:

  • state_id (Integer)

Returns:

  • (Hash[Integer, Set[Array[untyped]]]) 


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

def action_contributions(state_id)
  actions = Hash.new { |hash, key| hash[key] = Set.new } #: Hash[Integer, Set[Array[untyped]]]
  @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]
    actions[lookahead] << action
  end
  actions
end

#build ⇒ [ Array[packed_items], transitions ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions ]) 


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

def build
  partitions = refine_transitions(initial_partitions)
  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) 


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

def compatible?(members)
  merged = Hash.new { |hash, key| hash[key] = Set.new } #: Hash[Integer, Set[Array[untyped]]]
  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]) 


52
53
54
55
56
57
58
59
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 52

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]) 


145
146
147
148
149
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 145

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]) 


42
43
44
45
46
47
48
49
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 42

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) 


107
108
109
110
111
112
113
114
115
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 107

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]) 


98
99
100
101
102
103
104
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 98

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]) 


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

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]) 


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

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 ]]) 


91
92
93
94
95
 
# File 'lib/ibex/lalr/ielr_partition.rb', line 91

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