逆ポーランド記法における単項演算子などの処理

開いていただきありがとうございます。

質問内容は題名の通りなのですが、
中置記法の式を逆ポーランド記法に変換して計算を行う際に単項演算子をどのように扱うかで悩んでいます。+-などのように文脈に応じて意味合いが変化するものもあり、もうひとつスマートに処理することができません。
また前置・後置インクリメントなどに対応するとしたらなおざりに処理するわけにもいきませんし、三項演算子に至ってはどのように処理すればいいのかさっぱりです。

電卓に留まらず、簡単な処理系に組み込むという前提で、これらをどのように使えばよいかご教示いただければと存じます。

No.3 回答者： Tacosan 回答日時： 2010/02/14 23:23

加減と乗除で分けているのは, まさに言われる通り「優先順位」のためです. 優先順位を文法で表すためには, このように分けて書く必要があります. 実際, 例えば C の規格を見るとこのようにわらわらと並んでいます.

で, 再帰下降パーザではそれぞれの構文要素に対してそれを処理する関数があるので, 結局「優先順位ごとに関数がある」ということになります. 確かに気持ち悪いところですが. 再帰下降パーザを選んでしまうとなかなか回避できません. YACC なら (あるいは演算子順位文法なら) 逃げられるところなんですけどね.
本ですか.... う～ん, 振っておいてなんですがなにがいいかはよくわかんないです.... ただ, YACC を使ってないものだとほとんど再帰下降パーザを使っていると思うので, 実際に構文解析する部分はほとんど同じだと思いますよ. もちろん, 構文解析の前の字句解析の部分とか, あるいは構文解析した結果をどのように保存するかがものによって違うので, その違いが構文解析部分の実際に影響します.

No.2 回答者： Tacosan 回答日時： 2010/02/13 00:26

この辺は「コンパイラなりインタプリタなりを作る」っていう本だとしばしば書かれてます (お値段は 2000～3000円くらいから: ただし「構文木」の話はしないことも多い). で, その手の本だとだいたい再帰下降パーザを作るって話になるし, そっちが普通なのでそっちで説明してみる.

いずれにしても「正しい式とはどのようなものか」を決めないとダメなので, そのために「文法」を定義します. これは先人の知恵として
<式> ::= <項> (('+'|'-') <項>)*
とすることが多い. これは「式というものは, 項のあとに ±項 という形が 0個以上ある」という意味. この文法に対応して処理する関数を作ります. 文法から素直に作ると
式() {
項()
while (次が '+' か '-') {
項();
+/- を適切に出力
}
}
という形になります. じゃあ「項」ってなんだ, というと
<項> ::= <因子> (('*'|'/') <因子>)*
とするのが普通. これに対応して関数があるんだけど実質的に式と同じなので省略.
最後の「因子」は, ここでは「定数か単項演算子がつくかかっこのある式」ということにしておくけど
<因子> ::= 定数 | ('+'|'-') <因子> | '(' <式> ')'
となって. これに対応する関数は
因子() {
if (定数) {
素直に出力
} else if (次が '+' か '-') {
因子();
単項の '+'/'-' を出力
} else if (次が '(') {
式();
if (次が ')' じゃない) {
エラー
}
} else {
エラー
}
}
という感じ. 実質的な処理は因子の中にあるので, これだけ大きくなっています.
「次が」という条件判断が多いので, 「次のトークン」を先読みしておく必要があります. 上の関数には書いてないけど, 適当なところで読込む処理を入れなければなりません.
最初にも書いたように, なぜか言語処理系を作るって趣旨の本がいろいろあったりするので適当に眺めてみてもいいかもしれません.

この回答へのお礼

遅くなってしまい申し訳ございません。

文法の定義をそのまま関数にするのですね。
もうひとつ理解できていない節があるのですが、加減と乗除とで別定義を設けているのは優先順位ゆえでしょうか？
すると演算子の優先度が10段階ある場合は、似たようなものが10個は必要……？ 少し考えてみます。

確かに専門書を買うのがてっとり場合のでしょうが、
自分のような初学者でも、簡単にとは言わずともついていけるような内容で、
かつ肝心な部分をYACCに投げていない本をご存じでしたら教えてくださると助かります。
田舎在住なもので、書店におかれている限りは確認したのですが、冒頭から意味不明か「YACCを使いましょう」しか見当たりませんでした。

お礼日時：2010/02/13 20:57

No.1 回答者： Tacosan 回答日時： 2010/02/11 18:52

現在のところどのような処理をしているのでしょうか? 簡単に書いてもらえると説明がしやすいです.

一般には「中置記法の式」に対して適切な構文を定義し, それを解析するパーザを用意します. 手で書くなら LL から再帰下降パーザが簡単でしょうか. あるいは YACC/LEX (BISON/FLEX) というオプションもありますし, 数式に限定していいなら演算子順位文法で定義することもできます.

この回答への補足

現在は単なる電卓アプリケーションであるため、式あるいは括弧内の冒頭が単項+-演算子の場合は0を挿入することで強制的に二項演算子扱いしています。
学習目的であるためYACCなどは使わずにすべてを自作することを目標としているのですが、大抵の資料では知りたい部分がYACC任せとなっており（それが実用的であることは理解しています）、また学習目的でYACCを利用しないという趣旨のものでも仕様として二項演算子以外は削除されているものがほとんどです。
かといって構文木作成などをじっくりと解説した参考書はレベル的にもお値段的にも手が届かないかなーと。

補足日時：2010/02/11 19:59