Class: Ibex::LALR::LookaheadPropagation

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

Overview

Recomputes item lookaheads on an already-built LR(0) automaton. This is Phase 4 of direct IELR and is also useful as an independent cross-check for DirectLookaheads.

Constant Summary collapse

EMPTY =

Signature:

  • Array[Integer]

Returns:

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets, states, transitions, seeds:) ⇒ Array[packed_items]

RBS:

  • (IR::Grammar grammar, Analysis::Sets sets, Array[core_set] states, transitions transitions, seeds: Array[[Integer, item_core, Integer]]) -> Array[packed_items]

Parameters:

  • grammar (IR::Grammar)
  • sets (Analysis::Sets)
  • states (Array[core_set])
  • transitions (transitions)
  • seeds: (Array[[ Integer, item_core, Integer ]]) 


20
21
22
23
24
25
26
27
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 20

def initialize(grammar, sets, states, transitions, seeds:)
  @grammar = grammar
  @sets = sets
  @states = states
  @transitions = transitions
  @seeds = seeds
  @productions_by_lhs = grammar.productions.group_by(&:lhs)
end

Instance Attribute Details

#propagation_edge_count ⇒ Integer (readonly)

Signature:

  • Integer

Returns:

  • (Integer) 


16
17
18
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 16

def propagation_edge_count
  @propagation_edge_count
end

Instance Method Details

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

This method returns an undefined value.

RBS:

  • (Hash[Object, Array[Object]], Array[packed_items], Integer, Integer, Integer) -> void

Parameters:

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


57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 57

def add_closure(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))
  @productions_by_lhs.fetch(symbol.id, []).each do |production|
    item = [production.id, 0].freeze
    lookaheads.fetch(state_id).fetch(item).merge(spontaneous)
    edges[[state_id, production_id, dot]] << [state_id, production.id, 0] if
      @sets.sequence_nullable?(suffix)
  end
end

#add_transition(edges, state_id, production_id, dot) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Object, Array[Object]], Integer, Integer, Integer) -> void

Parameters:

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


48
49
50
51
52
53
54
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 48

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

  target = @transitions.fetch(state_id).fetch(symbol_id)
  edges[[state_id, production_id, dot]] << [target, production_id, dot + 1]
end

#build ⇒ Array[packed_items]

RBS:

  • () -> Array[packed_items]

Returns:

  • (Array[packed_items]) 


30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 30

def build
  lookaheads = @states.map { |items| items.to_h { |item| [item, Set.new] } }
  edges = Hash.new { |hash, key| hash[key] = [] }
  @states.each_with_index do |items, state_id|
    items.each do |production_id, dot|
      add_transition(edges, state_id, production_id, dot)
      add_closure(edges, lookaheads, state_id, production_id, dot)
    end
  end
  @seeds.each { |state_id, item, token| lookaheads.fetch(state_id).fetch(item) << token }
  @propagation_edge_count = edges.values.sum(&:length)
  propagate(lookaheads, edges)
  lookaheads
end

#propagate(lookaheads, edges) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[packed_items], Hash[Object, Array[Object]]) -> void

Parameters:

  • (Array[packed_items])
  • (Hash[Object, Array[Object]]) 


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

def propagate(lookaheads, edges)
  queue = @seeds.map { |state_id, (production_id, dot), _token| [state_id, production_id, dot] }
  queue.concat(lookaheads.each_with_index.flat_map do |items, state_id|
    items.filter_map { |(production_id, dot), values| [state_id, production_id, dot] unless values.empty? }
  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 = lookaheads.fetch(source[0]).fetch([source[1], source[2]])
    edges.fetch(source, EMPTY).each do |target|
      target_set = lookaheads.fetch(target[0]).fetch([target[1], target[2]])
      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

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


103
104
105
106
107
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 103

def rhs_for(production_id)
  return [@grammar.symbol(@grammar.starts.fetch(-production_id - 1)).id] if production_id.negative?

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

#terminal_ids(bits) ⇒ Array[Integer]

RBS:

  • (Integer bits) -> Array[Integer]

Parameters:

  • bits (Integer)

Returns:

  • (Array[Integer]) 


98
99
100
 
# File 'lib/ibex/lalr/lookahead_propagation.rb', line 98

def terminal_ids(bits)
  @grammar.terminals.filter_map { |terminal| terminal.id if bits.anybits?(1 << terminal.id) }
end