Some meditation (I didn't re(veal|ad) your code) ...

As far as I understand the complication is in the grammar and not in the auto-completion and you are shying away from implementing/maintaining a state-machine.

From your description I understand this (pseudo syntax)

• [ select | kill ] @animals [ give @foods | take_to @places ]

But it seems to me that kill shouldn't allow further commands

• [ kill @animals | select @animals [ give @foods | take_to @places ] ]

It's also not clear if give and take_to can be followed by further commands

• [ kill @animals | select @animals [ give @foods | take_to @places ] ]? # quantifier ? one-or-more commands

Or if you can have multiple items:

• [ kill @animals | select @animals [ give (@foods)? | take_to @places ] ] # ? one-or-more food items

What about senseless food-selection by animal?

select camel give fish #???

hence we need

• ... select @animals [ give ( @{$foods{$select}} )? ... # updated

The next question is validation , what happens if a someone manually types select horse ... which isn't in the animal-list, shouldn't that be rejected?

My naïve approach would be to implement/translate that grammar to a nested regex and input that doesn't match is rejected.

Typing TAB after a command displays the completion list.²

But I have a hunch there are already better ways to implement such grammars on CPAN.

²) from what I remember this can be done with Term::ReadLine by adding call backs for evaluation and expansion.