Class: Ibex::Analysis::Sets

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

Overview

Computes nullable, FIRST, and FOLLOW sets over Grammar IR using integer bitsets.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar) ⇒ Sets

Returns a new instance of Sets.

RBS:

  • (IR::Grammar grammar) -> void

Parameters:



19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/ibex/analysis/sets.rb', line 19

def initialize(grammar)
  @grammar = grammar
  @nullable_bits = 0
  @first_bits = Array.new(grammar.symbols.length, 0)
  @follow_bits = Array.new(grammar.symbols.length, 0)
  @first_dependencies = [] #: Array[Array[Integer]]
  @follow_dependencies = [] #: Array[Array[Integer]]
  grammar.terminals.each { |terminal| @first_bits[terminal.id] = bit(terminal.id) }
  compute_nullable
  compute_first
  compute_follow
end

Instance Attribute Details

#first_bits ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


8
9
10
 
# File 'lib/ibex/analysis/sets.rb', line 8

def first_bits
  @first_bits
end

#first_dependencies ⇒ Array[Array[Integer]] (readonly)

The index is a symbol id; each value lists the symbols that must be recomputed when the indexed symbol's set changes. These edges already point in the impact-propagation direction.

Returns:

  • (Array[Array[Integer]]) 


13
14
15
 
# File 'lib/ibex/analysis/sets.rb', line 13

def first_dependencies
  @first_dependencies
end

#follow_bits ⇒ Array[Integer] (readonly)

Signature:

  • Array[Integer]

Returns:

  • (Array[Integer]) 


9
10
11
 
# File 'lib/ibex/analysis/sets.rb', line 9

def follow_bits
  @follow_bits
end

#follow_dependencies ⇒ Array[Array[Integer]] (readonly)

Signature:

  • Array[Array[Integer]]

Returns:

  • (Array[Array[Integer]]) 


14
15
16
 
# File 'lib/ibex/analysis/sets.rb', line 14

def follow_dependencies
  @follow_dependencies
end

#nullable_bits ⇒ Integer (readonly)

Signature:

  • Integer

Returns:

  • (Integer) 


7
8
9
 
# File 'lib/ibex/analysis/sets.rb', line 7

def nullable_bits
  @nullable_bits
end

Instance Method Details

#bit(id) ⇒ Integer

RBS:

  • (Integer id) -> Integer

Parameters:

  • id (Integer)

Returns:

  • (Integer) 


204
205
206
 
# File 'lib/ibex/analysis/sets.rb', line 204

def bit(id)
  1 << id
end

#compute_first ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



100
101
102
103
104
105
106
107
108
109
110
111
 
# File 'lib/ibex/analysis/sets.rb', line 100

def compute_first
  dependencies = Array.new(@grammar.symbols.length) { [] }
  @grammar.productions.each do |production|
    production.rhs.each do |id|
      dependencies[id] << production.lhs
      break unless nullable_id?(id)
    end
  end

  @first_dependencies = freeze_dependencies(dependencies)
  propagate_bits(@first_bits, dependencies, @grammar.terminals.map(&:id))
end

#compute_follow ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/ibex/analysis/sets.rb', line 114

def compute_follow
  @grammar.starts.each do |name|
    start_definition = @grammar.symbol(name)
    raise Ibex::Error, "(analysis):1:1: unknown start symbol #{name}" unless start_definition

    @follow_bits[start_definition.id] |= bit(0)
  end
  dependencies = Array.new(@grammar.symbols.length) { [] }
  @grammar.productions.each { |production| initialize_follow(production, dependencies) }
  @follow_dependencies = freeze_dependencies(dependencies)
  seeds = @grammar.nonterminals.filter_map { |symbol| symbol.id unless @follow_bits[symbol.id].zero? }
  propagate_bits(@follow_bits, dependencies, seeds)
end

#compute_nullable ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/ibex/analysis/sets.rb', line 69

