Seems you can tell the Parse::Token what package to create the symbols in by calling $parse_token->inpkg($package_name) .
I thought the best way would be to specify the tokenClass option for Parse and subclass Parse::Token and do something in the constructor, but it seems there are problems with this ... the instance method tokenClass() of Parse::Lex (inherited from Parse::ALex) sets a "static" variable shared by all instances of any subclass of Parse::ALex so once you tell one instance to use a subclass for its tokens, all will. ...
Seems to me the best you can do is to build and eval a string and hope for the best:
my $rand_pkg = 'AnneliTokens::T' . rand();
my $parser = eval "package $rand_pkg; Parse::Lex->new(\@token);";
I do hope this will infest the rand package, not your package.
Enoch was right!
Enjoy the last years of Rome.