Class: Ibex::LALR::ConflictSearch

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

Overview

Searches the parser state space for one input accepted through both sides of a conflict. rubocop:disable Metrics/ClassLength -- inline type contracts make the focused search implementation longer.

Defined Under Namespace

Classes: Configuration

Constant Summary collapse

DEFAULT_MAX_TOKENS =

Signature:

  • Integer

Returns:

  • (Integer) 
ConflictSearchLimits::DEFAULT_MAX_TOKENS
DEFAULT_MAX_CONFIGURATIONS =

Signature:

  • Integer

Returns:

  • (Integer) 
ConflictSearchLimits::DEFAULT_MAX_CONFIGURATIONS

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from ConflictSearchLimits

#conflict_lookahead_length, #room_for_token?, validate!, validate_limit!, #within_token_budget?

Constructor Details

#initialize(automaton, state, conflict, max_tokens: DEFAULT_MAX_TOKENS, max_configurations: DEFAULT_MAX_CONFIGURATIONS) ⇒ ConflictSearch

Returns a new instance of ConflictSearch.

RBS:

  • (IR::Automaton automaton, IR::AutomatonState state, IR::conflict conflict, ?max_tokens: Integer, ?max_configurations: Integer) -> void

Parameters:

  • automaton (IR::Automaton)
  • state (IR::AutomatonState)
  • conflict (IR::conflict)
  • max_tokens: (Integer) (defaults to: DEFAULT_MAX_TOKENS)
  • max_configurations: (Integer) (defaults to: DEFAULT_MAX_CONFIGURATIONS) 


34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/ibex/lalr/conflict_search.rb', line 34

def initialize(automaton, state, conflict, max_tokens: DEFAULT_MAX_TOKENS,
               max_configurations: DEFAULT_MAX_CONFIGURATIONS)
  ConflictSearchLimits.validate!(max_tokens: max_tokens, max_configurations: max_configurations)
  @automaton = automaton
  @grammar = automaton.grammar
  @state = state
  @conflict = conflict
  @lookahead = @grammar.symbol(conflict[:symbol])&.id
  @max_tokens = max_tokens
  @max_configurations = max_configurations
  @explored = 0
  @input_tokens = @grammar.terminals.reject(&:reserved).sort_by(&:name).map(&:id)
  entry = conflict[:entries]&.first || @grammar.start
  @initial_state = automaton.entry_states.fetch(entry)
end

Instance Attribute Details

#explored ⇒ Integer (readonly)

RBS:

  • @automaton: IR::Automaton

  • @grammar: IR::Grammar

  • @state: IR::AutomatonState

  • @conflict: IR::conflict

  • @lookahead: Integer?

  • @max_tokens: Integer

  • @max_configurations: Integer

  • @explored: Integer

  • @input_tokens: Array[Integer]

  • @initial_state: Integer

Returns:

  • (Integer) 


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

def explored
  @explored
end

Instance Method Details

#accept_with_eof(left_config, right_config) ⇒ [ search_entry, search_entry ]?

RBS:

  • (Configuration left_config, Configuration right_config) -> [search_entry, search_entry]?

Parameters:

Returns:

  • ([ search_entry, search_entry ], nil) 


132
133
134
135
136
 
# File 'lib/ibex/lalr/conflict_search.rb', line 132

def accept_with_eof(left_config, right_config)
  left = advance(left_config, 0, branch_conflicts: true).select { |entry| entry.first == :accepted }
  right = advance(right_config, 0, branch_conflicts: true).select { |entry| entry.first == :accepted }
  left.product(right).first
end

#accepted_pair?(left, right) ⇒ Boolean

RBS:

  • (search_entry left, search_entry right) -> bool

Parameters:

  • left (search_entry)
  • right (search_entry)

Returns:

  • (Boolean) 


188
189
190
 
# File 'lib/ibex/lalr/conflict_search.rb', line 188

