Design Pattern, Interpreter

 

Class Behavioral Pattern

Interpreter Pattern

 

-----------------    INDEX     -----------------

 

Interpreter Pattern ?

BNF

Abstract Syntax Tree

Structure

Sample Code: Java

관련 패턴

 

----------------------------------------------

 

 

Given a language, define a represention for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

- GoF Design Patterns

 

인터프리터 패턴은 문법 규칙을 클래스화 한 구조로, 일련의 규칙으로 정의된 문법적 언어를 해석하는 패턴입니다.

 

인터프리터 패턴은 간단한 언어에 대한 문법을 정의하고, 언어로 문장을 표현하고, 이러한 문장을 해석하는 방법을 설명합니다.

간단한 언어를 구현하고, 그 문장을 해석하는 방법을 구현합니다.

 

언어를 정의하기 위해서 규칙을 명백히 표현해야하기 때문에 표기법을 사용합니다.

가장 유명하게 베커스-나우르 표기법(Backus-Naur form, BNF)입니다.

 

 

BNF

Backus-Naur form

BNF 표기법은 문법을 수학적인 수식으로 표기할 때 많이 이용합니다.

입력된 언어의 문장을 해석하기 위해 먼저 아래와 같이 정의합니다.

 

<기호> ::= <표현식>

 

::= 기호의 왼쪽은 정의가 되는 대상을 , 오른쪽에는 내용을 의미합니다.

비종료로는 <> 기호를, 선택은 | 기호를 표현합니다.

 

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number> ::= <digit> | <number><digit>

 

위 처럼 말이죠. 어떻게 표현되는지 같이 볼게요.

위에서 digit은 0...9까지의 문자로 표기될 수 있어요.

또, number은 digit과 같이 하나의 문자로 표현될 수도, 혹은(|) digit과 함께 재귀적인 표현도 가능합니다.

 

여기서 terminal expression과 nonterminal expression을 나눌 수 있어요.

 

 

Terminal Expression

digit을 확인해보면 0부터 9까지의 숫자 중 하나로 치환될 수 있다는 표시로 표현되어 있어요.

digit은 더 이상 다른 문자로 치환될 수 없는 종점의 문자입니다.

이러한 문자는 Terminal Expression이라고 해요.

 

 

Nonterminal Expression

Terminal Expression이 아닌 기호가 바로 Nonterminal Expression입니다.

위에서 보면 number가 될 수 있겠죠.

number는 <number><digit>으로 치환될 수가 있기 때문이죠.

 

 

 

Abstract Syntax Tree

컴퓨터 기계어과 달리 인간이 구현하는 고급언어에는 추상적 개념이 적용됩니다.

1차원적인 자료 구조로는 추상화된 언어를 처리할 수 없으며 하나의 언어를 처리하기 위해 광범위한 자료구조가 필요합니다.

구문트리syntax tree는 언어에서 표현한 구문의 정보를 가진 단순한 자료 구조입니다.

 

추상적이라는 의미는 실제 구문에서 나타내는 모든 세세한 것을 일일이 다루지 않는다는 것을 말합니다.

추상 구문 표현Abstract Expression은 모든 노드에 적용된 공통된 인터페이스를 갖고 있습니다.

 

추상 구문 트리는 컴파일러 등을 제작할 때 사용하는 자료 구조로,

문장 정보를 나누고 평가 순서를 재정의합니다.

주요 역할은 컴파일러가 작성된 언어를 해석할 때 단계별로 중간 표현을 처리하는 것입니다.

 

expression ::= literal | alternation | sequence | repetition | '(' expression ')' 

alternation ::= expression '|' expression 
sequence ::= expression '&' expression 
repetition ::= expression '*' 

literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... } *

 

예를 들어, 위와 같은 정의에서, raining & (dogs | cats) *와 같은 수식이 있을 때

raining <sequence> <expression> dogs <alternation> cats <expression> <repetition> 의 형식인게 확인되나요?

즉, 'raining'과 'dogs 혹은 cats의 반복'을 포함하는 문장이죠.

 

Gof Design Pattern

 

이 문장을 위와 같은 수식 트리로 표현할 수 있습니다.

 

 

 

Structure

 

GoF Design Patterns - Interpreter

 

AbstractExpression

✔️ 추상 syntax tree의 모든 노드에 공통으로 적용될 추상 Interpret() 메서드를 선언합니다.

 

TerminalExpression

✔️ 문법의 terminal 심볼과 관련된 Interpret() 메서드를 구현합니다.

✔️ 문장의 모든 terminal 심볼마다 인스턴스가 필요합니다.

표기가 더 이상 문자 또는 숫자로 치환되지 않는 최종적인 기호를 말합니다.

 

NonterminalExpression

