Class: Ibex::LALR::LR0Collection

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

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 =

Signature:

  • Integer

Returns:

  • (Integer) 
-1 #: Integer

Instance Method Summary collapse

Constructor Details

#initialize(grammar, starts: nil) ⇒ LR0Collection

Returns a new instance of LR0Collection.

RBS:

  • (IR::Grammar grammar, ?starts: Array[String]?) -> void

Parameters:

  • grammar (IR::Grammar)
  • starts: (Array[String], nil) (defaults to: nil) 


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) ⇒ Integer

RBS:

  • (Integer index) -> Integer

Parameters:

  • index (Integer)

Returns:

  • (Integer) 


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

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

#build ⇒ [ Array[core_set], transitions ]

RBS:

  • () -> [Array[core_set], transitions]

Returns:

  • ([ Array[core_set], transitions ]) 


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

#closure(seed) ⇒ core_set

RBS:

  • (core_set seed) -> core_set

Parameters:

  • seed (core_set)

Returns:

  • (core_set) 


94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 94

def closure(seed)
  items = seed.dup
  queue = seed.to_a
  cursor = 0
  while cursor < queue.length
    production_id, dot = queue.fetch(cursor)
    cursor += 1
    symbol = @grammar.symbol_by_id(rhs_for(production_id)[dot])
    next unless symbol&.nonterminal?

    @productions_by_lhs.fetch(symbol.id, []).each do |production|
      item = [production.id, 0].freeze
      queue << item if items.add?(item)
    end
  end
  items
end

#item_key(items) ⇒ Array[Integer]

RBS:

  • (core_set items) -> Array[Integer]

Parameters:

  • items (core_set)

Returns:

  • (Array[Integer]) 


113
114
115
116
117
 
# File 'lib/ibex/lalr/lr0_collection.rb', line 113

def item_key(items)
  items.map do |production_id, dot|
    ((production_id + @grammar.starts.length) * @item_key_stride) + dot
  end.sort
end

#lhs_for(production_id) ⇒ Integer

RBS:

  • (Integer production_id) -> Integer

Parameters:

  • production_id (Integer)

Returns:

  • (Integer) 


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) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


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) ⇒ Hash[Integer, core_set]

RBS:

  • (core_set items) -> Hash[Integer, core_set]

Parameters:

  • items (core_set)

Returns:

  • (Hash[Integer, core_set]) 


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