Здравствуйте, monax, Вы писали:

M>Какие ещё могут быть способы организации автодополнения?

Посмотри как в PyDev сделано, вот обзор http://pydev.blogspot.com/2012/01/code-completion-strategies-in-pydev.html
Правда там все сильно на Eclipse завязано.

Насчет AST. В PyPy есть все средства и оно по сути переводит код в статически типизированный (RPython)
http://doc.pypy.org/en/latest/architecture.html#translation-framework