Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

tratt.net

Post reply on HN
Print view View original

41–50 of 71 posts

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

#41

Post by nly »

dkarapetyan wrote: post #13
schoen wrote: 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.

How comforting it is that the paper is presented as a PDF ;)

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

#42

Post by sklogic »

jbangert wrote: post #36
sklogic wrote: post #35

How exactly "PEGs are rather inexpressive"? Still the same BNF, with some nice bells and whistles added. As for the left recursion, it's not a big deal. You mostly need left recursion for the binary expressions, and they are much better served by a Pratt parsing (which is trivial to mix with Packrat anyway). I moved to PEG+Pratt exclusively and never needed anything beyond that, for even craziest grammars imaginable.

One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)

I like this idea! Mind if I steal it for my PEG generator?

This is probably the best property of PEGs, they're extremely extensible and flexible, you can add features not possible in any other parsing technology, including high order parsers, dynamic extensibility, etc.

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

#43

Post by wodenokoto »

jblow wrote: post #38

It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be. If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a str…

That's horrible advice. Some problems are really complex and can't be solved just by working from A to B.

Your parser will probably not end up being able to handle the problems outlined in the article unless you take that theory into account before starting to program.

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

#44

Post by sovande »

jbangert wrote: post #36
sklogic wrote: post #35

How exactly "PEGs are rather inexpressive"? Still the same BNF, with some nice bells and whistles added. As for the left recursion, it's not a big deal. You mostly need left recursion for the binary expressions, and they are much better served by a Pratt parsing (which is trivial to mix with Packrat anyway). I moved to PEG+Pratt exclusively and never needed anything beyond that, for even craziest grammars imaginable.

One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)

Another issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.

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

#45

Post by sklogic »

sovande wrote: post #44
jbangert wrote: post #36

Earlier quoted context omitted.

One issue with PEG's (and other parsers) is that it doesn't address (unbounded) count fields (or bounded count fields in an elegant manner) or offsets. This means a pure PEG can't express e.g. PDF or ZIP files. To address this, we built a PEG-based parser generator with a few new features, Nail (paper at OSDI 14, github.com/jbangert/nail)

Another issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.

How is it so? If you're referring to the Packrat memoisation (which is not the only possible PEG implementation), you can do a lot of memory optimisation, like discarding memoised entries based on some rules (e.g., once a top-level entry, like a function or a class definition is parsed, all the alternative interpretations can be thrown away). You can memoise complex entries but re-parse simple tokens. And many, many more.

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

#46

Post by tjaerv »

Flow wrote: post #28
girvo wrote: post #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.

This is exactly what you want: https://www.coursera.org/course/compilers

Seconded. This was a good course.

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

#47

Post by justinpombrio »

c3d wrote: post #37

The XL programming language ( http://xlr.sf.net ) has a rather unique approach to parsing. There is a short article about it here: http://grenouille-bouillie.blogspot.fr/2010/06/xl-axioms-rec... . XL features 8 simple node types, 4 leafs (integer, real, text, name/symbol) and 4 inner nodes (infix, prefix, postfix and block). With that, you can use a rather standard looking syntax, yet have an inner parse tree structu…

Judging from the article, if you parsed "if 3", you'd get back out

    (prefix if 3)
instead of an error, since `if` is just a regular prefix operator. So, presumably there's some sort of well-formedness checking that goes on after parsing? Does anyone know more? The website says very little.

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

#48

Post by breuleux »

c3d wrote: post #37

The XL programming language ( http://xlr.sf.net ) has a rather unique approach to parsing. There is a short article about it here: http://grenouille-bouillie.blogspot.fr/2010/06/xl-axioms-rec... . XL features 8 simple node types, 4 leafs (integer, real, text, name/symbol) and 4 inner nodes (infix, prefix, postfix and block). With that, you can use a rather standard looking syntax, yet have an inner parse tree structu…

I designed the Earl Grey language (http://breuleux.github.io/earl-grey/repl/) on pretty much exactly the same principle, it's pretty interesting to see someone else had the same idea. Operator precedence grammars are surprisingly powerful and pretty simple to write (you can write a working parser in ~100 lines of Python or JavaScript, including support for multifix).

I did simplify the AST further than XL and added a few invariants. I have 3 leafs (literal, symbol, void) and 3 inner (send, multi, data). The inners roughly work like this:

    f x             (send f x)
    [x]             x
    [x, y, ...]     (multi x y ...)
    {x, y, ...}     (data x y ...)
    a + b           (send + (data a b))
    + a             (send + (data (void) a))
    a +             (send + (data a (void)))
[] serve as grouping brackets and are therefore purposefully erased from the parse tree if they only contain one expression. Prefix/postfix operators are interpreted as infix operators that have a blank operand on either side. Infix operators are themselves reduced to send/data, so "a + b" is equivalent to "[+]{a, b}". I find that a bit more robust and easier to manipulate generically.

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

#49

Post by sovande »

sklogic wrote: post #45
sovande wrote: post #44

Earlier quoted context omitted.

Another issue is that it uses at least the same memory as the the input. Not that I'm a PEG expert, but it also basically feels like a formalised recursive decent parser. Nothing wrong with that, but changing the grammar afterwards can have a rippling effect and require much more work than with a traditional LALR parser.

How is it so? If you're referring to the Packrat memoisation (which is not the only possible PEG implementation), you can do a lot of memory optimisation, like discarding memoised entries based on some rules (e.g., once a top-level entry, like a function or a class definition is parsed, all the alternative interpretations can be thrown away). You can memoise complex entries but re-parse simple tokens. And many, many…

I was and also when scanning/lexing. My limited PEG parsing experience is with peg/leg by http://piumarta.com/software/peg/ and http://pegjs.majda.cz which is a Javascript PEG parser. Both very cool projects.

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

#50

Post by sklogic »

sovande wrote: post #49
sklogic wrote: post #45

Earlier quoted context omitted.

How is it so? If you're referring to the Packrat memoisation (which is not the only possible PEG implementation), you can do a lot of memory optimisation, like discarding memoised entries based on some rules (e.g., once a top-level entry, like a function or a class definition is parsed, all the alternative interpretations can be thrown away). You can memoise complex entries but re-parse simple tokens. And many, many…

I was and also when scanning/lexing. My limited PEG parsing experience is with peg/leg by http://piumarta.com/software/peg/ and http://pegjs.majda.cz which is a Javascript PEG parser. Both very cool projects.

Looks like they do not include the optimisations I mentioned. But for this sort of use cases that would have been an overkill anyway.
Post reply on HN