Simple language generator for experienced programmer

I would like a "language generator" for a small right-regular grammar (i.e. 5 production rules and about 10 terminals). The generator parses the grammar and generates all possible words of the language. The syntax should allow annotation of production rules so that the generated words will also be annotated. The grammar should be allowed to contain insertion/deletion/and replacement rules. You will find an example and a detailed description on the project clarification board. The output should be Java sources with a main method to run the example. I think the task is easy for a programmer with experience in compiler building or NLP, but difficult for other people, so please consider this. In fact, two providers have already failed! In case of success, there will be further related projects.