Class: Ibex::LALR::IELR::ItemLookaheads

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/lalr/ielr/item_lookaheads.rb,
sig/ibex/lalr/ielr/item_lookaheads.rbs

Overview

Lazily derives the lookahead of a kernel item from predecessor states and goto-follow sets. Memoisation is important: predecessor paths can share exponentially many suffixes in a real grammar.

Instance Method Summary collapse

Constructor Details

#initialize(grammar, goto_follows, kernel_cores, predecessors, start_states: nil) ⇒ ItemLookaheads

Returns a new instance of ItemLookaheads.

RBS:

  • (IR::Grammar grammar, GotoFollows goto_follows, Array[Array[item_core]] kernel_cores, Array[Array[Integer]] predecessors, ?start_states: Array[Integer]?) -> void

Parameters:

  • grammar (IR::Grammar)
  • goto_follows (GotoFollows)
  • kernel_cores (Array[Array[item_core]])
  • predecessors (Array[Array[Integer]])
  • start_states: (Array[Integer], nil) (defaults to: nil) 


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

def initialize(grammar, goto_follows, kernel_cores, predecessors, start_states: nil)
  @grammar = grammar
  @goto_follows = goto_follows
  @kernel_cores = kernel_cores
  @predecessors = predecessors
  @start_states = start_states || []
  @index = {}
  kernel_cores.each_with_index do |cores, state_id|
    cores.each_with_index { |core, kernel_index| @index[[state_id, core]] = kernel_index }
  end
  @memo = {}
end

Instance Method Details

#compute(state_id, kernel_index) ⇒ Integer

RBS:

  • (Integer state_id, Integer kernel_index) -> Integer

Parameters:

  • state_id (Integer)
  • kernel_index (Integer)

Returns:

  • (Integer) 


48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/ibex/lalr/ielr/item_lookaheads.rb', line 48

def compute(state_id, kernel_index)
  production_id, dot = @kernel_cores.fetch(state_id).fetch(kernel_index)
  return start_seed(production_id) if production_id.negative? && dot.zero?
  return start_seed(production_id) if production_id.negative? && dot.positive?
  return 0 if dot.zero?
  return goto_follows_for(state_id, production_id) if dot == 1

  @predecessors.fetch(state_id).reduce(0) do |bits, previous|
    previous_index = @index[[previous, [production_id, dot - 1]]]
    previous_index ? bits | fetch(previous, previous_index) : bits
  end
end

#fetch(state_id, kernel_index) ⇒ Integer

RBS:

  • (Integer state_id, Integer kernel_index) -> Integer

Parameters:

  • state_id (Integer)
  • kernel_index (Integer)

Returns:

  • (Integer) 


33
34
35
36
37
38
 
# File 'lib/ibex/lalr/ielr/item_lookaheads.rb', line 33

def fetch(state_id, kernel_index)
  key = [state_id, kernel_index]
  return @memo.fetch(key) if @memo.key?(key)

  @memo[key] = compute(state_id, kernel_index)
end

#goto_follows_for(state_id, production_id) ⇒ Integer

RBS:

  • (Integer state_id, Integer production_id) -> Integer

Parameters:

  • state_id (Integer)
  • production_id (Integer)

Returns:

  • (Integer) 


62
63
64
65
66
67
68
 
# File 'lib/ibex/lalr/ielr/item_lookaheads.rb', line 62

def goto_follows_for(state_id, production_id)
  lhs = @grammar.productions.fetch(production_id).lhs
  @predecessors.fetch(state_id).reduce(0) do |bits, previous|
    goto_id = @goto_follows.goto_for(previous, lhs)
    bits | (goto_id ? @goto_follows.goto_follows.fetch(goto_id) : 0)
  end
end

#size ⇒ Integer

RBS:

  • () -> Integer

Returns:

  • (Integer) 


41
42
43
 
# File 'lib/ibex/lalr/ielr/item_lookaheads.rb', line 41

def size
  @memo.length
end

#start_seed(production_id) ⇒ Integer

RBS:

  • (Integer production_id) -> Integer

Parameters:

  • production_id (Integer)

Returns:

  • (Integer) 


71
72
73
 
# File 'lib/ibex/lalr/ielr/item_lookaheads.rb', line 71

def start_seed(production_id)
  production_id.negative? ? 1 : 0
end