解釋器模式

案例

張三公司最近需要開發(fā)一款簡單的加法/減法解釋器，只要輸入一個(gè)加法/減法表達(dá)式亩码，它就能夠計(jì)算出表達(dá)式結(jié)果，當(dāng)輸入字符串表達(dá)式為“1+2+3+4-5”時(shí)野瘦，將輸出計(jì)算結(jié)果為3模闲。很快張三就寫了出來：

1.計(jì)算表達(dá)式類：

public class Calculator {
    public int calculate(String expression) {
        String[] expressionArray = expression.split("");
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expressionArray.length; i++) {
            if ("+".equals(expressionArray[i])) {
                // 如果是 + 號，則再取下一個(gè)數(shù)累加后放入棧中
                Integer num = stack.pop();
                stack.push(num + Integer.valueOf(expressionArray[++i]));
            } else if ("-".equals(expressionArray[i])) {
                // 如果是 - 號洁桌，也是再取下一個(gè)數(shù)相減后放入棧中
                Integer num = stack.pop();
                stack.push(num - Integer.valueOf(expressionArray[++i]));
            } else {
                // 數(shù)字直接放入棧中
                stack.push(Integer.valueOf(expressionArray[i]));
            }
        }
        return stack.pop();
    }
}

2.客戶端使用：

public class Main {
    public static void main(String[] args) {
        Calculator calculator = new Calculator();
        String expression = "1+2+3+4-5";
        System.out.println(expression + "=" +calculator.calculate(expression));
    }
}

3.使用結(jié)果：

1+2+3+4-5=5

這里的例子比較簡單，主要目的是為了介紹下面的解釋器模式侯嘀，它主要就是使用面向?qū)ο笳Z言構(gòu)成一個(gè)簡單的語法解釋器另凌，如這里的"1+2+3+4-5"，在 Java 中是不能直接解釋運(yùn)行的戒幔，必須自己定義一套文法規(guī)則來實(shí)現(xiàn)對這些語句的解釋吠谢，相當(dāng)于設(shè)計(jì)一個(gè)自定義語言。就像編譯原理中語言和文法诗茎、詞法分析工坊、語法分析等過程。

模式介紹

一種行為型設(shè)計(jì)模式敢订。定義了一個(gè)解釋器栅组，來解釋給定語言和文法的句子。其實(shí)質(zhì)是把語言中的每個(gè)符號定義成一個(gè)（對象）類枢析，從而把每個(gè)程序轉(zhuǎn)換成一個(gè)具體的對象樹玉掸。

角色構(gòu)成

• AbstractExpression（抽象表達(dá)式）：在抽象表達(dá)式中聲明了抽象的解釋操作，它是所有終結(jié)符表達(dá)式和非終結(jié)符表達(dá)式的公共父類醒叁。
• TerminalExpression（終結(jié)符表達(dá)式）：終結(jié)符表達(dá)式是抽象表達(dá)式的子類司浪，它實(shí)現(xiàn)了與文法中的終結(jié)符相關(guān)聯(lián)的解釋操作，在句子中的每一個(gè)終結(jié)符都是該類的一個(gè)實(shí)例把沼。通常在一個(gè)解釋器模式中只有少數(shù)幾個(gè)終結(jié)符表達(dá)式類啊易，它們的實(shí)例可以通過非終結(jié)符表達(dá)式組成較為復(fù)雜的句子。
• NonterminalExpression（非終結(jié)符表達(dá)式）：非終結(jié)符表達(dá)式也是抽象表達(dá)式的子類饮睬，它實(shí)現(xiàn)了文法中非終結(jié)符的解釋操作租谈，由于在非終結(jié)符表達(dá)式中可以包含終結(jié)符表達(dá)式，也可以繼續(xù)包含非終結(jié)符表達(dá)式，因此其解釋操作一般通過遞歸的方式來完成割去。
• Context（環(huán)境類）：環(huán)境類又稱為上下文類窟却，它用于存儲(chǔ)解釋器之外的一些全局信息，通常它臨時(shí)存儲(chǔ)了需要解釋的語句呻逆。

UML 類圖

interpreter

解釋器模式是一種使用頻率相對較低但學(xué)習(xí)難度較大的設(shè)計(jì)模式夸赫，它用于描述如何使用面向?qū)ο笳Z言構(gòu)成一個(gè)簡單的語言解釋器。就是說在特定的應(yīng)用場景中咖城，可以創(chuàng)建一種新的語言茬腿，這種語言擁有自己的表達(dá)式和結(jié)構(gòu)，即文法規(guī)則宜雀，這些問題的實(shí)例將對應(yīng)為該語言中的句子切平。在這里的案例中"1+2+3+4-5"，可以用如下文法規(guī)則來定義：

