Class: Ibex::LALR::GotoFollows

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

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.



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

: Array



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

def always_follows
  @always_follows
end

#direct_reads ⇒ Object (readonly)

: Array



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

def direct_reads
  @direct_reads
end

#follow_kernel_items ⇒ Object (readonly)

: Array



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

def follow_kernel_items
  @follow_kernel_items
end

#from_state ⇒ Object (readonly) 



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

def from_state
  @from_state
end

#goto_follows ⇒ Object (readonly)

: Array



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

def goto_follows
  @goto_follows
end

#goto_index ⇒ Object (readonly)

: Hash[[Integer, Integer], Integer]



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

def goto_index
  @goto_index
end

#includes_edges ⇒ Object (readonly)

: Array[Array[Integer]]



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

def includes_edges
  @includes_edges
end

#internal_edges ⇒ Object (readonly)

: Array[Array[Integer]]



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

def internal_edges
  @internal_edges
end

#kernel_cores ⇒ Object (readonly)

: Array[Array[item_core]]



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

def kernel_cores
  @kernel_cores
end

#predecessors ⇒ Object (readonly)

: Array[Array[Integer]]



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

def predecessors
  @predecessors
end

#successor_edges ⇒ Object (readonly)

: Array[Array[Integer]]



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

def successor_edges
  @successor_edges
end

#successor_follows ⇒ Object (readonly)

: Array



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

def successor_follows
  @successor_follows
end

#to_state ⇒ Object (readonly)

: Array



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

def to_state
  @to_state
end

Instance Method Details

#goto_for(state_id, nonterminal_id) ⇒ Object 



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

#reduction_lookaheads ⇒ Object 



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