A Parser Combinator library for C | Hacker News Reader

A Parser Combinator library for C

github.com

58 points_zhqs25 comments

Open articleView on HN

Another is Hammer, https://github.com/UpstandingHackers/hammer

This is being used from another thing posted here about making your own lisp: http://www.buildyourownlisp.com/

Pretty nice and simple. I'm on Chapter 8 of 16.

I think both the library and the book are written by the same author [1].

[1] http://theorangeduck.com/page/you-could-have-invented-parser...

nice!

What's the difference between this and flex/yacc?

From the readme, a workflow that doesn't make you want to kill yourself.

Also no generated code that requires extra build steps and instantly breaks platform compatibility. That said, inline grammar definition might not be for everyone.

Hmm. So for people who don't know how to use Unix/flex/yacc?

This is just reinventing an existing wheel.

I dunno that that's a fair criticism... by that same argument you could say yacc/bison is for people who don't know how to use C to write a parser. This looks like an attempt to do something along the lines of Parsec from Haskell, but in C.

Edit, because it looks like we hit the max reply depth: It's not like this is ever going to seriously replace Bison, I think it's just someone trying a different approach. It's not like flex/yacc/bison are the absolutely most perfect lexer/parser that can possibly exist. If people didn't try and reinvent the wheel every now and then, we'd still have stone wheels.

But doing this in C already exists and works well. I don't understand the point of it. Although, in this day and age, rather than use the standard Unix toolset, people invent their own tools as if they are new. "Make" versus "npm" for example.

Do you really think Make could replace npm?

Make existed long before npm and make is the basis of all our package management in our company and our operating systems.

Recursive descent parsing can handle different class of languages from what yacc or bison can do. It is possible to build lexerless parsers this way (so scrap your old useless flex).

So your trying to say this thing does a better job?

I seriously doubt it ever will, but you have to start somewhere.

I've used Parsec before and it is certainly nice. Honestly I think it's a bit weird to try and shoehorn it into C, but hey maybe something interesting will come out of it.

What bugs me is the suggestion that just because bison works well enough, nobody should try and make a new parser generator in C. They will probably not take over the wold, bison is big and battle tested after all, but bison is itself also a replacement for older tools. And hey, maybe mpc here will succeed and revolutionize parsing for the best; then we can have this discussion again in 20 years about someone attempting to replace it.

What you just said is this new thing isn't as good, and probably never will be, but you imply we should use it, even though the current tools are better.

See my complaint? If they are going to introduce a new tool, it must be better than the current tool. It's not and it's worse and not as mature.

This one may not be that good. But any Packrat-based library is definitely much better than anything Yacc can offer.

I didn't say you should use it, nor would I. Only that it isn't pointless/futile to attempt. No tool will be as mature as bison or what have you until it has also been battle tested for 25+ years, but 25 years ago bison was also new and upcoming.

Not to mention that this is not even really a parser generator like bison or yacc... it's a combinator library. It's an entirely different way to write a parser. It's like me saying Python shouldn't exist because I know how to write C.

It is different, targetting a different set of use cases.

In yacc the generator will tell you about shift reduce conflicts. Once you have debugged the grammar the parser is likely to work. With parser combinators you have no such assurance - you don't know if your grammar has loops, the parser might get stuck easily while parsing. However for a simple and regular input language like sexpr everything is fine.

In recursive descent you simply do not have any shift/reduce conflicts.

you can have left recursion, or implicit left recursion in your recursive descent grammar, if you have then the parser gets stuck while parsing a clause that contains left recursion.

Firstly, this have nothing to do with shift/reduce. Secondly, you can safely handle left-recursive grammars in Packrat (which, in turn, can be implemented with combinators).

I didn't say that left recursion has anything to do with shift reduce conflicts. Please read again.

I see, yes, you mentioned loops earlier. Anyway, it is not a problem for combinator-based parsing, just use Packrat with a left-recursive extension [1]

[1] http://www.vpri.org/pdf/tr2007002_packrat.pdf

I know how to use lex/yacc. This is much better as lex/yacc are, frankly, miserable to use.

Reply on news.ycombinator.com