class Antelope::Generation::Recognizer

Recognizes all of the states in the grammar.

@see redjazz96.tumblr.com/post/88446352960

Attributes

grammar[R]

The grammar that the recognizer is running off of.

@return [Grammar]

start[R]

The initial state. This is the state that is constructed from the rule with the left-hand side being ‘$start`.

@return [State]

states[R]

A list of all of the states in the grammar.

@return [Set<State>]

Public Class Methods

new(grammar) click to toggle source

Initialize the recognizer.

@param grammar [Grammar]

# File lib/antelope/generation/recognizer.rb, line 31
def initialize(grammar)
  @grammar = grammar
  @states = Set.new
  @map = {}
end

Public Instance Methods

call() click to toggle source

Runs the recognizer. After all states have been created, it resets the state ids into a more friendly form (they were originally hexadecimal, see {State#initialize}), and then resets the rule ids in each state into a more friendly form (they were also originally hexadecmial, see {Rule#initialize} ).

@see compute_initial_state @return [void]

# File lib/antelope/generation/recognizer.rb, line 46
def call
  @states = Set.new
  @start  = compute_initial_state
  redefine_state_ids
  redefine_rule_ids
  grammar.states = states
end
compute_closure(state) click to toggle source

Given a state, it does a fixed point iteration on the rules of the state that have an active nonterminal, and add the corresponding production rules to the state.

@return [void]

# File lib/antelope/generation/recognizer.rb, line 101
def compute_closure(state)
  fixed_point(state.rules) do
    state.rules.select { |r| r.active.nonterminal? }.each do |rule|
      grammar.productions[rule.active.name].each do |prod|
        state << Rule.new(prod, 0)
      end
    end
  end
end
compute_gotos(state) click to toggle source
# File lib/antelope/generation/recognizer.rb, line 111
def compute_gotos(state)
  actives = state.rules.map(&:active).select(&:name)

  actives.each do |active|
    next if state.transitions[active.name]
    rules = state.rules
            .select { |r| r.active == active && r.succ? }
            .map(&:succ).to_set
    s = states.find { |st| rules.subset? st.rules } || begin
      s = State.new << rules
      compute_closure(s)
      states << s
      s
    end

    state.transitions[active.name] = s
  end
end
compute_initial_state() click to toggle source

Computes the initial state. Starting with the default production of ‘$start`, it then generates the whole state and then the spawned states from it.

@return [State]

# File lib/antelope/generation/recognizer.rb, line 59
def compute_initial_state
  production = grammar.productions[:$start][0]
  rule = Rule.new(production, 0)
  compute_whole_state(rule)
end
compute_states() click to toggle source

Computes all states. Uses a fix point iteration to determine when no states have been added. Loops through every state and every rule, looking for rules that have an active nonterminal and computing the closure for said rule.

@return [void] @see compute_closure

# File lib/antelope/generation/recognizer.rb, line 88
def compute_states
  fixed_point(states) do
    states.dup.each do |state|
      compute_gotos(state)
    end
  end
end
compute_whole_state(rule) click to toggle source

Computes the entire initial state from the initial rule. It starts with a blank state, adds the initial rule to it, and then generates the closure for that state; it then computes the rest of the states in the grammar.

@param rule [Rule] the initial rule. @return [State]

# File lib/antelope/generation/recognizer.rb, line 72
def compute_whole_state(rule)
  state = State.new
  state << rule
  compute_closure(state)
  states << state
  compute_states
  state
end

Private Instance Methods

fixed_point(enum) { || ... } click to toggle source

Begins a fixed point iteration on the given enumerable. It initializes the added elements to one; then, while the number of added elements is not zero, it yields and checks for added elements.

@param enum [Enumerable] @yield for every iteration. Guarenteed to do so at least

once.

@return [void]

# File lib/antelope/generation/recognizer.rb, line 166
def fixed_point(enum)
  added = 1

  until added.zero?
    added = enum.size
    yield
    added = enum.size - added
  end
end
redefine_rule_ids() click to toggle source

Redefines all of the rule ids to make them more friendly. Every rule in every state is given a unique ID, reguardless if the rules are equivalent.

@return [void]

# File lib/antelope/generation/recognizer.rb, line 146
def redefine_rule_ids
  start = 0

  states.each do |state|
    state.rules.each do |rule|
      rule.id = start
      start  += 1
    end
  end
end
redefine_state_ids() click to toggle source

Changes the IDs of the states into a more friendly format.

@return [void]

# File lib/antelope/generation/recognizer.rb, line 135
def redefine_state_ids
  states.each_with_index do |state, i|
    state.id = i
  end
end