C++ Compile Time Parser Generator | Hacker News Reader

C++ Compile Time Parser Generator

github.com

63 pointsingve56 comments

This is actually very nice. The documentation is also well done. I might try it for some personal projects.

Not sure if the OP is the author, but here are a few comments from someone with no experience in parsing:

- For the documentation, it would be better if it didn't use using namespace, as it make it easier to see which symbols are part of the library and which ones are part of the example.

- There's need to be a note about the lifetime of the buffer under referenced by the string_view parameters. I assume this is just the original buffer passed to parse, but it would be better to be explicit. Also, string_views are probably better passed around by value (the examples are inconsistent).

- The documentation probably need more details about handling parsing errors. Also is there any way to recover from a failed parse?

- It would be nice that a parser with no action could be used to validate a string against a grammar, but it seems that the implicit actions would prevent that.

- (Very minor) val should probably be called always, and create should just be always with an explicit template parameter and a defaulted argument.

- (Again, very minor) making create, push_back and emplace_back inline variables (available in C++17) instead of types would lead to a slightly more pleasant syntax.

Yes OP (me) is the author. Thanks for the kind words:) I will consider your suggestions. As for the eror recovery, the newest version has error recovery feature.

Thank you. I'll try give this a go and report my experience. Are you using this in production at $JOB or is it just a personal project?

Personal. But would galdly use it in production if given opportunity.

C++ compile times are super fast so this doesn't exacerbate a problem that causes people to give up and just use C99.

You mean the language where header libraries have become fashionable?

As technically interesting this is, it's certainly going to be surefire way to kill your compile time :-)

Does it matter? Put it behind a method, such as parse_foo( string_view ), and firewall it into it's own TU. One only needs to compile it when the parser requirements change

It would be interesting to compare compiling a grammar written with this against generating it with flex/bison and compiling the generated code.

Has there been any credible study of compile-time cost of constexpr vs. template metaprogramming?

I am assuming template metaprogramming is so bad because even elementary data structures have to employ ton of helper types that have to be matched/deduced against gigantic list of all other types and kept all in memory, while straightforward interpretation should not need any of that. I would expect constexpr to perform similarly to interpreted languages, which should be no different than invoking an external code generator written in Python, for example.

You say that like it's a bad thing.

https://xkcd.com/303/

I had written something like this and found a very interesting compiler difference between clang/gcc and MSVC. I used lambdas as parsers, which worked great for the first two compilers. Did not work at all for MSVC. It would not compile, heap-space exhausted, while clang/gcc wouldn't even show a noticeable blip on the memory usage.. Changing the lambdas out for templated functions made it work on both

Did anyone try it? I'm interested in the binary size for a nontrivial language.

That is what killed my own attempt at doing this - the code was large enough that I had to move some polymorphism from compile time to run time in order to - counterintuitively - speed it up!

(Entirely possible they executed better than I did, of course)

It produces bunch of arrays, the parse algorithm is trivial. For json grammar the arrays measure in kilobytes. For a programming language, probably several megabytes. Anyways, the binary should be comparable to Bison generated, at least if you tell bison to generate canonical LR parser.

Interesting approach. Instead of using a program to generate the table that is used by the parsing algorithm (like yacc) it generates it during compile time. This should not be any slower (in order of magnitudes) than using a parser generator.

Also nice how you can integrate the semantics within the rule by the use of lambda expressions.

