19장 간단한 문법에 기반한 검증 및 작업 처리 문제(Interpreter 패턴)

컴퓨터 프로그램에게 완벽히 의미를 전달하기 위해서는 같은 표현이 서로 다른 의미로 해석되는 경우가 없어야 할 것이다. 또한 표현하고자 하는 모든 표현이 가능해야 하며 표현에 사용되는 기본 단어들도 명확하고 유연하게 정의되어야 할 것이다. 이 같은 조건들을 만족시키기 위해서는 우리가 일반적으로 사용하는 자연어와는 달리 철저히 정형화된 언어가 필요한데 이런 특성을 가진 언어를 형식 언어(Formal Language)라고 부른다. 형식 언어는 모든 표현들을 정형화시키기 위해 특정한 문법에 기초하게 되는데 이를 형식 문법(Formal Grammar)라고 한다.
컴퓨터 프로그램에게 완벽한 의미를 전달하기 위해서는 형식 문법에 기초한 형식 언어를 통해 자료를 표현해야 하는 것이다. 이같은 형식 문법과 형식 언어로 만들어지는 대표적인 자료 중 하나가 컴파일러로 입력되는 프로그램이다.
컴퓨터 프로그램을 작성하다 보면 많은 경우 정형화된 문법에 의한 자료 처리를 수행해야 할 경우가 많다. 이들 중에는 프로그래밍 언어 문법과 같이 복잡한 문법에 따라 자료를 처리해야 하는 경우가 있는가 하면, 문법 규칙이 몇 개 안되는 간단한 경우도 존재한다. 이 장에서는 이들 중 간단한 문법에 따라 작업을 수행해야 할 경우 어떤 식으로 설계를 하면 입력되는 자료가 문법 규칙을 만족하는 지도 검증하면서 문법에 따라 수행해야 할 작업도 쉽게 처리할 수 있는지에 대해 알아본다.
• 문제 사례 설명
문서 파일에서 특정 문자열 패턴이 존재하는지를 검사해주는 프로그램을 작성한다고 가정해보자. 이때 찾고자 하는 문자열 패턴은 다음과 같은 문법에 따라 임의로 입력이 주어질 수 있다.





위 문법에서 ::= 기호의 왼쪽에 있는 것은 기호 오른쪽에 있는 것으로 정의된다는 것을 의미한다. 또한 | 기호는 좌측이나 우측의 내용으로 정의될 수 있음을 가리키며, * 기호는 앞에 { }로 묶인 부분들이 0번 이상 반복될 수 있음을 가리킨다. 작은 따옴표 내에 표시되는 것은 실제 문자열 패턴 입력 시에 나타날 수 있는 기본 요소들을 가리
킨다.
이 같은 문법에 따라 문서 파일에서 검색할 문자열 패턴이 주어졌을 때 프로그램에서는 크게 두 가지 작업을 해야 할 것이다. 하나는 입력된 문자열 패턴이 위에서 제시한 문법을 준수하는가를 검증하는 것이고, 다른 하나는 문서 파일에서 입력된 문자열 패턴을 실제로 검색해보는 것이다.
• 다양한 접근 방법 및 INTERPRETER 패턴
주어진 문제는 간단하다. 앞서 제시한 문법에 따라 문자열 패턴을 입력하면, 문서 파일에서 해당 문자열 패턴이 존재하는지를 검사해주는 프로그램을 설계하는 것이다. 이때 프로그램이 해야 하는 작업은 입력된 문자열 패턴이 정해진 문법을 따르는 것인지를 검사하는 것과 문서 파일에서 원하는 문자열 패턴이 존재하는지를 검사하는 것이다.
• 기본적인 방법: 각각 독립된 클래스를 통한 구현 방식
우선 프로그램이 수행해야 할 두 개의 작업을 각각 별대로 독립된 클래스를 이용해서 처리하는 것이다. 즉 입력된 문자열 패턴이 정해진 문법을 따르는지를 검사하기 위한 Parser 클래스와 문서 파일에서 입력된 문자열 패턴이 실제로 존재하는지를 검사하는 PatternChecker 클래스를 별개로 정의하는 것이다.
이때 Parser 클래스 객체는 입력된 문자열 패턴이 정해진 문법을 만족하는지를 알아보기 위해 LL 파싱이나 SLR, CLR, LALR 등의 다양한 파싱 알고리즘을 적용할 수 있을 것이다. 이런 과정을 통해 Parser 클래스 객체는 입력된 문자열 패턴을 구문 트리 형태로 생성하게 될 것이다. 예를 들어 "(best & love) | (long & sweet)"와 같은 문자열 패턴이 입력된 경우에는 [그림 19-1]과 같은 구문 트리가 생성될 것이다. 만약 Parser 클래스 객체가 이 같은 구문 트리 생성에 실패한다면, 입력된 문자열 패턴은 정해진 문법을 따르지 않은 것이므로 오류 처리하면 될 것이다.





