ねえパパ、ほとんどのエンジニアは四則演算を計算するプログラムすら書けないってホント？
どうも。「エクセルファイル読んでますか？」でおなじみの（？）アルダグラム テクニカルフェローの蓬莱です。お元気ですか？
え？そんなことより気になる事がある？あ、このタイトルの事ですか。
「四則演算ぐらいできるわ！バカにするな！！」
って青筋がピキってる読者の気配はひしひしと感じてますよ。
「安心してください、感じてますよ！」
まあまあ、一旦落ち着いてこの問題を考えてみてください。
どうですか？できそうですか？
(もちろん javascript の eval 関数みたいなものを使うのは無しです。自作してください。)
この問題ができるアナタ、すばらしいです。もうこの記事の続きを読む必要はないです。
どうしたらいいのか全然わからないよーっ、ひーん。。てアナタも大丈夫です。
「安心してください。問題が難しいんですよ！」
では、この問題がなぜ難しいのか、一緒に考えてみましょう。
例として
4 + (10 - 2 * 3) / (4 / (5 - 3))
を計算することを考えます。
普通に手で計算するとしたら、どうしますか？
- えーっと、まずかっこの中を計算しないといけないから・・
- 10 - 2 * 3 をまずやろっか・・
- 掛け算のほうが先にしないといけないから 2 * 3 = 6 を 10 からひいて・・4か
- で、次はえーっと ( 4 / (5 - 3) ) を計算しないといけなくて・・
- てことは 4 / 2 になるから 2 かな
- で、さっきの 4 から この 2 を割るから、 2 がでてきて・・
- で最初の4に足せば 6だ！できた！
みたいな感じになるんじゃないでしょうか。
というわけで・・
それをそのままコンピューターにやらせればいいのです。
「いやいや・・そうは言っても難しいんじゃないの？」
使えるものは再利用していくスタイル。SDGsです。
でも、問題が難しいという事だけでも気づいてもらえれば、記事を書いた意味があるってもんです。ここまで読んでくれてありがとうございます。
(この記事は結構長いので挫折しそうになったら、スクロールして最後にの部分だけでも読んでくれると嬉しいです）
いきなり話は変わりますが、コンピューターって日本語だとなんて言うかわかります？
答えは「電子計算機」です。
そう、コンピューターはもともと計算をするために作られたので、このような問題を解くために発展してきたのです。
文字で計算式を打ち込んで、それを実行すると答えが出てくる・・なんか馴染みないですか？？
そう。それは、まさにプログラミング言語の原型なのです。（大体どんなプログラミング言語でも四則演算はありますよね）
コンパイラってなんだろう
ところで、みなさんコンパイラという言葉は耳にしたことはあるでしょうか？なんなら日々使っている人もたくさんいるでしょう。
じゃあ、コンパイラを作ったことがある人はどれくらいいますか？
大学などでコンピューターサイエンス（計算機科学って日本語にするとダサいですよね）を履修した人はやった事あるんじゃないでしょうか？
（やったけど全く記憶がないという人も大勢いそうですが・・）
で、さっきの問題、コンパイラを作れる人ならできちゃいます。
「で、コンパイラって何なのよ？」
と思われるでしょうが、コンパイラとは大雑把に言うならば、
「プログラムをコンピューターが処理しやすい形式に変換するプログラム」
と言うことになります。
「抽象的なことばっかり言ってるんじゃねえぞ！プログラムを変換するプログラムだと？！わけわかんねえよ！」
大丈夫です。まだ慌てないでください。
むしろ慌てるのはこれからです。だって、これからコンパイラを作るためのコンパイラも紹介するんですから..
「ファッ！？」
ってなってます？アナタ今いい顔してますよ！
コンピューターが理解しやすい形式って何よ
さっきの四則演算ですが、コンピューターが理解しにくいのはなぜでしょうか？
「どこから計算を始めたらいいのかわからない」
ってのが原因じゃないでしょうか？人間は
- 掛け算・割り算は、足し算・引き算より先に計算する
- かっこはひとまとまりとして計算する
- かっこは開きかっこと対応する閉じかっこが必要
みたいなルールを知っていてそれを踏まえて計算するから正しい順序で計算できるわけですね。
さっきの式の一部 10 - 2 * 3をコンピューターが理解しやすい形式に直すとしたらこんな感じになります
10 2 3 * -
「何だこれ？」
って人もいるでしょうし、
「あ、知ってる！逆ポーランド記法だ！」
って人もいるでしょう。
実はこの形式、コンピューターにとってはめちゃくちゃ読みやすいんですよ。
実は、この形式には計算順序がもう埋め込まれているので、掛け算と引き算のどっちを先に計算するかなんて考える必要もないんです。
嘘みたいだろ・・？本当なんだぜ・・？
コンピューターが計算をする仕組み
じゃあ実際にそれをどうやって計算するのか説明しましょう。
さきほど、手で計算をするときに、途中の計算結果をメモって後から使ったりしましたよね？
2 と 3 をかけて 6 だから、それを 10 から引いて・・・みたいに。
コンピューターが計算するときにも同様に計算の途中結果をメモしておく仕組みが必要です。
これにはスタックを使うのが一般的です。有名なデータ構造なので知っている人も多いでしょう。
「知ってる知ってる。スタックオーバーフローとかのあれやろ？理解。理解。」
って人のために説明すると・・・
どんなデータがメモされているかは気にせず、上にポンポンとデータを積んでいく感じです。データを取り出すときも一番上からしか取り出せません。書類の山みたいなイメージですね。
コレがスタックだ！完全に理解した！
スタックさえ用意してしまえば、あとはむちゃくちゃ簡単なルールで計算できます。
式を左から順番に一つ読んでいって
- 数字が来たらそれをスタックに積みます
- 演算子 (* とか - ) が来たらスタックから２つ値を取り出して計算し、結果をスタックに積みます
- 最後まできたら、スタックに残っている値を見ます。それが答えです。
以上。
「まじかよ・・」
マジです。コレだけでどんな複雑な計算式も順序を気にする必要なく計算できます。
先程の例を計算してみましょう。
これがスタックマシンだ！Virtual Machine = VM と呼ぶこともあります
先ほどの例なら、こうするだけで機械的に計算できちゃいます。上の図を見ながら読んでみてください。
10 が来た → 数字なので積もう
2 が来た → 数字なので積もう
3 が来た → 数字なので積もう
* が来た → ２個取り出して計算して積もう
- が来た → ２個取り出して計算して積もう
最後に残ったのが答え
答えの4ができてますね！
こういうスタックを使って計算を実行するプログラムをスタックマシンと呼びます。(こんなプログラムだと簡単にかけそうですよね？）
ちなみに JVM や WebAssembly みたいな“仮想マシン”の多くも、まさにこの方式で動いていますよ。
（普段アナタが触っている x86 や ARM の実CPUはレジスタ方式が主流ですが、「命令を一つずつ読んで処理する」という骨格は同じです）
この形式が計算しやすいことはわかった。けど元の式をどうやって変換するの？
やっとここまでたどり着きましたか・・
元の式を別の形式に変換する、つまり・・コンパイラの作り方を知りたい、そうおっしゃりたいわけですね？
「いや・・べ、別に・・オレそんなつもりじゃ・・」
もうー、照れないでください！ちゃんと教えてあげますから！
確かに何も使わずに徒手空拳でコンパイラを作るのは難しいです。けど、世の中にはコンパイラを作るためのツールがあるんですよ。
パーサージェネレーターとかコンパイラコンパイラとか言われてるんですけどね。（コンパイラを作るためのコンパイラ！です）
Unix で古代から使われている有名なものに yacc というものがあります。
ちなみに yacc は Yet Another Compiler Compiler の略です。有名なC言語の初期の処理系とかもyaccを使って作られたそうです。
「ツールを使うなんてずるいじゃないか！完全自作しろよ！」
なんて過激派の人がいたらすいません。先に謝っておきます。（きっとそういう人は普段のプログラムはアセンブラ言語を手書きしてから16進数に手で変換しているのでしょう）
yacc は現在はその後継の bison が広く使われています。 yacc の他にはANTLR というツールもあります。是非色々調べてみてください。
なおツールを使わずにコンパイラを作る方法もあります。再帰降下パーサーでググると幸せになれるかも知れません
yacc をつかって構文解析してみよう
というわけで（？）お待たせしました。いよいよ yacc の出番です。
文法を定義してみよう
yacc に何をさせるかというと、まず文法を教えてあげます。「文法」とか言うと身構えちゃいますが、要は式ってこういうものだよという定義を書くだけです。
こんな感じ。
%left '+' '-' /* 足し算・引き算はあとまわし（優先度ひくい） */
%left '*' '/' /* 掛け算・割り算が優先（こっちが下=強い） */
%%
expr : expr '+' expr /* 式とは「式 ＋ 式」である */
| expr '-' expr /* または「式 − 式」である */
| expr '*' expr /* または「式 × 式」である */
| expr '/' expr /* または「式 ÷ 式」である */
| '(' expr ')' /* または「( 式 )」である */
| NUM /* または ただの数字である */
;
「なんかいきなり出てきた。怖い！」
気持ちはわかりますが、 expr がいっぱい出てくる辺りを眺めてみてください。
「式とは、式＋式であり、式×式であり、(式)であり、ただの数字でもある」
なんか禅問答みたいですが、これが式の正体です。
式の中に式が出てくる、この入れ子構造こそがカッコや優先順位を表現できる秘訣なのです。
次に注目すべきは一番上の %left から始まる2行。
これ、「掛け算・割り算の方が、足し算・引き算 よりも優先度が高い」って宣言してるんです。
(ちなみに %left は演算子が左結合するという意味だけど今は気にしなくてもいいよ)
「え、それだけ？」
それだけです。さっき手計算で掛け算のほうを先にしないとダメだしとかウンウン悩んだあの順序、たった2行で書けちゃいました。
で、そのルールに基づいた構文解析を yacc がやってくれるのです。
（ちなみに yacc は実際にはこれを逆向きにたどります。入力の式 10 - ( 2 * 3) の方から部品をまとめ上げて expr にたどり着く＝ボトムアップです。この「下から組み立てる」動きが後で重要になってきます。）
おかしな式はちゃんとエラーになるよ
ここで嬉しいお知らせです。
冒頭の問題、こんなのありましたよね。
" 7 - 32 * 4 + 3 / ( 21 + 3 - ( 4 ) " → ERROR
カッコが閉じてない不正な式です。「カッコの対応をチェックするコードを自分で書かなきゃ…」と思いました？
書かなくていいんです。
さっきの文法、よく見てください。'(' expr ')' ——開きカッコには必ず閉じカッコがセット、としか定義していません。
だから閉じカッコの足りない式は文法的にこの世に存在しえない式になり、yacc が生成したパーサーは「そんな式知らんがな」とエラーを出してくれるんです。
（ルールを適用しても答えにたどり着けないイメージ）
エラーが起きたとき yacc は yyerror という関数を呼んでくれるので、そこで ERROR と出力すれば仕様どおり。
「文法を定義しただけで、エラー検出までタダでついてくる」
yacc さんサマサマですね。
「もうたまらんっ！（謎）」
yacc で計算できちゃうじゃん
アクションを使って直接計算しちゃうぜ
文法を定義したらパーサー（構文解析器）はできました。
でも今のままだと式として正しいか判定するだけ。せっかくなので計算もさせましょう。
yacc では各ルールの後ろに { } で「アクション」(＝やってほしい処理)を書けます。
expr : expr '+' expr { $$ = $1 + $3; } /* 結果 = 左 + 右 */
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '(' expr ')' { $$ = $2; } /* カッコの中身がそのまま結果 */
| NUM { $$ = $1; } /* 数字はその値そのもの */
;
呪文みたいな $$ とか $1 は何かというと、
-
$1$3… そのルールの1個目・3個目の部品の値（expr '+' exprなら$1は左のexpr、$2は + 、$3は右のexpr） -
$$… このルール自身の計算結果
つまり expr '+' expr { $$ = $1 + $3; } は
「左の式と右の式が出そろったら、足してそれを自分の値にして」
という意味です。
…はい、これで電卓の完成です。
「ファッ！？ これだけ！？」
これだけです。
アナタの与えた式は、式の組み合わせでできていますが、それら式の値を芋づる式に計算して結果を出してくれる感じになります。
優先順位もカッコも yacc がよしなにやってくれるので、「どこから計算するか」をこちらは1ミリも気にしていません。さっきあれだけ悩んだ計算順序、完全に yacc に丸投げできちゃいました。
冒頭の問題を解くだけなら、実はここで完成です。
実際に作って実行してみるとこんな感じになります
yacc でコンパイルもできちゃう？
直接計算せずに逆ポーランド形式で出力しちゃうぜ
さて、さっきは構文解析のその場で計算しちゃいました。が、ここでちょっとだけ意地悪をします。
計算そのものをする代わりに、逆ポーランド記法を出力させてみましょう。
そう、記事の前半で出てきた 10 2 3 * - のあれです。
ここで yacc の性質がめちゃくちゃ効いてきます。
yacc は 式をボトムアップ（部品から組み立てる順番）で解析します。
そしてアクションは子が全部そろってから呼ばれる。
ということは下のようにアクションを書けば・・
expr : expr '+' expr { printf("+ "); } /* 子(左exprと右expr)のあとに + を print */
| expr '-' expr { printf("- "); } /* 同様に - を print */
| expr '*' expr { printf("* "); } /* 同様に * を print */
| expr '/' expr { printf("/ "); } /* 同様に / を print */
| '(' expr ')' /* カッコは何も出力しない！ */
| NUM { printf("%d ", $1); } /* 数字はその場で出力 */
;
- 「演算子は子のあとに出力」
- 「数字は出てきたら即出力」
という風に printf が実行されるので、結果的に逆ポーランドの順番に並んじゃいます。
というわけで、
4 + (10 - 2 * 3) / (4 / (5 - 3))
を食わせると…
4 10 2 3 * - 4 5 3 - / / +
が出てきます。カッコ、きれいさっぱり消えてますね？
逆ポーランドには計算順序がもう埋め込まれているので、カッコなんてもう要らないんです。
嘘みたいだろ…？ 本当なんだぜ…？
これはもう立派なコンパイラです。
「式」という人間語を、「逆ポーランド」というコンピューター向きの形式に変換するプログラム——まさに記事の最初で言った定義通りです。
後はスタックマシンで実行だ！
そろそろ息切れしてきましたか？大丈夫です。ここまで来たらゴールは目前。出てきた逆ポーランドの式
4 10 2 3 * - 4 5 3 - / / +
を、さっき作ったスタックマシンに流し込むだけです。覚えてますか、あのむちゃくちゃ簡単なルール。
- 数字が来たら積む
- 演算子が来たら2つ取り出して計算して積む
- 最後に残ったのが答え
機械的に回すと…ちゃんと 6 が出てきます。
（コードは簡単にかけるので省略します）
そしてアナタがやったことをまとめると・・こんな感じになります
「ソースコードをコンパイルして、VM で実行する」
——規模こそ違えど、アナタが普段使っているプログラミング言語の処理系とまったく同じ構造です。
四則演算しかできないオモチャですが、本質はガチなんですよ。
おめでとうございます！
アナタはもう四則演算を計算するプログラムを、コンパイラ + VM (スタックマシン) 構成で書けるエンジニアです。パパ、堂々と胸を張れますね。
この通りyacc は非常に強力なツールです。
ここから更に進めてガチのプログラミング言語を作ることまでできちゃいます。
もっと詳しく知りたい人には
yacc の実践方法を学ぶためにおすすめの本を紹介します。
非常に古い本ですが、カーニハンの “The UNIX Programming Environment” という本があります。日本語版の新版 (邦題: UNIXプログラミング環境) もあります（そっちのほうが安いですが、コード例に誤字があったりして嵌まる可能性大です）
この本の8章 ”Program Development”がまさに yacc を使って簡単な計算機から始めてそれを拡張してプログラミング言語を作る演習となっています。
弊社ではこの本を手にコンパイラの作り方を楽しく（？）学んでおります。 （自分は前任者から引き継いで講師をやってます）
最後に
「このAIがなんでもやってくれる時代に、なんでコンパイラなんか作らないといけないんだよ！」
みたいに思ってる人も大勢いるでしょう。
けど、コンパイラの仕組みを知らないということは、プログラムがコンピューターでどのように実行されているかわからないと言っているのと同じです。
そんなあなたは冒頭の質問にどう答えます？
「パパはね、プログラムがどうやって動いているかわからないんだ。基本的な四則演算すらね。なんならプログラムも全部AIに書いてもらってるんだ。何が起きているのか全然わかんない。すごいだろ？」
って答えるんですか？
それだけじゃありません。実際に業務で式などを評価して計算しないといけないって事は意外とあったりします。そんなとき、全く方針も立てられなかったら？
（え？エクセル関数をフロントエンドで実行したい？誰ですか、そんな変態は。帰ってください。個人的には好きですが。）
あと仕組みを理解していないと簡単な変更すらできません。（例: + - を * / よりも優先して計算するようにルールを変えたいって言われたらどうする？）
自分が想像もできないことは AI に頼むのも難しいですしねー
エンジニアの価値の本質が問われ始めている昨今ですが、強く生き抜くチカラを付けていきましょう！
蛇足
自分の学部の指導教官だった湯浅太一先生の著書を紹介しておきます。タイトルはそのものズバリ「コンパイラ」。実践よりも理論寄りの本ですが、深く理論を理解したい人にはおすすめです。
https://www.amazon.co.jp/情報系教科書シリーズ-コンパイラ-湯淺-太一/dp/4274216209
いやー、当時は全くわからなかったなぁ。（今もわかっているとは言っていない汗）
株式会社アルダグラムのTech Blogです。 世界中のノンデスクワーク業界における現場の生産性アップを実現する現場DXサービス「KANNA」を開発しています。 採用情報はこちら: herp.careers/v1/aldagram0508/
Discussion
あの...yaccの作り方は(;^ω^)