Class: Ibex::LALR::ConflictSearch

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

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 =

: Integer

ConflictSearchLimits::DEFAULT_MAX_TOKENS
DEFAULT_MAX_CONFIGURATIONS =

: Integer

ConflictSearchLimits::DEFAULT_MAX_CONFIGURATIONS

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from ConflictSearchLimits

validate!, validate_limit!

Constructor Details

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

Returns a new instance of ConflictSearch.



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 ⇒ Object (readonly) 



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

def explored
  @explored
end

Instance Method Details

#call ⇒ Object 



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

#exhausted? ⇒ Boolean

Returns:

  • (Boolean) 


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

def exhausted? = @explored >= @max_configurations