[Tutor] Python 2.7.1 interpreter passing function pointer as function argument and Shedskin 0.7
bob gailer
bgailer at gmail.com
Wed Dec 29 06:34:10 CET 2010
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
> 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 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 = self.levenshtein_automata(word, k).to_dfa()
> match = lev.next_valid_string('\0')
> while match:
> next = lookup_func(match) ***** line 148 *****
> if not next:
> return
> if match == next:
> yield match
> next = next + '\0'
> match = lev.next_valid_string(next)
> class Matcher(object):
> def __init__(self, l):
> self.l = l
> self.probes = 0
> def __call__(self, w): **** line 161 ******
> 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) **** line 172 *****
> testdfa = DFA(1)
> length = len(list(testdfa.find_all_matches('food', 1, m))) ****
> line 174 ***
>
>
> _______________________________________________
> Tutor maillist - Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
--
Bob Gailer
919-636-4239
Chapel Hill NC
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20101229/55865085/attachment-0001.html>
More information about the Tutor
mailing list