[디자인패턴][행위패턴] 인터프리터 Interpreter - C++

[모던 C++ 디자인 패턴] 책을 바탕으로 공부하는 내용을 정리한 내용이다.

---

Interpreter Pattern

Interpreter 디자인 패턴의 목적은 입력 데이터를 해석하는 것이다. 꼭 텍스트에 한정되지는 않는다. 인터프리터의 작업을 수행하는 몇 가지 단순한 예를 보여줄 것이다. 일반적인 예는 다음과 같다.

• 42나 1.234e12와 같은 숫자 리터럴은 바이너리로 저장하면 효율적이다. C++에서는 Boost.LexicalCast와 같은 고급 라이브러리를 사용할 수 있다. C의 API인 atof()를 이용할 수도 있다.
• 텍스트에서 어떤 패턴을 찾을 때 정규 표현식을 사용하면 편하다. 정규 표현식은 특정 목적을 위한 완전 별개의 언어다. 정규 표현식도 적절히 해석되어야만 한다.
• CSV, XML, JSON 또는 더 복잡한 경우를 포함해 어떤 형태로든 구조화된 데이터는 사용되기 위해 인터프리터가 필요하다.
• 인터프리터 응용의 정점은 프로그래밍 언어다. 컴파일러나 인터프리터는 코드를 실제 실행할 수 있는 형태로 바꾸기 위해 코드를 이해하는 작업을 수행한다.

---

산술 표현식의 계산

\(3+(5-4)\)와 같은 매우 단순한 수식 표현을 구문 분석해야 한다고 하자. 구문 분석을 지원하는 라이브러리의 도움 없이 바닥부터 구현해 간단한 계산기를 만들어보자. 이 예를 통해 텍스트 구문 분석이 가지는 복잡도를 어느 정도 이해할 수 있을 것이다.

렉싱(Lexing)

표현식을 해석하는 첫 단계는 렉싱이라 부른다. 렉싱은 문자열 입력을 토큰이라 불리는 단위로 나누어 나열한다. 토큰은 어떤 문법상에서 의미를 갖는 최소 단위다. 즉, 산술 표현식은 토큰들의 단순한 나열로 변환될 수 있어야 한다. 이 예에서는 아래와 같은 것들이 토큰이 된다.

• 정수
• 연산자(덧셈 기호, 뺄셈 기호)
• 괄호(열림 또는 닫힘)

struct Token {
    explicit Token(Type type, const string &test) : type(type), text(text) {
    }

    friend ostream &operator <<(ostream &os, const Token &obj) {
        return os << "`" << obj.text << "`";
    }

    enum Type {
        integer,
        plus,
        minus,
        lparen,
        rparen
    } type;
    
    string text;
};

 

단순한 enum 값은 토큰이 아니다. 토큰은 값이 아니라 분류에 가깝다. 기호는 토큰으로 분류되는 순간 값도 정해지지만, 숫자는 토큰으로 분류되더라도 텍스트에서 해당하는 부분이 별도 저장되어야 값을 보존할 수 있다.

아래는 렉싱 절차를 정의한 것이다.

vector<Token> lex(const string &input) {
    vector<Token> result;
    for ( int i = 0; i < input.size(); ++i ) {
        switch (input[i]) {
        case '+':
            result.push_back(Toknen(Token::plus, "+"));
            break;
        case '-':
            result.push_back(Token(Token::minus, "-"));
            break;
        case '(':
            result.push_back(Token(Token::lparen, "("));
            break;
        case ')':
            result.push_back(Token(Token::rparen, ")"));
            break;
        default:
            // 숫자 ??
        }
    }
}

덧셈, 뺄셈 기호처럼 확정적 토큰은 파싱 하기 쉽다. map<BinaryOperation, char>으로 저장하는 것이 더 편리하다. 하지만 숫자를 파싱 하는 것은 쉽지 않다. 연이어 오는 문자가 있는지 기다리는 루틴도 별도로 만들어야 한다.

ostringstream buffer;
buffer << input[i];
for ( int j = i + 1; j < input.size(); ++j ) {
    if ( isdigit(input[j]) ) {
        buffer << input[j];
        ++i;
    }
    else {
        result.push_back(Token(Token::integer, buffer.size()));
        break;
    }
}

