So comparing this to the previous sentence, does the (plural) definite article "na" make the difference between "cat na leabharlainne = the library's cat" vs. "cat leabharlainne = a library cat" (whatever a 'library cat' is?!) ?
That could explain why "leabhar leabharlainne = a library book" as opposed to "a library's book".
Of course it would then beg the question of why "hata fir = a man's hat" as opposed to "a man hat" (again, ignoring whatever that is for now!) ?
EDIT; I just thought of a 'man bag' which is a thing in English, so certainly such constructions can make sense in English at least some of the time.