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:



31
32
33
34
35
 
# File 'lib/antelope/generation/recognizer.rb', line 31

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

Instance Attribute Details

#grammar ⇒ Grammar (readonly)

The grammar that the recognizer is running off of.

Returns:



26
27
28
 
# File 'lib/antelope/generation/recognizer.rb', line 26

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:



21
22
23
 
# File 'lib/antelope/generation/recognizer.rb', line 21

def start
  @start
end

#states ⇒ Set<State> (readonly)

A list of all of the states in the grammar.

Returns:



15
16
17
 
# File 'lib/antelope/generation/recognizer.rb', line 15

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:



46
47
48
49
50
51
52
 
# 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) ⇒ 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.



101
102
103
104
105
106
107
108
109
 
# 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) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# 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 ⇒ 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:



59
60
61
62
63
 
# 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 ⇒ 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:



88
89
90
91
92
93
94
 
# 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) ⇒ 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:



72
73
74
75
76
77
78
79
 
# 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

#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.



166
167
168
169
170
171
172
173
174
 
# 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 ⇒ 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.



146
147
148
149
150
151
152
153
154
155
 
# 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 ⇒ void (private)

This method returns an undefined value.

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



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

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