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[Integer]

Returns:

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets, starts: nil, profile: false) ⇒ DirectLookaheads

Returns a new instance of DirectLookaheads.

RBS:

  • (IR::Grammar grammar, Analysis::Sets sets, ?starts: Array[String]?, ?profile: bool) -> void

Parameters:

  • grammar (IR::Grammar)
  • sets (Analysis::Sets)
  • starts: (Array[String], nil) (defaults to: nil)
  • profile: (Boolean) (defaults to: false) 


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 27

def initialize(grammar, sets, starts: nil, profile: false)
  @grammar = grammar
  @sets = sets
  @grammar_starts = grammar_starts.freeze
  @starts = (starts || @grammar_starts).dup
  raise ArgumentError, "starts must be a nonempty subset of grammar starts" if
    @starts.empty? || (@starts - @grammar_starts).any?

  @productions_by_lhs = grammar.productions.group_by(&:lhs)
  @augmented_production_ids = @starts.map { |name| AUGMENTED_PRODUCTION - start_index(name) }
  @augmented_rhs = @starts.each_with_index.to_h do |name, index|
    symbol = grammar.symbol(name) || raise(Ibex::Error, "missing start symbol #{name}")
    [@augmented_production_ids.fetch(index), [symbol.id].freeze]
  end.freeze
  @production_rhs = grammar.productions.map(&:rhs).freeze
  @augmented_item_cores = @augmented_rhs.to_h do |production_id, rhs|
    [production_id, item_cores_for(production_id, rhs.length)]
  end.freeze
  @production_item_cores = grammar.productions.map do |production|
    item_cores_for(production.id, production.rhs.length)
  end.freeze
  initialize_item_encoding
  @terminal_ids = grammar.terminals.map(&:id).freeze
  @terminal_masks = @terminal_ids.map { |id| 1 << id }.freeze
  @terminal_ids_by_bits = {} #: Hash[Integer, Array[Integer]]
  @lr0_state_count = nil
  @lr0_item_count = nil
  @propagation_edge_count = nil
  @profile = profile
end

Instance Attribute Details

#lr0_item_count ⇒ Integer? (readonly)

Signature:

  • Integer?

Returns:

  • (Integer, nil) 


21
22
23
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 21

def lr0_item_count
  @lr0_item_count
end

#lr0_state_count ⇒ Integer? (readonly)

Signature:

  • Integer?

Returns:

  • (Integer, nil) 


20
21
22
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 20

def lr0_state_count
  @lr0_state_count
end

#propagation_edge_count ⇒ Integer? (readonly)

Signature:

  • Integer?

Returns:

  • (Integer, nil) 


22
23
24
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 22

def propagation_edge_count
  @propagation_edge_count
end

#states ⇒ Array[core_set] (readonly)

Signature:

  • Array[core_set]

Returns:

  • (Array[core_set]) 


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

def states
  @states
end

#transitions ⇒ transitions (readonly)

Signature:

  • transitions

Returns:



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

def transitions
  @transitions
end

Instance Method Details

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

This method returns an undefined value.

RBS:

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

Parameters:

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


179
180
181
182
183
184
185
186
187
188
189
190
191
192
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 179

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 = node_id(state_id, production_id, dot)
  @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)
    edges[source] << node_id(state_id, production.id, 0) if @sets.sequence_nullable?(suffix)
  end
end

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

This method returns an undefined value.

RBS:

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

Parameters:

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


169
170
171
172
173
174
175
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 169

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)
  edges[node_id(state_id, production_id, dot)] << node_id(target_state, production_id, dot + 1)
end

#augmented_production(index) ⇒ Integer

RBS:

  • (Integer index) -> Integer

Parameters:

  • index (Integer)

Returns:

  • (Integer) 


78
79
80
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 78

def augmented_production(index)
  @augmented_production_ids.fetch(index)
end

#build ⇒ [ Array[packed_items], transitions ]

RBS:

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

Returns:



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

def build
  states, transitions = lr0_collection
  @states = states
  @transitions = transitions
  lookaheads = empty_lookaheads(states)
  propagation = propagation_graph(states, transitions, lookaheads)
  if @profile
    @lr0_state_count = states.length
    @lr0_item_count = states.sum(&:length)
    @propagation_edge_count = propagation.values.sum(&:length)
  end
  @starts.each_with_index do |_name, index|
    lookaheads.fetch(index).fetch(item_core(augmented_production(index), 0)) << 0
  end
  propagate(lookaheads, propagation)
  [lookaheads, transitions]
end

#closure(seed) ⇒ core_set

RBS:

  • (core_set seed) -> core_set

