Class: Ibex::LALR::Builder

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

Overview

Builds deterministic SLR, direct LALR(1), or canonical LR(1) automata. rubocop:disable Metrics/ClassLength -- collection strategies share one action/conflict construction path.

Constant Summary collapse

AUGMENTED_PRODUCTION =

Signature:

  • Integer

Returns:

  • (Integer) 
-1 #: Integer
ALGORITHMS =

Signature:

  • Array[Symbol]

Returns:

  • (Array[Symbol]) 
%i[slr lalr ielr lr1].freeze
LALR_STRATEGIES =

Signature:

  • Array[Symbol]

Returns:

  • (Array[Symbol]) 
%i[direct canonical_merge].freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, algorithm: :lalr, lalr_strategy: :direct, entry_isolation: false, starts: nil, attribute_entries: true) ⇒ Builder

Returns a new instance of Builder.

RBS:

  • (IR::Grammar grammar, ?algorithm: Symbol | String, ?lalr_strategy: Symbol | String, ?entry_isolation: bool, ?starts: Array[String]?, ?attribute_entries: bool) -> void

Parameters:

  • grammar (IR::Grammar)
  • algorithm: (Symbol, String) (defaults to: :lalr)
  • lalr_strategy: (Symbol, String) (defaults to: :direct)
  • entry_isolation: (Boolean) (defaults to: false)
  • starts: (Array[String], nil) (defaults to: nil)
  • attribute_entries: (Boolean) (defaults to: true) 


33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/ibex/lalr/builder.rb', line 33

def initialize(grammar, algorithm: :lalr, lalr_strategy: :direct, entry_isolation: false,
               starts: nil, attribute_entries: true)
  unless ALGORITHMS.include?(algorithm.to_sym)
    raise ArgumentError, "unknown parser algorithm #{algorithm.inspect}"
  end
  unless LALR_STRATEGIES.include?(lalr_strategy.to_sym)
    raise ArgumentError, "unknown LALR construction strategy #{lalr_strategy.inspect}"
  end

  @grammar = grammar
  @algorithm = algorithm.to_sym
  @lalr_strategy = lalr_strategy.to_sym
  @sets = Analysis::Sets.new(grammar)
  @productions_by_lhs = grammar.productions.group_by(&:lhs)
  @resolver = ConflictResolver.new(grammar)
  @metrics = nil
  @canonical_suffix_lookahead_cache = {}
  @canonical_item_cache = nil
  @canonical_key_radices = nil
  @start_names = starts || grammar.starts
  if @start_names.empty? || (@start_names - grammar.starts).any?
    raise ArgumentError, "starts must be a nonempty subset of grammar starts"
  end

  @entry_isolation = entry_isolation
  @attribute_entries = attribute_entries
end

Instance Attribute Details

#metrics ⇒ BuildMetrics? (readonly)

RBS:

  • @grammar: IR::Grammar

  • @algorithm: Symbol

  • @lalr_strategy: Symbol

  • @sets: Analysis::Sets

  • @productions_by_lhs: Hash[Integer, Array[IR::Production]]

  • @resolver: ConflictResolver

  • @metrics: BuildMetrics?

  • @start_names: Array[String]

  • @entry_isolation: bool

  • @attribute_entries: bool

  • @canonical_suffix_lookahead_cache: Hash[Integer, Hash[Integer, Hash[Integer, Array[Integer]]]]

  • @canonical_item_cache: Hash[Integer, Array[Array[lr_item?]?]]?

  • @canonical_key_radices: [Integer, Integer, Integer]?

Returns:



29
30
31
 
# File 'lib/ibex/lalr/builder.rb', line 29

def metrics
  @metrics
end

Instance Method Details

#add_completed_actions(items, candidates) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[IR::AutomatonItem] items, Hash[Integer, Array[IR::parser_action]] candidates) -> void

Parameters:

  • items (Array[IR::AutomatonItem])
  • candidates (Hash[Integer, Array[IR::parser_action]]) 


