Class: Ibex::LALR::DirectLookaheads

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/lalr/direct_lookaheads.rb

Overview

Builds an LR(0) collection and propagates LALR(1) lookaheads directly over item occurrences. Canonical LR(1) states are never materialized.

Constant Summary collapse

AUGMENTED_PRODUCTION =

: Integer

-1 #: Integer

Instance Method Summary collapse

Constructor Details

#initialize(grammar, sets) ⇒ DirectLookaheads

Returns a new instance of DirectLookaheads.



27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 27

def initialize(grammar, sets)
  @grammar = grammar
  @sets = sets
  @productions_by_lhs = grammar.productions.group_by(&:lhs)
  start = grammar.symbol(grammar.start) || raise(Ibex::Error, "missing start symbol")
  @augmented_rhs = [start.id].freeze
  @production_rhs = grammar.productions.map(&:rhs).freeze
  @augmented_item_cores = item_cores_for(AUGMENTED_PRODUCTION, @augmented_rhs.length)
  @production_item_cores = grammar.productions.map do |production|
    item_cores_for(production.id, production.rhs.length)
  end.freeze
  @terminal_ids = grammar.terminals.map(&:id).freeze
  @terminal_masks = @terminal_ids.map { |id| 1 << id }.freeze
end

Instance Method Details

#build ⇒ Object 



43
44
45
46
47
48
49
50
 
# File 'lib/ibex/lalr/direct_lookaheads.rb', line 43

def build
  states, transitions = lr0_collection
  lookaheads = empty_lookaheads(states)
  propagation = propagation_graph(states, transitions, lookaheads)
  lookaheads.fetch(0).fetch(item_core(AUGMENTED_PRODUCTION, 0)) << 0
  propagate(lookaheads, propagation)
  [lookaheads, transitions]
end