- Whats in a Grammar?
- Applications for a Simple Boolean Grammar
- Putting It All Together
- Running the Code
- Using the Interpreter Pattern
- Conclusion
- Additional Reading
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Applications for a Simple Boolean Grammar
Let’s make the discussion more concrete by considering a simple Boolean grammar. Figure 1 shows a common application for such a grammar.
)
Figure 1 A policy-based network management system.
In Figure 1, the Network Manager wants to create a dedicated forwarding path through the network from router 1 to router 5. (My earlier articles discussed this process in some detail, so if you want to put yourself to sleep, see "C++ Command Pattern for Network Operations.") For now, we just want to ask the network if it has the resources (buffers, bandwidth, links, etc.) to support the placement of a specified path. To do this, the network manager specifies a request using a simple grammar. The rule processor takes the request and translates it into a network-specific language (SNMP, COPS, etc.). The rule processor then engages in a dialogue with the network to determine whether the request can be fulfilled. The result is reported back to the network manager (as yes or no).
Figure 1 illustrates the use of simple rules to determine the configuration of a complex network. This process is often referred to as network modeling, in which you try what-if scenarios. In many cases, there is no network, just a simulator. The main point here is that when using a simple grammar, it’s possible to control very complex entities.
Let’s review some simple C++ code to implement the interpreter pattern. (For some background on this pattern, see Design Patterns: Elements of Reusable Object-Oriented Software by Erich Gamma et al.)
A Boolean Expression
Listing 2 contains a Boolean expression class.
Listing 2 A Boolean expression class.
class BooleanExpression
{
public:
explicit BooleanExpression(void);
virtual ~BooleanExpression(void);
virtual bool Evaluate(Context&) = 0;
};
The class in Listing 2 will be used to create subclasses for more complex Boolean statements. Listing 3 provides the default constructor and destructor pair for the BooleanExpression class.
Listing 3 Default constructor and destructor pair for BooleanExpression.
BooleanExpression::BooleanExpression(void)
{
}
BooleanExpression::~BooleanExpression(void)
{
}
A Context for Boolean Expressions
The parameters for a Boolean expression define the context for the associated operation (AND, OR, NOT, and so on). The class in Listing 4 models a context.
Listing 4 Modeling a Boolean context.
class Context
{
public:
explicit Context(void);
virtual ~Context(void);
bool Lookup(const char*) const;
void AssignX(VariableExpression*, bool);
void AssignY(VariableExpression*, bool);
private:
char* xName;
char* yName;
bool xValue;
bool yValue;
};
The main items of interest in Listing 4 are the following methods:
- Lookup()
- AssignX()
- AssignY()
The Lookup() method is used to retrieve from the context a specified parameter (such as X) and its Boolean value (true or false) . The AssignX() and AssignY() methods do the reverse of Lookup() in that they insert parameters and values into the context. The latter are then stored in the context’s private data members.
Let’s look at a class that models a specific Boolean expression.
A Derived Boolean Expression: OrExpression
Listing 5 is our first concrete Boolean expression derived from BooleanExpression. The constructor takes two parameters that are pointers to instances of BooleanExpression. Those two parameters are stored in the private data members. Remember the context from earlier? Well, this is used during the evaluation of the Boolean OR expression.
Listing 5 A Boolean OR expression.
class OrExpression : public BooleanExpression
{
public:
explicit OrExpression(BooleanExpression*, BooleanExpression*);
virtual ~OrExpression();
virtual bool Evaluate(Context&);
private:
BooleanExpression* _operand1;
BooleanExpression* _operand2;
};
Don’t worry too much about the details of these listings. It will all become clear when I put it all together. For the moment, when I want to create an OR expression, I instantiate an object of the class OrExpression and pass in the two required parameters. Next, I update the context, at which point I can call the Evaluate() method, which then returns the required OR result. Let’s examine the similar class AndExpression.
A Derived Boolean Expression: AndExpression
AndExpression is also derived from BooleanExpression (see Listing 6). Just like OrExpression, the constructor takes two parameters that are pointers to instances of BooleanExpression. The two classes are very similar—differing only in the implementation of their Evaluate() methods.
Listing 6 A Boolean AND expression.
class AndExpression : public BooleanExpression
{
public:
explicit AndExpression(BooleanExpression*, BooleanExpression*);
virtual ~AndExpression();
virtual bool Evaluate(Context&);
private:
BooleanExpression* _operand1;
BooleanExpression* _operand2;
};
We’re nearly at a point where we can see these classes in action! I need just one more class that combines the preceding classes—this last class is called VariableExpression.
A Complete Boolean Expression: VariableExpression
The VariableExpression class in Listing 7 follows the semantics of the preceding classes.
Listing 7 The VariableExpression class.
class VariableExpression : public BooleanExpression
{
public:
explicit VariableExpression(const char*);
virtual ~VariableExpression();
virtual bool Evaluate(Context&);
char* getName();
private:
char* _name;
};
As we’ll see later, objects of this class are used as parameters to instances of the OrExpression and AndExpression classes. We’ve finally covered enough ground now to be able to define some Boolean expressions. If the next section seems a little hard to follow, take a look at the later section "Running the Code." Remember, we’re not talking about anything more complex than Boolean logic.