PatternChecker 클래스 객체는 Parser 클래스 객체에 의해 생성된 구문 트리의 각 노드를 방문하는 형태를 통하여 문서 파일에서 입력된 문자열 패턴이 존재하는지를 검사할 수 있을 것이다.
• 패턴 활용 방식: INTERPRETER 패턴
Parser와 PatternChecker 클래스를 사용하는 방법은 노력대비 효용 측면에서 비경제적인 문제가 있다.
무엇보다도 필요로 하는 자료구조가 너무 많다는 것이 가장 큰 원인일 것이다. 앞서 제시한 방법의 경우 Parser, PatternChecker 클래스에서부터 구문 트리, 파싱 테이블 및 구문 트리의 각 노드를 방문하기 위한 자료구조가 각각 필요할 것이다. 이처럼 프로그램에서 다루어야 하는 자료구조가 많아지면 자연스럽게 프로그램이 복잡해지고, 구현이 힘들어질 것이다. 따라서 주어진 문제를 경제적으로 해결하기 위해 사용하는 자료구조의 개수를 최소화해야 할 것이다.
한 가지 가능한 방법은 핵심 자료구조를 제외하고는 복잡하나 자료구조를 사용하지 않고 필요한 기능을 구현하게 만드는 것이다. 이같은 접근이 가능한 이유는 복잡한 자료구조를 사용하지 않더라도 주어진 문법이 간단해서 필요한 기능의 구현이 가능하기 때문이다.
예를 들어 Parser 클래스 객체가 수행하던 파싱 작업의 경우 일반적으로 파싱 테이블을 이용하지만, 문제에서처럼 문법이 간단하다면 굳이 파싱 테이블을 사용하지 않고 '&'와 '|', '(', ')' 기호를 구분자로 간단히 파싱할 수 있는 함수만 하나 정의해서 사용하면 충분할 것이다.
이런 방법으로 Parser 및 PatternChecker 클래스를 사용하는 형태의 해결책을 분석해 보면 결국 구문 트리를 위한 자료구조만 있으면 별다른 자료구조를 정의하지 않고도 주어진 문제를 해결할 수 있음을 알 수 있다. 왜냐하면 수행해야 할 두 가지 작업인 입력된 문자열 패턴의 문법 검사와 문서 파일에서 입력된 문자열 패턴의 존재 여부를 검사하는 것이 모두 구문 트리를 이용함으로써 수행 가능하기 때문이다. 따라서 구문 트리를 위한 자료구조와 원하는 작업 수행을 위한 함수만 잘 정의한다면 주어진 문제를 경제적으로 해결할 수 있는 적절한 방법이 될 것이다.
먼저 구문 트리를 위한 자료구조는 주어진 문법에 따라 모든 문자열 패턴에 대해 구문 트릴르 생성해줄 수 있어야 한다. 또한 이 과정에서 문법을 만족하지 않는 문자열 패턴은 구문 트리를 생성하지 못하고 오류가 발생하게 만들어 주어야 한다.
그렇다면 구문 트리를 위한 자료구조를 정의할 때 어떻게 문제에서 주어진 문법 정보를 반영할 수 있겠는가?
모든 구문 트리는 문법에 의해 생성된다. 따라서 각각의 구문 트리는 문법에 의해 만들어진 하나의 객체라고 할 수 있다. 이런 생각을 바탕으로 한다면 구문 트리를 생성하기 위한 클래스를 정의할 것이 아니라 문법 정보 자체를 클래스로 정의하고 이를 이용해서 구문 트리를 생성하도록 만드는 것이 가능할 것이다.
문법은 크게 Terminal 심볼과 Nonterminal 심볼로 구분된다. 이때 Terminal 심볼은 모두 Nonterminal 심볼로부터 유도되며 고정된 값을 가진다. 또한 Nonterminal 심볼 중에는 시작 심볼이 존재해서 다른 심볼들을 유도하기 위한 출발점 역할을 한다.
그렇다면 Terminal 심볼과 Nonterminal 심볼에 대해 어떻게 클래스를 정의하는 것이 좋으며 클래스들간의 관계는 어떻게 설정할 수 있을까?
Terminal 심볼은 Nonterminal 심볼로부터 유도되며 고정된 값을 가진다고 하였다. 이런 사실은 Terminal 심볼이 Nonterminal 심볼로부터 유도될 수 있는 하나의 Instance라는 것을 의미한다. 이를 클래스와 객체로 표현한다면 Nonterminal 심볼은 클래스고, Terminal 심볼은 Nonterminal 심볼 클래스로부터 생성되는 객체라고 할 수 있을 것이다. 따라서 문법 정보를 클래스로 표현하고자 할 때 Nonterminal  심볼 클래스로 정의하면 충분하다고 말할 수 있다.
각각의 Nonterminal 심볼들은 시작 심볼로부터 유도 가능하다고 하였다. 이를 클래스로 바꾸어 생각하면 모든 Nonterminal 심볼 클래스들이 시작 심볼에 해당하는 클래스의 일종이라고 볼 수 있는 것이다. 이런 사실을 감안한다면 모든 Nonterminal 심볼 클래스들은 시작 심볼 클래스로부터 상속을 받는 관계로 정의될 수 있을 것이다.
이상과 같은 아이디어에 의해 주어진 문법을 클래스로 정의한다면 [그림 19-2]와 같다.
구문 트리는 문법에 의해 만들어지는 하나의 객체라고 언급했다. 그런데 문법은 [그림 19-2]의 클래스 형태로 이미 표현되었다. 따라서 문법의 객체로 인식될 수 있는 구문 트리는 [그림 19-2]의 클래스들로부터 만들어지는 객체로 표현될 수 있을 것이다.





