Are the examples all actual outputs of the program? It's entirely possible that my understanding of the grammar is off, but it looks like these examples are wrong:

$ echo 'cat dog' | trre 'c:bat|d:hog' bat hog

$ echo '' | trre ':a*' # <- do NOT do this dog

$ echo '' | trre ':(repeat-10-times){10}' dog