Class: Ibex::LALR::Builder

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/lalr/builder.rb

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 =

: Integer

-1 #: Integer
ALGORITHMS =

: Array

%i[slr lalr ielr lr1].freeze
LALR_STRATEGIES =

: Array

%i[direct canonical_merge].freeze
IELR_STRATEGIES =

: Array

%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.



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



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

def metrics
  @metrics
end

Instance Method Details

#build ⇒ Object 



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