expression ::= value | operation
operation ::= expression '+' expression | expression '-'  expression
value ::= an integer

首先這里的符號"::="表示“定義為”的意思辐董。第一行表示的是一個(gè)表達(dá)式揭绑，表達(dá)式的組成方式為 value 和 operation，即操作和數(shù)字組成郎哭。第二行 operation 操作表示表達(dá)式相加或表達(dá)式相減他匪。第三行就是指 value 是一個(gè)數(shù)字。下面就通過解釋器模式來實(shí)現(xiàn)加法/減法解釋器的功能夸研。

代碼改造

在解釋器模式中邦蜜，每一種終結(jié)符和非終結(jié)符都有一個(gè)具體類與之對應(yīng)，對于所有的終結(jié)符和非終結(jié)符亥至，我們首先需要抽象出一個(gè)公共父類悼沈，即抽象表達(dá)式類。

1.所以第一步創(chuàng)建抽象表達(dá)式類：

// 抽象表達(dá)式類
public abstract class AbstractExpression {
    // 提供統(tǒng)一的解釋接口
    public abstract int interpret();
}

2.各具體的終結(jié)或非終結(jié)符類：

數(shù)字解釋器類

// 終結(jié)符類
public class ValueExpression extends AbstractExpression {
    private int value;

    public ValueExpression(int value) {
        this.value = value;
    }

    @Override
    public int interpret() {
        return value;
    }
}

加法非終結(jié)符類

// 非終結(jié)符類
public class AddExpression extends AbstractExpression {
    private AbstractExpression left;
    private AbstractExpression right;

    public AddExpression(AbstractExpression left, AbstractExpression right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public int interpret() {
        return left.interpret() + right.interpret();
    }
}

減法非終結(jié)符類

// 非終結(jié)符類
public class SubtractionExpression extends AbstractExpression {
    private AbstractExpression left;
    private AbstractExpression right;

    public SubtractionExpression(AbstractExpression left, AbstractExpression right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public int interpret() {
        return left.interpret() - right.interpret();
    }
}

3.計(jì)算器類：

// 計(jì)算器類
public class Calculator {
    private AbstractExpression expression;

    public void parse(String expression) {
        String[] expressionArray = expression.split("");
        Stack<AbstractExpression> stack = new Stack<>();
        for (int i = 0; i < expressionArray.length; i++) {
            if ("+".equals(expressionArray[i])) {
                AbstractExpression left = stack.pop();
                AbstractExpression right = new ValueExpression(Integer.parseInt(expressionArray[++i]));
                stack.push(new AddExpression(left,right));
            } else if ("-".equals(expressionArray[i])) {
                AbstractExpression left = stack.pop();
                AbstractExpression right = new ValueExpression(Integer.parseInt(expressionArray[++i]));
                stack.push(new SubtractionExpression(left,right));
            } else {
                stack.push(new ValueExpression(Integer.parseInt(expressionArray[i])));
            }
        }
        this.expression = stack.pop();
    }

    public int calculate() {
        return expression.interpret();
    }
}

4.客戶端使用：

public class Main {
    public static void main(String[] args) {
        Calculator calculator = new Calculator();
        String expression = "1+2+3+4-5";
        calculator.parse(expression);
        System.out.println(expression + "=" + calculator.calculate());
    }
}

5.使用結(jié)果

1+2+3+4-5=5

可以看到結(jié)果和上面是一樣的姐扮。這里只是通過案例簡單的運(yùn)用了一下解釋器模式絮供，但不影響理解設(shè)計(jì)模式的魅力。

模式應(yīng)用

雖然解釋器模式的使用頻率不是特別高茶敏，但是它在正則表達(dá)式壤靶、XML文檔解釋等領(lǐng)域還是得到了廣泛使用。下面介紹的是其在Spring EL表達(dá)式中的典型應(yīng)用惊搏。

1.首先引入這里需要的 Spring 包：

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <parent>
        <artifactId>design-pattern</artifactId>
        <groupId>com.phoegel</groupId>
        <version>1.0-SNAPSHOT</version>
    </parent>
    <modelVersion>4.0.0</modelVersion>

    <artifactId>interpreter</artifactId>