def accepted_pair?(left, right)
  left.first == :accepted && right.first == :accepted
end

#accepted_result(prefix, suffix, left, right, left_action, right_action) ⇒ search_result?

RBS:

  • (Array[Integer] prefix, Array[Integer] suffix, search_entry left, search_entry right, IR::parser_action left_action, IR::parser_action right_action) -> search_result?

Parameters:

  • prefix (Array[Integer])
  • suffix (Array[Integer])
  • left (search_entry)
  • right (search_entry)
  • left_action (IR::parser_action)
  • right_action (IR::parser_action)

Returns:

  • (search_result, nil) 


163
164
165
166
167
168
169
170
171
172
 
# File 'lib/ibex/lalr/conflict_search.rb', line 163

def accepted_result(prefix, suffix, left, right, left_action, right_action)
  return unless within_token_budget?(prefix, suffix)

  sentence = prefix.dup
  lookahead = required_lookahead
  sentence << lookahead unless lookahead.zero?
  sentence.concat(suffix)
  { sentence_ids: sentence, lookahead_index: prefix.length,
    interpretations: [interpretation(left_action, left.last), interpretation(right_action, right.last)] }
end

#actions_for(state_id, token_id, forced, branch_conflicts) ⇒ Array[IR::parser_action]

RBS:

  • (Integer state_id, Integer token_id, IR::parser_action? forced, bool branch_conflicts) -> Array[IR::parser_action]

Parameters:

  • state_id (Integer)
  • token_id (Integer)
  • forced (IR::parser_action, nil)
  • branch_conflicts (Boolean)

Returns:

  • (Array[IR::parser_action]) 


242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 
# File 'lib/ibex/lalr/conflict_search.rb', line 242

def actions_for(state_id, token_id, forced, branch_conflicts)
  return [forced] if forced

  state = @automaton.states.fetch(state_id)
  actions = [state.actions[token_id] || state.default_action].compact
  return actions unless branch_conflicts

  token_name = symbol_name(token_id)
  state.conflicts.each do |conflict|
    next unless conflict[:symbol] == token_name

    actions.concat(actions_from(conflict))
  end
  actions.uniq
end

#actions_from(conflict) ⇒ Array[IR::parser_action]

RBS:

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

Parameters:

  • conflict (IR::conflict)

Returns:

  • (Array[IR::parser_action]) 


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

def actions_from(conflict)
  case conflict[:type]
  when :shift_reduce
    shift_reduce = conflict #: IR::shift_reduce_conflict
    shift = { type: :shift, state: shift_reduce[:shift_to] } #: IR::shift_action
    reduce = { type: :reduce, production: shift_reduce[:reduce] } #: IR::reduce_action
    [shift, reduce]
  when :reduce_reduce
    reduce_reduce = conflict #: IR::reduce_reduce_conflict
    reduce_reduce[:reductions].map do |production|
      { type: :reduce, production: production } #: IR::reduce_action
    end
  else
    []
  end
end

#advance(initial, token_id, forced_action: nil, stop_at: nil, branch_conflicts: false) ⇒ Array[search_entry]

RBS:

  • (Configuration initial, Integer token_id, ?forced_action: IR::parser_action?, ?stop_at: Integer?, ?branch_conflicts: bool) -> Array[search_entry]

Parameters:

  • initial (Configuration)
  • token_id (Integer)
  • forced_action: (IR::parser_action, nil) (defaults to: nil)
  • stop_at: (Integer, nil) (defaults to: nil)
  • branch_conflicts: (Boolean) (defaults to: false)

Returns:

  • (Array[search_entry]) 


217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
 
# File 'lib/ibex/lalr/conflict_search.rb', line 217

