跳转到内容

解释器

Edit links
25% developed
来自维基教科书，开放书籍，为开放世界

享元模式 计算机科学设计模式
解释器 		迭代器
目录

给定一种语言，定义其语法的表示以及一个解释器，该解释器使用该表示来解释该语言中的句子。

示例

以下逆波兰表示法示例说明了解释器模式。 语法： expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable  ::= 'a' | 'b' | 'c' | ... | 'z'
digit ::= '0' | '1' | ... '9'
number ::= digit | digit number

定义了一种包含逆波兰表达式的语言，例如

a b +
a b c + -
a b + c a - -

 遵循解释器模式，每个语法规则都有一个类。

成本

此模式并不昂贵。 它显着减少了业务代码，因此只有少量代码需要处理。

创建

如果代码已经存在，此模式有点昂贵。

维护

此模式非常易于维护。 由于模式，没有额外的成本。

移除

此模式使用 IDE 中的重构操作很容易移除。

建议

  • 使用解释器术语向其他开发人员指示模式的使用。

实现

在 BNF 中实现

以下巴科斯-诺尔范式示例说明了解释器模式。 语法

expression ::= plus | minus | variable | number
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
digit = '0' | '1' | ... | '9'
number ::= digit | digit number

定义了一种包含逆波兰表示法表达式的语言，例如

a b +
a b c + -
a b + c a - -
在 C# 中实现

此结构化代码演示了解释器模式，该模式使用定义的语法提供解释器来处理已解析的语句。

using System;
using System.Collections.Generic;

namespace OOP;

class Program
{
    static void Main()
    {
        var context = new Context();
        var input = new MyExpression();

        var expression = new OrExpression
        {
            Left = new EqualsExpression
            {
                Left = input,
                Right = new MyExpression { Value = "4" }
            },
            Right = new EqualsExpression
            {
                Left = input,
                Right = new MyExpression { Value = "four" }
            }
        };

        input.Value = "four";
        expression.Interpret(context);
        // Output: "true" 
        Console.WriteLine(context.Result.Pop());

        input.Value = "44";
        expression.Interpret(context);
        // Output: "false"
        Console.WriteLine(context.Result.Pop());
    }
}

class Context
{
    public Stack<string> Result = new Stack<string>();
}

interface IExpression
{
    void Interpret(Context context);
}

abstract class OperatorExpression : IExpression
{
    public IExpression Left { private get; set; }
    public IExpression Right { private get; set; }

    public void Interpret(Context context)
    {
        Left.Interpret(context);
        string leftValue = context.Result.Pop();

        Right.Interpret(context);
        string rightValue = context.Result.Pop();

        DoInterpret(context, leftValue, rightValue);
    }

    protected abstract void DoInterpret(Context context, string leftValue, string rightValue);
}

class EqualsExpression : OperatorExpression
{
    protected override void DoInterpret(Context context, string leftValue, string rightValue)
    {
        context.Result.Push(leftValue == rightValue ? "true" : "false");
    }
}

class OrExpression : OperatorExpression
{
    protected override void DoInterpret(Context context, string leftValue, string rightValue)
    {
        context.Result.Push(leftValue == "true" || rightValue == "true" ? "true" : "false");
    }
}

class MyExpression : IExpression
{
    public string Value { private get; set; }

    public void Interpret(Context context)
    {
        context.Result.Push(Value);
    }
}

另一个例子

using System;
using System.Collections.Generic;
 
namespace Interpreter
{
    class Program
    {
        interface IExpression
        {
            int Interpret(Dictionary<string, int> variables);
        }
 
        class Number : IExpression
        {
            public int number;
            public Number(int number) { this.number = number; }
            public int Interpret(Dictionary<string, int> variables) { return number; }
        }
 
        abstract class BasicOperation : IExpression
        {
            IExpression leftOperator, rightOperator;
 
            public BasicOperation(IExpression left, IExpression right)
            {
                leftOperator = left;
                rightOperator = right;
            }
 
            public int Interpret(Dictionary<string, int> variables)
            {
                return Execute(leftOperator.Interpret(variables), rightOperator.Interpret(variables));
            }
 
            abstract protected int Execute(int left, int right);
        }
 
        class Plus : BasicOperation
        {
            public Plus(IExpression left, IExpression right) : base(left, right) { }
 
            protected override int Execute(int left, int right)
            {
                return left + right;
            }
        }
 
        class Minus : BasicOperation
        {
            public Minus(IExpression left, IExpression right) : base(left, right) { }
 
