はい。これはかなり面白い「初期型AST」です。
今の chabo-dsl の原型につながる部分がかなり見えます。
ざっくり言うと、このコードは
文字列の計算式 → 演算子と数値に分解 → 優先順位を見て二分木を作る → 木を再帰的に計算
という流れです。
例えば、
1 + 2 * 3
を
+
/ \
1 *
/ \
2 3
という木にしてから、
1 + (2 * 3)
として計算しています。
1. 全体の流れ
このコードの中心的な流れはこれです。
ast()
↓
Astnew()
↓
setReOps()
↓
_ast()
↓
adjust()
↓
item_split()
↓
makeTree()
↓
AST完成
↓
readTree()
↓
計算結果
例えば、
$s->Astnew('formula' => '1 + 2 * 3');
とすると、
"1 + 2 * 3"
↓
["1", "+", "2", "*", "3"]
↓
+
/ \
1 *
/ \
2 3
↓
7
となります。
2. $op がこのASTの心臓部
まず非常に重要なのがこれです。
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'],
};
ここには演算子について、
演算処理
優先順位
結合方向
の3つが入っています。
例えば、
'+' => [sub {$_[0] + $_[1]},1,'L']
は、
+
├─ 計算方法 : $a + $b
├─ 優先順位 : 1
└─ 結合方向 : L
という意味です。
* は、
'*' => [sub {$_[0] * $_[1]},2,'L']
なので、
+ → priority 1
* → priority 2
となります。
この「数字が大きいほど強い」という設計です。
3. NGE が面白い
ここは初期ASTの中でも特に面白いところです。
'NGE' => [sub { -$_[0]},4,'R'],
NGE は普通の数学演算子ではありません。
これは、
-1
の先頭の - を、
NGE
という内部演算子に変換するためのものです。
つまり、
1 - 2
の - と、
-2
の - を区別しています。
例えば、
1 - -2
なら、
1
-
NGE
2
というASTにできます。
これは今の言語処理系でも非常に重要な考え方です。
4. ast() は入口
sub ast{
my $s = shift;
my $x = $s->Astnew('formula'=>$s->param('calc'));
$s->stash(anser => $x->{anser});
}
Web画面から、
calc=1+2*3
のように渡されたものを、
$s->param('calc')
で取得しています。
そして、
Astnew(...)
を呼び出しています。
最後に、
$s->stash(anser => $x->{anser});
で計算結果をテンプレートへ渡します。
ちなみに anser はおそらく answer のタイプミスですね。
5. Astnew() がAST生成を開始する
sub Astnew {
my $s = shift;
my $x = {@_};
$s->setReOps();
$s->_ast($x->{formula}) if (exists $x->{formula});
return $s;
}
ここでは、
$s->setReOps();
で演算子を正規表現として準備します。
その後、
$s->_ast($x->{formula})
を呼びます。
つまり Astnew() は実質、
「ASTを作り始めて！」
という初期化処理です。
6. setReOps() ― 演算子を正規表現にする
ここ、Perlらしいです。
$s->{ops} = join ('|',
map {
s/(\W)/\\$1/g;
$_;
}
sort {length $b <=> length $a} keys %$op
);
$s->{ops} = "(".$s->{ops}.")";
例えば演算子が、
-
+
*
/
%
NGE
**
(
)
なら、最終的に概ね、
(\*\*|\+|\-|\*|\/|%|NGE|\(|\))
のような正規表現を作ります。
そして、
adjust()
でこの正規表現を使います。
7. なぜ長い演算子を先にするのか
ここも重要です。
sort {length $b <=> length $a}
つまり、
長い演算子から並べる
という処理です。
例えば、
**
*
があったとします。
正規表現を、
(\*|\*\*)
としてしまうと、
**
を最初の * でマッチしてしまう可能性があります。
だから、
(\*\*|\*)
のように ** を先にします。
これは今の chabo-dsl にも通じる、かなり基本的なTokenizerテクニックです。
8. _ast() が実際のAST構築を開始
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});
}
ここが一本のパイプラインになっています。
adjust
↓
item_split
↓
makeTree
↓
readTree
つまり、
文字列
↓
演算子を分離
↓
トークン配列
↓
AST
↓
評価
です。
9. adjust() ― 式をトークン化しやすくする
sub adjust{
my ($s,$text) = @_;
$text =~ s/$s->{ops}/ $1 /g;
$s->{_text} =
$text =~ s{([\d\)])\s*\(}{$1 \* \(}g;
return $text;
}
例えば、
1+2*3
に対して、
$text =~ s/$s->{ops}/ $1 /g;
を実行すると、
1 + 2 * 3
のようになります。
つまり、演算子の前後に空白を入れています。
10. さらに暗黙の * を入れている
この部分です。
$text =~ s{([\d\)])\s*\(}{$1 \* \(}g;
これはかなり面白いです。
例えば、
(1+2)(2-1)
を、
(1+2) * (2-1)
に変換します。
つまり、
左側が数字または )
+
右側が (
なら、
*
を自動挿入しています。
数学でいう、
2(3+4)
のような暗黙の掛け算をサポートしようとしているわけですね。
ただし、この初期版では対象が
[\d\)]
なので、例えば変数などを考えるとまだ限定的です。
11. item_split() ― トークン配列にする
sub item_split{
my $s = shift;
my $text = shift || $s->{_text};
$s->{item} = [split ' ',$text];
return $s;
}
adjust() 後、
1 + 2 * 3
を、
[
"1",
"+",
"2",
"*",
"3"
]
にします。
この段階ではまだASTではありません。
単なる配列です。
12. makeTree() が一番重要
ASTを実際に作っているのはここです。
考え方は、
式の中から、一番外側にある「最も優先順位の低い演算子」を探して、そこを根にする
です。
例えば、
1 + 2 * 3
なら、
+ priority 1
* priority 2
なので、
+
を根にします。
結果、
+
/ \
1 *
/ \
2 3
となります。
13. 最初に外側の括弧を外す
while($_[0] eq '(' and $_[-1] eq ')'){
例えば、
(1 + 2)
なら、最初と最後が、
(
)
です。
そこで、
shift;
pop;
して、
1 + 2
として考えます。
ただし、
(1 + 2) * 3
の場合は、最初が (、最後が 3 なので、この処理はしません。
14. 括弧の中は演算子検索から除外
ここです。
$r = 0;
for(@_){
++$r if($_ eq '(');
--$r if($_ eq ')');
next if($r or $_ eq ')');
$r は括弧の深さです。
例えば、
1 + (2 * 3)
なら、
1 + ( 2 * 3 )
↑
depth = 1
となります。
depth != 0 の間は、
2
*
3
の * を無視します。
これによって、
1 + (2 * 3)
で、外側の + を根にできます。
15. 最も優先順位の低い演算子を探す
この部分です。
if($s->juge_priority($cur,$prio)){
$prio = $op->{$cur}->[1];
$m = $i;
}
最終的に $m に、
ASTの根にすべき演算子の位置
が入ります。
例えば、
1 + 2 * 3
なら、
index
0 1 2 3 4
1 + 2 * 3
↑ ↑
+ *
+ の優先順位は1。
* は2。
なので + が根になります。
16. なぜ「右側の演算子」を選ぶのか
ここが、
$op->{$cur}->[2]
の L/R と関係しています。
sub juge_priority {
my $s = shift;
$op->{$_[0]}->[2] eq 'R'
? $op->{$_[0]}->[1] < $_[1]
: $op->{$_[0]}->[1] <= $_[1];
}
左結合なら、
<=
右結合なら、
<
になっています。
例えば、
1 - 2 - 3
は通常、
(1 - 2) - 3
です。
つまり、
-
/ \
- 3
/ \
1 2
にしたい。
一方、
2 ** 3 ** 4
は右結合なので、
2 ** (3 ** 4)
にしたい。
そのために L/R が存在しています。
17. - を NGE に変換するところ
ここです。
if($_ eq '-' &&
($i == 0 ||
($_[$i - 1] =~ /^$s->{ops}$/ &&
$_[$i - 1] ne ')'))){
$_[$i] = $cur = 'NGE';
}
例えば、
-3
なら、
-
3
の - は減算ではありません。
だから、
NGE
3
に変換します。
また、
1 * -2
も、
1 * NGE 2
になります。
これによって、
二項演算子 -
と
単項演算子 -
をAST上で明確に分離できます。
18. newNode() がASTノードを作る
sub newNode{
my $s = shift;
return {
data => shift(),
left => shift(),
right => shift()
};
}
つまりASTの1ノードは、
{
data => '+',
left => ...,
right => ...
}
という構造です。
例えば、
1 + 2
なら、
{
data => '+',
left => '1',
right => '2'
}
です。
19. 再帰によってASTが完成する
makeTree() の最後です。
return $s->newNode(
$_[$m],
$s->makeTree(@_[0 .. $m-1]),
$s->makeTree(@_[$m+1 .. $#_])
);
これがAST生成の核心です。
例えば、
1 + 2 * 3
で + が $m だった場合、
makeTree(1)
と、
makeTree(2, '*', 3)
を呼びます。
後者はさらに、
*
├── 2
└── 3
を作ります。
最終的に、
+
/ \
1 *
/ \
2 3
になります。
20. readTree() はASTを計算する
ASTが完成したら、
$s->readTree($s->{root});
です。
ここも再帰です。
sub readTree{
my ($s,$node) = @_;
return $node if(ref($node) ne 'HASH');
まず、
数値
ならそのまま返します。
21. NGE は特別扱い
if($node->{data} eq 'NGE'){
return $op->{$node->{data}}->[0](
$s->readTree($node->{'right'})
);
}
例えば、
NGE
|
3
なら、
readTree(3)
で 3 を得て、
sub { -$_[0] }
に渡します。
結果、
-3
です。
22. 通常の二項演算
次に、
do {
$node->{$_} = $s->readTree($node->{$_})
if(ref($node->{$_}) eq 'HASH')
} for ('left','right');
で、
左の子
右の子
を再帰的に計算します。
例えば、
+
/ \
1 *
/ \
2 3
なら、
*
↓
2 * 3
↓
6
になり、
+
↓
1 + 6
↓
7
となります。
23. 最後の1行
exists $op->{$node->{data}}
? $op->{$node->{data}}->[0](
$node->{left},
$node->{right}
)
: $node->{data};
ここで、
演算子なら演算する
演算子でなければ値を返す
としています。
つまり、
+
-
*
/
%
**
なら $op に登録された関数を呼びます。
一方、
1
2
3
などなら、そのまま返します。
24. 実際に 1 + 2 * 3 を追ってみる
これが一番分かりやすいです。
入力：
1+2*3
① adjust
1 + 2 * 3
② item_split
["1", "+", "2", "*", "3"]
③ makeTree
最も外側で優先順位が低いのは +。
+
/ \
1 *
/ \
2 3
④ readTree
まず右側。
2 * 3
↓
6
次に、
1 + 6
↓
7
結果：
7
25. このASTの特徴
この実装、今見るとかなり「素朴」なんですが、実は非常にきれいです。
特に重要なのは、
Tokenizer
↓
Parser
↓
AST
↓
Evaluator
という現在の言語処理系にも通じる構造が、すでにあります。
この初期版では、
adjust()
item_split()
がTokenizer的な役割。
makeTree()
がParser。
newNode()
がAST生成。
readTree()
がEvaluator。
になっています。
26. 今の chabo-dsl との違い
以前の chabo-dsl の構造と比較すると、かなり興味深いです。
初期版：
Astnew
├─ setReOps
├─ adjust
├─ item_split
├─ makeTree
└─ readTree
現在の発展版では、これがもっと明確に、
入力
↓
Sugar
↓
Tokenizer / Parser
↓
AST Builder
↓
Evaluator
という形に整理されています。
つまり、今の chabo-dsl は突然生まれたものではなくて、
この小さな
Tool::mmt::Controller::Astの発想を育てていったもの
と見ることができます。
特に、
$text =~ s/$s->{ops}/ $1 /g;
や、
$s->makeTree(...)
のように、**「正規表現で式をほぐして、再帰で木を作る」**という思想は、現在の実装につながっています。
そして個人的に一番面白いのは、初期版ですでに
'**' => [ ..., 4, 'R']
と
'NGE' => [ ..., 4, 'R']
を使って、演算子の優先順位と結合方向をデータとして持たせていることです。
これは単なる「四則演算プログラム」から一歩進んで、すでにちゃんと小さな言語処理系のParserになっています。
このコードを資料化するなら、次は 1 - 2 - 3、-2**2、(1+2)*3 の3例を実際に makeTree() の再帰を1ステップずつ追うと、このASTの仕組みがかなり鮮明になります。