Package: python2.6 Version: 2.6.6-3 Severity: normalpython2.6 crashed with segmentation fault when I was running pyflakes (0.4.0-1) on the attached file. I've been observing similar crashes on other files; they are non-deterministic and extremely rare.
-- System Information: Debian Release: squeeze/sid APT prefers unstable APT policy: (990, 'unstable'), (500, 'experimental') Architecture: i386 (i686) Kernel: Linux 2.6.32-5-686 (SMP w/2 CPU cores) Locale: LANG=C, LC_CTYPE=pl_PL.UTF-8 (charmap=UTF-8) Shell: /bin/sh linked to /bin/dash Versions of packages python2.6 depends on: ii libbz2-1.0 1.0.5-5 high-quality block-sorting file co ii libc6 2.11.2-5 Embedded GNU C Library: Shared lib ii libdb4.8 4.8.30-2 Berkeley v4.8 Database Libraries [ ii libncursesw5 5.7+20100313-3 shared libraries for terminal hand ii libreadline6 6.1-3 GNU readline and history libraries ii libsqlite3-0 3.7.2-1 SQLite 3 shared library ii mime-support 3.48-1 MIME files 'mime.types' & 'mailcap ii python2.6-minimal 2.6.6-3 A minimal subset of the Python lan -- Jakub Wilk
#0 0x0810cd5d in visit_decref (op=<unknown at remote 0xb73b526c>, data=0x0) at
../Modules/gcmodule.c:271
No locals.
#1 0x08091e9d in dict_traverse (op=
{'Const': <classobj at remote 0xb7389b3c>, 'Raise': <classobj at remote
0xb73952cc>, 'AssTuple': <classobj at remote 0xb73898fc>, 'AssList': <classobj
at remote 0xb738989c>, 'UnaryAdd': <classobj at remote 0xb73954dc>,
'Decorators': <classobj at remote 0xb7389b9c>, 'Exec': <classobj at remote
0xb7389c8c>, '_assign_types': [304, 305, 306, 307, 308, 310, 311, 312, 313,
314, 315, 316], 'Stmt': <classobj at remote 0xb73953bc>, 'GenExprFor':
<classobj at remote 0xb7389dac>, 'FloorDiv': <classobj at remote 0xb7389cbc>,
'TryFinally': <classobj at remote 0xb739547c>, 'Not': <classobj at remote
0xb73951ac>, 'nodes': {'expression': 'Expression'}, 'Mod': <classobj at remote
0xb73950ec>, 'AssAttr': <classobj at remote 0xb738986c>, 'Keyword': <classobj
at remote 0xb7389f5c>, '__file__':
'/usr/lib/python2.6/compiler/transformer.pyc', 'AugAssign': <classobj at remote
0xb738998c>, 'Yield': <classobj at remote 0xb739559c>, 'LeftShift': <classobj
at remote 0xb7389fbc>, 'RightShift': <classobj at remote 0xb739532c>,
'OP_DELETE'...(truncated), visit=0x810cd50 <visit_decref>, arg=0x0) at
../Objects/dictobject.c:2003
vret = <value optimized out>
i = 152
pk = <value optimized out>
#2 0x0810d7ac in subtract_refs (generation=<value optimized out>) at
../Modules/gcmodule.c:296
gc = 0xb76f79b0
#3 collect (generation=<value optimized out>) at ../Modules/gcmodule.c:817
i = <value optimized out>
m = <value optimized out>
n = <value optimized out>
young = 0x823fdd4
old = 0x823fde8
unreachable = {gc = {gc_next = 0xb7350dec, gc_prev = 0x0, gc_refs =
134824275}, dummy = <invalid float value>}
finalizers = {gc = {gc_next = 0xbf89b3a8, gc_prev = 0x8065a7b, gc_refs
= -1221259796}, dummy = <invalid float value>}
gc = <value optimized out>
t1 = 0
#4 0x0810e1db in collect_generations (basicsize=16) at
../Modules/gcmodule.c:924
i = 50331648
#5 _PyObject_GC_Malloc (basicsize=16) at ../Modules/gcmodule.c:1363
op = <value optimized out>
g = 0xb7351f80
#6 0x080ab28b in PyType_GenericAlloc (type=0x860a5bc, nitems=0) at
../Objects/typeobject.c:758
obj = <value optimized out>
size = 16
#7 0x08178b1a in init_types () at ../Python/Python-ast.c:769
initialized = 140529116
#8 0x081796fb in PyAST_Check (obj=
'# Natural Language Toolkit: Finite State Automata\n#\n# Copyright (C)
2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: the alphabet of the FSA\n @type sigma: sequence\n
@param transitions: A dictionary representing the s...(truncated)) at
../Python/Python-ast.c:6484
No locals.
#9 0x080dabca in builtin_compile (self=0x0, args=
('# Natural Language Toolkit: Finite State Automata\n#\n# Copyright (C)
2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: the alphabet of the FSA\n @type sigma: sequence\n
@param transitions: A dictionary representing the ...(truncated), kwds=0x0) at
../Python/bltinmodule.c:508
str = <value optimized out>
filename = <value optimized out>
startstr = 0xb76fe3d4 "exec"
mode = 0
dont_inherit = 0
supplied_flags = 0
is_ast = <value optimized out>
cf = {cf_flags = 0}
result = <value optimized out>
cmd =
'# Natural Language Toolkit: Finite State Automata\n#\n# Copyright (C)
2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: the alphabet of the FSA\n @type sigma: sequence\n
@param transitions: A dictionary representing the s...(truncated)
tmp = <value optimized out>
length = <value optimized out>
kwlist = {0x8196f51 "source", 0x8185000 "filename", 0x821f51b "mode",
0x8193dde "flags", 0x8193e63 "dont_inherit", 0x0}
#10 0x080e0721 in call_function (f=
Frame 0x85fda24, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 29, in check
(codeString='# Natural Language Toolkit: Finite State Automata\n#\n# Copyright
(C) 2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: ...(truncated), throwflag=0) at ../Python/ceval.c:3750
callargs =
('# Natural Language Toolkit: Finite State Automata\n#\n# Copyright (C)
2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: the alphabet of the FSA\n @type sigma: sequence\n
@param transitions: A dictionary representing the ...(truncated)
flags = <value optimized out>
tstate = 0x855d050
func = <built-in function compile>
w = <value optimized out>
nk = -1220911716
n = 139841616
pfunc = 0x85fdb88
#11 PyEval_EvalFrameEx (f=
Frame 0x85fda24, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 29, in check
(codeString='# Natural Language Toolkit: Finite State Automata\n#\n# Copyright
(C) 2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: ...(truncated), throwflag=0) at ../Python/ceval.c:2412
sp = 0x85fdb8c
stack_pointer = <value optimized out>
next_instr = 0x85c4859 "\001Wn:"
opcode = <value optimized out>
oparg = <value optimized out>
why = 3077731596
err = <value optimized out>
x = <value optimized out>
v = <value optimized out>
w = <value optimized out>
u = <value optimized out>
t = <value optimized out>
stream = <value optimized out>
freevars = 0x85fdb88
retval = 0x0
tstate = 0x855d050
co = 0xb76e00b0
instr_ub = -1
instr_lb = 0
instr_prev = <value optimized out>
first_instr = 0x85c4844 "yU"
names =
('compile', 'MemoryError', 'sys', 'version_info', 'SyntaxError', 'None',
'IndentationError', 'args', 'lineno', 'offset', 'text', 'stderr', 'splitlines',
'len', 'UnicodeError', 'compiler', 'parse', 'checker', 'Checker', 'messages',
'sort')
consts =
('\n Check the Python source given by C{codeString} for flakes.\n\n
@param codeString: The Python source to check.\n @type codeString:
C{str}\n\n @param filename: The name of the file the source came from, used
to report\n errors.\n @type filename: C{str}\n\n @return: The
number of warnings emitted.\n @rtype: C{int}\n ', 'exec', 2, 4, 0, '%s:
problem decoding source', -1, '%s:%d: %s', ' ', '^', 1, 'encoding error at %r:
%s', <code at remote 0xb7743608>, None, (2, 4))
#12 0x080e18b0 in fast_function (f=
Frame 0x85fd6bc, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 83, in
checkPath
(filename='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py',
fd=<file at remote 0xb7700288>), throwflag=0) at ../Python/ceval.c:3836
i = 511
f =
Frame 0x85fda24, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 29, in check
(codeString='# Natural Language Toolkit: Finite State Automata\n#\n# Copyright
(C) 2001-2006 NLTK Project\n# Authors: Steven Bird <s...@ldc.upenn.edu>\n#
Rob Speer <rsp...@mit.edu>\n# URL: <http://www.nltk.org/>\n# For license
information, see LICENSE.TXT\n\n"""\nA module for finite state automata.
\nOperations are based on Aho, Sethi & Ullman (1986) Chapter 3.\n"""\n\nfrom
nltk import tokenize, cfg, Tree\nfrom nltk.parse import pchart\nimport
yaml\n\nepsilon = None\n\n# some helper functions\n\n# TODO - check that parse
was complete, and report error otherwise\n\nclass FSA(yaml.YAMLObject):\n
"""\n A class for finite state automata. In general, it represents\n
nondetermnistic finite state automata, with DFAs being a special case.\n
"""\n yaml_tag = \'!FSA\'\n def __init__(self, sigma=\'\',
transitions=None, start=0, finals=None):\n """Set up the FSA.\n\n
@param sigma: ...(truncated)
tstate = 0x855d050
stack = 0x3000000
co = <value optimized out>
nd = <value optimized out>
globals =
{'check': <function at remote 0xb734280c>, '__builtins__': {'bytearray':
<type at remote 0x826d640>, 'IndexError': <type at remote 0x822a280>, 'all':
<built-in function all>, 'help': <_Helper at remote 0xb76ea6ec>, 'vars':
<built-in function vars>, 'SyntaxError': <type at remote 0x8229f00>, 'unicode':
<type at remote 0x8235fc0>, 'UnicodeDecodeError': <type at remote 0x822a6e0>,
'isinstance': <built-in function isinstance>, 'copyright':
<_Printer(_Printer__data='Copyright (c) 2001-2010 Python Software
Foundation.\nAll Rights Reserved.\n\nCopyright (c) 2000 BeOpen.com.\nAll Rights
Reserved.\n\nCopyright (c) 1995-2001 Corporation for National Research
Initiatives.\nAll Rights Reserved.\n\nCopyright (c) 1991-1995 Stichting
Mathematisch Centrum, Amsterdam.\nAll Rights Reserved.', _Printer__lines=None,
_Printer__name='copyright', _Printer__dirs=(), _Printer__files=(...)) at remote
0xb774432c>, 'NameError': <type at remote 0x8229c60>, 'BytesWarning': <type at
remote 0x822b860>, 'dict': <type at remote 0x822f360>, 'i...(truncated)
argdefs = <value optimized out>
d = <value optimized out>
#13 call_function (f=
Frame 0x85fd6bc, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 83, in
checkPath
(filename='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py',
fd=<file at remote 0xb7700288>), throwflag=0) at ../Python/ceval.c:3771
func = <function at remote 0xb734280c>
w = <value optimized out>
nk = 139841616
n = 2
pfunc = 0x85fd800
#14 PyEval_EvalFrameEx (f=
Frame 0x85fd6bc, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 83, in
checkPath
(filename='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py',
fd=<file at remote 0xb7700288>), throwflag=0) at ../Python/ceval.c:2412
sp = 0x85fd80c
stack_pointer = <value optimized out>
next_instr = 0xb77385fb "SWd\002"
opcode = <value optimized out>
oparg = <value optimized out>
why = 3073648652
err = <value optimized out>
x = <value optimized out>
v = <value optimized out>
w = <value optimized out>
u = <value optimized out>
t = <value optimized out>
stream = <value optimized out>
freevars = 0x85fd800
retval = 0x0
tstate = 0x855d050
co = 0xb76e3ad0
instr_ub = -1
instr_lb = 0
instr_prev = <value optimized out>
first_instr = 0xb77385d4 "y8"
names = ('file', 'check', 'read', 'close', 'IOError', 'sys', 'stderr',
'args')
consts =
('\n Check the given path, printing out any warnings detected.\n\n
@return: the number of warnings printed\n ', 'U', None, '%s: %s', 1)
#15 0x080e18b0 in fast_function (f=
Frame 0x85e61ac, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 101, in main
(args=['binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'],
warnings=0,
arg='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'),
throwflag=0) at ../Python/ceval.c:3836
i = 511
f =
Frame 0x85fd6bc, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 83, in
checkPath
(filename='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py',
fd=<file at remote 0xb7700288>)
tstate = 0x855d050
stack = 0x3000000
co = <value optimized out>
nd = <value optimized out>
globals =
{'check': <function at remote 0xb734280c>, '__builtins__': {'bytearray':
<type at remote 0x826d640>, 'IndexError': <type at remote 0x822a280>, 'all':
<built-in function all>, 'help': <_Helper at remote 0xb76ea6ec>, 'vars':
<built-in function vars>, 'SyntaxError': <type at remote 0x8229f00>, 'unicode':
<type at remote 0x8235fc0>, 'UnicodeDecodeError': <type at remote 0x822a6e0>,
'isinstance': <built-in function isinstance>, 'copyright':
<_Printer(_Printer__data='Copyright (c) 2001-2010 Python Software
Foundation.\nAll Rights Reserved.\n\nCopyright (c) 2000 BeOpen.com.\nAll Rights
Reserved.\n\nCopyright (c) 1995-2001 Corporation for National Research
Initiatives.\nAll Rights Reserved.\n\nCopyright (c) 1991-1995 Stichting
Mathematisch Centrum, Amsterdam.\nAll Rights Reserved.', _Printer__lines=None,
_Printer__name='copyright', _Printer__dirs=(), _Printer__files=(...)) at remote
0xb774432c>, 'NameError': <type at remote 0x8229c60>, 'BytesWarning': <type at
remote 0x822b860>, 'dict': <type at remote 0x822f360>, 'i...(truncated)
argdefs = <value optimized out>
d = <value optimized out>
#16 call_function (f=
Frame 0x85e61ac, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 101, in main
(args=['binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'],
warnings=0,
arg='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'),
throwflag=0) at ../Python/ceval.c:3771
func = <function at remote 0xb734264c>
w = <value optimized out>
nk = 139841616
n = 1
pfunc = 0x85e6308
#17 PyEval_EvalFrameEx (f=
Frame 0x85e61ac, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 101, in main
(args=['binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'],
warnings=0,
arg='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'),
throwflag=0) at ../Python/ceval.c:2412
sp = 0x85e6310
stack_pointer = <value optimized out>
next_instr = 0xb76d0560 "7}\001"
opcode = <value optimized out>
oparg = <value optimized out>
why = 3073648204
err = <value optimized out>
x = <value optimized out>
v = <value optimized out>
w = <value optimized out>
u = <value optimized out>
t = <value optimized out>
stream = <value optimized out>
freevars = 0x85e6300
retval = 0x0
tstate = 0x855d050
co = 0xb76e3f50
instr_ub = -1
instr_lb = 0
instr_prev = <value optimized out>
first_instr = 0xb76d04bc "d\001"
names = ('os', 'path', 'isdir', 'walk', 'endswith', 'checkPath',
'join', 'check', 'sys', 'stdin', 'read')
consts = (None, 0, '.py', '<stdin>')
#18 0x080e18b0 in fast_function (f=Frame 0x8577b34, for file /usr/bin/pyflakes,
line 5, in <module> (), throwflag=0) at ../Python/ceval.c:3836
i = 511
f =
Frame 0x85e61ac, for file
/usr/lib/pymodules/python2.6/pyflakes/scripts/pyflakes.py, line 101, in main
(args=['binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py'],
warnings=0,
arg='binary/w3af-console_1.0-rc3svn3489-1_all/usr/share/w3af/extlib/nltk_contrib/mit/six863/kimmo/fsa.py')
tstate = 0x855d050
stack = 0x3000000
co = <value optimized out>
nd = <value optimized out>
globals =
{'check': <function at remote 0xb734280c>, '__builtins__': {'bytearray':
<type at remote 0x826d640>, 'IndexError': <type at remote 0x822a280>, 'all':
<built-in function all>, 'help': <_Helper at remote 0xb76ea6ec>, 'vars':
<built-in function vars>, 'SyntaxError': <type at remote 0x8229f00>, 'unicode':
<type at remote 0x8235fc0>, 'UnicodeDecodeError': <type at remote 0x822a6e0>,
'isinstance': <built-in function isinstance>, 'copyright':
<_Printer(_Printer__data='Copyright (c) 2001-2010 Python Software
Foundation.\nAll Rights Reserved.\n\nCopyright (c) 2000 BeOpen.com.\nAll Rights
Reserved.\n\nCopyright (c) 1995-2001 Corporation for National Research
Initiatives.\nAll Rights Reserved.\n\nCopyright (c) 1991-1995 Stichting
Mathematisch Centrum, Amsterdam.\nAll Rights Reserved.', _Printer__lines=None,
_Printer__name='copyright', _Printer__dirs=(), _Printer__files=(...)) at remote
0xb774432c>, 'NameError': <type at remote 0x8229c60>, 'BytesWarning': <type at
remote 0x822b860>, 'dict': <type at remote 0x822f360>, 'i...(truncated)
argdefs = <value optimized out>
d = <value optimized out>
#19 call_function (f=Frame 0x8577b34, for file /usr/bin/pyflakes, line 5, in
<module> (), throwflag=0) at ../Python/ceval.c:3771
func = <function at remote 0xb7342c6c>
w = <value optimized out>
nk = 139841616
n = 1
pfunc = 0x8577c70
#20 PyEval_EvalFrameEx (f=Frame 0x8577b34, for file /usr/bin/pyflakes, line 5,
in <module> (), throwflag=0) at ../Python/ceval.c:2412
sp = 0x8577c78
stack_pointer = <value optimized out>
next_instr = 0xb7700066 "d\004"
opcode = <value optimized out>
oparg = <value optimized out>
why = 3073649772
err = <value optimized out>
x = <value optimized out>
v = <value optimized out>
w = <value optimized out>
u = <value optimized out>
t = <value optimized out>
stream = <value optimized out>
freevars = 0x8577c6c
retval = 0x0
tstate = 0x855d050
co = 0xb7743530
instr_ub = -1
instr_lb = 0
instr_prev = <value optimized out>
first_instr = 0xb7700034 "d"
names = ('sys', 'pyflakes.scripts.pyflakes', 'main', 'exit', 'argv')
consts = (-1, None, ('main',), 1, 0)
#21 0x080e2507 in PyEval_EvalCodeEx (co=0xb7743530, globals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, locals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, args=0x0, argcount=0, kws=0x0, kwcount=0, defs=0x0, defcount=0,
closure=0x0)
at ../Python/ceval.c:3000
f = <unknown at remote 0xb770a4a0>
retval = <value optimized out>
freevars = 0x8577c6c
tstate = 0x855d050
x = <value optimized out>
u = <value optimized out>
#22 0x080e2607 in PyEval_EvalCode (co=0xb7743530, globals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, locals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}) at ../Python/ceval.c:541
No locals.
#23 0x080ffcbd in run_mod (fp=0x857c6b8, filename=0xbf89d95d
"/usr/bin/pyflakes", start=257, globals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, locals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, closeit=1, flags=0xbf89badc) at ../Python/pythonrun.c:1351
co = 0xb7743530
#24 PyRun_FileExFlags (fp=0x857c6b8, filename=0xbf89d95d "/usr/bin/pyflakes",
start=257, globals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, locals=
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}, closeit=1, flags=0xbf89badc) at ../Python/pythonrun.c:1337
ret = <value optimized out>
mod = <value optimized out>
arena = 0x856b420
#25 0x080fff22 in PyRun_SimpleFileExFlags (fp=0x857c6b8, filename=0xbf89d95d
"/usr/bin/pyflakes", closeit=1, flags=0xbf89badc) at ../Python/pythonrun.c:941
m = <value optimized out>
d =
{'__builtins__': <module at remote 0xb770a074>, '__file__':
'/usr/bin/pyflakes', '__package__': None, 'sys': <module at remote 0xb770a08c>,
'__name__': '__main__', 'main': <function at remote 0xb7342c6c>, '__doc__':
None}
v = <value optimized out>
ext = <value optimized out>
set_file_name = 1
ret = <value optimized out>
#26 0x0805dd81 in Py_Main (argc=3, argv=0xbf89bbc4) at ../Modules/main.c:577
c = <value optimized out>
sts = 0
command = 0x0
filename = 0x0
module = 0x0
fp = 0x857c6b8
p = <value optimized out>
unbuffered = 0
skipfirstline = 0
stdin_is_interactive = 0
help = -1081484963
version = 1
saw_unbuffered_flag = 0
cf = {cf_flags = 0}
#27 0x0805cf6b in main (argc=3, argv=0xbf89bbc4) at ../Modules/python.c:23
No locals.
# Natural Language Toolkit: Finite State Automata # # Copyright (C) 2001-2006 NLTK Project # Authors: Steven Bird <s...@ldc.upenn.edu> # Rob Speer <rsp...@mit.edu> # URL: <http://www.nltk.org/> # For license information, see LICENSE.TXT """ A module for finite state automata. Operations are based on Aho, Sethi & Ullman (1986) Chapter 3. """ from nltk import tokenize, cfg, Tree from nltk.parse import pchart import yaml epsilon = None # some helper functions # TODO - check that parse was complete, and report error otherwise class FSA(yaml.YAMLObject): """ A class for finite state automata. In general, it represents nondetermnistic finite state automata, with DFAs being a special case. """ yaml_tag = '!FSA' def __init__(self, sigma='', transitions=None, start=0, finals=None): """Set up the FSA. @param sigma: the alphabet of the FSA @type sigma: sequence @param transitions: A dictionary representing the states and transitions in the FSA. The keys are state identifiers (any hashable object), and the values are dictionaries that map input symbols to the sets of states they lead to. @type transitions: dict @param start: The identifier of the start state @type start: hashable object @param finals: The identifiers of the accept states @type finals: sequence """ self._transitions = transitions or {} self._start = start self._reverse = {} self._build_reverse_transitions() if finals: self._finals = set(finals) else: self._finals = set([0]) self._sigma = set(sigma) assert isinstance(self._transitions, dict) self._next_state_num = 0 def _build_reverse_transitions(self): for state in self._transitions: self._reverse.setdefault(state, {}) for (state, symbol, target) in self.generate_transitions(): self._add_transition(self._reverse, target, symbol, state) def generate_transitions(self): """ A generator that yields each transition arrow in the FSA in the form (source, label, target). """ for (state, map) in self._transitions.items(): for (symbol, targets) in map.items(): for target in targets: yield (state, symbol, target) def labels(self, s1, s2): """ A generator for all possible labels taking state s1 to state s2. """ map = self._transitions.get(s1, {}) for (symbol, targets) in map.items(): if s2 in targets: yield symbol def sigma(self): "The alphabet of the FSA." return self._sigma alphabet = sigma def check_in_sigma(self, label): "Check whether a given object is in the alphabet." if label and label not in self._sigma: raise ValueError('Label "%s" not in alphabet: %s' % (label, str(self._sigma))) def __len__(self): "The number of states in the FSA." return len(self._transitions) def new_state(self): """ Add a new state to the FSA. @returns: the ID of the new state (a sequentially-assigned number). @rtype: int """ while self._next_state_num in self._transitions: self._next_state_num += 1 self._transitions[self._next_state_num] = {} self._reverse[self._next_state_num] = {} return self._next_state_num def add_state(self, name): self._transitions[name] = {} self._reverse[name] = {} return name def start(self): """ @returns: the ID of the FSA's start state. """ return self._start def finals(self): """ @returns: the IDs of all accept states. @rtype: set """ # was a tuple before return self._finals def nonfinals(self): """ @returns: the IDs of all accept states. @rtype: set """ # was a tuple before return set(self.states()).difference(self._finals) def states(self): """ @returns: a list of all states in the FSA. @rtype: list """ return self._transitions.keys() def add_final(self, state): """ Make a state into an accept state. """ self._finals.add(state) def delete_final(self, state): """ Make an accept state no longer be an accept state. """ self._finals = self._finals.difference(set([state])) # del self._finals[state] def set_final(self, states): """ Set the list of accept states. """ self._finals = set(states) def set_start(self, start): """ Set the start state of the FSA. """ self._start = start def in_finals(self, list): """ Check whether a sequence contains any final states. """ return [state for state in list if state in self.finals()] != [] def insert_safe(self, s1, label, s2): if s1 not in self.states(): self.add_state(s1) if s2 not in self.states(): self.add_state(s2) self.insert(s1, label, s2) def insert(self, s1, label, s2): """ Add a new transition to the FSA. @param s1: the source of the transition @param label: the element of the alphabet that labels the transition @param s2: the destination of the transition """ if s1 not in self.states(): raise ValueError, "State %s does not exist in %s" % (s1, self.states()) if s2 not in self.states(): raise ValueError, "State %s does not exist in %s" % (s2, self.states()) self._add_transition(self._transitions, s1, label, s2) self._add_transition(self._reverse, s2, label, s1) def _add_transition(self, map, s1, label, s2): mapping = map[s1] targets = mapping.setdefault(label, []) targets.append(s2) def _del_transition(self, map, s1, label, s2): mapping = map[s1] targets = mapping.setdefault(label, []) targets.remove(s2) if len(targets) == 0: del mapping[label] def delete(self, s1, label, s2): """ Removes a transition from the FSA. @param s1: the source of the transition @param label: the element of the alphabet that labels the transition @param s2: the destination of the transition """ if s1 not in self.states(): raise ValueError, "State %s does not exist" % s1 if s2 not in self.states(): raise ValueError, "State %s does not exist" % s1 self._del_transition(self._transitions, s1, label, s2) self._del_transition(self._reverse, s2, label, s1) def delete_state(self, state): "Removes a state and all its transitions from the FSA." if state not in self.states(): raise ValueError, "State %s does not exist" % state for (s1, label, s2) in self.incident_transitions(state): self.delete(s1, label, s2) del self._transitions[state] del self._reverse[state] def incident_transitions(self, state): """ @returns: a set of transitions into or out of a state. @rtype: set """ result = set() forward = self._transitions[state] backward = self._reverse[state] for label, targets in forward.items(): for target in targets: result.add((state, label, target)) for label, targets in backward.items(): for target in targets: result.add((target, label, state)) return result def relabel_state(self, old, new): """ Assigns a state a new identifier. """ if old not in self.states(): raise ValueError, "State %s does not exist" % old if new in self.states(): raise ValueError, "State %s already exists" % new changes = [] for (s1, symbol, s2) in self.generate_transitions(): if s1 == old and s2 == old: changes.append((s1, symbol, s2, new, symbol, new)) elif s1 == old: changes.append((s1, symbol, s2, new, symbol, s2)) elif s2 == old: changes.append((s1, symbol, s2, s1, symbol, new)) for (leftstate, symbol, rightstate, newleft, newsym, newright)\ in changes: print leftstate, symbol, rightstate, newleft, newsym, newright self.delete(leftstate, symbol, rightstate) self.insert_safe(newleft, newsym, newright) del self._transitions[old] del self._reverse[old] def next(self, state, symbol): "The set of states reached from a certain state via a given symbol." return self.e_closure(self._transitions[state].get(symbol, set())) nextStates = next def move(self, states, symbol): "The set of states reached from a set of states via a given symbol." result = set() for state in states: result = result.union(self.next(state, symbol)) return self.e_closure(result) def is_deterministic(self): """ Return whether this is a DFA (every symbol leads from a state to at most one target state). """ for map in self._transitions.values(): for targets in map.values(): if len(targets) > 1: return False return True def nextState(self, state, symbol): """ The single state reached from a state via a given symbol. If there is more than one such state, raises a ValueError. If there is no such state, returns None. """ next = self.next(state, symbol) if len(next) > 1: raise ValueError, "This FSA is nondeterministic -- use nextStates instead." elif len(next) == 1: return list(next)[0] else: return None def forward_traverse(self, state): "All states reachable by following transitions from a given state." result = set() for (symbol, targets) in self._transitions[state].items(): result = result.union(targets) return result def reverse_traverse(self, state): """All states from which a given state is reachable by following transitions.""" result = set() for (symbol, targets) in self._reverse[state].items(): result = result.union(targets) return result def _forward_accessible(self, s1, visited): for s2 in self.forward_traverse(s1): if not s2 in visited: visited.add(s2) self._forward_accessible(s2, visited) return visited def _reverse_accessible(self, s1, visited): for s2 in self.reverse_traverse(s1): if not s2 in visited: visited.add(s2) self._reverse_accessible(s2, visited) return visited # delete inaccessible nodes and unused transitions def prune(self): """ Modifies an FSA to remove inaccessible states and unused transitions. """ acc = self.accessible() for state in self.states(): if state not in acc: self.delete_state(state) else: self._clean_map(self._transitions[state]) self._clean_map(self._reverse[state]) def _clean_map(self, map): for (key, value) in map.items(): if len(value) == 0: del map[key] # mark accessible nodes def accessible(self): acc = set() for final in self.finals(): reverse_acc = set([final]) self._reverse_accessible(final, reverse_acc) acc = acc.union(reverse_acc) forward_acc = set([self.start()]) self._forward_accessible(self.start(), forward_acc) acc = acc.intersection(forward_acc) return acc def e_closure(self, states): """ Given a set of states, return the set of states reachable from those states by following epsilon transitions. @param states: the initial set of states @type states: sequence @returns: a superset of the given states, reachable by epsilon transitions @rtype: set """ stack = list(states) closure = list(states) while stack: s1 = stack.pop() for s2 in self.next(s1, epsilon): if s2 not in closure: closure.append(s2) stack.append(s2) return set(closure) # return the corresponding DFA using subset construction (ASU p118) # NB representation of (a*) still isn't minimal; should have 1 state not 2 def dfa(self): "Return a DFA that is equivalent to this FSA." dfa = FSA(self.sigma()) dfa_initial = dfa.start() nfa_initial = tuple(self.e_closure((self.start(),))) map = {} map[dfa_initial] = nfa_initial map[nfa_initial] = dfa_initial if nfa_initial in self.finals(): dfa.add_final(dfa_initial) unmarked = [dfa_initial] marked = [] while unmarked: dfa_state = unmarked.pop() marked.append(dfa_state) # is a final state accessible via epsilon transitions? if self.in_finals(self.e_closure(map[dfa_state])): dfa.add_final(dfa_state) for label in self.sigma(): nfa_next = tuple(self.e_closure(self.move(map[dfa_state], label))) if map.has_key(nfa_next): dfa_next = map[nfa_next] else: dfa_next = dfa.new_state() map[dfa_next] = nfa_next map[nfa_next] = dfa_next if self.in_finals(nfa_next): dfa.add_final(dfa_next) unmarked.append(dfa_next) dfa.insert(dfa_state, label, dfa_next) return dfa def generate(self, maxlen, state=0, prefix=""): "Generate all accepting sequences of length at most maxlen." if maxlen > 0: if state in self._finals: print prefix for (s1, labels, s2) in self.outgoing_transitions(state): for label in labels(): self.generate(maxlen-1, s2, prefix+label) def pp(self): """ Print a representation of this FSA (in human-readable YAML format). """ print yaml.dump(self) @classmethod def from_yaml(cls, loader, node): map = loader.construct_mapping(node) result = cls(map.get('sigma', []), {}, map.get('finals', [])) for (s1, map1) in map['transitions'].items(): for (symbol, targets) in map1.items(): for s2 in targets: result.insert(s1, symbol, s2) return result @classmethod def to_yaml(cls, dumper, data): sigma = data.sigma() transitions = {} for (s1, symbol, s2) in data.generate_transitions(): map1 = transitions.setdefault(s1, {}) map2 = map1.setdefault(symbol, []) map2.append(s2) try: sigma = "".join(sigma) except: sigma = list(sigma) node = dumper.represent_mapping(cls.yaml_tag, dict( sigma = sigma, finals = list(data.finals()), start = data._start, transitions = transitions)) return node def show_pygraph(self, title='FSA', outfile=None, labels=True, root=None): from pygraph import pygraph, tkgraphview graph = pygraph.Grapher('directed') for state in self.states(): color = '#eee' if state in self.finals(): shape = 'oval' else: shape = 'rect' if state == self.start(): color = '#afa' term = '' if state == self.start(): term = 'start' elif state == 'End': term = 'end' if state in [0, '0', 'reject', 'Reject']: color='#e99' graph.addNode(state, state, color, shape, term) #for source, trans in self._transitions.items(): for source, label, target in self.generate_transitions(): if not labels: label = '' graph.addEdge(source, target, label, color='black', dup=False) if outfile is None: outfile = title return tkgraphview.tkGraphView(graph, title, outfile, root=root, startTk=(not root)) def __str__(self): return yaml.dump(self) ### FUNCTIONS TO BUILD FSA FROM REGEXP # the grammar of regular expressions # (probabilities ensure that unary operators # have stronger associativity than juxtaposition) def grammar(terminals): (S, Expr, Star, Plus, Qmk, Paren) = [cfg.Nonterminal(s) for s in 'SE*+?('] rules = [cfg.WeightedProduction(Expr, [Star], prob=0.2), cfg.WeightedProduction(Expr, [Plus], prob=0.2), cfg.WeightedProduction(Expr, [Qmk], prob=0.2), cfg.WeightedProduction(Expr, [Paren], prob=0.2), cfg.WeightedProduction(S, [Expr], prob=0.5), cfg.WeightedProduction(S, [S, Expr], prob=0.5), cfg.WeightedProduction(Star, [Expr, '*'], prob=1), cfg.WeightedProduction(Plus, [Expr, '+'], prob=1), cfg.WeightedProduction(Qmk, [Expr, '?'], prob=1), cfg.WeightedProduction(Paren, ['(', S, ')'], prob=1)] prob_term = 0.2/len(terminals) # divide remaining pr. mass for terminal in terminals: rules.append(cfg.WeightedProduction(Expr, [terminal], prob=prob_term)) return cfg.WeightedGrammar(S, rules) _parser = pchart.InsideParse(grammar('abcde')) # create NFA from regexp (Thompson's construction) # assumes unique start and final states def re2nfa(fsa, re): tokens = tokenize.regexp(re, pattern=r'.') tree = _parser.parse(tokens) if tree is None: raise ValueError('Bad Regexp') state = re2nfa_build(fsa, fsa.start(), tree) fsa.set_final([state]) # fsa.minimize() def re2nfa_build(fsa, node, tree): # Terminals. if not isinstance(tree, Tree): return re2nfa_char(fsa, node, tree) elif len(tree) == 1: return re2nfa_build(fsa, node, tree[0]) elif tree.node == '(': return re2nfa_build(fsa, node, tree[1]) elif tree.node == '*': return re2nfa_star(fsa, node, tree[0]) elif tree.node == '+': return re2nfa_plus(fsa, node, tree[0]) elif tree.node == '?': return re2nfa_qmk(fsa, node, tree[0]) else: node = re2nfa_build(fsa, node, tree[0]) return re2nfa_build(fsa, node, tree[1]) def re2nfa_char(fsa, node, char): new = fsa.new_state() fsa.insert(node, char, new) return new def re2nfa_qmk(fsa, node, tree): node1 = fsa.new_state() node2 = re2nfa_build(fsa, node1, tree) node3 = fsa.new_state() fsa.insert(node, epsilon, node1) fsa.insert(node, epsilon, node3) fsa.insert(node2, epsilon, node3) return node3 def re2nfa_plus(fsa, node, tree): node1 = re2nfa_build(fsa, node, tree[0]) fsa.insert(node1, epsilon, node) return node1 def re2nfa_star(fsa, node, tree): node1 = fsa.new_state() node2 = re2nfa_build(fsa, node1, tree) node3 = fsa.new_state() fsa.insert(node, epsilon, node1) fsa.insert(node, epsilon, node3) fsa.insert(node2, epsilon, node1) fsa.insert(node2, epsilon, node3) return node3 ################################################################# # Demonstration ################################################################# def demo(): """ A demonstration showing how FSAs can be created and used. """ # Define an alphabet. alphabet = "abcd" # Create a new FSA. fsa = FSA(alphabet) # Use a regular expression to initialize the FSA. re = 'abcd' print 'Regular Expression:', re re2nfa(fsa, re) print "NFA:" fsa.pp() # Convert the (nondeterministic) FSA to a deterministic FSA. dfa = fsa.dfa() print "DFA:" dfa.pp() # Prune the DFA dfa.prune() print "PRUNED DFA:" dfa.pp() # Use the FSA to generate all strings of length less than 3 # (broken) #fsa.generate(3) if __name__ == '__main__': demo()
signature.asc
Description: Digital signature
