Class: Ibex::LALR::GotoFollows

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

Overview

Computes DeRemer–Pennello goto-follow sets over an LR(0) collection. The three dependency closures are kept separately because IELR relies on the distinction between stable (successor/internal) and predecessor dependencies when a state is split.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets, states, transitions, start_states, start_names: nil) ⇒ GotoFollows

Returns a new instance of GotoFollows.

RBS:

  • (IR::Grammar grammar, Analysis::Sets sets, Array[core_set] states, transitions transitions, Array[Integer] start_states, ?start_names: Array[String]?) -> void

Parameters:

  • grammar (IR::Grammar)
  • sets (Analysis::Sets)
  • states (Array[core_set])
  • transitions (transitions)
  • start_states (Array[Integer])
  • start_names: (Array[String], nil) (defaults to: nil) 


40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/ibex/lalr/goto_follows.rb', line 40

def initialize(grammar, sets, states, transitions, start_states, start_names: nil)
  @grammar = grammar
  @sets = sets
  @states = states
  @transitions = transitions
  @start_states = start_states
  @start_names = start_names || grammar.starts
  @kernel_cores = states.map { |items| kernel_items(items) }
  build_gotos
  build_dependencies
  build_follow_sets
  @reduction_lookaheads = nil
end

Instance Attribute Details

#always_follows ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


33
34
35
 
# File 'lib/ibex/lalr/goto_follows.rb', line 33

def always_follows
  @always_follows
end

#direct_reads ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


27
28
29
 
# File 'lib/ibex/lalr/goto_follows.rb', line 27

def direct_reads
  @direct_reads
end

#follow_kernel_items ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


35
36
37
 
# File 'lib/ibex/lalr/goto_follows.rb', line 35

def follow_kernel_items
  @follow_kernel_items
end

#from_state ⇒ Array[Integer] (readonly)

RBS:

  • @grammar: IR::Grammar

  • @sets: Analysis::Sets

  • @states: Array[core_set]

  • @transitions: transitions

  • @kernel_cores: Array[Array[item_core]]

Returns:

  • (Array[Integer]) 


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

def from_state
  @from_state
end

#goto_follows ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


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

def goto_follows
  @goto_follows
end

#goto_index ⇒ Hash[[ Integer, Integer ], Integer] (readonly)

Signature:

  • Hash[[Integer, Integer], Integer]

Returns:

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


26
27
28
 
# File 'lib/ibex/lalr/goto_follows.rb', line 26

def goto_index
  @goto_index
end

#includes_edges ⇒ Array[Array[Integer]] (readonly)

Signature:

  • Array[Array[Integer]]

Returns:

  • (Array[Array[Integer]]) 


30
31
32
 
# File 'lib/ibex/lalr/goto_follows.rb', line 30

def includes_edges
  @includes_edges
end

#internal_edges ⇒ Array[Array[Integer]] (readonly)

Signature:

  • Array[Array[Integer]]

Returns:

  • (Array[Array[Integer]]) 


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

def internal_edges
  @internal_edges
end

#kernel_cores ⇒ Array[Array[item_core]] (readonly)

Signature:

  • Array[Array[item_core]]

Returns:

  • (Array[Array[item_core]]) 


36
37
38
 
# File 'lib/ibex/lalr/goto_follows.rb', line 36

def kernel_cores
  @kernel_cores
end

#predecessors ⇒ Array[Array[Integer]] (readonly)

Signature:

  • Array[Array[Integer]]

Returns:

  • (Array[Array[Integer]]) 


31
32
33
 
# File 'lib/ibex/lalr/goto_follows.rb', line 31

def predecessors
  @predecessors
end

#successor_edges ⇒ Array[Array[Integer]] (readonly)

Signature:

  • Array[Array[Integer]]

Returns:

  • (Array[Array[Integer]]) 


28
29
30
 
# File 'lib/ibex/lalr/goto_follows.rb', line 28

def successor_edges
  @successor_edges
end

#successor_follows ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


32
33
34
 
# File 'lib/ibex/lalr/goto_follows.rb', line 32

def successor_follows
  @successor_follows
end

#to_state ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


