7 ms·
C++ Compile Time Parser Generator
- Zagitta 5y agoAs technically interesting this is, it's certainly going to be surefire way to kill your compile time :-)
- beached_whale 5y agoDoes 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
- gpderetta 5y agoIt would be interesting to compare compiling a grammar written with this against generating it with flex/bison and compiling the generated code.
- hamstergene 5y agoHas 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.
- anamax 5y agoYou say that like it's a bad thing. https://xkcd.com/303/ https://xkcd.com/303/
- Foomf 5y agoI wonder how this compares to boost spirit.
- xyzzy_plugh 5y agoWell 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?
- ncmncm 5y agoLex, 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.
- klodolph 5y agoFlex 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.
- EuAndreh 5y agolex and yacc depend on global variables, flex and bison, which are one the implementations of lex and yacc, don't.
- klodolph 5y agoIs 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.
- henning 5y agoC++ compile times are super fast so this doesn't exacerbate a problem that causes people to give up and just use C99.
- deleted 5y ago[deleted]
- pjmlp 5y agoYou mean the language where header libraries have become fashionable?
- Terry_Roll 5y agoSo who here has compile times going into days, ie whats the longest you have to wait for your code to compile?
- 112233 5y agoBetter question: how long does it take to debug such code?
- Terry_Roll 5y agoDepends on what your cpu microcode and OS has been programmed to do.
- deleted 5y ago[deleted]
- vnorilo 5y agoDid 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)
- peter-winter 5y agoIt 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.
- fjfaase 5y agoInteresting 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 https://github.com/FransFaase )
- peter-winter 5y agoWell, 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.
- fjfaase 5y agoThat is really much longer than would expect. Sounds like using the C++ compiler for this purpose is not working well.
- peter-winter 5y agoNot 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.
- peter-winter 5y agoI just relased a new version. GCC compiles a JSON parser example in less than 8 seconds. Still on a low resource VM.
- macgyverismo 5y agoI 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
- gpderetta 5y agoThis 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.
- peter-winter 5y agoYes 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.
- gpderetta 5y agoThank 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?
- peter-winter 5y agoPersonal. But would galdly use it in production if given opportunity.