Learning Parser Combinators with Rust

289 点作者 chwolfe大约 6 年前

11 条评论

>> The novice programmer will ask, "what is a parser?">> The intermediate programmer will say, "that's easy, I'll write a regular expression.">> The master programmer will say, "stand back, I know lex and yacc."The Prolog programmer will write a Definite Clause Grammar [1], which is both a grammar and a parser, two-in-one. So you only have to do the easy and fun bit of writing a parser, which is defining the grammar.Leaves plenty of time to get online and brag about the awesome power of Prolog or get embroiled in flamewars with functional programming folks [2].______________[1] <a href="https://en.wikipedia.org/wiki/Definite_clause_grammar" rel="nofollow">https://en.wikipedia.org/wiki/Definite_clause_grammar</a>[2] Actually, DCGs are kiiind of like parser combinators. Ish. In the sense that they're executable grammars. But in Prolog you can run your programs backwards so your DCG is both a recogniser and a generator.

评论 #19703780 未加载

评论 #19712033 未加载

intertextuality大约 6 年前

On the reddit discussion of this [0], someone mentioned using a type offn parse(&self, input: &mut &str) -> Option<Output>instead of the article'sfn parse(&self, input: &'a str) -> Result<(&'a str, Output), &'a str>for composability. I found the article fascinating and plan on going back to see what an xml parsing implementation based on the former would act like.[0]: <a href="https://www.reddit.com/r/rust/comments/bepi63/learning_parser_combinators_with_rust/" rel="nofollow">https://www.reddit.com/r/rust/comments/bepi63/learning_parse...</a>

评论 #19699384 未加载

xymostech大约 6 年前

This was such a wonderful read! I've been getting into Rust recently, and the sections on dealing with challenges that are specific to Rust were particularly useful. The way they created a new trait to turn `Fn(&str) -> Result<(&str, T), &str>` into `Parser<T>` was insightful, and the discussion of how they dealt with the growing sizes of types was something that I can imagine myself running into in the future.Most importantly though, when they started writing `and_then`, my eyes lit up and I said "It's a Monad!" I think this is the first time I've really identified a Monad out in the wild, so I enjoyed that immensely.

louthy大约 6 年前

It doesn't feel very declarative in Rust. Personally, I'm finding it hard to see the intent (I haven't written a line of Rust in my life, so take that with a pinch of salt, but I am a polyglot programmer).Really, Haskell's do notation is the big winner when it comes to parser combinators, as the direction of the flow of the parser is easy to follow, but also you can capture variables mid-flight for use later in the expression without obvious nested scope blocks.It's possible to capture variables with `and_then` by the looks of it, but any suitably complex parser will start to end up quite an ugly mess of nested scopes.I ported Haskell's Parsec to C# [1], it has LINQ which is similar to Haskell's Do notation. Simple parsers [2] are beautifully declarative, and even complex ones, like this floating point number parser [3], are trivial to follow.[1] <a href="https://github.com/louthy/language-ext" rel="nofollow">https://github.com/louthy/language-ext</a>[2] <a href="https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Prim.cs#L452" rel="nofollow">https://github.com/louthy/language-ext/blob/master/LanguageE...</a>[2] <a href="https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Token.cs#L287" rel="nofollow">https://github.com/louthy/language-ext/blob/master/LanguageE...</a>

评论 #19703938 未加载

评论 #19708296 未加载

xixixao大约 6 年前

Nice article. I finally gave Rust a recently. It's really interesting how new languages evolve, and what "deficiencies" they exert. The article for example uses closures, but it's currently impossible in stable Rust to accept a closure that itself accepts a closure as an argument (while you can easily rewrite the same pattern with structs). The borrow checker could still do better on suggesting fixes to common problems (otherwise it's actually quite elegant). What struck me while reading this was the use of assert_eq!(expected, actual), as I've mostly seen the other order. Sure enough I checked and the macro does not define the order. That's unfortunate, as testing against "fixed" "expected" outcome is very common, and leads to more friendly testing devx (which in general while supported out of the box isn't great).On the other hand, Rust's IDE support, built-in linting, is seriously impressive.

评论 #19699343 未加载

评论 #19699273 未加载

评论 #19699163 未加载

评论 #19699615 未加载

评论 #19702705 未加载

评论 #19699356 未加载

norswap大约 6 年前

If someone wants to have a look at the code of a cutting-edge parser combinator framework with focus on features + usability, I'll plug this here (it's in Java)<a href="https://github.com/norswap/autumn4" rel="nofollow">https://github.com/norswap/autumn4</a>WIP but 1.0.0 will land somewhere within the next two months, with a full user-guide (half of it is already written and available).Constructive feedback welcome!

评论 #19703515 未加载

tiuPapa大约 6 年前

Okay, I am interested in this topic. Does anyone know of any good resources for exploring parser combinators further?

评论 #19701930 未加载

amelius大约 6 年前

What is the class of languages that can be parsed with such parsers, in the sense of [1]?[1] <a href="https://en.wikipedia.org/wiki/Context-free_grammar#Subclasses" rel="nofollow">https://en.wikipedia.org/wiki/Context-free_grammar#Subclasse...</a>

评论 #19700626 未加载

lelf大约 6 年前

<a href="https://news.ycombinator.com/item?id=19694793" rel="nofollow">https://news.ycombinator.com/item?id=19694793</a>

k0t0n0大约 6 年前

nice read; Hi I also wrote a SQL dump parser using rust here the code.> <a href="https://github.com/ooooak/sql-split" rel="nofollow">https://github.com/ooooak/sql-split</a>

vmchale大约 6 年前

I don't like Rust for this purposes. It doesn't have higher-kinded types and thus no applicatives or monads, which sort of misses the point.I also object to the idea that parser combinators are an alternative to parser generators. They're each useful in different scenarios. But for something like XML the parser combinators will be slower.I'd also be curious to see how the efficiency of parser combinators is affected by the absence of laziness in Rust. I seem to recall that laziness makes the analysis more complicated than you'd expect, but I need to find a source...

评论 #19708111 未加载