#15. [디자인 패턴-행위 패턴] Interpreter
Interpreter는 비교적 단순하게 설계된 임의의 언어를 해석하는 간단한 방법을 제공합니다. 파서를 통해 가상의 트리를 만들고 이를 이용하여 구문을 해석합니다.
설명
어떠한 기능을 구현하는데 있어서 좀더 자유도를 높이기 위해 임의의 언어를 설계하여 제공할 수 있습니다.
예를들어 도형의 너비와 높이를 곱한 값이 필요하다고 가정해 봅시다. 다음과 같이 계산할 수 있는데요,
1
2
3
Rectangle rectangle{l, t, w, h};
int val = Calc(rectangle.GetWidth() + rectangle.GetHeight());
다음처럼 사용자가 입력한 문자열로부터 계산하는 것을 지원한다면, 좀더 자유도가 높아집니다.
1
2
3
4
Rectangle rectangle{l, t, w, h};
std::string userInputString = "w * h";
int val = Calc(rectangle.GetWidth(), rectangle.GetHeight(), userInputString);
“w * h”를 계산하려면 w, *, h를 토큰으로 분리하고, 변수인 w와 h 대신 rectangle.GetWidth()와 rectangle.GetHeight()를 사용해야 합니다. 하지만, 문자열을 파싱하고, 이를 해석하는 것은 상당히 복잡한 일입니다. 특히 문법이 복잡해 질수록 난이도와 규모는 커지죠.
하지만, 문법이 비교적 단순하다면, Interpreter 패턴을 이용하여 간단하게 인터프리터를 구현할 수 있습니다.
다음 그림은 Interpreter의 일반적인 구조입니다.
AbstractExpression은 interpret()함수를 통해 실행 결과를 리턴합니다. 이때 각 AbstractExpression은 트리처럼 배치되어 최상위 AbstractExpression만 실행하면, 하위의 AbstractExpression이 모두 실행되는 구조입니다.
TerminalExpression은 현재 표현식까지 해석하는 것이고, NonterminalExpression는 다음 표현식까지 해석하는 것입니다.
Context는 각 표현식을 해석할때 사용되는 포괄적인 정보입니다. 예를 들어 w * h와 같이 너비와 높이에 해당하는 변수를 사용한다면, 표현식에서 너비와 높이에 대한 실제 값으로 계산할 수 있도록 정보를 제공해야 합니다.
예를 들어 w * h * 4 / 2는 각 토큰으로 분리한 뒤, 다음의 트리처럼 구성하여 처리해야 합니다.
상기 최상위 트리의 AbstractExpression을 실행하면, 하위의 AbstractExpression이 차례로 실행됩니다.
| 항목 | 내용 |
|---|---|
Context |
인터프리터에 대한 포괄적인 정보를 제공합니다. |
AbstractExpression |
각 토큰이 의미하는 바를 실행합니다. |
TerminalExpression |
현 표현식에서 연산이 종결됩니다. 즉, 변수, 상수등 단독으로 연산할 수 있거나, 왼쪽에 있는 AbstractExpression을 이용합니다. |
NonterminalExpression |
현 표현식에서 연산이 종결되지 않고 다음 표현식을 사용합니다. 예를 들어 *, /와 같이 오른편의 AbstractExpression을 이용합니다. |
Client |
최상위 AbstractExpression을 실행합니다. |
특징
비교적 문법이 단순한 경우에 사용 가능합니다. 문법이 복잡하다면 별도로 설계하여 인터프리터를 만드시기 바랍니다.
예제
다음은 내장 변수인 w와 h를 제공하고 * 과 /를 지원하는 인터프리터입니다. 각 토큰은 공백 문자로 구분합니다. 런타임에 선택한 사각형의 너비와 높이로부터 사용자가 입력한 임의의 수식을 계산(예를들어 w * h * 4 / 2는 너비와 높이를 곱하고, 4를 곱한뒤, 2로 나눕니다.)할 수 있습니다.(언어의 문법을 어떻게 설계하느냐에 따라 Interpreter의 구현은 달라질 수 있습니다.)
- #1 :
Context에서는w,h에 사용되는 포괄적인 정보를 제공합니다. - #2 :
Expression의 기본 인터페이스를 제공합니다.Interpret()시 연산 결과값을 리턴해야 합니다. - #3 :
TerminalExpression입니다.Context로부터w,h값을 읽어와 리턴하거나 상수값을 리턴합니다. - #4 :
NonterminalExpression입니다.*,/결과값을 리턴합니다. - #5 : 전달한 문자열을
Parse()하여Expression을 트리 형태로 구성하고, 최상위Expression을 구한뒤, 이의Interpret()를 호출하여 결과값을 구합니다. - #6 : 런타임에 임의의 수식을 입력받아
rectangle개체의 너비와 높이로부터 값을 구할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
// ----
// #1. w, h에 사용되는 포괄적인 정보를 제공합니다.
// ----
class Context {
int m_Width;
int m_Height;
std::string m_Exp;
public:
Context(int w, int h, const char* exp) : m_Width{w}, m_Height{h}, m_Exp{exp} {}
~Context() = default;
private:
Context(const Context&) = delete;
Context(Context&&) = delete;
Context& operator =(const Context&) = delete;
Context& operator =(Context&&) = delete;
public:
int GetWidth() const {return m_Width;}
int GetHeight() const {return m_Height;}
const std::string& GetExp() const {return m_Exp;}
};
// ----
// #2. 기본 인터페이스입니다. Interpret()시 연산 결과값을 리턴해야 합니다.
// ----
class Expression {
protected:
Expression() = default; // 다형 소멸을 제공하는 추상 클래스. 상속해서만 사용하도록 protected
public:
virtual ~Expression() = default; // 다형 소멸 하도록 public virtual
private:
Expression(const Expression&) = delete;
Expression(Expression&&) = delete;
Expression& operator =(const Expression&) = delete;
Expression& operator =(Expression&&) = delete;
public:
virtual int Interpret(const Context& context) const = 0; // #2
};
// ----
// #3. TerminalExpression입니다. Context로부터 w, h 값을 읽어와 리턴하거나, 상수값을 리턴합니다.
// ----
class WidthExpression : public Expression {
public:
WidthExpression() = default;
virtual int Interpret(const Context& context) const override{return context.GetWidth();}
};
class HeightExpression : public Expression {
public:
HeightExpression() = default;
virtual int Interpret(const Context& context) const override {return context.GetHeight();}
};
class ConstantExpression : public Expression {
int m_Val;
public:
explicit ConstantExpression(int val) : m_Val{val} {}
virtual int Interpret(const Context& context) const override {return m_Val;}
};
// ----
// #4. NonterminalExpression입니다. *, / 결과값을 리턴합니다.
// ----
class MulExpression : public Expression {
std::unique_ptr<Expression> m_Left;
std::unique_ptr<Expression> m_Right;
public:
MulExpression(std::unique_ptr<Expression> left, std::unique_ptr<Expression> right) :
m_Left{std::move(left)},
m_Right(std::move(right)) {
assert(m_Left && m_Right);
}
virtual int Interpret(const Context& context) const override {
assert(m_Left && m_Right);
return m_Left->Interpret(context) * m_Right->Interpret(context);
}
};
class DivExpression : public Expression {
std::unique_ptr<Expression> m_Left;
std::unique_ptr<Expression> m_Right;
public:
DivExpression(std::unique_ptr<Expression> left, std::unique_ptr<Expression> right) :
m_Left{std::move(left)},
m_Right(std::move(right)) {
assert(m_Left && m_Right);
}
virtual int Interpret(const Context& context) const override {
assert(m_Left && m_Right);
return m_Left->Interpret(context) / m_Right->Interpret(context);
}
};
// ----
// #5. 전달한 문자열을 Parse()하여 Expression을 트리 형태로 구성하고, 최상위 Expression을 구한뒤, 이의 Interpret()를 호출하여 결과값을 구합니다.
// ----
class Interpreter {
const Context& m_Context;
public:
explicit Interpreter(const Context& context) : m_Context{context} {}
~Interpreter() = default;
private:
Interpreter(const Interpreter&) = delete;
Interpreter(Interpreter&&) = delete;
Interpreter& operator =(const Interpreter&) = delete;
Interpreter& operator =(Interpreter&&) = delete;
public:
// #5. context를 파싱하고 실행 결과값을 리턴합니다.
int Run() const {
return Parse()->Interpret(m_Context);
}
private:
// ----
// w, h, 정수, *, / 가 공백 문자로 구분된 식을 계산합니다.
// 예를 들어 "w * h * 4 / 2" 와 같이 식을 작성할 수 있습니다.
// #5. context를 파싱하여 가상의 트리를 만들어 최상위 Expression을 리턴합니다.
// ----
std::unique_ptr<Expression> Parse() const {
std::vector<std::string> tokens{CreateToken(m_Context.GetExp(), " ")}; // 공백 문자로 token화 합니다.
std::stack<std::unique_ptr<Expression>> stack; // 수식을 차례대로 쌓아 가장 마지막 Expression이 트리의 root가 되게 합니다.
for (int i{0}; i < tokens.size(); ++i) {
if (IsVariable(tokens[i])) { // w, h
stack.push(CreateTerminalExpression(tokens[i]));
}
else if (IsConstant(tokens[i])) { // 상수
stack.push(CreateTerminalExpression(tokens[i]));
}
else if (IsMul(tokens[i])) { // *
std::unique_ptr<Expression> left{stack.top().release()};
stack.pop();
stack.push(std::unique_ptr<Expression>{new MulExpression{std::move(left), CreateTerminalExpression(tokens[++i])}}); // 다음 토큰을 사용합니다.
}
else if (IsDiv(tokens[i])) { // /
std::unique_ptr<Expression> left{stack.top().release()};
stack.pop();
stack.push(std::unique_ptr<Expression>{new DivExpression{std::move(left), CreateTerminalExpression(tokens[++i])}}); // 다음 토큰을 사용합니다.
}
else {
throw std::invalid_argument{"Invalid token. Need w, h, Integer, *, /."};
}
}
return std::unique_ptr<Expression>{stack.top().release()}; // 가장 마지막에 추가된 Expression을 리턴합니다.
}
static bool IsVariable(const std::string& str) {
return str == "w" || str == "h" ? true : false;
}
static bool IsConstant(const std::string& str) {
for (auto ch : str) {
if (!std::isdigit(ch)) { // 0123456789로 구성되었는지 확인합니다.
return false;
}
}
return true;
}
static bool IsMul(const std::string& str) {
return str == "*" ? true : false;
}
static bool IsDiv(const std::string & str) {
return str == "/" ? true : false;
}
// w, h, 정수를 Expression으로 만듭니다. token이 유효하지 않으면 예외를 발생합니다.
static std::unique_ptr<Expression> CreateTerminalExpression(const std::string& token) {
assert(IsVariable(token) || IsConstant(token));
if (IsVariable(token)) { // w, h
if (token == "w") {
return std::unique_ptr<Expression>{new WidthExpression{}};
}
else if (token == "h") {
return std::unique_ptr<Expression>{new HeightExpression{}};
}
else {
throw std::invalid_argument{"Invalid token. Need w, h."};
}
}
else if (IsConstant(token)) {
return std::unique_ptr<Expression>{new ConstantExpression{std::atoi(token.c_str())}};
}
else {
throw std::invalid_argument{"Invalid token. Need w, h, Integer."};
}
}
// #5. str을 delimeter로 구분하여 리턴합니다.
static std::vector<std::string> CreateToken(const std::string& str, const char* delimeter) {
assert(delimeter);
std::vector<std::string> result;
size_t pos{0};
size_t findPos{0};
while((findPos = str.find(delimeter, pos)) != std::string::npos) {
result.push_back(str.substr(pos, findPos - pos));
pos = ++findPos; // 다음 위치에서부터 찾습니다.
}
// 마지막이 delimeter가 아닌 경우 문자열 끝까지 token으로 만듭니다.
if (pos < str.length()) {
result.push_back(str.substr(pos, str.length() - pos));
}
return result;
}
};
class Rectangle {
int m_Left;
int m_Top;
int m_Width;
int m_Height;
public:
Rectangle(int l, int t, int w, int h) : m_Left{l}, m_Top{t}, m_Width{w}, m_Height{h} {}
int GetWidth() const {return m_Width;}
int GetHeight() const {return m_Height;}
};
// ----
// 테스트 코드
// ----
Rectangle rectangle{0, 0, 10, 20};
// #6. 런타임에 임의의 수식을 입력받아 rectangle 개체의 너비와 높이로부터 값을 구할 수 있습니다.
Context context{
rectangle.GetWidth(),
rectangle.GetHeight(),
"w * h * 4 / 2" // 공백 문자로 구분하며, w, h, 정수, * / 을 지원합니다.
};
Interpreter interpreter{context};
EXPECT_TRUE(interpreter.Run() == rectangle.GetWidth() * rectangle.GetHeight() * 4 / 2);
댓글남기기