[Tutor] Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined

[Frank Chang]

  Good morning, I am using Python 2.7.1 on Windows XP Service Pack 3. Here
is the program where the Python interpreter complains about NameError:
global name 'levenshtein_automata' is not defined.

     The python 2,7.1 error message is:

Traceback (most recent call last):
  File "automata_test.py", line 174, in <module>
    length = len(list(testdfa.find_all_matches('food', 1, m)))
  File "automata_test.py", line 145, in find_all_matches
    lev = levenshtein_automata(word, k).to_dfa()
NameError: global name 'levenshtein_automata' is not defined

Here is the program. I have marked lines 174, 145 and 125.

import bisect
import random
class NFA(object):
 EPSILON = object()
 ANY = object()
 def __init__(self, start_state):
         self.transitions = {}
  self.final_states = set()
  self._start_state = start_state
 @property
 def start_state(self):
    return frozenset(self._expand(set([self._start_state])))
 def add_transition(self, src, input, dest):
    self.transitions.setdefault(src, {}).setdefault(input, set()).add(dest)

 def add_final_state(self, state):
    self.final_states.add(state)
 def is_final(self, states):
    return self.final_states.intersection(states)
 def _expand(self, states):
    frontier = set(states)
    while frontier:
       state = frontier.pop()
       new_states = self.transitions.get(state, {}).get(NFA.EPSILON,
set()).difference(states)
              frontier.update(new_states)
       states.update(new_states)
    return states
 def next_state(self, states, input):
    dest_states = set()
    for state in states:
      state_transitions = self.transitions.get(state, {})
      dest_states.update(state_transitions.get(input, []))
      dest_states.update(state_transitions.get(NFA.ANY, []))
    return frozenset(self._expand(dest_states))
 def get_inputs(self, states):
    inputs = set()
    for state in states:
       inputs.update(self.transitions.get(state, {}).keys())
    return inputs
 def to_dfa(self):
   dfa = DFA(self.start_state)
   frontier = [self.start_state]
   seen = set()
   while frontier:
  current = frontier.pop()
  inputs = self.get_inputs(current)
  for input in inputs:
    if input == NFA.EPSILON: continue
   new_state = self.next_state(current, input)
   if new_state not in seen:
  frontier.append(new_state)
  seen.add(new_state)
  if self.is_final(new_state):
    dfa.add_final_state(new_state)
   if input == NFA.ANY:
  dfa.set_default_transition(current, new_state)
   else:
  dfa.add_transition(current, input, new_state)
   return dfa


class DFA(object):
    def __init__(self, start_state):
    self.start_state = start_state
    self.transitions = {}
    self.defaults = {}
    self.final_states = set()
    def add_transition(self, src, input, dest):
    self.transitions.setdefault(src, {})[input] = dest
    def set_default_transition(self, src, dest):
    self.defaults[src] = dest
    def add_final_state(self, state):
    self.final_states.add(state)
    def is_final(self, state):
    return state in self.final_states
    def next_state(self, src, input):
    state_transitions = self.transitions.get(src, {})
    return state_transitions.get(input, self.defaults.get(src, None))
    def next_valid_string(self, input):
    state = self.start_state
    stack = []
          # Evaluate the DFA as far as possible
    print state
    for i, x in enumerate(input):
   print "%s" % input
   print 'e'
   stack.append((input[:i], state, x))
   state = self.next_state(state, x)
   if not state: break
    else:
   stack.append((input[:i+1], state, None))

    if self.is_final(state):
             # Input word is already valid
       return input
          # Perform a 'wall following' search for the lexicographically
smallest
          # accepting state.
    while stack:
      path, state, x = stack.pop()
      x = self.find_next_edge(state, x)
      #print 'x'
      if x:
         path += x
         state = self.next_state(state, x)
      if self.is_final(state):
    print 'p'
    return path
      stack.append((path, state, None))
    print 'v'
    return None
    def find_next_edge(self, s, x):
     if x is None:
       x = '\0' # u'\0'
     else:
       x = chr(ord(x) + 1)
     state_transitions = self.transitions.get(s, {})
     if x in state_transitions or s in self.defaults:
    return x
     labels = sorted(state_transitions.keys())
     pos = bisect.bisect_left(labels, x)
     if pos < len(labels):
    print 'n'
    return labels[pos]
     return None
def levenshtein_automata(self, term, k):    ##### line 125 ########'
     nfa = NFA((0, 0))
     for i, c in enumerate(term):
        for e in range(k + 1):
                 # Correct character
     nfa.add_transition((i, e), c, (i + 1, e))
     if e < k:
                   # Deletion
       nfa.add_transition((i, e), NFA.ANY, (i, e + 1))
                   # Insertion
       nfa.add_transition((i, e), NFA.EPSILON, (i + 1, e + 1))
                   # Substitution
       nfa.add_transition((i, e), NFA.ANY, (i + 1, e + 1))
     for e in range(k + 1):
       if e < k:
          nfa.add_transition((len(term), e), NFA.ANY, (len(term), e + 1))

       nfa.add_final_state((len(term), e))
     return nfa
def find_all_matches(self, word, k, lookup_func):
    lev = levenshtein_automata(word, k).to_dfa()  ######### line 145
##########
    match = lev.next_valid_string('\0')
    while match:
        next = lookup_func(match)
        if not next:
           return
        if match == next:
          yield match
          next1 = next1 + '\0'
       match = lev.next_valid_string(next1)

class Matcher(object):
  def __init__(self, l):
    self.l = l
    self.probes = 0
  def __call__(self, w):
   self.probes += 1
 pos = bisect.bisect_left(self.l, w)
 if pos < len(self.l):
  return self.l[pos]
 else:
     return None

words = [x.strip().lower() for x in open('F:/shedskin/database.txt')]
words.sort()

m = Matcher(words)
testdfa = DFA(1)
length = len(list(testdfa.find_all_matches('food', 1, m))) ######## line 174
##########


   I cannot understand why the Python 2.7.1 interpreter complains about
NameError: global name 'levenshtein_automata' is not defined. On line 125 ,
I try to define levenshtein_automata(self,term,k) as a method of the class
DFA. I am new  to Python 2.7.1. Could someone help me fix this NameError
error message. Thank you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20101227/3943c996/attachment-0001.html>