[그림 19-1]의 입력 문자열 패턴에 대해 [그림 19-2]에서 정의한 클래스를 이용해서 구문 트리를 생성하면 [그림 19-3]과 같은 객체 구조로 표현될 수 있을 것이다.





[그림 19-3]과 같이 구문 트리가 생성되었을 때 문서 파일 내에 구문 트리가 표현하는 것과 동일한 문자열 패턴이 존재하는지 여부는 어떻게 판별할 수 있을까?
일반적으로 이 작업은 구문 트리를 구성하는 각 노드들을 방문하면서 문서 파일 내에 구문 트리에서 원하는 문자열이 존재하는지를 검사하는 형태로 이루어진다고 하였다. 그리고 이를 위해서는 별도의 트리 방문 알고리즘을 작성해야 했었다. 그런데 [그림 19-3]의 객체 구조를 이용하면 이 같은 트리 방문 작업이 단순화될 수 있다. 왜냐하면 트리를 구성하는 각 노드가 모두 객체고 이 객체 구조를 따라가면 곧바로 트리 방문이 이루어질 수 있기 때문이다.
• 샘플 코드
[소스 19-1] 간단한 문법에 대해 Interpreter 패턴을 적용

#include <iostream> #include <fstream> #include <string> #include <strstream> using namespace std;   static const int NA_POS = -1;   class RegularExp { public: virtual bool Match(string context) = 0; };   class LiteralExp : public RegularExp { public: LiteralExp(const char* pStr) : literal_(pStr) {} LiteralExp(const string str) : literal_(str) {}   bool Match(string context) { string str; ifstream ifs(context.data()); while (!ifs.eof()) { ifs >> str; if (literal_ == str) return true; } return false; } private: string literal_; };   class OrExp : public RegularExp { public: OrExp(RegularExp* pExp1, RegularExp* pExp2) : pOrExp1_(pExp1), pOrExp2_(pExp2) { }   bool Match(string context) { if (pOrExp1_->Match(context)) return true; else return pOrExp2_->Match(context); } private: RegularExp* pOrExp1_; RegularExp* pOrExp2_; };   class AndExp : public RegularExp { public: AndExp(RegularExp* pExp1, RegularExp* pExp2) : pAndExp1_(pExp1), pAndExp2_(pExp2) {} bool Match(string context) { return pAndExp1_->Match(context) && pAndExp2_->Match(context); } private: RegularExp* pAndExp1_; RegularExp* pAndExp2_; };   RegularExp* CreateRegularExp(string searchStr) { int len = searchStr.length(); if (len == 0) return NULL; else cout << "===>" << searchStr << endl;   int pos = searchStr.find_first_of("(&|"); if (searchStr[pos] == '(') { int endParentPos = 0; int parentCnt = 1;   for (int i = pos + 1; i < len; i++) { if (searchStr[i] == '(') parentCnt++; else if (searchStr[i] == ')') parentCnt--; else { }   if (parentCnt == 0) { int nextOpPos = searchStr.find_first_of("&|", i + 1); if (nextOpPos != NA_POS) { if (searchStr[nextOpPos] == '&') return new AndExp(CreateRegularExp(searchStr.substr(pos + 1, i - pos - 1)), CreateRegularExp(searchStr.substr(nextOpPos + 1, len - nextOpPos - 1))); else return new OrExp(CreateRegularExp(searchStr.substr(pos + 1, i - pos - 1)), CreateRegularExp(searchStr.substr(nextOpPos + 1, len - nextOpPos - 1))); } else return CreateRegularExp(searchStr.substr(pos + 1, i - pos - 1)); } } return NULL; } else if (searchStr[pos] == '&') { if (pos >= len - 1) return NULL;   return new AndExp(CreateRegularExp(searchStr.substr(0, pos)), CreateRegularExp(searchStr.substr(pos + 1, len - pos - 1))); } else if (searchStr[pos] == '|') { if (pos >= len - 1) return NULL;   return new OrExp(CreateRegularExp(searchStr.substr(0, pos)), CreateRegularExp(searchStr.substr(pos + 1, len - pos - 1))); } else { // 앞뒤 White Sapce 제거 string literal; strstream strm; strm << searchStr; strm >> literal;   if (literal.empty()) return NULL;   return new LiteralExp(literal); } }   void main() { string str; getline(cin, str);   RegularExp* pRegExp = CreateRegularExp(str); if (pRegExp == NULL) { cout << "Search Pattern Error" << endl; exit(0); }   if (pRegExp->Match("data.txt")) cout << "Found the search string" << endl; else cout << "Not Exist the search string" << endl; }

