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
IELR_STRATEGIES =

Signature:

  • Array[Symbol]

Returns:

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of Builder.

RBS:

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

Parameters:

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


40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/ibex/lalr/builder.rb', line 40

def initialize(grammar, algorithm: :lalr, lalr_strategy: :direct, entry_isolation: false,
               ielr_strategy: :partition, starts: nil, attribute_entries: true, profile: false,
               remove_unreachable: false)
  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
  unless IELR_STRATEGIES.include?(ielr_strategy.to_sym)
    raise ArgumentError, "unknown IELR construction strategy #{ielr_strategy.inspect}"
  end

  @grammar = grammar
  @algorithm = algorithm.to_sym
  @lalr_strategy = lalr_strategy.to_sym
  @ielr_strategy = ielr_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
  @profile = profile
  @remove_unreachable = remove_unreachable
end

Instance Attribute Details

#metrics ⇒ BuildMetrics? (readonly)

RBS:

  • @grammar: IR::Grammar

  • @algorithm: Symbol

  • @lalr_strategy: Symbol

  • @ielr_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

  • @profile: bool

  • @remove_unreachable: 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:



34
35
36
 
# File 'lib/ibex/lalr/builder.rb', line 34

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


453
454
455
456
457
458
459
460
461
462
463
464
465
466
 
# File 'lib/ibex/lalr/builder.rb', line 453

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) 


235
236
237
 
# File 'lib/ibex/lalr/builder.rb', line 235

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


383
384
385
386
387
388
389
390
391
 
# File 'lib/ibex/lalr/builder.rb', line 383

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:



670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
 
# File 'lib/ibex/lalr/builder.rb', line 670

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. Both conflict variants carry the same optional midrule provenance field.

RBS:

  • (IR::conflict conflict) -> IR::conflict

Parameters:

  • conflict (IR::conflict)

Returns:

  • (IR::conflict) 


437
438
439
440
441
442
443
444
445
446
447
448
449
450
 
# File 'lib/ibex/lalr/builder.rb', line 437

def attribute_midrule_conflict(conflict)
  production_ids = if conflict[:type] == :shift_reduce
                     [conflict[:reduce]]
                   else
                     conflict[:reductions]
                   end #: Array[Integer]
  origins = production_ids.filter_map do |production_id|
    production = @grammar.productions.fetch(production_id)
    production.origin[:loc] if production.origin[:kind] == :inline_action
  end
  result = conflict.dup #: Hash[Symbol, untyped]
  result[:midrule_origins] = origins.uniq unless origins.empty?
  result #: IR::conflict
end

#augmented_production(name) ⇒ Integer

RBS:

  • (String name) -> Integer

Parameters:

  • name (String)

Returns:

  • (Integer) 


527
528
529
530
531
532
 
# File 'lib/ibex/lalr/builder.rb', line 527

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, build_collection ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions, build_collection ]) 


127
128
129
130
131
132
133
134
135
136
 
# File 'lib/ibex/lalr/builder.rb', line 127

def automaton_collection
  return ielr_collection if @algorithm == :ielr
  return canonical_lr1_collection if @algorithm == :lr1
  return merged_canonical_collection(:canonical_merge) if @lalr_strategy == :canonical_merge
  return merged_canonical_collection(:canonical_merge_multi_entry) if @grammar.starts.length > 1

  direct_collection
ensure
  @canonical_item_cache = nil
end

#build ⇒ IR::Automaton

RBS:

  • () -> IR::Automaton

Returns:



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

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

  merged_items, merged_transitions, collection = 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)
  if @remove_unreachable
    states, mapping = UnreachableStates.remove(states, entry_states.values.uniq)
    entry_states = entry_states.transform_values { |state_id| mapping.fetch(state_id) }
    collection[:ielr_unreachable_removed] = mapping.length - states.length if collection.respond_to?(:[]=)
  end
  states = attribute_entry_conflicts(states, entry_states) if @attribute_entries && @start_names.length > 1
  summary = conflict_summary(states)
  final_items, final_lookahead_items = profiled_final_item_counts(merged_items)
  @metrics = build_metrics(collection, states.length, final_items, final_lookahead_items)
  build_output_automaton(states: states, conflict_summary: summary, entry_states: entry_states)
end

#build_isolated_automaton ⇒ IR::Automaton

RBS:

  • () -> IR::Automaton

Returns:



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

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 = isolated_metrics(entries, construction_states, canonical_states, states.length)
  build_output_automaton(
    states: states, conflict_summary: conflict_summary(states), entry_states: entry_states
  )
end

