class Antelope::Generation::Constructor

Constructs the lookahead sets for all of the rules in the grammar.

Attributes

grammar[R]

The grammar.

@return [Grammar::Grammar]

productions[R]

The augmented productions generated by the constructor.

@return [Set<Grammar::Production>]

Public Class Methods

new(grammar) click to toggle source

Initialize.

@param grammar [Grammar::Grammar] the grammar.

# File lib/antelope/generation/constructor.rb, line 32
def initialize(grammar)
  @productions = Set.new
  @grammar = grammar
  super()
end

Public Instance Methods

augment_rules(state) click to toggle source

Augments every final rule. For every rule in the current state that has a position of zero, it follows the rule through the DFA until the ending state; it then modifies the ending state’s lookahead set to be the FOLLOW set of the nonterminal it reduces to.

@param state [Recognizer::State] @return [void] @see Follow#follow

# File lib/antelope/generation/constructor.rb, line 99
def augment_rules(state)
  state.rules.each do |rule|
    next unless rule.position.zero?
    current_state = state

    label = rule.left.dup
    label.from = state
    label.to = state.transitions[label.name]

    rule.right.each do |part|
      transition = current_state.transitions[part.name]
      current_state = transition
    end

    final = current_state.rule_for(rule)

    final.lookahead = Set.new unless final.lookahead
    final.lookahead.merge follow(label)
  end
end
augment_state(state) click to toggle source

Augments the given state. On every rule within that state that has a position of zero, it follows the rule throughout the DFA until the end; it marks every nonterminal it encounters with the transitions it took on that nonterminal.

@param state [Recognizer::State] the state to augment. @return [void]

# File lib/antelope/generation/constructor.rb, line 60
def augment_state(state)
  state.rules.select { |x| x.position.zero? }.each do |rule|
    production = rule.production.clone
    production.items = []

    current_state = state
    old_state = state

    production.label.from = state
    production.label.to   = state.transitions[rule.left.name]

    rule.right.each_with_index do |part, pos|
      transition = current_state.transitions[part.name]
      new_item = part.dup

      if part.nonterminal?
        new_item.from = current_state
        new_item.to   = transition
      end

      production.items << new_item

      old_state = current_state
      current_state = transition
    end

    productions << production
  end
end
call() click to toggle source

Performs the construction. First, it goes through every state and augments the state. It then goes through every rule and augments it.

@return [void] @see augment_state @see augment_rule

# File lib/antelope/generation/constructor.rb, line 45
def call
  grammar.states.each do |state|
    augment_state(state)
  end.each do |state|
    augment_rules(state)
  end
end

Private Instance Methods

incorrect_argument!(arg, *types) click to toggle source
# File lib/antelope/generation/constructor.rb, line 122
def incorrect_argument!(arg, *types)
  raise ArgumentError, "Expected one of #{types.join(', ')}, got #{arg.class}"
end