PHP で簡単なインタプリタをつくる #PHP

はじめに

最近読んだ Go言語でつくるインタプリタという書籍がとても面白かったので、復習も兼ねて弊社のサーバーサイド開発で利用されている PHP で再実装してみようと思います。インタプリタといっても、今回は四則演算のみをサポートする簡易なものに留めます。

例えば、 1 + 2 という入力を受けると、3 という出力を返します。スペースは含まれていても無視されます。

$ ./run.sh
> 1 + 2
3

また、優先順位もサポートします。例えば 1 + 2 * (3 + 4) を受けると 15 を返します。

$ ./run.sh
> 1 + 2 * (3 + 4)
15

完成したソースコードはこちらにアップしています。

尚、詳しい説明に関しては今回省略します。適宜文献などを参照して下さい。

プログラムの流れ

インタプリタとはなんでしょうか。 Wikipedia によると、おおよそ以下のようなものを指すようです。

インタプリタは、およそ次のいずれかの動作をするプログラムである。

ソースコードを直接解釈実行する。

ソースコードを何らかの効率的な中間的なコード（中間表現）に、最初に全て変換して、あるいは、逐次変換しながら、解釈実行する。

何らかのコンパイラが生成し出力した、何らかの効率的な（マシンに依存しない、あるいは、マシン依存の）中間表現を解釈実行する。

ソースコードをその場で解釈実行する、というのがポイントのようです。今回は 2. の説明にあるような、ソースコードをそのまま評価するのではなく、プログラムが扱いやすい中間表現に一旦変換してから、それを対象として評価を行うようなインタプリタを作成します。

具体的には、以下の3つの工程に分けて処理を行います。

字句解析 (Lexer) ... 文字列 (ソースコード) → トークン列に変換
構文解析 (Parser) ... トークン列 → 抽象構文木に変換
評価 (Evaluator) ... 抽象構文木 → 計算結果に変換

