I'm attaching a new version of the patch, based on Oliver's (from 3 years ago).  This patch is against the py3k branch.

I've introduced a new table of (const) strings: _PyParser_TokenDescs, giving descriptions of each token type, so that you get e.g. "')'" rather than "RPAR"

The patch of pythonrun.c is unchanged other than using the description table, rather than the name table.

I've patched the expected results for the doctests in test_genexps and test_syntax.py so that these files pass: this gives the code the beginnings of a test suite.

The existing patch adds this compiler warning for me (gcc 4.4.2, on Fedora 12):
  Python/pythonrun.c: In function ‘err_input’:
  Python/pythonrun.c:1923: warning: embedded ‘\0’ in format
However I believe that snprintf isn't guaranteed to NUL-terminate the string under all conditions on all platforms, so the '\0' seems a sane failsafe.

How does this look?

I haven't attempted to deal with places where multiple token types are permitted, and it does sometimes simply emit "invalid syntax".