Class: Ibex::LALR::DirectLookaheads

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

Overview

Builds an LR(0) collection and propagates LALR(1) lookaheads directly over item occurrences. Canonical LR(1) states are never materialized.

Constant Summary collapse

AUGMENTED_PRODUCTION =

Signature:

  • Integer

Returns:

  • (Integer) 
-1 #: Integer
EMPTY_PRODUCTIONS =

Signature:

  • Array[IR::Production]

Returns:

Array.new(0).freeze
EMPTY_NODES =

Signature:

  • Array[lookahead_node]

Returns:

  • (Array[lookahead_node]) 
Array.new(0).freeze

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets) ⇒ DirectLookaheads

Returns a new instance of DirectLookaheads.

RBS:

  • (IR::Grammar grammar, Analysis::Sets sets) -> void

Parameters:



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

def initialize(grammar, sets)
  @grammar = grammar
  @sets = sets
  @productions_by_lhs = grammar.productions.group_by(&:lhs)
  start = grammar.symbol(grammar.start) || raise(Ibex::Error, "missing start symbol")
  @augmented_rhs = [start.id].freeze
  @production_rhs = grammar.productions.map(&:rhs).freeze
  @augmented_item_cores = item_cores_for(AUGMENTED_PRODUCTION, @augmented_rhs.length)
  @production_item_cores = grammar.productions.map do |production|
    item_cores_for(production.id, production.rhs.length)
  end.freeze
  @terminal_ids = grammar.terminals.map(&:id).freeze
  @terminal_masks = @terminal_ids.map { |id| 1 << id }.freeze
end

Instance Method Details

#add_closure_relations(edges, lookaheads, state_id, production_id, dot) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[lookahead_node, Array[lookahead_node]] edges, Array[packed_items] lookaheads, Integer state_id, Integer production_id, Integer dot) -> void

Parameters:

  • edges (Hash[lookahead_node, Array[lookahead_node]])
  • lookaheads (Array[packed_items])
  • state_id (Integer)
  • production_id (Integer)
  • dot (Integer) 


144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 144

def add_closure_relations(edges, lookaheads, state_id, production_id, dot)
  rhs = rhs_for(production_id)
  symbol = @grammar.symbol_by_id(rhs[dot])
  return unless symbol&.nonterminal?

  suffix = rhs.drop(dot + 1)
  spontaneous = terminal_ids(@sets.first_of_sequence(suffix))
  source = [state_id, production_id, dot] #: lookahead_node
  @productions_by_lhs.fetch(symbol.id, EMPTY_PRODUCTIONS).each do |production|
    target_item = item_core(production.id, 0)
    lookaheads.fetch(state_id).fetch(target_item).merge(spontaneous)
    if @sets.sequence_nullable?(suffix)
      target = [state_id, production.id, 0] #: lookahead_node
      edges[source] << target
    end
  end
end

#add_transition_edge(edges, transitions, state_id, production_id, dot) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[lookahead_node, Array[lookahead_node]] edges, transitions transitions, Integer state_id, Integer production_id, Integer dot) -> void

Parameters:

  • edges (Hash[lookahead_node, Array[lookahead_node]])
  • transitions (transitions)
  • state_id (Integer)
  • production_id (Integer)
  • dot (Integer) 


132
133
134
135
136
137
138
139
140
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 132

def add_transition_edge(edges, transitions, state_id, production_id, dot)
  symbol_id = rhs_for(production_id)[dot]
  return unless symbol_id

  target_state = transitions.fetch(state_id).fetch(symbol_id)
  source = [state_id, production_id, dot] #: lookahead_node
  target = [target_state, production_id, dot + 1] #: lookahead_node
  edges[source] << target
end

#build ⇒ [ Array[packed_items], transitions ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions ]) 


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

def build
  states, transitions = lr0_collection
  lookaheads = empty_lookaheads(states)
  propagation = propagation_graph(states, transitions, lookaheads)
  lookaheads.fetch(0).fetch(item_core(AUGMENTED_PRODUCTION, 0)) << 0
  propagate(lookaheads, propagation)
  [lookaheads, transitions]
end

#closure(seed) ⇒ core_set

RBS:

  • (core_set seed) -> core_set

Parameters:

  • seed (core_set)

Returns:

  • (core_set) 


79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 79

def closure(seed)
  items = seed.dup
  queue = seed.to_a
  cursor = 0
  while cursor < queue.length
    production_id, dot = queue.fetch(cursor)
    cursor += 1
    symbol = @grammar.symbol_by_id(rhs_for(production_id)[dot])
    next unless symbol&.nonterminal?

    @productions_by_lhs.fetch(symbol.id, EMPTY_PRODUCTIONS).each do |production|
      item = item_core(production.id, 0)
      queue << item if items.add?(item)
    end
  end
  items
end

#empty_lookaheads(states) ⇒ Array[packed_items]

RBS:

  • (Array[core_set] states) -> Array[packed_items]

Parameters:

  • states (Array[core_set])

Returns:

  • (Array[packed_items]) 


110
111
112
113
114
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 110

def empty_lookaheads(states)
  states.map do |items|
    items.to_h { |item| [item, Set.new] } #: packed_items
  end
end

#item_core(production_id, dot) ⇒ item_core

RBS:

  • (Integer production_id, Integer dot) -> item_core

Parameters:

  • production_id (Integer)
  • dot (Integer)

Returns:



222
223
224
225
226
227
228
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 222

