Tolmácsminta - Interpreter pattern

A számítógépes programozás során az értelmező minta egy tervezési minta, amely meghatározza, hogyan kell értékelni a mondatokat egy nyelven. Az alapötlet az, hogy minden szimbólumhoz ( terminálhoz vagy nem terminálhoz ) egy osztály tartozik egy speciális számítógépes nyelven . A nyelv egy mondatának szintaxisfa az összetett minta példánya, és a mondat kiértékelésére (értelmezésére) szolgál egy ügyfél számára. Lásd még Kompozit minta .

Áttekintés

Az Interpreter tervezési minta egyike annak a huszonhárom jól ismert GoF tervezési mintának, amelyek leírják, hogyan lehet megoldani az ismétlődő tervezési problémákat rugalmas és újrafelhasználható objektum-orientált szoftverek tervezéséhez, azaz olyan objektumokhoz, amelyeket könnyebb megvalósítani, megváltoztatni, tesztelni és újrafelhasználása.

Milyen problémákat tud megoldani a tolmács tervezési minta?

  • A nyelvtan egy egyszerű nyelven meg kell határozni
  • hogy a nyelv mondatai értelmezhetők legyenek.

Ha egy probléma nagyon gyakran fordul elő, úgy tekinthetjük, hogy egy egyszerű nyelven ( tartományspecifikus nyelvek ) mondatként ábrázolja, hogy a tolmács a mondat értelmezésével megoldhassa a problémát.

Például, ha sok különböző vagy összetett keresési kifejezést kell megadni. Azok közvetlen bevezetése (bekötése) egy osztályba rugalmatlan, mert az osztályt bizonyos kifejezésekre kötelezi, és lehetetlenné teszi az új kifejezések megadását vagy a meglévők megváltoztatását az osztálytól függetlenül (anélkül, hogy módosítaniuk kellene).

Milyen megoldást ír le a Tolmács tervezési minta?

  • Határozzon meg egy egyszerű nyelv nyelvtanát az Expressionosztályhierarchia meghatározásával és egy interpret()művelet végrehajtásával .
  • Jelöljön ki egy mondatot a nyelvben egy Expressionpéldányokból álló absztrakt szintaxisfa (AST) segítségével .
  • A mondat értelmezése interpret()az AST hívásával .

A kifejezésobjektumok rekurzív módon összetett/fa struktúrába kerülnek, amelyet absztrakt szintaktikai fának neveznek (lásd Összetett minta ).
Az Interpreter minta nem írja le, hogyan kell felépíteni egy absztrakt szintaktikai fát. Ezt manuálisan is elvégezheti egy ügyfél, vagy automatikusan egy elemző .

Lásd még az alábbi UML osztály- és objektumdiagramot.

Felhasználások

  • Speciális adatbázis -lekérdezési nyelvek, például SQL .
  • Speciális számítógépes nyelvek, amelyeket gyakran használnak a kommunikációs protokollok leírására.
  • A legtöbb általános célú számítógépes nyelv valójában több speciális nyelvet is tartalmaz.

Szerkezet

UML osztály és objektum diagram

Image
Minta UML osztály és objektumdiagram az Interpreter tervezési mintához.

A fenti UML osztálydiagramban az Clientosztály a kifejezés AbstractExpressionértelmezésére szolgáló közös felületre utal interpret(context).
Az TerminalExpressionosztálynak nincs gyermeke, és közvetlenül értelmez egy kifejezést.
Az NonTerminalExpressionosztály tart egy tárolót a gyermek kifejezésekből ( expressions), és továbbítja ezekhez a kéréseket expressions.

Az objektum együttműködési diagram a futási idejű interakciókat mutatja: Az Clientobjektum értelmezési kérést küld az absztrakt szintaxisfának. A kérést továbbítják (végrehajtják) az összes objektumhoz, lefelé a fa szerkezetét.
Az NonTerminalExpressionobjektumok ( ntExpr1,ntExpr2) továbbítják a kérést gyermekkifejezéseikhez.
Az TerminalExpressionobjektumok ( tExpr1,tExpr2,…) közvetlenül végzik az értelmezést.

UML osztály diagram

Tolmács UML osztály diagram.svg

Példák

BNF

A következő Backus – Naur űrlappélda szemlélteti az értelmező mintát. A nyelvtan 

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

olyan nyelvet határoz meg, amely fordított lengyel jelölési kifejezéseket tartalmaz, például: 

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

C#

Ez a szerkezeti kód az Interpreter mintákat mutatja be, amelyek egy meghatározott nyelvtant használva biztosítják az értelmezőt, amely feldolgozza az értelmezett utasításokat. 

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

Jáva

A tolmácsmintát követve minden nyelvtani szabályhoz implementálnunk kell az Expr interfészt lambdával (lehet osztály). 

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

Míg az értelmező minta nem foglalkozik az elemzéssel, a teljesség érdekében elemzőt biztosítunk. 

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

Végül értékelje a "wxz - +" kifejezést w = 5, x = 10 és z = 42 esetén. 

    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 (1. példa) 

/**
 * 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 (2. példa)

A fenti példa alapján az ügyfél másik megvalósításával. 

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

Mivel a JavaScript dinamikusan van gépelve, nem valósítunk meg felületet. 

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

Lásd még

Hivatkozások

  1. ^ a b Gamma, Erich ; Helm, Richard ; Johnson, Ralph; Vlissides, John (1994). Tervezési minták: Újrafelhasználható objektum-orientált szoftver elemei . Addison-Wesley. ISBN 0-201-63361-2.
  2. ^ Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1994). Tervezési minták: Újrafelhasználható objektum-orientált szoftver elemei . Addison Wesley. 243. o  . ISBN 0-201-63361-2.CS1 maint: több név: szerzői lista ( link )
  3. ^ "A tolmács tervezési mintája - probléma, megoldás és alkalmazhatóság" . w3sDesign.com . Letöltve: 2017-08-12 .
  4. ^ "A tolmács tervezési mintája - szerkezete és együttműködése" . w3sDesign.com . Letöltve: 2017-08-12 .

Külső linkek