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

Writing Parsers Like it is 2017 [pdf]

spw17.langsec.org

Post reply on HN
Print view View original

11–20 of 50 posts

Re: Writing Parsers Like it is 2017 [pdf]

#11

Post by wtetzner »

Analemma_ wrote: post #5

Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers? Even if mathematically they can't be perfect, could we have "good enough" ones? Nobody uses parser generators because even though P.G.s "work" on the barest level of ingesting source code and spitting an AST, they don't do anything beyond that. For example, trying to get helpful error m…

> Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers?

Isn't that basically what PEG parser generators are?

Re: Writing Parsers Like it is 2017 [pdf]

#12

Post by dukoid »

mattnewport wrote: post #10
geal wrote: post #9

Earlier quoted context omitted.

(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…

I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.

References: https://stackoverflow.com/questions/6319086/are-gcc-and-clan...

Re: Writing Parsers Like it is 2017 [pdf]

#13

Post by dukoid »

Analemma_ wrote: post #5

Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers? Even if mathematically they can't be perfect, could we have "good enough" ones? Nobody uses parser generators because even though P.G.s "work" on the barest level of ingesting source code and spitting an AST, they don't do anything beyond that. For example, trying to get helpful error m…

For my parsing pet project(s), the following structure seems to serve me best:

- Recursive descent parser for statements

- "Canned" configurable expression parser for expressions: https://github.com/stefanhaustein/expressionparser

- Both use a simple regex based generic tokenizer

- In more complex cases, parse the expressions to an unresolved syntax tree first (constructed from the bottom), then resolve the tree in a secondary top-down step (potentially to a linear representation).

Re: Writing Parsers Like it is 2017 [pdf]

#14

Post by amelius »

mattnewport wrote: post #10
geal wrote: post #9

Earlier quoted context omitted.

(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…

I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.

I suppose that's because they take the standpoint that they have so much testing code available, that any conflicts with the grammar are easily found.

However, in general, you can easily shoot yourself in the foot with a handwritten parser, because you can't see the conflicts by looking at the code locally.

Re: Writing Parsers Like it is 2017 [pdf]

#15

Post by kmill »

Analemma_ wrote: post #5

Is it possible to have "parser generators" (not necessarily in the formal sense of the term) that produce recursive descent parsers? Even if mathematically they can't be perfect, could we have "good enough" ones? Nobody uses parser generators because even though P.G.s "work" on the barest level of ingesting source code and spitting an AST, they don't do anything beyond that. For example, trying to get helpful error m…

Are you just talking about making parser generators for LL(k) grammars?

It's fairly straightforward to make one. One exercise in Wirth's short book Compiler Construction is to make an LL(1) parser generator. You even make it check for ambiguities. (I've even found it useful on a couple occasions.)

Re: Writing Parsers Like it is 2017 [pdf]

#16

Post by amelius »

dukoid wrote: post #12
mattnewport wrote: post #10

Earlier quoted context omitted.

I thought most real world compilers tend to be hand written rather than using a generator? By no means an expert but that's something I've heard and know to be true for many real world compilers.

References: https://stackoverflow.com/questions/6319086/are-gcc-and-clan...

They probably should have used this instead: http://scottmcpeak.com/elkhound/

Re: Writing Parsers Like it is 2017 [pdf]

#17

Post by amelius »

geal wrote: post #9
amelius wrote: post #4

Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.

(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…

> For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use.

That's not a theoretical issue, but more a practical issue.

> you'll have to hack around the generator's limitations

You're probably thinking of LALR(1) class generators. But we have GLR parser generators for a long time now, and they are very flexible and have little limitations. See e.g. [1].

[1] http://scottmcpeak.com/elkhound/

Re: Writing Parsers Like it is 2017 [pdf]

#18

Post by nickpsecurity »

amelius wrote: post #17
geal wrote: post #9

Earlier quoted context omitted.

(one of the authors here): parser generators are generally good for one thing: parsing programming languages. For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. I often meet people that tell me they want the parser generator to end all parsers. But for most real world formats, you'll have to hack around the generator's limitations. Theoretically, pa…

> For more complex formats, where you have to carry state around, or binary formats, they're extremely cumbersome to use. That's not a theoretical issue, but more a practical issue. > you'll have to hack around the generator's limitations You're probably thinking of LALR(1) class generators. But we have GLR parser generators for a long time now, and they are very flexible and have little limitations. See e.g. [1]. [1…

Or especially Semantic Designs' tool that gets a ton of mileage out of GLR:

http://semanticdesigns.com/Products/DMS/DMSToolkit.html

Re: Writing Parsers Like it is 2017 [pdf]

#19

Post by nickpsecurity »

amelius wrote: post #4

Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.

On top of that, we even have some that are formally verified or validating that could be tied into Rust.

https://arxiv.org/pdf/1105.2576.pdf

http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf

http://users.cecs.anu.edu.au/~aditi/esop09_submission_16.pdf

One of those handled most of C99 standard.

Re: Writing Parsers Like it is 2017 [pdf]

#20

Post by adwhit »

amelius wrote: post #4

Parser combinators are less powerful than what parser generators can do, in terms of expressiveness and efficiency. And we've known parser generators since the 70s. So I'm not sure what the point is of the title of the article.

It may be true that parser generators are superior from a technical point of view (I can't comment), but parser combinators sure can be nice to use. I very recently used nom to implement a parser for a structured text format, it feels wonderfully expressive and you can knock together a reasonably sophisticated parser in a matter of hours. Performance-wise, it is zero-copy and chomps through a 100MB file in less than half a second on my crappy laptop, so plenty fast enough for most situations.
Post reply on HN