25
26
27
 
# File 'lib/ibex/lalr/goto_follows.rb', line 25

def to_state
  @to_state
end

Instance Method Details

#advance(state_id, symbols) ⇒ Integer?

RBS:

  • (Integer state_id, Array[Integer]) -> Integer?

Parameters:

  • state_id (Integer)
  • (Array[Integer])

Returns:

  • (Integer, nil) 


207
208
209
210
211
 
# File 'lib/ibex/lalr/goto_follows.rb', line 207

def advance(state_id, symbols)
  symbols.reduce(state_id) do |current, symbol_id|
    @transitions.fetch(current).fetch(symbol_id, nil) || break
  end
end

#build_dependencies ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
# File 'lib/ibex/lalr/goto_follows.rb', line 107

def build_dependencies
  count = @from_state.length
  @direct_reads = Array.new(count, 0)
  @successor_edges = Array.new(count) { [] }
  @internal_edges = Array.new(count) { [] }
  @includes_edges = Array.new(count) { [] }
  @predecessors = Array.new(@states.length) { [] }
  @transitions.each_with_index do |edges, state_id|
    edges.each_value { |target| @predecessors.fetch(target) << state_id }
  end

  count.times do |goto_id|
    destination = @to_state.fetch(goto_id)
    @transitions.fetch(destination).each_key do |symbol_id|
      symbol = @grammar.symbol_by_id(symbol_id)
      if symbol&.terminal?
        @direct_reads[goto_id] |= 1 << symbol_id
      elsif symbol&.nonterminal? && @sets.nullable?(symbol_id)
        successor = @goto_index.fetch([destination, symbol_id])
        @successor_edges.fetch(goto_id) << successor
      end
    end
  end

  @start_states.each_with_index do |state_id, index|
    start_name = @start_names.fetch(index)
    start_symbol = @grammar.symbol(start_name) || raise(Ibex::Error, "missing start symbol #{start_name}")
    goto_id = @goto_index[[state_id, start_symbol.id]]
    @direct_reads[goto_id] |= 1 << eof_id if goto_id
  end

  @goto_index.each do |(inner_source, inner_symbol), inner_goto_id|
    @grammar.productions.each do |production|
      production.rhs.each_with_index do |symbol_id, position|
        next unless symbol_id == inner_symbol
        next unless @grammar.symbol_by_id(symbol_id)&.nonterminal?

        suffix = production.rhs[(position + 1)..] || []
        next unless @sets.sequence_nullable?(suffix)

        @goto_index.each do |(outer_source, outer_symbol), outer_goto_id|
          next unless outer_symbol == production.lhs

          reached = advance(outer_source, production.rhs.take(position))
          next unless reached == inner_source

          @includes_edges.fetch(inner_goto_id) << outer_goto_id
          @internal_edges.fetch(inner_goto_id) << outer_goto_id if position.zero?
        end
      end
    end
  end
  @successor_edges.each(&:uniq!)
  @internal_edges.each(&:uniq!)
  @includes_edges.each(&:uniq!)
  @predecessors.each(&:uniq!)
end

#build_follow_sets ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



166
167
168
169
170
171
172
173
174
175
 
# File 'lib/ibex/lalr/goto_follows.rb', line 166

def build_follow_sets
  @successor_follows = Analysis::Digraph.closure(@direct_reads, @successor_edges)
  internal_initial = @from_state.each_index.map do |goto_id|
    1 << symbol_for_goto(goto_id)
  end
  @internal_reachable_symbols = Analysis::Digraph.closure(internal_initial, @internal_edges)
  @always_follows = Analysis::Digraph.closure(@direct_reads, merged_edges(@successor_edges, @internal_edges))
  @goto_follows = Analysis::Digraph.closure(@always_follows, @includes_edges)
  @follow_kernel_items = @from_state.each_index.map { |goto_id| compute_follow_kernel_items(goto_id) }
end

#build_gotos ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/ibex/lalr/goto_follows.rb', line 87

