PHP7でデザインパターン入門23/23 Interpreterパターン

PHP design pattern

Interpreter パターンとは

Interpreter パターンの基本的な考えは、定義された種類の問題を素早く解くために、ドメインに特化した言語を実装することである。

Interpreter パターン - Wikipedia

Interpreterパターンでは、プログラムが解決しようとしている問題を簡単な「ミニ言語」で表現する。 通訳(interpreter)の役目を果たすプログラムを作ることで、そのミニ言語を理解し、ミニプログラムを解釈・実行する。

example

ミニ言語の命令

  • go: 前へ1ブロック進め
  • right: 右を向け
  • left: 左を向け

ミニ言語の構文

以下のように命令の初めて終わりを program と end で囲む

program go end

例えば回れ右をするミニプログラムは以下のようになる。

program go right right go end

また、repeat N … end 構文を使うことでN回の繰り返し処理ができるものとする。

program repeat 4 go right end end

サンプルプログラムは、上記のミニ言語を構文解析する。ミニプログラムを構文木としてメモリ上に作り上げる処理が構文解析。 サンプルプログラムでは、この構文木を構築するまでを扱う。

ミニ言語の文法として、BNF*1を使う。

Node 抽象クラス

構文木の各部分(ノード)を構成する最上位のクラス。parseメソッドのみ宣言している。このparseは「構文解析という処理を行う」ためのメソッドである。引数のContextは構文解析を行っている「状況」を表すクラス。

<?php
abstract class Node
{
    abstract public function parse(Context $context);
}

ProgramNodeクラス

構文解析の際の処理単位をトークンと呼ぶ。skipTokenメソッドはprogramというトークンがなかったら、ParseExceptionを投げる。

<?php
// <program> ::= program <command list>
class ProgramNode extends Node
{
    private $commandListNode;

    public function parse(Context $context)
    {
        $context->skipToken("program");
        $this->commandListNode = new CommandListNode();
        $this->commandListNode->parse($context);
    }
    public function __toString(): string
    {
        return $this->commandListNode
            ? "[program {$this->commandListNode}]"
            : "";
    }
}

CommandListNodeクラス

<?php
// <command list> ::= <command>* end
class CommandListNode extends Node
{
    private $list = [];

    public function parse(Context $context)
    {
        while (true) {
            if ($context->currentToken() === null) {
                throw new ParseException("Missing 'end'");
            }
            if ($context->currentToken() === "end") {
                $context->skipToken("end");
                break;
            }
            $commandNode = new CommandNode();
            $commandNode->parse($context);
            $this->list[] = $commandNode;
        }
    }

    public function __toString(): string
    {
        return $this->list
            ? "[" . join(" ", $this->list) . "]"
            : "[]";
    }
}

CommandNodeクラス

<?php
// <command> ::= <repeat command> | <primitive command>
class CommandNode extends Node
{
    private $node;

    public function parse(Context $context)
    {
        if ($context->currentToken() === "repeat") {
            $this->node = new RepeatCommandNode();
            $this->node->parse($context);
        } else {
            $this->node = new PrimitiveCommandNode();
            $this->node->parse($context);
        }
    }

    public function __toString(): string
    {
        return $this->node ?? "";
    }
}

RepeatCommandNodeクラス

<?php
// <repeat command> ::= repeat <number> <command list>
class RepeatCommandNode extends Node
{
    private $number;
    private $commandListNode;

    public function parse(Context $context)
    {
        $context->skipToken("repeat");
        $this->number = $context->currentNumber();
        $context->nextToken();
        $this->commandListNode = new CommandListNode();
        $this->commandListNode->parse($context);
    }
    public function __toString(): string
    {
        return $this->commandListNode
            ? "[repeat {$this->number} {$this->commandListNode}]"
            : "";
    }
}

PremitiveCommandNodeクラス

<?php
// <primitive command> ::= go | right | left
class PrimitiveCommandNode extends Node
{
    private $name;

    public function parse(Context $context)
    {
        $this->name = $context->currentToken();
        $context->skipToken($this->name);
        if ($this->name !== "go"
            && $this->name !== "right"
            && $this->name !== "left") {
            throw new ParseException("{$this->name} is undefined");
        }
    }

    public function __toString(): string
    {
        return $this->name ?? "";
    }
}

Contextクラス

<?php
class Context
{
    private $token;
    private $currentToken;

    public function __construct(string $text)
    {
        $this->token = preg_split("/[\s,]+/", $text);
        $this->nextToken();
    }

    public function nextToken(): string
    {
        $this->currentToken = ($this->currentToken === null)
            ? current($this->token)
            : next($this->token);

        return $this->currentToken;
    }

    public function currentToken(): string
    {
        return $this->currentToken;
    }

    public function skipToken(string $token)
    {
        if ($token !== $this->currentToken) {
            throw new ParseException("Warning: {$token} is expected, but {$this->currentToken} is found.");
        }
        $this->nextToken();
    }

    public function currentNumber(): int
    {
        return intval($this->currentToken);
    }
}

ParseExceptionクラス

<?php
class ParseException extends Exception
{
    public function __construct(string $msg)
    {
        parent::__construct($msg);
    }
}

Main

<?php
$f = file(__DIR__ . "/Program.txt", FILE_IGNORE_NEW_LINES);
if (empty($f)) {
    die('file read error.');
}

try {
    foreach ($f as $v) {
        echo "text = \"" . $v . "\"" . PHP_EOL;
        $node = new ProgramNode();
        $node->parse(new Context($v));
        echo "node = " . $node . PHP_EOL;
    }
} catch (\Exception $e) {
    echo $e->getMessage();
}

実行結果

$ php Main.php
text = "program end"
node = [program []]
text = "program go end"
node = [program [go]]
text = "program go right go right go right go right end"
node = [program [go right go right go right go right]]
text = "program repeat 4 go right end end"
node = [program [[repeat 4 [go right]]]]
text = "program repeat 4 repeat 3 go right go left end right end end"
node = [program [[repeat 4 [[repeat 3 [go right go left]] right]]]]

ソースコード

github.com

役割

AbstractExpression役

構文木のノードに共通のインターフェースを定める役。 サンプルコードにおけるNodeクラス。

TerminalExpression役

BNFのターミナルエクスプレッションに対応する役。 サンプルコードにおけるPremitiveCommandNode

NonterminalExpresion役

BNFのノンターミナルエクスプレッションに対応する役 サンプルコードにおけるProgramNode, CommandNode, RepeatCommandNode, CommandListNodeクラス。

Context役

インタプリタが構文解析を行うための情報を提供する役。 サンプルコードにおけるContextクラス。

Client役

サンプルコードにおけるMain.php。

関連するパターン

デザインパターンのまとめ

今更ながら、改めてデザインパターンを学習して良かった。

  • 抽象クラス、インターフェースの役割
  • 継承と委譲
  • 交換可能性
  • コードの再利用性

実際にデザインパターンを言語化してまとめることで、以前より設計に自信を持てるようになった。具体的には、デザインの目的、思想を言葉で説明できるようになり、より設計に対して強い根拠を持てるようになった。

このデザインパターン本学習は一旦終わり。

とても楽しく学習できた。参考にした本「Java言語で学ぶデザインパターン入門」の著者、結城浩に感謝。

関連パターン

増補改訂版Java言語で学ぶデザインパターン入門

増補改訂版Java言語で学ぶデザインパターン入門

*1:バッカス・ナウア記法 - Wikipedia