Class: Ibex::Analysis::Sets

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

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.



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 ⇒ Object (readonly)

: Array



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

def first_bits
  @first_bits
end

#first_dependencies ⇒ Object (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.



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

def first_dependencies
  @first_dependencies
end

#follow_bits ⇒ Object (readonly)

: Array



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

def follow_bits
  @follow_bits
end

#follow_dependencies ⇒ Object (readonly)

: Array[Array[Integer]]



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

def follow_dependencies
  @follow_dependencies
end

#nullable_bits ⇒ Object (readonly)

: Integer



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

def nullable_bits
  @nullable_bits
end

Instance Method Details

#first(symbol) ⇒ Object 



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



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

Raises:



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

#nullable?(symbol) ⇒ Boolean

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

#sequence_nullable?(symbol_ids) ⇒ Boolean

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