356
357
358
359
360
361
362
363
364
365
366
367
368
369
 
# File 'lib/ibex/lalr/builder.rb', line 356

def add_completed_actions(items, candidates)
  items.each do |item|
    next unless item.dot == rhs_for(item.production).length

    item.lookaheads.each do |lookahead|
      action = if item.production.negative?
                 { type: :accept } #: IR::accept_action
               else
                 { type: :reduce, production: item.production } #: IR::reduce_action
               end
      candidates[lookahead] << action
    end
  end
end

#algorithm_name ⇒ String

RBS:

  • () -> String

Returns:

  • (String) 


138
139
140
 
# File 'lib/ibex/lalr/builder.rb', line 138

def algorithm_name
  { lalr: "lalr1", ielr: "ielr1" }.fetch(@algorithm, @algorithm.to_s)
end

#apply_slr_lookaheads(states) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[packed_items] states) -> void

Parameters:

  • states (Array[packed_items]) 


286
287
288
289
290
291
292
293
294
 
# File 'lib/ibex/lalr/builder.rb', line 286

def apply_slr_lookaheads(states)
  states.each do |items|
    items.each do |(production_id, dot), lookaheads|
      next unless dot == rhs_for(production_id).length

      lookaheads.replace(slr_lookaheads(production_id))
    end
  end
end

#attribute_entry_conflicts(states, entry_states) ⇒ Array[IR::AutomatonState]

RBS:

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

Parameters:

Returns:



536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
 
# File 'lib/ibex/lalr/builder.rb', line 536

def attribute_entry_conflicts(states, entry_states)
  reachability = entry_reachability(states, entry_states)
  isolated = isolated_conflict_fingerprints
  states.map do |state|
    conflicts = state.conflicts.map do |conflict| # @type var conflict: IR::conflict
      entries = @start_names.select { |name| reachability.fetch(state.id).include?(name) }
      attributed = conflict.dup #: IR::conflict
      attributed[:entries] = entries
      attributed[:composite] = true unless isolated.include?(conflict_fingerprint(conflict))
      attributed
    end #: Array[IR::conflict]
    IR::AutomatonState.new(
      id: state.id, items: state.items, transitions: state.transitions, actions: state.actions,
      gotos: state.gotos, default_action: state.default_action, conflicts: conflicts
    )
  end
end

#attribute_midrule_conflict(conflict) ⇒ IR::conflict

Conflict hashes are produced locally immediately before this boundary. Keeping the parameter untyped avoids duplicating both discriminated hash variants solely to add their common optional provenance field.

RBS:

  • (untyped conflict) -> IR::conflict

Parameters:

  • conflict (Object)

Returns:

  • (IR::conflict) 


341
342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/ibex/lalr/builder.rb', line 341

def attribute_midrule_conflict(conflict)
  production_ids = if conflict[:type] == :shift_reduce
                     [conflict[:reduce]]
                   else
                     conflict[:reductions]
                   end
  origins = production_ids.filter_map do |production_id|
    production = @grammar.productions.fetch(production_id)
    production.origin[:loc] if production.origin[:kind] == :inline_action
  end
  conflict[:midrule_origins] = origins.uniq unless origins.empty?
  conflict
end

#augmented_production(name) ⇒ Integer

RBS:

  • (String name) -> Integer

Parameters:

  • name (String)

Returns:

  • (Integer) 


430
431
432
433
434
435
 
# File 'lib/ibex/lalr/builder.rb', line 430

def augmented_production(name)
  index = @grammar.starts.index(name)
  raise Ibex::Error, "missing start symbol #{name}" unless index

  AUGMENTED_PRODUCTION - index
end

#automaton_collection ⇒ [ Array[packed_items], transitions, Integer, Integer?, Symbol ]

RBS:

  • () -> [Array[packed_items], transitions, Integer, Integer?, Symbol]

Returns:

  • ([ Array[packed_items], transitions, Integer, Integer?, Symbol ]) 


103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/ibex/lalr/builder.rb', line 103