            protected override int Execute(int left, int right)
            {
                return left - right;
            }
        }
 
        class Variable : IExpression
        {
            private string name;
 
            public Variable(string name) { this.name = name; }
 
            public int Interpret(Dictionary<string, int> variables)
            {
                return variables[name];
            }
        }
 
        class Evaluator
        {
            private IExpression syntaxTree;
 
            public Evaluator(string expression)
            {
                Stack<IExpression> stack = new Stack<IExpression>();
                foreach (string token in expression.Split(' '))
                {
                    if (token.Equals("+"))
                        stack.Push(new Plus(stack.Pop(), stack.Pop()));
                    else if (token.Equals("-")){
                        IExpression right = stack.Pop();
                        IExpression left = stack.Pop();
                        stack.Push(new Minus(left, right));
                    }else
                        stack.Push(new Variable(token));
                }
                syntaxTree = stack.Pop();
            }
 
            public int Evaluate(Dictionary<string, int> context)
            {
                return syntaxTree.Interpret(context);
            }
        }
 
        static void Main(string[] args)
        {
            Evaluator evaluator = new Evaluator("w x z - +");
            Dictionary<string, int> values = new Dictionary<string,int>();
            values.Add("w", 5);
            values.Add("x", 10);
            values.Add("z", 42);
            Console.WriteLine(evaluator.Evaluate(values));
        }
    }
}
在 Java 中实现
public class Interpreter {
    @FunctionalInterface
    public interface Expr {
        int interpret(Map<String, Integer> context);
        
        static Expr number(int number) {
            return context -> number;
        }
        
        static Expr plus(Expr left, Expr right) {
            return context -> left.interpret(context) + right.interpret(context);
        }
        
        static Expr minus(Expr left, Expr right) {
            return context -> left.interpret(context) - right.interpret(context);
        }
        
        static Expr variable(String name) {
            return context -> context.getOrDefault(name, 0);
        }
    }
}

虽然解释器模式不涉及解析，但出于完整性，提供了解析器。

    private static Expr parseToken(String token, ArrayDeque<Expr> stack) {
        Expr left, right;
        switch(token) {
        case "+":
            // It's necessary to remove first the right operand from the stack
            right = stack.pop();
            // ...and then the left one
            left = stack.pop();
            return Expr.plus(left, right);
        case "-":
            right = stack.pop();
            left = stack.pop();
            return Expr.minus(left, right);
        default:
            return Expr.variable(token);
        }
    }
    public static Expr parse(String expression) {
        ArrayDeque<Expr> stack = new ArrayDeque<Expr>();
        for (String token : expression.split(" ")) {
            stack.push(parseToken(token, stack));
        }
        return stack.pop();
    }

最后评估表达式“w x z - +”，其中 w = 5，x = 10，z = 42。

    public static void main(final String[] args) {
        Expr expr = parse("w x z - +");
        Map<String, Integer> context = Map.of("w", 5, "x", 10, "z", 42);
        int result = expr.interpret(context);
        System.out.println(result);        // -27
    }
}

另一个例子

import java.util.Map;
interface Expression {
    public int interpret(Map<String, Expression> variables);
}

import java.util.Map;
class Number implements Expression {
    private int number;
    public Number(int number) {
        this.number = number;
    }
    public int interpret(Map<String, Expression> variables) {
        return number;
    }
}

import java.util.Map;
class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Plus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
    public int interpret(Map<String, Expression> variables) {
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}

import java.util.Map;
class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Minus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
    public int interpret(Map<String, Expression> variables)  {
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}

import java.util.Map;
class Variable implements Expression {
    private String name;
    public Variable(String name) {
        this.name = name;
    }
    public int interpret(Map<String, Expression> variables) {
        if (variables.get(name) == null) {
            // Either return new Number(0).
            return 0;
        } else {
            return variables.get(name).interpret(variables);
        }
    }
}

虽然解释器模式不涉及解析，但出于完整性，提供了解析器。

import java.util.Map;
import java.util.Stack;
class Evaluator implements Expression {
    private Expression syntaxTree;
 
    public Evaluator(String expression) {
        Stack<Expression> expressionStack = new Stack<Expression>();
        for (String token : expression.split(" ")) {
            if  (token.equals("+")) {
                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push( subExpression );
            }
            else if (token.equals("-")) {
                // it's necessary remove first the right operand from the stack
                Expression right = expressionStack.pop();
                // ..and after the left one
                Expression left = expressionStack.pop();
                Expression subExpression = new Minus(left, right);
                expressionStack.push( subExpression );
            }
            else                        
                expressionStack.push( new Variable(token) );
        }
        syntaxTree = expressionStack.pop();
    }
 
