Live data from Hacker News

Parsing: The Solved Problem That Isn't (2011)

tratt.net

11–20 of 71 posts

Re: Parsing: The Solved Problem That Isn't (2011)

#11
It may also relevant to mention the language-theoretic security research program ("LANGSEC").

http://langsec.org/

They've pointed out that the difficulty of parsing, and in a sense our overconfidence that we can just code up parsers for random languages and input formats when we need them, is a pretty pervasive source of security bugs.

A lot of those bugs can occur when you have two different parsers that have a different notion of what language they're supposed to recognize, so it's possible to construct an input whose meaning the two parsers disagree on. That can have pretty serious ramifications if, for example, the first parser is deciding whether a requested action is authorized and the second parser is carrying out the action!

I'm kind of sad about this because I love whipping up regular expressions to extract data even from things that regular expressions technically can't handle correctly. But there's a good argument to be made that this habit is playing with fire much of the time, at least in systems that will end up handling untrusted input. And the Shellshock bug is a recent example of the way that your intuitions about whether your software will "handle untrusted input" in some use case can go out of date.

Re: Parsing: The Solved Problem That Isn't (2011)

#12
post #2

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…

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

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).

Re: Parsing: The Solved Problem That Isn't (2011)

#13
post #11

It may also relevant to mention the language-theoretic security research program ("LANGSEC"). http://langsec.org/ They've pointed out that the difficulty of parsing, and in a sense our overconfidence that we can just code up parsers for random languages and input formats when we need them, is a pretty pervasive source of security bugs. A lot of those bugs can occur when you have two different parsers that have a diff…

See also this paper: http://www.ieee-security.org/TC/SPW2014/papers/5103a198.PDF. The authors implement a pdf file format parser and find bugs in pretty much all of the existing implementations. Basically pdf is a pretty shitty file format with several ill-defined corner cases. This is one of the reasons PDFs tend to be vectors for security breaches.

Re: Parsing: The Solved Problem That Isn't (2011)

#14
post #10
post #8

I've wondered why most existing LALR(1) parser generators are not replaced with LR parser generators with a higher look-ahead than 1. This improvement, considering that our computational power today does not justify these restrictions any more, would be Pareto-optimal even while it is being decided what completely alternative strategies (PEGs, boolean grammars, parser combinators, etc.) will take over.

ANTLR is LL(*).

Right. It's kinda impressive what it can do. On one end of the spectrum it has all the power of PEGs and on the other it has the predicative capabilities of LL(k) so there is basically no restriction on the kind of grammar it can generate parsers for.

Re: Parsing: The Solved Problem That Isn't (2011)

#15
post #12

Earlier quoted context omitted.

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

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.

Re: Parsing: The Solved Problem That Isn't (2011)

#16
post #2

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…

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

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.

Re: Parsing: The Solved Problem That Isn't (2011)

#20
This is probably a good place to ask; I've wanted to build a language myself -- whats the best place to begin learning about parsers and the like? About a decade ago I asked this question and was told to read the "Dragon book" but I was far too young and lacked experience. Now I really want to get stuck into something outside of my day-to-day web stuff.
Post reply on HN