まず 字句解析 で、文字列を トークン列 に変換します。トークンというのは +, (, あるいは 10 のような、意味のある最小単位のかたまりのことです。例えば 1 + 2 という文字列が与えられたときに、字句解析では 1, +, 2 というトークンを生成し、列にして返します。この際、空白文字は意味のない文字なので無視されます。

次に 構文解析 で、トークン列を 抽象構文木 に変換します。構文木というのは、ソースコードの解析結果を木構造で表したものを指します。そして構文木から余分な情報 (優先順位のためのカッコなど) を排したものを抽象構文木といいます。構文解析の手法はいくつかありますが、今回は再帰下降構文解析を用いて行います。

最後に 評価 です。抽象構文木を解釈、実行します。これにより最終的な 計算結果 が得られることになります。

コードで書くと、以下のような感じです。

// ユーザー入力を受け取る
$stdin = trim(fgets(STDIN)); // <- ex. "1 + 2"

// 字句解析
$lexer = new Lexer();
$tokens = $lexer->lex($stdin); // 文字列を受け取ってトークン列を返す

// 構文解析
$parser = new Parser();
$ast = $parser->parse($tokens); // トークン列を受け取って抽象構文木を返す

// 評価
$evaluator = new Evaluator();
$result = $evaluator->eval($ast); // 抽象構文木を受け取って評価した結果を返す

print_r($result); // "3" を出力

それでは、 Lexer, Parser, Evaluator をそれぞれ実装していきます。

字句解析

字句解析では、文字列をトークンという単位に分割し、その変換したトークンの列を返すことが目標です。これをコードで書くと以下のようになります。

lexer.php

<?php

// トークンを表現するクラス
class Token
{
    public const PLUS = "+";
    public const MINUS = "-";
    public const ASTERISK = "*";
    public const SLASH = "/";
    public const LPAREN = "(";
    public const RPAREN = ")";
    public const NUM = "NUM";

    public string $kind;
    public ?int $value; // num のときは数値が入る

    public function __construct(string $kind, ?int $value = null)
    {
        $this->kind = $kind;
        $this->value = $value;
    }
}

// 字句解析を行うクラス
class Lexer
{
    private string $input; // 入力文字列
    private int $pos; // 次に読む文字のインデックス。この $pos を移動させていきながら1文字ずつ読んでいく

    /**
     * @return Token[]
     */
    public function lex(string $input): array
    {
        $this->input = $input;
        $this->pos = 0;

        $tokens = [];

        while ($this->char()) {
            $this->skipSpaces();

            $ch = $this->char();
            switch ($ch) {
                case '+':
                    $tokens[] = new Token(Token::PLUS); $this->pos++; break;
                case '-':
                    $tokens[] = new Token(Token::MINUS); $this->pos++; break;
                case '*':
                    $tokens[] = new Token(Token::ASTERISK); $this->pos++; break;
                case '/':
                    $tokens[] = new Token(Token::SLASH); $this->pos++; break;
                case '(':
                    $tokens[] = new Token(Token::LPAREN); $this->pos++; break;
                case ')':
                    $tokens[] = new Token(Token::RPAREN); $this->pos++; break;
                default:
                    if (preg_match('/^[0-9]$/', $ch)) {
                        $tokens[] = new Token(Token::NUM, $this->readNumber());
                        break;
                    }
                    throw new Exception("invalid char: {$ch}");
            }
        }

        return $tokens;
    }

    // 次の文字を返す (最後まで読み終えていれば NULL)
    private function char(): ?string
    {
        return $this->input[$this->pos];
    }

    // 空白文字を読み飛ばす
    private function skipSpaces(): void
    {
        while ($this->char() && ctype_space($this->char())) {
            $this->pos++;
        }
    }

    // 数値を読んで返す
    private function readNumber(): int
    {
        $prev = $this->pos;
        while ($this->char() && preg_match('/^[0-9]$/', $this->char())) {
            $this->pos++;
        }
        return (int) mb_substr($this->input, $prev, $this->pos - $prev);
    }
}

Token クラスでトークンを表現しています。例えば new Token(Token::NUM, 10) とすると、これは数値の10を表すトークンです。

Lexer クラスの lex メソッドで字句解析を実行します。受け取った文字列をループの中で1文字ずつ読み取りながら、途中で現れる空白文字をスキップしつつ、対応する Token を素直に生成していきます。最後まで文字を読み終えると、ループを抜けて生成したトークン列を配列で返します。

構文解析

次に構文解析です。構文解析は、トークン列を受け取り抽象構文木を返すことが目標です。これをコードで書くと以下のようになります。

parser.php

<?php

require_once('lexer.php');

// 抽象構文木のノード
interface Node
{
}

// 数値ノード
class NumNode implements Node
{
    public int $value;

    public function __construct(int $value)
    {
        $this->value = $value;
    }
}

// 単項演算ノード
class UnaryNode implements Node
{
    public UnaryOp $op;
    public Node $rhs;

    public function __construct(UnaryOp $op, Node $rhs)
    {
        $this->op = $op;
        $this->rhs = $rhs;
    }
}

// 二項演算ノード
class BinaryNode implements Node
{
    public BinaryOp $op;
    public Node $lhs;
    public Node $rhs;

    public function __construct(BinaryOp $op, Node $lhs, Node $rhs)
    {
        $this->op = $op;
        $this->lhs = $lhs;
        $this->rhs = $rhs;
    }
}

// 単項演算子
class UnaryOp
{
    public const PLUS = "+";
    public const MINUS = "-";

    public string $kind;

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

// 二項演算子
class BinaryOp
{
    public const ADD = "+";
    public const SUB = "-";
    public const MUL = "*";
    public const DIV = "/";

    public string $kind;

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

// 構文解析を行うクラス
class Parser
{
    private array $tokens; // 入力トークン列
    private int $pos; // 次に読むトークンのインデックス

    // program = expr ;
    // expr = term ("+"|"-" term)* ;
    // term = unary ("*"|"/" unary)* ;
    // unary = ("+"|"-")? factor ;
    // factor = number | "(" expr ")" ;
    public function parse(array $tokens): Node
    {
        $this->tokens = $tokens;
        $this->pos = 0;

        return $this->parseProgram();
    }

    // program = expr ;
    private function parseProgram(): Node
    {
        return $this->parseExpr();
    }

    // expr = term ("+"|"-" term)* ;
    private function parseExpr(): Node
    {
        $lhs = $this->parseTerm();
        while (1) {
            if ($this->peek(Token::PLUS)) {
                $this->pos++;
                $lhs = new BinaryNode(new BinaryOp(BinaryOp::ADD), $lhs, $this->parseTerm());
            } elseif ($this->peek(Token::MINUS)) {
                $this->pos++;
                $lhs = new BinaryNode(new BinaryOp(BinaryOp::SUB), $lhs, $this->parseTerm());
            } else {
                return $lhs;
            }
        }
    }

    // term = unary ("*"|"/" unary)* ;
    private function parseTerm(): Node
    {
        $lhs = $this->parseUnary();
        while (1) {
            if ($this->peek(Token::ASTERISK)) {
                $this->pos++;
                $lhs = new BinaryNode(new BinaryOp(BinaryOp::MUL), $lhs, $this->parseUnary());
            } elseif ($this->peek(Token::SLASH)) {
                $this->pos++;
                $lhs = new BinaryNode(new BinaryOp(BinaryOp::DIV), $lhs, $this->parseUnary());
            } else {
                return $lhs;
            }
        }
    }

    // unary = ("+"|"-")? factor ;
    private function parseUnary(): Node
    {
        if ($this->peek(Token::PLUS)) {
            $this->pos++;
            return new UnaryNode(new UnaryOp(UnaryOp::PLUS), $this->parseFactor());
        } elseif ($this->peek(Token::MINUS)) {
            $this->pos++;
            return new UnaryNode(new UnaryOp(UnaryOp::MINUS), $this->parseFactor());
        } else {
            return $this->parseFactor();
        }
    }

    // factor = number | "(" expr ")" ;
    private function parseFactor(): Node
    {
        if ($this->peek(Token::NUM)) {
            $node = new NumNode($this->token()->value);
            $this->pos++;
            return $node;
        }

        $this->expect(Token::LPAREN);
        $expr = $this->parseExpr();
        $this->expect(Token::RPAREN);
        return $expr;
    }

    // 次に読むトークン
    private function token() : ?Token
    {
        return $this->tokens[$this->pos];
    }

    // 次に読むトークンを確認する。期待と一致していれば true
    private function peek(string $tokenKind): bool
    {
        return $this->token() && $this->token()->kind === $tokenKind;
    }

    // トークンを1つ読みすすめる。ただし期待と一致してなければエラー
    private function expect(string $tokenKind): void
    {
        if (!$this->peek($tokenKind)) {
            throw new Exception($tokenKind." expected, but got ".$this->token()->kind);
        }
        $this->pos++;
    }
}

構文解析はいくつか手法がありますが、今回は再起下降構文解析で実装していきます。

Parser クラスの parse メソッドで字句解析を実行します。各メソッドで自分の担当するノードを生成しながら、構文木をトップダウンで組み立てていきます。

評価

最後に評価を行います。ここでは、構文木を受け取り最終的な計算結果を返すことが目標です。これをコードで書くと以下のようになります。

evaluator.php

<?php

require_once('lexer.php');
require_once('parser.php');

class Evaluator
{
    public function eval(Node $node): int
    {
        switch (get_class($node)) {
            case NumNode::class:
                return $node->value;
            case UnaryNode::class:
                return $this->evalUnaryNode(
                    $node->op,
                    $this->eval($node->rhs)
                );
            case BinaryNode::class:
                return $this->evalBinaryNode(
                    $node->op,
                    $this->eval($node->lhs),
                    $this->eval($node->rhs)
                );
            default:
                throw new Exception('unreachable');
        }
    }

    private function evalBinaryNode(BinaryOp $op, int $lhs, int $rhs): int
    {
        switch ($op->kind) {
            case BinaryOp::ADD:
                return $lhs + $rhs;
            case BinaryOp::SUB:
                return $lhs - $rhs;
            case BinaryOp::MUL:
                return $lhs * $rhs;
            case BinaryOp::DIV:
                if ($rhs === 0) {
                    throw new Exception('devision by zero');
                }
                return $lhs / $rhs;
            default:
                throw new Exception('unreachable');
        }
    }

    private function evalUnaryNode(UnaryOp $op, int $value): int
    {
        switch ($op->kind) {
            case UnaryOp::PLUS:
                return $value;
            case UnaryOp::MINUS:
                return $value * -1;
            default:
                throw new Exception('unreachable');
        }
    }
}

ここまでくるとパーツは揃っているので、あとは計算をするだけです。 Eval クラスの eval メソッドで評価を実行します。ここでも再帰的に処理を行っていますが、最終的に数値を返して終わるのでこの処理は収束します。

以上で、四則演算をするプログラムは完成です。

おわりに

今回は PHP で書籍の内容を再実装してみましたが、同じ題材をサンプルコードとは別の言語で書いてみると、単なる写経よりも高い学習効果が得られそうだと感じました。今後も積極的に取り入れていこうと思います。

また、今回は簡単な四則演算器までを実装しましたが、書籍では文字列, 配列, ハッシュなどのさらなるデータ型や、変数や関数の実装まで含まれているので、興味がある方は是非読んでみて下さい。

PHP で簡単なインタプリタをつくる

はじめに

プログラムの流れ

字句解析

構文解析

評価

おわりに

参考