• 구현 관련 사항
먼저 Interpreter 패턴은 클래스 자체가 문법을 표현하고 있지만 자체적으로 파싱을 수행하지 않는다. 따라서 Interpreter 패턴을 사용하고자 할 경우 Client 자체적으로 파싱을 수행해야 한다.
다음으로 Interpreter 패턴을 구성하는 모든 클래스가 Match() 와 같은 멤버 함수를 구현하는 것은 종종 불편할 수 있다. 특히 정의되어야 할 멤버 함수가 많거나 계속 늘어날 가능성이 있을 경우에는 상당히 번거로울 뿐 아니라 기존 소스코드를 수정해야 하는 문제를 야기시킬 수 있다.
이런 문제를 해결하기 위한 한가지 방법으로는 Visitor 패턴을 활용하는 것이다. Visitor 패턴은 수행할 작업의 종류마다 클래스를 생성하고 정의된 클래스의 객체로 하여금 구문 트리의 각 노드를 순회하도록 함으로써 원하는 작업이 이루어지게 해준다.
이 밖에도 문법이 간단하더라도 사용하는 Terminal 심볼이 많을 경우 각 구문 트리마다 동일한 Terminal 심볼에 대해 일일이 객체를 생성하는 것이 메모리 공간의 낭비를 초래할 뿐만 아니라 불편할 수 있다. 이같은 문제를 회피하기 위한 방법으로는 Flyweight 패턴을 이용해서 동일한 Terminal 심볼들간에는 객체를 공유하게 만드는 것이 유용할 수 있다.
• INTERPRETER 패턴 정리

Interpreter 패턴이 유용한 경우
• 복잡한 문법보다 간단한 문법이 주어졌을 때 적용하는 것이 좋다. 복잡한 문법의 경우 문법에 맞추어 많은 클래스들을 정의해야 하고 그들간의 상속 관계도 복잡하므로 Interpreter패턴을 적용하는 것이 더 복잡해질 수 있다.
• Client가 직접 파싱을 수행해야 하고, 구문 트리를 만들기 위해 객체도 생성해야 하므로 실행 속도나 효율이 떨어질 수 있다. 따라서 속도나 효율이 중요하지 않을 경우에 Interpreter 패턴을 사용하는 것이 좋다.
Interpreter패턴의 장단점
• 문법을 변경시키거나 확장시키는 것이 쉽다.
• 클래스들의 구현 형태가 서로 비슷하므로 클래스 구현이 쉽다.
• 새로운 작업을 추가하려면 각 클래스마다 새로운 멤버 함수를 정의해야 한다.
• Composite 패턴과 대부분의 경우 유사한 클래스 구조를 사용한다. 단지 차이가 나는 것은 Interpreter 패턴은 주어진 문법을 기준으로 클래스를 정의한 것이고 Composite 패턴은 클래스간 구성 관계에 따라 클래스 구조가 정의된다는 사실이다.
• 20장에서 언급할 Iterator 패턴은 Interpreter 패턴에 의해 구성된 구문 트리 상의 각 객체들을 순회하고자 할 경우 유용하게 사용할 수 있다.