Class: Ibex::LALR::LookaheadPropagation

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

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 =

: Array

Array.new(0).freeze

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets, states, transitions, seeds:) ⇒ LookaheadPropagation

Returns a new instance of LookaheadPropagation.



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

: Integer



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

def propagation_edge_count
  @propagation_edge_count
end

Instance Method Details

#build ⇒ Object 



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