Wzorzec tłumacza - Interpreter pattern

W programowaniu komputerowym The pattern interpreter jest wzorzec projektowy , który określa w jaki sposób oceniać zdań w języku. Podstawową ideą jest posiadanie klasy dla każdego symbolu ( terminalowego lub nieterminalowego ) w wyspecjalizowanym języku komputerowym . Drzewo składni zdania w języku jest instancją kompozytowej strukturze i służy do oceny (interpretacji) kary dla klienta. Zobacz także Wzór złożony .

Przegląd

Wzorzec projektowy Interpreter jest jednym z dwudziestu trzech dobrze znanych wzorców projektowych GoF, które opisują sposób rozwiązywania powtarzających się problemów projektowych w celu projektowania elastycznego i wielokrotnego użytku oprogramowania zorientowanego obiektowo, czyli obiektów, które są łatwiejsze do wdrożenia, zmiany, testowania i ponowne użycie.

Jakie problemy może rozwiązać wzorzec projektowy Interpreter?

Gramatyki prostego języka powinny być określone
tak, że zdania w języku mogą być interpretowane.

Gdy problem pojawia się bardzo często, można rozważyć przedstawienie go jako zdania w prostym języku ( Domain Specific Languages ), aby tłumacz mógł rozwiązać problem, interpretując zdanie.

Na przykład, gdy należy określić wiele różnych lub złożonych wyrażeń wyszukiwania. Implementacja (hard-wiring) ich bezpośrednio do klasy jest nieelastyczna, ponieważ wiąże klasę z określonymi wyrażeniami i uniemożliwia określenie nowych wyrażeń lub zmianę istniejących niezależnie od (bez konieczności zmiany) klasy.

Jakie rozwiązanie opisuje wzorzec projektowy Interpreter?

Zdefiniuj gramatykę dla prostego języka, definiując Expressionhierarchię klas i implementując interpret()operację.
Reprezentuj zdanie w języku przez abstrakcyjne drzewo składni (AST) składające się z Expressioninstancji.
Zinterpretuj zdanie, dzwoniąc interpret()do AST.

Obiekty wyrażeń są składane rekursywnie do struktury złożonej/drzewa, która jest nazywana abstrakcyjnym drzewem składni (zobacz Wzorzec złożony ).
Wzorzec Interpreter nie opisuje, jak zbudować abstrakcyjne drzewo składni. Może to być zrobione ręcznie przez klienta lub automatycznie przez parser .

Zobacz także diagram klas i obiektów UML poniżej.

Zastosowania

Wyspecjalizowane języki zapytań do baz danych, takie jak SQL .
Wyspecjalizowane języki komputerowe często używane do opisu protokołów komunikacyjnych.
Większość języków komputerowych ogólnego przeznaczenia zawiera w rzeczywistości kilka języków specjalistycznych.

Struktura

Diagram klas i obiektów UML

Przykładowy diagram klas i obiektów UML dla wzorca projektowego Interpreter.

W powyższym diagramie klas UML , klasa odnosi się do wspólnego interfejsu do interpretacji wyrażenia . Klasa nie ma dzieci i interpretuje bezpośrednio wyrażenia. Klasa utrzymuje pojemnik wyrażeń dzieckiem ( ) i forward interpretować żądania do nich . ClientAbstractExpressioninterpret(context)
TerminalExpression
NonTerminalExpressionexpressionsexpressions

Diagram współpracy obiektów przedstawia interakcje w czasie wykonywania: ClientObiekt wysyła żądanie interpretacji do abstrakcyjnego drzewa składni. Żądanie jest przekazywane (wykonane) do wszystkich obiektów w dół struktury drzewa.
Te NonTerminalExpressionobiekty ( ntExpr1,ntExpr2) przekazuje wniosek do wyrażenia swoich dzieci.
W TerminalExpressionprzedmiotów ( tExpr1,tExpr2,…) przeprowadza się bezpośrednio w interpretacji.

Diagram klas UML

Przykłady

BNF

Poniższy przykład formularza Backus-Naur ilustruje wzorzec interpretera. Gramatyka

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

definiuje język, który zawiera wyrażenia Reverse Polish Notation, takie jak:

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

C#

Ten kod strukturalny demonstruje wzorce interpretera, który przy użyciu zdefiniowanej gramatyki zapewnia interpreter przetwarzający przeanalizowane instrukcje.

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 Expression
    {
        void Interpret(Context context);
    }

    abstract class OperatorExpression : Expression
    {
        public Expression Left { private get; set; }
        public Expression 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 : Expression
    {
        public string Value { private get; set; }

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

Jawa

Podążając za wzorcem interpretera, musimy zaimplementować interfejs Expr z lambdą (może to być klasa) dla każdej reguły gramatycznej.

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);
        }
    }

Podczas gdy wzorzec interpretera nie zajmuje się analizowaniem, analizator jest dostarczany dla kompletności.

    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();
    }

Ostateczna ocena wyrażenia „wxz - +” przy w = 5, x = 10 i 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
    }
}

PHP (przykład 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

PHP (przykład 2)

Na podstawie powyższego przykładu z inną realizacją klienta.

/**
 * 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;
    }
}

JavaScript

Ponieważ JavaScript jest wpisywany dynamicznie, nie implementujemy interfejsu.

// 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

Zobacz też

Bibliografia

^ ^B gamma Erich ; Helm, Ryszard ; Johnsona, Ralpha; Vlissides, John (1994). Wzorce projektowe: elementy oprogramowania obiektowego wielokrotnego użytku . Addisona-Wesleya. Numer ISBN 0-201-63361-2.
^ Erich Gamma Richard Helm Ralph Johnson John Vlissides (1994). Wzorce projektowe: elementy oprogramowania obiektowego wielokrotnego użytku . Addisona Wesleya. s. 243nn . Numer ISBN 0-201-63361-2.CS1 maint: wiele nazwisk: lista autorów ( link )
^ „Wzorzec projektowy Interpreter — problem, rozwiązanie i możliwość zastosowania” . w3sDesign.com . Pobrano 12.08.2017 .
^ "Wzorzec projektowy Interpreter - Struktura i współpraca" . w3sDesign.com . Pobrano 12.08.2017 .

Zewnętrzne linki

[GoF-1] B gamma Erich ; Helm, Ryszard ; Johnsona, Ralpha; Vlissides, John (1994). Wzorce projektowe: elementy oprogramowania obiektowego wielokrotnego użytku . Addisona-Wesleya. Numer ISBN 0-201-63361-2.

[GoF2-2] Erich Gamma Richard Helm Ralph Johnson John Vlissides (1994). Wzorce projektowe: elementy oprogramowania obiektowego wielokrotnego użytku . Addisona Wesleya. s. 243nn . Numer ISBN 0-201-63361-2.CS1 maint: wiele nazwisk: lista autorów ( link )

[3] „Wzorzec projektowy Interpreter — problem, rozwiązanie i możliwość zastosowania” . w3sDesign.com . Pobrano 12.08.2017 .

[4] "Wzorzec projektowy Interpreter - Struktura i współpraca" . w3sDesign.com . Pobrano 12.08.2017 .

Languages

In other projects