Class: Ibex::LALR::LR0Collection

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

Overview

Constructs only the LR(0) core collection. Keeping this separate from lookahead propagation makes the direct IELR phases reusable and gives them a stable, canonical-free input representation.

Constant Summary collapse

AUGMENTED_PRODUCTION =

: Integer

-1 #: Integer

Instance Method Summary collapse

Constructor Details

#initialize(grammar, starts: nil) ⇒ LR0Collection

Returns a new instance of LR0Collection.

Raises:

  • (ArgumentError) 


24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 24

def initialize(grammar, starts: nil)
  @grammar = grammar
  @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)
  @production_rhs = grammar.productions.map(&:rhs).freeze
  @augmented_production_ids = @starts.map { |name| AUGMENTED_PRODUCTION - grammar.starts.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
  @item_key_stride = [*@production_rhs, *@augmented_rhs.values].map(&:length).max.to_i + 1
end

Instance Method Details

#augmented_production(index) ⇒ Object 



63
64
65
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 63

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

#build ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 41

def build
  states = @starts.map { |name| closure(Set[[augmented_production(@starts.index(name)), 0]]) }
  transitions = [] #: transitions
  indexes = {}
  states.each_with_index { |items, index| indexes[item_key(items)] = index }
  cursor = 0
  while cursor < states.length
    transitions[cursor] = {}
    shifted_kernels(states.fetch(cursor)).keys.sort.each do |symbol_id|
      target = closure(shifted_kernels(states.fetch(cursor)).fetch(symbol_id))
      target_id = indexes[item_key(target)] ||= begin
        states << target
        states.length - 1
      end
      transitions.fetch(cursor)[symbol_id] = target_id
    end
    cursor += 1
  end
  [states, transitions]
end

#lhs_for(production_id) ⇒ Object 



75
76
77
78
79
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 75

def lhs_for(production_id)
  return rhs_for(production_id).fetch(0) if production_id.negative?

  @grammar.productions.fetch(production_id).lhs
end

#rhs_for(production_id) ⇒ Object 



68
69
70
71
72
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 68

def rhs_for(production_id)
  return @augmented_rhs.fetch(production_id) if production_id.negative?

  @production_rhs.fetch(production_id)
end

#shifted_kernels(items) ⇒ Object 



82
83
84
85
86
87
88
89
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 82

def shifted_kernels(items)
  kernels = Hash.new { |hash, key| hash[key] = Set.new } #: Hash[Integer, core_set]
  items.each do |production_id, dot|
    symbol_id = rhs_for(production_id)[dot]
    kernels[symbol_id] << [production_id, dot + 1].freeze if symbol_id
  end
  kernels
end