HN Explorer

Ask HN: Book recommendations for grammar as it relates to computing?

8 points by davegauer ↗ HN
Though any book on compilers or computation will make some reference to grammar (defining terms such as regular vs. non-regular), it is often in passing. I'm interested in a deeper dive. I believe a lot of the terminology we use comes from Chomsky, but his own books seem to be focused on humans and language learning. I'd like a wide survey of the field, but as it relates to making computers do things or encoding information. Oh, and while I'm being wishful, one written in layman's terms.

Is there a "Grammar as it Relates to Computing for Dummies"?

9 comments

[ 4.4 ms ] story [ 30.2 ms ] thread
harrada256
"Compilers: Principles, Techniques, and Tools" or "The Dragon Book" as it is informally known was always recommended on compsci courses I have taken. It has a section within "Syntax Analysis" which covers context-free grammars.
davegauer
Thank you. Indeed, I have The Dragon Book and I think it's a great resource! But it does leave me with the feeling that I'm learning about a practical byproduct of a whole other field of study. In other words, I feel like I've seen just one useful tip of an iceberg that might have other really interesting things in it.

In yet other words: I don't know what I don't know about grammar.

cafard
There is also The Cinderella Book by Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation.
davegauer
Oooh, thank you! I had heard of "The Cinderella Book" before, but hadn't looked into it. Seems especially promising given the title that came before it:

> The first edition in turn constituted a major revision of a previous textbook also written by Hopcroft and Ullman, entitled Formal Languages and Their Relation to Automata.

https://en.wikipedia.org/wiki/Introduction_to_Automata_Theor...

Used copy ordered.

Searching for that title also lead me to _Introduction to Formal Languages_ by Gyorgy E. Revesz, which also looks like a good fit and which Dover is currently printing as one of their reasonably-priced paperbacks!

open-source-ux
Does 'Backus–Naur form' meet your interest? It is a formal way of describing the syntax of a programming language, but I suspect it is not used much for modern programming languages:

https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form

davegauer
Yes, that very much falls under the area of interest! And following one of the Wikipedia citation links:

> Among his [Backus's] library at the time were the works of the modern philosopher and theorist Noam Chomsky, who studied the evolution of the human intellect and of written and spoken language in parallel. Chomsky was developing a symbolic syntax with which to frame his concepts of languages within languages, in the study of how sociology affects grammar. Backus borrowed some of Chomsky's concepts, including the idea that a symbology could represent a computer language...even one that didn't yet exist.

So again, it all seems to point back to Noam Chomsky. I do have a copy of Chomsky's _Aspects of the Theory of Syntax_ coming to my home soon. Should be interesting.

layer8
This might be what you’re looking for: https://www.amazon.com/Parsing-Techniques-Practical-Monograp...

Not exactly cheap, but pretty good.

There’s also https://www.amazon.com/Automata-Formal-Languages-Turing-Mach... which focuses more on the Chomsky hierarchy and automata, and doesn’t go into practical parsers and the related grammar types like the first book.

davegauer
Yeah, _Automata, Formal Languages, and Turing Machines_ looks like a good topic match (it seems "formal language" is the keyword I was missing?) and Parsing Techniques sounds like an excellent book as well. Thanks for the recommendations!
layer8
Yes, you could start with the second book for the basics of formal language theory and then delve into the first book for the various parsing approaches.