Writing Parsers Like it is 2017 [pdf]

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.

Re: Writing Parsers Like it is 2017 [pdf]

#5

Post by Analemma_ » Wed, Jun 28, 2017, 7:52 PM UTC

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 messages (think: from old GCC to Clang) from a P.G.s output is close So instead everyone writes custom parsers, and that introduces these problems.

Can't we have smarter parser generators that do make debugging nice, but are still formally verified?

Re: Writing Parsers Like it is 2017 [pdf]

#6

Post by zoren » Wed, Jun 28, 2017, 7:55 PM UTC

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.

Are they? I thought parser combinators made parsing context sensitive grammars easier than when using parser generators.

Re: Writing Parsers Like it is 2017 [pdf]

#7

Post by zoren » Wed, Jun 28, 2017, 7:57 PM UTC

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…

I would claim ANTLR is such a tool.

Re: Writing Parsers Like it is 2017 [pdf]

#8

Post by egnehots » Wed, Jun 28, 2017, 8:09 PM UTC

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.

I think it's more a response to the wave of attacks against unsafe parsers, such as those used to read subtitles in media players.

Re: Writing Parsers Like it is 2017 [pdf]

#9

Post by geal » Wed, Jun 28, 2017, 8:19 PM UTC

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, parser combinators are less expressive, but they're just functions: you can write whatever you want inside a subparser, and integrate it with the rest. That approach works well, since we wrote a lot of complex parsers with nom.

Re: Writing Parsers Like it is 2017 [pdf]

#10

Post by mattnewport » Wed, Jun 28, 2017, 8:38 PM UTC

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…

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.