I've always wondered how people from very different regions, with no roots in common, were able to understand each other, and even learn new languages, back in the days were "grammar books" were not available. For example, Christian missionaries trying to teach the Bible in Africa, or Spanish conquistadores with the native Americans.
You might be interested in this section of our Popular Questions wiki (the link is in the sidebar): Cross-cultural communication and lingua francas.
A 'grammar book' as you put it is the worst way to learn a language, immersion is the best way to learn. Ancient traders and explorers would gradually pick up phrases from locals, the same way you would if you went to live in Paris for a year.