views:

597

answers:

9

What is a good book that covers the topics of grammars (context-free and context-sensitive) and their notations (EBNF, BNF, etc), syntax, type and programming language theory, etc?

I'm not really digging the textbook we used at my school for our "Programming Languages" class and I'm looking to supplement some of the topics we covered with a different text.

If you have had good experience with a PL theory book that covers these topics please suggest it!

+4  A: 

I'd highly recommend The Dragon Book as it covers the basics fairly well and is a standard text. Another good book that goes over a simple LL(k) language, Oberon, a Pascal derivative, using a recursive descent approach is authored by Wirth (the creator of Pascal) and it is called Compiler Construction. It is a very easy read and is also fairly easy to understand.

Adam Markowitz
+4  A: 

Concepts, Techniques, and Models of Computer Programming is highly regarded by the Lambda the Ultimate community. I bought a copy because it is mentioned there constantly but I haven't actually started reading it yet. I figure if they like it it's probably at least worth considering.

+2  A: 

Structure and Interpretation of Computer Programs.
(http://mitpress.mit.edu/sicp/full-text/book/book.html)

Eric
+3  A: 

Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

Also you don't fully understand a language till you understand it's compiler so you might take a look at this as well Compilers: Principles, Techniques, & Tools with Gradiance by Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman

Piotr Dobrogost
+1 We used the Ullman book at University, it's very good!
Ed Woodcock
+1 for Ullman. My CS Theory class didn't use it, but I swear that book got me through the course.
Thomas Owens
+1 for Hopcroft/Ullman
Rodrigo
+2  A: 

Parsing Techniques - A Practical Guide - Dick Grune (free)

leppie
+1  A: 

Besides SICP, Programming Languages: Application and Interpretation by Shriram Krishnamurthi is a good one because it explains advanced concepts clearly and in a very direct style. Also the PDF is available under a CreativeCommons BY-NC-SA license.

However, those books are more about interpretation and semantics than parsing, but to be honest I'm not sure parsing is such an interesting subject per se :-). Syntaxes that require a powerful algorithm to parse tend to be ambiguous for humans, and inconvenient to handle by tools (coloring, formatters, refactorings). Anyway, the dragon book explains all the traditional approaches, and you can read about the recent development of parser combinators and PEGs (parsing expression grammars) online.

Damien Pollet
A: 

Types and Programming Languages by Benjamin Pierce. It's not for beginners, but once you've got a solid grasp on the Dragon Book, this is the best book on the theory and practice of type systems that I've run into so far.

There's a sequel, Advanced Topics in Types and Programming Languages, but I haven't read that one yet.

Meredith L. Patterson
A: 

Essentials of Programming Languages (EoPL) is by far the best book on programming language theory. The book starts with a very simple language based on the lambda calculus and cumulatively adds new constructs and shows the effect the constructs have on the expressive power of the language and on an interpreter of the language.

In your post you also ask for a book that covers context-free grammars, EBNF and the like. For that, I highly recommend Programing Language Pragmatics. I think that it takes more work than EoPL but it's well worth the effort.

My understanding is that EoPL was largely inspired by Structure and Interpretation of Computer Programs. The two together arguably make for the greatest complementary pair of computer science books ever written.

Jason
A: 

I like this one.... Programming Language Syntax and Semantics by David Watt

LB