How to parse DSL input to high performance expression template

Question

(EDITED both title and main text and created a spin-off question that arose)

For our application it would be ideal to parse a simple DSL of logical expressions. However the way I'd like to do this is to parse (at runtime) the input text which gives the expressions into some lazily evaluated structure (an expression template) which can then be later used within more performance sensitive code.

Ideally the evaluation is as fast as possible using this technique as it will be used a large number of times with different values substituting into the placeholders each time. I'm not expecting the expression template to be equivalent in performance to say a hardcoded function that models the same function as the given input text string i.e. there is no need to go down a route of actually compiling say, c++, in situ of a running program (I believe other questions cover dynamic library compiling/loading).

My own thoughts reading examples from boost is that I can use boost::spirit to do the parsing of the input text and I'm confident I can develop the grammar I need. However, I'm not sure how I can combine the parser with boost::proto to build an executable expression template. Most examples of spirit that I've seen are merely interpreters or end up building some kind of syntax tree but go no further. Most examples of proto that I've seen assume the DSL is embedded in the host source code and does not need to be initially interpreted from a string. I'm aware that boost::spirit is actually implemented with boost::proto but not sure if this is relevant to the problem or whether that fact will suggest a convenient solution.

To re-iterate, I need to be able to make real the something like following:

const std::string input_text("a && b || c");
// const std::string input_text(get_dsl_string_from_file("expression1.dsl"));

Expression expr(input_text);

while(keep_intensively_processing) {
    ...
    Context context(…);
    // e.g. context.a = false; context.b=false; context.c=true;

    bool result(evaluate(expr, context));
    ...
}

I would really appreciate a minimal example or even just a small kernel that I can build upon that creates an expression from input text which is evaluated later in context.

I don't think this is exactly the same question as posted here: parsing boolean expressions with boost spirit as I'm not convinced this is necessarily the quickest executing way of doing this, even though it looks very clever. In time I'll try to do a benchmark of all answers posted.

Ossein

I linked an answer that does what you need. Your wording seems to suggest you'd actually want to compile from a string to an (optimized) expression template. This is obviously impossible, unless you count generating c++ code or using libclang to emit JIT-table llvm bytecode on the fly :/ – Procaine

@Procaine I don't think this question is a duplicate. As sehe says this one is impossible to solve with spirit. In one of the recent Boostcon/CppNow there was a talk about a library that supports the creation of parsers that parse at compile-time, metaparse. There are several examples (that unfortunately I'm not able to understand, but maybe someone better will). – Stillman

This one seems to be quite similar. I will try to adapt it to your problem, but I'm not confident that I will succeed. – Stillman

@cv_and_he Mmm. That's way cool (and overblown, IYAM :)) but I doubt it's what the OP needs: "... do the parsing of the input text ..." clearly implies runtime input to me. Anyways, +1 for cool new libraries and +1 for considering the OP wasn't confused :/ (oh, and voted to reopen, in case you come up with something marvelous!) – Procaine

@Procaine This is what I was able to put together. It requires c++11 and according to the documentation this approach also requires a compiler that has constexpr functions. You can download metaparse from here. evaluate ( LAMBDA ( "!a&&(false||(b&&!c||false))" ), /*a=*/false, /*b=*/true, /*c=*/false ) is an example of how to use it. If the question is reopened or someone is interested I'll try to give an explanation (although I must admit that I still have problems understanding how the semantic actions really work). – Stillman

@cv_and_he awesomeness. I trust you had some fun there. Will have a look later; family things first... – Procaine

Thanks for all the comments so far. The code that has been linked to in these comments looks totally awesome. It will take me a while to grok but I'll clarify the question in detail at some point if I find I haven't got exactly what I need. Briefly though: Input string is given at runtime (although thanks for the cool introduction to metaparse!) The resultant expression template should execute as fast as possible when supplied with values - it is accepted this won't be as fast as say a hardcoded function for the same expression (actual compilation on the fly is not needed). – Ossein

Ah, I realise I made a mistake with the question title, which may have been misleading, by using the word compile - I sort of meant "compile" in the sense of the embedded DSL expression being created, rather than C++ compile. – Ossein

Thinking about it, the "compile-time" parse is in fact a route I could go down with our application. I have therefore posted a new question here and invite cv_and_he to repost the metaparse solution there as a full answer: #17783893 – Ossein

@Ossein you should update the question with the essential bits. I've asked for reopen votes on this question. – Procaine

The question was re-opened. I too vouch in favour of posting @cv_and_he's code as an answer here, because (a) it answers the most strict interpretation of the question (b) it's awesome – Procaine

@Procaine I was planning to put that code in the new question. It seems that this one was really a duplicate. For this one I have tried modifying the calc6 example. If you think I should not post that as an answer, just say so and I'll remove it. – Stillman

I'm aiming to update this question with a better title and with emphasis on high performance which I think will make it slightly different to the duplicate question that was found but to which the existing answer will still be valid. Please bear with me - thanks for your patience. – Ossein

@Ossein @Procaine I was curious and decided to check the performance of every one of the approaches. In my test I fill a vector with 10 million random contexts, create an "expression" based on "a||(!b||c)&&!b||c&&!a", and then measure the time needed to evaluate that expression with every context. The times elapsed on my computer are these: plain c++ evaluation=3.5s, metaparse-proto=3.5s, recursive variant visitor=4.0s and finally compiler-virtual machine=5.2s. "recursive variant visitor" is the approach linked originally by sehe, and "compiler-virtual machine" is the one in my answer. – Stillman

Informative! I'm not surprised the VM approach is somewhat slower, but a more complex VM might tip the balance, as well as there's (ample) room for optimization, I suspect. – Procaine

Wow. Thanks for doing all the work for me! That's extremely useful and information, and it's pretty amazing that the visitor approach doesn't actually take much longer than just plain c++. – Ossein

I've removed my answer since it didn't really answer the question. The real answer is, as sehe mentioned in the first comment before I confused everything, you can't do that with spirit. Expression templates are a compile-time construct that encode information in their types and at run-time you need to have a well defined type. In case anyone (who can't see deleted answers) wants to see my code, it can be found here. The approach that sehe linked that seems to have better performance can be found here. – Stillman