Class: Ibex::Verify::ReferenceCollection

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

Overview

Independently derives canonical LR(1) and LR(0) item collections.

Defined Under Namespace

Classes: Collection

Instance Method Summary collapse

Constructor Details

#initialize(grammar, max_states: 100_000, max_items: 1_000_000) ⇒ ReferenceCollection

Returns a new instance of ReferenceCollection.

RBS:

  • (IR::Grammar grammar, ?max_states: Integer, ?max_items: Integer) -> void

Parameters:

  • grammar (IR::Grammar)
  • max_states: (Integer) (defaults to: 100_000)
  • max_items: (Integer) (defaults to: 1_000_000) 


24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/ibex/verify/reference_collection.rb', line 24

def initialize(grammar, max_states: 100_000, max_items: 1_000_000)
  raise ArgumentError, "max_states must be positive" unless max_states.positive?
  raise ArgumentError, "max_items must be positive" unless max_items.positive?

  @grammar = grammar
  @max_states = max_states
  @max_items = max_items
  @sets = Analysis::Sets.new(grammar)
  @productions = grammar.productions.group_by(&:lhs)
  @item_count = 0
end

Instance Method Details

#account_item ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



142
143
144
145
146
147
148
149
150
 
# File 'lib/ibex/verify/reference_collection.rb', line 142

def 
  if @item_count >= @max_items
    raise BudgetExceeded.new(
      "(verify):1:1: reference collection exceeds #{@max_items} items", bounds: bounds
    )
  end

  @item_count += 1
end

#add_item(items, queue, item) ⇒ void

This method returns an undefined value.

RBS:

  • (Set[Array[Integer]] items, Array[Array[Integer]] queue, Array[Integer] item) -> void

Parameters:

  • items (Set[Array[Integer]])
  • queue (Array[Array[Integer]])
  • item (Array[Integer]) 


133
134
135
136
137
138
139
 
# File 'lib/ibex/verify/reference_collection.rb', line 133

def add_item(items, queue, item)
  return if items.include?(item)

  
  items << item
  queue << item
end

#bounds ⇒ Hash[Symbol, Integer]

RBS:

  • () -> Hash[Symbol, Integer]

Returns:

  • (Hash[Symbol, Integer]) 


185
186
187
 
# File 'lib/ibex/verify/reference_collection.rb', line 185

def bounds
  { max_states: @max_states, max_items: @max_items }
end

#build(kind) ⇒ Collection

RBS:

  • (Symbol kind) -> Collection

Parameters:

  • kind (Symbol)

Returns:



37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/ibex/verify/reference_collection.rb', line 37

def build(kind)
  raise ArgumentError, "kind must be :lr0 or :lr1" unless %i[lr0 lr1].include?(kind)

  @item_count = 0
  seeds = @grammar.starts.map.with_index do |name, index|
    raise Ibex::Error, "(verify):1:1: missing start symbol #{name}" unless @grammar.symbol(name)

    item = kind == :lr1 ? [-index - 1, 0, eof_id] : [-index - 1, 0]
    
    closure(Set[item], kind)
  end
  collection(seeds, kind)
end

#closure(seed, kind) ⇒ Set[Array[Integer]]

RBS:

  • (Set[Array[Integer]] seed, Symbol kind) -> Set[Array[Integer]]

Parameters:

  • seed (Set[Array[Integer]])
  • kind (Symbol)

Returns:

  • (Set[Array[Integer]]) 


89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/ibex/verify/reference_collection.rb', line 89

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

    productions = @productions.fetch(symbol.id) do
      [] #: Array[IR::Production]
    end
    productions.each do |production|
      if kind == :lr1
        closure_lookaheads(production_id, dot, lookahead).each do |token|
          add_item(items, queue, [production.id, 0, token])
        end
      else
        add_item(items, queue, [production.id, 0])
      end
    end
  end
  items
end

#closure_lookaheads(production_id, dot, inherited) ⇒ Array[Integer]

RBS:

  • (Integer production_id, Integer dot, Integer? inherited) -> Array[Integer]

Parameters:

  • production_id (Integer)
  • dot (Integer)
  • inherited (Integer, nil)

Returns:

  • (Array[Integer]) 


158
159
160
161
162
163
 
# File 'lib/ibex/verify/reference_collection.rb', line 158

def closure_lookaheads(production_id, dot, inherited)
  suffix = rhs_for(production_id).drop(dot + 1)
  bits = @sets.first_of_sequence(suffix)
  bits |= (1 << inherited) if inherited && @sets.sequence_nullable?(suffix)
  @grammar.terminals.filter_map { |terminal| terminal.id if bits.anybits?(1 << terminal.id) }
