Una soluzione stupida ma semplice che mi viene in mente è

- assumi che le parole composte siano in realtà delle parole più grosse

- comincia a sostituire le parole partendo da quelle a maggior lunghezza

quindi ordini

(3)gallo giallo barbuto
(2)gallo giallo
(1)gallo

e sostituisci in ordine...

Altro problema: per evitare che venga sostituito il link appena creato al passaggio successivo devi aggiungere un flag...il flag potrebbe essere semplicemente un simbolo particolare o una parola (#,$,{ok},...)
Se la parola trovata ha il flag come prefisso non la modifichi più

Quindi quando trovi gallo giallo barbuto sostituisci con un link e preponi un #...al secondo passaggio trovi gallo giallo lo ignori perchè $string[$indice-1]=='#'....già fatto!