Hacker News Reader

Comment by wslh | Hacker News Reader

I just found this "old" article looking for an easy to use parser in C++ (in Visual Studio, GCC, and CLang). I think the current state of parsers in C++ is... how to say it... terrible! flex and bison doesn't look like C++, Boost Spirit too much ado, ANTLR4 doesn't support it yet and setting up ANTLR3 in Visual Studio can be explained in a few steps if it were explained in a straightforward way.

When you look at the simplicity of OMeta[1] you feel the difference. But I am not aware of any (production ready) OMeta implementation for C++.

[1] http://tinlizzie.org/ometa/

View on HN

The 'Accent' compiler-compiler can have some advantages over yacc.

http://accent.compilertools.net

Thanks, I didn't have it on my list! I will try it.

If you don't mind incredibly long compile times for any moderately complex grammar, PEGTL is pretty straightforward compared to other alternatives.

http://code.google.com/p/pegtl/

Both are based in Bryan Ford's packrat (PEG is Ford's too). OMeta is more like PEGTL in that it's a set of facilities/library at a highish level, more than a particular grammar system (they're all packrat parsers).

http://bford.info/packrat/

It's all about descent parsing and memoisation (thus the name).

pegtl is not actually a packrat parser. Not all PEGs and absolutely not all recursive descent parsers are packrats.

And actually, my experience with packrat parsers (mostly in ruby) in other languages has been that they actually slow things down on moderately or more complex grammars by massively exploding memory use and thus allocation pressures. Turning it off can make it faster, especially on complex grammars. It's a pretty good case study in how optimizing an O(n^2) worst case to O(n) does not always improve things.

That said, I'm not against the principle, but the shotgun approach to it can be brutally bad. You really only want to memoize the paths that are actually likely to backtrack. Or simple grammars where O(n^2) memory use is not going to balloon your memory use too much it's a clear win.

> Not all PEGs and absolutely not all recursive descent parsers are packrats.

Of course not, see the link I posted. PEGs are TDPL and recursive descent (not the other way around), and an alternative to CFGs. PEGs were coined by Bryan Ford, who then coined packrat parsing based on them.

You want to do smarter things than just memoising everything, yeah. Especially for complex grammars.

See http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste51...

I've been working on a new PEG parsing algorithm, and though my first crack at it was way too slow and I still haven't finished debugging the second version, I was able to show that packrat parsing had about a 40% runtime hit over recursive descent for well-behaved inputs on some common grammars (and linear memory usage vs. constant).

Can't edit anymore, but I want to clarify that I mean that the grammar takes a long time to compile. The performance of the resulting parser is pretty good.

Reply on news.ycombinator.com