def build_gotos
  @from_state = []
  @to_state = []
  @goto_symbols = []
  @goto_index = {}
  @transitions.each_with_index do |edges, state_id|
    edges.keys.sort.each do |symbol_id|
      symbol = @grammar.symbol_by_id(symbol_id)
      next unless symbol&.nonterminal?

      goto_id = @from_state.length
      @from_state << state_id
      @to_state << edges.fetch(symbol_id)
      @goto_symbols << symbol_id
      @goto_index[[state_id, symbol_id]] = goto_id
    end
  end
end

#compute_follow_kernel_items(goto_id) ⇒ Integer

RBS:

  • (Integer goto_id) -> Integer

Parameters:

  • goto_id (Integer)

Returns:

  • (Integer) 


183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/ibex/lalr/goto_follows.rb', line 183

def compute_follow_kernel_items(goto_id)
  state_id = @from_state.fetch(goto_id)
  reachable = @internal_reachable_symbols.fetch(goto_id)
  @kernel_cores.fetch(state_id).each_with_index.reduce(0) do |mask, ((production_id, dot), index)|
    rhs = rhs_for(production_id)
    symbol_id = rhs[dot]
    next mask unless symbol_id && reachable.anybits?(1 << symbol_id)
    next mask unless @sets.sequence_nullable?(rhs[(dot + 1)..] || [])

    mask | (1 << index)
  end
end

#eof_id ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


221
222
223
 
# File 'lib/ibex/lalr/goto_follows.rb', line 221

def eof_id
  0
end

#goto_for(state_id, nonterminal_id) ⇒ Integer?

RBS:

  • (Integer state_id, Integer nonterminal_id) -> Integer?

Parameters:

  • state_id (Integer)
  • nonterminal_id (Integer)

Returns:

  • (Integer, nil) 


55
56
57
 
# File 'lib/ibex/lalr/goto_follows.rb', line 55

def goto_for(state_id, nonterminal_id)
  @goto_index[[state_id, nonterminal_id]]
end

#kernel_items(items) ⇒ Array[item_core]

RBS:

  • (core_set items) -> Array[item_core]

Parameters:

  • items (core_set)

Returns:

  • (Array[item_core]) 


197
198
199
 
# File 'lib/ibex/lalr/goto_follows.rb', line 197

def kernel_items(items)
  items.select { |production_id, dot| production_id.negative? || dot.positive? }.to_a.sort
end

#merged_edges(left, right) ⇒ Array[Array[Integer]]

RBS:

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

Parameters:

  • (Array[Array[Integer]])
  • (Array[Array[Integer]])

Returns:

  • (Array[Array[Integer]]) 


178
179
180
 
# File 'lib/ibex/lalr/goto_follows.rb', line 178

def merged_edges(left, right)
  left.each_index.map { |index| (left.fetch(index) + right.fetch(index)).uniq }
end

#reduction_lookaheads ⇒ Array[Hash[Integer, Integer]]

RBS:

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

Returns:

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


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

def reduction_lookaheads
  return @reduction_lookaheads if @reduction_lookaheads

  result = Array.new(@states.length) { {} }
  seeds = @start_states.each_with_index.map do |state_id, index|
    augmented = -1 - @grammar.starts.index(@start_names.fetch(index))
    [state_id, [augmented, 0], eof_id]
  end
  propagated = LookaheadPropagation.new(
    @grammar, @sets, @states, @transitions, seeds: seeds
  ).build
  @states.each_with_index do |items, state_id|
    items.each do |production_id, dot|
      next unless dot == rhs_for(production_id).length

      values = propagated.fetch(state_id).fetch([production_id, dot], [])
      result.fetch(state_id)[production_id] = values.reduce(0) do |bits, token|
        bits | (1 << token)
      end
    end
  end
  @reduction_lookaheads = result
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


214
215
216
217
218
 
# File 'lib/ibex/lalr/goto_follows.rb', line 214

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

#symbol_for_goto(goto_id) ⇒ Integer

RBS:

  • (Integer goto_id) -> Integer

Parameters:

  • goto_id (Integer)

Returns:

  • (Integer) 


202
203
204
 
# File 'lib/ibex/lalr/goto_follows.rb', line 202

def symbol_for_goto(goto_id)
  @goto_symbols.fetch(goto_id)
end