✔️ 문법상의 모든 규칙 $R::=R_1R_2...R_n$ 에 필요합니다.
✔️ RI에서 Rn까지의 각 기호들에 대해 AbstractExpression 유형의 인스턴스 변수를 유지합니다.
✔️ 문법의 non-terminal  기호에 대한 해석 연산을 구현합니다. 해석은 일반적으로 $R_1$에서 $R_2$까지 나타내는 변수에 대해 재귀적으로 자신을 호출합니다.

 

식별자와 같이 종료되지 않은 기호이고 해석을 위해 전개되는 표현이며 기호나 규칙에 대한 노드만 가진 트리를 말합니다. 

반복적인 기호를 사용할 경우 플라이웨이트 패턴을 이용해 공유할 수 있습니다.

 

Context

✔️ 해석 프로그램에 대한 전반적인 정보가 포함되어 있습니다.

 

Client

✔️ 문법이 정의하는 언어의 특정 문장을 나타내는 추상 구문 트리를 만듭니다. 추상 구문 트리는 NonTerminalExpression 및 TerminalExpression 클래스의 인스턴스에서 결합됩니다.
✔️ 해석 연산을 호출합니다.

non-terminal 클래스와 terminal 클래스의 객체로 구성되고 구성 객체의 Interpret()를 호출합니다.

 

 

Sample Code: Java

전위 표기법을 인터프리터 패턴에 적용한 해석기를 만들어볼게요.

단순한 예시를 위한 코드이기 때문에 더하는 연산만을 제작합니다.

 

 

AbstractExpression

interface Expression {
    String interpret();
}

 

 

TerminalExpression

public class Terminal implements Expression {
    private String n;

    public Terminal(String n) {
        this.n = n;
    }

    @Override
    public String interpret() {
        return this.n;
    }
}

 

 

NonterminalExpression

public class Add implements Expression {
    private Expression left;
    private Expression right;

    public Add(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public String interpret() {
        int left = Integer.parseInt(this.left.interpret());
        int right = Integer.parseInt(this.right.interpret());
        return Integer.toString(left + right);
    }
}

 

 

Context

public class Context implements Iterator {
    private String[] tokens;
    private int position;
    private String start = "{";
    private String end = "}";

    public Context(String token) {
        this.tokens = token.split(" ");
        this.position = 0;
    }

    public boolean isStart() {
        return tokens[position].equals(start);
    }

    @Override
    public boolean hasNext() {
        return tokens.length > position && !tokens[position].equals(end);
    }

    @Override
    public String next() {
        return tokens[position++];
    }
}

 

 

Client

public class Client {
    public static void main(String[] args) {
        String lex = "{ 1 1 + 4 + }";
        Stack<Terminal> stack = new Stack<>();
        Context context = new Context(lex);

        if (context.isStart()) {
            System.out.println("수식 : " + lex);
            while (context.hasNext()) {
                String token = context.next();

                if (token.chars().allMatch(Character::isDigit)) {
                    stack.push(new Terminal(token));
                } else if (token.equals("+")) {
                    Terminal left = stack.pop();
                    Terminal right = stack.pop();

                    Expression add = new Add(left, right);
                    String value = add.interpret();

                    System.out.println(left.interpret() + " + " + right.interpret() + " = " + value);
                    stack.add(new Terminal(value));
                }
            }
        }
        System.out.println("최종 결과 = " + stack.pop().interpret());
    }
}

 

Output

수식 : { 1 1 + 4 + }
1 + 1 = 2
4 + 2 = 6
최종 결과 = 6

 

코드를 보니 확실히 이해되지 않나요?

 

 

 

관련 패턴

C- Creational Patterns  |  S - Structural Patterns  |  B - Behavioral Patterns

 

 

S: Composite

해석자 패턴은 구문 트리를 생성합니다. 해석자 패턴이 트리 구조를 가진 측면에서 복합체 패턴을 응용합니다.

또한 복합체 패턴을 사용할 때도 해석자 패턴을 응용할 수 있으며,

복합체 패턴이 하나의 언어 구조로 정의될 때 해석자 패턴으로 변경됩니다.

 

 

S: Flyweight

BNF 표기 시 ‘비종료 기호’가 반복적으로 수행됩니다.

어떤 명령이 반복적으로 수행될 때 해당 정의가 공유될 수 있는데, 이때 플라이웨이트 패턴을 응용합니다.

 

 

B: Visitor

해석자 패턴은 구문 트리의 각 노드를 순회하여 처리하는데, 노드를 순회할 때 방문자 패턴을 응용합니다.

 

 

 

 

그럼 지금까지 Interpreter Pattern에 대해 알아보았습니다.

오타나 잘못된 내용이 있다면 댓글로 남겨주세요!

감사합니다 ☺️ 

 

 

 

모든 Design Patterns 모아보기

Design Patterns