8 ms·

Learning Parser Combinators with Rust

289 points by chwolfe 7y ago

xixixao 7y ago
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.
- intertextuality 7y ago
  > That's unfortunate, as testing against "fixed" "expected" outcome is very common, .... so write it in your preferred order then, in your own code? Why is it "unfortunate" that a generic macro isn't concerned with explicit order? It checks that left == right, [0] no more, no less. Instead of that, I'm free to follow my own conventions when writing tests. [1] [0]: https://doc.rust-lang.org/src/core/macros.rs.html#44 https://doc.rust-lang.org/src/core/macros.rs.html#44 [1]: https://git.sr.ht/~andrewzah/korean_numbers/tree/master/tests/test.rs#L176 https://git.sr.ht/~andrewzah/korean_numbers/tree/master/test...
  - masklinn 7y ago
    Fixing the ordering can provide for clearer error messages and the like, for instance rather than the error message being "foo is different from bar" you could have "got foo, expected bar". However I don't see how you can enforce it especially in a simple function / macro (I guess that's one point for BDD-style interfaces): the expected value is not necessarily static so it's not like you could require a const / static / literal even if the language allowed for such an annotation.
    - twic 7y ago
      You can use a form like: assert_that(foo, is_equal_to(bar)); Which makes it sort of clear that foo is the actual value, and bar is the expected. Especially when you also see things like: assert_that(foo, is_not_zero()); Perhaps that's what you mean by 'BDD-style interfaces'.
      - masklinn 7y ago
        > Perhaps that's what you mean by 'BDD-style interfaces'. Yes. It's usually a more OO shape but usually along the lines of `foo.should.be.equal.to(bar)` or somesuch, a "natural" reading makes it pretty likely the parameter is the expected value.
    - intertextuality 7y ago
      You could always define a macro like "expect_that", or something similar to ruby's expect(obj).to eq, etc. I find assert_eq!() personally to not be confusing since I always follow the same order, even though I come from a Ruby background with rspec and/or cucumber.
- steveklabnik 7y ago
  We looked at the order for assert_eq, and couldn’t find any real consensus. Large testing frameworks in a variety of languages use both orderings. So, we decided to not enforce a particular one.
  - skybrian 7y ago
    That seems like an odd decision? It's like saying there is no consensus for which side of the road to drive on, so let's not pick one. Standardization is arbitrary but useful here.
    - steveklabnik 7y ago
      The best argument for picking a specific side was the comment below about "expected, actual" vs "these two things are not equal." In the end, we decided that this just wasn't enough of a benefit to justify making an arbitrary choice. If we did choose, a lot of code would have to change, as existing Rust codebases also used both conventions. Rust already forces the user to follow a lot of rules; this one just wasn't deemed worth it.
    - coldtea 7y ago
      How is it useful, since it has no observable effect? Equals is equals!
      - skybrian 7y ago
        As many people pointed out, an expected value is not the same as the actual value. This affects error messages, which are important for ergonomics.
        eridius 7y ago
        The downside to enforcing an order is the compiler cannot enforce an order so people absolutely will get it wrong and not notice until much later when the test breaks and they get really confused because the message is telling them the expected value is the actual value and vice versa.
- oconnor663 7y ago
  > it's currently impossible in stable Rust to accept a closure that itself accepts a closure as an argument You can make it work this way, if the second closure doesn't actually close over anything: let apply_twice = |f: fn(u64) -> u64, x| f(f(x)); let plus_3 = |x| x + 3; let x = apply_twice(plus_3, 1); Or this way, even with closed-over variables, using dynamic dispatch: let apply_twice = |f: &dyn Fn(u64) -> u64, x| f(f(x)); let plus_3 = |x| x + 3; let x = apply_twice(&plus_3, 1); I don't know if it's possible to take a generic closure by value, though. > the use of assert_eq!(expected, actual), as I've mostly seen the other order That's interesting, in my head (expected, actual) is the usual order. For example, https://godoc.org/github.com/stretchr/testify/require#Equal https://godoc.org/github.com/stretchr/testify/require#Equal.
