http://php.net/preg_match
mmm..... digamos SI la cadena (el <a>) no tiene tal... atributo ENTONCES lo agregamos...
preg_match('/<a atributo\s*=\s*([\'\"])*(.+?)(\\1)?/i', $link)
luego reemplazar es mas facil....
$link = str_replace('<a', '<a atributo="xyz"', $link);