파싱(Parsing)

파싱은 토큰의 나열을 의미 있는 단위로 바꾼다. 보통 "의미 있는 단위"는 객체 지향적 데이터 구조를 말한다. 데이터 구조 위에 모든 타입을 감싸는 추상 부모 타입을 두면 편리한 경우가 많다.

struct Element {
    virtual int eval() const = 0;
};

struct Integer : Element {
    explicit Integer(const int value) : value(value) {
    }
    
    int eval() const override {
        return value;
    }
    
    int value;
};

struct BinaryOperation : Element {
    int eval() const override {
        if ( type == addition ) {
            return lhs->eval() + rhs->eval();
        }
        
        return lhs->eval() - rhs->eval();
    }

    enum Type {
        addition,
        subtraction,
    } type;
    shared_ptr<Element> lhs, rhs;
};

eval() 함수는 해당 항목의 숫자 값을 구한다. Integer 클래스에서 숫자 값을 저장하는 자식 타입을 정의한다. Integer가 아니라면 연산자여야 하는데, 덧셈과 뺄셈 모두 이항 연산자이므로 두 하위 항목을 갖는다.

위에서 BinaryOperation에서는 enum 클래스 대신 그냥 enum을 사용한다. 이는 BinaryOperation::addition을 쓸 수 있게 하기 위함이다.

파싱 과정이 해야 할 일은 토큰의 나열을 표현식에 대한 이진트리로 바꾸는 것이다. 앞서 준비를 이용해 아래와 같이 구현 가능하다.

shared_ptr<Element> parse(const vector<Token> &tokens) {
    auto result = make_unique<BinaryOperation>();
    bool have_lhs = false; //< 표ㅗ현식의 왼쪽에 위치해야 할지 오른쪼겡 위치해야 할지 결정
    for ( size_t i = 0; i < tokens.size(); i++ ) {
        auto token = tokens[i];
        switch (token.type) {
            // 각 토큰을 처리
        }
    }
}

 

이제 토큰별로 각각의 생성 코드로 넘겨지게 된다.

// 숫자
case Token::integer : {
    int value = boost::lexical_cast<int>(token.text);
    auto integer = make_shared<Integer>(value);
    
    if ( !have_lhs ) {
        result->lhs = integer;
        have_lhs = true;
    }
    else {
        result->rhs = integer;
    }
}
// 연산(덧셈, 뺄셈)
case Token::plus : 
    result->type = BinaryOperation::addition;
    break;
case Token::minus :
    result->type = BinaryOperation::subtraction;
    break;
// 괄호
case Token::lparen: {
    int j = i;
    for ( ; j < tokens.size(); ++j ) {
        // 오른쪽 괄호 발견
        if ( tokens[j].type == Token::rparen ) {
            break;
        }
    }
    
    vector<Token> subexpression(&tokens[i + 1], &tokens[j]);
    auto element = parse(subexpression); // 재귀 호출
    
    if ( !have_lhs ) {
        result->lhs = element;
        have_lhs = true;
    }
    else {
        result->rhs = element;
    }
    
    // 계속 진행
    i = j;
}

---

Boost.Spirit을 이용한 파싱

실제 상황에서는 보통 일일이 파서를 구현하지는 않는다. Boost.Spirit은 파서를 만드는 데 도움을 주는 라이브러리다. 직관적이지는 않을 수 있는데, 파서를 생성할 수 있는 간결한 API를 제공한다. 이 라이브러리는 렉싱과 파싱 단계를 명시적으로 구분하지는 않는다. 대신 어떤 텍스트 구조가 내가 정의한 타입의 객체에 어떻게 맵핑되는지 정의한다. 저자가 임의로 만든 언어를 통해 살펴보자.(트론(Tlon))

추상 구문 트리

추상 구문 트리(Abstract Syntax Tree, AST)를 먼저 정의해야 한다. 이를 위해 Visitor 디자인 패턴을 지원하는 베이스 클래스를 만든다. 트리 구조의 순회가 핵심이기 때문에 Visitor 디자인 패턴이 유용하다.

struct ast_element {
    virtual ~ast_element() = default;
    virtual void accept(ast_element_visitor &visitor) = 0;
};