def automaton_collection
  if @algorithm == :ielr
    states, transitions = canonical_collection
    items, merged_transitions = IELRPartition.new(@grammar, states, transitions).build
    return [items, merged_transitions, states.length, states.length, :ielr_partition]
  end

  if @algorithm == :lr1
    states, transitions = canonical_collection
    return [pack_canonical_items(states), transitions, states.length, states.length, :canonical_lr1]
  end

  if @lalr_strategy == :canonical_merge
    states, transitions = canonical_collection
    items, merged_transitions = merge_lalr(states, transitions)
    apply_slr_lookaheads(items) if @algorithm == :slr
    return [items, merged_transitions, states.length, states.length, :canonical_merge]
  end

  if @grammar.starts.length > 1
    states, transitions = canonical_collection
    items, merged_transitions = merge_lalr(states, transitions)
    apply_slr_lookaheads(items) if @algorithm == :slr
    return [items, merged_transitions, states.length, states.length, :canonical_merge_multi_entry]
  end

  items, transitions = DirectLookaheads.new(@grammar, @sets).build
  apply_slr_lookaheads(items) if @algorithm == :slr
  collection = [items, transitions, items.length, nil, :direct_lalr]
  collection #: [Array[packed_items], transitions, Integer, Integer?, Symbol]
ensure
  @canonical_item_cache = nil
end

#build ⇒ IR::Automaton

RBS:

  • () -> IR::Automaton

Returns:



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/ibex/lalr/builder.rb', line 62

def build
  return build_isolated_automaton if @entry_isolation && @start_names.length > 1

  merged_items, merged_transitions, construction_states, canonical_states, strategy = automaton_collection
  states = build_states(merged_items, merged_transitions)
  states = OnErrorReductions.apply(@grammar, states)
  states = DefaultReductions.apply(states, terminal_ids: @grammar.terminals.map(&:id))
  entry_states = entry_states_for(merged_items)
  states = attribute_entry_conflicts(states, entry_states) if @attribute_entries && @start_names.length > 1
  summary = conflict_summary(states)
  @metrics = BuildMetrics.new(
    construction_states: construction_states,
    canonical_states: canonical_states,
    final_states: states.length,
    strategy: strategy
  )
  IR::Automaton.new(grammar: @grammar, states: states, conflict_summary: summary,
                    algorithm: algorithm_name, entry_states: entry_states)
end

#build_isolated_automaton ⇒ IR::Automaton

RBS:

  • () -> IR::Automaton

Returns:



454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
 
# File 'lib/ibex/lalr/builder.rb', line 454

def build_isolated_automaton
  entries = @start_names.map { |name| isolated_entry(name) }
  states = [] #: Array[IR::AutomatonState]
  entry_states = {} #: Hash[String, Integer]
  construction_states = 0
  canonical_counts = [] #: Array[Integer?]
  entries.each do |name, automaton, metrics|
    offset = states.length
    entry_states[name] = offset + automaton.entry_states.fetch(name)
    states.concat(automaton.states.map { |state| offset_state(state, offset, name) })
    construction_states += metrics.construction_states
    canonical_counts << metrics.canonical_states
  end
  canonical_states = canonical_counts.compact.sum if canonical_counts.none?(&:nil?)
  @metrics = BuildMetrics.new(
    construction_states: construction_states,
    canonical_states: canonical_states,
    final_states: states.length,
    strategy: :entry_isolation
  )
  IR::Automaton.new(
    grammar: @grammar, states: states, conflict_summary: conflict_summary(states),
    algorithm: algorithm_name, entry_states: entry_states
  )
end

#build_state(state_id, items, transitions) ⇒ IR::AutomatonState

RBS:

  • (Integer state_id, Array[IR::AutomatonItem] items, Hash[Integer, Integer] transitions) -> IR::AutomatonState

Parameters:

  • state_id (Integer)
  • items (Array[IR::AutomatonItem])
  • transitions (Hash[Integer, Integer])

Returns:



317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
 
# File 'lib/ibex/lalr/builder.rb', line 317

