[디자인 패턴] 행동 패턴 (3) 해석자 Interpreter

해석자 (Interpreter) 패턴

 

1. 의도

• 어떤 언어로 표현된 문장을 해석하는 방법을 제공

2. 활용

• 어떤 언어로 표현된 문장을 해석하는 번역 문제를 해결하는 것이다.

- 정규식 표현으로 문자열을 찾는 문제

정규식 문법으로 표현된 문장을 어떻게 해석하여 문자열을 찾도록 할 것인가

 

다음 정규식 문법을 생각해보자

• expression: literal '|' alternation '|' sequence '|' repetition '|' 다른 expression을 포함한다.
• alternation: expression '|' expresssion, 두 표현 중 하나가 올 수 있다.
• sequence: expression '&' expression, 두 표현 모두가 와야한다.
• repetition: epxression '*', 표현이 반복적으로 올 수 있다.
• literal: 'a' | 'b' | 'c' | ... {'a' | 'b' | ... |'z'|}*, 기본 문자로 이루어질 수 있는 모든 조합

해석자 패턴은 클래스를 이용하여 문법을 해석하고 규칙을 이용하여 구조화한다.

• 정규식 문법을 모두 포괄할 수 있는 RegularExpression 추상 클래스를 정의하고 자신에 대한 해석을 수행하는 Interpret() 인터페이스를 정의한다.
• 추상 클래스를 상속하는 LiteralExpression, AlternationExpression, SequenceExpression, RepetitionExpression은 자신의 문법에 대해 어떻게 해석해야하는 지 Interpret()을 구현한다.
• 각 표현 문법에 따라 다른 문법을 가지는 인스턴스를 포함할 수 있는데 이에 따라 전체 구조는 트리 형태가 된다.

다음 정규 표현식을 해석자 패턴 트리로 표현하면 다음과 같다.

 

raining & (dogs | cats) *

 

이에 따라 LiteralExpression, AlternationExpression, SequenceExpression, RepetitionExpression 서브 클래스는 주어진 입력 문맥에 따라 해석을 하는 구현해야한다.

• LiteralExpression: 자신의 정의한 문자와 일치하는 정보가 문맥에 있는지 확인한다.
• AlternationExpression: 자신이 가지고 있는 대안 표현이 문맥에 있는지 확인한다.
• SequenceExpression: 자신이 가지고 있는 표현 모두가 문맥에 있는지 확인한다.
• RepetitionExpression: 자신이 가지고 있는 표현이 한 번이라도 문맥에 포함되는 지 몇 번이나 포함하는지 확인한다.

- 해석자 패턴을 사용할 때 고려사항

• 정의할 문법이 간단하여 구조화 할 수있다.
• 효율성을 따지지 않아도 된다. 번역이 주된 목적

3. 참여자

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

다음 문법을 포함하고 있다면,

R ::= R_1 R_2 ... R_n

 

R 표현식에서 R_1부터 R_n까지 기호에 해당하는 인스턴스 변수를 가지고 있어야하며 이 기호에 대해 Interpret() 연산을 제공해야한다. 보통 재귀적으로 호출하는 것이 일반적.

 

4. 협력 방법

• 사용자는 TerminalExpression와 NonterminalExpression 인스턴스를 활용하여 전체 표현식을 위한 구문 트리를 생성해야한다.
• NonterminalExpression은 자신이 가지고 있는 표현식의 Interpret()을 사용하여 재귀적으로 해석할 수 있게끔 구현해야한다.
• 각 노드에 정의한 Interpret() 해석 연산은 해석자의 상태를 저장하거나 문맥 정보를 이용한다.

 

5. 결과

• 문법의 변경과 확장이 쉽다. 새로운 서브 클래스를 정의하거나 표현식을 수정하면 새로운 표현식을 정의할 수 있다.
• 문법의 구현이 용이하다. 추상 구문 트리의 노드의 클래스는 비슷한 모습을 보인다.
• 복잡한 문법은 관리하기 어렵다. 구조화가 쉽지 않은 문법은 동일한 해석 연산으로 정의하기 힘들다.
• 표현식을 해석하는 새로운 방법을 추가할 수 있다.

 

6. 구현

• 추상 구문 트리를 생성한다.
• Interpret() 연산을 정의한다.
• 플라이급 패턴을 적용하여 단말 기호를 공유한다.

 

예제 코드

 

주어진 식에 대한 부울 값을 판별(해석)하는 방법.

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

추상 구문 트리로 접근

- 표현 문법을 클래스로 나타내고 포함된 부울 식 표현을 트리로 나타낸다.

BooleanExp.h

부울 표현식을 위한 추상 클래스

class BooleanExp
{
public:
	BooleanExp();
	virtual ~BooleanExp();

	virtual bool Evaluate(Context&) = 0;
	virtual BooleanExp* Replace(const char*, BooleanExp&) = 0;
	virtual BooleanExp* Copy() const = 0;
};

모든 Interpret() 연산은 다음과 같다.