(I have experience with writing parser and developed an interpreting parser myself. https://github.com/FransFaase )

Well, the json parser example is th heaviest one, compiling about a minute on my 2 core virtual machine. I guess it doesn' really matter, you can always put the parser definition is a separate compilation unit. The language grammar you are parsing should not change too frequently.

That is really much longer than would expect. Sounds like using the C++ compiler for this purpose is not working well.

Not at all. I didn't try too hard to optimze it yet, and when I use a modern physical machine, it will probably be more like 20 seconds already. I bet I could make it twice as fast after optimization.

I just relased a new version. GCC compiles a JSON parser example in less than 8 seconds. Still on a low resource VM.

So who here has compile times going into days, ie whats the longest you have to wait for your code to compile?

Better question: how long does it take to debug such code?

Depends on what your cpu microcode and OS has been programmed to do.

I wonder how this compares to boost spirit.

Well for one it's about a million times more readable than goddamn Spirit. It still abuses operator overloading so it's just as terrible.

Use a real tool instead of hacks like this. For fun? Do whatever you want. If I ever come across something like this in production it's going to be removed immediately.

Seriously, what's so wrong with lex + yacc, or antlr or parsec or ragel or any of the others?

> Seriously, what's so wrong with lex + yacc, or antlr or parsec or ragel or any of the others?

Not sure ANTLR is as fast (doesn't it use recursive descent? which is slower algorithmically) but even ignoring performance, it's basically the cost of adding a new tool to your toolchain. If you already have 20 other tools, maybe the 21st isn't a big deal, but if you have 2, the 3rd adds some complexity. And in general it's kinda nice to have fewer things to glue together.

(I'm not claiming "therefore this approach trumps what you listed", I'm just explaining some of its advantages. Obviously it has disadvantages too.)

ANTLR is LL, but not sure how that stacks up against LR in yacc in terms of speed.

Lex, yacc, antlr, parsec, ragel, and the others are all hacks.

Necessary hacks, when the language is inadequate to the job. But C++ is no longer inadequate.

Lex and yacc depend on global variables, so you get one (1) parser per program, unless you further massage their output.

Flex and Bison depend on global variables by default, but you can eliminate the global variables if you like (e.g. %option reentrant) and change the prefix if you like (%option prefix="mylexer_"). Bison has similar options.

I'm sure you could only have one lexer back at some point in the distant past, but that particular issue has been solvable for a long time by now.

lex and yacc depend on global variables, flex and bison, which are one the implementations of lex and yacc, don't.

Is there a reason why you'd be stuck on lex / yacc and unable to use flex / bison? The main reason I can think of is that you are in a legacy code base which already uses lex / yacc.

lex and yacc are part of POSIX, while flex and bison aren't.

Sure, and C++ isn't part of POSIX. So if you must stick to strictly POSIX utilities, you cannot use C++.

C++ and Posix are both ISO Standards.

Are you constrained to only use software which is standardized by ISO? I'm just trying to figure out what you're saying here.

I am not so constrained, but some are.

But in general, for anybody deploying software widely, any time you can avoid a necessary build dependency on another tool, you come out ahead.

Could you tell me more about who is constrained this way? I'm curious about what kind of organization has these kinds of constraints. I have some friends who work in aerospace or at defense contractors and these constraints sound a little extreme even by their standards.

They would know better than I do.

You can avoid a build dependency on Bison or Flex by shipping their output. Their output is intended to be portable and standard-conforming.

https://www.gnu.org/software/bison/manual/bison.html#Version...

Even if you have standard-conforming lex and yacc source code that, theoretically, work with any yacc or lex implementation, it's still wise to pick a good implementation and generate code with it, and ship that code. You don't want some random tool from the user's installation writing C code into your project.

And POSIX does not guarantee the presence of a yacc command in an installation; it just describes what it does if it is present. There are Unix-like systems with no dev tools on them; requiring lex plus yacc plus a compiler is a bigger dependency than just requiring a compiler.

There is no merit in adding a dependency on something that is demonstrated to be unnecessary.

People writing C++ code no longer have any need for a thing like yacc, and that is a net good.

More precisely, people writing C++ code who fork a copy of cpgg into their project, and maintain their fork forever, never peeking at the upstream again, have no external dependency.

Those who maintain some relationship with the cpgg upstream repo have some sort of dependency.

(C++ itself is a heavy dependency. People who don't use C++ demonstrate that C++ is not necessary.) Dependencies are not all the same; they have different weights. Three light dependencies could be equal to one heavy one.)

cpgg is currently not comparable to something like Bison. Bison has documentation, and an active mailing list where you can get quality help from knowledgeable people. It has multiple contributors.

It supports multiple languages, so your parser-writing skill transfers to different stacks: e.g. from C to Java, for instance. In many cases you should be able to port the grammar directly; just the semantic actions need a rewrite.

It has some novel diagnostic features, like the recently added feature of being able to generate counterexamples to explain conflicts.

It has the old diagnostic features, like the y.output file so you can pore over the LALR(1) state graph, and a debug mode.

It supports something called "push parsing": inverting the control flow, so that the parser becomes a state machine to which you can feed tokens one at a time. That makes it possible to do things like, oh, multiplex multiple parse jobs in parallel into a single event loop.

If you use only ISO standard tools, how do you read e-mail? Or access the web?

What bug database are you using: I don't know of any ISO-standard bug database.

Git is not an ISO-standard; do you pass around pax archives for version control? Not using SSH, I hope; that's not ISO standard.

Not even XWindow is an ISO standard, so nothing but ANSI terminals for you.

Is C++ adequate, when compile time and maintainability are taken into account?

Microsoft would say so, specially with all the module's talks.

I guess all those logos on ISO C++ meetings would state similar assertions.

Some of them might be playing with Rust, but when it comes down to shipping SDKs, it is all about C++.

Compile time seems like an odd thing for you to mention here. I don't know if your favorite language is similarly adequate, but I know it compiles way more slowly.

But generally the time to analyze a constexpr initializer expression, even of even a pretty substantial grammar, will generally be pretty negligible, particularly given that it need not appear in a header file.

This is false; GNU Bison introduced re-entrant parsing probably about a decade and half ago at least, in combination with Flex, and Berkeley Yacc implemented a compatible implementation.

I use this in TXR Lisp. There are situations in which a Lisp macro may be expanded in the context of the parser. The macro can use the parser (e.g. call (read "(1 2 3)"). This works.

that's nice, you and me will be in a cycle of immediately replacing each other's code. Seriously, lex+yacc / flex+bison absolutely suck, good luck when you have to put them as part of a complex cross-compilation build pipeline or run on windows. Also, have fun when you have multiple grammars in the same program and you don't want "colorful" ODR issues due to LTO, etc... they are entirely unfit for the job. In contrast Spirit just works for me after spending an hour reading the tutorial (my main problem was the sad issue common with expression templates and auto).

It also does not require to link anything, just -I/path/to/boost no matter the platform and tada, you get a fairly performant parser.

Flex / Bison are manageable if you spend a bit of extra time reading the manual. I admit that there are often better options out there these days, I'm just saying that some of these complaints about Flex / Bison may be a bit outdated.

Multiple grammars are fine, you just instruct Flex and Bison to use static or add prefixes. No worries about ODR or LTO.

If your build system can't handle generated code, that's an indictment of your build system. I know that's a bit harsh, but there are plenty of build systems which can handle generated code and cross-compile just fine. Flex and Bison work fine on Windows.

It's good that prefixes are now possible, but it's still something additional to know (I have never seen them in the wild and I've seen a lot of yacc in various projects), while most C++ programmers don't have to search inside some manual to know that two parsers must not have the same name : while with yacc / bison, you generally only discover it when it crashes at run-time.

Also http://gnuwin32.sourceforge.net/packages/bison.htm is not what "work fine on Windows" mean (hell, it does not even have the prefix thing you mentioned in the other comment). If there's anything ressembling a ./configure / some step that requires bash in its build pipeline then it's a complete no-go and given the GNU history of bison I doubt it'd use CMake.

Though even if all of this was solved, it'd still not be as convenient as Spirit.

When I integrate third-party dependencies I often port the build system to the build system I'm using. For projects made with autotools, that means ignoring the configure script, hand-writing a "correct" version of config.h.in, and reading Makefile.am. I'm sure this practice would offend some people. In my experience, this practice is quite common in industry.

I've done this enough times that using Bison on Windows was no problem at all. In my case, I wasn't really interested in Bison itself, but I was using a different third-party dependency which itself depended on Bison.

Bison now supports multiple start symbols. So that is to say, you can build multiple grammars in the same file that have their own start symbols, but otherwise share rules.

> or run on windows

If you're using Flex and Bison, you should arrange your project so that it can build without running the tools. Only someone who needs to make changes to the grammar files should require the tools to be installed at all.

That's your first line of defense.

If you want people to be able to develop the grammar files on Windows, you can do it. There are ports of these things to Windows. Cygwin, MinGW-W32 and others.

I have used compile-time parsing in production for great effect. Think protobufs except without the preprocessing steps - you can embed a human-readable schema right into your C++ sources.

Most of them have poor debugging tools, one has to try to guess what the piles of generated code actually do, hence why they are traditionally only used to bootstrap a compiler, and eventually the parser gets hand written.

I understand the biggest issue with automatically generated parsers is error handling, i.e. pleasant and precise error messages to the user and recovering from partial parse failures (for example for tooling like completion).

> lex + yacc

They're abysmal to use, have poor interfaces and poor error handling facilities.

> antlr

At least when I tried it years ago, it was an unapproachable mess of java tooling and editors.

> parsec

Is a parser combinator. This is different than a generator.

> ragel

Not heard about this.

Try Antlr 4. It's more approachable.

I'm the author, let me just answer this one. Spirit produces recursive descent parser, ctpg produces LR(1). So the parse speed is just much better. And the set of possible language grammars is bigger. Plus (this is just my opinion) ctpg just looks more intuitive.

Reply on news.ycombinator.com