7 ms·
Writing Parsers Like it is 2017 [pdf]
- oldsj 9y agoSorry for the low effort comment but Clever Cloud is an awesome name
- ldoguin 9y agoThanks, it's a pretty cool product too. (yeah I work there)
- amelius 9y agoParser 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.
- zoren 9y agoAre they? I thought parser combinators made parsing context sensitive grammars easier than when using parser generators.
- egnehots 9y agoI think it's more a response to the wave of attacks against unsafe parsers, such as those used to read subtitles in media players.
- geal 9y ago(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.
- mattnewport 9y agoI 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.
- dukoid 9y agoReferences: https://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten https://stackoverflow.com/questions/6319086/are-gcc-and-clan...
- amelius 9y agoI 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.
- vidarh 9y agoIt's usually because getting proper (as in user-friendly) error reporting is a massively weak spot with ever parser generator I've seen to date. Conflicts is generally one of the least interesting problems in writing a parser unless you're designing a new language, and especially when hand writing recursive descent parsers, potential conflicts/ambiguities tend to become obvious quickly. For prototyping a new language, sure, use a parser generator to test the grammar. I too fall in the category of loving the idea of parser generator (and having written a few) but always falling back on hand-written parsers because the generators I've seen have all been inadequate. I hope that chances some day.
- nickpsecurity 9y agoOn 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 https://arxiv.org/pdf/1105.2576.pdf http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf http://gallium.inria.fr/~xleroy/publi/validated-parser.pdf http://users.cecs.anu.edu.au/~aditi/esop09_submission_16.pdf http://users.cecs.anu.edu.au/~aditi/esop09_submission_16.pdf One of those handled most of C99 standard.
- adwhit 9y agoIt 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.
- ufo 9y agoThe nicest thing about parser generators, IMO, is that they can warn you if your grammar is ambiguous.
- lgas 9y ago> So I'm not sure what the point is of the title of the article. The rest of the paper elaborates on the title.
- seanmcdirmid 9y agoAnd if you really care about error recovery, error messages, incremental processing, and tooling integration, writing a parser by hand via recursive descent is always a sure bet. There are good reasons why many production PLs don't even use generators.
- kazinator 9y agoParser 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 of the rest of the tooling. ("How come if I add a variant to ths rule, I get a reduce/reduce conflict in these five other rules elsewhere? Waaaah ...") Lest there be any doubt: GCC uses a hand-written recursive descent parser for C++. (Meg and a half of code and increasing.) That's virtually a proof that just parsing with functional decomposition is good enough for anything. Another thing is that with functional parsing, you can use the exception handling (or other non-local, dynamic control transfers) of the programming language for recovery and speculative parsing. This parse didn't work? Chuck the whole damn branch of the parse with a dynamic return, and try going down another rabbit hole.
- c-cube 9y agoThat'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.
- mattnewport 9y agoFile 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.
- kibwen 9y agoWhat 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.
- coldtea 9y agoWell, we gladly trade power and efficiency all the time for more intuitiveness and ease of use in computing...
- Analemma_ 9y agoIs 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?
- zoren 9y agoI would claim ANTLR is such a tool.
- wtetzner 9y ago> 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?
- dukoid 9y agoFor 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 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).
- kmill 9y agoAre 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.)
- 9y ago
- kazinator 9y agoAs long as you're writing parsers, it is forever 1969. Knuth invented all you need to know just recently. Off you go and parse!
- saywatnow 9y agoThis 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.
- geal 9y agoWe 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 https://github.com/ANSSI-FR/bootcode_parser (python) or https://github.com/ANSSI-FR/caradoc 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 :)
- JoelJacobson 9y agoAre there any Context-sensitive algorithms/parsers/generators? The list at https://en.wikipedia.org/wiki/Context-sensitive_grammar 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.
- sfvisser 9y agoMonadic parser combinators are context-sensitive, because you can arbitrarily branch your parser based on previously parsed content.
- BigIQ 9y agoNice overview of the pitfalls of C-parsers, their hardening, a presentation of Rust advantages, parser combinators, the nom crate, its usage, the application to VLC and an intrusion detector, the integration with those complex existing C codebase, fuzzing and a few ideas to improve rust for more security. And I am happy to see the ANSSI here :)
- CodesInChaos 9y agoIn my experience avoiding unlimited recursion/stackoverflows is one of the most annoying parts of writing a parser, so I find it surprising that the paper doesn't even mention that topic.
- geezerjay 9y ago> In my experience avoiding unlimited recursion/stackoverflows is one of the most annoying parts of writing a parser This, x10. My take is that this is perhaps the main reason why everyone tends to rely on hand-written parsers instead of simply using code churned out by a parser generator. Parser generators are developed with a single use case in mind: pick up a grammar definition, perhaps with pre and post-conditions, and proceed to map it to some programming language. Yet, this fails very basic requirements for real world parser applications.
- souenzzo 9y agoNo mentions to instaparse? https://github.com/Engelberg/instaparse https://github.com/Engelberg/instaparse "Parse IS be something easy as regexp"