- Thaxll 7y ago
  Rust IDE support is not great tbh, there are recent languages that have way better support. I would day it's average at best.
  - bluejekyll 7y ago
    Compared to what? Very few languages compare well to the excellent support out there for Java. IntelliJ’s Rust plugin is probably the best IDE experience with Rust, and now includes macro expansion. Personally, I still use the RLS with VSCode, mostly because I’m still enjoying the VSCode editor’s versatility when working with many different file types.
    - gameswithgo 7y ago
      C#, Java, Go, Kotlin It is true though that top notch IDE experience is rare.
- gameswithgo 7y ago
  The IDE support seems impressive at first, but RLS will start to break down and be unusable as projects get a bit large or a bit complex. One challenge, even if/when rls bugs are all sorted out, is that Rust compile times may make it impractical to use with large projects.
  - steveklabnik 7y ago
    It turns out, these problems are connected, and we're starting work on a second generation of tooling for this, based off of things like Rosyln. See https://ferrous-systems.com/blog/rust-analyzer-2019/ https://ferrous-systems.com/blog/rust-analyzer-2019/, which is already usable for basic things. This also means improving the compiler. From the 2019 roadmap: https://github.com/rust-lang/rfcs/blob/master/text/2657-roadmap-2019.md#compiler https://github.com/rust-lang/rfcs/blob/master/text/2657-road... > This is where the RLS 2.0 effort comes in. The plan is to build a prototype of the new front-end, thus enabling a truly first-class IDE experience. Wherever possible, we aim to share code between this front-end and rustc by extracting libraries, such as Chalk (for traits), Polonius (for the borrow checker), and a new library focusing on name resolution. Eventually, we will merge this new front-end with the remaining bits of back-end from rustc. rust-analyzer is that "RLS 2.0"
    - gameswithgo 7y ago
      >based off of things like Rosyln That is spectacular news! This is a huge project I had assumed it would be a while before anyone could take this on.
      - steveklabnik 7y ago
        It is certainly a huge project, but that's one nice thing about the "split everything into a ton of crates" philosophy; it enables this kind of thing to be done in a fairly piecemeal way.
- josteink 7y ago
  > What struck me while reading this was the use of assert_eq!(expected, actual) This order is common in probably 200+ test-frameworks. For me, I’m surprised whenever I see the opposite. > leads to more friendly testing devx IMO being ergonomic, consistent and well documented leads to good developer experience. Things like this matter little.
lelf 7y ago
https://news.ycombinator.com/item?id=19694793 https://news.ycombinator.com/item?id=19694793
intertextuality 7y ago
On the reddit discussion of this [0], someone mentioned using a type of fn parse(&self, input: &mut &str) -> Option<Output> instead of the article's fn 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]: https://www.reddit.com/r/rust/comments/bepi63/learning_parser_combinators_with_rust/ https://www.reddit.com/r/rust/comments/bepi63/learning_parse...
- steveklabnik 7y ago
  This might be the first time I’ve seen a good use for &mut &T, very cool! For those of you not well-versed in Rust, this is a mutable pointer to an immutable string. This means that you can change the part of the string you’re pointing at, but you can’t change the underlying string itself.
  - e12e 7y ago
    What does that mean? Is it equivalent to the pointer starting out (say) pointing to the first letter of the string, but being able to "walk"/iterate along the length of the string?
    - bluejekyll 7y ago
      It means you can change the string to which the pointer is currently associated. Edit: I removed my initial “no.”
      - progval 7y ago
        But in this case, it will be used the way that e12e described.
        bluejekyll 7y ago
        Ah. I may have misunderstood what they were suggesting.
k0t0n0 7y ago
nice read; Hi I also wrote a SQL dump parser using rust here the code. > https://github.com/ooooak/sql-split https://github.com/ooooak/sql-split
amelius 7y ago
What is the class of languages that can be parsed with such parsers, in the sense of [1]? [1] https://en.wikipedia.org/wiki/Context-free_grammar#Subclasses https://en.wikipedia.org/wiki/Context-free_grammar#Subclasse...
- jcranmer 7y ago
  It's basically a recursive-descent parser, which means LL(k)-ish. The "-ish" is because you can use other tricks instead of straightforward recursive-descent (expression parsing is a common example of where you might want to do so), but the basic combinator concept itself is LL(k).
