C++ 인터프리터 패턴

프로그램을 작성하다 보면 정형화된 문법에 의한 자료 처리를 수행해야 하는 경우가 있는데 간단한 문법에 따라 작업을 할 경우 어떤 설계로 프로그램을 짜면 입력되는 자료가 문법 규칙을 만족하는지 아닌지를 판단할 수 있는지를 소개합니다.

 

특정 문자열 패턴이 존재하는 지 검사해주는 프로그램을 짤 때 입력된 문자열 패턴이 문법을 준수하고 있는지 문서 파일에서 입력된 문자 패턴이 실제로 있는지를 검색해야 합니다.

RegularExp ::= LiteralExp | AndExp | OrExp | '(' RegularExp')'
AndExp ::= RegularExp '&' RegularExp
OrExp ::= RegularExp '|' RegularExp
LiteralExp ::= 'A' | 'a' ... { 'A' | 'a' ... }*

위와 같은 문법에 따라 만약 "(test & game) | (test & team)"와 같은 문자열 패턴을 검색하면 우선 패턴이 정한 조건을 만족하는지 체크하고 만족한다면 저 패턴에 맞는 문자열이 존재하는지를 체크해야 합니다.

 

두 경우를 각각의 클래스로 구성한다면 문법을 검사하기 위한 Parser 클래스와 해당 패턴이 존재하는 지를 검사하는 PatternChecker 클래스를 정의해야 합니다. Parser 클래스에서는 파싱 알고리즘을 통해 입력된 문자열 패턴을 구문 트리로 생성하려 하는데 생성이 실패한다면 입력된 문자열 패턴이 정해진 문법을 따르지 않는다 판단하고 false를 떨구면 됩니다. PatternChecker 클래스에선 생성된 노드를 접근해서 문자열이 있는지를 체크하면 됩니다. 위 방식에 문제는 파싱 알고리즘을 사용하여 구현하는 부분도 알고리즘의 어려움 뿐 아니라 파싱을 위한 별도의 자료구조가 필요하고 트리를 생성하여 구문 트리를 방문하는 것도 쉽지 않습니다. 

 

위 방식보다 더 효율적으로 해결하기 위해서는 우선 해결해야 할 문제가 자료구조를 줄여야 합니다. 줄이기 위해서는 파싱 테이블을 사용하지 않고 구분 기호를 구분자로 파싱 하는 함수를 사용하고 문자열 패턴의 존재 여부 검사도 구문 트리 자체가 문자열 패턴을 직접 검사하면 따로 PatternChecker 클래스도 필요하지 않습니다.

 

구문 트리를 위한 자료구조는 주어진 문법에 따라 모든 문자열 패턴에 대해 트리를 생성해줄 수 있어야 하고 문법을 만족하지 않는 패턴은 생성을 하지 않아야 합니다. 이 방법을 위해서는 문법 정보를 클래스로 정의해서 사용하는 것이 좋습니다. 구문 트리를 생성하기 위한 클래스를 만들어 사용한다면 결국 또 다른 자료구조를 사용하게 되므로 효율적이지 못합니다.

 

문법 정보를 클래스로 정의하기 전에 문법은 Terminal 심볼과 Nonterminal 심볼로 구분되는 것을 알아야 합니다. Terminal 심볼은 Nonterminal 심볼로 유도되며 고정된 값을 가지고 Nonterminal 심볼 중에는 시작 심볼이 존재해서 다른 심볼로부터 유도하기 위한 출발점 역할을 합니다. 그 관계를 클래스로 바라보면 Terminal 심볼은 Nonterminal 심볼 클래스로부터 생성되는 객체라고 할 수 있습니다. 그리고 각각의 Nonterminal 심볼은 시작 심볼로부터 유도 가능하여 모든 Nonterminal 심볼 클래스들이 시작 심볼에 해당하는 클래스의 일종이라고 볼 수 있습니다. 결국 모든 Nonterminal 심볼 클래스는 시작 심볼 클래스로부터 상속을 받는 관계로 정의됩니다. 

 

여기서 아까 문법에서 시작 심볼이 RegExp이어서 최상위 클래스가 됩니다. 또한 각각의 Nonterminal 심볼들이 RegExp를 상속받는 구조를 가지게 됩니다. Nonterminal 심볼들은 유도 과정에서 다시 RegularExp를 가지고 있기 때문에 이를 표현하기 위해 OrExp와 AndExp는 RegularExp는 다시 참조하고 있습니다.

위 클래스 구조를 이용해서 "(test & game) | (test & team)" 패턴을 구문 트리로 생성하면 아래의 구조로 생성이 됩니다.

이제 제대로된 문법이라면 위의 구조를 만들어낼 것이고 그 이후에 각 노드들을 방문하면서 문자열이 존재하는지 검사합니다. 

 

class RegularExp { virtual bool Match(string context) = 0; };
class LiteralExp : public RegularExp {
    bool Match(string context) {
        if(literal == context) { return true; } else { return false; }
    }
private:
    string listeral;
};

class OrExp : public RegularExp {
    OrExp(RegularExp* pE1, RegularExp* pE2) : pOrExp(pE1), pOrExp(pE2) {}
    bool Match(string context) { 
        if (pOrExp1->Match(context)) { return true; }
        else { return pOrExp2->Match(context); }
    }
private:
    RegualarExp* pOrExp1, pOrExp2;
};
  
class AndExp : public RegularExp {
    AndExp(RegularExp* pE1, RegularExp* pE2) : pAndExp(pE1), pAndExp(pE2) {}
    bool Match(string context) { 
        if (pAndExp1->Match(context)) { return true; }
        else { return pAndExp2->Match(context); }
    }
private:
    RegualarExp* pAndExp1, pAndExp2;
};  

RegularExp* createRegularExp(string searchExp);

int main()
{
    string search;
    RegularExp* pRegExp = createRegularExp(string);
    if ( pRegExp == NULL ) { cout << "생성 실패"; }
    
    if(pRegExp->Match("data.txt") { cout << "찾기 성공"; }
};
        

위처럼 문법 자체를 클래스로 정의해서 문법 검사와 함께 필요한 기능을 별도의 자료구조 없이 효율적으로 수행할 수 있게 하는 클래스 구조를 인터프리터 패턴이라고 합니다. 인터프리터 패턴을 사용할 경우 상속관계를 변경시키면서 문법을 변경시키거나 확장시키는 것이 쉽고 클래스들의 구현 형태가 비슷해 구현이 쉽습니다.