end

#collection(seeds, kind) ⇒ Collection

RBS:

  • (Array[Set[Array[Integer]]] seeds, Symbol kind) -> Collection

Parameters:

  • seeds (Array[Set[Array[Integer]]])
  • kind (Symbol)

Returns:



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/ibex/verify/reference_collection.rb', line 54

def collection(seeds, kind)
  states = [] #: Array[Set[Array[Integer]]]
  transitions = [] #: Array[Hash[Integer, Integer]]
  indexes = {} #: Hash[Array[Array[Integer]], Integer]
  seeds.each { |seed| insert_state(states, indexes, seed) }
  cursor = 0
  while cursor < states.length
    transitions[cursor] = {}
    next_symbols(states.fetch(cursor)).each do |symbol_id|
      target = go_to(states.fetch(cursor), symbol_id, kind)
      target_id = insert_state(states, indexes, target)
      transitions.fetch(cursor)[symbol_id] = target_id
    end
    cursor += 1
  end
  Collection.new(states: states.freeze, transitions: transitions.freeze).freeze
end

#eof_id ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


179
180
181
182
 
# File 'lib/ibex/verify/reference_collection.rb', line 179

def eof_id
  symbol = @grammar.symbol("$eof")
  symbol&.id || raise(Ibex::Error, "(verify):1:1: grammar has no $eof terminal")
end

#go_to(state, symbol_id, kind) ⇒ Set[Array[Integer]]

RBS:

  • (Set[Array[Integer]] state, Integer symbol_id, Symbol kind) -> Set[Array[Integer]]

Parameters:

  • state (Set[Array[Integer]])
  • symbol_id (Integer)
  • kind (Symbol)

Returns:

  • (Set[Array[Integer]]) 


120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/ibex/verify/reference_collection.rb', line 120

def go_to(state, symbol_id, kind)
  moved = state.each_with_object(Set.new) do |item, result|
    production_id = item.fetch(0)
    dot = item.fetch(1)
    lookahead = item[2]
    next unless rhs_for(production_id)[dot] == symbol_id

    result << (kind == :lr1 ? [production_id, dot + 1, lookahead] : [production_id, dot + 1])
  end
  closure(moved, kind)
end

#insert_state(states, indexes, state) ⇒ Integer

RBS:

  • (Array[Set[Array[Integer]]] states, Hash[Array[Array[Integer]], Integer] indexes, Set[Array[Integer]] state) -> Integer

Parameters:

  • states (Array[Set[Array[Integer]]])
  • indexes (Hash[Array[Array[Integer]], Integer])
  • state (Set[Array[Integer]])

Returns:

  • (Integer) 


74
75
76
77
78
79
80
81
82
83
84
85
86
 
# File 'lib/ibex/verify/reference_collection.rb', line 74

def insert_state(states, indexes, state)
  key = state.to_a.sort
  existing = indexes[key]
  return existing if existing
  if states.length >= @max_states
    raise BudgetExceeded.new(
      "(verify):1:1: reference collection exceeds #{@max_states} states", bounds: bounds
    )
  end

  states << state.freeze
  indexes[key] = states.length - 1
end

#next_symbols(state) ⇒ Array[Integer]

RBS:

  • (Set[Array[Integer]] state) -> Array[Integer]

Parameters:

  • state (Set[Array[Integer]])

Returns:

  • (Array[Integer]) 


153
154
155
 
# File 'lib/ibex/verify/reference_collection.rb', line 153

def next_symbols(state)
  state.filter_map { |item| rhs_for(item.fetch(0))[item.fetch(1)] }.uniq.sort
end

#rhs_for(production_id) ⇒ Array[Integer]

RBS:

  • (Integer production_id) -> Array[Integer]

Parameters:

  • production_id (Integer)

Returns:

  • (Array[Integer]) 


166
167
168
169
170
 
# File 'lib/ibex/verify/reference_collection.rb', line 166

def rhs_for(production_id)
  return [start_symbol(production_id).id] if production_id.negative?

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

#start_symbol(production_id) ⇒ IR::GrammarSymbol

RBS:

  • (Integer production_id) -> IR::GrammarSymbol

Parameters:

  • production_id (Integer)

Returns:



173
174
175
176
 
# File 'lib/ibex/verify/reference_collection.rb', line 173

def start_symbol(production_id)
  name = @grammar.starts.fetch(-production_id - 1)
  @grammar.symbol(name) || raise(Ibex::Error, "(verify):1:1: missing start symbol #{name}")
end