tiuPapa 7y ago
Okay, I am interested in this topic. Does anyone know of any good resources for exploring parser combinators further?
- vmchale 7y ago
  I like http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf
YeGoblynQueenne 7y ago
>> 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] https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar [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.
- fwip 7y ago
  This is beside your point, but I've found PEG to be a nice step up in usability from lex&yacc, as again, you only have to write one grammar definition. Wiki: https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar Example Implementation: https://pegjs.org/ https://pegjs.org/
  - minxomat 7y ago
    Yep, PEGs are seriously underutilized. Here's a nice introduction using LPeg: http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html
  - int_19h 7y ago
    For Rust: https://github.com/kevinmehall/rust-peg https://github.com/kevinmehall/rust-peg
- thesz 7y ago
  Regarding your [2]. It is easy to combine parser and generator into one thing: http://hackage.haskell.org/package/reform http://hackage.haskell.org/package/reform (and then you can get to http://happstack.com/docs/crashcourse/Reform.html#reform http://happstack.com/docs/crashcourse/Reform.html#reform explaining how and how to).
xymostech 7y ago
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.
vmchale 7y ago
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...
- thramp 7y ago
  > 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. Having used parser combinators in Rust and Haskell (combine and attoparsec, respectively), I've found that even without applicatives, parser combinators are pretty handy—they're a step above regexes, but a step below a parser generator. > 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... Same here, but I suspect that aggressive inlining might be pretty helpful.
louthy 7y ago
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] https://github.com/louthy/language-ext https://github.com/louthy/language-ext [2] https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Prim.cs#L452 https://github.com/louthy/language-ext/blob/master/LanguageE... [2] https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Token.cs#L287 https://github.com/louthy/language-ext/blob/master/LanguageE...
- pornel 7y ago
  There are libraries like nom: https://lib.rs/crates/nom https://lib.rs/crates/nom or combine https://github.com/Marwes/combine/blob/master/examples/date.rs https://github.com/Marwes/combine/blob/master/examples/date.... that have more declarative-looking syntax. In TFA you intentionally get "raw Rust" to avoid syntax sugar obscuring what's going on.
- Matthias247 7y ago
  Since you mention parsec and .NET: fparsec [1] for F# is also a great library for building parser combinators. [1] https://www.quanttec.com/fparsec/ https://www.quanttec.com/fparsec/
