Ast.pm 最初のAST構築から計算
数式を計算するプログラムは、文字列を左から順番に計算すればよいわけではありません。
例えば 2*(3+4)-5 では、括弧の中を先に計算し、次に乗算、最後に減算を行う必要があります。
今回は、Perlで書かれた Ast.pm を題材に、数式からAST（抽象構文木）を構築し、その木をたどって計算する仕組みを追いかけてみます。
概要
Tool::mmt::Controller::Ast は、文字列で受け取った数式を二分木（AST）に変換し、その木をたどって計算する Mojolicious コントローラです。対象ファイルは Ast.pm（コミット 59dd332） です。
- 入力: リクエストパラメータ
calc（例:2*(3+4)-5） - 出力: stash の
anser（計算結果）とtree（Data::Dumper による木のダンプ） - 方式: 式を「最も優先順位の低い演算子」で左右に分割することを再帰的に繰り返して木を作り、葉から順に計算する
eval で文字列をそのまま実行しないため、入力がコードとして実行される心配はありません。
演算子テーブル
演算子は %$op に [処理のコードリファレンス, 優先順位, 結合性] の形で定義されています。数字が小さいほど結合が弱く、木の上（根に近い側）に来ます。
my $op = +{ '-' => [sub {$_[0] - $_[1]},1,'L'], # オペレータ定義
'+' => [sub {$_[0] + $_[1]},1,'L'],
'*' => [sub {$_[0] * $_[1]},2,'L'],
'/' => [sub {$_[0] / $_[1]},2,'L'],
'%' => [sub {$_[0] % $_[1]},2,'L'],
'NGE' => [sub { -$_[0]},4,'R'],
'**' => [sub {$_[0] ** $_[1]},4,'R'],
'(' => [sub { },9,'L'],
')' => [sub { },10,'L'],
};
| 演算子 | 優先順位 | 結合性 | 処理 |
|---|---|---|---|
+ -
|
1 | 左 | 加算・減算 |
* / %
|
2 | 左 | 乗算・除算・剰余 |
** |
4 | 右 | べき乗 |
NGE |
4 | 右 | 単項マイナス（解析時に - から置き換える内部用の記号） |
( )
|
9 / 10 | 左 | 何もしない。正規表現で分割するためだけに登録 |
setReOps はこのキーを長い順に並べて正規表現 $s->{ops} を作ります。長い順にするのは、** を * 2つと誤認しないためです。
sub setReOps{ # 演算子の正規表現作成
my $s = shift;
$s->{ops} = join ('|',map {s/(\W)/\\$1/g;$_;} sort {length $b <=> length $a} keys %$op);
$s->{ops} = "(".$s->{ops}.")";
return $s;
}
処理の流れ
リクエストから答えまでは、次の順に一直線で進みます。
-
ast（アクション）:calcパラメータを取り出し、formulaとしてAstnewに渡す。戻り値のanserを stash に入れる。 -
Astnew: 引数をハッシュにし、setReOpsで演算子の正規表現を用意する。formulaがあれば_astを呼ぶ。 -
_ast: 以下の 4〜7 を順に実行し、木のダンプを stash のtreeに、結果を$s->{anser}に入れる。 -
adjust: 演算子の前後に空白を入れる。数字や)の直後に(があれば*を補う（(1+2)(2-1)→(1+2)*(2-1)）。 -
item_split: 空白で区切ってトークンの配列$s->{item}にする。 -
makeTree: トークン列から二分木を組み立てる（次の節で詳しく説明）。 -
readTree: 木を葉から根へたどって値を計算する。
_ast は 4〜7 を 1 行に連結しています。
sub _ast{
my $s = shift;
$s->{root} = $s->makeTree(@{$s->item_split($s->adjust(shift))->{item}});
$s->stash(tree => Dumper $s->{root});
$s->{anser} = $s->readTree($s->{root});
}
sub adjust{ # 計算式の要素をスペースで分割
my ($s,$text) = @_;
$text =~ s/$s->{ops}/ $1 /g;
$s->{_text} = $text =~ s{([\d\)])\s*\(}{$1 \* \(}g; # 開き括弧の前が演算子じゃない時に*を補完
return $text;
}
ノードは newNode が作る {data => 演算子, left => 左, right => 右} のハッシュです。葉は数値そのもの（スカラー）で、readTree は「ハッシュリファレンスかどうか」で葉と演算子を見分けます。
readTree の動き:
- 葉ならその値を返す
-
NGEなら右の子を計算して符号を反転する（左は使わない） - それ以外は左右を再帰的に計算し、その結果をノードに書き戻してから演算子のコードを適用する
sub readTree{ # AST計算
my ($s,$node) = @_;
return $node if(ref($node) ne 'HASH');
if($node->{data} eq 'NGE'){
return $op->{$node->{data}}->[0]($s->readTree($node->{'right'}));
}
do{$node->{$_} = $s->readTree($node->{$_}) if(ref($node->{$_}) eq 'HASH')} for ('left','right');
exists $op->{$node->{data}} ? $op->{$node->{data}}->[0]($node->{left},$node->{right})
: $node->{data};
}
AST構築の仕組み（makeTree）
makeTree は「括弧の外にある、優先順位が最も低い演算子」を根にし、その左側と右側のトークン列で自分自身を再帰的に呼びます。
-
外側の括弧を外す: 先頭が
(、末尾が)で、その括弧が式全体を包んでいるときだけ外す。((1))のような重ね括弧は繰り返し外す。(1+2)*(3+4)のように括弧の塊が複数あるときは外さない。 - 葉の判定: トークンが 1 つだけならそれを葉として返す。
-
分割点を探す: 括弧の深さ 0 のトークンだけを見て、優先順位が最も低い演算子の位置を記録する。比較は
juge_priorityが行う。 -
分割して再帰: 分割点より前を左の子、後ろを右の子として
makeTreeを呼び、newNodeでまとめる。
sub makeTree{ # AST組み立て
my $s = shift;
while($_[0] eq '(' and $_[-1] eq ')'){
my ($r,$sw) = (0,0);
for(@_){ # '('の深さを計算
++$r if($_ eq '(');
--$r if($_ eq ')');
++$sw if($r == 1 and $_ eq '(');
}
if($sw == 1){ # 一番外側の括弧を外す
shift; pop;
}else{
last;
}
}
return shift() if(@_ <= 1); # 要素が一つの時は要素を返す
my ($prio,$i,$m,$r) = (99,-1,0,0);
for(@_){ # 一番右側の一番プライオリティの低いオペレータを検索
++$i;
my $cur = $_;
if(/^$s->{ops}$/){
++$r if($_ eq '(');
--$r if($_ eq ')');
next if($r or $_ eq ')'); # 括弧の間は読み飛ばす
if($_ eq '-' && ($i == 0 || ($_[$i - 1] =~ /^$s->{ops}$/ && $_[$i - 1] ne ')'))){
$_[$i] = $cur = 'NGE';
}
if($s->juge_priority($cur,$prio)){
$prio = $op->{$cur}->[1];
$m = $i;
}
}
}
return $s->newNode($_[$m], # オペレータとオペランド（右と左）を返す
$s->makeTree(@_[0 .. $m-1]),
$s->makeTree(@_[$m+1 .. $#_])
);
}
$sw は深さ 1 で開いた ( の数、つまり最上位の括弧の塊の数です。これが 1 のときだけ外側の括弧を外します。( の優先順位 9 と ) の 10 は、括弧が分割点に選ばれないようにするための大きな値です。
同じ優先順位が並んだとき（結合性）
- 左結合（
+ - * / %）: 同順位なら後ろのもので上書きするので、一番右で分割する。8-3-2は(8-3)-2= 3 になる。 - 右結合（
**NGE）: より低いときだけ上書きするので、一番左で分割する。2**3**2は2**(3**2)= 512 になる。
結合性の違いは juge_priority の < と <= の 1 文字だけで表現されています。
sub juge_priority {
my $s = shift;
$op->{$_[0]}->[2] eq 'R'
?$op->{$_[0]}->[1] < $_[1]
:$op->{$_[0]}->[1] <= $_[1];
}
juge_priority が真を返したときだけ、現在の演算子の位置を $m に記録します。左結合の演算子は同じ優先順位でも位置を更新するため、最後に見つかった演算子が分割点になります。一方、右結合の演算子は同じ優先順位では更新しないため、最初に見つかった演算子が分割点として残ります。
単項マイナス
- が式の先頭にあるか、) 以外の演算子の直後にあるとき、NGE に置き換えます。NGE ノードは left が空で、right に対象の式を持ちます。優先順位は ** と同じ 4 なので、-2**2 は -(2**2) = -4 になります（数学の一般的な解釈と同じ）。
計算例: 2*(3+4)-5
calc=2*(3+4)-5 を渡すと、答えは 9 になります。
-
adjustとitem_splitでトークン列2 * ( 3 + 4 ) - 5になる。 - 括弧の外にある演算子は
*（順位 2）と-（順位 1）。低い-が根になり、左が2 * ( 3 + 4 )、右が5。 - 左側では
*で分割し、左が2、右が( 3 + 4 )。 -
( 3 + 4 )は外側の括弧を外して+で分割し、左が3、右が4。 -
readTreeが葉から計算する: 3+4 = 7 → 2*7 = 14 → 14-5 = 9。
-
/ \
* 5
/ \
2 +
/ \
3 4
木は上から作られ、計算は下（葉）から進みます。優先順位の低い演算子ほど根に近く、最後に計算されます。
実行すると、stash の tree には次のダンプが入ります（見やすさのため $Data::Dumper::Indent = 1 と Sortkeys = 1 で出力）。
$VAR1 = {
'data' => '-',
'left' => {
'data' => '*',
'left' => '2',
'right' => {
'data' => '+',
'left' => '3',
'right' => '4'
}
},
'right' => '5'
};
注意点・改善点
入力チェックがないため、不正な式でもエラーにならずに何かしらの結果を返す点に注意が必要です。
表の挙動は、次のスクリプトで確認できます（Mojolicious が必要です。toolmmt ディレクトリに置き、perl try_ast.pl '1/0' '(1+2' '1 2' のように実行します）。
try_ast.pl（確認用スクリプト）
#!/usr/bin/env perl
# 使い方: perl try_ast.pl '2*(3+4)-5' '1/0' ...
use strict;
use warnings;
use lib 'lib';
BEGIN { # 親クラス Tool::mmt::Controller::Mmt の代わり
package Tool::mmt::Controller::Mmt;
use Mojo::Base 'Mojolicious::Controller';
$INC{'Tool/mmt/Controller/Mmt.pm'} = __FILE__;
}
use Tool::mmt::Controller::Ast;
use Mojo::Transaction::HTTP;
for my $calc (@ARGV) {
my $tx = Mojo::Transaction::HTTP->new; # controller は tx を弱参照で持つので保持しておく
my $c = Tool::mmt::Controller::Ast->new(tx => $tx);
$c->req->url->query(calc => $calc);
my $ok = eval { $c->ast; 1 };
printf "%-12s => %s\n", $calc,
$ok ? $c->stash('anser') // 'undef' : "die: $@";
print $c->stash('tree') if $ENV{TREE};
}
| 入力・箇所 | 現在の動き | 改善案 |
|---|---|---|
1/0、1%0
|
Perl が "Illegal division by zero" で die する |
eval で囲んでエラーを返す |
(1+2（括弧の不一致） |
( が根になり、結果が undef |
括弧の対応を事前に検査 |
() |
undef と未初期化値の警告 | 同上 |
1 2（演算子なし） |
分割点が先頭になり、結果は 1 | 演算子が見つからないときはエラー |
a + 1（数値でない） |
a が 0 扱い（警告のみ） |
葉が数値か検査 |
+3（単項プラス） |
左が undef の加算として 3 | 単項マイナスと同様に扱う |
7.5 % 2 |
Perl の % は整数演算のため小数部が切り捨て |
必要なら POSIX::fmod
|
NGE 3（内部記号を入力） |
単項マイナスとして扱われ -3 | トークン化の段階で NGE を拒否 |
コード上の細かい点:
- stash のキー
anserはanswer、juge_priorityはjudge_priorityの綴り違いと思われる。 -
adjustの$s->{_text} = $text =~ s{...}{...}gは置換後の文字列ではなく置換回数を保存している。_textは使われていないので実害はない。 -
treeは Data::Dumper の出力なので、テンプレートで表示するときはエスケープが必要。テンプレートはこのファイルには含まれていない。
振り返りと今後の改善
学習用・小さな電卓ツールとしては素直な実装ですが、不特定の入力を受けるには入力チェックが足りません。
うまくいった点
-
evalを使わず自前で解析しており、入力がコードとして実行される危険がない - 優先順位と結合性が正しい（
8-3-2=3、2**3**2=512、-2**2=-4） - 演算子がテーブル駆動で、
%$opに 1 行足すだけで拡張できる -
(1+2)(2-1)のような省略された掛け算を補う - 木のダンプを出すので、AST の学習教材として分かりやすい
課題
- エラー処理がない: ゼロ除算で die、不正な式でも undef や誤った値を黙って返す
- 効率: 分割のたびに配列を切り出して再走査するので最悪 O(n²)。電卓の式の長さなら実用上は問題ない
- 綴り違い（
anser、juge_priority）、_textのバグ、入力にNGEと書ける点 - このファイルからはテストコードが確認できない
今後の改善（優先順）
-
_astをeval { }で囲み、エラー時はanserにメッセージを入れる - トークン化の段階で、括弧の対応と「数値・演算子が交互に並ぶか」を検査する
- 計算例や境界ケースを
Test::Moreのテストにする
本格化するなら Shunting-yard 法や再帰下降パーサにすると、検査と速度の両方が良くなる。ただし「AST を作ってから計算する」仕組みを見せる目的なら、現在の作りの方が理解しやすい。