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.



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

: Array



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

def first_bits
  @first_bits
end

#follow_bits ⇒ Object (readonly)

: Array



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

def follow_bits
  @follow_bits
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 



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



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

Raises:



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

#nullable?(symbol) ⇒ Boolean

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

#sequence_nullable?(symbol_ids) ⇒ Boolean

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