def compute_nullable
  dependencies, remaining, queue = nullable_worklist

  until queue.empty?
    id = queue.shift
    next if nullable_id?(id)

    @nullable_bits |= bit(id)
    dependencies[id].each do |production|
      remaining[production.id] -= 1
      queue << production.lhs if remaining[production.id].zero?
    end
  end
end

#definition_for(symbol) ⇒ IR::GrammarSymbol

RBS:

  • (Integer | String | Symbol | IR::GrammarSymbol symbol) -> IR::GrammarSymbol

Parameters:

Returns:



189
190
191
192
193
194
195
196
 
# File 'lib/ibex/analysis/sets.rb', line 189

def definition_for(symbol)
  return symbol if symbol.is_a?(IR::GrammarSymbol)

  definition = symbol.is_a?(Integer) ? @grammar.symbol_by_id(symbol) : @grammar.symbol(symbol.to_s)
  return definition if definition

  raise Ibex::Error, "(analysis):1:1: unknown symbol #{symbol}"
end

#first(symbol) ⇒ Array[String]

RBS:

  • (Integer | String | Symbol | IR::GrammarSymbol symbol) -> Array[String]

Parameters:

Returns:

  • (Array[String]) 


39
40
41
 
# File 'lib/ibex/analysis/sets.rb', line 39

def first(symbol)
  terminal_names(@first_bits.fetch(symbol_id(symbol)))
end

#first_of_sequence(symbol_ids) ⇒ Integer

RBS:

  • (Array[Integer] symbol_ids) -> Integer

Parameters:

  • symbol_ids (Array[Integer])

Returns:

  • (Integer) 


52
53
54
55
56
57
58
59
 
# File 'lib/ibex/analysis/sets.rb', line 52

def first_of_sequence(symbol_ids)
  bits = 0
  symbol_ids.each do |id|
    bits |= @first_bits.fetch(id)
    return bits unless nullable_id?(id)
  end
  bits
end

#follow(symbol) ⇒ Array[String]

RBS:

  • (Integer | String | Symbol | IR::GrammarSymbol symbol) -> Array[String]

Parameters:

Returns:

  • (Array[String]) 


44
45
46
47
48
49
 
# File 'lib/ibex/analysis/sets.rb', line 44

def follow(symbol)
  definition = definition_for(symbol)
  raise Ibex::Error, "(analysis):1:1: FOLLOW is only defined for nonterminals" unless definition.nonterminal?

  terminal_names(@follow_bits.fetch(definition.id))
end

#freeze_dependencies(dependencies) ⇒ Array[Array[Integer]]

RBS:

  • (Array[Array[Integer]] dependencies) -> Array[Array[Integer]]

Parameters:

  • dependencies (Array[Array[Integer]])

Returns:

  • (Array[Array[Integer]]) 


129
130
131
 
# File 'lib/ibex/analysis/sets.rb', line 129

def freeze_dependencies(dependencies)
  dependencies.map { |targets| targets.uniq.sort.freeze }.freeze
end

#initialize_follow(production, dependencies) ⇒ void

This method returns an undefined value.

RBS:

  • (IR::Production production, Array[Array[Integer]] dependencies) -> void

Parameters:



134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/ibex/analysis/sets.rb', line 134

def initialize_follow(production, dependencies)
  trailer = 0
  suffix_nullable = true
  production.rhs.reverse_each do |id|
    definition = required_symbol_by_id(id)
    if definition.nonterminal?
      @follow_bits[id] |= trailer
      dependencies[production.lhs] << id if suffix_nullable
      trailer = @first_bits[id] | (nullable_id?(id) ? trailer : 0)
      suffix_nullable &&= nullable_id?(id)
    else
      trailer = @first_bits[id]
      suffix_nullable = false
    end
  end
end

#nullable?(symbol) ⇒ Boolean

RBS:

  • (Integer | String | Symbol | IR::GrammarSymbol symbol) -> bool

