この記事は オープンロジアドベントカレンダー の5日目の記事です。
はじめに
最近読んだ 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 をそれぞれ実装していきます。
字句解析
字句解析では、文字列をトークンという単位に分割し、その変換したトークンの列を返すことが目標です。これをコードで書くと以下のようになります。
<?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 を素直に生成していきます。最後まで文字を読み終えると、ループを抜けて生成したトークン列を配列で返します。
構文解析
次に構文解析です。構文解析は、トークン列を受け取り抽象構文木を返すことが目標です。これをコードで書くと以下のようになります。
<?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 メソッドで字句解析を実行します。各メソッドで自分の担当するノードを生成しながら、構文木をトップダウンで組み立てていきます。
評価
最後に評価を行います。ここでは、構文木を受け取り最終的な計算結果を返すことが目標です。これをコードで書くと以下のようになります。
<?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 で書籍の内容を再実装してみましたが、同じ題材をサンプルコードとは別の言語で書いてみると、単なる写経よりも高い学習効果が得られそうだと感じました。今後も積極的に取り入れていこうと思います。
また、今回は簡単な四則演算器までを実装しましたが、書籍では文字列, 配列, ハッシュなどのさらなるデータ型や、変数や関数の実装まで含まれているので、興味がある方は是非読んでみて下さい。