    <properties>
        <spring.version>5.1.15.RELEASE</spring.version>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-expression</artifactId>
            <version>${spring.version}</version>
        </dependency>
    </dependencies>

</project>

2.簡單的使用例子：

public class Main {
    public static void main(String[] args) {
        SpelExpressionParser parser = new SpelExpressionParser();
        String expressionStr = "1+2+3+4-5";
        Expression expression = parser.parseExpression(expressionStr);
        System.out.println(expressionStr + "=" + expression.getValue());
    }
}

3.使用結(jié)果：

1+2+3+4-5=5

可以看到這里主要使用了類SpelExpressionParser.parseExpression()方法返回了Expression實(shí)例贮乳，看到這個(gè)類名就感覺和解釋器模式很有關(guān)系，因此由此深入源碼會(huì)發(fā)現(xiàn)Expression是一個(gè)接口恬惯，它的具體實(shí)現(xiàn)類有CompositeStringExpression向拆、LiteralExpression和SpelExpression等。而這里使用的SpelExpressionParser類來獲取Expression酪耳，因此很明顯它將返回SpelExpression浓恳，通過追蹤源碼也可以證明這一點(diǎn)。

下面是SpelExpressionParser類中獲取Expression的關(guān)鍵代碼，它其實(shí)最終通過InternalSpelExpressionParser類中doParseExpression()方法返回的：

protected SpelExpression doParseExpression(String expressionString, @Nullable ParserContext context)
      throws ParseException {
   try {
      this.expressionString = expressionString;
      // 根據(jù)傳入的字符串生成 Tokenizer 類實(shí)例
      Tokenizer tokenizer = new Tokenizer(expressionString);
      // 分析詞法生成 List<Token> 集合颈将，在這里類似于將字符串"1+2+3+4-5"分成了一個(gè)一個(gè)的次梢夯，類似于：1、+吆鹤、2厨疙、+洲守、3......
      this.tokenStream = tokenizer.process();
      this.tokenStreamLength = this.tokenStream.size();
      this.tokenStreamPointer = 0;
      this.constructedNodes.clear();
      // 生成抽象語法樹 ast
      SpelNodeImpl ast = eatExpression();
      Assert.state(ast != null, "No node");
      Token t = peekToken();
      if (t != null) {
         throw new SpelParseException(t.startPos, SpelMessage.MORE_INPUT, toString(nextToken()));
      }
      Assert.isTrue(this.constructedNodes.isEmpty(), "At least one node expected");
      // 最后將上面的數(shù)據(jù)封裝入 SpelExpression 類實(shí)例并返回
      return new SpelExpression(expressionString, ast, this.configuration);
   }
   catch (InternalParseException ex) {
      throw ex.getCause();
   }
}

上面代碼中最重要的是調(diào)用了tokenizer.process()生成詞法集合疑务，以及eatExpression()方法生成了 ast 抽象語法樹」４迹可以看到 ast 的類型為SpelNodeImpl知允，它的子類主要有 Literal，Operator叙谨，Indexer等温鸽，其中 Literal 是各種類型的值的父類，Operator 則是各種操作的父類手负。通過運(yùn)行時(shí)的查看涤垫，能夠看到這里的屬性如下圖示：

interpreter

根據(jù)上面的圖可以詳細(xì)的看出整個(gè) ast 抽象語法數(shù)的結(jié)構(gòu)及其每個(gè)節(jié)點(diǎn)的組成。最后就是通過expression.getValue()方法獲取結(jié)果了竟终，代碼如下：

public Object getValue() throws EvaluationException {
   CompiledExpression compiledAst = this.compiledAst;
   // 這里的 compiledAst == null 蝠猬，所以不會(huì)進(jìn)入判斷
   if (compiledAst != null) {
      try {
         EvaluationContext context = getEvaluationContext();
         return compiledAst.getValue(context.getRootObject().getValue(), context);
      }
      catch (Throwable ex) {
         // If running in mixed mode, revert to interpreted
         if (this.configuration.getCompilerMode() == SpelCompilerMode.MIXED) {
            this.compiledAst = null;
            this.interpretedCount.set(0);
         }
         else {
            // Running in SpelCompilerMode.immediate mode - propagate exception to caller
            throw new SpelEvaluationException(ex, SpelMessage.EXCEPTION_RUNNING_COMPILED_EXPRESSION);
         }
      }
   }

   ExpressionState expressionState = new ExpressionState(getEvaluationContext(), this.configuration);
   // 直接調(diào)用 this.ast.getValue() 獲取值
   Object result = this.ast.getValue(expressionState);
   checkCompile(expressionState);
   return result;
}

可以看到獲取值的時(shí)候是調(diào)用 ast 中的getValue()方法的，而這里的 ast 語法樹的節(jié)點(diǎn)類型從上面的 ast 抽象語法樹結(jié)構(gòu)圖可以看出來是OpMinus類實(shí)例统捶，因此會(huì)調(diào)用OpMinus類中的getValue()方法榆芦，這個(gè)方法的核心就是計(jì)算減法兩邊表達(dá)式的值相減返回結(jié)果，由于getValue()較長喘鸟，這里只貼出關(guān)鍵代碼：

public TypedValue getValueInternal(ExpressionState state) throws EvaluationException {
   SpelNodeImpl leftOp = getLeftOperand();

   // 判斷類型代碼省略...
   
   Object left = leftOp.getValueInternal(state).getValue();
   Object right = getRightOperand().getValueInternal(state).getValue();

   if (left instanceof Number && right instanceof Number) {
      Number leftNumber = (Number) left;
      Number rightNumber = (Number) right;

      if (leftNumber instanceof BigDecimal || rightNumber instanceof BigDecimal) {
         
      }
      // 其他判斷類型代碼省略...

      else if (CodeFlow.isIntegerForNumericOp(leftNumber) || CodeFlow.isIntegerForNumericOp(rightNumber)) {
          // 這里是數(shù)字做運(yùn)算匆绣，所以會(huì)進(jìn)入這里并返回相減結(jié)果
         this.exitTypeDescriptor = "I";
         return new TypedValue(leftNumber.intValue() - rightNumber.intValue());
      }
      else {
         // Unknown Number subtypes -> best guess is double subtraction
         return new TypedValue(leftNumber.doubleValue() - rightNumber.doubleValue());
      }
   }

   // ...
   return state.operate(Operation.SUBTRACT, left, right);
}

整個(gè) SpringEl 表達(dá)式中相關(guān)聯(lián)的類非常多，這里只是根據(jù)例子進(jìn)行了源碼追蹤什黑，來更好的理解解釋器模式崎淳。

總結(jié)

主要優(yōu)點(diǎn)

• 易于改變和擴(kuò)展文法。由于在解釋器模式中使用類來表示語言的文法規(guī)則愕把，因此可以通過繼承等機(jī)制來改變或擴(kuò)展文法凯力。

• 每一條文法規(guī)則都可以表示為一個(gè)類，因此可以方便地實(shí)現(xiàn)一個(gè)簡單的語言礼华。

• 實(shí)現(xiàn)文法較為容易咐鹤。在抽象語法樹中每一個(gè)表達(dá)式節(jié)點(diǎn)類的實(shí)現(xiàn)方式都是相似的，這些類的代碼編寫都不會(huì)特別復(fù)雜圣絮，還可以通過一些工具自動(dòng)生成節(jié)點(diǎn)類代碼祈惶。

• 增加新的解釋表達(dá)式較為方便。如果用戶需要增加新的解釋表達(dá)式只需要對應(yīng)增加一個(gè)新的終結(jié)符表達(dá)式或非終結(jié)符表達(dá)式類，原有表達(dá)式類代碼無須修改捧请，符合“開閉原則”凡涩。

主要缺點(diǎn)

• 對于復(fù)雜文法難以維護(hù)。在解釋器模式中疹蛉，每一條規(guī)則至少需要定義一個(gè)類活箕，因此如果一個(gè)語言包含太多文法規(guī)則，類的個(gè)數(shù)將會(huì)急劇增加可款，導(dǎo)致系統(tǒng)難以管理和維護(hù)育韩，此時(shí)可以考慮使用語法分析程序等方式來取代解釋器模式。
• 執(zhí)行效率較低闺鲸。由于在解釋器模式中使用了大量的循環(huán)和遞歸調(diào)用筋讨，因此在解釋較為復(fù)雜的句子時(shí)其速度很慢，而且代碼的調(diào)試過程也比較麻煩摸恍。

適用場景

• 可以將一個(gè)需要解釋執(zhí)行的語言中的句子表示為一個(gè)抽象語法樹悉罕。
• 一些重復(fù)出現(xiàn)的問題可以用一種簡單的語言來進(jìn)行表達(dá)。
• 一個(gè)語言的文法較為簡單立镶。
• 執(zhí)行效率不是關(guān)鍵問題壁袄。【注：高效的解釋器通常不是通過直接解釋抽象語法樹來實(shí)現(xiàn)的媚媒，而是需要將它們轉(zhuǎn)換成其他形式嗜逻，使用解釋器模式的執(zhí)行效率并不高⌒婪叮】

參考資料

• 大話設(shè)計(jì)模式
• 設(shè)計(jì)模式Java版本-劉偉
• 設(shè)計(jì)模式 | 解釋器模式及典型應(yīng)用

本篇文章github代碼地址：https://github.com/Phoegel/design-pattern/tree/main/interpreter
轉(zhuǎn)載請說明出處变泄，本篇博客地址：http://www.reibang.com/p/bb606ce1c8a5