中置記法

提供: miniwiki
移動先:案内検索

テンプレート:Infobox notation 中置記法(ちゅうちきほう、infix notation)とは、数式やプログラムを記述する方法(記法)の一種。演算子を操作対象の中間に記述することから、このように呼ばれる。

その他の記法として、演算子を操作対象の前(左)に記述する前置記法(ポーランド記法)、演算子を操作対象の後(右)に記述する後置記法(逆ポーランド記法)がある。

四則演算など初歩的な算術においては、もっぱら中置記法が多用されている。

多義性

次のようなBNFの構文規則群で定義される中置記法の文法について考える。

<expr>  = <infix> | <num>
<infix> = <expr> <op> <expr>
<num>   = 0 | 1 | 2 | 3 | 4 | ...
<op>    = + | ー | × | ÷

この文法には多義性(ambiguity。曖昧さ、とも言うが、「曖昧」という語には「輪郭がはっきりしない」というような意味もあるがそちらの意味ではない)がある(「曖昧な文法」の記事を参照)。たとえば、

"1 - 2 + 3"

が、この構文規則からは「(1 - 2) + 3」と「1 - (2 + 3)」の、どちらに相当する構文木にも構文解析できてしまう。

加算のような結合法則の成り立つ演算だけが対象である場合など、むしろ便利である場合もあるが、一般の場合には補助的なカッコを多用して明示するなどの必要がある。算術の四則演算では、加減算の両方が使われている場合などについて、左から右という規則で意味の一意化が図られている。また、カッコの省略を意図して、加減算に対する乗除算の優先という規則も、もっぱら付加される。

yaccなどでは、BNFによる定義に、さらに「演算子の優先順位」と「演算子の結合性」(結合法則#プログラミング言語を参照)に相当する規則を付加することができ、これは大変に使い良い機能である。特に(yaccは違うが)再帰下降構文解析などLL法の構文解析では、四則演算の式のような左から右の順をナイーブに実装すると左再帰の問題があるので、問題を避けて簡潔に定義する方法があると良い。

関連項目