Interpreter Pattern

개념
- 간단한 언어의 문법을 정의하는 방법과 그 언어로 문장을 구성하는 방법, 문장을 해석하는 방법을 제시

I. 의도

     간단한 언어의 문법을 정의하는 방법과 그 언어로 문장을 구성하는 방법, 문장을 해석하는 방법을 제시

II. 활용 

    해석이 필요한 언어가 존재하거나 추상구문트리로 언어에 정의된 문장을 표현하고자 할 때

    정의할 언어 문법이 간단하고, 효율성은 큰 고려 사항이 아닐 때

III. 장점

  • 문법의 변경과 확장이 쉽다
  • 문법의 구현이 용이하다
  • 표현식을 해석하는 새로운 방법을 추가할 수 있다  - 새 방법 계속 추가해야 할 때는 visitor 패턴이 좋다

IV. 단점: 복잡한 문법은 관리하기 어렵다

관련 패턴: 추상 구문 트리는 Composite 패턴의 한 인스턴스로 볼 수 있다. 하나의 구문 트리 내에 여러 개의 터미널 기호를 공유하기 위해서 Flyweight 패턴을 적용할 수 있다.

Interpreter는 Iterator를 이용해서 자신의 구조를 순회한다.

Visitor 패턴을 이용하면 하나의 클래스에 정의된 구문 트리의 각 노드에 대한 상태를 관리할 수 있다.

  • AbstractExpression: 추상 구문 트리에 속한 모든 노드에 해당하는 클래스들이 공통으로 가져야 할 Interpret() 오퍼레이션을 추상 오퍼레이션으로 정의한다.
  • TerminalExpression: 문법에 정의한 터미널 기호와 관련된 해석 방법을 구현한다. 문장을 구성하는 모든 터미널 기호에 대해서 해당 클래스를 만들어야 한다.
  • NonterminalExpression: 문법의 오른편에 나타나는 모든 기호에 대해서 클래스를 정의해야 한다. 문법에

R :: = R1 R2 … Rn

을 정의하고 있다면 R 에 대해서 NonterminalExpression 에 해당하는 클래스를 정의해야 한다. 또한 규칙의 오른쪽에 나타난 R1 에서 Rn 에 이르기까지의 모든 기호에 대응하는 인스턴스 변수들을 정의해야 한다. 또한 터미널 기호가 아닌 모든 기호들에 대해서 Interpret() 오퍼레이션을 구현해야 한다. 이 Interpret() 오퍼레이션은 R1 에서 Rn 에 이르기까지의 각 인스턴스 변수를 재귀적으로 호출하는 것이 일반적이다.

Context: 번역기에 대한 포괄적인 정보를 포함한다.

Client: 언어로 정의한 특정 문장을 나타내는 추상 구문 트리이다. 이 추상 구문 트리는 NonterminalExpression 과 TerminalExpression 클래스의 인스턴스로 구성된다. 이 인스턴스의 Interpret() 오퍼레이션을 호출한다.

 

 

소스코드

 

The following Reverse Polish notation example illustrates the interpreter pattern. The grammar
expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable  ::= 'a' | 'b' | 'c' | ... | 'z'
digit = '0' | '1' | ... '9'
number ::= digit | digit number

defines a language which contains reverse Polish expressions like:
a b +
a b c + -
a b + c a - -

Following the interpreter pattern there is a class for each grammar rule

import java.util.Map;

 

interface Expression {

    public int interpret(Map<String,Expression> variables);

}

 

class Number implements Expression {

    private int number;

    public Number(int number)       { this.number = number; }

    public int interpret(Map<String,Expression> variables)  { return number; }

}

 

class Plus implements Expression {

    Expression leftOperand;

    Expression rightOperand;

    public Plus(Expression left, Expression right) {

        leftOperand = left;

        rightOperand = right;

    }

 

    public int interpret(Map<String,Expression> variables)  {

        return leftOperand.interpret(variables) + rightOperand.interpret(variables);

    }

}

 

class Minus implements Expression {

    Expression leftOperand;

    Expression rightOperand;

    public Minus(Expression left, Expression right) {

        leftOperand = left;

        rightOperand = right;

    }

 

    public int interpret(Map<String,Expression> variables)  {

        return leftOperand.interpret(variables) - rightOperand.interpret(variables);

    }

}

 

class Variable implements Expression {

    private String name;

    public Variable(String name)       { this.name = name; }

    public int interpret(Map<String,Expression> variables)  {

        if(null==variables.get(name)) return 0; //Either return new Number(0).

        return variables.get(name).interpret(variables);

    }

}

 

While the interpreter pattern does not address parsing[2] a parser is provided for completeness.

import java.util.Map;

import java.util.Stack;

 

class Evaluator implements Expression {

    private Expression syntaxTree;

 

    public Evaluator(String expression) {

        Stack<Expression> expressionStack = new Stack<Expression>();

        for (String token : expression.split(" ")) {

            if  (token.equals("+")) {

                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());

                expressionStack.push( subExpression );

            }

            else if (token.equals("-")) {

                // it's necessary remove first the right operand from the stack

                Expression right = expressionStack.pop();

                // ..and after the left one

                Expression left = expressionStack.pop();

                Expression subExpression = new Minus(left, right);

                expressionStack.push( subExpression );

            }

            else                       

                expressionStack.push( new Variable(token) );

        }

        syntaxTree = expressionStack.pop();

    }

 

    public int interpret(Map<String,Expression> context) {

        return syntaxTree.interpret(context);

    }

}

 

Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.

import java.util.Map;

import java.util.HashMap;

 

public class InterpreterExample {

    public static void main(String[] args) {

        String expression = "w x z - +";

        Evaluator sentence = new Evaluator(expression);

        Map<String,Expression> variables = new HashMap<String,Expression>();

        variables.put("w", new Number(5));

        variables.put("x", new Number(10));

        variables.put("z", new Number(42));

        int result = sentence.interpret(variables);

        System.out.println(result);

    }

}

 

댓글