#build_metrics(collection, final_states, final_items, final_lookahead_items) ⇒ BuildMetrics

RBS:

  • (build_collection collection, Integer final_states, Integer? final_items, Integer? final_lookahead_items) -> BuildMetrics

Parameters:

  • collection (build_collection)
  • final_states (Integer)
  • final_items (Integer, nil)
  • final_lookahead_items (Integer, nil)

Returns:



211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
# File 'lib/ibex/lalr/builder.rb', line 211

def build_metrics(collection, final_states, final_items, final_lookahead_items)
  BuildMetrics.new(
    construction_states: collection.fetch(:construction_states),
    canonical_states: collection.fetch(:canonical_states),
    strategy: collection.fetch(:strategy),
    lr0_states: collection.fetch(:lr0_states),
    lr0_items: collection.fetch(:lr0_items),
    canonical_items: collection.fetch(:canonical_items),
    propagation_edges: collection.fetch(:propagation_edges),
    ielr_initial_partitions: collection.fetch(:ielr_initial_partitions),
    ielr_final_partitions: collection.fetch(:ielr_final_partitions),
    ielr_annotations: collection.fetch(:ielr_annotations, nil),
    ielr_annotated_states: collection.fetch(:ielr_annotated_states, nil),
    ielr_inadequacies: collection.fetch(:ielr_inadequacies, nil),
    ielr_split_stable_discarded: collection.fetch(:ielr_split_stable_discarded, nil),
    ielr_lalr_states: collection.fetch(:ielr_lalr_states, nil),
    ielr_split_states: collection.fetch(:ielr_split_states, nil),
    ielr_unreachable_removed: collection.fetch(:ielr_unreachable_removed, nil),
    ielr_remergeable_candidates: collection.fetch(:ielr_remergeable_candidates, nil),
    final_states: final_states, final_items: final_items, final_lookahead_items: final_lookahead_items
  )
end

#build_output_automaton(states:, conflict_summary:, entry_states:) ⇒ IR::Automaton

RBS:

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

Parameters:

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

Returns:



100
101
102
103
104
105
106
 
# File 'lib/ibex/lalr/builder.rb', line 100

def build_output_automaton(states:, conflict_summary:, entry_states:)
  IR::Automaton.new(
    grammar: @grammar, states: states, conflict_summary: conflict_summary,
    algorithm: algorithm_name, entry_states: entry_states,
    entry_construction: output_entry_construction || raise(Ibex::Error, "missing entry construction")
  )
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:



414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
 
# File 'lib/ibex/lalr/builder.rb', line 414

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:



403
404
405
406
407
408
409
410
411
 
# File 'lib/ibex/lalr/builder.rb', line 403

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


240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/ibex/lalr/builder.rb', line 240

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) 


314
315
316
317
318
319
320
321
322
323
 
# File 'lib/ibex/lalr/builder.rb', line 314

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


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

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_lr1_collection ⇒ [ Array[packed_items], transitions, build_collection ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions, build_collection ]) 


158
159
160
161
 
# File 'lib/ibex/lalr/builder.rb', line 158

def canonical_lr1_collection
  states, transitions = canonical_collection
  [pack_canonical_items(states), transitions, canonical_profile(states, strategy: :canonical_lr1)]
end

#canonical_profile(states, strategy:) ⇒ build_collection

RBS:

  • (Array[item_set] states, strategy: Symbol) -> build_collection

Parameters:

  • states (Array[item_set])
  • strategy: (Symbol)

Returns:

  • (build_collection) 


189
190
191
192
193
194
195
196
197
198
199
200
 
# File 'lib/ibex/lalr/builder.rb', line 189

def canonical_profile(states, strategy:)
  cores = states.to_h { |items| [core_key(items), true] }.keys if @profile
  {
    construction_states: states.length, canonical_states: states.length, strategy: strategy,
    lr0_states: cores&.length, lr0_items: cores&.sum(&:length),
    canonical_items: @profile ? states.sum(&:length) : nil,
    propagation_edges: nil, ielr_initial_partitions: nil, ielr_final_partitions: nil,
    ielr_annotations: nil, ielr_annotated_states: nil, ielr_inadequacies: nil,
    ielr_split_stable_discarded: nil, ielr_lalr_states: nil, ielr_split_states: nil,
    ielr_unreachable_removed: nil, ielr_remergeable_candidates: nil
  }
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]) 


304
305
306
307
308
309
310
311
 
# File 'lib/ibex/lalr/builder.rb', line 304

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) 


267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/ibex/lalr/builder.rb', line 267

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) ⇒ conflict_fingerprint

