Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

• Express instances of the problem as sentences in a simple language.
• Build an interpreter that solves the problem by interpreting these sentences.

expression ::= literal | alternation | sequence | 
	repetition |'(' expression ')'
alternation ::= expression  '|' expression
sequence ::= expression '&' expression
repetition ::= expression '*'
literal ::= 'a' | 'b' | 'c' | ... |
	{ 'a' | 'b' | 'c' | ... }*

• The Interpreter pattern uses a class to represent each grammar rule.
• Symbols on the right-hand side of the rule are instance variables of these classes.

• Abstract syntax tree made up of instances of these classes for (raining & (dogs | cats)*)

• Interpret takes as an argument the context in which to interpret the expression.

• Use the Interpreter pattern when there is a language to interpret, and you can represent statements in the language as abstract syntax trees.
• The Interpreter pattern works best when

• AbstractExpression (RegularExpression)
• declares an abstract Interpret operation that is common to all nodes in the abstract syntax tree.
• TerminalExpression (LiteralExpression)
• implements an Interpret operation associated with terminal symbols in the grammar.
• an instance is required for every terminal symbol in a sentence.
• NonterminalExpression (AlternationExpression, RepetitionExpression, SequenceExpressions)
• one such class is required for every rule R ::= R₁ R₂ ... R_n in the grammar.
• maintains instance variables of type AbstractExpression for each of the symbols R₁ through R_n.
• implements an Interpret operation for nonterminal symbols in the grammar.
• Context
• contains information that's global to the interpreter.
• Client
• builds (or is given) an abstract syntax tree representing a particular sentence in the language that the grammar defines.
• invokes the Interpret operation.

• The client builds (or is given) the sentence as an abstract syntax tree of NonterminalExpression and TerminalExpression instances.
• The client initializes the context and invokes the Interpret operation.
• Each NonterminalExpression node defines Interpret in terms of Interpret on each subexpression.
• The Interpret operation of each TerminalExpression defines the base case in the recursion.
• The Interpret operations at each node use the context to store and access the state of the interpreter.

1. It's easy to change and extend the grammar that is represented by classes.
2. Implementing the grammar is easy, too.
3. Complex grammars are hard to maintain.
4. Adding new ways to interpret expressions by adding new operations in classes.

• The Interpreter and Composite patterns share many implementation issues.

• Example 1: Smalltalk

    expression ::= literal | alternation | sequence | 
		repetition |'(' expression ')'
    alternation ::= expression  '|' expression
    sequence ::= expression '&' expression
    repetition ::= expression 'repeat'
    literal ::= 'a' | 'b' | 'c' | ... |
     	{ 'a' | 'b' | 'c' | ... }*

    match: inputState
        ^ expression2 match: 
			(expression1 match: inputState).

• AlternationExpression

    match: inputState
        | finalState |
        finalState := alternative1 match: inputState.
        finalState addAll: 
			(alternative2 match: inputState).
        ^ finalState

• RepetitionExpression

    match: inputState
        | aState finalState |
        aState := inputState.
        finalState := inputState copy.
        [aState isEmpty]
            whileFalse:
                [aState := repetition 
					match: aState.
                finalState addAll: aState].
            ^ finalState

• LiteralExpression

    match: inputState
        | finalState tStream |
        finalState := Set new.
        inputState
            do:
                [:stream | tStream := stream copy.
                    (tStream nextAvailable:
                         components size
                    ) = components
                        ifTrue: 
				   [finalState add: tStream]
                ].
            ^ finalState

• RegularExpression class

    & aNode
        ^ SequenceExpression new
            expression1: self expression2: aNode asRExp
    
    repeat
        ^ RepetitionExpression new repetition: self
    
    | aNode
        ^ AlternationExpression new
        alternative1: self alternative2: aNode asRExp
    
    asRExp 
        ^ self

• String class

    & aNode
        ^ SequenceExpression new
            expression1:self asRExp expression2:aNode asRExp
    
    repeat
        ^ RepetitionExpression new repetition: self
    
    | aNode
        ^ AlternationExpression new
            alternative1: self asRExp 
		alternative2: aNode asRExp
    
    asRExp
        ^ LiteralExpression new components: self

    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'

• Two operations on Boolean expressions.
• Evaluate: evaluates a Boolean expression in a context that assigns a true or false value to each variable.

• Replace: produces a new Boolean expression by replacing a variable with an expression.

    class BooleanExp {
    public:
        BooleanExp();
        virtual ~BooleanExp();
    
        virtual bool Evaluate(Context&) = 0;
        virtual BooleanExp* Replace
			(const char*, BooleanExp&) = 0;
        virtual BooleanExp* Copy() const = 0;
    };

    class Context {
    public:
        bool Lookup(const char*) const;
        void Assign(VariableExp*, bool);
    };

    class VariableExp : public BooleanExp {
    public:
        VariableExp(const char*);
        virtual ~VariableExp();
    
        virtual bool Evaluate(Context&);
        virtual BooleanExp* Replace
			(const char*, BooleanExp&);
        virtual BooleanExp* Copy() const;
    private:
        char* _name;
    };

    VariableExp::VariableExp (const char* name) {
        _name = strdup(name);
    }

        bool VariableExp::Evaluate (Context& aContext) {
        return aContext.Lookup(_name);
    }

    BooleanExp* VariableExp::Copy () const {
        return new VariableExp(_name);
    }

    BooleanExp* VariableExp::Replace (
        const char* name, BooleanExp& exp
    ) {
        if (strcmp(name, _name) == 0) {
            return exp.Copy();
        } else {
            return new VariableExp(_name);
       }
    }

    class AndExp : public BooleanExp {
    public:
        AndExp(BooleanExp*, BooleanExp*);
        virtual ~ AndExp();
    
        virtual bool Evaluate(Context&);
        virtual BooleanExp* Replace
			(const char*, BooleanExp&);
        virtual BooleanExp* Copy() const;
    private:
        BooleanExp* _operand1;
        BooleanExp* _operand2;
    };
    
    AndExp::AndExp (BooleanExp* op1, BooleanExp* op2) 
   	{
        _operand1 = op1;
        _operand2 = op2;
    }

    bool AndExp::Evaluate (Context& aContext) {
        return
            _operand1->Evaluate(aContext) &&
            _operand2->Evaluate(aContext);
    }

    BooleanExp* AndExp::Copy () const {
        return
            new AndExp(_operand1->Copy(), _operand2->Copy());
    }
    
    BooleanExp* AndExp::Replace 
			(const char* name, BooleanExp& exp) {
        return
            new AndExp(
                _operand1->Replace(name, exp),
                _operand2->Replace(name, exp)
            );
    }

    (true and x) or (y and (not x))

    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);

• Replace the variable y with a new expression and then reevaluate it:

    VariableExp* z = new VariableExp("Z");
    NotExp not_z(z);
    
    BooleanExp* replacement = 
		expression->Replace("Y", not_z);
    
    context.Assign(z, true);
    
    result = replacement->Evaluate(context);

• Nearly every use of the Composite pattern will also contain the Interpreter pattern.
• The Interpreter pattern should be reserved for those cases in which you want to think of the class hierarchy as defining a language.

• Composite: The abstract syntax tree is an instance of the Composite pattern.