これはQiita 15周年記念カレンダー Advent Calendar 2026の17日目の記事です。
今年、ちっちゃなインタプリタができた。
もちろん、最初から作ろうと思っていたわけではない。壮大な計画があったわけでもない。数式パーサーをいじっているうちに、気がつけばそうなっていた。
始まりの数式パーサー
AIに昔作った数式パーサーを見てもらったところ、べき乗は右結合であると教えてもらった。
四則演算は左結合、べき乗・代入演算子は右結合──そう知って、べき乗の結合規則を修正し、代入文を追加して変数を導入した。これが、私の「車輪の再発明」のはじまりだった。
小さな数式パーサーから始まった
数式パーサーと言っても大げさなものではない。まずは次のようなシンプルな構造からスタートした。
- トークナイザー:計算式の文字列から正規表現で演算子を検索し、演算子と数値を区切って扱いやすくする。
- パーサー:トークナイザーで整理した数式を、数値や演算子などの要素に分解する。
- AST構築:パースした要素から、演算子の優先順位に従ってツリー構造を構築する。優先順位が最も低い演算子が根(ルート)になる。
- AST評価・実行:構築したASTを評価・実行して答えを計算する。
(※詳細は Ast.pmを読む:数式からASTを構築して計算するまで をご覧ください)
結合規則:< と <= の1文字の差
きっかけになった「べき乗は右結合」の話を、木で見てみる。
同じ優先順位の演算子が並んだとき、どのようにグループ化するかを決めるのが 結合規則 だ。
10 - 3 - 2 → (10 - 3) - 2 = 5 左結合
2 ** 3 ** 2 → 2 ** (3 ** 2) = 512 右結合
このパーサーでは、式の中で 優先順位が最も低い演算子 を木の根(ルート)にして、その左右を再帰的に組み立てていく。
では、優先順位が同じ演算子が複数あった場合、どれを根にするのか。ここで結合規則が決まる。
- 左結合:一番 右 の演算子を根にする → 左側が先に計算される
- 右結合:一番 左 の演算子を根にする → 右側が先に計算される
実際に組み立てた AST を出力すると、こうなる。
10 - 3 - 2 2 ** 3 ** 2
- **
/ \ / \
- 2 2 **
/ \ / \
10 3 3 2
(10-3)-2 = 5 2**(3**2) = 512
木の深いところから計算されるので、左結合なら左の 10 - 3 が先、右結合なら右の 3 ** 2 が先になる。
コードで見ると、この違いは比較演算子の 1文字 だけだった(コメントは説明のために加えたもの)。
sub judge_priority {
my $s = shift;
$op->{$_[OPERATOR]}->[ASSOCIATIVE] eq RIGHT
? $op->{$_[OPERATOR]}->[PRIORITY] < $_[PRIORITY] # 右結合:最初に見つけたものを残す
: $op->{$_[OPERATOR]}->[PRIORITY] <= $_[PRIORITY]; # 左結合:後から来た同順位で上書き
}
式を左から順に見ていき、優先順位が同じ演算子が来たとき、
-
<=なら上書きする → 最後(一番右)の演算子が根になる → 左結合 -
<なら上書きしない → 最初(一番左)の演算子が根になる → 右結合
AI に「べき乗は右結合ですよ」と言われて直したのは、突き詰めるとこの = を1つ取ることだった。
言語処理系は、こういう1文字に意味が詰まっている。
少しずつ言語に近づく
べき乗や代入演算子が右結合だと知って実装していくと、今度は「ユーザー関数が欲しい」、関数ができたら「再帰には止まる条件が要るから比較演算子が欲しい」という具合に、次から次へと必要なものが増えていった。
「これも欲しい」「あれも欲しい」と機能を追加していくうちに、変数、関数、配列、ハッシュ、再帰処理などが使えるようになり、小さな言語処理系として形になってきた。
そこで、この処理系を chabo-dsl と名付けてGitHubで公開 した。
実際に動かすとこんな感じ
ここまで足してきた機能を使うと、再帰関数が書ける。
階乗
fact(n) = n < 2 ? 1 : n * fact(n - 1);
fact(10);
上の2行を fact.chabo に保存して実行する。
$ perl script/chabo.pl fact.chabo
3628800
関数定義は 名前(引数) = 式; という形式で、1行で書ける。
再帰には「どこで止まるか」が必要なので、比較演算子 < と三項演算子 ? : が欠かせない。
フィボナッチ数列
fb(x, y, z) = x < 1 ? z : fb(x - 1, y + z, y);
join(",", map(fb($_, 1, 0), 0..10));
0,1,1,2,3,5,8,13,21,34,55
map や join、範囲演算子 0..10 は、Perl を書いている人ならおなじみの形にした。
日本語でも書ける
Sugar.pm を通すと、同じフィボナッチをこう書ける。
【関数定義:フィボナッチ数を計算する関数】
・回数と中間値と答えでフィボナッチを計算するには
もし回数が1未満の場合は、答えを返す
以外はフィボナッチを計算する(回数-1,中間値+答え,中間値)。
join(",",map(フィボナッチを計算する($_,1,0),0から10));
0,1,1,2,3,5,8,13,21,34,55
エンジン本体は日本語に依存していない。Sugar.pm が日本語の文を、内部の式に変換しているだけだ。
ブラウザで試せる Webデモ もある。
Perlで作るという選択
文字列操作が得意で、正規表現も書きやすい。
今さら感はあるかもしれないが、やっぱり私はPerlが好きだ。
Webの黎明期、CGIを書くために使い始めたPerl。15年以上経った今でも、こうしてPerlで新しいものを作って遊んでいる。
技術や環境は変わっても、コンピュータを使って何かを作る楽しさは変わらない。
今回は、以前Perlで書いた数式パーサーを、この言語処理系へと成長させた。
最初は100行ほどだった数式パーサーは、本体(Ast.pm)655行+演算子テーブル(Op.pm)166行の言語処理系へと発展した。変数や関数、再帰処理まで実装しても、この程度のコード量に収まっている。
改めてPerlの表現力の高さを感じた。
処理の全体を自分で追うことができ、コード量もコンパクトに収まっているため、言語処理系の教材としても良いのではないかと思っている。
車輪を再発明して分かったこと
- 普段何気なく使っているプログラミング言語の仕組みが見えてくる。
- AIにドキュメントを書いてもらうと、AIも間違えることがあるとわかる。
- やっぱり、動くものを作るのは最高に楽しい。
車輪を再発明したからといって、世の中に新しい車輪が生まれたわけではない。
それでも自分の手で作ってみると、いつもの a = 1 + 2 ** 3 の裏で何が起きているのかを、少しだけ実感できる。
そして何より、その過程が楽しい。
今年はそんな「車輪の再発明」を存分に楽しんだ一年だった。