def build_state(state_id, items, transitions)
  candidates = Hash.new { |hash, key| hash[key] = Array.new(0) } #: Hash[Integer, Array[IR::parser_action]]
  gotos = {} #: Hash[Integer, Integer]
  transitions.each do |symbol_id, target|
    grammar_symbol = @grammar.symbol_by_id(symbol_id)
    raise Ibex::Error, "missing grammar symbol id #{symbol_id}" unless grammar_symbol

    if grammar_symbol.terminal?
      candidates[symbol_id] << { type: :shift, state: target }
    else
      gotos[symbol_id] = target
    end
  end
  add_completed_actions(items, candidates)
  actions, conflicts = resolve_actions(candidates)
  conflicts = conflicts.map { |conflict| attribute_midrule_conflict(conflict) }
  IR::AutomatonState.new(id: state_id, items: items, transitions: transitions, actions: actions,
                         gotos: gotos, conflicts: conflicts)
end

#build_states(merged_items, transitions) ⇒ Array[IR::AutomatonState]

RBS:

  • (Array[packed_items] merged_items, transitions transitions) -> Array[IR::AutomatonState]

Parameters:

  • merged_items (Array[packed_items])
  • transitions (transitions)

Returns:



306
307
308
309
310
311
312
313
314
 
# File 'lib/ibex/lalr/builder.rb', line 306

def build_states(merged_items, transitions)
  merged_items.each_with_index.map do |item_map, state_id|
    items = item_map.sort.map do |(production, dot), lookaheads|
      visible_production = production.negative? ? AUGMENTED_PRODUCTION : production
      IR::AutomatonItem.new(production: visible_production, dot: dot, lookaheads: lookaheads.to_a)
    end
    build_state(state_id, items, transitions[state_id])
  end
end

#canonical_collection ⇒ [ Array[item_set], transitions ]

RBS:

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

Returns:

  • ([ Array[item_set], transitions ]) 


143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/ibex/lalr/builder.rb', line 143

