Class: Antelope::Generation::Recognizer

Inherits:
Object
  • Object
show all
Defined in:
lib/antelope/generation/recognizer.rb,
lib/antelope/generation/recognizer/rule.rb,
lib/antelope/generation/recognizer/state.rb

Overview

Recognizes all of the states in the grammar.

See Also:

Defined Under Namespace

Classes: Rule, State

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(grammar) ⇒ Recognizer

Initialize the recognizer.

Parameters:



33
34
35
36
37
 
# File 'lib/antelope/generation/recognizer.rb', line 33

def initialize(grammar)
  @grammar = grammar
  @states = Set.new
  @map = {}
end

Instance Attribute Details

#grammar ⇒ Ace::Grammar (readonly)

The grammar that the recognizer is running off of.

Returns:



28
29
30
 
# File 'lib/antelope/generation/recognizer.rb', line 28

def grammar
  @grammar
end

#start ⇒ State (readonly)

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

Returns:



23
24
25
 
# File 'lib/antelope/generation/recognizer.rb', line 23

def start
  @start
end

#states ⇒ Set<State> (readonly)

A list of all of the states in the grammar.

Returns:



17
18
19
 
# File 'lib/antelope/generation/recognizer.rb', line 17

def states
  @states
end

Instance Method Details

#call ⇒ void

This method returns an undefined value.

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

See Also:



48
49
50
51
52
53
54
 
# File 'lib/antelope/generation/recognizer.rb', line 48

def call
  @states = Set.new
  @start  = compute_initial_state
  redefine_state_ids
  redefine_rule_ids
  grammar.states = states
end

#compute_closure(state) ⇒ void

This method returns an undefined value.

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.



117
118
119
120
121
122
123
124
125
 
# File 'lib/antelope/generation/recognizer.rb', line 117

def compute_closure(state)
  fixed_point(state.rules) do
    state.rules.select { |_| _.active.nonterminal? }.each do |rule|
      grammar.productions[rule.active.name].each do |prod|
        state << Rule.new(prod, 0)
      end
    end
  end
end

#compute_initial_state ⇒ State

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

Returns:



61
62
63
64
65
 
# File 'lib/antelope/generation/recognizer.rb', line 61

def compute_initial_state
  production = grammar.productions[:$start][0]
  rule = Rule.new(production, 0)
  compute_whole_state(rule)
end

#compute_states ⇒ void

This method returns an undefined value.

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.

See Also:



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/antelope/generation/recognizer.rb', line 90

def compute_states
  fixed_point(states) do
    states.dup.each do |state|
      state.rules.each do |rule|
        next unless rule.succ?
        transitional = find_state_for(rule.succ) do |succ|
          ns = State.new << succ
          compute_closure(ns)
          @map[succ] = ns
        end

        if state.transitions[rule.active.name]
          state.transitions[rule.active.name].merge! transitional
        else
          states << transitional
          state.transitions[rule.active.name] = transitional
        end
      end
    end
  end
end

#compute_whole_state(rule) ⇒ State

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.

Parameters:

  • rule (Rule) —

    the initial rule.

Returns:



74
75
76
77
78
79
80
81
 
# File 'lib/antelope/generation/recognizer.rb', line 74

def compute_whole_state(rule)
  state = State.new
  state << rule
  compute_closure(state)
  states << state
  compute_states
  state
end

#find_state_for(rule) {|rule| ... } ⇒ State (private)

Find a state that include a specific rule, or yields the rule.

Parameters:

Yields:

  • (rule)

Returns:



134
135
136
137
 
# File 'lib/antelope/generation/recognizer.rb', line 134

def find_state_for(rule, &block)
  #states.find { |state| state.include?(rule) } or yield(rule)
  @map.fetch(rule) { block.call(rule) }
end

#fixed_point(enum) { ... } ⇒ void (private)

This method returns an undefined value.

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.

Parameters:

  • enum (Enumerable)

Yields:

  • for every iteration. Guarenteed to do so at least once.



173
174
175
176
177
178
179
180
181
 
# File 'lib/antelope/generation/recognizer.rb', line 173

def fixed_point(enum)
  added = 1

  until added.zero?
    added = enum.size
    yield
    added = enum.size - added
  end
end

#redefine_rule_ids ⇒ void (private)

This method returns an undefined value.

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.



153
154
155
156
157
158
159
160
161
162
 
# File 'lib/antelope/generation/recognizer.rb', line 153

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 ⇒ void (private)

This method returns an undefined value.

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



142
143
144
145
146
 
# File 'lib/antelope/generation/recognizer.rb', line 142

def redefine_state_ids
  states.each_with_index do |state, i|
    state.id = i
  end
end