Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

8. Dealing with associativity

[Note] Note

Note that you can find everything that has been included and defined so far here.

Let's add division to our calculator language. Since it has the same precedence as multiplication, it should be added to that layer:

> #include <boost/mpl/divides.hpp>
> template <class L, class R> struct eval_binary_op<L, '/', R> : boost::mpl::divides<L, R>::type {};
> using divides_token = token<lit_c<'/'>>;
> using mult_exp2 = \
...> foldl_start_with_parser< \
...>   sequence<one_of<times_token, divides_token>, int_token>, \
...>   int_token, \
...>   boost::mpl::quote2<binary_op> \
...> >;
> using exp_parser16 = \
...> build_parser< \
...>   foldl_start_with_parser< \
...>     sequence<one_of<plus_token, minus_token>, mult_exp2>, \
...>     mult_exp2, \
...>     boost::mpl::quote2<binary_op> \
...>   > \
...> >;

copy-paste friendly version

We have to include <boost/mpl/divides.hpp> to get a metafunction for doing a division. We need to extend the eval_binary_op metafunction to support division as well. We had to introduce a new token, divides_token that can parse the / symbol.

We have extended mult_exp1 to accept either a times_token or a divides_token as the operator. This extended parser is called mult_exp2.

We have written a new parser, exp_parser16 which is the same as exp_parser15 but uses mult_exp2 instead of mult_exp1. This can parse expressions using division as well (and this new operator has the right precedence). Let's try it out:

> exp_parser16::apply<BOOST_METAPARSE_STRING("8 / 4")>::type
mpl_::integral_c<int, 2>

This works as expected. But what should be the value of 8 / 4 / 2? The answer can be either 1 or 4 depending on the associativity of the division operator. If it is left associative, then this expressions is interpreted as (8 / 4) / 2 and the result is 1. If it is right associative, this expression is interpreted as 8 / (4 / 2) and the result is 4.

Try to guess which result our current implementation gives before trying it out. Once you have verified the current behaviour, continue reading.

[Note] Note

Note that you can find everything that has been included and defined so far here.

Here is a diagram showing how our current parser processes the expression 8 / 4 / 2:

It takes the first number, 8, divides it by the second one, 4 and then it divides the result with the third one, 2. This means, that in our current implementation, division is left associative: 8 / 4 / 2 means (8 / 4) / 2.

Another thing to note is that the initial value is 8 and the list of values foldl iterates over is "/ 4", "/ 2".


PrevUpHomeNext