해석자(Interpreter)

의도

• 어떤 언어에 대해, 그 언어의 문법에 대한 표현을 정의하면서 표현을 사용하여 해당 언어로 기술된 문장을 해석하는 해석자를 함께 정의함.

 

언제 쓰는가 ?

• 정의할 언어의 문법이 간단함. 문법이 복잡하다면 문법을 정의하는 클래스 계통이 복잡해지고 관리할 수 없게 됨.
• 효율성은 별로 고려할 사항이 아님. 

 

구조

GoF의 디자인 패턴 중 P.327

• AbstractExpression : 추상 구문 트리에 속한 모든 노드에 해당하는 클래스들이 공통으로 가져야 할 Interpret() 연산을 추상 연산으로 정의
• TerminalExpression : 문법에 정의한 터미널 기호와 관련된 해석 방법을 구현함. 문장을 구성하는 모든 터미널 기호에 대해서 해당 클래스를 만들어야 함.
• NonterminalExpression : 문법의 오른편에 나타나는 모든 기호에 대해서 클래스를 정의해야 함.
• Context : 번역기에 대한 포괄정인 정보를 포함
• Client : 언어로 정의한 특정 문장을 나타내는 추상 구문 트리. 이 추상 구문 트리는 NonterminalExpression과 TerminalExpression 클래스의 인스턴스로 구성됨.

 

협력 방법

• 사용자는 NonterminalExpression과 TerminalExpression 인스턴스들로 해당 문장에 대한 추상 구문 트리를 만듬. 그리고 사용자는 Interpret() 연산을 호출하는데, 이때 해석에 필요한 문맥 정보를 초기화
• 각 NonterminalExpression 노드는 또 다른 서브 표현식에 대한 Interpret()를 이용하여 자신의 Interpret() 연산을 정의함. Interpret() 연산은 재귀적으로 Interpret() 연산을 이용하여 기본적 처리를 담당함.
• 각 노드에 정의한 Interpret() 연산은 해석자의 상태를 저장하거나 그것을 알기 위해서 문맥 정보를 이용함.

 

결과

1. 문법의 변경과 확장이 쉬움
2. 문법의 구현이 용이
3. 복잡한 문법은 관리하기 어려움
4. 표현식을 해석하는 새로운 방법을 추가할 수 있음

 

구현

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

 

예제 코드

• 개인적으로 해석자 패턴을 사용할 일이 있을까 싶긴 합니다.
• 책에 나온 거의 그대로 따라해봤고, 표현식에 해당하는 문자열을 파싱해서 결과로 보여줄 수 있으면 더 좋았을 거라 생각합니다.

#include "Interpreter1.h"
#include <iostream>

int main()
{
	BooleanExp* expression1;
	BooleanExp* expression2;
	Context<bool> context;

	VariableExp* x = new VariableExp("X");
	VariableExp* y = new VariableExp("Y");

	context.Assign(x, true);
	context.Assign(y, false);

	expression1 = new OrExp(
		new AndExp(x, y),
		new AndExp(x, x)
	);

	expression2 = new OrExp(
		new AndExp(x, y),
		new AndExp(x, y)
	);

	bool result1 = expression1->Evaluate(context);
	bool result2 = expression2->Evaluate(context);

	std::cout << result1 << std::endl;
	std::cout << result2 << std::endl;

	return 0;
}

• 일단 결과만 보자면 expression1 ( (x && y) || (x && x) ) 의 경우 true가 나왔고 expression1 ( (x && y) || (x && y) ) 의 경우 false가 나왔습니다.
  • ( (x && y) || (x && x) ) : ( (true && false) || (true && true) ) 이므로 true입니다.
  • ( (x && y) || (x && y) ) : ( (true && false) || (true && false) ) 이므로 false입니다.
• 해석자 패턴을 사용해 ValiableExp* 타입인 x 와 y에 각각 true 혹은 false에 해당하는 값을 메길 수 있었고 x와 y를 연산으로서 포함하는 AndExp, OrExp를 Evaluate 함으로서 true 혹은 false의 값을 리턴 받을 수 있었습니다.

//Interpreter1.h

#pragma once
#include <string>
#include <map>

class VariableExp;

template<typename T>
class Context
{
public:
	bool Lookup(std::string str);
	void Assign(VariableExp* variable_exp, T value);

private:
	std::map<std::string, T> expression_map;
};

class BooleanExp
{
public:
	virtual ~BooleanExp();

	virtual bool Evaluate(Context<bool>& context) = 0;
};

class VariableExp : public BooleanExp
{
public:
	VariableExp(std::string expression);

	virtual bool Evaluate(Context<bool>& context) override;
	std::string GetExpression() { return expression; }

private:
	std::string expression;
};

class AndExp : public BooleanExp
{
public:
	AndExp(BooleanExp* exp1, BooleanExp* exp2);

	virtual bool Evaluate(Context<bool>& context) override;

private:
	BooleanExp* expression1;
	BooleanExp* expression2;
};

class OrExp : public BooleanExp
{
public:
	OrExp(BooleanExp* exp1, BooleanExp* exp2);

	virtual bool Evaluate(Context<bool>& context) override;

private:
	BooleanExp* expression1;
	BooleanExp* expression2;
};

template<typename T>
inline bool Context<T>::Lookup(std::string str)
{
	return expression_map[str];
}

template<typename T>
inline void Context<T>::Assign(VariableExp* variable_exp, T value)
{
	std::string expression = variable_exp->GetExpression();
	expression_map[expression] = value;
}

• 실제 문자열에 해당하는 특정 값 T (혹은 boolean 값) 에 대해 Context에서 관리하게 됩니다. Context를 통해 해당 문자열이 true 인지 false인지를 알 수 있게 됩니다.
  • Context의 Assign 메서드를 통해 문자열을 map 컨테이너에 T value에 해당하는 값으로 저장할 수 있고
  • Context의 Lookup 메서드를 통해 map 컨테이너에서 문자열에 해당하는 T 값을 리턴합니다.
    • 이 Lookup 메서드는 결국 ValiableExp의 Evaluate 메서드에서 최종적으로 사용합니다.
• Boolean에 대한 표현식을 작성할 것이기 때문에 BooleanExp라는 클래스가 추상클래스로 최상위 클래스를 담당하고, 그 밑으로 실제 변수에 해당하는 VariableExp이 있고, 좌측과 우측의 값을 저장해두는 And, Or 연산을 정의했습니다.

//Interpreter1.cpp

#include "Interpreter1.h"

BooleanExp::~BooleanExp()
{
}

VariableExp::VariableExp(std::string expression)
{
	this->expression = expression;
}

bool VariableExp::Evaluate(Context<bool>& context)
{
	return context.Lookup(expression);
}

AndExp::AndExp(BooleanExp* exp1, BooleanExp* exp2)
{
	expression1 = exp1;
	expression2 = exp2;
}

bool AndExp::Evaluate(Context<bool>& context)
{
	return expression1->Evaluate(context) && expression2->Evaluate(context);
}

OrExp::OrExp(BooleanExp* exp1, BooleanExp* exp2)
{
	expression1 = exp1;
	expression2 = exp2;
}

bool OrExp::Evaluate(Context<bool>& context)
{
	return expression1->Evaluate(context) || expression2->Evaluate(context);
}

• 결국 or 연산과 and 연산이 가능한 이유는 &&과 ||를 통해 가능한 것이고, 최종적으로 VariableExp가 어떤 값을 가지는 지를 Context에서 찾아와 가능하게 해줍니다.