Class: Ibex::LALR::DirectLookaheads

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

Overview

Builds an LR(0) collection and propagates LALR(1) lookaheads directly over item occurrences. Canonical LR(1) states are never materialized.

Constant Summary collapse

AUGMENTED_PRODUCTION =

: Integer

-1 #: Integer

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets, starts: nil, profile: false) ⇒ DirectLookaheads

Returns a new instance of DirectLookaheads.

Raises:

  • (ArgumentError) 


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 27

def initialize(grammar, sets, starts: nil, profile: false)
  @grammar = grammar
  @sets = sets
  @grammar_starts = grammar_starts.freeze
  @starts = (starts || @grammar_starts).dup
  raise ArgumentError, "starts must be a nonempty subset of grammar starts" if
    @starts.empty? || (@starts - @grammar_starts).any?

  @productions_by_lhs = grammar.productions.group_by(&:lhs)
  @augmented_production_ids = @starts.map { |name| AUGMENTED_PRODUCTION - start_index(name) }
  @augmented_rhs = @starts.each_with_index.to_h do |name, index|
    symbol = grammar.symbol(name) || raise(Ibex::Error, "missing start symbol #{name}")
    [@augmented_production_ids.fetch(index), [symbol.id].freeze]
  end.freeze
  @production_rhs = grammar.productions.map(&:rhs).freeze
  @augmented_item_cores = @augmented_rhs.to_h do |production_id, rhs|
    [production_id, item_cores_for(production_id, rhs.length)]
  end.freeze
  @production_item_cores = grammar.productions.map do |production|
    item_cores_for(production.id, production.rhs.length)
  end.freeze
  initialize_item_encoding
  @terminal_ids = grammar.terminals.map(&:id).freeze
  @terminal_masks = @terminal_ids.map { |id| 1 << id }.freeze
  @terminal_ids_by_bits = {} #: Hash[Integer, Array[Integer]]
  @lr0_state_count = nil
  @lr0_item_count = nil
  @propagation_edge_count = nil
  @profile = profile
end

Instance Attribute Details

#lr0_item_count ⇒ Object (readonly)

: Integer?



21
22
23
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 21

def lr0_item_count
  @lr0_item_count
end

#lr0_state_count ⇒ Object (readonly)

: Integer?



20
21
22
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 20

def lr0_state_count
  @lr0_state_count
end

#propagation_edge_count ⇒ Object (readonly)

: Integer?



22
23
24
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 22

def propagation_edge_count
  @propagation_edge_count
end

#states ⇒ Object (readonly)

: Array



23
24
25
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 23

def states
  @states
end

#transitions ⇒ Object (readonly)

: transitions



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

def transitions
  @transitions
end

Instance Method Details

#augmented_production(index) ⇒ Object 



78
79
80
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 78

def augmented_production(index)
  @augmented_production_ids.fetch(index)
end

#build ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 59

def build
  states, transitions = lr0_collection
  @states = states
  @transitions = transitions
  lookaheads = empty_lookaheads(states)
  propagation = propagation_graph(states, transitions, lookaheads)
  if @profile
    @lr0_state_count = states.length
    @lr0_item_count = states.sum(&:length)
    @propagation_edge_count = propagation.values.sum(&:length)
  end
  @starts.each_with_index do |_name, index|
    lookaheads.fetch(index).fetch(item_core(augmented_production(index), 0)) << 0
  end
  propagate(lookaheads, propagation)
  [lookaheads, transitions]
end