• Evaluate(Context&): 문맥에서 자신의 표현식에 대한 부울 값을 반환한다.
• Replace(const char*, BooleanExp&): 쿼리 이름에 대해 표현식에 있다면 주어진 부울 표현식으로 대체한 것을 반환한다.
• Copy(): 자신의 표현식을 복제한 것을 반환한다.

Context.h

문맥이란 모든 이름 변수에 대응하는 부울 값을 테이블과 같이 저장해놓는 자료 구조이다. LookUp 연산으로 이름 쿼리에 대해 테이블에서 대응하는 부울 값을 반환하거나 새로운 이름 변수-부울 값 쌍을 저장할 수 있다. 

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

 

VariableExp.h

VaraibleExp 클래스는 이름을 가지며 자신의 이름에 대한 부울 값이 있다.

 

- 표현 문법

 

"name" = true/false;

 

- VaraibleExp에 대하여

• VaraibleExp 인스턴스는 Constant 인스턴스처럼 전체 표현식 트리의 단말 노드에 해당한다.
• 자식이 없기 때문에 추가 호출 없이 부울 값을 바로 반환하는 기저 호출을 구현한다.
• Evaluate(Context&): 문맥에서 자신의 표현식에 대한 부울 값을 찾아 반환한다.
• Replace(const char*, BooleanExp&): 쿼리 이름에 대해 표현식에 있다면 주어진 식으로 대체한, 복제한 것을 반환하고 아니라면 자신을 복제하여 반환한다.

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:
	const char* _name;
};

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

bool VariableExp::Evaluate(Context& aContext)
{
	// 자신 이름 변수에 해당하는 bool 평가값을 반환
	return aContext.Lookup(_name);
}

BooleanExp* VariableExp::Replace(const char* name, BooleanExp& exp)
{
	// 자신의 이름일 경우 대체하고 아닐 경우 자신의 복사본
	return strcmp(name, _name) == 0 ? exp.Copy() : this->Copy();
}

BooleanExp* VariableExp::Copy() const
{
	// 자신의 복사본을 만듦
	return new VariableExp(_name);
}

 

Constant.h

이름이 없고 리터럴 상수를 위한 표현으로 부울 표현식을 상속하여 표현할 수 있다.

class Constant : public BooleanExp
{
public:
	Constant(bool);
	virtual ~Constant();

	virtual bool Evaluate(Context&);
	virtual BooleanExp* Replace(const char*, BooleanExp&) override;
	virtual BooleanExp* Copy() const;
private:
	bool _value;
};

Constant::Constant(bool value) :_value(value){}

bool Constant::Evaluate(Context& aContext) { return _value; }

BooleanExp* Constant::Replace(const char* name, BooleanExp& exp) { return this->Copy(); }

BooleanExp* Constant::Copy() const { return new Constant(_value); }

 

AndExp.h / OrExp.h / NotExp.h

각 AndExp, OrExp, NotExp 클래스는 단말 노드를 가지거나 또 다른 복합 부울 식을 포함할 수 있는데 연산 문법 정의에 따라 가질 수 있는 식의 갯수가 정해져 있다.

 

- 연산 표현과 관련된 클래스에 대하여

해석 연산을 재귀적으로 구현

• 생성자에서 자신이 가져야하는 부울식 표현을 매개변수로 받아 초기화 한다.
• 해석 연산에서 공통적으로 자신이 가지고 있는 부울식의 연산을 직접적으로 이용하는 재귀적 호출을 사용한다.
• Evaluate()는 해당 서브 클래스의 문법 표현을 해석하는 것이 반영되어 있다.

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

class NotExp : public BooleanExp
{
public:
	NotExp(BooleanExp*);
	virtual ~NotExp();

	virtual bool Evaluate(Context&);
	virtual BooleanExp* Replace(const char*, BooleanExp&);
	virtual BooleanExp* Copy() const;
private:
	BooleanExp* _operand;
};

NotExp::NotExp(BooleanExp* operand)
{
	_operand = operand;
}

bool NotExp::Evaluate(Context& aContext)
{
	return !_operand->Evaluate(aContext);
}

BooleanExp* NotExp::Replace(const char* name, BooleanExp& exp)
{
	return new NotExp(_operand->Replace(name, exp));
}

BooleanExp* NotExp::Copy() const
{
	return new NotExp(_operand->Copy());
}

 

- 주어진 식에 대해 사용자 코드로 구문 트리를 구성해보고 결과를 확인할 수 있다.

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

// (true and false) or (true and (not false)) = true
bool result = expression->Evaluate(context);

 

- y 변수에 대해 not z로 치환을 한다면 다음 식이 되는데 Replace() 연산을 통해 쉽게 표현 가능하다.

(true and (not z)) or ((not z) and (not x))

VariableExp* z = new VariableExp("Z");
NotExp not_z(z);

BooleanExp* replacement = expression->Replace("Y", not_z);

context.Assign(z, true);

result = replacement->Evaluate(context);