struct property : ast_element {
    void accept(ast_element_visitor &visitor) override {
        visitor.visit(*this);
    }
    
    vector<wstring> names;
    type_specification type;
    bool is_constant (false);
    wstring default_value;
};

4가지 속성 정보를 갖는데, type_specification은 그 자체로 또 하나의 ast_element이다.

AST의 모든 클래스는 Boost.Fusion을 적용해야 한다. Boost.Fusion은 컴파일 타임 합성(메타-프로그래밍)과 런타임 알고리즘을 지원한다. 아래와 같이 단순히 적용 가능하다.

BOOST_FUSION_ADAPT_STRUCT (
    tl n::property,
    (std::vector<std::wstring>, names),
    (tl n::type_specification, type),
    (bool, is_constant),
    (std::wstring, default_value)
)

Boost.Spirit은 std::vector나 std::optional 같은 공용 데이터 타입을 파싱 하는 데에는 아무 문제가 없다. 다형성 처리에 조금 문제가 있어, AST를 상속 관계로 구성하기보다는 variant를 사용하는 것이 유리하다.

optional / variant 참고

typedef variant<function_body, property, function_signature> class member;

 

파서

Boost.Spirit은 규칙의 집합으로서 파서를 정의할 수 있다. 규칙 정의는 정규 표현식이나 BNF(Bachus-Naur Form) 표시법과 유사하다. 연산자가 심볼 뒤가 아니라 앞에 위치한다는 것만 다르다. "트론"을 위해 마음대로 정한 문법 규칙이 다음과 같다고 해보자.

class_declaration_rule %=
    lit(L"class ") >> +(almnum) % '.'
    >> -(lit(L"(") >> -parameter_declaration_rule % ',' >> lit(")"))
    >> "{"
    >> *(function_body_rule | property_rule | function_signature_rule)
    >> "}";

규칙을 설명하자면 "class"로 클래스 선언이 시작해야 하고, 하나 이상의 단어가 ','으로 구분(% 연산자)되어 붙을 수 있다. 각 단어는 하나 이상의 알파벳 또는 숫자로 구성(+(alnum))될 수 있다. 결과는 vector에 맵핑된다. 중괄호 다음에 0개 이상의 함수 또는 속성 또는 함수 시그니처의 정의가 올 수 있다. 이러한 것들은 앞서 정의한 variant에 의해 결정된다.

어떤 항목은 전체 AST 항목들의 계층에서 뿌리가 된다. 그러한 뿌리 항목을 파일이라 부른다. 아래는 파일을 파싱하고 결과를 보기 좋게 출력하는 함수다. TLanguagePrinter 타입은 방문자 패턴의 방문자 역할을 한다. TLanguagePrinter는 트론 언어를 C++ 같은 다른 언어로 변환하는 데 사용될 수 있다.

template<typename TLanguagePrinter, typename Iterator>
wstring parse(Iterator first, Iterator last) {
    using spirit::qi::phrase_parse;
    file f;
    file_parser<wstring::const_iterator> fp{};
    auto b = phrase_parse(first, last, fp, space, f);
    if ( b ) {
        return TLanguagePrinter{}.pretty_print(f);
    }
    return wstring(L"FAIL");
}

프린터

언어를 파싱해 다른 언어로 변환할 수도 있다. 전체 AST 계층에 accept() 멤버 함수로 쉽게 할 수 있다. 유일한 어려운 부분은 variant 타입을 어떻게 처리할 것인가이다. 가변 타입은 특별한 Visitor를 필요로 한다. std::variant를 사용했다면 std::visit()가 호출된다. 하지만, boost::variant를 사용했기 때문에 boost::accept_visitor()가 호출되고, static_visitor를 상속받은 클래스를 넘겨주어야 한다. 넘길 클래스는 모든 가능한 타입에 대해 함수 호출 연산자가 오버로딩되어야 한다.

---

요약

인터프리터 디자인 패턴은 흔히 사용되지는 않는다. 파서를 직접 만들어야 할 상황도 많지 않다. 디자인 패턴 맥락에서는 여기까지 살펴본다. 관심이 있다면 Lex/Yacc, ANTLR 등 렉서/파서 관련 프레임워크를 살펴보길 바란다.