Parameters:

Returns:

  • (Boolean) 


33
34
35
36
 
# File 'lib/ibex/analysis/sets.rb', line 33

def nullable?(symbol)
  id = symbol_id(symbol)
  @nullable_bits.anybits?(bit(id))
end

#nullable_id?(id) ⇒ Boolean

RBS:

  • (Integer id) -> bool

Parameters:

  • id (Integer)

Returns:

  • (Boolean) 


174
175
176
 
# File 'lib/ibex/analysis/sets.rb', line 174

def nullable_id?(id)
  @nullable_bits.anybits?(bit(id))
end

#nullable_worklist ⇒ [ Array[Array[IR::Production]], Array[Integer], Array[Integer] ]

RBS:

  • () -> [Array[Array[IR::Production]], Array[Integer], Array[Integer]]

Returns:



85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/ibex/analysis/sets.rb', line 85

def nullable_worklist
  dependencies = Array.new(@grammar.symbols.length) { [] }
  remaining = Array.new(@grammar.productions.length, 0)
  queue = [] #: Array[Integer]
  @grammar.productions.each do |production|
    next if production.rhs.any? { |id| required_symbol_by_id(id).terminal? }

    remaining[production.id] = production.rhs.length
    production.rhs.each { |id| dependencies[id] << production }
    queue << production.lhs if production.rhs.empty?
  end
  [dependencies, remaining, queue]
end

#propagate_bits(sets, dependencies, seeds) ⇒ void

This method returns an undefined value.

RBS:

  • (Array[Integer] sets, Array[Array[Integer]] dependencies, Array[Integer] seeds) -> void

Parameters:

  • sets (Array[Integer])
  • dependencies (Array[Array[Integer]])
  • seeds (Array[Integer]) 


152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/ibex/analysis/sets.rb', line 152

def propagate_bits(sets, dependencies, seeds)
  queue = seeds.dup
  queued = Array.new(@grammar.symbols.length, false)
  queue.each { |id| queued[id] = true }

  until queue.empty?
    source = queue.shift
    queued[source] = false
    dependencies[source].each do |target|
      combined = sets[target] | sets[source]
      next if combined == sets[target]

      sets[target] = combined
      next if queued[target]

      queued[target] = true
      queue << target
    end
  end
end

#required_symbol_by_id(id) ⇒ IR::GrammarSymbol

RBS:

  • (Integer id) -> IR::GrammarSymbol

Parameters:

  • id (Integer)

Returns:



199
200
201
 
# File 'lib/ibex/analysis/sets.rb', line 199

def required_symbol_by_id(id)
  @grammar.symbol_by_id(id) || raise(Ibex::Error, "(analysis):1:1: unknown symbol id #{id}")
end

#sequence_nullable?(symbol_ids) ⇒ Boolean

RBS:

  • (Array[Integer] symbol_ids) -> bool

Parameters:

  • symbol_ids (Array[Integer])

Returns:

  • (Boolean) 


62
63
64
 
# File 'lib/ibex/analysis/sets.rb', line 62

def sequence_nullable?(symbol_ids)
  symbol_ids.all? { |id| nullable_id?(id) }
end

#symbol_id(symbol) ⇒ Integer

RBS:

  • (Integer | String | Symbol | IR::GrammarSymbol symbol) -> Integer

Parameters:

Returns:

  • (Integer) 


184
185
186
 
# File 'lib/ibex/analysis/sets.rb', line 184

def symbol_id(symbol)
  definition_for(symbol).id
end

#terminal_names(bits) ⇒ Array[String]

RBS:

  • (Integer bits) -> Array[String]

Parameters:

  • bits (Integer)

Returns:

  • (Array[String]) 


179
180
181
 
# File 'lib/ibex/analysis/sets.rb', line 179

def terminal_names(bits)
  @grammar.terminals.filter_map { |terminal| terminal.name if bits.anybits?(bit(terminal.id)) }
end