def item_core(production_id, dot)
  raise IndexError, "invalid item dot: #{dot}" if dot.negative?
  return @augmented_item_cores.fetch(dot) if production_id == AUGMENTED_PRODUCTION
  raise IndexError, "invalid production id: #{production_id}" if production_id.negative?

  @production_item_cores.fetch(production_id).fetch(dot)
end

#item_cores_for(production_id, rhs_length) ⇒ Array[item_core]

RBS:

  • (Integer production_id, Integer rhs_length) -> Array[item_core]

Parameters:

  • production_id (Integer)
  • rhs_length (Integer)

Returns:



215
216
217
218
219
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 215

def item_cores_for(production_id, rhs_length)
  Array.new(rhs_length + 1) do |dot|
    [production_id, dot].freeze #: item_core
  end.freeze
end

#item_key(items) ⇒ Array[item_core]

RBS:

  • (core_set items) -> Array[item_core]

Parameters:

  • items (core_set)

Returns:



231
232
233
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 231

def item_key(items)
  items.to_a.sort
end

#lr0_collection ⇒ [ Array[core_set], transitions ]

RBS:

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

Returns:

  • ([ Array[core_set], transitions ]) 


55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 55

def lr0_collection
  seed = Set[item_core(AUGMENTED_PRODUCTION, 0)] #: core_set
  states = [closure(seed)]
  transitions = [] #: transitions
  indexes = { item_key(states.first) => 0 }
  cursor = 0
  while cursor < states.length
    transitions[cursor] = {}
    kernels = shifted_kernels(states.fetch(cursor))
    kernels.keys.sort.each do |symbol_id|
      target = closure(kernels.fetch(symbol_id))
      key = item_key(target)
      target_id = indexes[key] ||= begin
        states << target
        states.length - 1
      end
      transitions.fetch(cursor)[symbol_id] = target_id
    end
    cursor += 1
  end
  [states, transitions]
end

#node_set(lookaheads, node) ⇒ Set[Integer]

RBS:

  • (Array[packed_items] lookaheads, lookahead_node node) -> Set[Integer]

Parameters:

  • lookaheads (Array[packed_items])
  • node (lookahead_node)

Returns:

  • (Set[Integer]) 


191
192
193
194
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 191

def node_set(lookaheads, node)
  state_id, production_id, dot = node
  lookaheads.fetch(state_id).fetch(item_core(production_id, dot))
end

#propagate(lookaheads, edges) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[packed_items] lookaheads, Hash[lookahead_node, Array[lookahead_node]] edges) -> void

Parameters:

  • lookaheads (Array[packed_items])
  • edges (Hash[lookahead_node, Array[lookahead_node]]) 


163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 163

def propagate(lookaheads, edges)
  queue = lookaheads.each_with_index.flat_map do |items, state_id|
    items.filter_map do |(production_id, dot), tokens|
      next if tokens.empty?

      [state_id, production_id, dot] #: lookahead_node
    end
  end #: Array[lookahead_node]
  queued = queue.to_h { |node| [node, true] } #: Hash[lookahead_node, bool]
  cursor = 0
  while cursor < queue.length
    source = queue.fetch(cursor)
    cursor += 1
    queued.delete(source)
    source_set = node_set(lookaheads, source)
    edges.fetch(source, EMPTY_NODES).each do |target|
      target_set = node_set(lookaheads, target)
      previous_size = target_set.size
      target_set.merge(source_set)
      next if target_set.size == previous_size || queued[target]

      queue << target
      queued[target] = true
    end
  end
end

#propagation_graph(states, transitions, lookaheads) ⇒ Hash[lookahead_node, Array[lookahead_node]]

RBS:

  • (Array[core_set] states, transitions transitions, Array[packed_items] lookaheads) -> Hash[lookahead_node, Array[lookahead_node]]

Parameters:

  • states (Array[core_set])
  • transitions (transitions)
  • lookaheads (Array[packed_items])

Returns:

  • (Hash[lookahead_node, Array[lookahead_node]]) 


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

def propagation_graph(states, transitions, lookaheads)
  edges = Hash.new { |hash, key| hash[key] = [] } #: Hash[lookahead_node, Array[lookahead_node]]
  states.each_with_index do |items, state_id|
    items.each do |production_id, dot|
      add_transition_edge(edges, transitions, state_id, production_id, dot)
      add_closure_relations(edges, lookaheads, state_id, production_id, dot)
    end
  end
  edges.each_value(&:uniq!)
  edges
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


208
209
210
211
212
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 208

def rhs_for(production_id)
  return @augmented_rhs if production_id == AUGMENTED_PRODUCTION

  @production_rhs.fetch(production_id)
end

#shifted_kernels(items) ⇒ Hash[Integer, core_set]

RBS:

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

Parameters:

  • items (core_set)

Returns:

  • (Hash[Integer, core_set]) 


98
99
100
101
102
103
104
105
106
107
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 98

def shifted_kernels(items)
  kernels = {} #: Hash[Integer, core_set]
  items.each do |production_id, dot|
    symbol_id = rhs_for(production_id)[dot]
    next unless symbol_id

    (kernels[symbol_id] ||= Set.new) << item_core(production_id, dot + 1)
  end
  kernels
end

#terminal_ids(bits) ⇒ Array[Integer]

RBS:

  • (Integer bits) -> Array[Integer]

Parameters:

  • bits (Integer)

Returns:

  • (Array[Integer]) 


197
198
199
200
201
202
203
204
205
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 197

def terminal_ids(bits)
  selected = [] #: Array[Integer]
  index = 0
  while index < @terminal_ids.length
    selected << @terminal_ids[index] if bits.anybits?(@terminal_masks[index])
    index += 1
  end
  selected
end