norswap 7y ago
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) https://github.com/norswap/autumn4 https://github.com/norswap/autumn4 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!
- tempguy9999 7y ago
  Honest question, why use parser combinators? If I need to do it by hand I can write a recursive descent parser, but I never do it by hand any more, just break out lex/yacc or antlr. So, what have I or anyone to gain by learning/using PCs? (I'm never against learning new stuff but I have so much to learn that adding something unnecessary to that would be just dumb). TIA
  - fooker 7y ago
    Parser combinators aid in writing recursive descent parsers, they are not something alien. You can maybe consider it a design pattern which eliminates redundancies and makes it easier to construct an AST.
  - norswap 7y ago
    The problem is the definition of "by hand". I assume you mean it as "writing code in a general programming language". Note that in a sense, lex/yacc and antlr are programming languages as well. Parser combinators are usually put out in the form of DSLs. So effectively they're very similar to the above. e.g. here are JSON and Java in Autumn https://github.com/norswap/autumn4/blob/master/test/lang/json/JSON.java https://github.com/norswap/autumn4/blob/master/test/lang/jso... https://github.com/norswap/autumn4/blob/master/src/norswap/lang/java/Grammar.java https://github.com/norswap/autumn4/blob/master/src/norswap/l... There is actually very little difference between parser generators and parser generators. Like you could take the above Autumn code and make it generate a parser (I plan to do that eventually). The main advantage of parser generators is that the code you generate is usually a faster. The main disadvantage compared to combinators is that you add a layer of indirection: it's not code in your language that you can trace and debug directly, but generated code. The main advantage of Autumn over lex/yacc and ANTLR (and a whole host of others, though not all) is that you can define new combinators (not an advantage of PC, you could have this in a parser generator too). Essentially add the recursive-descent logic you need to do something new, then wrap in a nice combinator, and now your grammar has a new primitive element! Autumn has cool built-in combinators that users could have built themselves using the available facilities. For instance: memoization, longest-match, ways to define left- and right-associative operators, ... (https://github.com/norswap/autumn4/tree/master/src/norswap/autumn/parsers https://github.com/norswap/autumn4/tree/master/src/norswap/a...)

289 points by chwolfe 7y ago

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.

intertextuality 7y ago
> That's unfortunate, as testing against "fixed" "expected" outcome is very common, .... so write it in your preferred order then, in your own code? Why is it "unfortunate" that a generic macro isn't concerned with explicit order? It checks that left == right, [0] no more, no less. Instead of that, I'm free to follow my own conventions when writing tests. [1] [0]: https://doc.rust-lang.org/src/core/macros.rs.html#44 https://doc.rust-lang.org/src/core/macros.rs.html#44 [1]: https://git.sr.ht/~andrewzah/korean_numbers/tree/master/tests/test.rs#L176 https://git.sr.ht/~andrewzah/korean_numbers/tree/master/test...
- masklinn 7y ago
  Fixing the ordering can provide for clearer error messages and the like, for instance rather than the error message being "foo is different from bar" you could have "got foo, expected bar". However I don't see how you can enforce it especially in a simple function / macro (I guess that's one point for BDD-style interfaces): the expected value is not necessarily static so it's not like you could require a const / static / literal even if the language allowed for such an annotation.
  - twic 7y ago
    You can use a form like: assert_that(foo, is_equal_to(bar)); Which makes it sort of clear that foo is the actual value, and bar is the expected. Especially when you also see things like: assert_that(foo, is_not_zero()); Perhaps that's what you mean by 'BDD-style interfaces'.
    - masklinn 7y ago
      > Perhaps that's what you mean by 'BDD-style interfaces'. Yes. It's usually a more OO shape but usually along the lines of `foo.should.be.equal.to(bar)` or somesuch, a "natural" reading makes it pretty likely the parameter is the expected value.
  - intertextuality 7y ago
    You could always define a macro like "expect_that", or something similar to ruby's expect(obj).to eq, etc. I find assert_eq!() personally to not be confusing since I always follow the same order, even though I come from a Ruby background with rspec and/or cucumber.
steveklabnik 7y ago
We looked at the order for assert_eq, and couldn’t find any real consensus. Large testing frameworks in a variety of languages use both orderings. So, we decided to not enforce a particular one.
- skybrian 7y ago
  That seems like an odd decision? It's like saying there is no consensus for which side of the road to drive on, so let's not pick one. Standardization is arbitrary but useful here.
  - steveklabnik 7y ago
    The best argument for picking a specific side was the comment below about "expected, actual" vs "these two things are not equal." In the end, we decided that this just wasn't enough of a benefit to justify making an arbitrary choice. If we did choose, a lot of code would have to change, as existing Rust codebases also used both conventions. Rust already forces the user to follow a lot of rules; this one just wasn't deemed worth it.
  - coldtea 7y ago
    How is it useful, since it has no observable effect? Equals is equals!
    - skybrian 7y ago
      As many people pointed out, an expected value is not the same as the actual value. This affects error messages, which are important for ergonomics.
      - eridius 7y ago
        The downside to enforcing an order is the compiler cannot enforce an order so people absolutely will get it wrong and not notice until much later when the test breaks and they get really confused because the message is telling them the expected value is the actual value and vice versa.
oconnor663 7y ago
> it's currently impossible in stable Rust to accept a closure that itself accepts a closure as an argument You can make it work this way, if the second closure doesn't actually close over anything: let apply_twice = |f: fn(u64) -> u64, x| f(f(x)); let plus_3 = |x| x + 3; let x = apply_twice(plus_3, 1); Or this way, even with closed-over variables, using dynamic dispatch: let apply_twice = |f: &dyn Fn(u64) -> u64, x| f(f(x)); let plus_3 = |x| x + 3; let x = apply_twice(&plus_3, 1); I don't know if it's possible to take a generic closure by value, though. > the use of assert_eq!(expected, actual), as I've mostly seen the other order That's interesting, in my head (expected, actual) is the usual order. For example, https://godoc.org/github.com/stretchr/testify/require#Equal https://godoc.org/github.com/stretchr/testify/require#Equal.
Thaxll 7y ago
Rust IDE support is not great tbh, there are recent languages that have way better support. I would day it's average at best.
- bluejekyll 7y ago
  Compared to what? Very few languages compare well to the excellent support out there for Java. IntelliJ’s Rust plugin is probably the best IDE experience with Rust, and now includes macro expansion. Personally, I still use the RLS with VSCode, mostly because I’m still enjoying the VSCode editor’s versatility when working with many different file types.
  - gameswithgo 7y ago
    C#, Java, Go, Kotlin It is true though that top notch IDE experience is rare.
gameswithgo 7y ago
The IDE support seems impressive at first, but RLS will start to break down and be unusable as projects get a bit large or a bit complex. One challenge, even if/when rls bugs are all sorted out, is that Rust compile times may make it impractical to use with large projects.
- steveklabnik 7y ago
  It turns out, these problems are connected, and we're starting work on a second generation of tooling for this, based off of things like Rosyln. See https://ferrous-systems.com/blog/rust-analyzer-2019/ https://ferrous-systems.com/blog/rust-analyzer-2019/, which is already usable for basic things. This also means improving the compiler. From the 2019 roadmap: https://github.com/rust-lang/rfcs/blob/master/text/2657-roadmap-2019.md#compiler https://github.com/rust-lang/rfcs/blob/master/text/2657-road... > This is where the RLS 2.0 effort comes in. The plan is to build a prototype of the new front-end, thus enabling a truly first-class IDE experience. Wherever possible, we aim to share code between this front-end and rustc by extracting libraries, such as Chalk (for traits), Polonius (for the borrow checker), and a new library focusing on name resolution. Eventually, we will merge this new front-end with the remaining bits of back-end from rustc. rust-analyzer is that "RLS 2.0"
  - gameswithgo 7y ago
    >based off of things like Rosyln That is spectacular news! This is a huge project I had assumed it would be a while before anyone could take this on.
    - steveklabnik 7y ago
      It is certainly a huge project, but that's one nice thing about the "split everything into a ton of crates" philosophy; it enables this kind of thing to be done in a fairly piecemeal way.
josteink 7y ago
> What struck me while reading this was the use of assert_eq!(expected, actual) This order is common in probably 200+ test-frameworks. For me, I’m surprised whenever I see the opposite. > leads to more friendly testing devx IMO being ergonomic, consistent and well documented leads to good developer experience. Things like this matter little.

lelf 7y ago

https://news.ycombinator.com/item?id=19694793 https://news.ycombinator.com/item?id=19694793

intertextuality 7y ago

On the reddit discussion of this [0], someone mentioned using a type of fn parse(&self, input: &mut &str) -> Option<Output> instead of the article's fn 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]: https://www.reddit.com/r/rust/comments/bepi63/learning_parser_combinators_with_rust/ https://www.reddit.com/r/rust/comments/bepi63/learning_parse...

steveklabnik 7y ago
This might be the first time I’ve seen a good use for &mut &T, very cool! For those of you not well-versed in Rust, this is a mutable pointer to an immutable string. This means that you can change the part of the string you’re pointing at, but you can’t change the underlying string itself.
- e12e 7y ago
  What does that mean? Is it equivalent to the pointer starting out (say) pointing to the first letter of the string, but being able to "walk"/iterate along the length of the string?
  - bluejekyll 7y ago
    It means you can change the string to which the pointer is currently associated. Edit: I removed my initial “no.”
    - progval 7y ago
      But in this case, it will be used the way that e12e described.
      - bluejekyll 7y ago
        Ah. I may have misunderstood what they were suggesting.

k0t0n0 7y ago

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

amelius 7y ago

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

jcranmer 7y ago
It's basically a recursive-descent parser, which means LL(k)-ish. The "-ish" is because you can use other tricks instead of straightforward recursive-descent (expression parsing is a common example of where you might want to do so), but the basic combinator concept itself is LL(k).

tiuPapa 7y ago

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

vmchale 7y ago
I like http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

YeGoblynQueenne 7y ago

>> 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] https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar [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.

fwip 7y ago
This is beside your point, but I've found PEG to be a nice step up in usability from lex&yacc, as again, you only have to write one grammar definition. Wiki: https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar Example Implementation: https://pegjs.org/ https://pegjs.org/
- minxomat 7y ago
  Yep, PEGs are seriously underutilized. Here's a nice introduction using LPeg: http://leafo.net/guides/parsing-expression-grammars.html http://leafo.net/guides/parsing-expression-grammars.html
- int_19h 7y ago
  For Rust: https://github.com/kevinmehall/rust-peg https://github.com/kevinmehall/rust-peg
thesz 7y ago
Regarding your [2]. It is easy to combine parser and generator into one thing: http://hackage.haskell.org/package/reform http://hackage.haskell.org/package/reform (and then you can get to http://happstack.com/docs/crashcourse/Reform.html#reform http://happstack.com/docs/crashcourse/Reform.html#reform explaining how and how to).

xymostech 7y ago

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.

vmchale 7y ago

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...

thramp 7y ago
> 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. Having used parser combinators in Rust and Haskell (combine and attoparsec, respectively), I've found that even without applicatives, parser combinators are pretty handy—they're a step above regexes, but a step below a parser generator. > 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... Same here, but I suspect that aggressive inlining might be pretty helpful.

louthy 7y ago

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] https://github.com/louthy/language-ext https://github.com/louthy/language-ext [2] https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Prim.cs#L452 https://github.com/louthy/language-ext/blob/master/LanguageE... [2] https://github.com/louthy/language-ext/blob/master/LanguageExt.Parsec/Parsers/Token.cs#L287 https://github.com/louthy/language-ext/blob/master/LanguageE...

