Re:Parsing Techniques - A Practical Guide
by barrkel on Monday February 20, 2012 @03:05AM
(#3611707)
Parser combinator libraries are usually just embedded DSLs for constructing data structures (implicitly or explicitly) that are then interpreted during traversal, mostly in a way which has equivalent power to LL(1) or LL with backtracking - and frequently without the advantages of a "proper" analysis, such as detection of grammar ambiguities that you need first and follow sets to find. They're very cute, IMO; an appealing piece of hackery. I wouldn't try and push them much beyond fairly small ad-hoc parsing problems though. At core, they are a form of metaprogramming, where the text of your combinator expressions is a program that writes a program, and the extra distance your code needs to go through to get to the hardware is liable to introduce problems: either unforseen issues with the library, unexpected overuse of CPU or memory, or hard to diagnose errors.
PEGs, meanwhile, are all-out backtracking exponential matchers that try and get back the performance by spending memory on memoizing. A PEG parser would be my last choice in writing a parser, unless I had to recognize a complex language with no tools and almost no time, but plentiful CPU and memory. With tools, I'd prefer GLR parsing if the problem is hard enough; with time, I'd prefer hand-written LL(k) recursive descent, which gives substantial flexibility. Most commercial compilers use hand-written recursive descent for a reason.
In summary, if you have good knowledge of even just LL(1) alone, you should be able to understand how both parser combinator libraries and PEG parsers work very easily, and also see why they can be problematic. So I wouldn't be too fast to dismiss the book as dated.
PEGs, meanwhile, are all-out backtracking exponential matchers that try and get back the performance by spending memory on memoizing. A PEG parser would be my last choice in writing a parser, unless I had to recognize a complex language with no tools and almost no time, but plentiful CPU and memory. With tools, I'd prefer GLR parsing if the problem is hard enough; with time, I'd prefer hand-written LL(k) recursive descent, which gives substantial flexibility. Most commercial compilers use hand-written recursive descent for a reason.
In summary, if you have good knowledge of even just LL(1) alone, you should be able to understand how both parser combinator libraries and PEG parsers work very easily, and also see why they can be problematic. So I wouldn't be too fast to dismiss the book as dated.