コンパイラを作ろう その2
「中置記法から逆ポーランド記法へ」
前回は逆ポーランド記法をプログラムで処理する方法をやりました。
しかし、全ての数式を逆ポーランド記法で書かなければいけないとなると、これはアセンブラと何が違うのかという話になってきてしまいます。
そもそも人間が直感的にわかりやすいプログラムを書くために高級言語を使おうというのに、その高級言語がわかりにくかったら本末転倒です。
逆ポーランド記法がプログラムで処理しやすいのなら、普通の中置記法を逆ポーランド記法に変換すればいいじゃないか、というのが今回の話。
さて、言葉で説明するより実際にやってみたほうがわかりやすいと思うので例を一つ。
a+b*c+d
この計算では当然最初に行われるのは積算です。その後、加算が行われますが、加算が二つ存在します。この場合、優先度は最初に出てきた（つまり左側）の加算の方が高くなります。
これを踏まえて、この例をカッコでくくってみましょう。
((a+(b*c))+d)
ここからわかるように、カッコがつくのは演算数の右か左になります。左につくのは左カッコ、右につくのは右カッコです。
優先順位が最大である * の部分にかかる演算数を抜き出してみると、このようになります。
+(b*
*c)+
つまり、ある演算数があったとすると、その演算数の両側の演算子を調べ、演算子の優先順位が高い方とは逆側にカッコをつければOKということになります。
ここで問題となるのはカッコがついている場合はどうなるのか、ということです。
上記の抜き出した部分にはありませんが、演算数 c の部分は実際にはこのようになっています。
*c))+
これを考えるにはこの部分だけをもってきても意味がありません。
+(b*c))+
ここまで持ってきて正解です。つまり、(b*c) が演算数となるわけです。
この場合、二つの + が存在し、優先度は左側の + の方が大きくなります。故に右カッコになるわけです。
これらのことから最初の式にカッコをつけるアルゴリズムをみてみましょう。
まず、最初に左カッコをつけます。全く何もない状態では比較ができないためです。
(a+b*c+d
次は a ですが、これは演算数です。その次は + で、これは演算子。演算数を間にはさんで演算子同士（カッコも演算子と考える）の比較をします。カッコは常に全ての演算子より優先度が低いと考えると、
((a+b*c+d
こうなります。次は演算数、その次は演算子で、ここでも比較を行います。
((a+(b*c+d
次は演算数 c の両側比較。
((a+(b*c)+d
最後の + と最初の + を比較して
((a+(b*c))+d
最後に右カッコが存在するものと仮定すると
((a+(b*c))+d)
となり、優先度にあわせてカッコをつけた式と一致します。
あとはこのカッコのネストが深いところから計算していけばOKなのですが、これでは逆ポーランド記法になりません。
しかし、このアルゴリズムを利用することで逆ポーランド記法を作成することができます。アルゴリズムは以下のようになります。
１．演算数はそのまま出力する。
２．演算子がきたらスタックの演算子と比較する。今回の演算子の優先度が高ければ演算子をスタックに積む。スタックの演算子が高ければスタックの演算子を取り出し、出力する。今回の演算子がスタックに積まれるまでこれを実行する。
３．１、２を最後まで繰り返す。
気をつけなければならないのはどのような計算式が来たとしても常に最初と最後をカッコでくくっていると見なすことです。なので、必ず一番最初の演算子は左カッコということになります。
では、このアルゴリズムで実際にうまく行くか試してみましょう。
| 入力 | ( | a | + | b | * | c | + | d | ) | ||
| スタック | ( | ( | (+ | (+ | (+* | (+* | (+ | ( | (+ | (+ | ( |
| 出力 | a | ab | ab | abc | abc* | abc*+ | abc*+ | abc*+d | abc*+d+ |
以上です。結果は出力の一番最後ですね。これは元の数式を逆ポーランド記法にしたものと一致します。
さて、ここで問題となるのがカッコの扱い。元の数式にそもそもカッコがあった場合、このアルゴリズムだけでは破綻します。
カッコを扱う場合は以下のアルゴリズムを追加しましょう。
２の補足．左カッコが来たら優先度は無視して必ずスタックに積む。右カッコが来たら通常の優先度チェックを行うが、左カッコがスタックの最上位に来たら左カッコをポップして自分も消える。
これで問題ありません。実際にうまく行くかどうかは各自で調べてみてください。
なお、今回はカッコ以外は全て2項演算子でしたが単項演算子（符合反転の - とか）の場合でも処理は変わりません。
では、サンプルです。
基本的に前回と変わりません。入力として中置記法の式を与えればOKです。
スペースは入れないでください。また、カッコの使用、符合反転の - の使用も可能です。
逆ポーランド記法での形式も一緒に表示されますが、この中で (-) と表示されているのが符合反転の - です。
今回はこれで終了です。
次回はスクリプトの仕様とかちょっと考えたいと思うので、少々…いや、かなり時間がかかるものと思ってください。
いきなりこのコーナーが停滞してしまうわけですが…許して。