pornel 7y ago
There are libraries like nom: https://lib.rs/crates/nom https://lib.rs/crates/nom or combine https://github.com/Marwes/combine/blob/master/examples/date.rs https://github.com/Marwes/combine/blob/master/examples/date.... that have more declarative-looking syntax. In TFA you intentionally get "raw Rust" to avoid syntax sugar obscuring what's going on.
Matthias247 7y ago
Since you mention parsec and .NET: fparsec [1] for F# is also a great library for building parser combinators. [1] https://www.quanttec.com/fparsec/ https://www.quanttec.com/fparsec/

norswap 7y ago

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) https://github.com/norswap/autumn4 https://github.com/norswap/autumn4 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!

tempguy9999 7y ago
Honest question, why use parser combinators? If I need to do it by hand I can write a recursive descent parser, but I never do it by hand any more, just break out lex/yacc or antlr. So, what have I or anyone to gain by learning/using PCs? (I'm never against learning new stuff but I have so much to learn that adding something unnecessary to that would be just dumb). TIA
- fooker 7y ago
  Parser combinators aid in writing recursive descent parsers, they are not something alien. You can maybe consider it a design pattern which eliminates redundancies and makes it easier to construct an AST.
- norswap 7y ago
  The problem is the definition of "by hand". I assume you mean it as "writing code in a general programming language". Note that in a sense, lex/yacc and antlr are programming languages as well. Parser combinators are usually put out in the form of DSLs. So effectively they're very similar to the above. e.g. here are JSON and Java in Autumn https://github.com/norswap/autumn4/blob/master/test/lang/json/JSON.java https://github.com/norswap/autumn4/blob/master/test/lang/jso... https://github.com/norswap/autumn4/blob/master/src/norswap/lang/java/Grammar.java https://github.com/norswap/autumn4/blob/master/src/norswap/l... There is actually very little difference between parser generators and parser generators. Like you could take the above Autumn code and make it generate a parser (I plan to do that eventually). The main advantage of parser generators is that the code you generate is usually a faster. The main disadvantage compared to combinators is that you add a layer of indirection: it's not code in your language that you can trace and debug directly, but generated code. The main advantage of Autumn over lex/yacc and ANTLR (and a whole host of others, though not all) is that you can define new combinators (not an advantage of PC, you could have this in a parser generator too). Essentially add the recursive-descent logic you need to do something new, then wrap in a nice combinator, and now your grammar has a new primitive element! Autumn has cool built-in combinators that users could have built themselves using the available facilities. For instance: memoization, longest-match, ways to define left- and right-associative operators, ... (https://github.com/norswap/autumn4/tree/master/src/norswap/autumn/parsers https://github.com/norswap/autumn4/tree/master/src/norswap/a...)