[디자인패턴] 인터프리터 패턴 ( Interpreter Pattern )

Creational Patterns ( 생성 패턴 )

These design patterns provides way to create objects while hiding the creation logic, rather than instantiating objects directly using new operator. This gives program more flexibility in deciding which objects need to be created for a given use case. 

생성패턴은 객체의 생성로직을 숨기고 new 명령어를 통하지 않고 객체를 생성하는 방법들을 제공한다. 이는 특정 상황에서 어떤 방법으로 객체를 생성해야할지를 결정하는데 있어서 유연성을 제공한다. 

 Structural Patterns ( 구조적 패턴 )

These design patterns concern class and object composition. Concept of inheritance is used to compose interfaces and define ways to compose objects to obtain new functionalities. 

구조적 패턴들은 클래스와 객체의 구성에 관여한다.

 

 Behavioral Patterns ( 행위적 패턴 )

These design patterns are specifically concerned with communication between objects.

이 패턴들은 객체들 사이의 커뮤니케이션에 관심을 가진다.

 

오늘 살펴볼  Interpreter 패턴은 Behavioral 패턴에 속합니다. 

 

Interpreter Pattern Structure

 

  

패턴의 목적 ( Intent ) :  

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

패턴이 나오게 된 동기 ( Motivation ) :

   
A class of problems occurs repeatedly in a well-defined and well-understood domain. If the domain were characterized with a "language", then problems could be easily solved with an interpretation "engine".

 

GoF의 디자인 패턴에서는 아래와 같은 예제가 나옵니다.

 

아래 문법이 정규식을 표현한다고 가정합니다.

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

alternation ::= expression '|' expression
sequence ::= expression '&' expression
repetition ::= expression '*'
literal ::= 'a' | 'b' | 'c' | ... { 'a' | 'b' | 'c' | ... }*  

여기서 expression은 시작 symbol이고 literal은 종료 symbol입니다. 

인터프리터 패턴은 각 문법을 표현하기 위해서 하나의 클래스를 사용합니다. 우측의 심볼들은 이 클래스들의 인스턴스입니다. 위 문법은 다섯개의 클래스로 이루어져 있습니다. 추상클래스 RegularExpression 과 그 하위 클래스들인 LiteralExpression, AlternationExpression, SequenceExpression, 그리고 RepetitionExpression입니다. 마지막의 세 클래스들은 하위표현식을 갖는 변수를 정의합니다.

 

이 문법으로 정의된 모든 정규 표현식은 위와같은 클래스 인스턴스로 이루어진 추상 문법 트리로 표현됩니다. 예를 들면, 추상 문법 트리는 아래와 같습니다.

 

represents the regular expression  

raining & (dogs | cats) *

We can create an interpreter for these regular expressions by definingthe Interpret operation on each subclass of RegularExpression.Interpret takes as an argument the context in which to interpret theexpression. The context contains the input string and information onhow much of it has been matched so far. Each subclass ofRegularExpression implements Interpret to match the next part of theinput string based on the current context. For example,

• LiteralExpression will check if the input matches the literal it defines,

• AlternationExpression will check if the input matches any of its alternatives,

• RepetitionExpression will check if the input has multiple copies of expression it repeats, and so on.

 

유용성 ( Applicability ) :

 

Use the Interpreter pattern when there is a language to interpret, and you can represent statements in the language as abstract syntax trees.The Interpreter pattern works best when

 

• the grammar is simple. For complex grammars, the class hierarchy forthe grammar becomes large and unmanageable. Tools such as parsergenerators are a better alternative in such cases. They can interpret expressions without building abstract syntax trees, which can savespace and possibly time.

• efficiency is not a critical concern. The most efficient interpreters are usually not implemented by interpreting parse trees directly but by first translating them into another form. For example, regular expressions are often transformed into state machines. But even then,the translator can be implemented by the Interpreter pattern, so the pattern is still applicable.

등장 인물 ( Participants ) :

• AbstractExpression (RegularExpression)
  o declaresanabstractInterpretoperationthatiscommontoallnodes in the abstract syntax tree.