RBS:

  • (IR::conflict conflict) -> conflict_fingerprint

Parameters:

  • conflict (IR::conflict)

Returns:



721
722
723
724
725
726
727
728
 
# File 'lib/ibex/lalr/builder.rb', line 721

def conflict_fingerprint(conflict)
  reductions = if conflict[:type] == :shift_reduce
                 [conflict[:reduce]]
               else
                 conflict[:reductions]
               end #: Array[Integer]
  [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) 


109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/ibex/lalr/builder.rb', line 109

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


510
511
512
513
514
515
 
# File 'lib/ibex/lalr/builder.rb', line 510

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

#direct_collection ⇒ Object

RBS:

  • () -> untyped

Returns:

  • (Object) 


172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/ibex/lalr/builder.rb', line 172

def direct_collection
  direct = DirectLookaheads.new(@grammar, @sets, profile: @profile)
  items, transitions = direct.build
  apply_slr_lookaheads(items) if @algorithm == :slr
  profile = {
    construction_states: items.length, canonical_states: nil, strategy: :direct_lalr,
    lr0_states: direct.lr0_state_count, lr0_items: direct.lr0_item_count, canonical_items: nil,
    propagation_edges: direct.propagation_edge_count,
    ielr_initial_partitions: nil, ielr_final_partitions: nil,
    ielr_annotations: nil, ielr_annotated_states: nil, ielr_inadequacies: nil,
    ielr_split_stable_discarded: nil, ielr_lalr_states: nil, ielr_split_states: nil,
    ielr_unreachable_removed: nil, ielr_remergeable_candidates: nil
  }
  [items, transitions, profile]
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) 


326
327
328
 
# File 'lib/ibex/lalr/builder.rb', line 326

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


689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
 
# File 'lib/ibex/lalr/builder.rb', line 689

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


540
541
542
543
544
545
546
547
548
 
# File 'lib/ibex/lalr/builder.rb', line 540

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

#ielr_collection ⇒ [ Array[packed_items], transitions, build_collection ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions, build_collection ]) 


139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/ibex/lalr/builder.rb', line 139

def ielr_collection
  return ielr_direct_collection if @ielr_strategy == :direct

  states, transitions = canonical_collection
  partition = IELRPartition.new(@grammar, states, transitions, profile: @profile)
  items, merged_transitions = partition.build
  profile = canonical_profile(states, strategy: :ielr_partition)
  profile[:ielr_initial_partitions] = partition.initial_partition_count
  profile[:ielr_final_partitions] = partition.final_partition_count
  [items, merged_transitions, profile]
end

#ielr_direct_collection ⇒ [ Array[packed_items], transitions, build_collection ]

RBS:

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

Returns:

  • ([ Array[packed_items], transitions, build_collection ]) 


152
153
154
155
 
# File 'lib/ibex/lalr/builder.rb', line 152

def ielr_direct_collection
  pipeline = IELR::Pipeline.new(@grammar, @sets, starts: @start_names, profile: @profile)
  pipeline.build
end

#isolated_conflict_fingerprints ⇒ Set[conflict_fingerprint]

RBS:

  • () -> Set[conflict_fingerprint]

Returns:



707
708
709
710
711
712
713
714
715
716
717
718
 
# File 'lib/ibex/lalr/builder.rb', line 707

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,
                ielr_strategy: @ielr_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:



613
614
615
616
617
618
619
620
621
622
623
624
625
 
# File 'lib/ibex/lalr/builder.rb', line 613

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

  [name, automaton, metrics]
end

#isolated_metrics(entries, construction_states, canonical_states, final_states) ⇒ BuildMetrics

RBS:

  • (Array[[String, IR::Automaton, BuildMetrics]] entries, Integer construction_states, Integer? canonical_states, Integer final_states) -> BuildMetrics

Parameters:

  • entries (Array[[ String, IR::Automaton, BuildMetrics ]])
  • construction_states (Integer)
  • canonical_states (Integer, nil)
  • final_states (Integer)

Returns:



573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
 
# File 'lib/ibex/lalr/builder.rb', line 573