Parameters:

  • seed (core_set)

Returns:

  • (core_set) 


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

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


149
150
151
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 149

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

#grammar_starts ⇒ Array[String]

RBS:

  • () -> Array[String]

Returns:

  • (Array[String]) 


280
281
282
283
284
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 280

def grammar_starts
  return @grammar.starts if @grammar.respond_to?(:starts)

  [@grammar.start]
end

#initialize_item_encoding ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



85
86
87
88
89
90
91
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 85

def initialize_item_encoding
  @item_key_stride = [*@augmented_rhs.values, *@production_rhs].map(&:length).max.to_i + 1
  # Negative augmented ids are global to Grammar#starts.  A builder
  # may isolate a non-first entry, so reserve the full global range.
  @production_offset = @grammar_starts.length
  @node_stride = (@production_offset + @production_rhs.length) * @item_key_stride
end

#item_core(production_id, dot) ⇒ item_core

RBS:

  • (Integer production_id, Integer dot) -> item_core

Parameters:

  • production_id (Integer)
  • dot (Integer)

Returns:



260
261
262
263
264
265
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 260

def item_core(production_id, dot)
  raise IndexError, "invalid item dot: #{dot}" if dot.negative?
  return @augmented_item_cores.fetch(production_id).fetch(dot) 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:



250
251
252
253
254
255
256
257
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 250

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

#item_key(items) ⇒ Array[Integer]

RBS:

  • (core_set items) -> Array[Integer]

Parameters:

  • items (core_set)

Returns:

  • (Array[Integer]) 


268
269
270
271
272
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 268

def item_key(items)
  items.map do |production_id, dot|
    (((production_id + @production_offset) * @item_key_stride) + dot).to_i
  end.sort!
end

#lr0_collection ⇒ [ Array[core_set], transitions ]

RBS:

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

Returns:



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 94

def lr0_collection
  states = @starts.each_index.map { |index| closure(Set[item_core(augmented_production(index), 0)]) }
  transitions = [] #: transitions
  indexes = {} #: Hash[Array[Integer], Integer]
  states.each_with_index { |items, index| indexes[item_key(items)] = index }
  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_id(state_id, production_id, dot) ⇒ Integer

RBS:

  • (Integer state_id, Integer production_id, Integer dot) -> Integer

Parameters:

  • state_id (Integer)
  • production_id (Integer)
  • dot (Integer)

Returns:

  • (Integer) 


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

def node_id(state_id, production_id, dot)
  ((state_id * @node_stride) + ((production_id + @production_offset) * @item_key_stride) + dot).to_i
end

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

RBS:

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

Parameters:

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

Returns:

  • (Set[Integer]) 


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

def node_set(lookaheads, node)
  state_id = node / @node_stride
  item = node % @node_stride
  production_id = ((item / @item_key_stride) - @production_offset).to_i
  dot = (item % @item_key_stride).to_i
  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[Integer, Array[Integer]] edges) -> void

Parameters:

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


195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 195

def propagate(lookaheads, edges)
  queue = lookaheads.each_with_index.flat_map do |items, state_id|
    items.filter_map do |(production_id, dot), tokens|
      node_id(state_id, production_id, dot) unless tokens.empty?
    end
  end
  queued = queue.to_h { |node| [node, true] }
  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[Integer, Array[Integer]]

RBS:

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

Parameters:

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

Returns:

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


155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 155

def propagation_graph(states, transitions, lookaheads)
  edges = Hash.new { |hash, key| hash[key] = [] } #: Hash[Integer, Array[Integer]]
  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]) 


243
244
245
246
247
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 243

def rhs_for(production_id)
  return @augmented_rhs.fetch(production_id) if production_id.negative?

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


137
138
139
140
141
142
143
144
145
146
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 137

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

#start_index(name) ⇒ Integer

RBS:

  • (String name) -> Integer

Parameters:

  • name (String)

Returns:

  • (Integer) 


275
276
277
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 275

def start_index(name)
  @grammar_starts.index(name) || raise(Ibex::Error, "missing start symbol #{name}")
end

#terminal_ids(bits) ⇒ Array[Integer]

RBS:

  • (Integer bits) -> Array[Integer]

Parameters:

  • bits (Integer)

Returns:

  • (Array[Integer]) 


235
236
237
238
239
240
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 235

def terminal_ids(bits)
  @terminal_ids_by_bits.fetch(bits) do
    selected = @terminal_ids.select { |id| bits.anybits?(@terminal_masks[@terminal_ids.index(id)]) }
    @terminal_ids_by_bits[bits] = selected.freeze
  end
end