5 ms·

Even at 1680x1050, I find attached menu's really grating. I think it's the lost screen real estate because the larger they are, the more irritating I find them.

by adbge 16y ago

Even at 1680x1050, I find attached menu's really grating. I think it's the lost screen real estate because the larger they are, the more irritating I find them. On the other hand, Twitter went ahead and implemented a top attached menu, so maybe I'm in the minority. 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?

aarongough 16y ago
I think the path to learning about parsers is different for everyone. Personally I started by reading docs for parser generators like YACC and Bison, then just started messing around until I felt I understood what was going on. 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.
- silentbicycle 16y ago
  In my experience* , PEGs are really good for basic parsing (from basics to a few steps beyond advanced Perl regex hackery), but aren't really a complete substitute for other formal parsing methods. Having separate lexing and parsing phases can make things cleaner, because the grammar no longer has to keep track of purely lexical details like whitespace. PEGs are simple and easy to build interactively, though, so they occupy a very useful middle ground. I'm surprised they aren't more popular. * 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 http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html), which is based on the same formalism.
  - aarongough 16y ago
    My experience with really large scale grammars is extremely limited so it's good to hear your thoughts on that! 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!
    - silentbicycle 16y ago
      LPEG is actually quite fast. (Often as fast or faster than well-tuned regexp implementations.) In general, Lua is usually faster than Ruby and JS because the language itself seems to have been engineered with a very clear understanding of where the language could be expressive/dynamic without unnecessarily sacrificing efficiency, and it's had a long time to mature. LPEG was written by one of the primary Lua authors, and it shows. If you're geeked about PEGs, I highly recommend reading the paper and then the source. There are some details specific to the Lua C API, but it shouldn't be that hard to port or understand in isolation.
silentbicycle 16y ago
Niklaus Wirth's _Compiler Construction_ (free online, http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf) has a good intro to parsing, though for better or worse it's skewed towards recursive-descent parsing and has a "hit the ground running / focus on theory later" style. 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 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.
- adbge 16y ago
  That is likely the most thorough, informative response I have ever received. I almost qualified that with "on the internet", but then I realized, hell, it's probably more informative than any response I've ever received anywhere. 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.

by adbge 16y ago

aarongough 16y ago

I think the path to learning about parsers is different for everyone. Personally I started by reading docs for parser generators like YACC and Bison, then just started messing around until I felt I understood what was going on. 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.

silentbicycle 16y ago
In my experience* , PEGs are really good for basic parsing (from basics to a few steps beyond advanced Perl regex hackery), but aren't really a complete substitute for other formal parsing methods. Having separate lexing and parsing phases can make things cleaner, because the grammar no longer has to keep track of purely lexical details like whitespace. PEGs are simple and easy to build interactively, though, so they occupy a very useful middle ground. I'm surprised they aren't more popular. * 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 http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html), which is based on the same formalism.
- aarongough 16y ago
  My experience with really large scale grammars is extremely limited so it's good to hear your thoughts on that! 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!
  - silentbicycle 16y ago
    LPEG is actually quite fast. (Often as fast or faster than well-tuned regexp implementations.) In general, Lua is usually faster than Ruby and JS because the language itself seems to have been engineered with a very clear understanding of where the language could be expressive/dynamic without unnecessarily sacrificing efficiency, and it's had a long time to mature. LPEG was written by one of the primary Lua authors, and it shows. If you're geeked about PEGs, I highly recommend reading the paper and then the source. There are some details specific to the Lua C API, but it shouldn't be that hard to port or understand in isolation.

silentbicycle 16y ago

Niklaus Wirth's _Compiler Construction_ (free online, http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf) has a good intro to parsing, though for better or worse it's skewed towards recursive-descent parsing and has a "hit the ground running / focus on theory later" style. 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 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.

adbge 16y ago
That is likely the most thorough, informative response I have ever received. I almost qualified that with "on the internet", but then I realized, hell, it's probably more informative than any response I've ever received anywhere. 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.