def isolated_metrics(entries, construction_states, canonical_states, final_states)
  BuildMetrics.new(
    construction_states: construction_states, canonical_states: canonical_states,
    final_states: final_states, strategy: :entry_isolation,
    lr0_states: sum_optional_metric(entries, :lr0_states),
    lr0_items: sum_optional_metric(entries, :lr0_items),
    canonical_items: sum_optional_metric(entries, :canonical_items),
    final_items: sum_optional_metric(entries, :final_items),
    final_lookahead_items: sum_optional_metric(entries, :final_lookahead_items),
    propagation_edges: sum_optional_metric(entries, :propagation_edges),
    ielr_initial_partitions: sum_optional_metric(entries, :ielr_initial_partitions),
    ielr_final_partitions: sum_optional_metric(entries, :ielr_final_partitions),
    ielr_annotations: sum_optional_metric(entries, :ielr_annotations),
    ielr_annotated_states: sum_optional_metric(entries, :ielr_annotated_states),
    ielr_inadequacies: sum_optional_metric(entries, :ielr_inadequacies),
    ielr_split_stable_discarded: sum_optional_metric(entries, :ielr_split_stable_discarded),
    ielr_lalr_states: sum_optional_metric(entries, :ielr_lalr_states),
    ielr_split_states: sum_optional_metric(entries, :ielr_split_states),
    ielr_unreachable_removed: sum_optional_metric(entries, :ielr_unreachable_removed),
    ielr_remergeable_candidates: sum_optional_metric(entries, :ielr_remergeable_candidates)
  )
end

#item_key(items) ⇒ Array[Integer]

RBS:

  • (item_set items) -> Array[Integer]

Parameters:

  • items (item_set)

Returns:

  • (Array[Integer]) 


518
519
520
521
522
523
524
 
# File 'lib/ibex/lalr/builder.rb', line 518

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


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

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

#merged_canonical_collection(strategy) ⇒ [ Array[packed_items], transitions, build_collection ]

RBS:

  • (Symbol strategy) -> [Array[packed_items], transitions, build_collection]

Parameters:

  • strategy (Symbol)

Returns:

  • ([ Array[packed_items], transitions, build_collection ]) 


164
165
166
167
168
169
 
# File 'lib/ibex/lalr/builder.rb', line 164

def merged_canonical_collection(strategy)
  states, transitions = canonical_collection
  items, merged_transitions = merge_lalr(states, transitions)
  apply_slr_lookaheads(items) if @algorithm == :slr
  [items, merged_transitions, canonical_profile(states, strategy: strategy)]
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) 


640
641
642
643
644
645
 
# File 'lib/ibex/lalr/builder.rb', line 640

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) 


653
654
655
656
657
658
659
660
661
662
663
664
665
666
 
# File 'lib/ibex/lalr/builder.rb', line 653

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) 


648
649
650
 
# File 'lib/ibex/lalr/builder.rb', line 648

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:



628
629
630
631
632
633
634
635
636
637
 
# File 'lib/ibex/lalr/builder.rb', line 628

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

#output_entry_construction ⇒ String?

RBS:

  • () -> String?

Returns:

  • (String, nil) 


608
609
610
 
# File 'lib/ibex/lalr/builder.rb', line 608

def output_entry_construction
  @entry_isolation ? "isolated" : "shared"
end

#output_schema_version ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


603
604
605
 
# File 'lib/ibex/lalr/builder.rb', line 603

def output_schema_version
  IR::SCHEMA_VERSION
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]) 


374
375
376
377
378
379
380
 
# File 'lib/ibex/lalr/builder.rb', line 374

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

#profiled_final_item_counts(items) ⇒ [ Integer?, Integer? ]

RBS:

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

Parameters:

  • items (Array[packed_items])

Returns:

  • ([ Integer?, Integer? ]) 


203
204
205
206
207
 
# File 'lib/ibex/lalr/builder.rb', line 203

def profiled_final_item_counts(items)
  return [nil, nil] unless @profile

  [items.sum(&:length), items.sum { |state| state.values.sum(&:length) }]
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] ]) 


470
471
472
473
474
475
476
477
478
479
480
481
 
# File 'lib/ibex/lalr/builder.rb', line 470

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


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

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


331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
 
# File 'lib/ibex/lalr/builder.rb', line 331

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


394
395
396
397
398
399
400
 
# File 'lib/ibex/lalr/builder.rb', line 394

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) 


535
536
537
 
# File 'lib/ibex/lalr/builder.rb', line 535

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


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

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

#sum_optional_metric(entries, method) ⇒ Integer?

RBS:

  • (Array[[String, IR::Automaton, BuildMetrics]] entries, Symbol method) -> Integer?

Parameters:

Returns:

  • (Integer, nil) 


597
598
599
600
 
# File 'lib/ibex/lalr/builder.rb', line 597

def sum_optional_metric(entries, method)
  values = entries.map { |_name, _automaton, metrics| metrics.public_send(method) }
  values.compact.sum if values.none?(&:nil?)
end