    public int interpret(Map<String,Expression> context) {
        return syntaxTree.interpret(context);
    }
}

最后评估表达式“w x z - +”，其中 w = 5，x = 10，z = 42。

import java.util.Map;
import java.util.HashMap;
public class InterpreterExample {
    public static void main(String[] args) {
        String expression = "w x z - +";
        Evaluator sentence = new Evaluator(expression);
        Map<String,Expression> variables = new HashMap<String,Expression>();
        variables.put("w", new Number(5));
        variables.put("x", new Number(10));
        variables.put("z", new Number(42));
        int result = sentence.interpret(variables);
        System.out.println(result);
    }
}
在 JavaScript 中实现

由于 JavaScript 是动态类型的，我们没有实现接口。

// Nonterminal expression
class Plus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) + this.b.interpret(context);
    }
}
// Nonterminal expression
class Minus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) - this.b.interpret(context);
    }
}
// Nonterminal expression
class Times {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) * this.b.interpret(context);
    }
}
// Nonterminal expression
class Divide {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) / this.b.interpret(context);
    }
}
// Terminal expression
class Number {
    a;
    constructor(a, b) {
        this.a = a;
    }
    interpret(context) {
        return this.a; 
    }
}
// Terminal expression
class Variable {
    a;
    constructor(a) {
        this.a = a;
    }
    interpret(context) {
        return context[this.a] || 0;
    }
}
// Client
class Parse {
    context;
    constructor(context) {
        this.context = context;
    }
    parse(expression) {
        let tokens = expression.split(" ");
        let queue = [];
        for (let token of tokens) {
            switch (token) {
                case "+":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Plus(a, b);
                    queue.push(exp);
                break;
                case "/":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Divide(a, b);
                    queue.push(exp);
                break;
                case "*":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Times(a, b);
                    queue.push(exp);
                break;
                case "-":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Minus(a, b);
                    queue.push(exp);
                break;
                default:
                    if (isNaN(token)) {
                        var exp = new Variable(token);
                        queue.push(exp);   
                    } else {
                        var number = parseInt(token);
                        var exp = new Number(number);
                        queue.push(exp);
                    }
                break;
            } 
        }
        let main = queue.pop();
        return main.interpret(this.context);
    }
}
var res = new Parse({v: 45}).parse("16 v * 76 22 - -");
console.log(res)
//666
在 PHP 中实现

示例 1

/**
 * AbstractExpression
 */
interface Expression
{
    public function interpret(array $context): int;
}

/**
 * TerminalExpression
 */
class TerminalExpression implements Expression
{
    /** @var string */
    private $name;

    public function __construct(string $name)
    {
        $this->name = $name;
    }

    public function interpret(array $context): int
    {
        return intval($context[$this->name]);
    }
}

/**
 * NonTerminalExpression
 */
abstract class NonTerminalExpression implements Expression
{
    /** @var Expression $left */
    protected $left;

    /** @var ?Expression $right */
    protected $right;

    public function __construct(Expression $left, ?Expression $right)
    {
        $this->left = $left;
        $this->right = $right;
    }

    abstract public function interpret(array $context): int;
    
    public function getRight()
    {
        return $this->right;
    }

    public function setRight($right): void
    {
        $this->right = $right;
    }
}

/**
 * NonTerminalExpression - PlusExpression
 */
class PlusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) + $this->right->interpret($context));
    }
}

/**
 * NonTerminalExpression - MinusExpression
 */
class MinusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) - $this->right->interpret($context));
    }
}

/**
 * Client
 */
