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

31–40 of 50 posts

Re: Writing Parsers Like it is 2017 [pdf]

#31

Post by c-cube »

kazinator wrote: post #30
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.

Parser combinators let you put a breakpoint on a rule and get a call trace. (Same with plain old recursive descent or anything just involving function calls.) That alone pretty much wipes out any remaining advantages of parser generators, in which the "cow" of your rules has been turned into a "hamburger" state machine that is very difficult to follow, usually having very poor debug support compared to the maturity o…

That's more a proof that the grammar of C++ is absolutely terrible. More modern languages such as rust have been carefully designed to be parsable by non-necronomicon-level code.

Re: Writing Parsers Like it is 2017 [pdf]

#32

Post by coldtea »

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.

Well, we gladly trade power and efficiency all the time for more intuitiveness and ease of use in computing...

Re: Writing Parsers Like it is 2017 [pdf]

#33

Post by mattnewport »

c-cube wrote: post #31
kazinator wrote: post #30

Earlier quoted context omitted.

Parser combinators let you put a breakpoint on a rule and get a call trace. (Same with plain old recursive descent or anything just involving function calls.) That alone pretty much wipes out any remaining advantages of parser generators, in which the "cow" of your rules has been turned into a "hamburger" state machine that is very difficult to follow, usually having very poor debug support compared to the maturity o…

That's more a proof that the grammar of C++ is absolutely terrible. More modern languages such as rust have been carefully designed to be parsable by non-necronomicon-level code.

File that next to the 'proof' that the grammar of English is absolutely terrible. More modern languages such as Esperanto have been carefully designed to be learnable by regular human beings.

I know which language I'd rather be fluent in.

Re: Writing Parsers Like it is 2017 [pdf]

#34

Post by kibwen »

mattnewport wrote: post #33
c-cube wrote: post #31

Earlier quoted context omitted.

That's more a proof that the grammar of C++ is absolutely terrible. More modern languages such as rust have been carefully designed to be parsable by non-necronomicon-level code.

File that next to the 'proof' that the grammar of English is absolutely terrible. More modern languages such as Esperanto have been carefully designed to be learnable by regular human beings. I know which language I'd rather be fluent in.

What is this trying to say? If a crucial portion of your job depends on the ability to parse a language (and it does, if you're a programmer who uses an IDE), then that's a point in favor of a language that's LL(1) rather than context-dependent. Making an analogy to natural languages here isn't relevant.

Re: Writing Parsers Like it is 2017 [pdf]

#35

Post by saywatnow »

This should be titled more honestly: perhaps something like "Case studies in rapidly replacing dangerous C parser code with Rust using nom".

The examples are interesting and well presented. But the first sections trying to put a veneer of respectability on rust-all-the-things were a bit rough and got my cynic sense tingling.

Yes, you believe Rust will produce better results: don't try to justify that with facts you don't have ("Several languages were tested .." bullshit, unless you show some data. Likewise the assertions about type-safety and no-GC being essential properties). The data you do have (implementations produced and integrated and tested in a paper-like time frame) are valuable, unfortunately they're cheapened/buried under this false veneer.

Re: Writing Parsers Like it is 2017 [pdf]

#36

Post by JoelJacobson »

Are there any Context-sensitive algorithms/parsers/generators?

The list at https://en.wikipedia.org/wiki/Context-sensitive_grammar only contains two links, where one of them, "LuZc" seems completely dead with "lorem ipsum" under Downloads, and the other "bnf2xml" seems to be misplaced since BNF is not context-sensitive.

Re: Writing Parsers Like it is 2017 [pdf]

#37

Post by tom_mellior »

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…

> trying to get helpful error messages

Menhir is a parser generator that tries to do that: http://gallium.inria.fr/~fpottier/slides/fpottier-2015-11-ou... (Don't get scared by the first slide; the title is in French, the rest is in English.)

> formally verified

Menhir has been used for a formally verified parser for C: http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf

The result is in CompCert: https://github.com/AbsInt/CompCert/tree/master/cparser

Re: Writing Parsers Like it is 2017 [pdf]

#38

Post by sfvisser »

JoelJacobson wrote: post #36

Are there any Context-sensitive algorithms/parsers/generators? The list at https://en.wikipedia.org/wiki/Context-sensitive_grammar only contains two links, where one of them, "LuZc" seems completely dead with "lorem ipsum" under Downloads, and the other "bnf2xml" seems to be misplaced since BNF is not context-sensitive.

Monadic parser combinators are context-sensitive, because you can arbitrarily branch your parser based on previously parsed content.

Re: Writing Parsers Like it is 2017 [pdf]

#39

Post by geal »

saywatnow wrote: post #35

This should be titled more honestly: perhaps something like "Case studies in rapidly replacing dangerous C parser code with Rust using nom". The examples are interesting and well presented. But the first sections trying to put a veneer of respectability on rust-all-the-things were a bit rough and got my cynic sense tingling. Yes, you believe Rust will produce better results: don't try to justify that with facts you d…

We in fact tested multiple languages. I can even point you to various works done at the ANSSI like https://github.com/ANSSI-FR/bootcode_parser (python) or https://github.com/ANSSI-FR/caradoc (OCaml). I tried Haskell for VLC and it was not really suited for it (GC pauses in a synchronized media pipepline, and not meant to be called from C). But this was not a paper about comparing parser implementations.

Type-safety and lack of garbage collection are essential properties, could you tell me why you don't think that's the case?

Giving the reason for our language choice felt useful. Otherwise, it would have really looked like Rust developers steamrolling into projects :)

Re: Writing Parsers Like it is 2017 [pdf]

#40

Post by kazinator »

c-cube wrote: post #31
kazinator wrote: post #30

Earlier quoted context omitted.

Parser combinators let you put a breakpoint on a rule and get a call trace. (Same with plain old recursive descent or anything just involving function calls.) That alone pretty much wipes out any remaining advantages of parser generators, in which the "cow" of your rules has been turned into a "hamburger" state machine that is very difficult to follow, usually having very poor debug support compared to the maturity o…

That's more a proof that the grammar of C++ is absolutely terrible. More modern languages such as rust have been carefully designed to be parsable by non-necronomicon-level code.

> That's more a proof that the grammar of C++ is absolutely terrible.

Oh, I took that for granted as the basis of my remarks: far from a random choice on my part.

Post reply on HN