def canonical_collection
  states = @start_names.map do |name|
    seed = Set[canonical_item(augmented_production(name), 0, 0)] #: item_set
    closure(seed)
  end
  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[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[cursor][symbol_id] = target_id
    end
    cursor += 1
  end
  [states, transitions]
end

#canonical_item(production_id, dot, lookahead) ⇒ lr_item

RBS:

  • (Integer production_id, Integer dot, Integer lookahead) -> lr_item

Parameters:

  • production_id (Integer)
  • dot (Integer)
  • lookahead (Integer)

Returns:

  • (lr_item) 


217
218
219
220
221
222
223
224
225
226
 
# File 'lib/ibex/lalr/builder.rb', line 217

def canonical_item(production_id, dot, lookahead)
  cache = (@canonical_item_cache ||= {}) #: Hash[Integer, Array[Array[lr_item?]?]]
  production_cache = (cache[production_id] ||= []) #: Array[Array[lr_item?]?]
  dot_cache = (production_cache[dot] ||= []) #: Array[lr_item?]
  cached = dot_cache[lookahead]
  return cached if cached

  item = [production_id, dot, lookahead].freeze #: lr_item
  dot_cache[lookahead] = item
end

#canonical_key_radices ⇒ [ Integer, Integer, Integer ]

RBS:

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

Returns:

  • ([ Integer, Integer, Integer ]) 


398
399
400
401
402
403
404
405
406
407
408
409
410
 
# File 'lib/ibex/lalr/builder.rb', line 398

def canonical_key_radices
  cached = @canonical_key_radices
  return cached if cached

  longest_rhs = @grammar.productions.map { |production| production.rhs.length }.max || 0
  highest_terminal_id = @grammar.terminals.map(&:id).max || 0
  radices = [
    @grammar.starts.length,
    [longest_rhs, 1].max + 1,
    highest_terminal_id + 1
  ] #: [Integer, Integer, Integer]
  @canonical_key_radices = radices.freeze
end

#canonical_suffix_lookaheads(production_id, dot, inherited) ⇒ Array[Integer]

RBS:

  • (Integer production_id, Integer dot, Integer inherited) -> Array[Integer]

Parameters:

  • production_id (Integer)
  • dot (Integer)
  • inherited (Integer)

Returns:

  • (Array[Integer]) 


207
208
209
210
211
212
213
214
 
# File 'lib/ibex/lalr/builder.rb', line 207

def canonical_suffix_lookaheads(production_id, dot, inherited)
  production_cache = (@canonical_suffix_lookahead_cache[production_id] ||= {})
  inherited_cache = (production_cache[dot] ||= {})
  return inherited_cache.fetch(inherited) if inherited_cache.key?(inherited)

  suffix = rhs_for(production_id).drop(dot + 1)
  inherited_cache[inherited] = suffix_lookaheads(suffix, inherited).freeze
end

#closure(seed) ⇒ item_set

RBS:

  • (item_set seed) -> item_set

Parameters:

  • seed (item_set)

Returns:

  • (item_set) 


170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
 
# File 'lib/ibex/lalr/builder.rb', line 170

def closure(seed)
  cache = (@canonical_item_cache ||= {}) #: Hash[Integer, Array[Array[lr_item?]?]]
  items = seed.dup
  queue = seed.to_a
  cursor = 0
  while cursor < queue.length
    production_id, dot, lookahead = queue.fetch(cursor)
    cursor += 1
    rhs = rhs_for(production_id)
    grammar_symbol = @grammar.symbol_by_id(rhs[dot])
    next unless grammar_symbol&.nonterminal?

    lookaheads = canonical_suffix_lookaheads(production_id, dot, lookahead)
    @productions_by_lhs.fetch(grammar_symbol.id, Array.new(0)).each do |production|
      production_cache = (cache[production.id] ||= []) #: Array[Array[lr_item?]?]
      item_cache = (production_cache[0] ||= []) #: Array[lr_item?]
      lookaheads.each do |token_id|
        item = item_cache[token_id]
        unless item
          item = [production.id, 0, token_id].freeze #: lr_item
          item_cache[token_id] = item
        end
        enqueue_item(items, queue, item)
      end
    end
  end
  items
end

#conflict_fingerprint(conflict) ⇒ Array[untyped]

RBS:

  • (IR::conflict conflict) -> Array[untyped]

Parameters:

  • conflict (IR::conflict)

Returns:

  • (Array[untyped]) 


586
587
588
589
590
591
592
593
 
# File 'lib/ibex/lalr/builder.rb', line 586

def conflict_fingerprint(conflict)
  reductions = if conflict[:type] == :shift_reduce
                 [conflict[:reduce]]
               else
                 conflict[:reductions]
               end
  [conflict[:type], conflict[:symbol], reductions]
end

#conflict_summary(states) ⇒ IR::conflict_summary

RBS:

  • (Array[IR::AutomatonState] states) -> IR::conflict_summary

Parameters:

Returns:

  • (IR::conflict_summary) 


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/ibex/lalr/builder.rb', line 85

def conflict_summary(states)
  conflicts = states.flat_map(&:conflicts)
  shift_reduce = conflicts.select { |item| item[:type] == :shift_reduce }
  counted_shift_reduce = shift_reduce.count { |item| item.dig(:resolution, :by) == :default_shift }
  summary = { sr: counted_shift_reduce,
              resolved_sr: shift_reduce.length - counted_shift_reduce,
              rr: conflicts.count { |item| item[:type] == :reduce_reduce },
              expected_sr: @grammar.expect,
              expectation_met: counted_shift_reduce == @grammar.expect } #: IR::conflict_summary
  expected_rr = @grammar.expect_rr
  if expected_rr
    summary[:expected_rr] = expected_rr
    summary[:rr_expectation_met] = summary[:rr] == expected_rr
  end
  summary
end

#core_key(items) ⇒ Array[Integer]

RBS:

  • (item_set items) -> Array[Integer]

Parameters:

  • items (item_set)

Returns:

  • (Array[Integer]) 


413
414
415
416
417
418
 
# File 'lib/ibex/lalr/builder.rb', line 413

def core_key(items)
  production_offset, dot_radix, = canonical_key_radices
  items.map do |production, dot, _lookahead|
    ((production + production_offset) * dot_radix) + dot
  end.uniq.sort
end

#enqueue_item(items, queue, item) ⇒ void

This method returns an undefined value.

RBS:

  • (item_set items, Array[lr_item] queue, lr_item item) -> void

Parameters:

  • items (item_set)
  • queue (Array[lr_item])
  • item (lr_item) 


229
230
231
 
# File 'lib/ibex/lalr/builder.rb', line 229

def enqueue_item(items, queue, item)
  queue << item if items.add?(item)
end

#entry_reachability(states, entry_states) ⇒ Array[Array[String]]

RBS:

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

Parameters:

Returns:

  • (Array[Array[String]]) 


555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
 
# File 'lib/ibex/lalr/builder.rb', line 555

def entry_reachability(states, entry_states)
  reachable = Array.new(states.length) { [] } #: Array[Array[String]]
  entry_states.each do |name, initial|
    queue = [initial]
    visited = {} #: Hash[Integer, bool]
    until queue.empty?
      state_id = queue.shift
      next if visited[state_id]

      visited[state_id] = true
      reachable.fetch(state_id) << name
      states.fetch(state_id).transitions.each_value { |target| queue << target }
    end
  end
  reachable
end

#entry_states_for(items) ⇒ Hash[String, Integer]

RBS:

  • (Array[packed_items] items) -> Hash[String, Integer]

Parameters:

  • items (Array[packed_items])

Returns:

  • (Hash[String, Integer]) 


443
444
445
446
447
448
449
450
451
 
# File 'lib/ibex/lalr/builder.rb', line 443

def entry_states_for(items)
  @start_names.to_h do |name|
    production = augmented_production(name)
    state = items.index { |item_map| item_map.key?([production, 0]) }
    raise Ibex::Error, "missing initial state for start symbol #{name}" unless state

    [name, state]
  end
end

#isolated_conflict_fingerprints ⇒ Set[Array[untyped]]

RBS:

  • () -> Set[Array[untyped]]

Returns:

  • (Set[Array[untyped]]) 


573
574
575
576
577
578
579
580
581
582
583
 
# File 'lib/ibex/lalr/builder.rb', line 573

def isolated_conflict_fingerprints
  @start_names.each_with_object(Set.new) do |name, fingerprints|
    isolated = self.class.new(
      @grammar, algorithm: @algorithm, lalr_strategy: @lalr_strategy,
                starts: [name], attribute_entries: false
    ).build
    isolated.states.each do |state|
      state.conflicts.each { |conflict| fingerprints << conflict_fingerprint(conflict) }
    end
  end
end

#isolated_entry(name) ⇒ [ String, IR::Automaton, BuildMetrics ]

RBS:

  • (String name) -> [String, IR::Automaton, BuildMetrics]

Parameters:

  • name (String)

Returns:



481
482
483
484
485
486
487
488
489
490
491
 
# File 'lib/ibex/lalr/builder.rb', line 481

def isolated_entry(name)
  builder = self.class.new(
    @grammar, algorithm: @algorithm, lalr_strategy: @lalr_strategy,
              starts: [name], attribute_entries: false
  )
  automaton = builder.build
  metrics = builder.metrics
  raise Ibex::Error, "missing build metrics for start symbol #{name}" unless metrics

  [name, automaton, metrics]
end

#item_key(items) ⇒ Array[Integer]

RBS:

  • (item_set items) -> Array[Integer]

Parameters:

  • items (item_set)

Returns:

  • (Array[Integer]) 


421
422
423
424
425
426
427
 
# File 'lib/ibex/lalr/builder.rb', line 421

def item_key(items)
  production_offset, dot_radix, lookahead_radix = canonical_key_radices
  items.map do |production, dot, lookahead|
    core = ((production + production_offset) * dot_radix) + dot
    (core * lookahead_radix) + lookahead
  end.sort
end

#merge_lalr(states, transitions) ⇒ [ Array[packed_items], transitions ]

RBS:

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

Parameters:

  • states (Array[item_set])
  • transitions (transitions)

Returns:

  • ([ Array[packed_items], transitions ]) 


255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
 
# File 'lib/ibex/lalr/builder.rb', line 255

def merge_lalr(states, transitions)
  groups = {} #: Hash[Array[Integer], Integer]
  state_groups = states.map do |items|
    core = core_key(items)
    groups[core] ||= groups.length
  end
  merged = Array.new(groups.length) do
    Hash.new { |hash, key| hash[key] = Set.new } #: packed_items
  end
  states.each_with_index do |items, state_id|
    items.each { |production, dot, lookahead| merged[state_groups[state_id]][[production, dot]] << lookahead }
  end
  merged_transitions = Array.new(groups.length) do
    {} #: Hash[Integer, Integer]
  end
  transitions.each_with_index do |edges, state_id|
    edges.each { |symbol, target| merged_transitions[state_groups[state_id]][symbol] = state_groups[target] }
  end
  [merged, merged_transitions]
end

#offset_action(action, offset) ⇒ IR::parser_action

RBS:

  • (IR::parser_action action, Integer offset) -> IR::parser_action

Parameters:

  • action (IR::parser_action)
  • offset (Integer)

Returns:

  • (IR::parser_action) 


506
507
508
509
510
511
 
# File 'lib/ibex/lalr/builder.rb', line 506

def offset_action(action, offset)
  return action unless action[:type] == :shift

  shift = action #: IR::shift_action
  { type: :shift, state: shift[:state] + offset }
end

#offset_conflict(conflict, offset, entry) ⇒ IR::conflict

RBS:

  • (IR::conflict conflict, Integer offset, String entry) -> IR::conflict

Parameters:

  • conflict (IR::conflict)
  • offset (Integer)
  • entry (String)

Returns:

  • (IR::conflict) 


519
520
521
522
523
524
525
526
527
528
529
530
531
532
 
# File 'lib/ibex/lalr/builder.rb', line 519

def offset_conflict(conflict, offset, entry)
  if conflict[:type] == :shift_reduce
    shift_reduce = conflict #: IR::shift_reduce_conflict
    shifted = shift_reduce.dup #: IR::shift_reduce_conflict
    shifted[:shift_to] = shift_reduce[:shift_to] + offset
    shifted[:entries] = [entry]
    return shifted
  end

  reduce_reduce = conflict #: IR::reduce_reduce_conflict
  shifted = reduce_reduce.dup #: IR::reduce_reduce_conflict
  shifted[:entries] = [entry]
  shifted
end

#offset_default_action(action, offset) ⇒ IR::parser_action?

RBS:

  • (IR::parser_action? action, Integer offset) -> IR::parser_action?

Parameters:

  • action (IR::parser_action, nil)
  • offset (Integer)

Returns:

  • (IR::parser_action, nil) 


514
515
516
 
# File 'lib/ibex/lalr/builder.rb', line 514

def offset_default_action(action, offset)
  action && offset_action(action, offset)
end

#offset_state(state, offset, entry) ⇒ IR::AutomatonState

RBS:

  • (IR::AutomatonState state, Integer offset, String entry) -> IR::AutomatonState

Parameters:

Returns:



494
495
496
497
498
499
500
501
502
503
 
# File 'lib/ibex/lalr/builder.rb', line 494

def offset_state(state, offset, entry)
  actions = state.actions.transform_values { |action| offset_action(action, offset) }
  conflicts = state.conflicts.map { |conflict| offset_conflict(conflict, offset, entry) }
  IR::AutomatonState.new(
    id: state.id + offset, items: state.items,
    transitions: state.transitions.transform_values { |target| target + offset },
    actions: actions, gotos: state.gotos.transform_values { |target| target + offset },
    default_action: offset_default_action(state.default_action, offset), conflicts: conflicts
  )
end

#pack_canonical_items(states) ⇒ Array[packed_items]

RBS:

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

Parameters:

  • states (Array[item_set])

Returns:

  • (Array[packed_items]) 


277
278
279
280
281
282
283
 
# File 'lib/ibex/lalr/builder.rb', line 277

def pack_canonical_items(states)
  states.map do |items|
    packed = Hash.new { |hash, key| hash[key] = Set.new } #: packed_items
    items.each { |production, dot, lookahead| packed[[production, dot]] << lookahead }
    packed
  end
end

#resolve_actions(candidates) ⇒ [ Hash[Integer, IR::parser_action], Array[IR::conflict] ]

RBS:

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

Parameters:

  • candidates (Hash[Integer, Array[IR::parser_action]])

Returns:

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


373
374
375
376
377
378
379
380
381
382
383
384
 
# File 'lib/ibex/lalr/builder.rb', line 373

def resolve_actions(candidates)
  actions = {} #: Hash[Integer, IR::parser_action]
  conflicts = [] #: Array[IR::conflict]
  candidates.keys.sort.each do |token_id|
    action, found = @resolver.resolve(token_id, candidates[token_id])
    raise Ibex::Error, "empty parser action candidates" unless action

    actions[token_id] = action
    conflicts.concat(found)
  end
  [actions, conflicts]
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


387
388
389
390
391
392
393
394
395
 
# File 'lib/ibex/lalr/builder.rb', line 387

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

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

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

RBS:

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

Parameters:

  • items (item_set)

Returns:

  • (Hash[Integer, item_set]) 


234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/ibex/lalr/builder.rb', line 234

def shifted_kernels(items)
  cache = (@canonical_item_cache ||= {}) #: Hash[Integer, Array[Array[lr_item?]?]]
  kernels = {} #: Hash[Integer, item_set]
  items.each do |production_id, dot, lookahead|
    symbol_id = rhs_for(production_id)[dot]
    next unless symbol_id

    production_cache = (cache[production_id] ||= []) #: Array[Array[lr_item?]?]
    shifted_dot = dot + 1
    item_cache = (production_cache[shifted_dot] ||= []) #: Array[lr_item?]
    item = item_cache[lookahead]
    unless item
      item = [production_id, shifted_dot, lookahead].freeze #: lr_item
      item_cache[lookahead] = item
    end
    (kernels[symbol_id] ||= Set.new) << item
  end
  kernels
end

#slr_lookaheads(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


297
298
299
300
301
302
303
 
# File 'lib/ibex/lalr/builder.rb', line 297

def slr_lookaheads(production_id)
  return [0] if production_id.negative?

  lhs = @grammar.productions.fetch(production_id).lhs
  bits = @sets.follow_bits.fetch(lhs)
  @grammar.terminals.filter_map { |terminal| terminal.id if bits.anybits?(1 << terminal.id) }
end

#start_name_for_augmented(production_id) ⇒ String

RBS:

  • (Integer production_id) -> String

Parameters:

  • production_id (Integer)

Returns:

  • (String) 


438
439
440
 
# File 'lib/ibex/lalr/builder.rb', line 438

def start_name_for_augmented(production_id)
  @grammar.starts.fetch(-production_id - 1)
end

#suffix_lookaheads(suffix, inherited) ⇒ Array[Integer]

RBS:

  • (Array[Integer] suffix, Integer inherited) -> Array[Integer]

Parameters:

  • suffix (Array[Integer])
  • inherited (Integer)

Returns:

  • (Array[Integer]) 


200
201
202
203
204
 
# File 'lib/ibex/lalr/builder.rb', line 200

def suffix_lookaheads(suffix, inherited)
  bits = @sets.first_of_sequence(suffix)
  bits |= (1 << inherited) if @sets.sequence_nullable?(suffix)
  @grammar.terminals.filter_map { |terminal| terminal.id if bits.anybits?(1 << terminal.id) }
end