def advance(initial, token_id, forced_action: nil, stop_at: nil, branch_conflicts: false)
  queue = [[initial, forced_action]] #: Array[[Configuration, IR::parser_action?]]
  visited = {} #: Hash[[Array[Integer], bool], bool]
  results = [] #: Array[search_entry]
  until queue.empty? || exhausted?
    current, forced = queue.shift
    if stop_at == current.states.last
      results << [:conflict, current]
      next
    end

    key = [current.states, !forced.nil?] #: [Array[Integer], bool]
    next if visited[key]

    visited[key] = true
    count_configuration
    actions_for(current.states.last, token_id, forced, branch_conflicts).each do |action|
      apply_action(results, queue, current, action, token_id)
    end
  end
  results
end

#apply_action(results, queue, current, action, token_id) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[search_entry] results, Array[[Configuration, IR::parser_action?]] queue, Configuration current, IR::parser_action action, Integer token_id) -> void

Parameters:

  • results (Array[search_entry])
  • queue (Array[[ Configuration, IR::parser_action? ]])
  • current (Configuration)
  • action (IR::parser_action)
  • token_id (Integer) 


278
279
280
281
282
283
284
285
286
287
288
289
290
 
# File 'lib/ibex/lalr/conflict_search.rb', line 278

def apply_action(results, queue, current, action, token_id)
  case action[:type]
  when :shift
    shift_action = action #: IR::shift_action
    results << [:shifted, shift(current, shift_action[:state], token_id)]
  when :reduce
    reduce_action = action #: IR::reduce_action
    reduced = reduce(current, reduce_action[:production])
    queue << [reduced, nil] if reduced
  when :accept
    results << [:accepted, current]
  end
end

#call ⇒ search_result?

RBS:

  • () -> search_result?

Returns:

  • (search_result, nil) 


51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/ibex/lalr/conflict_search.rb', line 51

def call
  return unless @lookahead

  initial = configuration([@initial_state], Array.new(0))
  queue = [[initial, Array.new(0)]] #: Array[[Configuration, Array[Integer]]]
  visited = { [@initial_state] => true }
  until queue.empty? || exhausted?
    current, prefix = queue.shift
    conflict_configurations(current).each do |candidate|
      result = unify_from(candidate, prefix)
      return result if result
    end
    enqueue_prefixes(queue, visited, current, prefix)
  end
  nil
end

#configuration(states, nodes) ⇒ Configuration

RBS:

  • (Array[Integer] states, Array[derivation_node] nodes) -> Configuration

Parameters:

  • states (Array[Integer])
  • nodes (Array[derivation_node])

Returns:



315
 
# File 'lib/ibex/lalr/conflict_search.rb', line 315

def configuration(states, nodes) = Configuration.new(states: states.freeze, nodes: nodes.freeze)

#conflict_actions ⇒ Array[IR::parser_action]

RBS:

  • () -> Array[IR::parser_action]

Returns:

  • (Array[IR::parser_action]) 


198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
 
# File 'lib/ibex/lalr/conflict_search.rb', line 198

def conflict_actions
  case @conflict[:type]
  when :shift_reduce
    conflict = @conflict #: IR::shift_reduce_conflict
    shift = { type: :shift, state: conflict[:shift_to] } #: IR::shift_action
    reduce = { type: :reduce, production: conflict[:reduce] } #: IR::reduce_action
    [shift, reduce]
  when :reduce_reduce
    conflict = @conflict #: IR::reduce_reduce_conflict
    conflict[:reductions].map do |production|
      { type: :reduce, production: production } #: IR::reduce_action
    end
  else
    []
  end
end

#conflict_configurations(current) ⇒ Array[Configuration]

RBS:

  • (Configuration current) -> Array[Configuration]

Parameters:

Returns:



74
75
76
77
 
# File 'lib/ibex/lalr/conflict_search.rb', line 74

def conflict_configurations(current)
  advance(current, required_lookahead, stop_at: @state.id, branch_conflicts: true)
    .filter_map { |status, candidate| candidate if status == :conflict }
end

#count_configuration ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


