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:



14
15
16
17
18
19
20
21
22
23
 
# File 'lib/ibex/analysis/sets.rb', line 14

def initialize(grammar)
  @grammar = grammar
  @nullable_bits = 0
  @first_bits = Array.new(grammar.symbols.length, 0)
  @follow_bits = Array.new(grammar.symbols.length, 0)
  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

#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

#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) 


190
191
192
 
# File 'lib/ibex/analysis/sets.rb', line 190

def bit(id)
  1 << id
end

#compute_first ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/ibex/analysis/sets.rb', line 93

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

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

#compute_follow ⇒ void

This method returns an undefined value.

RBS:

  • () -> void



106
107
108
109
110
111
112
113
114
115
116
117
 
# File 'lib/ibex/analysis/sets.rb', line 106

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) }
  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



62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/ibex/analysis/sets.rb', line 62

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:



175
176
177
178
179
180
181
182
 
# File 'lib/ibex/analysis/sets.rb', line 175

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]) 


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

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) 


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

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]) 


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

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

#initialize_follow(production, dependencies) ⇒ void

This method returns an undefined value.

RBS:

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

Parameters:



120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/ibex/analysis/sets.rb', line 120

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) 


26
27
28
29
 
# File 'lib/ibex/analysis/sets.rb', line 26

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) 


160
161
162
 
# File 'lib/ibex/analysis/sets.rb', line 160

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:



78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/ibex/analysis/sets.rb', line 78

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]) 


138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 
# File 'lib/ibex/analysis/sets.rb', line 138

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:



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

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) 


55
56
57
 
# File 'lib/ibex/analysis/sets.rb', line 55

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) 


170
171
172
 
# File 'lib/ibex/analysis/sets.rb', line 170

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]) 


165
166
167
 
# File 'lib/ibex/analysis/sets.rb', line 165

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