Re: [Tutor] python 2.7.1
On 20/08/12 05:47, john wrote: print"hello world"#this is just something to say >>> /Users/jonathan/Documents/hello.py You don;t run Python scripts from the python prompt. You only type Python co0mmands there. You could import your file which wiull run it but the effect is slightly different. Its better to run scripts from the OS prompt $ python /Users/jonathan/Documents/hello.py -- Alan G Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] python 2.7.1
john wrote: > print "hello world" #this is just something to say /Users/jonathan/Documents/hello.py > File "", line 1 > /Users/jonathan/Documents/hello.py > ^ > SyntaxError: invalid syntax > > what am i doing wrong? The >>> prompt indicates that you have already started the interactive interpreter by typing $ python This is a great way to test Python statements interactively -- type and explore Python's response. However, to run a script you have to provide the script name on the commandline $ python /Users/jonathan/Documents/hello.py ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] python 2.7.1
On 08/20/2012 12:47 AM, john wrote: > print "hello world" #this is just something to say > > > > > /Users/jonathan/Documents/hello.py > File "", line 1 > /Users/jonathan/Documents/hello.py > ^ > SyntaxError: invalid syntax > > what am i doing wrong? > > > it would help if you showed the actual content of hello.py. Looks to me like the first line looks like: /Users/jonathan/Documents/hello.py Comment that out, and see what happens. -- DaveA ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] python 2.7.1
print "hello world" #this is just something to say >>> /Users/jonathan/Documents/hello.py File "", line 1 /Users/jonathan/Documents/hello.py ^ SyntaxError: invalid syntax what am i doing wrong? ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter
I wanted to thank Steven D'Aprano and Allan Gauld for solving my Python 2.7.1 interpreter question in Tutor Digest Vol. 82 Issue 121. Thank you for yor help. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter question
Frank Chang wrote:
When I use the Python 2.7.1 interpreter I get the following traceback
:
F:\shedskin\shedskin-0.7>python automata_test2.py
Traceback (most recent call last):
File "automata_test2.py", line 23, in
list(automata.find_all_matches('nice', 1, m))
AttributeError: 'module' object has no attribute 'find_all_matches'
Could anyone help me fix this error? I am new to python. Thank you.
This error tells you that the module "automata.py" does not have a
global-level object called "find_all_matches".
If you look at the module, you will see it does not have a global-level
object called "find_all_matches", exactly as Python tells you. To fix
this, you need to either:
(1) Give the automata module a function "find_all_matches" that does
what you expect it to do; or
(2) Change automata_test2 to create a DFA instance, then call the
find_all_matches method in that instance. Something like:
instance = automata.DFA(start_state)
instance.find_all_matches("word", k, lookup_func)
--
Steven
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter question
"Frank Chang" wrote
automata.py. The pastebin url for automata.py is:
http://pastebin.com/embed_iframe.php?i=J9MRPibX";
style="border:none;width:100%">
list(automata.find_all_matches('nice', 1, m))
AttributeError: 'module' object has no attribute 'find_all_matches'
find_all_matches() is a method of a class. Therefore you need to
call it via an instance of that class. You need to instantiate the
class using the module name but after that the object will be
local:
myObj = module.myclass()
myObj.myMethod()
HTH,
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
[Tutor] Python 2.7.1 interpreter question
I separated my test program into two python files. The first one is
automata.py. The pastebin url for automata.py is:
http://pastebin.com/embed_iframe.php?i=J9MRPibX";
style="border:none;width:100%">
The second file is automata_test2.py. It imports automata.py. The
pastebin url for automata_test2.py is:
http://pastebin.com/embed_iframe.php?i=A44d2EvV";
style="border:none;width:100%">.
When I use the Python 2.7.1 interpreter I get the following traceback
:
F:\shedskin\shedskin-0.7>python automata_test2.py
Traceback (most recent call last):
File "automata_test2.py", line 23, in
list(automata.find_all_matches('nice', 1, m))
AttributeError: 'module' object has no attribute 'find_all_matches'
Could anyone help me fix this error? I am new to python. Thank you.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
Alan Gauld wrote: "Frank Chang" wrote I apologize for the cut and paste mangling. Is there a better method than copy-pasting for including 20 or more lines of python source code in the tutor posts? Thank you. Long listings are usually better in pastebin - where the indentation is clear and we get syntax colouring too. It all makes them more readable :-) Even better is to spend the time to work out the smallest amount of code that exhibits the problem. The code you post must be runnable, it must actually demonstrate the problem -- it is surprising how many people post "broken" code that actually works, or worse, code that fails in some completely different way -- and lastly, and most importantly, it should be as small as possible. Doing so shows respect to those you are asking to look at the code, AND maximizes the number of people willing to spend the time answering your question: instead of looking at 200 lines and seven functions, they only need to look at one function and sixteen lines of code. (Or whatever it takes to reproduce the problem.) Even more important, while trying to reproduce the problem in the minimum code possible, you may very well solve the problem yourself. I can't tell you how many times I've gone to write up a request for help, but while refactoring my code I've discovered the mistake and didn't need to post my question. -- Steven ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
"Frank Chang" wrote I apologize for the cut and paste mangling. Is there a better method than copy-pasting for including 20 or more lines of python source code in the tutor posts? Thank you. Long listings are usually better in pastebin - where the indentation is clear and we get syntax colouring too. It all makes them more readable :-) Then just post the url to the pastebin on your mail. HTH, -- Alan Gauld Author of the Learn to Program web site http://www.alan-g.me.uk/ ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
I asked the Shedskin developers about this issue and they are currently
adding support for __call__ . They recommend renaming the class Matcher
__call__ method ,for example as next, and then explicitly call it on line
148 as
lookup_func.next(match).
I followed their suggestion and the Shedskin 0.7 Python to C++ compiler
does not complain about the unbound identifier 'lookup_func' anymore.
I apologize for the cut and paste mangling. Is there a better method
than copy-pasting for including 20 or more lines of python source code in
the tutor posts? Thank you.
def find_all_matches(self, word, k, lookup_func):
lev = self.levenshtein_automata(word, k).to_dfa()
match = lev.next_valid_string('\0')
while match:
follow = lookup_func.test(match) ### line 148 ###
if not follow:
return
if match == follow:
yield match
follow = follow + '\0'
match = lev.next_valid_string(follow)
class Matcher(object):
def __init__(self, l):
self.l = l
self.probes = 0
def test(self, w):
self.probes += 1
pos = bisect.bisect_left(self.l, w)
if pos < len(self.l):
return self.l[pos]
else:
return None
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
Frank Chang, 28.12.2010 22:35: Good afternoon. I want to thank everyone who helped me fix the global name 'levinshtein_automata' is not defined error. When I run the Shedskin 0.7 Python to C+++ compiler on the same python program, I receive the error message * Error * automata_test.py:148 : unbound identifier 'lookup_func'. ShedSkin is very restrictive compared to CPython. It requires static types for variables and it doesn't support all Python features. Is there a reason you want to use ShedSkin for your program? Stefan ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
On 12/28/2010 4:35 PM, Frank Chang wrote:
Good afternoon. I want to thank everyone who helped me fix the
global name 'levinshtein_automata' is not defined error.
When I run the Shedskin 0.7 Python to C+++ compiler on the
same python program, I receive the error message * Error *
automata_test.py:148 : unbound identifier 'lookup_func'. lookup_func
is a python function pointer passed as an argument to a python function.
I'd like to help
Please post the entire traceback.
Fix the indentation. I have to make too many assumptions with the
indentation messed up.
Let's refine our terminology. Python does not pass pointers, it passes
objects.
m is not a function. It is a callable class instance.
I have marked lines 148,161,172 and 174 in the python program
automata_test.py shown below. The shedskin tutorial says the latest
version of the Shedskin 0.7 Python to C++ compiler does not support
overloading __iter__ and __call__. I was wondering if anyone could
suggest a python workaround to this error message as I am new to
python. Thank you.
# automata_test.py
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'
else:
x = chr(ord(x) + 1)
state_transitions = self.transitions.get(s, {})
if x in state_transitions or s in self.defaults:
return x
la
Re: [Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
"Frank Chang" wrote When I run the Shedskin 0.7 Python to C+++ compiler on the same python program, I receive the error message * Error * automata_test.py:148 : unbound identifier 'lookup_func'. lookup_func is a python function pointer passed as an argument to a python function. I have marked lines 148,161,172 and 174 in the python program automata_test.py shown below. The shedskin tutorial says the latest version of the Shedskin 0.7 Python to C++ compiler does not support overloading __iter__ and __call__. These sound like issues with shedskin rather than Python, you will probably get better support on their forum/newsggroup/list. You may also find other compilers deal with your particular needs better - cython for example. But finally, remember that Python is not C++. If you really need C++ use C++. The compilers are clever and can save a lot of effort, but Python is primarily an dynamic interpreted language and a lot of its more advanced idioms do not translate easily to statically compiled code. HTH, ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
Good afternoon. I want to thank everyone who helped me fix the global
name 'levinshtein_automata' is not defined error.
When I run the Shedskin 0.7 Python to C+++ compiler on the
same python program, I receive the error message * Error *
automata_test.py:148 : unbound identifier 'lookup_func'. lookup_func is a
python function pointer passed as an argument to a python function.
I have marked lines 148,161,172 and 174 in the python program
automata_test.py shown below. The shedskin tutorial says the latest version
of the Shedskin 0.7 Python to C++ compiler does not support overloading
__iter__ and __call__. I was wondering if anyone could suggest a python
workaround to this error message as I am new to python. Thank you.
# automata_test.py
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'
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):
print 's'
nfa = NFA((0, 0))
for i, c in enumerate(term):
for e in range(k + 1):
# Correct ch
Re: [Tutor] Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined
"Frank Chang" wrote
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 others have answered the specific question, however I think you
have another problem lurking:
def find_all_matches(self, word, k, lookup_func):
lev = levenshtein_automata(word, k).to_dfa()
match = lev.next_valid_string('\0')
while match:
next = lookup_func(match)
if not next:
return
Here you return a None value
if match == next:
yield match
next1 = next1 + '\0'
match = lev.next_valid_string(next1)
length = len(list(testdfa.find_all_matches('food', 1, m)))
line 174
And here you try to convert the return value to a list.
But list(None) will fail with a TypeError.
You should probably returm an empty string or raise an exception
and catch it in your main block.
HTH,
--
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined
See my comment following line 145:
On 12/27/2010 8:25 PM, Frank Chang wrote:
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
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))
Re: [Tutor] Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined
It appears that you've defined "levenshtein_automata" as a method on your DFA class, but you did not reference the class instance in your call by prefixing "self". Instead, you're trying to call a globally defined function named "levenshtein_automata" -- which because it is not defined, is throwing a NameError. Try changing line 145 to the below and see if that resolves the issue: lev = self.levenshtein_automata(word, k).to_dfa() # line 145 ## ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
[Tutor] Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined
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
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))
