<CODE>true</CODE> and <CODE>false</CODE>.   Nonterminal symbols representexpressions containing the operators <CODE>and</CODE>, <CODE>or</CODE>, and<CODE>not</CODE>.  The grammar is defined asfollows<A NAME="fn1"></A><A HREF="#footnote1"><SUP>1</SUP></A>:</P><A NAME="auto1089"></A><PRE>    BooleanExp ::= VariableExp | Constant | OrExp | AndExp | NotExp |                   '(' BooleanExp ')'    AndExp ::= BooleanExp  'and' BooleanExp    OrExp ::= BooleanExp  'or' BooleanExp    NotExp ::= 'not' BooleanExp    Constant ::= 'true' |  'false'    VariableExp ::= 'A' | 'B' | ... | 'X' | 'Y' | 'Z'</PRE><A NAME="auto1090"></A><P>We define two operations on Boolean expressions. The first,<CODE>Evaluate</CODE>, evaluates a Boolean expression in a contextthat assigns a true or false value to each variable.  The secondoperation, <CODE>Replace</CODE>, produces a new Boolean expression byreplacing a variable with an expression. <CODE>Replace</CODE> showshow the Interpreter pattern can be used for more than just evaluatingexpressions. In this case, it manipulates the expression itself.</P><A NAME="variableexp"></A><P>We give details of just the <CODE>BooleanExp</CODE>,<CODE>VariableExp</CODE>, and <CODE>AndExp</CODE> classes here. Classes<CODE>OrExp</CODE> and <CODE>NotExp</CODE> are similar to <CODE>AndExp</CODE>.The <CODE>Constant</CODE> class represents the Boolean constants.</P><A NAME="auto1091"></A><P><CODE>BooleanExp</CODE> defines the interface for all classes that definea Boolean expression:</P><A NAME="auto1092"></A><PRE>    class BooleanExp {    public:        BooleanExp();        virtual ~BooleanExp();            virtual bool Evaluate(Context&amp;) = 0;        virtual BooleanExp* Replace(const char*, BooleanExp&amp;) = 0;        virtual BooleanExp* Copy() const = 0;    };</PRE><A NAME="auto1093"></A><P>The class <CODE>Context</CODE> defines a mapping from variables toBoolean values, which we represent with the C++ constants<CODE>true</CODE> and <CODE>false</CODE>. <CODE>Context</CODE> has thefollowing interface:</P><A NAME="auto1094"></A><PRE>    class Context {    public:        bool Lookup(const char*) const;        void Assign(VariableExp*, bool);    };</PRE><A NAME="auto1095"></A><P>A <CODE>VariableExp</CODE> represents a named variable:</P><A NAME="auto1096"></A><PRE>    class VariableExp : public BooleanExp {    public:        VariableExp(const char*);        virtual ~VariableExp();            virtual bool Evaluate(Context&amp;);        virtual BooleanExp* Replace(const char*, BooleanExp&amp;);        virtual BooleanExp* Copy() const;    private:        char* _name;    };</PRE><A NAME="auto1097"></A><P>The constructor takes the variable's name as an argument:</P><A NAME="auto1098"></A><PRE>    VariableExp::VariableExp (const char* name) {        _name = strdup(name);    }</PRE><A NAME="auto1099"></A><P>Evaluating a variable returns its value in the current context.</P><A NAME="auto1100"></A><PRE>    bool VariableExp::Evaluate (Context&amp; aContext) {        return aContext.Lookup(_name);    }</PRE><A NAME="auto1101"></A><P>Copying a variable returns a new <CODE>VariableExp</CODE>:</P><A NAME="auto1102"></A><PRE>    BooleanExp* VariableExp::Copy () const {        return new VariableExp(_name);    }</PRE><A NAME="auto1103"></A><P>To replace a variable with an expression, we check to see if thevariable has the same name as the one it is passed as an argument:</P><A NAME="auto1104"></A><PRE>    BooleanExp* VariableExp::Replace (        const char* name, BooleanExp&amp; exp    ) {        if (strcmp(name, _name) == 0) {            return exp.Copy();        } else {            return new VariableExp(_name);       }    }</PRE><A NAME="andexp"></A><P>An <CODE>AndExp</CODE> represents an expression made by ANDing twoBoolean expressions together.</P><A NAME="auto1105"></A><PRE>    class AndExp : public BooleanExp {    public:        AndExp(BooleanExp*, BooleanExp*);        virtual ~ AndExp();            virtual bool Evaluate(Context&amp;);        virtual BooleanExp* Replace(const char*, BooleanExp&amp;);        virtual BooleanExp* Copy() const;    private:        BooleanExp* _operand1;        BooleanExp* _operand2;    };        AndExp::AndExp (BooleanExp* op1, BooleanExp* op2) {        _operand1 = op1;        _operand2 = op2;    }</PRE><A NAME="auto1106"></A><P>Evaluating an <CODE>AndExp</CODE> evaluates its operands and returnsthe logical "and" of the results.</P><A NAME="auto1107"></A><PRE>    bool AndExp::Evaluate (Context&amp; aContext) {        return            _operand1->Evaluate(aContext) &amp;&amp;            _operand2->Evaluate(aContext);    }</PRE><A NAME="auto1108"></A><P>An <CODE>AndExp</CODE> implements <CODE>Copy</CODE> and <CODE>Replace</CODE> bymaking recursive calls on its operands:</P><A NAME="auto1109"></A><PRE>    BooleanExp* AndExp::Copy () const {        return            new AndExp(_operand1->Copy(), _operand2->Copy());    }        BooleanExp* AndExp::Replace (const char* name, BooleanExp&amp; exp) {        return            new AndExp(                _operand1->Replace(name, exp),                _operand2->Replace(name, exp)            );    }</PRE><A NAME="auto1110"></A><P>Now we can define the Boolean expression</P><A NAME="auto1111"></A><PRE>    (true and x) or (y and (not x))</PRE><A NAME="auto1112"></A><P>and evaluate it for a given assignment of <CODE>true</CODE> or<CODE>false</CODE> to the variables <CODE>x</CODE> and <CODE>y</CODE>:</P><A NAME="auto1113"></A><PRE>    BooleanExp* expression;    Context context;        VariableExp* x = new VariableExp("X");    VariableExp* y = new VariableExp("Y");        expression = new OrExp(        new AndExp(new Constant(true), x),        new AndExp(y, new NotExp(x))    );        context.Assign(x, false);    context.Assign(y, true);        bool result = expression->Evaluate(context);</PRE><A NAME="auto1114"></A><P>The expression evaluates to <CODE>true</CODE> for this assignment to<CODE>x</CODE> and <CODE>y</CODE>.  We can evaluate the expression with adifferent assignment to the variables simply by changing thecontext.</P><A NAME="auto1115"></A><P>Finally, we can replace the variable <CODE>y</CODE> with a new expression andthen reevaluate it:</P><A NAME="auto1116"></A><PRE>    VariableExp* z = new VariableExp("Z");    NotExp not_z(z);        BooleanExp* replacement = expression->Replace("Y", not_z);        context.Assign(z, true);        result = replacement->Evaluate(context);</PRE><A NAME="auto1117"></A><P>This example illustrates an important point about the Interpreterpattern: many kinds of operations can "interpret" a sentence.  Ofthe three operations defined for <CODE>BooleanExp</CODE>,<CODE>Evaluate</CODE> fits our idea of what an interpreter should do mostclosely&#151;that is, it interprets a program or expression and returns asimple result.</P><A NAME="variable-w-interp2"></A><P>However, <CODE>Replace</CODE> can be viewed as an interpreter as well.It's an interpreter whose context is the name of the variable beingreplaced along with the expression that replaces it, and whose resultis a new expression.  Even <CODE>Copy</CODE> can be thought of as aninterpreter with an empty context.  It may seem a little strange toconsider <CODE>Replace</CODE> and <CODE>Copy</CODE> to be interpreters, becausethese are just basic operations on trees.  The examples in<A HREF="pat5kfs.htm" TARGET="_mainDisplayFrame">Visitor (331)</A> illustrate how all three operations can berefactored into a separate "interpreter" visitor, thus showing thatthe similarity is deep.</P><A NAME="auto1118"></A><P>The Interpreter pattern is more than just an operation distributedover a class hierarchy that uses the <A HREF="pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>pattern.  We consider <CODE>Evaluate</CODE> an interpreter because wethink of the <CODE>BooleanExp</CODE> class hierarchy as representing alanguage.  Given a similar class hierarchy for representing automotivepart assemblies, it's unlikely we'd consider operations like<CODE>Weight</CODE> and <CODE>Copy</CODE> as interpreters even though theyare distributed over a class hierarchy that uses the Compositepattern&#151;we just don't think of automotive parts as a language.  It'sa matter of perspective; if we started publishing grammars ofautomotive parts, then we could consider operations on those parts tobe ways of interpreting the language.</P><A NAME="knownuses"><A><H2><A HREF="#relatedpatterns"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: Related Patterns"></A> Known Uses</H2> <A NAME="smalltalk-use-interp"></A><A NAME="spectalk-use-interp"></A><P>The Interpreter pattern is widely used in compilers implemented withobject-oriented languages, as the Smalltalk compilers are.  SPECTalkuses the pattern to interpret descriptions of input fileformats [<A HREF="bibfs.htm#szafron_tools92" TARGET="_mainDisplayFrame">Sza92</A>].  The QOCA constraint-solving toolkituses it to evaluate constraints [<A HREF="bibfs.htm#qoca" TARGET="_mainDisplayFrame">HHMV92</A>].</P><A NAME="auto1119"></A><P>Considered in its most general form (i.e., an operation distributedover a class hierarchy based on the Composite pattern), nearly everyuse of the Composite pattern will also contain the Interpreterpattern.  But the Interpreter pattern should be reserved for thosecases in which you want to think of the class hierarchy as defining alanguage.</P><A NAME="relatedpatterns"></A><H2><A HREF="#last"><IMG SRC="gifsb/down3.gif" BORDER=0 ALT="next: navigation"></A> Related Patterns</H2> <A NAME="auto1120"></A><P><A HREF="pat4cfs.htm" TARGET="_mainDisplayFrame">Composite (163)</A>:The abstract syntax tree is an instance of the Composite pattern.</P><A NAME="auto1121"></A><P><A HREF="pat4ffs.htm" TARGET="_mainDisplayFrame">Flyweight (195)</A>shows how to share terminal symbols within the abstract syntaxtree.</P><A NAME="auto1122"></A><P><A HREF="pat5dfs.htm" TARGET="_mainDisplayFrame">Iterator (257)</A>:The interpreter can use an Iterator to traverse the structure.</P><A NAME="auto1123"></A><P><A HREF="pat5kfs.htm" TARGET="_mainDisplayFrame">Visitor (331)</A> canbe used to maintain the behavior in each node in the abstract syntaxtree in one class.</P><A NAME="last"></A><P><A HREF="#intent"><IMG SRC="gifsb/up3.gif" BORDER=0></A><BR><A HREF="pat5dfs.htm" TARGET="_mainDisplayFrame"><IMG SRC="gifsb/rightar3.gif"        ALIGN=TOP BORDER=0></A> <A HREF="pat5dfs.htm"        TARGET="_mainDisplayFrame">Iterator</A><BR><A HREF="pat5bfs.htm" TARGET="_mainDisplayFrame"><IMG SRC="gifsb/leftarr3.gif"        ALIGN=TOP BORDER=0></A> <A HREF="pat5bfs.htm"        TARGET="_mainDisplayFrame">Command</A></P><HR><A NAME="footnote1"></A><P><SUP>1</SUP>For simplicity, we ignore operator precedence andassume it's the responsibility of whichever object constructs thesyntax tree.</P></BODY></HTML>