334
 
# File 'lib/ibex/lalr/conflict_search.rb', line 334

def count_configuration = (@explored += 1)

#enqueue_prefixes(queue, visited, current, prefix) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[[Configuration, Array[Integer]]] queue, Hash[Array[Integer], bool] visited, Configuration current, Array[Integer] prefix) -> void

Parameters:

  • queue (Array[[ Configuration, Array[Integer] ]])
  • visited (Hash[Array[Integer], bool])
  • current (Configuration)
  • prefix (Array[Integer]) 


81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/ibex/lalr/conflict_search.rb', line 81

def enqueue_prefixes(queue, visited, current, prefix)
  return unless room_for_token?(prefix, [])

  @input_tokens.each do |token_id|
    advance(current, token_id, branch_conflicts: true).each do |status, candidate|
      next unless status == :shifted
      next if visited[candidate.states]

      visited[candidate.states] = true
      queue << [candidate, prefix + [token_id]]
    end
  end
end

#enqueue_suffixes(queue, visited, left_config, right_config, suffix) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[[Configuration, Configuration, Array[Integer]]] queue, Hash[[Array[Integer], Array[Integer]], bool] visited, Configuration left_config, Configuration right_config, Array[Integer] suffix) -> void

Parameters:



141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/ibex/lalr/conflict_search.rb', line 141

def enqueue_suffixes(queue, visited, left_config, right_config, suffix)
  @input_tokens.each do |token_id|
    left = shifted_results(left_config, token_id)
    right = shifted_results(right_config, token_id)
    left.product(right).each do |left_candidate, right_candidate|
      key = pair_key(left_candidate, right_candidate)
      next if visited[key]

      visited[key] = true
      queue << [left_candidate, right_candidate, suffix + [token_id]]
    end
  end
end

#exhausted? ⇒ Boolean

RBS:

  • () -> bool

Returns:

  • (Boolean) 


69
 
# File 'lib/ibex/lalr/conflict_search.rb', line 69

def exhausted? = @explored >= @max_configurations

#interpretation(action, current) ⇒ IR::interpretation

RBS:

  • (IR::parser_action action, Configuration current) -> IR::interpretation

Parameters:

Returns:

  • (IR::interpretation) 


175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/ibex/lalr/conflict_search.rb', line 175

def interpretation(action, current)
  details = { kind: action[:type], tree: current.nodes.last } #: IR::interpretation
  if action[:type] == :shift
    shift_action = action #: IR::shift_action
    details[:state] = shift_action[:state]
  elsif action[:type] == :reduce
    reduce_action = action #: IR::reduce_action
    details[:production] = reduce_action[:production]
  end
  details
end

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

RBS:

  • (Configuration left, Configuration right) -> [Array[Integer], Array[Integer]]

Parameters:

Returns:

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


329
330
331
 
# File 'lib/ibex/lalr/conflict_search.rb', line 329

def pair_key(left, right)
  [left.states, right.states]
end

#reduce(current, production_id) ⇒ Configuration?

RBS:

  • (Configuration current, Integer production_id) -> Configuration?

Parameters:

Returns:



299
300
301
302
303
304
305
306
307
308
309
310
311
312
 
# File 'lib/ibex/lalr/conflict_search.rb', line 299

def reduce(current, production_id)
  production = @grammar.productions.fetch(production_id)
  length = production.rhs.length
  return if length >= current.states.length

  states = current.states.take(current.states.length - length)
  children = current.nodes.last(length)
  nodes = current.nodes.take(current.nodes.length - length)
  target = @automaton.states.fetch(states.last).gotos[production.lhs]
  return unless target

  symbol = symbol_name(production.lhs)
  configuration(states + [target], nodes + [{ symbol: symbol, production: production_id, children: children }])
end

#required_lookahead ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


318
319
320
 
# File 'lib/ibex/lalr/conflict_search.rb', line 318

