Anyways, back on topic, do you (or any HNers) have any recommendations on how to get started with formal grammars and parsers? Is there a canonical introductory text?
After that, you could dig deeper with Andrew Appel's _Modern Compiler Techniques in {ML,C}_ books. The ML one is better, IMHO. Those cover other methods (LL, LALR, SLR, etc.) in greater detail, and I'd also recommend either for learning compilers in a heartbeat. (Appel's _Compiling with Continuations_ is also excellent, but doesn't cover parsing.)
Following that, Dick Grune's _Parsing Techniques: A Practical Guide_ (http://www.few.vu.nl/~dick/PTAPG.html) is a good reference...and thorough. If you're reading it to learn the basics, it might seem a bit dry, but I think it's at a sweet spot between depth of coverage and deference to the extensive bibliography. I have the second edition; the first is free online. Not sure about the differences, but the coverage of fundamentals probably haven't changed much. Also, while the other two are compiler books with chapters on parsing, this one is 100% parsing, and gets to a lot of interesting parsing algorithms (e.g. Earley parsing) that don't usually get much love in compiler texts.
Some people will also recommend the Dragon book, but I think those three will be more helpful. I haven't read the new edition, but the old seems drier & less thorough than the Grune book, less direct than the Wirth book, and less modern than the Appel book.
Also: For learning lex and yacc, the intros in the _4.4BSD Programmer's Supplementary Documents_ ("PSD", included with OpenBSD and probably the other BSDs, and not hard to find online) are hard to beat. The O'Reilly _Lex and Yacc_ book somehow manages to be roughly ten times as long yet less informative.
And if you have full control over the syntax used, S-expressions (Lisp), RPN (Forth), or Lua/JSON will let you dodge the issue of parsing entirely.
I recently saw a news piece about a philanthropist helping people in poor African villages by simply building wells. The tribesmen were so grateful, one said "I wish he lives one hundred and fifty years so that he can continue helping people like us."
Well, Scott, thank you. I hope you live one hundred and fifty years.
And, thanks. :)
Picking a grammar that is fairly small is a definite help at the early stages which is why I chose S-Expressions for this post.
EDIT: getting started with lexers first may actually be an easier way to start. PEGs like in the article combine a lexer and parser, but understanding each separately is important.
* I haven't used Treetop or PEG.js, but I've done a lot with Lua's LPEG (http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html), which is based on the same formalism.
My main issue so far with PEGs is that the generators seem to produce parsers that are relatively slow. That being said I need to experiment with PEGs in languages other than Ruby. Thanks!