• TerminalExpression (LiteralExpression)
  o implements an Interpret operation associated with terminal symbols in the grammar.
  o an instance is required for every terminal symbol in a sentence.

• NonterminalExpression (AlternationExpression,RepetitionExpression, SequenceExpressions)
  o one such class is required for every rule R ::= R1 R2 ... Rn in the grammar.
  o maintains instance variables of type AbstractExpression for each of the symbols R1 through Rn.
  o implements an Interpret operation for nonterminal symbols in the grammar. Interpret typically calls itself recursively on the variables representing R1 through Rn.

• Context
  o contains information that's global to the interpreter.

• Client
  o builds (or is given) an abstract syntax tree representing a particular sentence in the language that the grammar defines. The abstract syntax tree is assembled from instances of the NonterminalExpression and TerminalExpression classes.
  o invokes the Interpret operation.

원리 ( Collaborations ) :  

• The client builds (or is given) the sentence as an abstract syntax tree of NonterminalExpression and TerminalExpression instances. Then the client initializes the context and invokes the Interpret operation.

• Each NonterminalExpression node defines Interpret in terms ofInterpret on each subexpression. The Interpret operation of eachTerminalExpression defines the base case in the recursion.

• The Interpret operations at each node use the context to store and access the state of the interpreter.

패턴 사용법

1. Decide if a "little language" offers a justifiable return on investment.
2. Define a grammar for the language.
3. Map each production in the grammar to a class.
4. Organize the suite of classes into the structure of the Composite pattern.
5. Define an interpret(Context) method in the Composite hierarchy.
6. The Context object encapsulates the current state of the input and output as the former is parsed and the latter is accumulated. It is manipulated by each grammar class as the "interpreting" process transforms the input into the output.

패턴 사용의 장단점 ( Consequences ): 

0. The Interpreter pattern has the following benefits and liabilities:  

1. 
   

   1. It's easy to change and extend the grammar. Because the pattern uses classes to represent grammar rules, you canuse inheritance to change or extend the grammar. Existing expressions can be modified incrementally, and new expressions can be defined as variations on old ones.  

2. 
   

   2. Implementing the grammar is easy,too. Classes defining nodes in the abstract syntax tree have similar implementations. These classes are easy to write, and often their generation can be automated with a compiler or parser generator.  

3. 
   

   3. Complex grammars are hard to maintain. The Interpreter pattern defines at least one class for every rule in the grammar (grammar rules defined using BNF may require multiple classes). Hence grammars containing many rules can be hard to manage and maintain. Other design patterns can be applied to mitigate the problem (see Implementation).But when the grammar is very complex, other techniques such as parser or compiler generators are more appropriate.  

4. 
   

   4. Adding new ways to interpret expressions. The Interpreter pattern makes it easier to evaluate an expression in a new way. For example, you can support pretty printing ortype-checking an expression by defining a new operation on the expression classes. If you keep creating new ways of interpreting an expression, then consider using the Visitor pattern to avoid changing the grammar classes.

 

관련 패턴들 :  

 

Composite :The abstract syntax tree is an instance of the Composite pattern.

Flyweight shows how to share terminal symbols within the abstract syntax tree.

Iterator :The interpreter can use an Iterator to traverse the structure.

Visitor can be used to maintain the behavior in each node in the abstract syntax tree in one class.

 

추가 정보 :    

• Considered in its most general form (i.e. an operation distributed over a class hierarchy based on the Composite pattern), nearly every use of the Composite pattern will also contain the Interpreter pattern. But the Interpreter pattern should be reserved for those cases in which you want to think of this class hierarchy as defining a language.
• Interpreter can use State to define parsing contexts.
• The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).
• Terminal symbols within Interpreter's abstract syntax tree can be shared with Flyweight.
• The pattern doesn't address parsing. When the grammar is very complex, other techniques (such as a parser) are more appropriate.

 

출처 :  http://sourcemaking.com/design_patterns/interpreter

Design Patterns : Element of Reusable Object Oriented Software ( by GoF, 1994 )