What is the most efficient way to recalculate attributes of a Boost Spirit parse with a different symbol table?

Question

I'm using Boost Spirit to implement functionality in some software that allows the user to enter a mathematical equation that will be repeatedly applied to an input stream. Input stream values are represented as symbols using boost::spirit::qi::symbols which the user can reference in their equation. (e.g. out1 = 3 * in1 + in2)

Parsing and compiling the user's equation is not performance sensitive but calculating its output value is as it forms part of a time-critical pipeline.

The standard way Spirit is used within the documentation is to calculate the output (attribute) of an input as it is parsed. However, as between each calculation only the attribute values of the symbols (out1, in1, etc.) will have changed, it feels like there might be a more efficient way to achieve this, perhaps by caching the abstract syntax tree of the expression and reiterating through it.

What is the most efficient way to recalculate the value of this (fixed) equation given a new set of symbol values?

Fragmentation

Answer 1

The standard way Spirit is used is not as limited as you seem to think.

While you can use it to calulate an immediate value on the fly, it is much more usual to build an AST tree in the output attribute, that can be transformed (simplified, optimized) and interpreted (e.g. emitting virtual machine or even assembly instructions).

The compiler tutorials show this in full fledged, but the calculator samples are very close to what you seem to be looking for: http://www.boost.org/doc/libs/1_55_0/libs/spirit/example/qi/compiler_tutorial/

• calc1 in example/qi/compiler_tutorial/calc1.cpp

  Plain calculator example demonstrating the grammar. The parser is a syntax checker only and does not do any semantic evaluation.

• calc2 in example/qi/compiler_tutorial/calc2.cpp

  A Calculator example demonstrating the grammar and semantic actions using plain functions. The parser prints code suitable for a stack based virtual machine.

• calc3 in example/qi/compiler_tutorial/calc3.cpp

  A calculator example demonstrating the grammar and semantic actions using phoenix to do the actual expression evaluation. The parser is essentially an "interpreter" that evaluates expressions on the fly.

Here's where it gets interesting for you, since it stops doing the calculations during parsing:

• calc4 in example/qi/compiler_tutorial/calc4.cpp

  A Calculator example demonstrating generation of AST. The AST, once created, is traversed,

  1. To print its contents and
  2. To evaluate the result.
     
     

• calc5 in example/qi/compiler_tutorial/calc5.cpp

  Same as Calc4, this time, we'll incorporate debugging support, plus error handling and reporting.

• calc6 in example/qi/compiler_tutorial/calc6.cpp

  Yet another calculator example! This time, we will compile to a simple virtual machine. This is actually one of the very first Spirit example circa 2000. Now, it's ported to Spirit2.

• calc7 in example/qi/compiler_tutorial/calc7/main.cpp

  Now we'll introduce variables and assignment. This time, we'll also be renaming some of the rules -- a strategy for a grander scheme to come ;-)

  This version also shows off grammar modularization. Here you will see how expressions and statements are built as modular grammars.

• calc8 in example/qi/compiler_tutorial/calc8/main.cpp

  Now we'll introduce boolean expressions and control structures. Is it obvious now what we are up to? ;-)

I'm sure you'll find lots of inspiration towards the end of the tutorial!

Pornography

examples starting from calc5 show error if not compiled with c++11 or above as reported here link. - compiling with clang (Apple LLVM version 9.0), boost version 1.57 – Ruffianism

@UtkarshBhardwaj yes, progress has been made. C++11 is a lot older than that, so if you're interested in running the samples on ancient compilers, prepare to do some manual labour, downgrade boost or a combination of that. – Pornography

In this case you can just comment out the error handler: wandbox.org/permlink/UNHngZYWyzOFD68c @UtkarshBhardwaj alternatively you can workaround the result-of failure using phoenix::bind: wandbox.org/permlink/RmXZ53Q98TZnIKE9 or indeed with the phoenix::function: wandbox.org/permlink/CVfoYVUMMzbU33v2 I'd say that the problem is a bug in Phoenix V2 variadics support (using macros), but I don't think anyone is going to fix that. – Pornography

Answer 2

You can build your own tree of calculator objects which mirrors the AST. So for your example out1 = 3 * in1 + in2 the AST is:

*
  3
  +
    in1
    in2

So you'd build an object hierarchy like this:

Multiplier(
  Constant(3),
  Adder(
    Variable(&in1),
    Variable(&in2)
  )
)

With classes something like:

class Result {
  virtual double value() = 0;
};

class Multiplier : public Result {
  Multiplier(Result* lhs, Result* rhs);
  double value() { return _lhs->value() * _rhs->value(); }
}

Sobriquet