Parsing left-recursive/ambiguous grammars

[SuperJMN]

Hello everybody!

This is my favorite parser combinators library. In fact, the only I use. But after some time and having much more experience, I found that only the most simple grammars can be expressed with it while keeping complexity low (and being readable / maintainable).

For example, I tried to define a grammar for the ANSI-C language and failed multiple times. The problem is that most of grammars I've found are left-recursive, thus, not handled by Superpower (with the exception of some combinators like Chain)

Well, my dream is to create a C compiler. And I would like to use Superpower. The reasons are obvious: it's .NET and it's cross-platform. Also, I love C#.

I really hope that Superpower could become more mature and maybe copy some concepts from other parsers like GLL Combinators to be able to deal with such grammars.

Also, I hope to finish my compiler some time. The current parser is here (based on Superpower, of course) https://github.com/SuperJMN/SuppaParser. Feel free to collaborate. I really want to learn!

Expressions aren't handled in any way, for now.

I leave this issue as a reminder of my wishes and hopes, since I know this request is very unlikely to be seen in the near future. Also, I know @nblumhardt is quite busy and there aren't a lot of collaborators that could implement such an improvement.

Anyways, thank you :)

[nblumhardt]

Thanks for the note, @SuperJMN!

The goals of Superpower are a little different from what I think you have in the case of building a C compiler. You could parse C with Superpower (to the best of my knowledge), but if you want to easily translate an existing grammar, you'll be better served by a library that's aligned with the kind of grammar you have on hand, as you pointed out.

While translating from existing left-recursive grammars with Superpower isn't much fun, the straightforward recursive descent combinator approach has other distinct advantages that make it a good fit for lots of tasks - being able to treat parsers as simple executable programs removes a whole lot of mystery from the development process, and it's very easy to extend the library to suit different grammatical constructs.

GLL looks extremely interesting. I imagine there would be some simplicity trade-off. A GLL combinator library in C# would, however, be really interesting to see :-)

[SuperJMN]

Thanks! it seems that I will have to wait some years before I attempt to create my compiler. It's a huge task. I'll take a look to LLVM an other options. Anyways, I encourage you to investigate, since this project has a lot of future, even more because there's NOTHING in the .NET space that does this kind of work. Superpower does it, and it does it elegantly (LINQ-style definitions are a killer feature).

I'm also providing more like about the topic http://ceur-ws.org/Vol-2241/
http://hackage.haskell.org/package/XSaiga
(By Richard Frost)

BTW, do you know any academic/developer that could be interested in providing support for more complex grammars?

Thank you!

[nblumhardt]

So much interesting stuff out there! :-) I can't think of anyone who would be likely to pick this up right now, but good luck all the same.