def required_lookahead
  @lookahead || raise(Ibex::Error, "missing conflict lookahead")
end

#search_common_suffix(left, right, prefix, left_action, right_action) ⇒ search_result?

RBS:

  • (search_entry left, search_entry right, Array[Integer] prefix, IR::parser_action left_action, IR::parser_action right_action) -> search_result?

Parameters:

  • left (search_entry)
  • right (search_entry)
  • prefix (Array[Integer])
  • left_action (IR::parser_action)
  • right_action (IR::parser_action)

Returns:

  • (search_result, nil) 


114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/ibex/lalr/conflict_search.rb', line 114

def search_common_suffix(left, right, prefix, left_action, right_action)
  return accepted_result(prefix, [], left, right, left_action, right_action) if accepted_pair?(left, right)
  return unless shifted_pair?(left, right)

  queue = [[left.last, right.last, Array.new(0)]] #: Array[[Configuration, Configuration, Array[Integer]]]
  visited = { pair_key(left.last, right.last) => true }
  until queue.empty? || exhausted?
    left_config, right_config, suffix = queue.shift
    accepted = accept_with_eof(left_config, right_config)
    return accepted_result(prefix, suffix, accepted[0], accepted[1], left_action, right_action) if accepted
    next unless room_for_token?(prefix, suffix)

    enqueue_suffixes(queue, visited, left_config, right_config, suffix)
  end
  nil
end

#shift(current, state_id, token_id) ⇒ Configuration

RBS:

  • (Configuration current, Integer state_id, Integer token_id) -> Configuration

Parameters:

Returns:



293
294
295
296
 
# File 'lib/ibex/lalr/conflict_search.rb', line 293

def shift(current, state_id, token_id)
  symbol = symbol_name(token_id)
  configuration(current.states + [state_id], current.nodes + [{ symbol: symbol, token: symbol }])
end

#shifted_pair?(left, right) ⇒ Boolean

RBS:

  • (search_entry left, search_entry right) -> bool

Parameters:

  • left (search_entry)
  • right (search_entry)

Returns:

  • (Boolean) 


193
194
195
 
# File 'lib/ibex/lalr/conflict_search.rb', line 193

def shifted_pair?(left, right)
  left.first == :shifted && right.first == :shifted
end

#shifted_results(current, token_id) ⇒ Array[Configuration]

RBS:

  • (Configuration current, Integer token_id) -> Array[Configuration]

Parameters:

Returns:



156
157
158
159
 
# File 'lib/ibex/lalr/conflict_search.rb', line 156

def shifted_results(current, token_id)
  advance(current, token_id, branch_conflicts: true)
    .filter_map { |status, candidate| candidate if status == :shifted }
end

#symbol_name(id) ⇒ String

RBS:

  • (Integer id) -> String

Parameters:

  • id (Integer)

Returns:

  • (String) 


323
324
325
326
 
# File 'lib/ibex/lalr/conflict_search.rb', line 323

def symbol_name(id)
  symbol = @grammar.symbol_by_id(id) || raise(Ibex::Error, "missing grammar symbol id #{id}")
  symbol.name
end

#unify_from(current, prefix) ⇒ search_result?

RBS:

  • (Configuration current, Array[Integer] prefix) -> search_result?

Parameters:

Returns:

  • (search_result, nil) 


96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/ibex/lalr/conflict_search.rb', line 96

def unify_from(current, prefix)
  return unless within_token_budget?(prefix, [])

  conflict_actions.combination(2) do |left_action, right_action|
    next unless left_action && right_action

    left_results = advance(current, required_lookahead, forced_action: left_action, branch_conflicts: true)
    right_results = advance(current, required_lookahead, forced_action: right_action, branch_conflicts: true)
    left_results.product(right_results).each do |left, right|
      result = search_common_suffix(left, right, prefix, left_action, right_action)
      return result if result
    end
  end
  nil
end