class InterpreterClient
{
    protected function parseList(array &$stack, array $list, int &$index)
    {
        /** @var string $token */
        $token = $list[$index];

        switch($token) {
            case '-':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new MinusExpression($left, $right);
            case '+':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    protected function fetchArguments(array &$stack, array $list, int &$index): array
    {
        /** @var Expression $left */
        $left = array_pop($stack);
        /** @var Expression $right */
        $right = array_pop($stack);
        if ($right === null) {
            ++$index;
            $this->parseListAndPush($stack, $list, $index);
            $right = array_pop($stack);
        }

        return array($left, $right);
    }

    protected function parseListAndPush(array &$stack, array $list, int &$index)
    {
        array_push($stack, $this->parseList($stack, $list, $index));
    }

    protected function parse(string $data): Expression
    {
        $stack = [];
        $list = explode(' ', $data);
        for ($index=0; $index<count($list); $index++) {
            $this->parseListAndPush($stack, $list, $index);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

// test.php

function loadClass($className)
{
    require_once __DIR__ . "/$className.php";
}

spl_autoload_register('loadClass');

(new InterpreterClient())->main();
//result: -16

示例 2：基于上面的示例，使用另一种客户端实现。

/**
 * Client
 */
class InterpreterClient
{
    public function parseToken(string $token, array &$stack): Expression
    {
        switch($token) {
            case '-':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new MinusExpression($left, $right);
            case '+':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    public function parse(string $data): Expression
    {
        $unfinishedData = null;
        $stack = [];
        $list = explode(' ', $data);
        foreach ($list as $token) {
            $data = $this->parseToken($token, $stack);
            if (
                ($unfinishedData instanceof NonTerminalExpression) &&
                ($data instanceof TerminalExpression)
            ) {
                $unfinishedData->setRight($data);
                array_push($stack, $unfinishedData);
                $unfinishedData = null;
                continue;
            }
            if ($data instanceof NonTerminalExpression) {
                if ($data->getRight() === null) {
                    $unfinishedData = $data;
                    continue;
                }
            }
            array_push($stack, $data);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

示例 3：在一个文件中，我们有类和接口，定义了程序的逻辑（并应用了解释器模式）。 现在是expr.php文件

<?php
    interface expression{
        public function interpret (array $variables);
        public function __toString();
    }
    class number implements expression{
        private $number;
        public function __construct($number){
            $this->number = intval($number);
        }
        public function interpret(array $variables){
            return $this->number;
        }
        public function __toString(){
            return (string) $this->number;
        }
    }
    class plus implements expression{
        private $left_op;
        private $right_op;
        public function __construct(expression $left, expression $right){
            $this->left_op = $left;
            $this->right_op = $right;
        }
        public function interpret(array $variables){
            return ($this->left_op->interpret($variables) + $this->right_op->interpret($variables));
        }
        public function __toString(){
            return (string) ("Left op: {$this->left_op} + Right op: {$this->right_op}\n");
        }
    }
    class minus implements expression{
        private $left_op;
        private $right_op;
        public function __construct(expression $left, expression $right){
            $this->left_op = $left;
            $this->right_op = $right;
        }
        public function interpret(array $variables){
            return ($this->left_op->interpret($variables) - $this->right_op->interpret($variables));
        }
        public function __toString(){
            return (string) ("Left op: {$this->left_op} - Right op: {$this->right_op}\n");
        }
    }
    class variable implements expression{
        private $name;
        public function __construct($name){
            $this->name = $name;
        }
        public function interpret(array $variables){
            if(!isset($variables[$this->name]))
                return 0;
            return $variables[$this->name]->interpret($variables);
        }
        public function __toString(){
            return (string) $this->name;
        }
    }
?>

以及evaluate.php

<?php
    require_once('expr.php');
    class evaluator implements expression{
        private $syntaxTree;
        public function __construct($expression){
            $stack = array();
            $tokens = explode(" ", $expression);
            foreach($tokens as $token){
                if($token == "+"){
                    $right = array_pop($stack);
                    $left = array_pop($stack);
                    array_push($stack, new plus($left, $right));
                }
                else if($token == "-"){
                    $right = array_pop($stack);
                    $left = array_pop($stack);
                    array_push($stack, new minus($left, $right));
                }else if(is_numeric($token)){
                    array_push($stack, new number($token));
                }else{
                    array_push($stack, new variable($token));
                }
            }
            $this->syntaxTree = array_pop($stack);
        }
        public function interpret(array $context){
            return $this->syntaxTree->interpret($context);
        }
        public function __toString(){
            return "";
        }
    }
    // main code
    // works for it:
    $expression = "5 10 42 - +";
    // or for it:
    //$expression = "w x z - +";
    $variables = array();
    $variables['w'] = new number("5");
    $variables['x'] = new number("10");
    $variables['z'] = new number("42");
    print ("Evaluating expression {$expression}\n");
    $sentence = new evaluator($expression);
    $result = $sentence->interpret($variables);
    print $result . "\n";
?>

您可以在终端中通过键入 php5 -f evaluator.php 来运行（或将其放在 Web 应用程序中）。


Clipboard

待办事项
添加更多插图。


享元模式 计算机科学设计模式
解释器 		迭代器


您对本页有疑问吗？
在此提问


在本图书上创建新页面


取自"https://wikibooks.cn/w/index.php?title=Computer_Science_Design_Patterns/Interpreter&oldid=4287814"
华夏公益教科书