Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext
Defining EDSL Grammars

In this section we'll see how to use Proto to define a grammar for your EDSL and use it to validate expression templates, giving short, readable compile-time errors for invalid expressions.

[Tip] Tip

You might think that this is a backwards way of doing things. If Proto let me select which operators to overload, my users wouldn't be able to create invalid expressions in the first place, and I wouldn't need a grammar at all! That may be true, but there are reasons for preferring to do things this way.

First, it lets you develop your EDSL rapidly -- all the operators are there for you already! -- and worry about invalid syntax later.

Second, it might be the case that some operators are only allowed in certain contexts within your EDSL. This is easy to express with a grammar, and hard to do with straight operator overloading.

Third, using an EDSL grammar to flag invalid expressions can often yield better errors than manually selecting the overloaded operators.

Fourth, the grammar can be used for more than just validation. You can use your grammar to define tree transformations that convert expression templates into other more useful objects.

If none of the above convinces you, you actually can use Proto to control which operators are overloaded within your domain. And to do it, you need to define a grammar!

In a previous section, we used Proto to define an EDSL for a lazily evaluated calculator that allowed any combination of placeholders, floating-point literals, addition, subtraction, multiplication, division and grouping. If we were to write the grammar for this EDSL in EBNF, it might look like this:

group       ::= '(' expression ')'
factor      ::= double | '_1' | '_2' | group
term        ::= factor (('*' factor) | ('/' factor))*
expression  ::= term (('+' term) | ('-' term))*

This captures the syntax, associativity and precedence rules of a calculator. Writing the grammar for our calculator EDSL using Proto is even simpler. Since we are using C++ as the host language, we are bound to the associativity and precedence rules for the C++ operators. Our grammar can assume them. Also, in C++ grouping is already handled for us with the use of parenthesis, so we don't have to code that into our grammar.

Let's begin our grammar for forward-declaring it:

struct CalculatorGrammar;

It's an incomplete type at this point, but we'll still be able to use it to define the rules of our grammar. Let's define grammar rules for the terminals:

struct Double
  : proto::terminal< proto::convertible_to< double > >
{};

struct Placeholder1
  : proto::terminal< placeholder<0> >
{};

struct Placeholder2
  : proto::terminal< placeholder<1> >
{};

struct Terminal
  : proto::or_< Double, Placeholder1, Placeholder2 >
{};

Now let's define the rules for addition, subtraction, multiplication and division. Here, we can ignore issues of associativity and precedence -- the C++ compiler will enforce that for us. We only must enforce that the arguments to the operators must themselves conform to the CalculatorGrammar that we forward-declared above.

struct Plus
  : proto::plus< CalculatorGrammar, CalculatorGrammar >
{};

struct Minus
  : proto::minus< CalculatorGrammar, CalculatorGrammar >
{};

struct Multiplies
  : proto::multiplies< CalculatorGrammar, CalculatorGrammar >
{};

struct Divides
  : proto::divides< CalculatorGrammar, CalculatorGrammar >
{};

Now that we've defined all the parts of the grammar, we can define CalculatorGrammar:

struct CalculatorGrammar
  : proto::or_<
        Terminal
      , Plus
      , Minus
      , Multiplies
      , Divides
    >
{};

That's it! Now we can use CalculatorGrammar to enforce that an expression template conforms to our grammar. We can use proto::matches<> and BOOST_MPL_ASSERT() to issue readable compile-time errors for invalid expressions, as below:

template< typename Expr >
void evaluate( Expr const & expr )
{
    BOOST_MPL_ASSERT(( proto::matches< Expr, CalculatorGrammar > ));
    // ...
}

PrevUpHomeNext